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



На сайте map.meta.ua карта киевской области. |

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


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

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

Мы отметили самые главные варианты LZ-метода, которые ниже будут pассмотpены более подробно. Таблица 2 содержит сведения об основных отличиях в разных реализациях этого метода. Все они произошли от одного из двух разных подходов.

Таблица 2. Основные варианты LZ-схемы.

ИмяАвторыОтличия
LZ77Ziv and Lempel[1977]Указатели и символы чередуются. Указатели адресуют подстроку среди предыдущих N символов.
LZRRoden et al.            [1981]Указатели и символы чередуются. Указатели адресуют подстроку среди всех предыдущих символов.
LZSSBell                         [1986]Указатели и символы различаются флажком-битом. Указатели адресуют подстроку среди предыдущих N символов.
LZBBell                         [1987]Аналогично LZSS, но для указателей применяется разное кодирование.
LZHBrent                       [1987]Аналогично LZSS, но на втоpом шаге для указателей пpименяется кодиpование Хаффмана.
LZ78Ziv and Lempel        [1978]Указатели и символы чередуются. Указатели адресуют ранее разобранную подстроку.
LZWWelch                      [1984]Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку. Указатели имеют фиксированную длину.
LZCThomas et al.           [1985]Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку.
LZTTischer                    [1987]Аналогично LZC, но фразы помещаются в LRU-список.
LZMWMiller and Wegman [1984]Аналогично LZT, но фразы строятся конкатенацией двух предыдущих фраз.
LZJJakobsson               [1985]Вывод содержит только указатели. Указатели адресуют подстроку среди всех предыдущих символов.
LZFGFiala and Greene     [1989]Указатель выбирает узел в дереве цифрового поиска. Строки в дереве берутся из скользящего окна.

описанных Зивом и Лемпелом [118,119], и помеченных соответственно как LZ77 и LZ78. Эти два подхода совсем различны, хотя некоторые авторы закрепляют путаницу утверждениями об их идентичности. Теpмин "LZ-схемы" происходят от имен их изобретателей. Обычно каждый следующий рассматриваемый вариант есть улучшение более раннего, и в последующих описаниях мы отметим их предшественников. Более подробное изучение этого типа кодирования можно найти в [96].




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