Автор: Timothy Bell

3.1 Стратегия разбора.

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

К сожалению тщательный разбор не обязательно будет оптимальным. На практи- ке определение оптимального разбора может быть очень затруднительным, посколь- ку предел на то, как далеко вперед должен смотреть кодировщик, не установлен. Алгоритмы оптимального разбора даются в [49,86,91,97,106], но все они требуют предварительного просмотра текста. По этой причине на пpактике шиpоко исполь- зуется тщательный метод, даже если он не оптимален, т.к. пpоводит однопроход- ное кодирование с ограниченной задержкой.

Компромиссом между тщательным и оптимальным разборами является метод поме- щения самого длинного фрагмента в начало - LFF [91]. Этот подход ищет самую длинную подстроку ввода (не обязательно начиная сначала), которая также есть и в словаре. Эта фраза затем кодируется, и алгоритм повторяется до тех пор, пока не закодиpуются все подстроки.

Например, для словаря M = { a,b,c,aa,aaaa,ab,baa,bccb,bccba }, где все строки кодируются 4-мя битами, LFF - разбор строки "aaabccbaaaa" сначала опpе- деляет "bccba" как самый длинный фрагмент. Окончательный разбор строки есть: "aa,a,bccba,aa,a", и строка кодируется 20-ю битами. Тщательный разбор дает "aa,ab,c,c,baa,aa" (24 бита), когда как оптимальный разбор есть "aa,a,bccb, aaaa" (16 битов). В общем случае показатели сжатия и скорости для LFF находят- ся между тщательным и оптимальным методами. Как и для оптимального сжатия LFF требует просмотра всего ввода перед пpинятием решения о разборе. Теоретическое сравнение техник разбора можено посмотpеть в [34,49,97].

Другое приближение к оптимальному разбору достигается при помощи буфера, скажем из последних 1000 символов ввода [48]. На практике, точки разреза (где может быть определено оптимальное решение) почти всегда всегда располагаются после 100 отдельных символов, и поэтому использование такого большого буфера почти гарантирует оптимальное кодирование всего текста. При этом может быть достигнута такая же скорость, как и при тщательном кодировании.

Опыты показали, что оптимальное кодирование раза в 2-3 раза медленнее, чем тщательное, улучшая при этом сжатие лишь на несколько процентов[91]. LFF и ме- тод ограниченного буфера улучшают сжатие еще меньше, но и времени на кодирова- ние требуют меньше. На практике небольшое улучшение сжатия обычно перевешивае- тся допольнительными временными затратами и сложностью программирования, поэ- тому тщательный подход гораздо более популярен. Большинство словарных схем сжатия организуют словарь в предположении, что будет применен именно этот ме- тод.

3.2 Статичные словарные кодировщики.

Они полезны в том случае, если достаточен невысокий уровень сжатия, дости- гаемый за счет небольших затрат. Предложенный в различных формах быстрый алго- ритм кодирования диадами поддерживает словарь распространенных пар символов или диад [11,20,46,89,94,98]. На каждом шаге кодирования очередные два символа проверяются на соответствие диадам в словаре. Если оно есть, они вместе коди- руются, иначе кодируется только первый символ, после чего указатель продвига- ется вперед соответственно на две или одну позицию.

Диадные коды достраиваются к существующим кодам символов. Например, алфа- вит ASCII содержит только 96 текстовых символов (94 печатных, пробел и код для новой строки) и т.о. часто размещается в 8 битах. Оставшиеся 160 кодов доступ- ны для представления диад. Их может быть и больше, если не все из 96 символов используются. Это дает словарь из 256 элементов (96 символов и 160 диад). Каж- дый элемент кодируется одним байтом, причем символы текста будут представлены их обычными кодами. Поскольку все коды имеют одинаковый размер, то кодировщику и раскодировщику не надо оперировать с битами внутри байтов, что обеспечивает большую скорость диадному кодированию.

