Лекция 1_09: Методы сжатия информации

Постановка задачи

Исследование экономичных схем поиска привело к появлению первого метода сжатия информации, который был назван методом Хаффмена. Фактически Дэвид Хаффмен (1925-1999) просто нашел очень красивый метод решения задачи, рассмотренной в предыдущей лекции. Его метод использовали для сокращения объемов передаваемой и хранимой информации, и построенные на его основе программы оказались настолько эффективны, что вызвали целый поток конкуррентных исследований в этой области.

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

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



Префиксные коды. Код Хаффмена

Часто префиксный код называется кодом Шеннона-Фено, по имени двух известных американских специалистов, предложивших этот подход независимо друг от друга. Рассмотривается алфавит, символы которого кодируются последовательностями из нулей и единиц, и, в отличие от прошлой практики, кодовые последовательности разных символов имеют различную длину. Для того, чтобы обеспечить распознавание символов требуется, чтобы никакая кодовая комбинация не была префиксом (началом) другой кодовой комбинации.

Коды, обладающие таким свойством, называются префиксными.

Шеннон и Фено поставили (независимо) задачу о поиске префиксного кода с минимальным математическим ожиданием длины кодовой комбинации в предположении, что кодируемые символы появляются независимо и имеют заданный закон распределения. Они предложили способ нахождения кода, близкого к оптимальному.

Метод поиска точного решения этой задачи и предложил математик Д. Хаффмен. Его метод основывается на нескольких простых утверждениях. Мы их сейчас и рассмотрим.



Монотонность длин кодовых последовательностей


Лемма 1. Пусть алфавит  A  состоит из  n  символов с вероятностями  p1, p2, ... pn.  Пусть длины кодовых последовательностей этих символов в оптимальном коде равны соответственно  r1, r2, ... rk.

Тогда ни для какой пары различных индексов  k  и  l  не могут одновременно выполняться неравенства

       pk < pl    и    rk < rl .

Доказательство. Действительно, при выполнении этих неравенств верно и неравенство

       (pl − pk) · (rl − rk) > 0.

Это неравенство можно переписать так

       pl · rl + pk · rk > pl · rk + pk · rl.

Из него видно, что если у  k-го и  l-го символов поменять кодовые комбинации, то значение целевой функции (т. е. математическое ожидание длины кодовой комбинации случайно выбранного символа) уменьшится. Значит, в оптимальном коде таких пар быть не может, и лемма доказана.

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



Самые длинные кодовые последовательности


Лемма 2. В оптимальном коде количество самых длинных кодовых последовательностей четно.

Доказательство. Двоичное дерево, соответствующее оптимальному коду, должно быть полным — у каждого узла, не являющегося листом, должно быть двое детей. А листы, уровень которых максимален, могут быть детьми узлов, только образуя пары.



Сокращение алфавита

Из леммы 2 следует, что у двух самых редких символов алфавита  A  длины кодовых комбинаций одинаковы (во всяком случае, есть оптимальный код с таким свойством). Сократим алфавит, объединив два эти символа в один — особый, найдем для сокрашенного алфавита оптимальный код, а затем преобразуем его в код для исходного алфавита, продлив двумя способами кодовую комбинацию особого символа, т. е. приписав к нему 0 и 1, и назначив эти новые комбинации символам, составившим особый.

Если вероятности символов, составляющих особый, равны  p  и  p',  то вероятность особого символа будет равна  
p + p',  и математическое ожидание длины кодовой последовательности для исходного и сокращенного алфавита будут отличаться ровно на эту величину, не зависящую от самого кода. Поэтому верна следующая лемма


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



Из этих лемм легко виден алгоритм построения оптимального кода, который можно описать рекурсивно:

Если число символов в алфавите равно 2, закодировать их 0 и 1 (порядок несущественен).
В противном случае соединить два самых редких символа в один, найти оптимальный код для сокращенного алфавита, а затем этот оптимальный код преобразовать в оптимальный код для исходного алфавита, удлинив кодовую комбинацию особого символа.

