Алгоритмы, структуры данных
5c8b6e8c

СЛОВАРHЫЕ МЕТОДЫ.


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

Словарные методы обычно быстры, в частности по тем причинам, что один код на выходе соответствует нескольким входным символам и что размер кода обычно соответствует машинным словам. Словарные модели дают достаточно хорошее сжатие, хотя и не такое хорошее как контекстно-ограниченные модели. Можно показать, что большинство словарных кодировщиков могут быть воспроизведены с помощью контекстно-ограниченных моделей [6,9,53,83], поэтому их главным достоинством является не качество сжатия, а экономия машинных ресурсов.

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



Содержание раздела