Алгоритм LZ-78
В данной же статье мы рассмотрим идею, лежащую в основе алгоритмов семейства LZ-78 (L и Z - первые буквы фамилий Лемпеля и Зива, разработчиков первого LZ-алгоритма, 78 - год публикации) на примере широко известного алгоритма LZW (Лемпеля-Зива-Уэлча). Методы данного семейства относятся к словарным методам, в основе работы которых лежит принцип "повторения старого". Эти методы выделяют во входных данных повторяющиеся строки и заменяют их определенными кодами. Упомянутый же метод Хаффмана относится к статистическим методам, работающим по принципу "сокращения частого".
Итак, приступаем. Что нам понадобится для работы? Во-первых, данные, которые мы будем сжимать. Во-вторых, нам понадобится словарь, в котором мы будем хранить закодированные строки. Размер словаря выбирают равным целой степени двойки, обычно используют словари размером от 210 до 214 гнезд. В гнезда словаря мы будем заносить повторяющиеся строки, причем по номеру гнезда мы сразу сможем определить код данной строки (он будет равен номеру гнезда минус 1). Сразу отметим, что, хотя число кодов у нас равно размеру словаря, но для кодирования повторяющихся строк мы будем использовать на два кода меньше, поскольку последние два кода мы зарезервируем для служебных целей (о них поговорим чуть позже). После выбора размера словаря нам необходимо перед непосредственно архивированием провести инициализацию словаря, занеся в его первые гнезда все односимвольные строки. Их количество зависит от типа входных данных. В самом общем случае будут заполнены первые 256 гнезд словаря (т. е. в него мы занесем всю стандартную таблицу ASCII-символов). Но если известна особенность входных данных, предполагающая ограничение диапазона возможных символов, то количество инициализируемых гнезд может быть уменьшено.
Переходим теперь непосредственно к сжатию. Будем читать по одному символу входных данных, добавляя их в конец строки S (изначально пустой). При этом после каждого добавления будем проверять, есть ли полученная строка S в нашем словаре. В случае, если такая строка в словаре уже присутствует, то мы продолжим чтение входных данных. В противном случае (строки нет в словаре) выполняем следующие действия. Строку S можно представить в виде S'c, где c - последний добавленный символ, а S' - предшествующая ему строка, уже содержащаяся в словаре. Тогда в архив мы записываем код, соответствующий строке S', а в следующее пустое гнездо словаря добавляем строку S. После чего оставляем в строке S только последний прочитанный символ c и продолжаем процесс чтения входных данных.
Вот, в принципе, и весь алгоритм LZW. Упомянем еще о некоторых важных моментах. Если вы помните, мы зарезервировали два кода для служебных целей. Речь сейчас пойдет именно о них. Первый из этих кодов будем использовать в качестве признака завершения сжатия. При упаковке нескольких файлов в один архив необходимо по окончанию сжатия каждого файла записать данный код (иначе как распаковщик узнает, где заканчивается один файл и начинается другой?). Второй код - это код очистки словаря. Какого бы размера вы не взяли словарь, все равно найдутся такие данные, при сжатии которых словарь будет полностью заполнен в процессе архивирования. В этом случае можно либо "заморозить словарь" (т. е. прекратить добавлять в него новые строки), либо очистить его (записав в архив код очистки), причем можно очистить словарь как полностью (т. е. привести его в проинициализированное состояние), либо частично.
По такому принципу работает упаковщик. Вкратце опишем алгоритм работы распаковщика. После инициализации словаря (процессы инициализации у упаковщика и распаковщика должны быть полностью идентичны!) читается первый код из сжатых данных, и соответствующая ему строка выводится в разархивируемый файл. Следующие действия повторяются циклически до тех пор, пока не будет встречен признак завершения сжатия. Сохраняем прочитанный код как "старый". Читаем следующий код. Если такой код уже есть в словаре, то мы в разархивируемый файл выводим строку S, соответствующую этому коду, а в словарь добавляем строку вида S'K, где S' - это строка старого кода, а K - первый символ строки S. Если же в словаре прочитанного кода еще нет, то мы в разархивируемый файл выводим строку S'K' (K' - первый символ S') и эту же строку добавляем в словарь.
Ну ладно, хватит теории. Теория без практики мертва. Поэтому давайте рассмотрим на простеньком примере, как же работает алгоритм LZW. Возьмем, к примеру, текст "Мама мыла раму. Раму мыла мама". Словарь инициализируем всеми символами ASCII-таблицы, так что кодом для символа будет его порядковый номер в этой таблице.
Процесс сжатия представим таблицей (в третьем столбце в скобках указан номер гнезда, соответствующий строке S):
Прочитанный символ |
Строка S |
Строка в словаре |
Пишем в архив |
Добавляем строку с кодом |
'М' |
'М' |
есть (140) |
||
'а' |
'Ма' |
нет |
140 |
'Ма' 256 |
'м' |
'ам' |
нет |
160 |
'ам' 257 |
'а' |
'ма' |
нет |
172 |
'ма' 258 |
' ' |
'а ' |
нет |
160 |
'а ' 259 |
'м' |
' м' |
нет |
32 |
'м' 260 |
'ы' |
'мы' |
нет |
172 |
'мы' 261 |
'л' |
'ыл' |
нет |
235 |
'ыл' 262 |
'а' |
'ла' |
нет |
171 |
'ла' 263 |
' ' |
'а ' |
есть (259) |
||
'р' |
'а р' |
нет |
259 |
'а р' 264 |
'а' |
'ра' |
нет |
224 |
'ра' 265 |
'м' |
'ам' |
есть (257) |
||
'у' |
'аму' |
нет |
257 |
'аму' 266 |
'.' |
'у.' |
нет |
227 |
'у.' 267 |
' ' |
'. ' |
нет |
46 |
'. ' 268 |
'Р' |
' Р' |
нет |
32 |
' Р' 269 |
'а' |
'Ра' |
нет |
144 |
'Ра' 270 |
'м' |
'ам' |
есть (257) |
||
'у' |
'аму' |
есть (266) |
||
' ' |
'аму ' |
нет |
266 |
'аму ' 271 |
'м' |
' м' |
есть (260) |
||
'ы' |
' мы' |
нет |
260 |
' мы' 272 |
'л' |
'ыл' |
есть (262) |
||
'а' |
'ыла' |
нет |
262 |
'ыла' 273 |
' ' |
'а ' |
есть (259) |
||
'м' |
'а м' |
нет |
259 |
'а м' 274 |
'а' |
'ма' |
есть (258) |
||
'м' |
'мам' |
нет |
258 |
'мам' 275 |
'а' |
'ма' |
есть (258) |
||
'.' |
'ма.' |
нет |
258 |
'ма.' 276 |
конец данных |
. |
46 |
|
И еще несколько слов. Во-первых, как можно заметить, строки, хранимые в словаре, обладают определенной особенностью: если в словаре есть строка S длины N, то должны быть также и строки длины 1, 2, ... , k, ... , N-1, состоящие из k первых символов строки S (таким образом, словарь у нас обладает свойством префиксности). Что же из этого следует? Во-первых, в словаре можно хранить строку S не полностью, а как указатель на строку, состоящую из первых N-1 символа строки S плюс последний символ, обеспечивающий ее уникальность. Во-вторых, данная особенность влияет на поиск строки в словаре. Так что когда мы ищем в словаре строку S длины N, то нам нет необходимости просматривать весь словарь. Мы начнем наш поиск со следующего за содержащим строку S' гнезда. Во-вторых, мы не сказали ни слова о размере нашего словаря. Давайте посмотрим, какие бы результаты сжатия у нас получились, если бы размер словаря был равен 1024 (210, 10-битовый код) или 8192 (212, 12-битовый код) гнезд. Длина нашего примера - 31 символ. Так как каждый символ кодируется 8 битами, то исходный текст должен был занимать 31*8=241 бит. В архив мы записали 23 кода (22 кода для строк, последний - признак окончания сжатия). Таким образом, в первом случае размер архива у нас будет 23*10=230 бит, а во втором - 23*12=276 бит. Что же получается - в первом случае мы действительно сжали текст, а во втором, наоборот, увеличили? Да, возможно и такое. Однако из этого не следует, что словарь нужно брать меньшего размера. Просто текст, взятый нами для примера, имел небольшую длину, да и повторяющиеся строки встречались не так уж и часто. Естественно, на больших объемах данных алгоритм все таки сожмет их.
Вот, в принципе, и все, что касается метода LZW. Отличие других методов семейства LZ-78 (среди них - MW, AP, Y) заключается в способе добавления новых строк в словарь. В частности, метод MW добавляет в словарь не строку S, как метод LZW, а конкатенацию строк S' и P' (S' - это подстрока строки S, уже имеющаяся в словаре, а P' - аналогичная строка для предыдущего добавления в словарь). Метод AP добавляет в словарь уже не одну строку, а множество строк AP(P',S'), т. е. все префиксы строки P'S'.
DelphiWorld 6.0