डेटा के दिए गए सेट को संसाधित करते समय zlib 'setDictionary' के लिए एक अच्छा/इष्टतम शब्दकोश कैसे ढूंढें?

Question

मेरे पास समान डेटा फ़ाइलों का एक (विशाल) सेट है। सेट लगातार बढ़ रहा है। एक फ़ाइल का आकार लगभग 10K है। प्रत्येक फ़ाइल को स्वयं पर संपीड़ित किया जाना चाहिए। संपीड़न zlib लाइब्रेरी के साथ किया जाता है, जिसका उपयोग java.util.zip.Deflater वर्ग द्वारा किया जाता है। setDictionary का उपयोग कर डिफ्लेट एल्गोरिदम में एक शब्दकोश को पास करते समय, मैं संपीड़न अनुपात में सुधार कर सकता हूं।

क्या 'इष्टतम' शब्दकोश खोजने के लिए कोई तरीका है (एल्गोरिदम), यानी समग्र इष्टतम संपीड़न अनुपात वाला एक शब्दकोश?

zlib manual

Answer 1

जॉन रीसर explained on comp.compression देखें:

शब्दकोश के लिए: लघु सबस्ट्रिंग के हिस्टोग्राम बनाने के लिए, प्रकार अदायगी से (घटनाओं बार बिट्स की संख्या की संख्या बचाया जब संकुचित) और डाल शब्दकोश में सबसे ज्यादा भुगतान substrings। उदाहरण के लिए, यदि के सबसे छोटी सबस्ट्रिंग की लंबाई है जिसे संपीड़ित किया जा सकता है (आमतौर पर 3 == के या 2 == के), तो लम्बाई के सभी सबस्ट्रिंग्स का एक हिस्टोग्राम बनाएं, 1 + के, 2 + के, और 3 + K। बेशक वहाँ शब्दकोश में उन सबस्ट्रिंग रखने, सबस्ट्रिंग उच्च पते अंत के अतिव्यापी, लघु तार नजदीक का लाभ लेने, आदि के लिए कुछ कला है

लिनक्स कर्नेल एक ऐसी ही तकनीक के नाम संपीड़ित करने के लिए उपयोग करता है प्रतीक जो subroutine कॉलिंग स्टैक के बैकट्रैस प्रिंट करने के लिए उपयोग किया जाता है। फ़ाइल स्क्रिप्ट/kallsyms.c देखें। उदाहरण के लिए, https://code.woboq.org/linux/linux/scripts/kallsyms.c.html

zlib manual recommends शब्दकोश के अंत में सबसे आम आवृत्तियों जगह।

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

ऐसा इसलिए है क्योंकि एलजेड 77 में एक स्लाइडिंग विंडो एल्गोरिदम है, इसलिए बाद के सबस्ट्रिंग पहले कुछ की तुलना में डेटा की आपकी स्ट्रीम पर पहुंच योग्य होंगे।

मैं तारों के अच्छे समर्थन के साथ उच्च स्तर की भाषा के साथ शब्दकोश उत्पन्न करने के साथ खेलूँगा। एक कच्चे जावास्क्रिप्ट उदाहरण:

var str = "The dictionary should consist of strings (byte sequences) that" 
    + " are likely to be encountered later in the data to be compressed," 
    + " with the most commonly used strings preferably put towards the " 
    + "end of the dictionary. Using a dictionary is most useful when the" 
    + " data to be compressed is short and can be predicted with good" 
    + " accuracy; the data can then be compressed better than with the " 
    + "default empty dictionary."; 
// Extract words, remove punctuation (extra: replace(/\s/g, " ")) 
var words = str.replace(/[,\;.:\(\)]/g, "").split(" ").sort(); 
var wcnt = [], w = "", cnt = 0; // pairs, current word, current word count 
for (var i = 0, cnt = 0, w = ""; i < words.length; i++) { 
    if (words[i] === w) { 
     cnt++; // another match 
    } else { 
     if (w !== "") 
      wcnt.push([cnt, w]); // Push a pair (count, word) 
     cnt = 1; // Start counting for this word 
     w = words[i]; // Start counting again 
    } 
} 
if (w !== "") 
    wcnt.push([cnt, w]); // Push last word 
wcnt.sort(); // Greater matches at the end 
for (var i in wcnt) 
    wcnt[i] = wcnt[i][1]; // Just take the words 
var dict = wcnt.join("").slice(-70); // Join the words, take last 70 chars 

फिर dict के साथ 70 वर्ण की एक श्रृंखला है:

rdsusedusefulwhencanismostofstringscompresseddatatowithdictionarybethe 

आप इसे कॉपी-पेस्ट रन कोशिश here कर सकते हैं (जोड़ें: "प्रिंट (dict)")

यह सिर्फ पूरे शब्द है, सबस्ट्रिंग नहीं। शब्दकोश पर स्थान बचाने के लिए सामान्य सबस्ट्रिंग को ओवरलैप करने के तरीके भी हैं।