Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Идея словарных методов

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

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

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

Уменьшение размера возможно в первую очередь за счет того, что обычно в сжимаемых данных встречается лишь малая толика всех возмож­ных строк длины и, поэтому для представления индекса фразы требуется, как правило, меньшее число битов, чем для представления исходной строки. Например, рассмотрим количество взаимно различных строк длины от 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, что указывает на выгодность применения статистического кодирования, когда часто исполь­зуемым фразам ставятся в соответствие коды меньшей длины.

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

Очевидно, что процессы моделирования и кодирования, рассматриваемые в гл. 4, для словарных методов сливаются. Моделирование в явном виде может выполняться уже только для индексов. Заметим, что апологеты идеи универ­сального моделирования и кодирования последовательно изучают любой метод, не вписывающийся явно в их модель, и обычно достаточно убедительно доказы­вают, что для него можно построить аналог в виде статистического метода. Так, например, доказано, что несколько рассматриваемых ниже словарных ал­горитмов семейства Зива - Лемпела могут быть воспроизведены в рамках кон­текстного моделирования ограниченного порядка либо с помощью моделей со­стояний [6, 9].

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

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