Lzss как понять

LZSS — название словарного метода сжатия данных без потерь . LZSS — это улучшенный вариант метода LZ77 .

Название метода происходит от названий: Lempel-Ziv-Storer-Szymanski, был разработан Джеймсом А. Сторером и Томасом Г. Шимански и описан в 1982 году в журнале ACM в статье, озаглавленной Сжатие данных с помощью текстовой замены (стр. 928–951).

Алгоритм LZSS используется, в частности, в программах PKZIP и ARJ .

Метод LZSS, как и LZ77, использует буфер , разделенный на две части:

Алгоритм LZ77 записывает на выход трех ( П. , С. , С. ) , <\ displaystyle (P, C, S),>даже если тройка длиннее, чем строка, которую она описывает. Алгоритм LZSS выводит на выход только пары. ( П. , С. ) , <\ displaystyle (P, C),>но также принимает во внимание, не занимает ли пара битов больше, чем последовательность символов, которую она описывает. Если закодированная строка длиннее пары, то имеет смысл записать пару на вывод, в противном случае на вывод печатается только первый символ из входного буфера. С. ′ . <\ displaystyle S '.>Чтобы отличить символ от пары, им предшествует один бит :

Формально алгоритм сжатия следующий:

Заполните словарь первым символом, запишите этот символ в вывод; заполнить входной буфер п <\ displaystyle n>первые входные символы.

Пока есть данные во входном буфере:

