У меня есть (огромный) набор подобных файлов данных. Набор постоянно растет. Размер единственного файла о 10K. Каждый файл должен быть сжат самостоятельно. Сжатие сделано с zlib библиотекой, которой пользуются java.util.zip.Deflater
класс. При передаче словаря Выкачивать использованию алгоритма setDictionary
, Я могу улучшить степень сжатия.
Существует ли путь (алгоритм) для нахождения 'оптимального' словаря, т.е. словаря с полной оптимальной степенью сжатия?
См. zlib руководство
Джон Рейзер объяснил сжатие :
Для словаря: составьте гистограмму коротких подстрок , отсортируйте по результату (количество вхождений, умноженное на количество битов, сохраненных при сжатии) и поместите в словарь подстроки с наибольшей отдачей. Например, если k - длина самой короткой подстроки, которая может быть сжата (обычно 3 == k или 2 == k), то сделайте гистограмму всех подстрок длин k, 1 + k, 2 + k и 3 + к. Конечно, есть искусство помещать эти подстроки в словарь, используя преимущества подстрок, перекрытия, короткие строки ближе к концу высокого адреса и т. Д.
Ядро Linux использует аналогичную технику для сжать имена символов, которые используются для печати трассировки стека вызова подпрограммы.См. Файл scripts / 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)")
Это просто целые слова, а не подстроки. Также есть способы перекрыть общие подстроки, чтобы сэкономить место в словаре.