2.2. LZSS

Эта версия LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982 [Storer 82]. Базовый алгоритм был улучшен по трем направлениям: (1) упреждающий буфер сохранялся в циклической очереди, (2) буфер поиска (словарь) хранился в виде дерева двоичного поиска и (3) метки имели два поля, а не три.

Двоичное дерево поиска - это двоичное дерево, в котором левое поддерево каждого узла А содержит узлы, меньшие чем A, а узлы правого поддерева все больше А. Поскольку узлы нашего двоичного дерева состоят из строк (или слов), прежде всего необходимо определиться, как эти строки следует сравнивать, что значит, одна строка «больше» другой. Это легко понять, представив себе строки в словаре, где они упорядочены по алфавиту. Ясно, что строка rote предшествует строке said, так как буква r стоит раньше буквы s (хотя о и следует после а). Мы будем считать, что строка rote меньше строки said. Такое упорядочение строк называется лексикографическим.

А как быть со строкой «_аbс»? Фактически все современные компьютеры используют код ASCII для представления символов (хотя все большее распространение получают коды Unicode, о которых говорится на стр. 90, а некоторые старые большие компьютеры IBM, Amdahl, Fujitsu, Siemens работают со старыми 8-битными кодами EBCDIC, разработанными в IBM). В кодах ASCII символ пробела предшествует символам букв, поэтому строка, начинающаяся с пробела будет считаться меньше любой строки, в начале которой стоит буква. В общем случае сортировку последовательностей в компьютере определяет последовательность символов, упорядоченных от меньшего к большему. На рис. 2.2 показаны два примера двоичных деревьев поиска.

Рис. 2.2. Двоичные деревья поиска.

Обратите внимание на различие между (почти) сбалансированным деревом (а) и косым деревом (b). Эти деревья состоят из одного числа 14 узлов, но они устроены и ведут себя совершенно по-разному. В сбалансированном дереве любой узел можно достичь не более, чем в 4 шага, а в косом дереве для этого может потребоваться до 14 шагов. В любом случае максимальное число шагов потребуется для того, чтобы достичь узлы, удаленные от корня на полную высоту дерева. Для косого дерева (которое, на самом деле, эквивалентно присоединенному списку), высота дерева это число его элементов , а для сбалансированного дерева его высота равна , что существенно меньше. Более подробные сведения о двоичных деревьях поиска можно найти в любом учебнике по структурам данных.

 

Unicode            Новый международный стандартный коде Unicode был разработан и предложен для употребления международной организацией Unicode (www.unicode.org). В этом коде используются 16-битные последовательности для кодирования символов, что дает  различных символов. Unicode содержит все ASCII коды плюс коды для букв иностранных языков (включая такие сложные алфавиты, как корейский, китайский и японский), а кроме того многие математические символы и другие знаки. К настоящему времени около 39000 из 65536 кодов получили назначение, но еще остается много места для добавления новых символов в будущем. Операционная система Microsoft Windows NT поддерживает коды Unicode.

Единственное место, где успех приходит

 до работы - это в словаре

- Видал Сассон

Пример: Покажем, как двоичное дерево способно ускорить поиск в словаре. Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals». Для простоты предположим, что окно состоит из 16-байтного буфера поиска и 5-байтного упреждающего буфера. После ввода первых  символов скользящее окно выглядит так:

sid_eastman_clum

sily_

teases_sea_sick_seals

причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.

Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл. 2.3) (их двенадцать, так как ), которые помещены на двоичное дерево поиска вместе с их смещениями.

Первым символом в упреждающем буфере является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.

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

В нашем примере длина совпадения равна 2, поэтому кодер выдает метку (16,2). Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:

si

d_eastman_clumsi

ly_te

ases_sea_sick_seals

С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi. Если бы случилось совпадение длины , то дерево надо было бы перестроить путем удаления  строк и добавления  строк, но вот каких?

Немного подумав, становится ясно, что удаляться будут первые  строк буфера поиска до его сдвига, а добавляться будут последние  строк этого буфера после сдвига. Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних 5 символов буфера поиска и добавить ее на дерево. Это следует повторить  раз. (Конец примера.)

sid_e	16
id_ea	15
d_eas	14
_east	13
eastm	12
astma	11
stmаn	10
tman_	09
man_c	08
an_cl	07
n_clu	06
_clum	05

Табл. 2.3. Строки по пять символов.

На дереве все время находится одинаковое число узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк. Число  равно: длина буфера поиска минус длина упреждающего буфера плюс 1 . Однако, форма дерева может существенно измениться. Поскольку узлы удаляются и добавляются, то форма дерева может меняться от абсолютно косой (худший случай для поиска) до сбалансированной, идеальной формы.

Третье улучшение метода LZ77 в алгоритме LZSS касалось создаваемых кодером меток. Метка LZSS состоит только из смещения и длины. Если не найдено совпадений, то кодер просто подает на выход несжатый код следующего символа вместо расточительной метки из трех полей (0,0,...). Для различения меток и несжатых кодов используется флаговый бит.

На практике буфер поиска может состоять из нескольких сотен байт, поэтому поле смещения, обычно, состоит из 11-13 бит. Размер упреждающего буфера выбирается с таким условием, чтобы в сумме с буфером поиска длина составляла 16 бит (2 байта). Например, если буфер поиска имеет размер 2 KB (), то упреждающий буфер состоит из 32 байт (). Длина поля смещения равна 11, а поле «длина» имеет 5 разрядов. При таком выборе размеров буферов кодер будет выдавать или 2-х байтовую метку или 1-байтовый несжатый код ASCII. А как насчет флага? Хороший практический совет состоит в накоплении восьми последовательных выходов (меток или ASCII кодов) в маленьком буфере, затем выдавать один байт из 8 флагов, за которым следуют восемь накопленных элементов по 2 или 1 байту.