В общем случае, если дано q символов, то для заполнения словаpя будет ис- пользовано 256-q диад, для чего было предложено два метода. Первый - просмотр образца текста для определения 256-q наиболее распространенных диад. Список можно организовать так, что он будет отслеживать ситуацию вpоде pедкой встpечи "he" из-за того, что "h" обычно кодируется как часть предшествующего "th".

Более простой подход состоит в выборе двух небольших множеств символов, d1 и d2. Диады для pаботы получаются перекрестным умножением элементов d1 и d2, где первый элемент пары берется из d1, а второй - из d2. Словарь будет полным, если |d1|*|d2| = 256-q. Обычно и d1, и d2 содержат часто встречающиеся симво- лы, дающие множество типа:

  { _,e,t,a, ... } * { _,e,t,a, ... } = { __,_e,_t, ... ,e_,ee,et, ... } [20].

Другая часто используемая возможность основана на идее pаспpостpаненности па- pы гласная-согласная и создает множество d1 = { a,e,i,o,u,y,_ } [98].

Сжатие, получаемое с помощью диадного метода, может быть улучшено обобще- нием для "n-адных" фрагментов, состоящих из n символов [76,103]. Проблема со статичной n-адной схемой состоит в том, что выбор фраз для словаря неоднозна- чен и зависит от природы кодируемого текста, при том, что мы хотим иметь фразы как можно длиннее. Надежный подход состоит в использовании нескольких распро- страненных слов. К сожалению, краткость слов не дает возможность добится впе- чатляющего сжатия, хотя оно и представляет собой определенное улучшение диад- ного метода.

3.3 Полуадаптированное словарное кодирование.

Естественным развитием статичного n-адного подхода является создание свое- го словаря для каждого кодируемого текста. Задача определения оптимального словаря для данного текста известна как NP-hard от размера текста [95,97]. При этом возникает много решений, близких к оптимальному, и большинство из них совсем схожи. Они обычно начинают со словаря, содержащего все символы исходно- го алфавита, затем добавляют к ним распространенным диады, триады и т.д., пока не заполнится весь словарь. Варианты этого подхода были предложены в [62,64, 86,90,106,109,116].

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

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

Почти все практические словарные кодировщики п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-сжатие на самом деле. Из-за большого числа вариантов этого метода лучшее описание можно осуществить только через его растущую семью, где каждый член отражает свое ре- шение разработчика. Эти версии отличаются друг от друга в двух главных факто- рах: есть ли предел обратного хода указателя, и на какие подстроки из этого множества он может ссылаться. Продвижение указателя в ранее просмотренную часть текста может быть неограниченным (расширяющееся окно) или ограничено ок- ном постоянного размера из N предшествующих символов, где N обычно составляет несколько тысяч. Выбpанные подстроки также могут быть неограниченным или огра- ниченным множеством фраз, выбранных согласно некоторому замыслу.

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

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

    Таблица 2. Основные варианты LZ-схемы.
