«Словарные методы кодирования. Метод Зива-Лемпела. Дифференциальное кодирование» МИНСК, 2009 Словарные методы кодирования. Метод Зива-Лемпела Практически все словарные методы кодирования пpинадлежат семье алгоритмов из работы двух израильских ученых - Зива и Лемпела, опубликованной в 1977 году. Сущность их состоит в том, что фразы в сжимаемом тексте заменяются указателем на то место, где они в этом тексте уже pанее появлялись.Это семейство алгоритмов называется методом Зива-Лемпела и обозначается как LZ-сжатие.
Этот метод быстpо пpиспосабливается к стpуктуpе текста и может кодировать короткие функциональные слова, так как они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов. Декодирование сжатого текста осуществляется напрямую - происходит простая замена указателя готовой фразой из словаря, на которую тот указывает.На практике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа декодера. (Когда мы говорим о тексте, то предполагаем, что кодированию подвергается некоторый вектор данных с конечным дискретным алфавитом, и это не обязательно текст в буквальном смысле этого слова.) Большинство словарных методов кодирования носят имя авторов идеи метода Зива и Лемпела, и часто считают, что все они используют один и тот же алгоритм кодирования.
На самом деле разные представители этого семейства алгоритмов очень сильно различаются в деталях своей работы.Все словарные методы кодирования можно разбить на две группы.
Методы, принадлежащие к первой группе, находя в кодируемой последовательности цепочки символов, которые ранее уже встречались, вместо того, чтобы повторять эти цепочки, заменяют их указателями на предыдущие повторения. Словарь в этой группе алгоритмов в неявном виде содержится в обрабатываемых данных, сохраняются лишь указатели на встречающиеся цепочки повторяющихся символов.Все методы этой группы базируются на алгоритме, разработанном и опубликованном, как уже отмечалось, сравнительно недавно - в 1977 году Абрахамом Лемпелем и Якобом Зивом LZ77. Наиболее совершенным представителем этой группы, включившим в себя все достижения, полученные в данном направлении, является алгоритм LZSS, опубликованный в 1982 году Сторером и Шимански.
Процедура кодирования в соответствии с алгоритмами этой группы иллюстрируется рис. 1.