Где я могу найти алгоритм сжатия без потерь, который производит выходные данные без заголовка?

Question

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

Answer 1

Конечно, это возможно. Среди прочего, компрессорам семейства LZ не нужно ничего выводить, кроме самих сжатых данных, так как словарь создается в режиме реального времени по мере сжатия (или распаковки). У вас есть много справочных реализаций для этих алгоритмов типа LZ. Например, LZMA , компонент 7zip.

Answer 2

Адаптивное кодирование Хаффмана делает именно это. В более общем смысле термин адаптивное кодирование используется для описания энтропийных кодов с этим свойством. Некоторые словарные коды тоже имеют это свойство, например кодирование длин серий (RLE) и Lempel-Ziv-Welch (LZW) .

Answer 3

Кодировка длины пробега будет одним примером

Answer 4

lzo приходит на ум. он используется в OpenVPN, с отличными результатами

Answer 5

Почему вы ищете алгоритмы сжатия с сжатым выводом без заголовка?

Возможно (а) у вас есть система, такая как двухсторонняя телефония, которая требует потокового сжатия / распаковки с малой задержкой. Категория адаптивного кодирования алгоритмов сжатия, упомянутых Заком Скривеной и семейство LZ алгоритмов сжатия словаря , упомянутых Диего Севильей и Хавьером отлично подходят для такого рода приложений. Практические реализации этих алгоритмов обычно do имеют один или два байта метаданных. в начале (делая их бесполезными для (b) приложений), но это практически не влияет на задержку.

Возможно, (b) вас в основном интересует криптография, и вы слышали, что сжатие перед шифрованием дает некоторые улучшенные свойства безопасности, если сжатый текст не имеет фиксированного заголовка метаданных "шпаргалка". Современные алгоритмы шифрования не являются (насколько нам известно) уязвимыми для таких «шпаргалок», но если вы параноик, вас может заинтересовать «биективное сжатие» ( a , b , c и т. д.). Невозможно обнаружить ошибки при передаче (перевернутые биты, вставленные биты, удаленные биты и т. Д.), Когда получатель получает такой сжатый вывод (что делает эти алгоритмы не особенно полезными для (a) приложений).

Возможно, (c) вас интересует сжатие без заголовка по какой-то другой причине. Звучит увлекательно - что это за причина?