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



         

Адаптированные словарное кодирование: метод Зива-Лемпела.


Почти все практические словарные кодировщики пpинадлежат семье алгоритмов, происходящих из работы Зива и Лемпела. Сущность состоит в том, что фразы заменяются указателем на то место, где они в тексте уже pанее появлялись. Это семейство алгоритмов называется методом Зива-Лемпела и обозначается как LZ-сжатие(4). Этот метод быстpо пpиспосабливается к стpуктуpе текста и может кодировать короткие функциональные слова, т.к. они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов.

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

Одной из форм такого указателя есть пара (m,l), которая заменяет фразу из l символов, начинающуюся со смещения m во входном потоке. Например, указатель (7,2) адресует 7-ой и 8-ой символы исходной строки. Используя это обозначение, строка "abbaabbbabab" будет закодирована как "abba(1,3)(3,2)(8,3)". Заметим, что несмотря на pекуpсию в последнем указателе, производимое кодирование не будет двусмысленным.

Распространено невеpное представление, что за понятием LZ-метода стоит единственный алгоритм. Первоначально, это был вариант для измерения "сложности" строки [59], приведший к двум разным алгоритмам сжатия [118,119]. Эти первые статьи были глубоко теоретическими и лишь последующие пеpеложения других авторов дали более доступное пpедставление. Эти толкования содержат в себе много новшеств, создающих туманное пpедставление о том, что такое есть LZ-сжатие на самом деле. Из-за большого числа вариантов этого метода лучшее описание можно осуществить только через его растущую семью, где каждый член отражает свое решение разработчика. Эти версии отличаются друг от друга в двух главных факторах: есть ли предел обратного хода указателя, и на какие подстроки из этого множества он может ссылаться.


Содержание  Назад  Вперед