Comments 6
А вот, кстати, объясните, если вы в курсе. Допустим, разрядность индекса у нас - 12 бит, и последний индекс - 100000000011 (только что записанный). Декодер читает - видит первый бит - "1". Он понимает - "О! Раз первый бит 1 - то мы можем получить 100000000000, 100000000001, 100000000010 или 100000000011". В любом случае мы получим после единицы девять нулей. И кодер, и декодер это знают. Так почему бы не посылать их? Если и кодер и декодер знают, что идет далее, это ведь можно не посылать?
Тем не менее, например в GIF (использующем LZW), да и в других LZW-архиваторах - шлется весь индекс, независимо ни от чего. Почему?
Я думаю, что это сделано для простоты реализации. LZW - очень простой но при этом эффективный алгоритм, который каждый может реализовать без мудрствований. Но если продолжать вашу мысль и довести её до идеала, то оптимально было бы применять для каждой фразы LZW адаптивное интервальное кодирование или что-то в этом духе. Тогда вся последовательность из z фраз LZW будет занимать всего log2(256) + log2(257) + ... + log2(255 + z) + 1 битов, ну или log2(256) + log2(257) + ... + log2(d) + log2(d) + ... + log2(d) + 1 битов, если размер словаря ограничен d фразами (например, d = 2^16, как обычно полагают). В стандартных реализациях LZW (типа LZC) тоже есть механизмы уменьшения размера кодов для первых фраз (хоть и не такие оптимальные): обычно первые фразы занимают последовательно 9, 10, ..., 16 битов, а потом словарь перестаёт расти. Вполне возможно, что на реальных датасетах этот простой трюк не намного хуже более хитрого оптимального кодирования. Вообще, если нужно сжатие по-лучше, то лучше сразу обращаться к LZMA, а не пытаться тюнить LZW.
LZ + опциональный Huffman + арифметическое кодирование дают больший прирост в скорости декодирования чем lzma при сравнимо той же степени сжатия
Бегло прошёлся по бенчмаркам в интернете и, судя по всему, LZMA и его производные даже против deflate (это LZ77 с Хаффманов) дают в 1.5 - 2 раза лучшее сжатие. А против LZW они будут ещё лучше (LZW проигрывает deflate по сжатию, но не так драматически). По-моему это не "сравнимая" степень сжатия. Зависит от сжимаемых данных, конечно, но эти бенчмарки часто довольно репрезентативны. Недавно, кстати, на хабре была хорошая статья на близкую тему: https://habr.com/ru/post/570694/ (там же есть ссылка на один хороший бенчмарк; ещё можно посмотреть http://www.mattmahoney.net/dc/text.html). Много раз уже сталкивался с похожим мнением, что сжатие не важно и важнее скорость. Согласен, есть такие приложения, где это так. Но даже в таком случае LZW далеко не лучший выбор и методы на основе LZ77 (не обязательно LZMA) работаю лучше. Например, zstd с флагом "level 2" (или около того), судя по бенчмаркам, так же эффективен по степени сжатия, как deflate с наилучшим сжатием, но раз в 5 быстрее декодирует. Я уверен, что LZW с Хаффманом/арифметиком декодирует медленнее, чем deflate (LZW для декодирования использует более сложного вида словарь, а deflate просто копирует уже декодированные куски); в интернете пишут, что LZW в 2 раза медленнее декодирует, чем deflate, в некоторых реализациях. Без Хаффмана LZW точно по-быстрее будет, но тоже не факт, что быстрее чем deflate. Так что zstd явно гораздо лучше в этом отношении и чем LZW, и чем deflate.
Ну как минимальная оптимизация - пока размер словаря от 256 о 511 - можно писать 9-битные индексы, потом до 1023 - 10-битные и т.д. до максимальной длины индекса. Следующим шагом - да, выкидывать внутренние нули, но тогда есть риск в конце выйти не на границу байта. Хотя надо считать.
Сжатие данных LZW