В 1971 г. студенты матмеха Петер Сёке и Андрей Терехов предложили очень удобную реализацию алгоритма Хаффмена. Алфавит состоит из двух списков: исходных символов и новых символов. В каждом из списков символы упорядочены по возрастанию их вероятностей.

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



Пример


17 19 23 29 35 37 51 5436 = 17+19 Минимальные частоты 17 и 19
17 19 23 29 35 37 51 54 36 52 = 17+19 Минимальные частоты 23 и 29
17 19 23 29 35 37 51 54 36 52 71 = 35+36 Минимальные частоты 35 и 36
17 19 23 29 35 37 51 54 36 52 71 88 = 37+51 Минимальные частоты 37 и 51
17 19 23 29 35 37 51 54 36 52 71 88 106 = 52+54 Минимальные частоты 52 и 54
17 19 23 29 35 37 51 54 36 52 71 88 106 159 = 71+88 Минимальные частоты 71 и 88

Осталось два символа с частотами 106 и 159. Им сопоставляются кодовые комбинации 0 и 1. Теперь начанается обратный ход.


cod(106) = 0 cod(159) = 1 Разбиваем 159 = 71 + 88
cod(79) = 10 cod(88) = 11 Разбиваем 106 = 52 + 54
cod(52) = 00 cod(54) = 01 Разбиваем 88 = 37+51
cod(37) = 110 cod(51) = 111 Разбиваем 71 = 35+36
cod(35) = 100 cod(36) = 101 Разбиваем 52 = 23+29
cod(23) = 000 cod(29) = 001 Разбиваем 36 = 17+19
cod(17) = 1010 cod(19) = 1011 Код построен



Преобразование MTF (Move To Front)

Доказанная оптимальность кода Хаффмена предполагает независимость символов в тексте. Между тем, в реальных текстах такой независимости нет, так что могут быть (и на самом деле имеются) способы сжатия с более высокими характеристиками, чем у алгоритма Хаффмена.

Прежде всего отметим, что алгоритм Хаффмена может использоваться как один из шагов в цепочке преобразований. В качестве возможного другого преобразования иногда используется плгоритм, получивший название Move To Front или просто MTF.

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

В качестве примера рассмотрим, как преобразуется строка
ababaabbacacacacccccccaabbddddbdbdddbdbd
В этой строке 40 символов, и каждый из четырех символов встречается ровно по 10 раз, так что кодировка Хаффмена даст для каждого из символов двухбитовый код, и среднее будет равняться двум. Применим теперь MTF.

Номер Буква Код Новые Очередь
1 a 0 a a
2 b 0 ab ba
3 a 2 ab ab
4 b 2 ab ba
5 a 2 ab ab
6 a 1 ab ab
7 b 2 ab ba
8 b 1 ab ba
9 a 2 ab ab
10 c 0 abc cab
11 a 2 abc acb
12 c 2 abc cab
13 a 2 abc acb
14 c 2 abc cab
15 a 2 abc acb
16 c 2 abc cab
17 c 1 abc cab
18 c 1 abc cab
19 c 1 abc cab
20 c 1 abc cab
21 c 1 abc cab
22 c 1 abc cab
23 a 2 abc acb
24 a 1 abc acb
25 b 3 abc bac
26 b 1 abc bac
27 d 0 abcd dbac
28 d 1 abcd dbac
29 d 1 abcd dbac
30 d 1 abcd dbac
31 b 2 abcd bdac
32 d 2 abcd dbac
33 b 2 abcd bdac
34 d 2 abcd dbac
35 d 1 abcd dbac
36 d 1 abcd ab
37 b 2 abcd bdac
38 d 2 abcd dbac
39 b 2 abcd bdac
40 d 2 abcd dbac

