Здесь описаны некоторые современные методы сжатия: метод Хаффмана, арифметическое кодирование, LZ77….. Описываются алгоритмы, которые используются в архиваторах Zip, 7-Zip НА, CabArc(*.саb-файлы), RAR...

Алгоритмы и методы сжатия данных Идея словарных методов

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

Мы пытаемся преобразовать исходную последова­тельность путем ее представления в таком алфавите, что его "буквы" явля­ются фразами словаря, состоящими, в общем случае из произвольного ко­личества символов входной последовательности.

Словарь - это набор таких фраз, которые, предположительно, будут встре­чаться в обрабатываемой последовательности. Индексы фраз должны быть построены таким образом, чтобы в среднем их представление занимало меньше места, чем требуют замещаемые строки. За счет этого и происходит сжатие.

Уменьшение размера возможно в первую очередь за счет того, что обычно в сжимаемых данных встречается лишь малая толика всех возмож­ных строк длины и, поэтому для представления индекса фразы требуется, как правило, меньшее число битов, чем для представления исходной строки.

Например, рассмотрим количество взаимно различных строк длины от 1 до 5 в тексте на русском языке (роман Ф.М. Достоевского "Бесы", обычный неформатированный текст, размер около 1.3 Мб):

Длина строки	Количество различных строк	Использовано комбинаций, % от всех возможных
5	196969	0.0004
4	72882	0.0213
3	17481	0.6949
2	2536	13.7111
1	136	100.0000

Иначе говоря, размер (мощность) алфавита равен 136 символам, но ре­ально используется только 2536/(136136)100% ~ 13.7 % от всех возможных двухсимвольных строк и т. д.

Если есть гипотезы о частоте ис­пользования тех или иных фраз либо проводился какой-то частотный анализ обрабатываемых данных, то мы можем назначить более вероятным фразам коды меньшей длины. Например, для той же электронной версии романа "Бесы" статистика встречаемости строк длины 5 имеет вид:

N	Количество строк длины 5, встретившихся ровно N раз	Количество относительно общего числа всех различных строк длины 5, %
1	91227	46.3
2	30650	15.6
3	16483	8.4
4	10391	5.3
5	7224	3.7
>6	40994	20.7
Всего	196969	100.0

Заметим, что из всех 197 тыс. различных строк длины 5 почти половина встретилась лишь один раз, поэтому они вообще не будут использованы как фразы при словарном кодировании в том случае, если словарь строится только из строк обработанной части потока. Наблюдаемые частоты остав­шейся части строк быстро уменьшаются с увеличением N, что указывает на выгодность применения статистического кодирования, когда часто исполь­зуемым фразам ставятся в соответствие коды меньшей длины.

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

Ниже будут рассмотрены алгоритмы словарного сжатия, относимые к классу методов Зива - Лемпела. В качестве примера словарного алгоритма иного класса укажем .

Методы Зива - Лемпела ориентированы на сжатие качественных дан­ных, причем эффективность применения достигается в том случае, когда статистические характеристики обрабатываемых данных соответствуют мо­дели источника с памятью.