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

Question

我有一组（大量）类似的数据文件。该集合正在不断增长。单个文件大小约为10K。每个文件必须单独压缩。压缩是通过 zlib 库完成的，该库由

java.util.zip.Deflater

类使用。当使用

setDictionary

将字典传递给 Deflate 算法时，我可以提高压缩率。

有没有办法（算法）找到“最佳”字典，即具有整体最佳压缩比的字典？

参见zlib手册

Answer 1

John Reiser 解释 comp.compression：

对于字典：制作一个短子串直方图，按收益排序（出现次数乘以压缩时保存的位数）并将最高收益子串放入字典中。 例如，如果k是可压缩的最短子串的长度（通常为3==k或2==k），则将所有长度为k、1+k、2+k的子串制作直方图，并3+k。 当然，将这些子字符串放入字典中需要一些技巧，利用子字符串、重叠、靠近高地址端的短字符串等。

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

zlib 手册建议将最常见的出现位置放在字典的末尾。

字典应由稍后可能在要压缩的数据中遇到的字符串（字节序列）组成，最常用的字符串最好放在字典的末尾。当要压缩的数据很短并且可以很准确地预测时，使用字典是最有用的；与默认的空字典相比，可以更好地压缩数据。

这是因为 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

您可以尝试复制粘贴运行这里（添加：“print（dict）”）

这只是整个单词，而不是子字符串。还有一些方法可以重叠公共子字符串以节省字典空间。