Посмотрим статистику появления различных цифр в получившемся коде. Сама строка выглядит так
0022212120222222111111213101112222112222
В ней цифра 2 встречается 20 раз, цифра 1 — 15 раз, цифра 0, как и ожидалось, 4 раза и один раз цифра 3. Конечно, наш пример был очень «тенденционзым», чтобы усилить эффект.



Метод Зива-Лемпеля

Замечательные методы сжатия были предложены американскими учеными Джекобом Зивом и Абрахамом Лемпелем. Мы рассмотрим ту разновидность, которая называется методом LZ-78.

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

В качестве примера рассмотрим ту же строку, которая была примером в методе MTF
ababaabbacacacacccccccaabbddddbdbdddbdbd
Символ a составляет первую строку и кодируется парой 0a. Символ b составляет вторую строку и кодируется парой 0b. Пара символов ab составляет третью строку и кодируется парой 1b. Можно все это записывать таблицей.

Номер Строка Код
1 a 0a
2 b 0b
3 ab 1b
4 aa 1a
5 bb 2b
6 ac 1c
7 aca 6a
8 c 0c
9 acc 7cb
10 cc 8c
11 ccc 10c
12 aab 4b
13 bd 2d
15 d 0d
16 dd 15b
17 bdb 13b
18 ddd 16d
19 bdbd 17b

Разумеется, номер каждой строки записывается как число. Можно было бы для получающегося закодированного текста найти статистику встречаемости номеров и символов и сжать получившийся текст еще и по Хаффмену. Такое усовершенствование описывалось и используется, но большого приращения эффекта это дополнение не дает.

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



Метод Зива-Лемпеля-Велча (LZW)

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

Предопределенными строками являются все мыслимые однобайтовые строки. Номер каждой строки — это код составляющего ее символа. Таким образом предопределено 256 строк, нумеруемых от 0 до 255.

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

В качестве примера рассмотрим все ту же строку. Появляющиеся в ней символы имеют коды от 97 до 100
ababaabbacacacacccccccaabbddddbdbdddbdbd
Символ a составляет первую строку и кодируется числом 97. Строка [97]b = ab запоминается с номером 256. Опять составим таблицу.

Строка Код Новая строка Номер
a 97 ab 256
b 98 ba 257
ab 256 aba 258
a 97 aa 259
ab 256 abb 260
ba 257 bac 261
c 99 ca 262
a 97 ac 263
ca 262 cac 264
cac 264 cacc 265
c 99 cc 266
cc 266 ccc 267
ccc 267 ccca 268
aa 259 aab 269
b 98 bb 270
b 98 bd 271
d 100 dd 272
dd 272 ddd 273
d 100 db 274
bd 271 bdb 275
bd 271 bdd 276
dd 272 ddb 277
bdb 275 bdbd 278
d 100

В этом варианте от каждой строки передается только ее номер. И этого оказывается достаточно для полного восстановления закодированного текста!

Обычно под каждый номер отводится 12 битов, так что можно накапливать 4096 номеров. Когда лимит номеров исчерпывается, происходит «сброс», и система строк начинает накапливаться заново.

Метод LZW часто используют в модемах — договорившись о способе сжатия, модемы переходят в сжатый режим передачи, и прямо на ходу передающий модем зашифровывает текст, а принимающий его разбирает и передает получателю в естественном виде.



Метод Барроуза-Уилера

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

Два последних преобразования нам уже известны, рассмотрим два первых.

Прежде всего выполняется лексикографическое упорядочение всех суффиксов сжимаемого текста. Здесь требуется сразу много пояснений.

Текст рассматривается как одна длинная (огромная) строка. Для удобства в конце этой строке добавляется специальный «флажковый символ» — sentinel, который больше в тексте не встречается. В качестве этого флажкового символа обычно в примерах берется знак доллара.

Суффиксом называется любая строка, получающаяся из исходной удалением некоторого начала. Суффиксы упорядочиваются лексикографически, причем сентинел считается предшествующим любому другому символу. Методы построения такого упорядочения особенно интенсивно развивались в последние несколько лет.