Искать в словаре самую длинную подстроку, равную началу входного буфера — возвращаются числа П. <\ displaystyle P>а также С. . <\ displaystyle C.>
- Если размер пары ( П. , <\ displaystyle P,>С. <\ displaystyle C>) меньше размера найденной подстроки, вывести на выход тройку (1, П. , <\ displaystyle P,>С. <\ displaystyle C>), переместите весь буфер на С. <\ displaystyle C>положение влево и введите во входной буфер такое же количество последовательных символов.
- В противном случае напишите пару (0, С. ′ <\ displaystyle S '>), сдвиньте весь буфер 1 на позицию влево и вставьте еще один входной символ во входной буфер.

Пример шага алгоритма

1. Найдите самую длинную строку, равную началу входного буфера (здесь: aac).

2. Результат поиска:

3. Предполагая, что пара (P, C) занимает меньше, чем последовательность aac — сдвиньте буфер на позицию C, добавив необработанные символы во входной буфер.

4. Предполагая, что пара (P, C) занимает больше битов, чем закодированная последовательность — сдвиг буфера на 1 позицию, введение одного символа во входной буфер.

Для распаковки вам понадобится буфер точно такого же размера, как и для сжатия; он разделен на словарь ( k <\ displaystyle k>символы) и выходной буфер ( п <\ displaystyle n>символы).

Заполните словарь первым символом.

Для следующих данных (пары и тройки) повторите:

Если мы имеем дело с тремя (0, П. , <\ displaystyle P,>С. <\ displaystyle C>) затем скопируйте символы из диапазона словаря в начало буфера вывода. П. … П. + С. — 1 , <\ Displaystyle P \ ldots P + C-1,>записать скопированные символы в вывод и сдвинуть весь буфер на С. <\ displaystyle C>левое положение.
Если мы имеем дело с двумя (1, С. <\ displaystyle S>) затем скопируйте символ С. <\ displaystyle S>в начало буфера вывода, запишите этот символ в вывод и сдвиньте весь буфер на одну позицию влево.

тройной размер (0, P, C) — 1 + 2 + 2 = 5 бит;
размер пары (1, S) — 1 + 8 = 9 бит.

Строка aabbcabbcabd из 12 элементов будет сжата .

#	словарь / буфер ввода	выход энкодера	комментарий
1	аааа / аабб	словарь заполняется первым символом, а буфер ввода — первыми четырьмя входными символами
2	аа аа / аа бб	(0.0.2)	в словаре есть 2-элементная подстрока, равная началу входного буфера — ее размер составляет 16 бит, а размер тройки — 5 бит, поэтому на выходе печатается тройка, а буфер сдвигается на 2 позиции
3	aaaa / bbca	(1, `б` )	в словаре нет строки, начинающейся с `b` , поэтому печатается пара, а буфер сдвигается на одну позицию
4	ааа б / б кабина	(0.3.1)	в словаре есть 1-элементная подстрока, равная началу входного буфера — ее размер составляет 8 бит, а размер тройки — 5 бит, поэтому на выходе печатается тройка, а буфер сдвигается на 1 позиции
5	aabb / cabb	(1, `в` )	в словаре нет строки, начинающейся с `c` , поэтому печатается пара, а буфер сдвигается на одну позицию
6	abbc / abbc	(0.0.4)	в словаре есть 4-элементная подстрока, равная началу входного буфера — ее размер 32 бита, а размер триплета 5 бит, поэтому на выходе получается тройка, а буфер сдвинут на 4 позиции
7	ab bc / ab d	(0.0.2)	в словаре (в его начале) есть двухэлементная подстрока, равная началу входного буфера; печатается триплет, а буфер сдвигается на 2 позиции
8	bcab / d	(1, `г` )	в словаре нет строки, начинающейся с `d` , поэтому печатается пара, а буфер сдвигается на одну позицию

Размер данных до сжатия: 12 ⋅ 8 знак равно 96 <\ Displaystyle 12 \ cdot 8 = 96>биты.

Размер сжатых данных:

начальный символ: 8 бит.
три пары: 3 ⋅ 9 знак равно 27 <\ Displaystyle 3 \ cdot 9 = 27>биты
четыре тройки: 4 ⋅ 5 знак равно двадцать <\ Displaystyle 4 \ cdot 5 = 20>биты.

Всего 55 бит, что составляет примерно 42% степени сжатия.

Данные из предыдущего примера будут несжатыми.

#	вход декодера	выход декодера	Словарь	комментарий
1	а также	аааа	заполните словарь первым символом
2	(0.0.2)	аа	аааа	копирование двухэлементной строки в выходной буфер и в выходной; сдвиг всего буфера на 2 позиции влево
3	(1, `б` )	б	аааб	запись символа в выходной буфер, запись его в выходной и перемещение всего буфера на одну позицию влево
4	(0.3.1)	б	aabb	копирование 1-элементной строки в выходной буфер и в выходной; сдвиг всего буфера на 1 позицию влево
5	(1, `в` )	c	abbc	запись символа в выходной буфер, запись его в выходной и перемещение всего буфера на одну позицию влево
6	(0.0.4)	abbc	abbc	копирование 4-элементной строки в выходной буфер и в выходной; сдвиг всего буфера на 4 позиции влево
7	(0.0.2)	ab	bcab	как указано выше
8	(1, `г` )	d	такси	запись символа в выходной буфер, запись его в выходной и перемещение всего буфера на одну позицию влево

Как видите, вывод содержит точно такие же символы, которые были ранее сжаты.

Лемпель – Зив – Сторер – Шиманский

Lempel – Ziv – Storer – Szymanski ( LZSS ) — это алгоритм сжатия данных без потерь , производный от LZ77 , который был создан в 1982 году Джеймсом А. Сторером и Томасом Шимански . LZSS был описан в статье «Сжатие данных с помощью текстовой замены», опубликованной в Journal of the ACM (1982, стр. 928–951). [1]

LZSS — это метод словарного кодирования . Он пытается заменить строку символов ссылкой на местоположение той же строки в словаре.

Основное различие между LZ77 и LZSS состоит в том, что в LZ77 словарная ссылка на самом деле может быть длиннее, чем строка, которую она заменяет. В LZSS такие ссылки опускаются, если длина меньше точки «безубыточности». Кроме того, LZSS использует однобитовые флаги, чтобы указать, является ли следующий фрагмент данных литералом (байтом) или ссылкой на пару смещение / длина.

СОДЕРЖАНИЕ

Пример [ править ]

Вот начало книги доктора Сьюза « Зеленые яйца и ветчина» с номерами знаков в начале строк для удобства. Green Eggs and Ham — оптимальный пример для иллюстрации сжатия LZSS, потому что сама книга содержит только 50 уникальных слов, несмотря на то, что количество слов составляет 170. [2] Таким образом, слова повторяются, но не последовательно.

Этот текст занимает 177 байт в несжатом виде. Предполагая, что точка безубыточности составляет 2 байта (и, следовательно, 2 пары байтов указатель / смещение) и один байт новой строки, этот текст, сжатый с помощью LZSS, становится длиной 94 байта:

Примечание: сюда не входят 12 байтов флагов, указывающих, является ли следующий фрагмент текста указателем или литералом. При его добавлении длина текста становится 106 байт, что по-прежнему меньше исходных 177 байт.

Реализации [ править ]

Многие популярные архиваторы, такие как PKZip , ARJ , RAR , ZOO , LHarc, используют LZSS, а не LZ77 в качестве основного алгоритма сжатия; кодирование буквальных символов и пар длина-расстояние варьируется, наиболее распространенным вариантом является кодирование Хаффмана . Большинство реализаций основано на общедоступном коде 1989 года Харухико Окумуры . [3] [4] Версия 4 библиотеки Allegro может кодировать и декодировать формат LZSS, [5] но эта функция была вырезана из версии 5. Game Boy Advance BIOS может декодировать слегка измененный формат LZSS. [6] Mac OS X от Apple использует LZSS как один из методов сжатия кода ядра. [7]

Алгоритм LZSS

Эта версия алгоритма LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982. Базовый алгоритм был улучшен по трем направлениям:

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

Содержание

Модель данных [ править ]

Реализация «скольжения» [ править ]

Как и в алгоритме LZ77, в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77. Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.

Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция «смещение по модулю размер», может быть заменена побитовой логической операцией, что еще больше повышает эффективность.

Организация поиска в словаре [ править ]

Скорость кодирования LZ77 сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины [math]M[/math] (максимальная длина совпадения). В дереве хранятся все подстроки словарной части размером длины буфера.

Порядок изменения дерева поиска [ править ]

Кодер изучает буфер поиска, создавая [math]T [/math] строк с числом символов [math]L[/math] , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями. На дереве все время находится одинаковое число [math]T [/math] узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, [math]T=S-L+1[/math] .

Если во время кодирования случается совпадение длины [math]k[/math] , то дерево надо перестроить путем удаления [math]k[/math] строк и добавления [math]k[/math] строк.

Удаляться будут первые [math]k[/math] строк буфера поиска до его сдвига, а добавляться будут последние [math]k[/math] строк этого буфера после сдвига.

Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних [math]L[/math] символов буфера поиска и добавить ее на дерево. Это следует повторить [math]k[/math] раз.

Для определения смещения уславливаемся, что:

нулевое смещение зарезервировали для обозначения конца кодирования;
если имеется несколько фраз с одинаковой длиной совпадения, то выбираем ближайшую к буферу.

Покажем на примере, как в алгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь.

Пример [ править ]

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

sid_eastman_clum

sily_

teases_sea_sick_seals

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

Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как [math]12=16-5+1[/math] ), которые помещены на двоичное дерево поиска вместе с их смещениями.