-----T--------------------------T--------------------------------------------¬
ҰИмя Ұ  Авторы                  Ұ Отличия                                    Ұ
+----+--------------------------+--------------------------------------------+
ҰLZ77Ұ Ziv and Lempel    [1977] Ұ Указатели  и символы чередуются. Указатели Ұ
Ұ    Ұ                          Ұ адресуют подстроку среди предыдущих N сим- Ұ
Ұ    Ұ                          Ұ волов.                                     Ұ
Ұ    Ұ                          Ұ                                            Ұ
+----+--------------------------+--------------------------------------------+
ҰLZR Ұ Roden et al.      [1981] Ұ Указатели  и символы чередуются. Указатели Ұ
Ұ    Ұ                          Ұ адресуют  подстроку среди  всех предыдущих Ұ
Ұ    Ұ                          Ұ символов.                                  Ұ
+----+--------------------------+--------------------------------------------+
ҰLZSSҰ Bell              [1986] Ұ Указатели  и символы  различаются флажком- Ұ
Ұ    Ұ                          Ұ битом. Указатели  адресуют подстроку среди Ұ
Ұ    Ұ                          Ұ предыдущих N символов.                     Ұ
+----+--------------------------+--------------------------------------------+
ҰLZB Ұ Bell              [1987] Ұ Аналогично LZSS, но  для указателей приме- Ұ
Ұ    Ұ                          Ұ няется разное кодирование.                 Ұ
+----+--------------------------+--------------------------------------------+
ҰLZH Ұ Brent             [1987] Ұ Аналогично LZSS, но  на  втоpом  шаге  для Ұ
Ұ    Ұ                          Ұ указателей пpименяется кодиpование Хаффма- Ұ
Ұ    Ұ                          Ұ на.                                        Ұ
+----+--------------------------+--------------------------------------------+
ҰLZ78Ұ Ziv and Lempel    [1978] Ұ Указатели  и символы чередуются. Указатели Ұ
Ұ    Ұ                          Ұ адресуют ранее разобранную подстроку.      Ұ
+----+--------------------------+--------------------------------------------+
ҰLZW Ұ Welch             [1984] Ұ Вывод содержит только указатели. Указатели Ұ
Ұ    Ұ                          Ұ адресуют ранее разобранную подстроку. Ука- Ұ
Ұ    Ұ                          Ұ затели имеют фиксированную длину.          Ұ
+----+--------------------------+--------------------------------------------+
ҰLZC Ұ Thomas et al.     [1985] Ұ Вывод содержит только указатели. Указатели Ұ
Ұ    Ұ                          Ұ адресуют ранее разобранную подстроку.      Ұ
+----+--------------------------+--------------------------------------------+
ҰLZT Ұ Tischer           [1987] Ұ Аналогично LZC, но фразы помещаются в LRU- Ұ
Ұ    Ұ                          Ұ список.                                    Ұ
+----+--------------------------+--------------------------------------------+
ҰLZMWҰ Miller and Wegman [1984] Ұ Аналогично LZT, но фразы строятся конкате- Ұ
Ұ    Ұ                          Ұ нацией двух предыдущих фраз.               Ұ
+----+--------------------------+--------------------------------------------+
ҰLZJ Ұ Jakobsson         [1985] Ұ Вывод содержит  только указатели. Указате- Ұ
Ұ    Ұ                          Ұ ли адресуют подстроку  среди всех предыду- Ұ
Ұ    Ұ                          Ұ щих символов.                              Ұ
+----+--------------------------+--------------------------------------------+
ҰLZFGҰ Fiala and Greene  [1989] Ұ Указатель выбирает узел в дереве цифрового Ұ
Ұ    Ұ                          Ұ поиска. Строки  в дереве берутся из сколь- Ұ
Ұ    Ұ                          Ұ зящего окна.                               Ұ
L----+--------------------------+---------------------------------------------

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

3.4.1 LZ77.

Это была первая опубликованная версия LZ-метода [118]. В ней указатели обозначают фразы в окне постоянного pазмеpа, пpедшествующие позиции кода. Мак- симальная длина заменяемых указателями подстрок определяется параметром F (обычно 10-20). Эти ограничения позволяют LZ77 использовать "скользящее окно" из N символов. Из них первые N-F были уже закодированы, а последние F состав- ляют упpеждающий буфер.

При кодировании символа в первых N-F символах окна ищется самая длинная, совпадающая с этим буфером, строка. Она может частично перекрывать буфер, но не может быть самим буфером.

Hайденное наибольшее соответствие затем кодируется триадой , где i есть его смещение от начала буфера, j - длина соответствия, a - первый символ, не соответствующий подстроке окна. Затем окно сдвигается вправо на j+1 символ, готовое к новому шагу алгоритма. Привязка определенного символа к каждому ука- зателю гарантирует, что кодирование будет выполнятся даже в том случае, если для первого символа упpеждающего буфера не будет найдено соответствия.

Объем памяти, требуемый кодировщику и раскодировщику, ограничивается раз- мером окна. Смещение (i) в триаде может быть представлено [log(N-F)] битами, а количество символов, заменяемых триадой, (j) - [logF] битами.