Возьмем все ту же строку, к которой добавим флажковый символ
ababaabbacacacacccccccaabbddddbdbdddbdbd$
Упорядоченные суффиксы будут выглядеть так (перед каждым суффиксом записан — он нам еще понадобится — предшествующий ему символ, для полной строки взят флажковый символ)
d $
b aabbacacacacccccccaabbddddbdbdddbdbd$
c aabbddddbdbdddbdbd$
b abaabbacacacacccccccaabbddddbdbdddbdbd$
$ ababaabbacacacacccccccaabbddddbdbdddbdbd$
a abbacacacacccccccaabbddddbdbdddbdbd$
a abbddddbdbdddbdbd$
b acacacacccccccaabbddddbdbdddbdbd$
c acacacccccccaabbddddbdbdddbdbd$
c acacccccccaabbddddbdbdddbdbd$
c acccccccaabbddddbdbdddbdbd$
a baabbacacacacccccccaabbddddbdbdddbdbd$
a babaabbacacacacccccccaabbddddbdbdddbdbd$
b bacacacacccccccaabbddddbdbdddbdbd$
a bbacacacacccccccaabbddddbdbdddbdbd$
a bbddddbdbdddbdbd$
d bd$
d bdbd$
d bdbdddbdbd$
d bdddbdbd$
b bddddbdbdddbdbd$
c caabbddddbdbdddbdbd$
a cacacacccccccaabbddddbdbdddbdbd$
a cacacccccccaabbddddbdbdddbdbd$
a cacccccccaabbddddbdbdddbdbd$
c ccaabbddddbdbdddbdbd$
c cccaabbddddbdbdddbdbd$
c ccccaabbddddbdbdddbdbd$
c cccccaabbddddbdbdddbdbd$
c ccccccaabbddddbdbdddbdbd$
a cccccccaabbddddbdbdddbdbd$
b d$
b dbd$
d dbdbd$
d dbdbdddbdbd$
b dbdddbdbd$
d ddbdbd$
d ddbdbdddbdbd$
b dddbdbd$
d dddbdbdddbdbd$
b ddddbdbdddbdbd$
 Именно строка, составленная из этих красных предшествующих символов нам и нужна. Вот она

dbcb$aabcccaabaaddddbcaaacccccabbddbddbdb

Построение этой строки по найденному упорядочению и было вторым преобразованием текста. Зачем же нам такое странное преобразование? Рассмотрим некоторые свойства получившейся строки.

Во-первых, она состоит точно из тех же символов, что и исходный текст. Во-вторых, по ней можно восстановить строку первых символов упорядоченных суффиксов — для этого нужно просто отсортировать символы строки
$aaaaaaaaaabbbbbbbbbbccccccccccdddddddddd

В-третьих, выровняв, т. е. поставив друг под другом, две получившихся строки, мы увидим все двухсимвольные подстроки исходного текста
dbcb$aabcccaabaaddddbcaaacccccabbddbddbdb
$aaaaaaaaaabbbbbbbbbbccccccccccdddddddddd

По этому сопоставлению можно восстановить весь текст. Понятно, что в конце текста стоит флажковый символ $, и если мы найдем его во второй строке, то над ним в первой строке будет стоять исходный последний символ. В нашем примере это символ d. Из всех вхождений символа в первую строку это вхождение первое, и мы опознаем его среди одинаковых символов второй строки по занимаемому месту. Над ним стоит символ b, который в первой строке является шестым среди всех b. Почему это так? Потому, что суффиксы расположены у нас в лексикографическом порядке, и расположение суффиксов, начинающихся с одной и той же буквы определяется расположением их «хвостов» — суффиксов на единицу меньшей длины.

Таким приемом — вычислением номера вхождения символа в верхней строке и использованием этого номера в нижней — мы расшифровываем всю строку.

Продолжим пример. Найденную строку

dbcb$aabcccaabaaddddbcaaacccccabbddbddbdb

преобразуем по MFT