Таблицы 1 и 2. Строки по пять символов.

Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями [math]16[/math] и [math]10[/math] , но первая из них, sid_e, имеет более длинное совпадение. Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть [math]L-1[/math] .

В нашем примере длина совпадения равна [math]2[/math] , поэтому кодер выдает метку [math]\langle[/math] [math]16,2[/math] [math]\rangle[/math] . Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:

d_eastman_clumsi

ly_te

ases_sea_sick_seals

С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi (см. табл.2). Для того чтобы найти эти строки, можно просмотреть все вершины дерева и выбрать те пары, где разница между смещением и длиной буфера не превосходит длины части совпадения. В данном примере длина буфера — [math]5[/math] символов, часть совпадения — [math]2[/math] символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит [math]2[/math] . Это смещения [math]5[/math] и [math]6[/math] . Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.

Оптимизация памяти [ править ]

У алгоритма LZ77 возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Такое кодирование существенно понижает производительность алгоритма.

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

Кодер LZSS [ править ]

Инициализация [ править ]

Для того чтобы кодер мог начать работать, необходимо загрузить буфер очередными символами сообщения и проинициализировать дерево. Для этого в дерево вставляется содержимое буфера.

Основной цикл работы [ править ]

Алгоритм последовательно выполняет следующие действия:

Кодирует содержимое буфера.
Считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря.
Вставляет в дерево новые строки, соответствующие считанным символам.

Завершение работы [ править ]

Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» после того, как он обработал все символы сообщения.

Пример кодирования [ править ]

Закодировать по алгоритму LZSS строку «КРАСНАЯ КРАСКА». В данном примере один символ кодируется восемью битами. Поэтому после префикса [math]0[/math] декодер считывает следующие [math]8[/math] бит. После префикса [math]1[/math] хранится пара [math]\langle[/math] [math]offset,length[/math] [math]\rangle[/math] . Так как смещение и длина не превосходят длины словаря, то размер пары [math]\langle[/math] [math]offset,length[/math] [math]\rangle[/math] равен удвоенному количеству бит, требуемых для хранения длины словаря. Длина словаря в данном примере [math]8[/math] . Поэтому после префикса [math]1[/math] декодер считывает [math]6[/math] бит.

Декодер LZSS [ править ]

Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.

Декодер читает один бит сжатой информации и решает — это символ или пара [math]\langle[/math] [math]offset,length[/math] [math]\rangle[/math] . Если это символ, то следующие [math]8[/math] бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.

Пример декодирования [ править ]

LZSS, длина словаря — [math]8[/math] байт (символов). Коды сжатого сообщения —

Практическое использование алгоритма LZSS [ править ]

Так как алгоритм LZSS не является запатентованным, он широко используется. LZSS можно удачно скомбинировать с методами сжатия, основанными на переменной длине кода (Алгоритм Хаффмана, алгоритм Шеннона-Фано (Shannon-Fano)) например в PKZIP V.1.0 использован LZSS в комбинации с алгоритмом Шеннона-Фано, а в ARJ — LZSS с алгоритмом Хаффмана.

Lzss как понять