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

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

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

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

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

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

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

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

Во второй строке — текст, который надо закодировать, в третьей — код.

Начинаем кодировать текст, одновременно пополняя словарь:

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

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

Если бы мы действовали согласно предшествующему алгоритму, то должны были бы занести в словарь ми, но это слово уже есть в словаре под номером $ 9_{} $! Подставляем вместо нее ее код:

А что заносим в словарь? — Слово, получаемое присоединением к ми следующего символа текста, т.е. пробела. Итак, словарь может пополняться не только двухбуквенными, но и трехбуквенными, четырехбуквенными и т.д. словами. В верхней строке таблицы стоят номера словарных слов; эти номера и берутся в качестве кодов при кодировании следующих кусков текста. Очередной пришедший на вход процесса кусок текста состоящий сначала из двух букв проверяем на наличие его в словаре. Если его там нет, то заносим в словарь под очередным номером, а в кодовую строку подставляем код первой его буквы (она-то в словаре всегда есть!). Если же двухбуквенное слово в словаре уже имеется, то дополняем его очередной буквой кодируемого текста и снова проверяем полученное трехбуквенное слово на наличие в словаре. Если его там нет, заносим в словарь под очередным номером, а вместо словарного двухбуквенного слова подставляем в кодовую строку его номер из словаря. Именно это происходит на следующем шаге: _о содержится в словаре, но _оо не содержится, поэтому в кодовую строку добавляем $ 12 $

а в словарь — трехбуквенное слово _оо. Идем далее:

Вот уже в словаре появляется четырехбуквенное слово…

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

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

Здесь уже появилось пятибуквенное…

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

Полученная кодировка $ 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 …

Стартовое состояние: известна кодировка базового словаря (алфавита). Это позволяет декодировать начальный отрезок закодированного текста

Параллельно процессу декодирования запускается процесс заполнения (восстановления) словаря. После того как произошло декодирование первых двух чисел в буквы, из этих букв формируется новое слово и помещается в словарь

Номер этого слова $ 6_{} $ и является его кодировкой. Декодировав следующее число кодировки в букву т мы снова образуем словарное слово, подсоединив эту букву к предыдущей декодированной:

Дальнейшая процедура протекает аналогично вплоть до вот этого момента

Следующее поступившее на вход процесса число $ 9_{} $ не входит в базовый алфавит. Но, однако же, она уже занесена в разворачиваемый словарь: ей соответствует слово ми:

Какое слово следует занести в словарь под номером $ 15 $? — Слово, первая буква которого уже известна из предыдущего шага, а именно и, а второй буквой берется первая буква последнего декодированного слова, т.е. м

Продолжаем процесс декодирования

3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 …

Какое слово следует занести в словарь под номером $ 16 $? — К слову ми, декодированному на предыдущем шаге, присоединяется первый символ слова, декодированного на последнем шаге, т.е. пробел:

Продолжаем процесс

3 1 4 3 2 1 1 0 3 0 1 9 12 3 5 4 16 …

Какое слово следует занести в словарь под номером $ 20 $: тм или тми ? — Именно тм: очередное слово имеет окончание совпадающим с приставкой следующего слова, но эта общая часть должна состоять только из одной буквы.

Это правило позволяет согласовать генерацию словаря с той, что совершалась в ходе кодирования текста. ♦

В том же алфавите (и при той же кодировке его букв в словаре) декодировать

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_{} $.

Кодирование не вызывает проблем:

Декодируем:

В словарь за номером $ 4 $ мы должны поместить слово из трёх букв, первые две из которых ма, а третьей надо взять первую из следующего $ 5 $-го декодируемого блока. Число $ 4 $ указывает на номер соответствующего слова в словаре. Но этого слова еще в словаре нет! Проблема состоит слишком «медленном» заполнении словаря — оно слишком быстро потребовалось!

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

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

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

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

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

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 $ цифрами.

Что делать? — Отказываться от требований блочности и однозначности кодирования.

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

Пример.

Первые шаги алгоритма кодирования абсолютно идентичны рассмотренным в его начальной версии:

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

Код слова ом равен $ \underline{8}_{_{10}}=\underline{1000}_{_2} $, т.е. он требует уже $ 4 $ бита для записи. Что же подставить в кодовую строку вместо буквы o — код $ 011 $? — Нет, код $ 0011 $. Начиная с $ 8 $-го шага все кодовые последовательности становятся $ 4 $-хбитными:

Дошли до $ 5 $-битного номера $ \underline{16}_{_{10}}=\underline{10000}_{_2} $. Должны подставить вместо словарного слова ми его код $ 1001 $, а новому словарному слову ми_ присвоить номер $ 10000 $. Но мы подставляем вместо ми код $ 01001 $: все кодовые слова с $ 16 $-го по $ 31 $-е будут кодироваться $ 5 $-битными блоками:

Иными словами, кодовые последовательности становятся шагозависимыми. Если на очередном шаге требуется закодировать слово т, то его кодировка будет $ 100 $ если этот шаг — за номером $ 7 $, $ 00100 $ — если он имеет номер $ 20 $ и $ 000100 $ — если его номер $ 50 $. Неудобно? — Зато можно однозначно декодировать: проблема разбиения кодовой последовательности на блоки решается автоматически. А уж отсечь лишние нули в начале декодируемого блока — не проблема.

Насколько экономичен алгоритм 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 \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_{} $ первых слов³⁾ кодируемого текста равно $$ \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 $ означает целую часть числа ).

Пример. В английском переводе «Войны и мира»⁴⁾ выбросили все буквы кроме $ 9 $: a,e,g,h,i,r,s,t,z, после удаления символов пустоты «затягивались», но пробелы между словами учитывались в качестве $ 10 $-й буквы алфавита.

Буквы алфавита кодировались байтами, т.е. в приведенной выше формуле $ n_{}=8 $.

За счет чего осуществляется экономия? — За счет того, что в натуральном языке работают статистические закономерности. Определенный артикль the будет встречаться достаточно часто, если его закодировать небольшим количеством бит, то в ходе дальнейшего кодирования будем экономить. Именно это и происходит в примере: пятибайтное слово _the_ заносится в словарь на $ 380 $-м шаге и, следовательно, при дальнейшем кодировании будет «стоить» всего $ 9_{} $ бит⁵⁾ ♦

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

Буквы алфавита кодировались байтами, т.е. в приведенной выше формуле $ n_{}=8 $.

[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.