आंशिक मिलान द्वारा भविष्यवाणी

आंशिक मिलान द्वारा भविष्यवाणी (पीपीएम) संदर्भ मॉडलिंग और भविष्यवाणी पर आधारित एक अनुकूली सांख्यिकी डेटा संपीड़न तकनीक है। पीपीएम मॉडल स्ट्रीम में अगले प्रतीक की भविष्यवाणी करने के लिए असम्पीडित प्रतीक स्ट्रीम में पिछले प्रतीकों के एक सेट का उपयोग करते हैं। पीपीएम एल्गोरिदम का उपयोग क्लस्टर विश्लेषण में पूर्वानुमानित समूहों में डेटा को क्लस्टर करने के लिए भी किया जा सकता है।

सिद्धांत

भविष्यवाणियाँ आमतौर पर प्रतीक रैंकिंग तक सीमित कर दी जाती हैं. प्रत्येक प्रतीक (एक अक्षर, बिट या डेटा की कोई अन्य मात्रा) को संपीड़ित करने से पहले रैंक किया जाता है, और रैंकिंग प्रणाली संबंधित कोडवर्ड (और इसलिए संपीड़न दर) निर्धारित करती है। कई संपीड़न एल्गोरिदम में, रैंकिंग संभाव्यता द्रव्यमान फ़ंक्शन अनुमान के बराबर है। पिछले अक्षरों को देखते हुए (या एक संदर्भ दिया गया है), प्रत्येक प्रतीक को एक संभावना के साथ निर्दिष्ट किया गया है। उदाहरण के लिए, अंकगणित कोडिंग में प्रतीकों को उनकी संभावनाओं के आधार पर पिछले प्रतीकों के बाद प्रदर्शित होने के लिए क्रमबद्ध किया जाता है, और पूरे अनुक्रम को एक एकल अंश में संपीड़ित किया जाता है जिसकी गणना इन संभावनाओं के अनुसार की जाती है।

पिछले प्रतीकों की संख्या, n, PPM मॉडल का क्रम निर्धारित करती है जिसे PPM(n) के रूप में दर्शाया जाता है। असीमित संस्करण जहां संदर्भ की कोई लंबाई सीमा नहीं है, वे भी मौजूद हैं और उन्हें पीपीएम* के रूप में दर्शाया गया है। यदि सभी n संदर्भ प्रतीकों के आधार पर कोई भविष्यवाणी नहीं की जा सकती है, तो n - 1 प्रतीकों के साथ भविष्यवाणी का प्रयास किया जाता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि कोई मेल न मिल जाए या संदर्भ में कोई और प्रतीक न रह जाए। उस समय एक निश्चित भविष्यवाणी की जाती है।

पीपीएम मॉडल को अनुकूलित करने में अधिकांश काम उन इनपुट को संभालना है जो पहले से ही इनपुट स्ट्रीम में नहीं आए हैं। उन्हें संभालने का स्पष्ट तरीका एक कभी न देखा गया प्रतीक बनाना है जो भागने के क्रम को ट्रिगर करता है. लेकिन उस प्रतीक को क्या संभावना दी जानी चाहिए जो कभी देखा ही नहीं गया है? इसे शून्य-आवृत्ति समस्या कहा जाता है। एक संस्करण लाप्लास अनुमानक का उपयोग करता है, जो कभी न देखे गए प्रतीक को एक की निश्चित छद्म गणना प्रदान करता है। PPMd नामक एक प्रकार हर बार कभी न देखे गए प्रतीक का उपयोग करने पर कभी न देखे गए प्रतीक की छद्म संख्या को बढ़ा देता है। (दूसरे शब्दों में, PPMd अद्वितीय प्रतीकों की संख्या और देखे गए प्रतीकों की कुल संख्या के अनुपात के रूप में एक नए प्रतीक की संभावना का अनुमान लगाता है)।

कार्यान्वयन

पीपीएम संपीड़न कार्यान्वयन अन्य विवरणों में बहुत भिन्न होता है। वास्तविक प्रतीक चयन आमतौर पर अंकगणितीय कोडिंग का उपयोग करके दर्ज किया जाता है, हालांकि हफ़मैन एन्कोडिंग या यहां तक ​​कि कुछ प्रकार की शब्दकोश कोडर तकनीक का उपयोग करना भी संभव है। अधिकांश पीपीएम एल्गोरिदम में उपयोग किए जाने वाले अंतर्निहित मॉडल को कई प्रतीकों की भविष्यवाणी करने के लिए भी बढ़ाया जा सकता है। मार्कोव मॉडलिंग को बदलने या पूरक करने के लिए गैर-मार्कोव मॉडलिंग का उपयोग करना भी संभव है। प्रतीक का आकार आमतौर पर स्थिर होता है, आमतौर पर एक बाइट, जो किसी भी फ़ाइल प्रारूप के सामान्य प्रबंधन को आसान बनाता है। एल्गोरिदम के इस परिवार पर प्रकाशित शोध 1980 के दशक के मध्य में पाया जा सकता है। 1990 के दशक की शुरुआत तक सॉफ़्टवेयर कार्यान्वयन लोकप्रिय नहीं थे क्योंकि पीपीएम एल्गोरिदम को महत्वपूर्ण मात्रा में रैंडम एक्सेस मेमोरी की आवश्यकता होती है। हाल के पीपीएम कार्यान्वयन प्राकृतिक भाषा पाठ के लिए सबसे अच्छा प्रदर्शन करने वाले दोषरहित संपीड़न कार्यक्रमों में से एक हैं।

PPMd दिमित्री शकारिन द्वारा PPMII का कार्यान्वयन है। इसका उपयोग डिफ़ॉल्ट रूप से RAR (फ़ाइल स्वरूप) में किया जाता है। इसका उपयोग 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 PPM compressors with benchmarks
• BICOM, a bijective PPM compressor
• "Arithmetic Coding + Statistical Modeling = Data Compression", Part 2
• (in Russian) PPMd compressor by Dmitri Shkarin
• PPM compression in C++ by René Puschinger