डेटा संपीड़न

मुझे इस मुद्दे पर लंबे समय से दिलचस्पी होने लगी थी। मेमोरी, डिस्क स्थान को बचाने का विचार लंबे समय से और शायद सभी के लिए है। RLE एल्गोरिथम के समान अपना खुद का कम्प्रेशन अल्गोरिथम लिखने का पहला प्रयास 2000 में हुआ था, तब कई और अधिक मूल संपीड़न अवधारणाएँ थीं, लेकिन यह प्रारंभिक परीक्षणों से आगे नहीं बढ़ीं। 2005 में, उन्होंने संपीड़न के विचार को गंभीरता से लिया। 6 साल बाद, मैं अनुसंधान के कुछ अंश साझा करता हूं।

इस लेख को समझने और समझने के लिए, हम कुछ शब्दावली का परिचय देते हैं:

• एन - प्राकृतिक संख्या
• शब्द - एन बिट, अर्थात् एन बिट्स को एक शब्द में समूहीकृत (बाइट एक 8 बिट शब्द है)
• शब्द में संयोजन 2 ^ N (N की शक्ति से दो) (बाइट में 256 संयोजन) हैं
• ब्लॉक (वाक्य) - N * 2 ^ N (शब्द * शब्द संयोजन)
• ब्लॉक में संयोजन - 2 ^ (एन * 2 ^ एन)
• एक ब्लॉक में अद्वितीय शब्द - 2 ^ एन
• ब्लॉक आवंटन तालिका - एन रो (पंक्ति में एन यूनिक शब्दों के साथ ब्लॉक के संयोजन की संख्या)
• प्रवेश तालिका - एन रो (एक पंक्ति में एन अद्वितीय शब्दों के साथ ब्लॉक की घटनाओं की संख्या)
• आने वाली धारा - जानकारी का एक टुकड़ा में बाइट्स की एक सीमित संख्या

एक ब्लॉक में अनूठे शब्दों की परिभाषा - एक ब्लॉक में शब्दों के गैर-दोहराए जाने वाले संयोजनों की संख्या। एक उदाहरण:
1 1 1 1 1 1 1 1
8 8 8 8 8 8 8 8
1 8 2 5 1 5 1 2
4 6 7 3 3 3 3 3

N = 3 वाले ब्लॉक में अद्वितीय शब्द खोजना

एक ब्लॉक में सभी संयोजनों के माध्यम से जाने के बाद, हमें ब्लॉक वितरण की एक तालिका मिलती है। एक उदाहरण:
1 4
2 84
3 144
4 24

256 (8 ) - 2^(N*2^N)

ब्लॉक आवंटन तालिका N = 2

01 16
02 7864080
03 23996064960
04 7504175995680
05 574579238688000
06 15768930151054080
07 189225474428390400
08 1111400775560275200
09 3407360398041600000
10 5630409646557696000
11 5045340384103219200
12 2403608358767616000
13 577538743541760000
14 62977597562880000
15 2510734786560000
16 20922789888000

18446744073709551616 (64 ) - 2^(N*2^N)

ब्लॉक आवंटन तालिका N = 4

एन = 4 और अधिक के लिए, कुछ सेकंड में जानवर बल द्वारा ब्लॉक वितरण की एक तालिका अब प्राप्त नहीं की जा सकती है।

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

एन = 8 पर घटनाओं की तालिका के अनुसार प्लॉटिंग, फ़ाइलों को यहां डाउनलोड किया जा सकता है

एन = 8 पर घटनाओं की तालिका के अनुसार प्लॉटिंग, फ़ाइलों को यहां डाउनलोड किया जा सकता है

एन = 8 पर घटनाओं की तालिका के अनुसार प्लॉटिंग, फ़ाइलों को यहां डाउनलोड किया जा सकता है

इस तरह से डेटा स्ट्रीम का विश्लेषण करके, यह स्पष्ट है कि संपीड़ित और एन्क्रिप्टेड डेटा पर अप्रयुक्त लाइनें हैं जो एक से अधिक ब्लॉक नहीं मिली हैं, क्योंकि ब्लॉक को उनके अनन्य शब्दों द्वारा अलग किया जाता है, शामिल नहीं किए गए ब्लॉक की संख्या वितरण तालिका पर पाई जा सकती है।

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

विशेष एल्गोरिथ्म प्रदर्शन

वीडियो डेटा पर डेटा संपीड़न में सुधार की संभावना को प्रदर्शित करने के लिए बनाया गया "बिना अतिरेक के।" यह एक विशेष एल्गोरिथ्म है जो स्रोत डेटा में अतिरेक बनाता है।

पुनश्च पहला एल्गोरिथ्म बहुत लंबे समय से चल रहा है, वीडियो ने काम करना शुरू नहीं किया। वीडियो में दूसरा एल्गोरिदम दिखाया गया है। यह BTW एल्गोरिथ्म के रूप में एक ही विचार पर काम करता है, अर्थात, यह पहले डेटा तैयार करता है, और फिर यह डेटा शास्त्रीय एल्गोरिथ्म द्वारा संकुचित होता है।