Номер Буква Код Новые Очередь
1 d 0 d d
2 b 0 db bd
3 c 0 dbc cbd
4 $ 0 dbc $cbd
5 $ 0 dbc$ $bcd
6 a 0 dbc$a a$bcd
7 a 1 dbc$a a$bcd
8 b 3 dbc$a ba$cd
9 c 4 dbc$a cba$d
10 c 1 dbc$a cba$d
11 c 1 dbc$a cba$d
12 a 3 dbc$a acb$d
13 a 1 dbc$a acb$d
14 b 3 dbc$a bac$d
15 a 2 dbc$a abc$d
16 a 1 dbc$a abc$d
17 d 5 dbc$a dabc$
18 d 1 dbc$a dabc$
19 d 1 dbc$a dabc$
20 d 1 dbc$a dabc$
21 b 3 dbc$a bdac$
22 c 4 dbc$a cbda$
23 a 4 dbc$a acbd$
24 a 1 dbc$a acbd$
25 a 1 dbc$a acbd$
26 c 2 dbc$a cabd$
27 c 1 dbc$a cabd$
28 c 1 dbc$a cabd$
29 c 1 dbc$a cabd$
30 c 1 dbc$a cabd$
31 a 2 dbc$a acbd$
32 b 3 dbc$a bacd$
33 b 1 dbc$a bacd$
34 d 4 dbc$a dbac$
35 d 1 dbc$a dbac$
36 b 2 dbc$a bdac$
37 d 2 dbc$a dbac$
38 d 1 dbc$a dbac$
39 b 2 dbc$a bdac$
40 d 2 dbc$a dbac$
41 b 2 dbc$a bdac$


Выпишем строку получившихся кодов:
0, 0, 0, 2, 0, 0, 1, 3, 4, 1, 1, 3, 1, 3, 2, 1, 5, 1, 1, 1,
3, 4, 4, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 4, 1, 2, 2, 1, 2, 2, 2
Имеем:

Число (как символ) "0" "1" "2" "3" "4" "5"
Встречаемость 5 17 9 5 4 1
Длина кодовой последовательности 3 1 3 3 4 4
Произведение 15 17 27 15 16 4

Общая длина закодированного текста равна
15 + 17 + 27 + 15 + 16 + 4 = 94 бита.
Получается по два с четвертью бита на символ. Правда, нужно прибавить к этому декодировочную таблицу кода Хаффмена и строку новых букв для MTF.
Окончательный вариант расчетов этого примера выполнил студент А. Алексеев (2209).



Упражнения


  1. Подсчитайте частоты символов во фразе и по этим частотам постройте код Хаффмена
    • на_дворе_трава_на_траве_дрова_не_руби_дрова_на траве_двора
    • aaabbaaabbababababaaaaabbbaaaabbbaaabbbbaaabbbdadadadadadddddaaa
    • мороз_и_солнце_день_чудесный_еще_ты_дремлешь_друг_прелестный (А. Пушкин)
    • майомбе_бомбе_майомбе_майомбе_бомбе_майомбе_майомбе_бомбе_майомбе_ (Николас Гильен)
    Подсчитайте математическое ожидание длины кодовой комбинации.

  2. Закодируйте полученным кодом вторую строку, переведите результат в 16-ричную систему счисления и разбейте на байты.
  3. Постройте код Хаффмена для строки, полученной в результате работы преобразования MTF.
  4. Методом LZ сожмите строку aaaaabbaabaaaabbaabbaaaaabbbbaaaaaa.
  5. Эту же строку сожмите методом LZW, а затем восстановите исходную строку из сжатого текста.
  6. Методом Барроуза-Уилера сожмите строку 4 из первого упражнения.



Экзаменационные вопросы


  1. Метод сжатия Хаффмена.

  2. Метод MTF (Move To Front).

  3. Метод сжатия LZ.

  4. Метод сжатия LZW.

  5. Метод сжатия Барроуза-Уилера.

ІZ