§ Часть I. "Штурм"
Эта статья написана под руководством идиотизма в 20 лет, потому что я не знал как работает LZW (Лис из будущего).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].