Алгоритм Хаффмана

Архивация. Транспортное кодирование

Подавляющее большинство современных форматов записи данных содержат их в виде, удобном для быстрого манипулирования, для удобного прочтения пользователями. При этом данные занимают объем больший, чем это действительно требуется для их хранения Алгоритмы, которые устраняют избыточность записи данных, называются алгоритмами сжатия данных, или алгоритмами архивации. В настоящее время существует огромное множество программ для сжатия данных, основанных на нескольких основных способах.

Зачем же нужна архивация в криптографии? Дело в том, что в современном криптоанализе, то есть науке о противостоянии криптографии, с очевидностью доказано, что вероятность взлома криптосхемы при наличии корреляции между блоками входной информации значительно выше, чем при отсутствии таковой. А алгоритмы сжатия данных по определению и имеют своей основной задачей устранение избыточности, то есть корреляций между данными во входном тексте.

Все алгоритмы сжатия данных качественно делятся на алгоритмы сжатия без потерь, при использовании которых данные на приемной восстанавливаются без малейших изменений, и алгоритмы сжатия с потерями, которые удаляют из потока данных информацию, незначительно влияющую на суть данных, либо вообще невоспринимаемую человеком (такие алгоритмы сейчас разработаны только для аудио- и видеоизображений) В криптосистемах, естественно, используется только первая группа алгоритмов.

Существует два основных метода архивации без потерь:

- алгоритм Хаффмана, ориентированный на сжатие последовательностей байт, не связанных между собой;

- алгоритм Лемпеля-Зива, ориентированный на сжатие любых видов текстов, то есть использующий факт неоднократного повторения «слов» - последовательностей байт.

Практически все популярные программы архивации без потерь (ARJ, RAR, ZIP) используют объединение этих двух методов – алгоритм LZH/\.

Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, - реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов - длинные, то суммарный объем файла уменьшится.

В теории кодирования информации показывается, что код Хаффмана является префиксным, то есть код никакого символа не является началом кода какого-либо другого символа. А из этого следует, что код Хаффмана однозначно восстановим получателем, даже если не сообщается длина кода каждого переданного символа.

Дата добавления: 2014-01-11