गोरकॉफ़ 24 फरवरी, 2015 पूर्वाह्न 11:41 बजे

डेटा संपीड़न के तरीके

• एल्गोरिदम

मैं और मेरे वैज्ञानिक सलाहकार इमेज प्रोसेसिंग पर एक छोटा मोनोग्राफ तैयार कर रहे हैं। मैंने हबरासोसाइटी के निर्णय के लिए छवि संपीड़न एल्गोरिदम पर एक अध्याय प्रस्तुत करने का निर्णय लिया। चूंकि एक पोस्ट के ढांचे के भीतर पूरे अध्याय को फिट करना मुश्किल है, इसलिए मैंने इसे तीन पदों में विभाजित करने का फैसला किया:
1. डेटा संपीड़न के तरीके;
2. छवियों का दोषरहित संपीड़न;
3. नुकसान के साथ छवियों का संपीड़न।
नीचे आप सीरीज की पहली पोस्ट पढ़ सकते हैं।

फिलहाल, बड़ी संख्या में दोषरहित संपीड़न एल्गोरिदम हैं, जिन्हें सशर्त रूप से दो बड़े समूहों में विभाजित किया जा सकता है:
1. स्ट्रीम और डिक्शनरी एल्गोरिदम। इस समूह में RLE (रन-लेंथ एन्कोडिंग), LZ *, आदि परिवारों के एल्गोरिदम शामिल हैं। इस समूह के सभी एल्गोरिदम की एक विशेषता यह है कि एन्कोडिंग संदेश में वर्णों की आवृत्तियों के बारे में जानकारी नहीं, बल्कि अनुक्रमों के बारे में जानकारी का उपयोग करता है। जिनका सामना पहले किया गया था।
2. सांख्यिकीय (एन्ट्रॉपी) संपीड़न के लिए एल्गोरिदम। एल्गोरिदम का यह समूह उन आवृत्तियों की असमानता का उपयोग करके जानकारी को संपीड़ित करता है जिसके साथ संदेश में विभिन्न वर्ण होते हैं। इस समूह में एल्गोरिदम में अंकगणित और उपसर्ग कोडिंग एल्गोरिदम शामिल हैं (शैनन-फ़ैनो, हफ़मैन, सेकेंड ट्री का उपयोग करके)।
सूचना परिवर्तन एल्गोरिदम को एक अलग समूह में प्रतिष्ठित किया जा सकता है। इस समूह के एल्गोरिदम सीधे जानकारी को संपीड़ित नहीं करते हैं, लेकिन उनका अनुप्रयोग स्ट्रीम, डिक्शनरी और एन्ट्रॉपी एल्गोरिदम का उपयोग करके आगे के संपीड़न को बहुत सरल करता है।

स्ट्रीमिंग और शब्दकोश एल्गोरिदम

रन लेंथ कोडिंग

रन-लेंथ एन्कोडिंग (आरएलई) सबसे सरल और सबसे आम डेटा संपीड़न एल्गोरिदम में से एक है। इस एल्गोरिथम में, दोहराए गए वर्णों के अनुक्रम को एक वर्ण से बदल दिया जाता है और जितनी बार इसे दोहराया जाता है।
उदाहरण के लिए, स्ट्रिंग "एएएएएए", जिसे स्टोर करने के लिए 5 बाइट्स की आवश्यकता होती है (यह मानते हुए कि एक बाइट को एक कैरेक्टर को स्टोर करने के लिए आवंटित किया गया है), को "5 ए" से बदला जा सकता है, जिसमें दो बाइट्स होते हैं। जाहिर है, पुनरावृत्ति श्रृंखला जितनी लंबी होगी, यह एल्गोरिथ्म उतना ही अधिक कुशल होगा।

इस एल्गोरिथम का मुख्य नुकसान गैर-दोहराए जाने वाले वर्णों के अनुक्रमों पर इसकी अत्यंत कम दक्षता है। उदाहरण के लिए, यदि हम अनुक्रम "ABABAB" (6 बाइट्स) पर विचार करते हैं, तो RLE एल्गोरिथम लागू करने के बाद यह "1A1B1A1B1A1B" (12 बाइट्स) में बदल जाएगा। गैर-दोहराए जाने वाले पात्रों की समस्या से निपटने के लिए विभिन्न तरीके हैं।

