УказательРазделыОбозначенияАвторО проекте


Вспомогательная страница к разделу КОДИРОВАНИЕ


Алгоритм LZW

Статистические методы кодирования, имеющие целью сжатие передаваемой информации — типа префиксных кодов Хаффмана или Шеннона-Фано — предполагают предварительный анализ всего кодируемого документа и составление кодовой таблицы. Последняя должна быть известной декодеру или же, в общем случае, быть приложенной к закодированному документу.

Можно ли осуществить процесс кодирования со сжатием без предварительного статистического анализа? Иными словами, хочется организовать кодирование источника в поточном режиме, т.е. по мере поступления кодируемых данных и формировать кодовую таблицу (словарь) одновременно с кодированием (ну, или с небольшим запаздыванием), динамически пополняя его с учетом «прошлого опыта» — уже закодированного таким способом начального куска документа.

Именно это предлагается в алгоритме Лемпеля-Зива-Уэлча (Lempel—Ziv—Welch) или LZW[1,2]. Более того, алгоритм не предполагает необходимости передачи декодеру составленного кодером словаря: по получении закодированной последовательности и при дополнительном знании кодировки начальных слов словаря (обычно, некоторого базового «алфавита»), декодер может сам динамически, т.е. в параллель с декодированием, восстановить исходный кодовый словарь!

§

Идея алгоритма напомнила мне идею шифрования по методу Кардано.

Кодирование (первое приближение)

П

Пример. Алфавит языка состоит из четырех букв и,м, о, т и пробела1). Требуется закодировать текст

оитомии о ими оооитми о о о ооиимтомиимотоим оои тоо и и м оио и омтоо тоимо т и

Стартовое состояние словаря: известна кодировка букв алфавита, будем считать, что она совпадает с нумерацией этих букв согласно таблице:

оитомии_о_ими

Шаги 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 указывает на номер соответствующего слова в словаре. Но этого слова еще в словаре нет! Проблема состоит слишком «медленном» заполнении словаря — оно слишком быстро потребовалось!

Для разрыва этого порочного круга2) сообразим, что нам нужна информации только о первой букве 5-го декодируемого блока. Но она нам известна из того правила как производится декодирование:

Шаги 0 1 2 3 4 5 6
Код 1 0 2 4 0
Текст м а ма ма?
Словарь а м ма ам ма?

Вместо знака ? в нижней строке может быть только буква м. Это рассуждение позволяет продолжить процедуру декодирования — вплоть до ее благополучного окончания.


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

И для разрешения этой коллизии нам придется откорректировать алгоритм кодирования.

Кодирование (коррекция алгоритма)

Решение коллизии возможно, например, удовлетворением требования блочности кода: все кодовые блоки делаем одинаковой длины. В рассмотренном примере в кодовой последовательности

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? Тестирование производилось с помощью реализации, осуществленной Иваном Боровым.

П

Пример. Текст

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 бит .
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 бит .
2856/(1052\times 3) \approx 0.905 \ ,

т.е. эффективность сжатия порядка 10_{} %.

Можно считать кодируемую в предыдущем примере последовательность фактически случайной. В следующем примере оставим в алфавите побольше букв, чтобы получить приближение реального языка с его статистическими зависимостями. Для упрощения расчетов будем считать, что базовый алфавит закодирован числами от 0_{} до 2^n-1 записанными n_{}-битными блоками, и кодирование собственно документа начинается с номера 2^n. В таких предположениях, количество бит, необходимых для кодирования L_{} первых слов3) кодируемого текста равно

\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 означает целую часть числа ).

П

Пример. В английском переводе «Войны и мира»4) выбросили все буквы кроме 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)

П

Пример. Текст «Идиота»6) в русском алфавите, без буквы ё, пробел учитывается, знаки препинания — нет.

Буквы алфавита кодировались байтами, т.е. в приведенной выше формуле 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.

1) В дальнейшем пробел тоже будем считать буквой.
2) circulus vitiosus (лат.)
3) Это значит: на момент окончания кодирования словарь состоит из L слов, без учета алфавита.
4) Кодирование производилось, начиная с Главы 3, первого тома
5) На самом деле, при дальнейшем увеличении объема кодируемого текста эта стоимость будет постепенно возрастать; см. материал предыдущего пункта. Теоретически она может достигнуть когда-нибудь и 5 байт. Объем словаря к этому моменту должен составить не менее 2.08 \times 10^{13} слов. Согласно вот этой ССЫЛКЕ, количество символов (букв и пробелов) в оригинальном тексте Льва Толстого — 2 709 700.
6) Кодирование производилось, начиная с Главы 1

2016/01/07 11:46 редактировал au