ГЛАВА 2 СЛОВАРНЫЕ МЕТОДЫ

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

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

В результате выходной файл состоит из индексов и рядов слов, поэтому необходимо уметь делать различие между ними. Один возможный способ это добавление к записываемому в файл образчику еще один дополнительный бит. В принципе, 19-битовый индекс будет достаточен для точного указания слов в словаре объема  элементов. Поэтому, если прочитанное слово найдено в словаре, то можно записать 20-битную ссылку, состоящую из флагового бита (возможно, нулевого), за которым следует 19 битов индекса. Если данное слово не обнаружено в словаре, записывается флаг 1, потом длина слова и, наконец, само это слово.

Пример: Предположим, что слово bet находится в словаре под номером 1025. Тогда оно будет закодировано 20-битовым числом 0|0000000010000000001. Пусть слово xet не обнаружено в словаре. Тогда в выходной файл будет записана последовательность битов 1|0000011|01111000|01100101|01110100. В этом четырехбайтовом числе 7-битовое поле 0000011 означает, что за ним следуют еще три байта.

Если считать, что размер записывается в виде 7-битового числа и что средний размер слова состоит из 5 букв, то несжатое слово будет в среднем занимать 6 байт (= 48 бит) в выходном файле. Сжатие 48 бит в 20 является замечательным, при условии, что это делается достаточно часто. При этом, возникает вопрос: «Сколько совпадений слов надо обнаруживать в словаре, чтобы иметь общее сжатие?». Пусть вероятность обнаружения слова в словаре равна . После чтения и сжатия  слов размер выходного файла будет равен . Размер входного файла равен (при условии, что слово имеет 5 букв) . Тогда сжатие будет достигаться, если , то есть, при . Следовательно, надо иметь 29% или больше успешных нахождений слов в словаре для положительного сжатия.

Пример: Если вероятность обнаружения выше, например, , то размер выходного файла будет равен . Размер входного файла равен, как и раньше, . Фактор сжатия равен .

До тех пор, пока входной файл содержит английский текст, большинство слов будут обнаружены в полумиллионном словаре. Для других типов данных, разумеется, это не будет выполняться. В файле, содержащем код компьютерной программы будут находиться «слова» типа cout, xor, malloc, которые, возможно, не удастся обнаружить в словаре английского языка. А бинарный файл, если его рассматривать в ASCII кодах, обычно, содержит всякий «мусор», который едва ли удастся обнаружить в этом словаре. В результате произойдет расширение вместо сжатия.

Все это говорит о том, что статический словарь не самый лучший выбор для общего алгоритма сжатия. Однако в ряде специальных случаев, это будет хорошим методом. Возьмем сеть компьютерных магазинов. Их файлы во множестве будут содержать слова типа nut, bolt, paint. В то же время, слова peanut, lightning, painting будут встречаться реже. Поэтому специальное компрессионное программное обеспечение этой фирмы может использовать очень маленький специализированный словарь, состоящий всего из нескольких сотен слов. Каждый сетевой компьютер будет иметь копию этого словаря, что позволит легко сжимать файлы и пересылать их по сети между магазинами и офисами фирмы.

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

1. Алгоритм использует только операции над последовательностями строк типа поиска и сравнения и не использует арифметические вычисления.

2. Декодер очень прост (значит, мы имеем дело с асимметричным методом компрессии). В статистическом методе сжатия декодер в точности противоположен кодеру (делается симметричная компрессия). В адаптивном методе словарного сжатия декодер должен прочитать файл, распознать, является ли прочитанный образчик меткой или несжатыми данными, использовать метку для извлечения данных из словаря и выдать исходный разжатый файл. Не придется производить сложный грамматический разбор входного файла, также не нужно делать поиск по словарю для обнаружения совпадений. Многие программисты тоже не любят делать это.

Большая честь для ученого, когда его имя присваивается научному открытию, методу или явлению. Еще более почетно, когда имя присваивается целому научному направлению. Как раз это случилось с Якобом Зивом (Jacob Ziv) и Абрахамом Лемпэлом (Abraham Lempel). В 1970 году эти ученые разработали два первых метода, называемые LZ77 и LZ78, для словарного сжатия данных. Их замечательные идеи вдохновили многих исследователей, которые стали улучшать, обобщать и комбинировать их с другими методами (например, с RLE или со статистическим методом) для создания многих широко используемых на практике алгоритмов сжатия без потери информации для компрессии текстов, изображений и звука.

Далее в этой главе описано несколько общих LZ методов компрессии и показано, как они развивались из основополагающих идей Зива и Лемпэла.