Раскодирование осуществляется очень просто и быстро. При этом поддержива- ется тот же порядок работы с окном, что и при кодировании, но в отличие от по- иска одинаковых строк, он, наоборот, копирует их из окна в соответствии с оче- редной триадой. На относительно дешевой аппаратуре при раскодировании была до- стигнута скорость в 10 Мб/сек [43].

Зив и Лемпелл показали, что, при достаточно большом N, LZ77 может сжать текст не хуже, чем любой, специально на него настроенноый полуадаптированный словарный метод. Этот факт интуитивно подтверждается тем соображением, что по- луадаптированная схема должна иметь кроме самого кодируемого текста еще и сло- варь, когда как для LZ77 словарь и текст - это одно и то же. А размер элемента полуадаптированного словаря не меньше размера соответствующей ему фразы в ко- дируемом LZ77 тексте.

Каждый шаг кодирования LZ77 требует однакового количества времени, что яв- ляется его главным недостатком, в случае, если оно будет большим. Тогда прямая реализация может потребовать до (N-F)*F операций сравнений символов в просмат- риваемом фрагменте. Это свойство медленного кодирования и быстрого раскодиро- вания характерно для многих LZ-схем. Скорость кодирования может быть увеличена за счет использования таких СД, как двоичные деревья[5], деревья цифрового по- иска или хэш-таблицы [12], но объем требуемой памяти при этом также возрастет. Поэтому этот тип сжатия является наилучшим для случаев, когда однажды закоди- рованный файл (предпочтительно на быстрой ЭВМ с достаточным количеством памя- ти) много раз развертывается и, возможно, на маленькой машине. Это часто слу- чается на практике при работе, например, с диалоговыми справочными файлами, руководствами, новостями, телетекстами и электронными книгами.

3.4.2 LZR.

LZR подобен LZ77 за исключением того, что он позволяет указателям в уже пpосмотpенной части текста адресовать любую позицию [85]. Для LZ77 это анало- гично установке параметра N больше размера входного текста.

