Как найти хороший/оптимальный словарь для zlib 'setDictionary' при обработке заданного набора данных?

Ответ 1

John Reiser объясняется на comp.compression:

Для словаря: сделайте гистограмму коротких подстрок, сортируйте по выигрышу (количество вхождений умножает количество бит, сохраненных при сжатии) и помещайте подстроки с наивысшей выгодой в словарь. Например, если k - длина самой короткой подстроки, которая может быть сжата (обычно 3 == k или 2 == k), тогда сделайте гистограмму всех подстрок длин k, 1 + k, 2 + k и 3 + к. Конечно, есть некоторое искусство помещать эти подстроки в словарь, используя подстроки, перекрывающиеся, короткие строки ближе к верхнему адресу и т.д.

Ядро Linux использует подобный метод для сжатия имен символов, которые используются для печати обратных трасс стека вызовов подпрограммы. См. Файл-скрипты/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

Вы можете попробовать его скопировать-вставить-запустить здесь (add: "print (dict)" )

Это просто целые слова, а не подстроки. Также есть способы перекрытия общих подстрок, чтобы сэкономить место в словаре.