Сущность символ-ориентированных методов сжатия информации.
Сущность символ-ориентированных (словарных) методов состоит в последовательном анализе сжим. информации с целью поиска повторяющихся или проаналированных ранее в данном документе последовательностей и замене таких последовательностей на более короткие. Методы, основанные на словарном подходе, не рассматривают статистические модели, они также не используют коды переменной длины. Вместо этого они выбирают некоторые последовательности символов, сохраняют их в словаре, а все последовательности кодируются в виде меток, используя словарь. Словарь может быть:
– статический словарь – является постоянным. Иногда в него добавляют новые последовательности, но никогда не удаляют.
– динамический (адаптивный) словарь содержит последовательности, ранее поступившие из входного файла, при этом разрешается и добавление, и удаление данных из словаря по мере чтения входного файла.
К этим методам сжатия относятся следующие алгоритмы: LZ77/78, LZW, LZO и др.
LZ-алгоритм. Почти все практические словарные кодировщики принадлежат семье алгоритмов, происходящих из работы Зива и Лемпела. Сущность состоит в том, что фразы заменяются указателем на то место, где они в тексте уже ранее появлялись. Это семейство алгоритмов называется методом Зива-Лемпела и обозначается как LZ-сжатие и разделяется на два семейства - алгоритмы типа LZ77 и алгоритмы типа LZ78. Этот метод быстро приспосабливается к структуре текста и может кодировать короткие функциональные слова, т.к. они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов.
Раскодирование сжатого текста осуществляется напрямую – происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. Одной из форм такого указателя есть пара (i,j), которая заменяет последовательность из j символов, начинающуюся со смещения i во входном потоке. По мере выполнения обработки словарь скользит по входному потоку данных. Скользящее окно имеет длину N и состоит из двух частей: последовательности уже закодированных символов, которая и является словарем, и упреждающего буфера, или буфера предварительного просмотра.
 |
Пример: сжать строку "кот_ломом_колол_слона" длиной 21 символ. Пусть длина буфера равна 7 символам, а размер словаря больше длины сжимаемой строки.
Для кодирования i нам достаточно 5 битов, для j нужно 3 бита, и пусть символы требуют 1 байта для своего представления. Тогда всего мы потратим 12·(5+3+8) = 192 бита. Исходно строка занимала 21·8 = 168 битов, т.е. LZ77 кодирует нашу строку еще более расточительным образом.