आंशिक मिलान द्वारा भविष्यवाणी: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
आंशिक मिलान द्वारा [[भविष्यवाणी]] (पीपीएम) [[संदर्भ मॉडलिंग]] और | '''आंशिक मिलान द्वारा [[भविष्यवाणी|पूर्वानुमान]] (पीपीएम)''' [[संदर्भ मॉडलिंग|कांटेक्स्ट मॉडलिंग]] और पूर्वानुमान पर आधारित अनुकूली सांख्यिकी डेटा संपीड़न तकनीक है। पीपीएम मॉडल स्ट्रीम में अगले प्रतीक की पूर्वानुमान करने के लिए असम्पीडित प्रतीक स्ट्रीम में पिछले प्रतीकों के सेट का उपयोग करते हैं। पीपीएम एल्गोरिदम का उपयोग [[क्लस्टर विश्लेषण]] में पूर्वानुमानित समूहों में डेटा को क्लस्टर करने के लिए भी किया जा सकता है। | ||
== सिद्धांत == | == सिद्धांत == | ||
पूर्वानुमान सामान्यतः प्रतीक रैंकिंग तक सीमित कर दी जाती हैं. प्रत्येक प्रतीक (एक अक्षर, बिट या डेटा की कोई अन्य मात्रा) को संपीड़ित करने से पहले रैंक किया जाता है, और इस प्रकार रैंकिंग प्रणाली संबंधित कोडवर्ड (और इसलिए संपीड़न दर) निर्धारित करती है। इस प्रकार कई संपीड़न एल्गोरिदम में, रैंकिंग संभाव्यता द्रव्यमान फ़ंक्शन अनुमान के समान है। पिछले अक्षरों को देखते हुए (या कांटेक्स्ट दिया गया है), प्रत्येक प्रतीक को संभावना के साथ निर्दिष्ट किया गया है। उदाहरण के लिए, अंकगणित कोडिंग में प्रतीकों को उनकी संभावनाओं के आधार पर पिछले प्रतीकों के बाद प्रदर्शित होने के लिए क्रमबद्ध किया जाता है, और पूरे अनुक्रम को एकल अंश में संपीड़ित किया जाता है जिसकी गणना इन संभावनाओं के अनुसार की जाती है। | |||
प्रत्येक प्रतीक (एक अक्षर, बिट या डेटा की कोई अन्य मात्रा) को संपीड़ित करने से पहले रैंक किया जाता है, और रैंकिंग प्रणाली संबंधित कोडवर्ड (और इसलिए संपीड़न दर) निर्धारित करती है। | |||
कई संपीड़न एल्गोरिदम में, रैंकिंग संभाव्यता द्रव्यमान फ़ंक्शन अनुमान के | |||
उदाहरण के लिए, अंकगणित कोडिंग में प्रतीकों को उनकी संभावनाओं के आधार पर पिछले प्रतीकों के बाद प्रदर्शित होने के लिए क्रमबद्ध किया जाता है, और पूरे अनुक्रम को एकल अंश में संपीड़ित किया जाता है जिसकी गणना इन संभावनाओं के अनुसार की जाती है। | |||
पिछले प्रतीकों की संख्या, n, | पिछले प्रतीकों की संख्या, n, पीपीएम मॉडल का क्रम निर्धारित करती है जिसे पीपीएम (n) के रूप में दर्शाया जाता है। इस प्रकार असीमित संस्करण जहां कांटेक्स्ट की कोई लंबाई सीमा नहीं है, वे भी उपस्थित हैं और उन्हें पीपीएम के रूप में दर्शाया गया है। यदि सभी n कांटेक्स्ट प्रतीकों के आधार पर कोई पूर्वानुमान नहीं की जा सकती है, जिससे n - 1 प्रतीकों के साथ पूर्वानुमान का प्रयास किया जाता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि कोई मेल न मिल जाए या कांटेक्स्ट में कोई और प्रतीक नही रह जाती है। उस समय निश्चित पूर्वानुमान की जाती है। | ||
पीपीएम मॉडल को अनुकूलित करने में अधिकांश | पीपीएम मॉडल को अनुकूलित करने में अधिकांश कार्य उन इनपुट को संभालना है जो पहले से ही इनपुट स्ट्रीम में नहीं आए हैं। उन्हें संभालने का स्पष्ट विधि कभी न देखा गया प्रतीक बनाना है इस प्रकार जो भागने के क्रम को ट्रिगर करता है. किन्तु उस प्रतीक को क्या संभावना दी जानी चाहिए जो कभी देखा ही नहीं गया है? इसे [https://en.wikibooks.org/wiki/Data_Compression/The_zero-frequeency_problem शून्य-आवृत्ति समस्या] कहा जाता है। संस्करण [[लाप्लास अनुमानक]] का उपयोग करता है, जो कभी न देखे गए प्रतीक को की निश्चित छद्म गणना प्रदान करता है। इस प्रकार पीपीएमडी नामक प्रकार प्रत्येक बार कभी न देखे गए प्रतीक का उपयोग करने पर कभी न देखे गए प्रतीक की छद्म संख्या को बढ़ा देता है। (दूसरे शब्दों में, पीपीएमडी अद्वितीय प्रतीकों की संख्या और देखे गए प्रतीकों की कुल संख्या के अनुपात के रूप में नए प्रतीक की संभावना का अनुमान लगाता है)। | ||
== कार्यान्वयन == | == कार्यान्वयन == | ||
पीपीएम संपीड़न कार्यान्वयन अन्य विवरणों में बहुत भिन्न होता है। वास्तविक प्रतीक चयन | पीपीएम संपीड़न कार्यान्वयन अन्य विवरणों में बहुत भिन्न होता है। इस प्रकार वास्तविक प्रतीक चयन सामान्यतः अंकगणितीय कोडिंग का उपयोग करके अंकित किया जाता है, चूँकि [[हफ़मैन एन्कोडिंग]] या यहां तक कि कुछ प्रकार की [[शब्दकोश कोडर]] तकनीक का उपयोग करना भी संभव है। इस प्रकार अधिकांश पीपीएम एल्गोरिदम में उपयोग किए जाने वाले अंतर्निहित मॉडल को कई प्रतीकों की पूर्वानुमान करने के लिए भी बढ़ाया जा सकता है। इस प्रकार मार्कोव मॉडलिंग को बदलने या पूरक करने के लिए गैर-मार्कोव मॉडलिंग का उपयोग करना भी संभव है। प्रतीक का आकार सामान्यतः स्थिर होता है, सामान्यतः बाइट, जो किसी भी फ़ाइल प्रारूप के सामान्य प्रबंधन को सरल बनाता है। | ||
एल्गोरिदम के इस | एल्गोरिदम के इस वर्ग पर प्रकाशित शोध 1980 के दशक के मध्य में पाया जा सकता है। इस प्रकार 1990 के दशक की प्रारंभ तक सॉफ़्टवेयर कार्यान्वयन लोकप्रिय नहीं थे क्योंकि पीपीएम एल्गोरिदम को महत्वपूर्ण मात्रा में [[रैंडम एक्सेस मेमोरी]] की आवश्यकता होती है। वर्तमान के पीपीएम कार्यान्वयन [[प्राकृतिक भाषा]] टेक्स्ट के लिए सबसे अच्छा प्रदर्शन करने वाले [[दोषरहित संपीड़न]] कार्यक्रमों में से हैं। | ||
पीपीएमडी दिमित्री शकारिन द्वारा पीपीएमआईआई का कार्यान्वयन है। इसका उपयोग डिफ़ॉल्ट रूप से आरएआर (फ़ाइल स्वरूप) में किया जाता है। इसका उपयोग [[7-ज़िप]] द्वारा [[7z]] फ़ाइल प्रारूप में कई संभावित संपीड़न विधियों में से के रूप में भी किया जाता है। | |||
पीपीएम एल्गोरिदम को | पीपीएम एल्गोरिदम को उत्तम बनाने के प्रयासों से डेटा संपीड़न एल्गोरिदम की पीएक्यू श्रृंखला का निर्माण हुआ था। | ||
एक पीपीएम एल्गोरिथ्म, संपीड़न के लिए उपयोग किए जाने के | एक पीपीएम एल्गोरिथ्म, संपीड़न के लिए उपयोग किए जाने के अतिरिक्त, वैकल्पिक इनपुट विधि प्रोग्राम [[डैशर (सॉफ्टवेयर)]] में उपयोगकर्ता इनपुट की दक्षता बढ़ाने के लिए उपयोग किया जाता है। | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[भाषा मॉडल]] | * [[भाषा मॉडल]] | ||
* | * एन-ग्राम | ||
==स्रोत== | ==स्रोत== | ||
| Line 32: | Line 29: | ||
* {{Cite journal| last1 = Moffat | first1 = A.| title = पीपीएम डेटा संपीड़न योजना का कार्यान्वयन| doi = 10.1109/26.61469| journal = [[IEEE Transactions on Communications|IEEE Trans. Commun.]]| volume = 38| issue = 11| pages = 1917–1921| date=November 1990 | citeseerx = 10.1.1.120.8728}} | * {{Cite journal| last1 = Moffat | first1 = A.| title = पीपीएम डेटा संपीड़न योजना का कार्यान्वयन| doi = 10.1109/26.61469| journal = [[IEEE Transactions on Communications|IEEE Trans. Commun.]]| volume = 38| issue = 11| pages = 1917–1921| date=November 1990 | citeseerx = 10.1.1.120.8728}} | ||
* {{Cite journal| last1 = Cleary | first1 = J. G.| last2 = Teahan | first2 = W. J.| last3 = Witten | first3 = I. H.| title = पीपीएम के लिए असीमित लंबाई के संदर्भ| journal = The Computer Journal | year = 1997| volume = 40 | issue = 2_and_3 | pages = 67–75 | publisher = Oxford University Press | location = Oxford, England | language = English | url = https://academic.oup.com/comjnl/article-abstract/40/2_and_3/67/360793 | issn = 0010-4620 | doi = 10.1093/comjnl/40.2_and_3.67}} | * {{Cite journal| last1 = Cleary | first1 = J. G.| last2 = Teahan | first2 = W. J.| last3 = Witten | first3 = I. H.| title = पीपीएम के लिए असीमित लंबाई के संदर्भ| journal = The Computer Journal | year = 1997| volume = 40 | issue = 2_and_3 | pages = 67–75 | publisher = Oxford University Press | location = Oxford, England | language = English | url = https://academic.oup.com/comjnl/article-abstract/40/2_and_3/67/360793 | issn = 0010-4620 | doi = 10.1093/comjnl/40.2_and_3.67}} | ||
* सी. ब्लूम, [http://www.cbloom.com/papers/ppmz.zip | * सी. ब्लूम, [http://www.cbloom.com/papers/ppmz.zip कांटेक्स्ट मॉडलिंग की समस्याओं का समाधान]। | ||
* डब्ल्यू.जे. टीहान, [http://cotty.16x16.com/compress/peppm.htm पीपीएम के लिए संभाव्यता अनुमान], [https://web.archive.org/web/20010605194536/http://www.cs.waikato .ac.nz/~wjt/papers/NZCSRSC.ps.gz मूल स्रोत Archive.org से]। | * डब्ल्यू.जे. टीहान, [http://cotty.16x16.com/compress/peppm.htm पीपीएम के लिए संभाव्यता अनुमान], [https://web.archive.org/web/20010605194536/http://www.cs.waikato .ac.nz/~wjt/papers/NZCSRSC.ps.gz मूल स्रोत Archive.org से]। | ||
* {{Cite journal| last1 = Schürmann | first1 = T.| last2 = Grassberger | first2 = P.| doi = 10.1063/1.166191| title = प्रतीक अनुक्रमों का एन्ट्रॉपी अनुमान| journal = Chaos| volume = 6| pmid = 12780271| issue = 3| pages = 414–427| date=September 1996 | arxiv = cond-mat/0203436| bibcode = 1996Chaos...6..414S| s2cid = 10090433}} | * {{Cite journal| last1 = Schürmann | first1 = T.| last2 = Grassberger | first2 = P.| doi = 10.1063/1.166191| title = प्रतीक अनुक्रमों का एन्ट्रॉपी अनुमान| journal = Chaos| volume = 6| pmid = 12780271| issue = 3| pages = 414–427| date=September 1996 | arxiv = cond-mat/0203436| bibcode = 1996Chaos...6..414S| s2cid = 10090433}} | ||
== | ==कांटेक्स्ट== | ||
{{Reflist}} | {{Reflist}} | ||
| Line 42: | Line 39: | ||
== बाहरी संबंध == | == बाहरी संबंध == | ||
{{बाहरी संबंध|date=November 2015}} | {{बाहरी संबंध|date=November 2015}} | ||
* [http://mattmahoney.net/dc/text.html Suite of | * [http://mattmahoney.net/dc/text.html Suite of पीपीएम compressors with benchmarks] | ||
* [http://www3.sympatico.ca/mt0000/bicom/bicom.html BICOM, a bijective | * [http://www3.sympatico.ca/mt0000/bicom/bicom.html BICOM, a bijective पीपीएम compressor] | ||
* [https://marknelson.us/posts/1991/02/01/arithmetic-coding-statistical-modeling-data-compression.html#part2 "Arithmetic Coding + Statistical Modeling = Data Compression", Part 2] | * [https://marknelson.us/posts/1991/02/01/arithmetic-coding-statistical-modeling-data-compression.html#part2 "Arithmetic Coding + Statistical Modeling = Data Compression", Part 2] | ||
* {{in lang|ru}} [http://compression.ru/ds/ | * {{in lang|ru}} [http://compression.ru/ds/ पीपीएमडी compressor] by Dmitri Shkarin | ||
* [https://github.com/rene-puschinger/ppm PPM compression in C++] by René Puschinger | * [https://github.com/rene-puschinger/ppm PPM compression in C++] by René Puschinger | ||
[[Category: दोषरहित संपीड़न एल्गोरिदम]] | [[Category: दोषरहित संपीड़न एल्गोरिदम]] | ||
Revision as of 16:58, 12 July 2023
आंशिक मिलान द्वारा पूर्वानुमान (पीपीएम) कांटेक्स्ट मॉडलिंग और पूर्वानुमान पर आधारित अनुकूली सांख्यिकी डेटा संपीड़न तकनीक है। पीपीएम मॉडल स्ट्रीम में अगले प्रतीक की पूर्वानुमान करने के लिए असम्पीडित प्रतीक स्ट्रीम में पिछले प्रतीकों के सेट का उपयोग करते हैं। पीपीएम एल्गोरिदम का उपयोग क्लस्टर विश्लेषण में पूर्वानुमानित समूहों में डेटा को क्लस्टर करने के लिए भी किया जा सकता है।
सिद्धांत
पूर्वानुमान सामान्यतः प्रतीक रैंकिंग तक सीमित कर दी जाती हैं. प्रत्येक प्रतीक (एक अक्षर, बिट या डेटा की कोई अन्य मात्रा) को संपीड़ित करने से पहले रैंक किया जाता है, और इस प्रकार रैंकिंग प्रणाली संबंधित कोडवर्ड (और इसलिए संपीड़न दर) निर्धारित करती है। इस प्रकार कई संपीड़न एल्गोरिदम में, रैंकिंग संभाव्यता द्रव्यमान फ़ंक्शन अनुमान के समान है। पिछले अक्षरों को देखते हुए (या कांटेक्स्ट दिया गया है), प्रत्येक प्रतीक को संभावना के साथ निर्दिष्ट किया गया है। उदाहरण के लिए, अंकगणित कोडिंग में प्रतीकों को उनकी संभावनाओं के आधार पर पिछले प्रतीकों के बाद प्रदर्शित होने के लिए क्रमबद्ध किया जाता है, और पूरे अनुक्रम को एकल अंश में संपीड़ित किया जाता है जिसकी गणना इन संभावनाओं के अनुसार की जाती है।
पिछले प्रतीकों की संख्या, n, पीपीएम मॉडल का क्रम निर्धारित करती है जिसे पीपीएम (n) के रूप में दर्शाया जाता है। इस प्रकार असीमित संस्करण जहां कांटेक्स्ट की कोई लंबाई सीमा नहीं है, वे भी उपस्थित हैं और उन्हें पीपीएम के रूप में दर्शाया गया है। यदि सभी n कांटेक्स्ट प्रतीकों के आधार पर कोई पूर्वानुमान नहीं की जा सकती है, जिससे n - 1 प्रतीकों के साथ पूर्वानुमान का प्रयास किया जाता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि कोई मेल न मिल जाए या कांटेक्स्ट में कोई और प्रतीक नही रह जाती है। उस समय निश्चित पूर्वानुमान की जाती है।
पीपीएम मॉडल को अनुकूलित करने में अधिकांश कार्य उन इनपुट को संभालना है जो पहले से ही इनपुट स्ट्रीम में नहीं आए हैं। उन्हें संभालने का स्पष्ट विधि कभी न देखा गया प्रतीक बनाना है इस प्रकार जो भागने के क्रम को ट्रिगर करता है. किन्तु उस प्रतीक को क्या संभावना दी जानी चाहिए जो कभी देखा ही नहीं गया है? इसे शून्य-आवृत्ति समस्या कहा जाता है। संस्करण लाप्लास अनुमानक का उपयोग करता है, जो कभी न देखे गए प्रतीक को की निश्चित छद्म गणना प्रदान करता है। इस प्रकार पीपीएमडी नामक प्रकार प्रत्येक बार कभी न देखे गए प्रतीक का उपयोग करने पर कभी न देखे गए प्रतीक की छद्म संख्या को बढ़ा देता है। (दूसरे शब्दों में, पीपीएमडी अद्वितीय प्रतीकों की संख्या और देखे गए प्रतीकों की कुल संख्या के अनुपात के रूप में नए प्रतीक की संभावना का अनुमान लगाता है)।
कार्यान्वयन
पीपीएम संपीड़न कार्यान्वयन अन्य विवरणों में बहुत भिन्न होता है। इस प्रकार वास्तविक प्रतीक चयन सामान्यतः अंकगणितीय कोडिंग का उपयोग करके अंकित किया जाता है, चूँकि हफ़मैन एन्कोडिंग या यहां तक कि कुछ प्रकार की शब्दकोश कोडर तकनीक का उपयोग करना भी संभव है। इस प्रकार अधिकांश पीपीएम एल्गोरिदम में उपयोग किए जाने वाले अंतर्निहित मॉडल को कई प्रतीकों की पूर्वानुमान करने के लिए भी बढ़ाया जा सकता है। इस प्रकार मार्कोव मॉडलिंग को बदलने या पूरक करने के लिए गैर-मार्कोव मॉडलिंग का उपयोग करना भी संभव है। प्रतीक का आकार सामान्यतः स्थिर होता है, सामान्यतः बाइट, जो किसी भी फ़ाइल प्रारूप के सामान्य प्रबंधन को सरल बनाता है।
एल्गोरिदम के इस वर्ग पर प्रकाशित शोध 1980 के दशक के मध्य में पाया जा सकता है। इस प्रकार 1990 के दशक की प्रारंभ तक सॉफ़्टवेयर कार्यान्वयन लोकप्रिय नहीं थे क्योंकि पीपीएम एल्गोरिदम को महत्वपूर्ण मात्रा में रैंडम एक्सेस मेमोरी की आवश्यकता होती है। वर्तमान के पीपीएम कार्यान्वयन प्राकृतिक भाषा टेक्स्ट के लिए सबसे अच्छा प्रदर्शन करने वाले दोषरहित संपीड़न कार्यक्रमों में से हैं।
पीपीएमडी दिमित्री शकारिन द्वारा पीपीएमआईआई का कार्यान्वयन है। इसका उपयोग डिफ़ॉल्ट रूप से आरएआर (फ़ाइल स्वरूप) में किया जाता है। इसका उपयोग 7-ज़िप द्वारा 7z फ़ाइल प्रारूप में कई संभावित संपीड़न विधियों में से के रूप में भी किया जाता है।
पीपीएम एल्गोरिदम को उत्तम बनाने के प्रयासों से डेटा संपीड़न एल्गोरिदम की पीएक्यू श्रृंखला का निर्माण हुआ था।
एक पीपीएम एल्गोरिथ्म, संपीड़न के लिए उपयोग किए जाने के अतिरिक्त, वैकल्पिक इनपुट विधि प्रोग्राम डैशर (सॉफ्टवेयर) में उपयोगकर्ता इनपुट की दक्षता बढ़ाने के लिए उपयोग किया जाता है।
यह भी देखें
- भाषा मॉडल
- एन-ग्राम
स्रोत
- Cleary, J.; Witten, I. (April 1984). "अनुकूली कोडिंग और आंशिक स्ट्रिंग मिलान का उपयोग करके डेटा संपीड़न". IEEE Trans. Commun. 32 (4): 396–402. CiteSeerX 10.1.1.14.4305. doi:10.1109/TCOM.1984.1096090.
- Moffat, A. (November 1990). "पीपीएम डेटा संपीड़न योजना का कार्यान्वयन". IEEE Trans. Commun. 38 (11): 1917–1921. CiteSeerX 10.1.1.120.8728. doi:10.1109/26.61469.
- Cleary, J. G.; Teahan, W. J.; Witten, I. H. (1997). "पीपीएम के लिए असीमित लंबाई के संदर्भ". The Computer Journal (in English). Oxford, England: Oxford University Press. 40 (2_and_3): 67–75. doi:10.1093/comjnl/40.2_and_3.67. ISSN 0010-4620.
- सी. ब्लूम, कांटेक्स्ट मॉडलिंग की समस्याओं का समाधान।
- डब्ल्यू.जे. टीहान, पीपीएम के लिए संभाव्यता अनुमान, .ac.nz/~wjt/papers/NZCSRSC.ps.gz मूल स्रोत Archive.org से।
- Schürmann, T.; Grassberger, P. (September 1996). "प्रतीक अनुक्रमों का एन्ट्रॉपी अनुमान". Chaos. 6 (3): 414–427. arXiv:cond-mat/0203436. Bibcode:1996Chaos...6..414S. doi:10.1063/1.166191. PMID 12780271. S2CID 10090433.
कांटेक्स्ट
बाहरी संबंध
- Suite of पीपीएम compressors with benchmarks
- BICOM, a bijective पीपीएम compressor
- "Arithmetic Coding + Statistical Modeling = Data Compression", Part 2
- (in Russian) पीपीएमडी compressor by Dmitri Shkarin
- PPM compression in C++ by René Puschinger