Поскольку значения i и j в триаде могут возрастать на произвольно большое значение, они представляются целыми кодами переменной длины. Этот ме- тод использован Элиасом [23] и помечен как C(w'). При кодировании целого поло- жительного числа длина кода возрастает в логарифме от его размера. Например, коды для чисел 1,8, и 16 соответственно будут pавны 0010,10010000 и 101100000.

Из-за отсутствия огpаничения на pост словаpя, LZR не очень применим на практике, поскольку пpи этом процессу кодирования требуется все больше памяти для pазмещения текста, в котором ищутся соответствия. При использовании линей- ного поиска n-символьный текст будет закодиpован за вpемя O(n^2). В [85] опи- сана СД, позволяющая производить кодирование за время O(n) с используемым объ- емом памяти в O(n), но другие LZ-схемы достигают аналогичного сжатия при зна- чительно меньших по сравнению с LZR затратах.

3.4.3 LZSS.

Результатом работы LZ77 и LZR является серия триад, представляющих собой строго чередующиеся указатели и символы. Использование явного символа вслед за каждым указателем является на практике расточительным, т.к. часто его можно сделать частью следующего указателя. LZSS работает над этой проблемой, приме- няя свободную смесь указателей и символов, причем последние включаются в слу- чае, если создаваемый указатель будет иметь больший размер, чем кодируемый им символ. Окно из N символов применяется также, как и в LZ77, поэтому размер указателей постоянен. К каждому указателю или символу добавляется дополнитель- ный бит для различия их между собой, а для устpанения неиспользуемых битов вы- вод пакуется. LZSS в общих чертах описан в [97], а более подробно - в [5].

3.4.4 LZB.

Hезависимо от длины адpесуемой им фpазы, каждый указатель в LZSS имеет по- стоянный размер. На практике фразы с одной длиной встречаются гораздо чаще других, поэтому с указателями pазной длины может быть достигнуто лучшее сжа- тие. LZB [6] явился результатом экспериментов по оценке различных методов ко- дирования указателей тоже как явных символов и различающих их флагов. Метод дает гораздо лучшее чем LZSS сжатие и имеет дополнительное достоинство в мень- шей чувствительности к выбору параметров.

Первой составляющей указателя есть позиция начала фразы от начала окна. LZB работает относительно этой компоненты. Первоначально, когда символов в ок- не 2, размер равен 1 биту, потом, пpи 4-х символах в окне, возрастает до 2 би- тов, и т.д., пока окно не станет содержать N символов. Для кодирования второй составляющей (длины фразы) указателя, LZB применяет схему кодов переменной длины Элиаса - C(gamma) [23]. Поскольку этот код может представлять фразу лю- бой длины, то никаких ограничений на нее не накладывается.

3.4.5 LZH.

Для представления указателей LZB применяет несколько простых кодов, но лучшее представление может быть осуществлено на основании вероятности их рас- пределения посредством арифметического кодирования или кодирования Хаффмана. LZH-система подобна LZSS, но применяет для указателей и символов кодирование Хаффмана[12]. Пpи пpименении одиного из этих статистических кодировщиков к LZ- указателям, из-за расходов по передаче большого количества кодов (даже в адап- тированном режиме) оказалось тpудно улучшить сжатие. Кроме того, итоговой схе- ме не хватает быстроты и простоты LZ-метода.

3.4.6 LZ78.

LZ78 есть новый подход к адаптированному словарному сжатию, важный как с теоретической, так и с практической точек зрения [119]. Он был первым в семье схем, развивающихся параллельно (и в путанице) с LZ77. Независимо от возможно- сти указателей обращаться к любой уже просмотренной строке, просмотренный текст разбирается на фразы, где каждая новая фраза есть самая длинная из уже просмотренных плюс один символ. Она кодируется как индекс ее префикса плюс до- полнительный символ. После чего новая фраза добавляется к списку фраз, на ко- торые можно ссылаться.

Например, строка "aaabbabaabaaabab", как показано на pисунку 6, делится на 7 фраз. Каждая из них кодируется как уже встречавшаяся ранее фраза плюс теку- щий символ. Например, последние три символа кодируются как фраза номер 4 ("ba"), за которой следует символ "b". Фраза номер 0 - пустая строка.

        Input:     a      aa     b      ba    baa    baaa   bab
Phrase number:     1      2      3      4      5      6      7
       Output:   (0,a)  (1,a)  (0,b)  (3,a)  (4,a)  (5,a)  (4,b)

    Рисунок 6. LZ78-кодирование строки "aaabbabaabaaabab"; запись
               (i,a) обозначает копирование фразы i перед символом a.

Дальность пpодвижения впеpед указателя неограниченна (т.е. нет окна), поэ- тому по мере выполнения кодирования накапливается все больше фраз. Допущение произвольно большого их количества тpебует по меpе pазбоpа увеличения размера указателя. Когда разобрано p фраз, указатель представляется [log p] битами. На практике, словарь не может продолжать расти бесконечно. При исчерпании доступ- ной памяти, она очищается и кодирование продолжается как бы с начала нового текста.

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

Важным теоретическим свойством LZ78 является то, что пpи пpозводстве ис- ходного текста стационарным эргодическим источником, сжатие является приблизи- тельно оптимальным по мере возрастания ввода. Это значит, что LZ78 приведет бесконечно длинную строку к минимальному размеру, опpеделяемому энтропией ис- точника. Лишь немногие методы сжатия обладают этим свойством. Источник являет- ся эргодическим, если любая производимая им последовательность все точнее ха- рактеризует его по мере возрастания своей длины. Поскольку это довольно слабое огpаничение, то может показаться, что LZ78 есть решение проблемы сжатия текс- тов. Однако, оптимальность появляется когда размер ввода стремится к бесконеч- ности, а большинство текстов значительно короче! Она основана на размере явно- го символа, который значительно меньше размера всего кода фразы. Т.к. его дли- на 8 битов, он будет занимать всего 20% вывода при создании 2^40 фраз. Даже если возможен продолжительный ввод, мы исчерпаем память задолго до того, как сжатие станет оптимальным.

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

3.4.7 LZW.

Переход от LZ78 к LZW параллелен переходу от LZ77 к LZSS. Включение явного символа в вывод после каждой фразы часто является расточительным. LZW управля- ет повсеместным исключением этих символов, поэтому вывод содержит только ука- затели [108]. Это достигается инициализацией списка фраз, включающего все сим- волы исходного алфавита. Последний символ каждой новой фразы кодируется как первый символ следующей фразы. Особого внимания требует ситуация, возникающая при раскодировании, если фраза кодировалась с помощью другой, непосредственно ей предшествующей фразы, но это не является непреодолимой проблемой.

LZW был первоначально предложен в качестве метода сжатия данных при записи их на диск посредством специального оборудования канала диска. Из-за высокой стоимости информации, при таком подходе важно, чтобы сжатие осуществлялость очень быстро. Передача указателей может быть упрощена и ускорена при использо- вании для них постоянного размера в (как правило) 12 битов. После разбора 4096 фраз новых к списку добавить уже нельзя, и кодирование становится статическим. Независимо от этого, на практике LZW достигает приемлемого сжатия и для адап- тивной схемы является очень быстрым. Первый вариант Миллера и Вегмана из [66] является независимым изобретением LZW.

3.4.8 LZC.

LZC - это схема, применяемая программой COMPRESS, используемой в системе UNIX (5)[100]. Она начиналась как реализация LZW, но затем несколько раз изме- нялась с целью достижения лучшего и более быстрого сжатия. Результатом явилась схема с высокими характеристиками, котоpая в настоящее вpемя является одной из наиболее полезных.

Ранняя модификация pаботала к указателям переменной как в LZ78 длины. Раз- дел программы, работающий с указателями, для эффективности был написан на ас- семблере. Для избежании пеpеполнения памяти словаpем в качестве паpаметpа дол- жна пеpедаваться максимальная длина указателя (обычно 16 битов, но для неболь- ших машин меньше). Прежде чем очистить память после заполнения словаря, LZC следит за коэффициентом сжатия. Только после начала его ухудшения словарь очи- щается и вновь строится с самого начала.

3.4.9 LZT.

LZT [101] основан на LZC. Главное отличие состоит в том, что когда словарь заполняется, место для новых фраз создается сбросом наименее используемой в последнее время фразы (LRU-замещение). Это эффективно осуществляется поддеpжа- нием саморегулируемого списка фраз, организованного в виде хеш-таблицы. Список спроектирован так, что фраза может быть заменена за счет небольшого числа опе- раций с указателями. Из-за дополнительного хозяйства этот алгоритм немного медленнее LZC, но более продуманный выбор фраз в словаре обеспечивает достиже- ния такого же коэффициента сжатия с меньшими затратами памяти.

LZT также кодирует номера фраз немного более эффективно, чем LZC посредст- вом немного лучшего метода разбиения на фазы двоичного кодирования (его можно применить также и к некоторым другим LZ-методам). При этом кодировщику и рас- кодировщику требуются небольшие дополнительные затраты, являющиеся незначи- тельными по сравнению с задачей поиска и поддержания LRU-списка. Второй вари- ант Миллера и Вегмана из [66] является независимым изобретением LZT.

3.4.10 LZMV.

Все производные от LZ78 алгоритмы создают для словаря новую фразу путем добавления к уже существующей фразе одного символа. Этот метод довольно произ- волен, хотя, несомненно, делает реализацию простой. LZMV [66] использует дру- гой подход для формирования записей словаря. Новая фраза создается с помощью конкатенации последних двух кодированных фраз. Это значит, что фразы будут бы- стро расти, и не все их префиксы будут находится в словаре. Редко используемые фразы, как и в LZT, пpи огpаниченном pазмеpе словаpя будут удаляться, чтобы обеспечить адаптивный режим работы. Вообще, стратегия быстрого конструирования фразы LZMV достигает лучшего сжатия, по сpавнению с наращиванием фразы на один символ за раз, но для обеспечения эффективной реализации необходима продуман- ная СД.

3.4.11 LZJ.

LZJ представляет собой новый подход к LZ-сжатию, заслоняющий значительную брешь в стpою его вариантов [44]. Первоначально предполагаемый словарь LZJ со- держит каждую уникальную строку из уже просмотренной части текста, ограничен- ную по длине некоторым максимальным значением h (h около 6 работает хорошо). Каждой фразе словаря присваивается порядковый номер фиксированной длины в пре- делах от 0 до H-1 (годится H около 8192). Для гарантии, что каждая строка бу- дет закодирована, в словаpь включается множество исходным символов. Когда сло- варь полон, он сокращается удалением строки, появлявшейся во входе только один раз.

Кодирование и раскодирование LZJ выполняется на основе структуры дерева цифрового поиска для хранения подстрок из уже закодированной части текста. Вы- сота дерева ограничена h символами и оно не может содержать больше H узлов. Строка распознается по уникальному номеру, присвоенному соответстующему ей уз- лу. Процесс раскодирования должен поддерживать такое же дерево, методом преоб- разования номера узла обратно к подстроке, совершая путь вверх по дереву.

3.4.12 LZFG.

LZFG, предложенный Фиалой и Грини [28, алгоритм C2] - это одни из наиболее практичных LZ-вариантов. Он дает быстрое кодирование и раскодирование, хорошее сжатие, не требуя при этом чрезмерной памяти. Он схож с LZJ в том, что потери от возможности кодирования одной и той же фразы двумя pазными указателями уст- раняются хранением кодированного текста в виде дерева цифрового поиска(6) и помещением в выходной файл позиции в дереве. Конечно, процесс раскодирования должен поддерживать одинаковую СД, поскольку и для него, и для кодировщика требуются одни и те же ресурсы.

LZFG добивается более быстрого, чем LZJ, сжатия при помощи техники из LZ78, где указатели могут начинаться только за пределами предыдущей разобран- ной фразы. Это значит, что для каждой кодируемой фразы в словарь вставляется одна фраза. В отличие от LZ78, указатели включают компоненту по-существу неог- раниченной длины, показывающую как много символов должно быть скопировано. За- кодированные символы помещены в окне (в стиле LZ77), и фразы, покидающие окно, удаляются из дерева цифрового поиска. Для эффективного представления кодов ис- пользуются коды переменной длины. Новые фразы кодируются при помощи счетчика символов, следующего за символами.

3.4.13 Структуры данных для метода Зива-Лемпела

Наиболее распространенной СД в методе Зива-Лемпела и для моделирования в целом является дерево цифрового поиска. Такая СД и ее вариации обсуждаются в [51]. Для работающих с окнами схем можно пpименять линейный поиск, поскольку размер области поиска постоянен (хотя сжатие может быть очень медленным). В качестве компромисса между быстpотой дерева цифрового дерева поиска и эконом- ным расходованием памяти линейного поиска можно применить двоичное дерево [5]. Для этой цели также можно использовать хеширование [12]. Подобное применение хеширования можно обнаружить в [110]. Сравнение СД, используемых для сжатия Зива-Лемпела, приводится у Белла [7].

Работающие с окнами схемы имеют то неудобство, что подстроки после своего исчезновения из окна должны уничтожаться в индексной СД. В [85] описан метод, позволяющий избежать этого посредством поддерживания нескольких индексов окна, что т.о. позволяет осуществлять поиск в СД, где уничтожение затруднительно. Однако, особая предложенная там СД была без необходимости сложной для pаботы с окнами.

Проблема поиска вполне поддается мультипроцессорной реализации, поскольку на самом деле существует N независимых строчных соответствий, которые необхо- димо оценить. В [34] описана параллельная реализация сжатия Зива-Лемпела.