!!§!!
Вспомогательная страница к разделу
☞
((:codes#kody_xaffmana КОДИРОВАНИЕ))
----
==Алгоритм LZW==
~~TOC~~
Статистические методы кодирования, имеющие целью сжатие передаваемой информации --- типа префиксных кодов ((:codes#коды_хаффмана Хаффмана)) или
((:shannon#код_шеннона_-_фано Шеннона-Фано)) --- предполагают предварительный анализ __всего__ кодируемого документа и составление кодовой таблицы. Последняя должна быть известной декодеру или же, в общем случае, быть приложенной к закодированному документу.
Можно ли осуществить процесс кодирования со сжатием без предварительного статистического анализа? Иными словами, хочется организовать кодирование источника в //поточном режиме//, т.е. по мере поступления кодируемых данных и формировать кодовую таблицу (словарь) одновременно с кодированием (ну, или с небольшим запаздыванием), динамически пополняя его с учетом "прошлого опыта" --- уже закодированного таким способом начального куска документа.
Именно это предлагается в алгоритме Лемпеля-Зива-Уэлча (Lempel—Ziv—Welch) или ** LZW**((#источники [1,2])). Более того, алгоритм __не предполагает__ необходимости передачи декодеру составленного кодером словаря: по получении закодированной последовательности и при дополнительном знании кодировки начальных слов словаря (обычно, некоторого базового "алфавита"), декодер может сам динамически, т.е. в параллель с декодированием, восстановить исходный кодовый словарь!
!!§!! Идея алгоритма напомнила мне идею ((:crypto#шифр_кардано шифрования по методу Кардано)).
===Кодирование (первое приближение)==
!!П!! **Пример.** Алфавит ((:codes:vspom1 языка)) состоит из четырех букв **и**,**м**, **о**, **т** и пробела[[В дальнейшем пробел тоже будем считать буквой.]]. Требуется закодировать текст
**оитомии о ими оооитми о о о ооиимтомиимотоим оои тоо и и м оио и омтоо тоимо т и**
Стартовое состояние словаря: известна кодировка букв алфавита, будем считать, что она совпадает с нумерацией этих букв согласно таблице:
**оитомии_о_ими**
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ^ ^ ^ ^ ^ ^
^ Код | 0 | 1 | 2 | 3 | 4 | | | | | | | | | | | | | | | | | |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
Во второй строке --- текст, который надо закодировать, в третьей --- код.
Начинаем кодировать текст, одновременно пополняя словарь:
**оитомии_о_ими**
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ^ ^ ^ ^ ^ ^
^ Код | 0 | 1 | 2 | 3 | 4 | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | | | | |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^
Словарь пополняется словами, состоящими из пар соседних букв, и эти слова нумеруются числами верхней строки. До сего момента собственно кодирование идет побуквенно: каждая буква заменяется на соответствующее число из кодировки алфавита. Однако следующий шаг привносит новизну в процесс кодирования:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ м ^ и ^ ^ ^ ^ ^
^ Код | 0 | 1 | 2 | 3 | 4 | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | | | | |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им | ми |
Если бы мы действовали согласно предшествующему алгоритму, то должны были бы занести в словарь **ми**, но это слово уже есть в словаре под номером $ 9_{} $! Подставляем вместо нее ее код:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ _ ^ ^ ^ ^ ^
^ Код | 0 | 1 | 2 | 3 | 4 | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | | | |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^ ми_ ^
А что заносим в словарь? --- Слово, получаемое присоединением к **ми** следующего символа текста, т.е. пробела. Итак, словарь может пополняться не только двухбуквенными, но и трехбуквенными, четырехбуквенными и т.д. словами. В верхней строке таблицы стоят номера словарных слов; эти номера и берутся в качестве кодов при кодировании следующих кусков текста. Очередной пришедший на вход процесса кусок текста состоящий сначала из двух букв проверяем на наличие его в словаре. Если его там нет, то заносим в словарь под очередным номером, а в кодовую строку подставляем код первой его буквы (она-то в словаре всегда есть!). Если же двухбуквенное слово в словаре уже имеется, то дополняем его очередной буквой кодируемого текста и снова проверяем полученное трехбуквенное слово на наличие в словаре. Если его там нет, заносим в словарь под очередным номером, а вместо словарного двухбуквенного слова подставляем в кодовую строку его номер из словаря. Именно это происходит на следующем шаге: **_о** содержится в словаре, но **_оо** не содержится, поэтому в кодовую строку добавляем $ 12 $
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ _о ^ ^ ^ ^ ^
^ Код | 0 | 1 | 2 | 3 | 4 | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | 12 | | |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^ ми_ ^ _оо ^
а в словарь --- трехбуквенное слово **_оо**. Идем далее:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ _о ^ о ^ ои ^ т ^ ми_ ^
^ Код | 0 | 1 | 2 | 3 | 4 | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | 12 | 3 | 5 | 4 | 16 |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^ ми_ ^ _оо ^ оо ^ оит ^ тм ^ ми_о ^
Вот уже в словаре появляется четырехбуквенное слово...
**оитомии_о_ими_оооитми_**
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ _о ^ о ^ ои ^ т ^ ми_ ^
^ Код | 0 | 1 | 2 | 3 | 4 | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | 12 | 3 | 5 | 4 | 16 |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^ ми_ ^ _оо ^ оо ^ оит ^ тм ^ ми_о ^
**о_о_о_ооиимтомиимотоим_оои_тоо_и_и_м_о**
^ Шаги | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
^ Текст ^ о_ ^ о_о ^ _оо ^ ии ^ м ^ то ^ ми ^ им ^ о ^ то ^ им ^ _оои ^ и_ ^ то ^ о_ ^ и_ ^ и_ ^ м ^ _o ^
^ Код | 13 | 22 | 17 | 10 | 2 | 7 | 9 | 15 | 3 | 7 | 15 | 24 | 11 | 7 | 13 | 11 | 11 | 2 | 12 |
^ Словарь ^ о_о ^ о_о_ ^ _оои ^ иим ^ мт ^ том ^ мии ^ имо ^ от ^ тои ^ им_ ^ _оои_ ^ и_и ^ тоо ^ о_и ^ и_и ^ и_м ^ м_ ^ _ои ^
Здесь уже появилось пятибуквенное...
**ио_и_омтоо_тоимо_т_иимиотмии**
^ Шаги | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 |
^ Текст ^ и ^ о_и ^ _о ^ мт ^ оо ^ _ ^ тои ^ м ^ о_ ^ т ^ _и ^
^ Код | 1 | 36 | 12 | 26 | 18 | 0 | 31 | 2 | 13 | 4 |
^ Словарь ^ ио ^ о_и_ ^ _oм ^ мто ^ оо_ ^ _т ^ тоим ^ мо ^ о_т ^ т_ ^
В строке <<Текст>> происходит просто "нарезка" кодируемого текста на слова, в строке <<Словарь>> последняя буква (окончание) очередного слова совпадает с первой буквой (приставкой) следующего.
Полученная кодировка $ 80 $-буквенного текста состоит из $ 46 $ однозначных и двузначных десятичных чисел:
**3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 13 22 17 10 2 7 9 15 3 7 15 24 11 7 13 11 11 2 12 1 36 12 26 18 0 31 2 13 4**
===Декодирование==
На вход процедуры подается последовательность чисел
**3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 ...**
Стартовое состояние: известна кодировка базового словаря (алфавита). Это позволяет декодировать начальный отрезок закодированного текста
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | ... | | | | | |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ^ ^ ^ ^ ^ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ | | | | | |
Параллельно процессу декодирования запускается процесс заполнения (восстановления) словаря. После того как произошло декодирование первых двух
чисел в буквы, из этих букв формируется новое слово и помещается в словарь
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | ... | | | | | |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои | | | | |
Номер этого слова $ 6_{} $ и является его кодировкой. Декодировав следующее число кодировки в букву **т** мы снова образуем словарное слово,
подсоединив эту букву к предыдущей декодированной:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | ... | | | | | |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои | ит | | | |
Дальнейшая процедура протекает аналогично вплоть до вот этого момента
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | | | | | |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ^ ^ ^ ^ ^ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ |
Следующее поступившее на вход процесса число $ 9_{} $ не входит в базовый алфавит. Но, однако же, она уже занесена в разворачиваемый словарь: ей соответствует слово **ми**:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | | | | | |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ ^ ^ ^ ^ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ |
Какое слово следует занести в словарь под номером $ 15 $? --- Слово, первая буква которого уже известна из предыдущего шага, а именно **и**, а второй буквой берется первая буква последнего декодированного слова, т.е. **м**
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | | | | | |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ ^ ^ ^ ^ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^
Продолжаем процесс декодирования
**3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 ...**
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | 12 | | | | |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ _о ^ ^ ^ ^ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^
Какое слово следует занести в словарь под номером $ 16 $? --- К слову **ми**, декодированному на предыдущем шаге, присоединяется первый символ слова, декодированного на последнем шаге, т.е. пробел:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | 12 | | | | |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ _о ^ ^ ^ ^ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^ ми_ ^
Продолжаем процесс
**3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 ...**
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | 12 | 3 | 5 | 4 | 16 |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ _о ^ о ^ ои ^ т ^ ми_ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^ ми_ ^ _о_ ^ оо ^ оит ^
Какое слово следует занести в словарь под номером $ 20 $: **тм** или **тми** ? --- Именно **тм**: очередное слово имеет окончание совпадающим с приставкой следующего слова, но эта общая часть должна состоять только из одной буквы.
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
^ Код | | | | | | 3 | 1 | 4 | 3 | 2 | 1 | 1 | 0 | 3 | 0 | 1 | 9 | 12 | 3 | 5 | 4 | 16 |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ _о ^ о ^ ои ^ т ^ ми_ ^
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^ ми_ ^ _о_ ^ оо ^ оит ^ тм |
Это правило позволяет согласовать генерацию словаря с той, что совершалась в ходе кодирования текста.
♦
!!?!! В том же алфавите (и при той же кодировке его букв в словаре) декодировать
**3 0 4 3 2 6 8 1 4 0 3 4 12 0 1 0 2 15 20 1 21 10 7**
В разобранном алгоритме декодирования имеется слабое место, которое проиллюстируем примером.
!!П!! **Пример.** Закодировать и декодировать текст **МАМАМАМА**. Кодировка алфавита: **а** --- $ 0_{} $, **м** --- $ 1_{} $.
Кодирование не вызывает проблем:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
^ Текст ^ ^ ^ м ^ а ^ ма ^ мам ^ а ^
^ Код | 0 | 1 | 1 | 0 | 2 | 4 | 0 |
^ Словарь ^ а ^ м ^ ма ^ ам ^ мам ^ мама ^
Декодируем:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
^ Код | | | 1 | 0 | 2 | 4 | 0 |
^ Текст ^ ^ ^ м ^ а ^ ма ^
^ Словарь ^ а ^ м ^ ма ^ ам |
В словарь за номером $ 4 $ мы должны поместить слово из трёх букв, первые две из которых **ма**, а третьей надо взять первую из следующего $ 5 $-го декодируемого блока. Число $ 4 $ указывает на номер соответствующего слова в словаре. Но этого слова еще в словаре нет! Проблема состоит слишком "медленном" заполнении словаря --- оно слишком быстро потребовалось!
Для разрыва этого порочного круга[[circulus vitiosus (//лат.//)]] сообразим, что нам нужна информации только о первой букве $ 5 $-го декодируемого блока. Но она нам известна из того правила как производится декодирование:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
^ Код | | | 1 | 0 | 2 | 4 | 0 |
^ Текст ^ ^ ^ м ^ а ^ ма | ма? |
^ Словарь ^ а ^ м ^ ма ^ ам | ма?|
Вместо знака ? в нижней строке может быть только буква **м**. Это рассуждение позволяет продолжить процедуру декодирования --- вплоть до ее благополучного окончания.
♦
----
В разобранном алгоритме декодирования имеется еще один, и более существенный недостаток. Как распознать очередную цифру на то является ли она номером первых девяти слов алфавита или же первой цифрой двузначного номера? В разобранном выше примере с пятибуквенным алфавитом все числа кодировки заботливо разделены пробелами, но в реальном потоке эти пробелы либо отсутствуют, либо же должны обеспечиваться дополнительными служебными битами.
И для разрешения этой коллизии нам придется откорректировать алгоритм кодирования.
===Кодирование (коррекция алгоритма)==
Решение коллизии возможно, например, удовлетворением требования ((:codes#блочные_коды блочности)) кода: все кодовые блоки делаем одинаковой длины. В рассмотренном ((#кодирование_первое_приближение примере)) в кодовой последовательности
**3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 13 22 17 10 2 7 9 15 3 7 15 24 11 7 13 11 11 2 12 1 36 12 26 18 0 31 2 13 4**
вставляем нули перед однозначными числами:
**03 01 04 03 02 01 01 00 03 00 01 09 12 03 05 04 16 13 22 17 10 02 07 09 15 03 07 15 24 11 07 13 11 11 02 12 01 36 12 26 18 00 31 02 13 04**
(и пробелы здесь сделаны исключительно только для удобства визуального восприятия; в реальности их нет). И сразу же теряем экономию в кодировании: $ 80 $-буквенный текст (который может быть закодирован таким же количеством десятичных цифр), теперь кодируется $ 92 $ цифрами.
Что делать? --- Отказываться от требований блочности и однозначности кодирования.
Возвращаемся к ((#кодирование_первое_приближение примеру)) из начала раздела, только теперь перепишем кодовые последовательности в более привычном бинарном виде.
!!П!! **Пример.**
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ^ ^ ^ ^ ^ ^
^ Код | 000 | 001 | 010 | 011 | 100 | | | | | | | | | | | | | | | | | |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
Первые шаги алгоритма кодирования абсолютно идентичны рассмотренным в его начальной версии:
**оитомии_о_ими**
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ^ ^ ^ ^ ^ ^
^ Код | 000 | 001 | 010 | 011 | 100 | 011 | 001 | 100 | | | | | | | | | | | | |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^
Код слова **ом** равен $ \underline{8}_{_{10}}=\underline{1000}_{_2} $, т.е. он требует уже $ 4 $ бита для записи. Что же подставить в кодовую строку вместо буквы **o** --- код $ 011 $? --- Нет, код $ 0011 $. Начиная с $ 8 $-го шага все кодовые последовательности становятся $ 4 $-хбитными:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | ... |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ^ ^ ^ ^ ^ ^
^ Код | 000 | 001 | 010 | 011 | 100 | 011 | 001 | 100 | 0011 | 0010 | 0001 | 0001 | 0000 | 0011 | 0000 | 0001 | | | | |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^
Дошли до $ 5 $-битного номера $ \underline{16}_{_{10}}=\underline{10000}_{_2} $. Должны подставить вместо словарного слова **ми** его код
$ 1001 $, а новому словарному слову **ми_** присвоить номер $ 10000 $. Но мы подставляем вместо **ми** код $ 01001 $: все кодовые слова с $ 16 $-го по $ 31 $-е будут кодироваться $ 5 $-битными блоками:
^ Шаги | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
^ Текст ^ ^ ^ ^ ^ ^ о ^ и ^ т ^ о ^ м ^ и ^ и ^ _ ^ о ^ _ ^ и ^ ми ^ _о ^ о ^ ои ^ т ^ ми_ ^
^ Код | 000 | 001 | 010 | 011 | 100 | 011 | 001 | 100 | 0011 | 0010 | 0001 | 0001 | 0000 | 0011 | 0000 | 0001 | 01001 | 01100 | 00011 | 00101 | 00100 | 10000 |
^ Словарь ^ _ ^ и ^ м ^ o ^ т ^ ои ^ ит ^ то ^ ом ^ ми ^ ии ^ и_ ^ _о ^ о_ ^ _и ^ им ^ ми_ ^ _оо ^ оо ^ оит ^ тм ^ ми_о ^
Иными словами, кодовые последовательности становятся шагозависимыми. Если на очередном шаге требуется закодировать слово **т**, то его кодировка будет $ 100 $ если этот шаг --- за номером $ 7 $, $ 00100 $ --- если он имеет номер $ 20 $ и $ 000100 $ --- если его номер $ 50 $. Неудобно? --- Зато можно однозначно декодировать: проблема разбиения кодовой последовательности на блоки решается автоматически. А уж отсечь лишние нули в начале декодируемого блока --- не проблема.
О чем подумалось в связи с такой "неоднозначностью" кодирования. При увеличении словаря все труднее становится поиск по нему очередного кандидата на кодирование: есть ли данное слово в словаре или еще нет? Допустим, мы совершили ошибку: слово в словаре есть, но мы его не
обнаружили и проверяемому слову присвоили новый код. То есть в словаре появляются одинаковые слова с разными кодами. Приведет ли это к ошибке декодирования? Нет! Именно такая возможность предлагалась первоначальными версиями алгоритма (**LZ** без **W**): когда поиск в словаре кодируемого слова осуществлялся только на определенную "глубину", а именно среди слов недавно добавленных в словарь (т.е. с номерами ненамного отличающимися от текущего).
===Стоимость==
Насколько экономичен алгоритм **LZW**? Тестирование производилось с помощью реализации, осуществленной **Иваном Боровым**.
!!П!! **Пример.** ((:codes:lzw:vspom1 Текст))
oitomii o imi oooitmi o o o ooiimtomiimotoim oi too i i m oio i omtoo toimo t
iimiotmii ttmiotoitoomt imo o t mii i i m o ooi o tom tototoi oto i moi t i o
mimto toootoi otomtioio t m iim toi m i iooim ittoomooo i i tom t oto iimitimoi
o tmi tmi otomi i too t tioot tim mii oiooi tooimioomiootoooioo i oomiotmiotomi
i o m ooo i tootmtiti i o ototi o omi i m iti i otooi i toooioomo i tmooi i oti
tot iimii mio i moo omt totoo o m mooii imt i totmi i oot i o otito tom tot otoiiii
i ootottm o ottoioooimo too imtoimoom oom titoo i oiomotoii i i oto iiioi i tioio
too o m too tiotomtii oii o iii tom mot imt tiooi
содержащий $ 613 $ символов может быть закодирован $ 3 \times 613 = 1839 $ битами. Алгоритм **LZW** дал $ 241 $ слово в словарь, стоимость кодирования
$$ 3 \times 3 + 8 \times 4 + 16 \times 5 + 32 \times 6 + 64 \times 7 + (241-3-120) \times 8 = 1705 \quad \mbox{ бит .} $$
$$ 1705/1839 \approx 0.927 \ , $$
т.е. получили $ 8_{} $ % экономии. Более длинный кусок, содержащий $ 1052 $ символа, дал $ 370 $ слов в словарь, стоимость кодирования
$$ 3 \times 3 + 8 \times 4 + 16 \times 5 + 32 \times 6 + 64 \times 7 + 128 \times 8 +(370-3-248)\times 9 = 2856 \quad \mbox{ бит .} $$
$$ 2856/(1052\times 3) \approx 0.905 \ , $$
т.е. эффективность сжатия порядка $ 10_{} $ %.
♦
Можно считать кодируемую в предыдущем примере последовательность фактически случайной. В следующем примере оставим в алфавите побольше букв, чтобы получить приближение реального языка с его статистическими зависимостями. Для упрощения расчетов будем считать, что базовый алфавит закодирован числами от $ 0_{} $ до $ 2^n-1 $ записанными $ n_{} $-битными блоками, и кодирование собственно документа начинается с номера $ 2^n $. В таких предположениях, количество бит, необходимых для кодирования $ L_{} $ первых слов[[Это значит: на момент окончания кодирования словарь состоит из $ L $ слов, без учета алфавита.]] кодируемого текста равно
$$ \sum_{j=n}^{K-1} 2^{j} (j+1) + (L-\sum_{j=n}^{K-1} 2^{j})(K +1) = (K-n+2)2^n -2^{K+1}+L(K+1) $$
при $ K=\lfloor \log_2 L \rfloor $ ( $ \lfloor \ \rfloor $ означает ((:algebra2:notations#целая_часть_числа целую часть числа)) ).
!!П!! **Пример.** В ((http://www.gutenberg.org/cache/epub/2600/pg2600.txt английском переводе)) "Войны и мира"[[Кодирование производилось, начиная с Главы 3, первого тома]] выбросили все буквы кроме $ 9 $: **a**,**e**,**g**,**h**,**i**,**r**,**s**,**t**,**z**, после удаления символов пустоты "затягивались", но пробелы между словами учитывались в качестве $ 10 $-й буквы алфавита.
Буквы алфавита кодировались байтами, т.е. в приведенной выше формуле $ n_{}=8 $.
^ Количество букв исходного текста | $ 10^3 $ | $ 10^4 $ | $ 3\cdot 10^4 $ | $ 10^5 $ | $ 5 \cdot 10^5 $ | $ 10^6 $ |
^ LZW-код (в байтах)| 403 | 3647 | 10471 | 33801 | 161867 | 318754 |
^ коэффициент сжатия |0.40 | 0.36 | 0.35 | 0.34 | 0.32 | 0.32 |
^ количество слов в словаре (L+256) | 417 | 2774 | 7075 | 20213 | 83884 | 156233 |
^ максимальное количество букв словарного слова | 7 | 10 | 11 | 13 | 16 | 17 |
^ пример самого длинного словарного слова | at_ther | _the_ite_i | _the_ite_h_ | the_riess_ith | _the_itte_riess_ | the_itte_riess_t_ |
^ номер этого слова в словаре | 389 | 505 | 1904 | 19668 | 59590 | 93855 |
За счет чего осуществляется экономия? --- За счет того, что в натуральном языке работают статистические закономерности. Определенный артикль **the** будет встречаться достаточно часто, если его закодировать небольшим количеством бит, то в ходе дальнейшего кодирования будем экономить. Именно это и происходит в примере: пятибайтное слово **_the_** заносится в словарь на $ 380 $-м шаге и, следовательно, при дальнейшем кодировании будет "стоить" всего $ 9_{} $ бит[[На самом деле, при дальнейшем увеличении объема кодируемого текста эта стоимость будет постепенно возрастать; см. материал предыдущего пункта. Теоретически она может достигнуть когда-нибудь и $ 5 $ байт. Объем словаря к этому моменту должен составить не менее $ 2.08 \times 10^{13} $ слов. Согласно вот этой
☞
((http://www.bolshoyvopros.ru/questions/794732-skolko-simvolov-s-probelami-v-romane-vojna-i-mir.html ССЫЛКЕ)), количество символов (букв и пробелов) в оригинальном тексте Льва Толстого --- $ 2 709 700 $.]]
♦
!!П!! **Пример.** Текст "Идиота"[[Кодирование производилось, начиная с Главы 1]] в русском алфавите, без буквы **ё**, пробел учитывается, знаки препинания --- нет.
Буквы алфавита кодировались байтами, т.е. в приведенной выше формуле $ n_{}=8 $.
^ Количество букв исходного текста | $ 10^3 $ | $ 10^4 $ | $ 10^5 $ | $ 5 \cdot 10^5 $ | $ 10^6 $ |
^ LZW-код (в байтах)| 673 | 5426 | 45150 | 202549 | 387402 |
^ коэффициент сжатия | 0.67 | 0.54 | 0.45 | 0.41 | 0.39 |
^ количество слов в словаре (L+256) | 819 | 4106 | 26383 | 103132 | 186841 |
^ максимальное количество букв словарного слова | 6 | 8 | 14 | 23 | 25 |
^ пример самого длинного словарного слова | были_б | ственном | настасья_филип | настасья_филипповна_все | лизавета_прокофьевна_не_б |
^ номер этого слова в словаре | 582 | 3091 | 25531 | 61932 | 131555 |
==Источники==
[1]. **Ziv J., Lempel A.** Compression of Individual Sequences via Variable-Rate Coding. //IEEE Trans. Inform. Theory//, 1978, V. 24 (5), pp. 530--536
[2]. **Welch T.** A Technique for High-Performance Data Compression. //Computer//, 1984, V. 17 (6), pp. 8–-19.
[3]. **Сэломон Д.** //Сжатие данных, изображений и звука.// М.Техносфера. 2006.