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