Фантазии о Вселенной и мой личный сайт
Страница запроса

Как работает LZW

Часть I. "Штурм"

LZW... для меня он был кошмаром. Да и сейчас тоже есть... но плохо выполнимый на асме алгоритм. Но это достаточно распространенный и простой алгоритм сжатия, применяемый теперь в изображениях формата GIF (Graphic Interleace Format). Он позволяет без потерь сжать информацию, используя метод повторяющихся последовательностей, с учетом словаря, как его называют.

Суть всего метода заключается в том, что он ищет повторяющиеся ранее фрагменты данных и должным образом их кодирует. Но сказать легко, а понять труднее. Допустим, есть строка данных:
IAMTHEBUIZAMTHENUIZGTHEBAUIZA#
Нужно ее "сжать". Алгоритм LZW работает так: он проходит строку слева направо всю, ища в ней соответствующие повторящиеся фрагменты и записывает их в "словарь". Вначале в словаре ничего нет, потому берутся две первых буквы и записываются в словарь. А почему? Потому что они могут пригодится. Эти две буквы из строки – это [IA], которому мы присваиваем номер 256, потому что этот номер не занят никакой буквой и записываем последнюю букву из сочетания в файл (или на экран), который кодируем. Дальше алгоритм берет следующие две буквы [AM], НО! начиная со второй позиции, и смотрит, есть ли они в словаре... опс, а там и нету. Записывает эти две буквы "на всякий случай"... идет дальше... Таким образом, прогнав достаточно далеко и записав в словарь сочетания [IA], [AM], [MT], [TH], [EB], [BU], [UI], [IZ], [ZA] (довольно-таки много), он натыкается на следующее сочетание букв [AM], которое уже ранее в словаре встречалось. Непорядок... а как раз все нормально тут: алгоритм делает следующее – он добавляет к этому сочетанию следующую букву "T", получая [AMT]. Как известно, в словаре ранее этого сочетания не было, потому алгоритм добавляет полученную строку в словарь. Продолжим далее... закончив на букве "T", он снова начинает с нее поиск, образовав с ней пару со следующим символом, с "H", получая новое сочетание [TH]. Оно имеется в словаре уже, значит, добавлять в него не надо повторяющееся значени, берем следующую букву, "E". Получилось [THE], раннее в словаре не встречающееся. Так... последняя буква было "E", теперь она станет первой для нового сочетания [EN], которое добавляется в словарь, т.к. ранее там оно не наблюдалось, так же добавляется [NU], а вот уже [UI] было, так что добавляется в словарь [UIZ].

Продолжу в виде таблицы:
[ZG]   не было, добавляем, присваиваем номер
[GT]   не было, добавляем, номер + 1
[TH]   было... так, значит, берем следующую букву "E"
[THE]  тоже было, берем теперь букву "B"
[THEB] не было точно, добавим в словарь, номер + 1
[BA]   не было, в словарь под следующим номером (уже даже непонятно, каким)
[AU]   так же, как и в прошлои разе
[UI]   есть, добавим [Z]... тоже есть, добавим [A] – получилось [UIZA]. Этого в словаре нет, добавим и присвоим следующий номер.

Теперь в словаре находятся следующие последовательности:
[IA] [AM] [MT] [TH]     – последовательности под номерами 256, 257, 258, 259
[EB] [BU] [UI] [IZ]     – номер 260, 261, 262, 263
[ZA] [AMT] [THE] [EN]   – 264, 265, 266, 267
[NU] [UIZ] [ZG] [GT]    – 268, 269, 270, 271
[THEB] [BA] [AU] [UIZA] – 272, 273, 274, 275
Хорошо, словарь заполнен. Теперь осталось разобраться со следующим вопросом – а зачем это все было надо?! И вообще, при чем здесь номера какие-то и последовательности?

Часть II. "Прояснение сознания"

Начну как бы с общего примера и как бы издалека. Например, есть строка:
"ИДУ Я ;) ПОЙДУ. Я ПОЙНДУ ;)"
Допустим следующее: если где-нибудь в этой строке я увижу вот это [256], то напишу "ДУ", а если вот это [257], то пишу я – "ПОЙ"; или вот это – [258], то смело вычерчиваю рожицу с приколом ";)" Так... Тогда, в этом случае, могу написать и это:
"И[256] Я [258] [257]Н[256] [258]"
Фу ты... белиберда какая! [258] ой.... Кончая шутить, можно сказать, что данные [..] с циферой есть замены определенным сочетанием букв, то будет очень прекрасно. Тем более, заметив следующую интересную особенность – сочетания букв всегда занимают больше места в памяти (даже если это 2 буквы подряд), чем код, который замещает их.

Например, сказав 256, подрузамеваем "ДУ". Данное выражение "ДУ"(РАК) :) хм... не все же не сдержался :-) прошу извинить... в общем, занимает в памяти 16 бит, т.к. один символ "Д" или "У" содержит в себе 8 бит, а два – 16. Дело в том, что число 256 требует только 9 бит, значит, происходит экономия целых 7 бит! Теперь попробуем проверить, сколько "сэкономили" на сжатии вышесказанно страшного и ужасного выражения. Было в этом выражении 27 байт(ов), они занимают аж 216 бит(ов).

Так, теперь пересчитаем второе выражение. Каждый символ будет там занимать 9 бит. Так уж надо, чтобы учесть то, что [256], [257] и [258] тоже символ в 9 бит. Пересчет показал, что там 12 символов, а это из этого следует, что 9*12 = 108. Вот! Сжатие уже произошло в 108 битов! Ровненько и наполовину, т.е. показатель сжатия был был равен 50% даже несмотря на то, что один символ отнимает 9 бит(ов). Вот как словари выручают в трудную минуту :-)

