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 шагов. В любом случае максимальное число шагов потребуется для того, чтобы достичь узлы, удаленные от корня на полную высоту дерева. Для косого дерева (которое, на самом деле, эквивалентно присоединенному списку), высота дерева это число его элементов
Единственное место, где успех приходит до работы - это в словаре - Видал Сассон Пример: Покажем, как двоичное дерево способно ускорить поиск в словаре. Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals». Для простоты предположим, что окно состоит из 16-байтного буфера поиска и 5-байтного упреждающего буфера. После ввода первых
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе. Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл. 2.3) (их двенадцать, так как Первым символом в упреждающем буфере является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение. (Здесь необходимо отвлечься и обсудить случай, когда строка на дереве полностью совпадает с содержимым упреждающего буфера. Тогда кодер мог бы искать дальнейшие совпадения. В принципе, длина совпадения может быть В нашем примере длина совпадения равна 2, поэтому кодер выдает метку (16,2). Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi. Если бы случилось совпадение длины Немного подумав, становится ясно, что удаляться будут первые
Табл. 2.3. Строки по пять символов. На дереве все время находится одинаковое число Третье улучшение метода LZ77 в алгоритме LZSS касалось создаваемых кодером меток. Метка LZSS состоит только из смещения и длины. Если не найдено совпадений, то кодер просто подает на выход несжатый код следующего символа вместо расточительной метки из трех полей (0,0,...). Для различения меток и несжатых кодов используется флаговый бит. На практике буфер поиска может состоять из нескольких сотен байт, поэтому поле смещения, обычно, состоит из 11-13 бит. Размер упреждающего буфера выбирается с таким условием, чтобы в сумме с буфером поиска длина составляла 16 бит (2 байта). Например, если буфер поиска имеет размер 2 KB (
|