सबसे सरल तरीका निम्नलिखित संशोधन है: दोहराव की संख्या को बाइट एन्कोडिंग न केवल दोहराने की संख्या के बारे में, बल्कि उनकी उपस्थिति के बारे में भी जानकारी संग्रहीत करनी चाहिए। यदि पहला बिट 1 है, तो अगले 7 बिट्स संबंधित वर्ण के दोहराव की संख्या को इंगित करते हैं, और यदि पहला बिट 0 है, तो अगले 7 बिट्स वर्णों की संख्या को इंगित करते हैं जिन्हें बिना दोहराव के लिया जाना चाहिए। यदि आप इस संशोधन का उपयोग करके "ABABAB" को एनकोड करते हैं, तो हमें "-6ABABAB" (7 बाइट्स) मिलता है। जाहिर है, प्रस्तावित तकनीक वर्णों के गैर-दोहराए जाने वाले अनुक्रमों पर RLE एल्गोरिथम की दक्षता में काफी सुधार कर सकती है। प्रस्तावित दृष्टिकोण का कार्यान्वयन सूची 1 में दिखाया गया है:

1. प्रकार
2. समारोह RLEEncode (InMsg: शॉर्टस्ट्रिंग): TRLEncodedString;
3. मैचफ्ल: बूलियन;
4. मैचकाउंट: शॉर्टिंट;
5. एन्कोडेडस्ट्रिंग: TRLEncodedString;
6. एन, मैं: बाइट;
7. शुरू
8. एन: = 0;
9. सेटलेंथ (एन्कोडेडस्ट्रिंग, 2 * लंबाई (इनएमएसजी));
10. जबकि लंबाई (InMsg)> = 1 do
11. शुरू
12. MatchFl: = (लंबाई (InMsg)> 1) और (InMsg [1] = InMsg [2]);
13. मैचकाउंट: = 1;
14. जबकि (मैचकाउंट<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. मैचकाउंट: = मैचकाउंट + 1;
16. अगर मैचफ्ल तो
17. शुरू
18. एन: = एन + 2;
19. एन्कोडेडस्ट्रिंग [एन - 2]: = मैचकाउंट + 128;
20. एन्कोडेडस्ट्रिंग [एन -1]: = ऑर्ड (इनएमएसजी [1]);
21. अन्यथा
22. शुरू
23. अगर मैचकाउंट<>लंबाई (InMsg) तब
24. मैचकाउंट: = मैचकाउंट - 1;
25. एन: = एन + 1 + मैचकाउंट;
26. एन्कोडेडस्ट्रिंग [एन -1 - मैचकाउंट]: = - मैचकाउंट + 128;
27. i के लिए: = 1 से MatchCount do
28. एन्कोडेडस्ट्रिंग [एन -1 - मैचकाउंट + आई]: = ऑर्ड (इनएमएसजी [i]);
29. समाप्त;
30. हटाएं (इनएमएसजी, 1, मैचकाउंट);
31. समाप्त;
32. सेटलेंथ (एन्कोडेडस्ट्रिंग, एन);
33. आरएलईएनकोड: = एनकोडेडस्ट्रिंग;
34. समाप्त;

एक संपीड़ित संदेश को डिकोड करना बहुत सरल है और संकुचित संदेश पर एक ही पास तक उबाल जाता है, सूचीकरण 2 देखें:

1. प्रकार
2. TRLEncodedString = बाइट की सरणी;
3. समारोह RLEDecode (InMsg: TRLEncodedString): शॉर्टस्ट्रिंग;
4. रिपीटकाउंट: शॉर्टिंट;
5. मैं, जे: शब्द;
6. आउट संदेश: शॉर्टस्ट्रिंग;
7. शुरू
8. आउट संदेश: = "";
9. मैं: = 0;
10. मैं जबकि< length(InMsg) do
11. शुरू
12. रिपीटकाउंट: = इनएमएसजी [i] - 128;
13. मैं: = मैं + 1;
14. अगर रिपीटकाउंट< 0 then
15. शुरू
16. रिपीटकाउंट: = एब्स (रिपीटकाउंट);
17. j के लिए: = i से i + रिपीटकाउंट - 1 do
18. OutMsg: = OutMsg + chr (InMsg [j]);
19. i: = i + रिपीटकाउंट;
20. अन्यथा
21. शुरू
22. j के लिए: = 1 दोहराएँ करने के लिए do
23. OutMsg: = OutMsg + chr (InMsg [i]);
24. मैं: = मैं + 1;
25. समाप्त;
26. समाप्त;
27. आरएलईडीकोड: = आउटएमएसजी;
28. समाप्त;

आरएलई एल्गोरिदम की दक्षता बढ़ाने के लिए दूसरी विधि सूचना परिवर्तन एल्गोरिदम का उपयोग है जो सीधे डेटा को संपीड़ित नहीं करता है, लेकिन इसे ऐसे रूप में लाता है जो संपीड़न के लिए अधिक सुविधाजनक हो। इस तरह के एक एल्गोरिथ्म के एक उदाहरण के रूप में, हम एक BWT क्रमपरिवर्तन पर विचार करेंगे जिसका नाम बुरो-व्हीलर ट्रांसफॉर्म के आविष्कारकों के नाम पर रखा गया है। यह क्रमपरिवर्तन स्वयं वर्णों को नहीं बदलता है, लेकिन केवल स्ट्रिंग में उनके क्रम को बदलता है, जबकि क्रमपरिवर्तन को लागू करने के बाद बार-बार होने वाले सबस्ट्रिंग को घने समूहों में एकत्र किया जाता है, जो कि RLE एल्गोरिथम का उपयोग करके बेहतर रूप से संकुचित होते हैं। प्रत्यक्ष BWT रूपांतरण को निम्न चरणों के अनुक्रम में घटाया गया है:
1. मूल स्ट्रिंग में एक विशेष एंड-ऑफ़-लाइन वर्ण जोड़ना, जो कहीं और नहीं मिलता है;
2. मूल स्ट्रिंग के सभी चक्रीय क्रमपरिवर्तन प्राप्त करना;
3. प्राप्त पंक्तियों को लेक्सिकोग्राफिक क्रम में क्रमबद्ध करना;
4. परिणामी मैट्रिक्स का अंतिम कॉलम लौटाना।
इस एल्गोरिथ्म का कार्यान्वयन लिस्टिंग 3 में दिखाया गया है।

1. स्थिरांक
2. ईओएमएसजी = "|" ;
3. समारोह BWTEncode (InMsg: शॉर्टस्ट्रिंग): शॉर्टस्ट्रिंग;
4. आउट संदेश: शॉर्टस्ट्रिंग;
5. LastChar: ANSIChar;
6. एन, मैं: शब्द;
7. शुरू
8. InMsg: = InMsg + EOMsg;
9. एन: = लंबाई (इनएमएसजी);
10. शिफ्टटेबल [1]: = इनएमएसजी;
11. i के लिए: = 2 से N do
12. शुरू
13. लास्टचर: = इनएमएसजी [एन];
14. InMsg: = LastChar + copy (InMsg, 1, N-1);
15. शिफ्टटेबल [i]: = इनएमएसजी;
16. समाप्त;
17. क्रमबद्ध करें (ShiftTable);
18. आउट संदेश: = "";
19. i के लिए: = 1 से N do
20. OutMsg: = OutMsg + ShiftTable [i] [N];
21. बीडब्ल्यूटीईएनकोड: = आउटएमएसजी;
22. समाप्त;

इस परिवर्तन को समझाने का सबसे आसान तरीका एक विशिष्ट उदाहरण है। आइए स्ट्रिंग "ANANAS" लें और सहमत हों कि अंतिम वर्ण "|" का प्रतीक होगा। इस रेखा के सभी चक्रीय क्रमपरिवर्तन और उनकी शब्दावली छँटाई के परिणाम तालिका में दिखाए गए हैं। एक।

वे। प्रत्यक्ष रूपांतरण का परिणाम स्ट्रिंग "| " होगा। यह देखना आसान है कि यह स्ट्रिंग मूल स्ट्रिंग की तुलना में बहुत बेहतर है; यह RLE एल्गोरिथम द्वारा संकुचित है, क्योंकि इसमें दोहराए गए अक्षरों के लंबे क्रम शामिल हैं।
अन्य परिवर्तनों की मदद से एक समान प्रभाव प्राप्त किया जा सकता है, लेकिन बीडब्ल्यूटी ट्रांसफ़ॉर्म का लाभ यह है कि यह प्रतिवर्ती है, हालांकि, उलटा परिवर्तन प्रत्यक्ष की तुलना में अधिक कठिन है। मूल स्ट्रिंग को पुनर्स्थापित करने के लिए, आपको निम्न कार्य करने होंगे:
एक खाली n * n मैट्रिक्स बनाएं, जहां n एन्कोडेड संदेश में वर्णों की संख्या है;
एन्कोडेड संदेश के साथ सबसे दाहिना खाली कॉलम भरें;
लेक्सिकोग्राफिक क्रम में तालिका पंक्तियों को क्रमबद्ध करें;
चरण 2-3 को तब तक दोहराएं जब तक कि खाली कॉलम न हों;
वह रेखा लौटाएं जो अंत-पंक्ति वर्ण के साथ समाप्त होती है।

पहली नज़र में, रिवर्स ट्रांसफ़ॉर्मेशन सीधा है, और विकल्पों में से एक लिस्टिंग 4 में दिखाया गया है।

1. स्थिरांक
2. ईओएमएसजी = "|" ;
3. समारोह BWTDecode (InMsg: शॉर्टस्ट्रिंग): शॉर्टस्ट्रिंग;
4. आउट संदेश: शॉर्टस्ट्रिंग;
5. शिफ्टटेबल: शॉर्टस्ट्रिंग की सरणी;
6. एन, आई, जे: शब्द;
7. शुरू
8. आउट संदेश: = "";
9. एन: = लंबाई (इनएमएसजी);
10. सेटलेंथ (ShiftTable, N + 1);
11. i के लिए: = 0 से N do
12. शिफ्टटेबल [i]: = "";
13. i के लिए: = 1 से N do
14. शुरू
15. j के लिए: = 1 से N do
16. शिफ्टटेबल [जे]: = इनएमएसजी [जे] + शिफ्टटेबल [जे];
17. क्रमबद्ध करें (ShiftTable);
18. समाप्त;
19. i के लिए: = 1 से N do
20. अगर शिफ्टटेबल [i] [एन] = ईओएमएसजी तो
21. आउट संदेश: = शिफ्टटेबल [i];
22. हटाएं (आउटएमएसजी, एन, 1);
23. बीडब्ल्यूटीडीकोड: = आउटएमएसजी;
24. समाप्त;

लेकिन व्यवहार में, दक्षता चयनित छँटाई एल्गोरिथ्म पर निर्भर करती है। द्विघात जटिलता वाले तुच्छ एल्गोरिदम का प्रदर्शन पर स्पष्ट रूप से अत्यधिक नकारात्मक प्रभाव पड़ेगा, इसलिए कुशल एल्गोरिदम का उपयोग करने की अनुशंसा की जाती है।

सातवें चरण में प्राप्त तालिका को छाँटने के बाद, तालिका से "|" वर्ण के साथ समाप्त होने वाली एक पंक्ति का चयन करना आवश्यक है। यह देखना आसान है कि यह एकमात्र पंक्ति है। वह। हमने एक विशिष्ट उदाहरण का उपयोग करके BWT परिवर्तन की जांच की।

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

शब्दकोश संपीड़न (एलजेड एल्गोरिदम)

शब्दकोश एल्गोरिदम का समूह, आरएलई समूह के एल्गोरिदम के विपरीत, वर्णों की पुनरावृत्ति की संख्या को नहीं, बल्कि वर्णों के पहले से सामना किए गए अनुक्रमों को एन्कोड करता है। विचाराधीन एल्गोरिदम के संचालन के दौरान, पहले से सामना किए गए अनुक्रमों और उनके संबंधित कोड की सूची के साथ एक तालिका गतिशील रूप से बनाई जाती है। इस तालिका को अक्सर एक शब्दकोश कहा जाता है, और एल्गोरिदम के संबंधित समूह को शब्दकोश कहा जाता है।

शब्दकोश एल्गोरिथ्म का सबसे सरल संस्करण नीचे वर्णित है:
इनपुट स्ट्रिंग में प्रकट होने वाले सभी वर्णों के साथ शब्दकोश को प्रारंभ करें;
शब्दकोश में सबसे लंबा अनुक्रम (एस) खोजें जो एन्कोडेड संदेश की शुरुआत से मेल खाता हो;
पाए गए अनुक्रम का कोड जारी करें और इसे एन्कोडेड संदेश की शुरुआत से हटा दें;
यदि संदेश का अंत नहीं हुआ है, तो अगला अक्षर पढ़ें और शब्दकोश में Sc जोड़ें, चरण 2 पर जाएं। अन्यथा, बाहर निकलें।

उदाहरण के लिए, "CUCKOOKUCHONKUPILACAPUCHON" वाक्यांश के लिए नई आरंभिक शब्दावली तालिका में दिखाई गई है। 3:

संपीड़न प्रक्रिया के दौरान, संदेश में पाए जाने वाले अनुक्रमों के साथ शब्दकोश को पूरक किया जाएगा। शब्दकोश को फिर से भरने की प्रक्रिया तालिका में दिखाई गई है। 4.

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

सबसे पहले, आइए एक डिक्शनरी को एक रिकॉर्ड के रूप में परिभाषित करें जो न केवल पाए गए सबस्ट्रिंग को स्टोर करता है, बल्कि डिक्शनरी में स्टोर किए गए सबस्ट्रिंग्स की संख्या भी:

पहले सामने आए बाद के क्रम Words सरणी में संग्रहीत किए जाते हैं, और उनके कोड इस सरणी में बाद की संख्या होते हैं।
हम शब्दकोश में खोजने और शब्दकोश में जोड़ने के लिए कार्यों को भी परिभाषित करते हैं:

1. स्थिरांक
2. MAX_DICT_LENGTH = 256;
3. फ़ंक्शन FindInDict (D: TDictionary; str: ShortString): पूर्णांक;
4. आर: पूर्णांक;
5. मैं: पूर्णांक;
6. फ्लो: बूलियन;
7. शुरू
8. आर: = - 1;
9. अगर डी। वर्डकाउंट> 0 तो
10. शुरू
11. i: = डी. वर्डकाउंट;
12. एफएल: = झूठा;
13. जबकि (fl नहीं) और (i> = 0) do
14. शुरू
15. मैं: = मैं - 1;
16. fl: = D. शब्द [i] = str;
17. समाप्त;
18. समाप्त;
19. अगर fl तो
20. आर: = मैं;
21. FindInDict: = r;
22. समाप्त;
23. प्रक्रिया AddToDict (var D: TDictionary; str: ShortString);
24. शुरू
25. अगर डी। वर्डकाउंट< MAX_DICT_LENGTH then
26. शुरू
27. डी। वर्डकाउंट: = डी। वर्डकाउंट + 1;
28. सेटलेंथ (डी। वर्ड्स, डी। वर्डकाउंट);
29. डी शब्द [डी वर्डकाउंट - 1]: = str;
30. समाप्त;
31. समाप्त;

इन कार्यों का उपयोग करके, वर्णित एल्गोरिथम के अनुसार कोडिंग प्रक्रिया को निम्नानुसार लागू किया जा सकता है:

1. समारोह LZWEncode (InMsg: शॉर्टस्ट्रिंग): TEncodedString;
2. आउट संदेश: टेनकोडेडस्ट्रिंग;
3. tmpstr: शॉर्टस्ट्रिंग;
4. डी: टीडिक्शनरी;
5. मैं, एन: बाइट;
6. शुरू
7. सेटलेंथ (आउटएमएसजी, लंबाई (आईएनएमएसजी));
8. एन: = 0;
9. इनिटडिक्ट (डी);
10. जबकि लंबाई (InMsg)> 0 do
11. शुरू
12. tmpstr: = इनएमएसजी [1];
13. जबकि (FindInDict (D, tmpstr)> = 0) और (लंबाई (InMsg)> लंबाई (tmpstr)) करते हैं
14. tmpstr: = tmpstr + InMsg [लंबाई (tmpstr) + 1];
15. अगर FindInDict (डी, tmpstr)< 0 then
16. हटाएं (tmpstr, लंबाई (tmpstr), 1);
17. आउट संदेश [एन]: = FindInDict (डी, tmpstr);
18. एन: = एन + 1;
19. हटाएं (InMsg, 1, लंबाई (tmpstr));
20. अगर लंबाई (InMsg)> 0 तो
21. AddToDict (डी, tmpstr + InMsg [1]);
22. समाप्त;
23. सेटलेंथ (आउटएमएसजी, एन);
24. LZWEncode: = आउटएमएसजी;
25. समाप्त;

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

निम्नलिखित स्थिति में एकमात्र समस्या संभव है: जब किसी ऐसे अनुक्रम को डिकोड करना आवश्यक हो जो अभी तक शब्दकोश में नहीं है। यह देखना आसान है कि यह केवल तभी संभव है जब मौजूदा चरण में जोड़े जाने वाले सबस्ट्रिंग को निकालना आवश्यक हो। इसका मतलब है कि सबस्ट्रिंग सीएससी पैटर्न से मेल खाती है, यानी। एक ही चरित्र के साथ शुरू और समाप्त होता है। इसके अलावा, cS पिछले चरण में जोड़ा गया विकल्प है। विचार की गई स्थिति केवल एक ही होती है जब एक पंक्ति को डिकोड करना आवश्यक होता है जिसे अभी तक जोड़ा नहीं गया है। उपरोक्त को ध्यान में रखते हुए, हम एक संपीड़ित स्ट्रिंग को डीकोड करने के लिए निम्नलिखित विकल्प सुझा सकते हैं:

1. समारोह LZWDecode (InMsg: TEncodedString): शॉर्टस्ट्रिंग;
2. डी: टीडिक्शनरी;
3. आउट संदेश, tmpstr: शॉर्टस्ट्रिंग;
4. मैं: बाइट;
5. शुरू
6. आउट संदेश: = "";
7. tmpstr: = "";
8. इनिटडिक्ट (डी);
9. i के लिए: = 0 से लंबाई (InMsg) - 1 do
10. शुरू
11. अगर InMsg [i]> = D. वर्डकाउंट तो
12. tmpstr: = D. शब्द [InMsg [i - 1]] + D. शब्द [InMsg [i - 1]] [1]
13. अन्यथा
14. tmpstr: = D. शब्द [InMsg [i]];
15. आउट संदेश: = आउट संदेश + tmpstr;
16. अगर मैं> 0 तो
17. AddToDict (D, D. Words [InMsg [i - 1]] + tmpstr [1]);
18. समाप्त;
19. एलजेडडब्ल्यूडीकोड: = आउटएमएसजी;
20. समाप्त;

शब्दकोश एल्गोरिदम के लाभों में RLE की तुलना में उनकी उच्च संपीड़न दक्षता शामिल है। फिर भी, यह समझा जाना चाहिए कि इन एल्गोरिदम का वास्तविक उपयोग कुछ कार्यान्वयन कठिनाइयों से जुड़ा है।

एन्ट्रापी कोडिंग

शैनन-फ़ानो पेड़ों के साथ एन्कोडिंग

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

एन्कोडिंग के बिना, संदेश 40 बिट्स पर कब्जा कर लेगा (यह मानते हुए कि प्रत्येक वर्ण 4 बिट्स के साथ एन्कोड किया गया है), और शैनन-फ़ानो एल्गोरिथम 4 * 2 + 2 + 4 + 4 + 3 + 3 + 3 = 27 बिट्स का उपयोग करते हुए। संदेश की मात्रा में 32.5% की कमी आई है, लेकिन यह नीचे दिखाया जाएगा कि इस परिणाम में काफी सुधार किया जा सकता है।

हफमैन पेड़ के साथ एन्कोडिंग

हफ़मैन कोडिंग एल्गोरिथम, शैनन-फ़ानो एल्गोरिथम के कुछ साल बाद विकसित हुआ, इसमें उपसर्ग संपत्ति भी है, और, इसके अलावा, सिद्ध न्यूनतम अतिरेक, यही कारण है कि यह बेहद व्यापक है। हफ़मैन कोड प्राप्त करने के लिए, निम्नलिखित एल्गोरिथम का उपयोग किया जाता है:
1. वर्णमाला के सभी प्रतीकों को मुक्त नोड्स के रूप में दर्शाया जाता है, जबकि नोड का वजन संदेश में प्रतीक की आवृत्ति के समानुपाती होता है;
2. मुक्त नोड्स के सेट से, न्यूनतम वजन वाले दो नोड्स का चयन किया जाता है और चयनित नोड्स के वजन के योग के बराबर वजन वाला एक नया (पैरेंट) नोड बनाया जाता है;
3. चयनित नोड्स को मुफ्त सूची से हटा दिया जाता है, और उनके आधार पर बनाए गए मूल नोड को इस सूची में जोड़ा जाता है;
4. चरण 2-3 तब तक दोहराए जाते हैं जब तक कि मुक्त सूची में एक से अधिक नोड न हों;
5. निर्मित वृक्ष के आधार पर, वर्णमाला के प्रत्येक वर्ण को एक उपसर्ग कोड दिया जाता है;
6. संदेश प्राप्त कोड के साथ एन्कोड किया गया है।

उसी उदाहरण पर विचार करें जैसे शैनन-फ़ानो एल्गोरिथम के मामले में। हफ़मैन ट्री और "AAAAABVGDEZH" संदेश के लिए प्राप्त कोड अंजीर में दिखाए गए हैं। 2:

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

सिकंट फंक्शन ट्री के साथ एन्कोडिंग

सेकेंड फ़ंक्शन का उपयोग करके एन्कोडिंग लेखकों द्वारा विकसित एक एल्गोरिदम है जो उपसर्ग कोड प्राप्त करने की अनुमति देता है। एल्गोरिथ्म एक पेड़ के निर्माण के विचार पर आधारित है, जिसके प्रत्येक नोड में एक सेकेंडरी फ़ंक्शन होता है। एल्गोरिथ्म का अधिक विस्तार से वर्णन करने के लिए, कई परिभाषाओं को पेश करना आवश्यक है।
एक शब्द m बिट्स का एक क्रमबद्ध क्रम है (संख्या m को शब्द की लंबाई कहा जाता है)।
सेकेंड लिटरल अंक के अंक-मान के प्रकार की एक जोड़ी है। उदाहरण के लिए, शाब्दिक (4,1) का अर्थ है कि शब्द के 4 बिट 1 होने चाहिए। यदि शाब्दिक शर्त पूरी होती है, तो शाब्दिक को सत्य माना जाता है, अन्यथा यह गलत है।
एक k-bit secant k अक्षर का एक सेट है। यदि सभी अक्षर सत्य हैं, तो सेकेंट फ़ंक्शन स्वयं सत्य है, अन्यथा यह असत्य है।

पेड़ बनाया गया है ताकि प्रत्येक नोड वर्णमाला को निकटतम संभव भागों में विभाजित करे। अंजीर में। 3 एक छेदक वृक्ष का एक उदाहरण दिखाता है:

सामान्य स्थिति में सेकेंट फ़ंक्शंस का पेड़ इष्टतम कोडिंग की गारंटी नहीं देता है, लेकिन यह नोड्स में ऑपरेशन की सादगी के कारण काम की अत्यधिक उच्च गति प्रदान करता है।

अंकगणित कोडिंग

अंकगणित कोडिंग सूचना को संपीड़ित करने के सबसे कुशल तरीकों में से एक है। हफ़मैन एल्गोरिथ्म के विपरीत, अंकगणितीय कोडिंग आपको प्रति प्रतीक 1 बिट से कम की एन्ट्रापी वाले संदेशों को एन्कोड करने की अनुमति देती है। चूंकि अधिकांश अंकगणितीय कोडिंग एल्गोरिदम पेटेंट द्वारा संरक्षित हैं, केवल मूल विचारों का वर्णन नीचे किया जाएगा।
मान लीजिए कि प्रयुक्त वर्णमाला में क्रमशः p_1, ..., p_N, आवृत्तियों के साथ N प्रतीक a_1, ..., a_N हैं। तब अंकगणित कोडिंग एल्गोरिथ्म इस तरह दिखेगा:
एक कार्यशील अर्ध-अंतराल के रूप में लें)