Блог

Я пытаюсь понять алгоритм deflate, и я прочитал о кодах Хаффмана, а также о сжатии LZ77. Я играл с размерами сжатия разных строк и наткнулся на то, что не мог объяснить. Строка aaa при сжатии, как через zlib, так и через gzip, оказывается того же размера, aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa что и (36 a с).

Прежде чем читать об этом, я бы предположил, что компрессор выполняет что-то вроде хранения 36 * a вместо каждого символа по отдельности, но я не смог найти нигде в спецификациях, где это упоминается.

Использование фиксированного кода Хаффмана дало тот же результат, поэтому я предполагаю, что экономия места заключается в LZ77, но при этом используются только пары расстояние-длина. Как это позволит строке длиной 3 расширяться в 12 раз без увеличения размера?

Прерывание строки a s одним или несколькими b s в середине резко увеличивает размер. Если пары расстояния и длины — это то, что делает работу, почему она не может просто пропустить b s при поиске в обратном направлении? Или используются коды Хаффмана, и я неправильно понял, что подразумевают фиксированные коды Хаффмана?

36 «a» эффективно кодируются LZ77 по длине выполнения, предоставляя первую «a» в качестве литерала, а затем совпадение с расстоянием в единицу и длиной 35. Длина может достигать 258 для deflate.

Поищите в Интернете учебные пособия по LZ77, кодированию Хаффмана и deflate. Вы можете разобрать полученные сжатые данные с помощью infgen, чтобы получить более полное представление о том, как данные представляются.