在处理给定的数据集时,如何为zlib'setDictionary'找到一个好的/最佳的字典？

我有一组(巨大的)类似的数据文件.该集合不断增长.单个文件的大小约为10K.每个文件都必须自己压缩.使用zlib库完成压缩,该库由java.util.zip.Deflater类使用.使用字典将字典传递给Deflate算法时setDictionary,我可以提高压缩率.

有没有办法(算法)找到'最佳'字典,即具有整体最佳压缩比的字典？

请参阅zlib手册

1> alecco..：

---

John Reiser 解释comp.compression:

对于字典:制作短子串的直方图,按收益排序(出现次数乘以压缩时保存的位数),并将最高支付子字符串放入字典中.例如,如果k是可以压缩的最短子串的长度(通常为3 == k或2 == k),则制作长度为k,1 + k,2 + k的所有子串的直方图,以及3 + K. 当然,将这些子串放入字典中有一些技巧,利用子串,重叠,更接近高地址端的短串等.

Linux内核使用类似的技术来压缩用于打印子例程调用堆栈的回溯的符号名称.请参阅文件scripts/kallsyms.c.例如,https://code.woboq.org/linux/linux/scripts/kallsyms.c.html

所述的zlib手册建议放置的最常见ocurrences在字典的末尾.

字典应该包含稍后可能在要压缩的数据中遇到的字符串(字节序列),最常用的字符串优选地放在字典的末尾.当要压缩的数据很短并且可以高精度地预测时,使用字典是最有用的; 然后可以比使用默认空字典更好地压缩数据.

这是因为LZ77具有滑动窗口算法,因此后续的子串将在您的数据流上比前几个更容易到达.

我会使用更高级别的语言生成字典,并且支持字符串.一个粗略的JavaScript示例:

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

你可以在这里试试copy-paste-run (添加:"print(dict)")

这只是整个单词,而不是子串.还有一些方法可以重叠常见的子串以节省字典上的空间.

---

有没有办法"导出"通过压缩文件创建的字典,以便将其应用于后续文件,即自动"训练"字典？

---

@RustyX,您可以使用[infgen](https://github.com/madler/infgen)查看压缩数据的结构,并从中查看数据中最常引用的文字.使用自定义词典,您可以确保存在更长的匹配子序列并获得更好的压缩率.