Часть III. "Кодировщик"

Окрыленный успехом, я беру и уверенно кодирую ту строку, что была еще в первой части нашего развеселого повестовавания. Это строка "IAMTHEBUIZAMTHENUIZGTHEBAUIZA#". Теперь, беру я словарь, гляжу в него и начинаю выписывать все последовательности по порядку, какие найду:
[256][258]H[260][262]Z[265]H[267][269][271][272]A[274]
 IA   MT  H EB   UI  Z AMT H EN   UIZ  GT   THEBA UIZA
Расчудесно! Получилось всего 14 символов по 9 бит, это значит, что 126 бит всего потрачено вместо 8*29 = 232! Степень сжатия почти половина, 54%. Надо пойти это дело отметить...

Пока я радовался, словарь куда-то делся. Непонятно, куда. То ли кто-то украл, то ли взял почитать, а не отдал, то ли еще чего. Может, в щелку провалился случайно, кто знает :-( Но так или иначе, а его... нет. Так что вместо праздника тяжелая работа декодера странных иероглифов, что только что понятны были, а сейчас вообще не понятны. Так-так... как же раскодировать? Остались буквы HZHA от всего 29-байтного кода, который только что архивировал... Потом мне стало понятно, в чем дело. Словарь я записал, ну и что теперь с того, если у меня его не будет на другой машине, скажем? Тогда такой метод превращается в хлам.

Но выход есть. Все дело в том, что словарь должен создаваться и дополняться по ходу расшифровки данных. Значит, первоначально данные должны существовать. Возьму простое слово, чтобы было понятно с ходу.
VETER[ET]H[ER][ETH]A#
Здесь легко заметно, что ET повторяется дважды, значит, оно уже есть в словаре, как знаем. Не забывая, конечно, что [ETH] тоже добавится в словарь, по правилам заполнения словаря. Таким же образом заменяется [ER], а потом [ETH], так как они все были недавно добавлены в словарь. При расшифровке этого кода в словаре будут последовательно созданы следующие элементы:
[256] VE
[257] ET
[258] TE
[259] ER
[260] RE
[261] ETH
[262] HE
[263] ERE
[264] ETHA
[265] A#
Все буквы и последовательности букв, помеченные полужирным начертанием шрифта, заменяются каким-нибудь кодом. Если это одиночная буква, она заменяется кодом от 0 до 255 из таблицы ASCII, проще говоря, просто выдается сама буква. Если это группа буквы, например, [ET], [ER], [ETH], они заменяются кодами [257], [259] и [261] соответственно. Теперь зашифрованный код будет выглядеть следующим образом:
VETER[257]H[259][261]A#
Итак... экономия пока небольшая. Из 15*8=120 битов код был "скомпрессован" в 9*11 = 99 битов, экономия около 3 байт. Как бы то ни было, неплохо! Суть расшифровки LZW заключается в том, что при самой же расшифровке алгоритм "на лету" создает словарь и, используя его, может заместить 2 или более байтов одним лишь символом, но уже большим 255. Разберем более простое слово.
"BAMBATAM"
Словарь такой:
[256] – [B]A
[257] – [A]M
[258] – [M]B
[259] – [BA]T
[260] – [T]A
[261] – [AM]
  • Начинаем усиленный скан со второй позиции. Буква "A", а перед ней буква "B" образуют сочетание [BA], ранее в словаре не существующее. Ладно, раз так, то добавим в [256] элемент нашего "расширенного словаря" получившееся слово [BA]. Тогда, в таком случае, выдаем предыдущую букву, т.е. "B", на экран.
  • Следующая буква "M", а если к ней присоединить предыдущую "A", получится "AM", в словаре, ясное дело, не встречавшееся, и потому сидящая сейчас под биркой [257]. Записываем предыдущую букву "A" на экран.
  • Мужественно боремся дальше. На подходе буквочка "B", та-ак... Словосочетание [MB] тоже добавляется в словарь под номером [258], а предыдущая буква "M", в таком случае, выдается на экран.
  • Наконец, подобрались к новой "A". Присоединив к ней предыдущую букву, получаем... [BA]! Чудесно! Отлично! Она есть в словаре... но нужно удостовериться, так что двигаемся дальше.
  • На следующей позици засела буква "T", которая, совместно с "BA", будет выглядеть как [BAT], в словаре не существовавшее ранее. Ладно, тогда пусть эта летучая мышь (Bat, англ.) сидит себе мирно в нашем музее-словаре под биркой [259]... А что делать с [BA]? Нельзя же его записать прямо так – [BA]? Оно ведь встречалось в словаре под номером [256]! Так вот берем, и записываем оный номер на экран (или в файл), и по уши довольны сжатием супер-инфы :-)
  • Переходим к букве "A", которая образует с предыдущей ей буквой "T" сочетание [TA]. Добавляем в словарь под номером [260]. Это очевидно уже и так.
  • Следующая буква "M", а предыдущая буква "A", значит [AM]. В словаре есть это, значит, нужно допроверить, может быть, джек-пот выпадет, и, присоединив еще букву, другой, более длинный словарный элемент выпадет. Так как следующей буквы, к сожалению, нет, ограничимся и этим. Так... если такое дело, то вместо [AM] записываем код [257].

Вот... Вроде все. В итоге вот что наблюдается: "BAM[256]T[257]" – 6 символов вместо 8. Хотя тут мало что меняет, ведь 6*9 = 54, а 8*8 = 64, сжатие супер, прямо 10 бит. Если еще повезет. Могут быть довольно страшные выражения вида 123456789ABCDEFGHIJKLMNO и т.д. где словарь может создаваться бесконечно и без единой замены. Он же тоже ограничен – если он превысит 256 значении, начнет заполняться уже другими значениями, постепенно вымещая старые.