Вернер М. Основы кодирования (2004), страница 10

Алгоритм Ле'мпеля-Зива LZ77 был предложен в 1977 году и модифицирован в 1984 г. Он используется в рекомендации ITU V.42.bisи называется LZW алгоритмом.6,2. Арифметическое кодированиеПри арифметическом кодировании мы исходим из того факта, чтопри нормализованном распределении сумма вероятностей символов(и соответствующих им относительных частот) источника всегда равна единице. Если относительные частоты символов неизвестны передатчику и приемнику:к78Глава 6. Сжатие данныхТаблица 6.1. Буквы и их относительные частоты.БукваОтносительная частотаЕSGLR0,50,20,10,10,1- они могут определяться, например, путем текущих статистических изменений передаваемой информации в фиксированные моменты времени;- приемник и передатчик совместно, исходя из относительныхчастот, устанавливают жесткие правила кодирования.Особенностью арифметического кодирования является то, чтодля отображения последовательности символов в потоки натуральных чисел на интервале [0,1] используются относительные частоты.Результатом такого отображения является сжатие символов (посимвольное сжатие) в соответствии с их вероятностями.

Пояснимидею арифметического кодирования с помощью следующего примера.Рассмотрим арифметическое кодирование последовательностибукв «GELEEESSER». Относительные частоты букв в этом потокеприведены в таблице 6.1.Процедура кодирования представлена на рис. 6.2.Первой букве «G», в соответствии с ее относительной частотой,соответствует интервал [0.7,0.8[. Согласно алгоритму, каждая цепочка букв, начинающихся с G, всегда будет отображаться в число, принадлежащее этому интервалу.

Таким образом, в рассматриваемомпримере первая десятичная цифра после запятой уже определена.Кодирование последующих букв производится аналогично с темважным отличием, что теперь делению каждый раз будет подвергаться интервал, выбранный на предыдущем шаге. Из рис. 6.2 следует, что букве «Е» на втором шаге соответствует интервал [0.7,0.75[.Таблица 6.3, в которой алгоритм кодирования прослежен но шагам, показывает, что последовательность «GELEEESER» отображается в число 740387 (0 и запятая не нуждаются в отображении). Отметим, что:1. Часто встречающимся буквам ставятся в соответствие большиеинтервалы.

На их отображение затрачивается меньше десятичныхцифр, чем на отображение редко встречающихся букв.2. Длинные сообщения отображаются в «длинные» числа. Представление этих чисел в двоичной форме, необходимое для передачисообщений, приводит к появлению кодовых слов большой длины.6,2. Арифметическое кодирование79 JПрактическая реализация скользящего алгоритма арифметического кодирования требует высокой точности, которая ограничивается длиной кодовых слов.

Для сокращения необходимой длины регистра, при реализации арифметического кодирования используетсяцелочисленная арифметика с выдачей уже готовых промежуточныхрезультатов.Рис. 6.2. Арифметическое кодирование.Алгоритм представлен в таблице 6.2. Механизм его действия раскрывается с помощью таблицы 6.3. В нашем примере для реализациикодирования достаточно регистра для хранения шести текущих десятичных цифр.В соответствии с таблицей 6.2, на первом шаге происходит инициализация переменных LO и HI.

Для первой кодируемой буквы«G» ширина интервала равна В = l'000'OOO. Нижняя и верхняя границы равны соответственно LO =F 0 4- l'000'OOO • 0, 7 = 700'000 и/// = 0 + l'000'OOO -0,8- 1 = 799'999. Первая десятичная цифра ужеопределена и равна 7, а содержимое регистров LO и HI сдвигаетсяна одну позицию влево. Заметим, что в регистре LO освободившеесяместо занимает 0, а в регистре HI - 9.к80Глава. 6. Сжатие данныхТаблица 6.2. Алгоритм арифметического кодирования.Начальные значенияIII - 999'999РегистрLO- ООО'ОООСимволЕSGLRLS(-)00,50,70,80,9HS(-)0,50,70,80,91АлгоритмШирина интервалаВ=Ш-Ш+1Нижняя границаLO=LO - B L SВерхняя границаHI-LO+BHS-1Для второй буквы «Е» ширина интервала равна В = l'000'OOO,поэтому, получаем LO = 0 + l'000'OOO = ОООО' ОО и HI = 0+ l'000'OOO0,5 — 1 = 499'999. Кодирование последующих букв проводится аналогично.

В завершении работы алгоритма выдается некоторое числоиз последнего интервала. Для этого мы округляем верхнюю границу интервала HI, отбрасывая младшие разряды до тех пор, покаэто возможно. В результате получаем число с минимальным количеством цифр, принадлежащее последнему интервалу.6.3. Кодирование Лемпеля - ЗиваАлгоритм кодирования Лемпеля Зива LZ77 основан на принципединамических словарей. Мы представим вкратце эту концепцию инаглядно поясним ее на простейших примерах [19].В основе алгоритма лежат четыре основные идеи:1. Каждая очередная закодированная последовательность символов добавляется к ранее закодированным символам таким образом, что вместе с ними она образует разложение всей переданной и принятой информации на несовпадающие междусобой фразы (Парсинг).2. Такое разложение хранится в памяти и используется в дальнейшем в качестве словаря.3.

Кодирование осуществляется при помощи указателей на фразыиз уже сформированного словаря фраз. .6.3. Кодирование Лемпсля - ЗиваТаблица 6.3. Арифметическое«GELEEESSER».СимволLOIIIСтартООО'ООО 999'999G700'000 799'999Выход/сдвиг ООО'ООО 999'999ЕООО'ООО 499'999L400'000 449'999Выход/сдвиг ООО'ООО 499'999кодированиеВыходСимволLOЕфразыHIS312'500 437'499S375'000 399'999Выход/сдвиг 750'000 999'9994ВыходООО'ООО 062'499Выход/ сдвиг ООО'ООО 624'999781Е750'000 874'999862'500 874'999'ЕООО'ООО 249'999RЕООО'ООО 124'999Конец03874. Кодирование является динамической процедурой, ориентированной на блоки. Сам процесс кодирования может быть дополнен скользящими окнами, содержащими текущий словарь фрази Look-ahead буфером.ФразаF A|C|H|H|O|C|H|S|C|H|U|L|E21 20 19 18 17 16 15 14 13 12 11 10 9 8lF|U|LlD765|43Буфер Look-aheadА¥ А С Н|В|Е R Е2 1Рис.

6.3. Скользящее окно алгоритма LZ77, соответствующее фразе FACH.В процессе кодирования обрабатываемый текст отображается впоследовательность указателей или флагов. Структура закодированного текста показана на рис. 6.4. В примере, показанном на рис. 6.3,цепочка букв «FACH» заменяется последовательностью [21,4,5].Относительныйадрес в словареЧисло совпадающихсловСледующийсимвол из буфера,который отличаетсяот продолжения фразыв словаре фразРис. 6.4. Структура указателей.82Глава 6.

Сжатие данныхФраза] jTj~l2[l I j IOi 4 [ Й [ 7 fft [ Д' pt" J '2 Г IФразаБуфер Look-aheadI !N'F[6iRiMJA r f]!lON-NdT-MATTRR-'NOR-'ENFROY:JiilillEElL1I5.7.TI^ Look-ahead_j IO'N : -"N]OJX! -||I5,4.N|fyrfep Look-ahead^)t-NOR-ENERGY1iji11iTTi] 1111 Oj 9 p J 7 Щ 5r z iVJ2~T~4 Д"б[7'|110.1.T1Фраза!15.14 13j 12 II 1 0 . 9 8 7 6 5 4 1 J | 2 I 1Буфер Look-ahead1 ' З Д . 4 5 I6 7 ,I4.1.M)Фразаl5;l4}i?|T2TTi]7o|T[8Буфер Look-aheadА ? О Ж ? Г - Л Й IQI ^ENERGY112[П.2.Т]ФразаБуфер Look-aheadмГХГтЩрИ -"Шо 1 TUM1A1T]¥HRPNTOTRI-.IE1I 5 i l 4 1.1 I 2 J I I 1 0 9 | 8 7 6 5 4 | 32I 2|3'4.. 5 [ 6 | 7 |[O,O,EJФразаАТТЛОЩ - f6 [S [4f ]EERGYНулевая фразаБуфер Look-aheadRI -"N O7i[0,0,R]|RGYНулевая фразаР и с . 6.5.

Пример кодирования по алгоритму LZ77 о нулевой фразой и повторением символов.На рис. 6.5 представлен некоторый частный случай и приведеноего алгоритмическое решение. На шестом шаге кодирования очередным является символ «Е», не содержащийся в словаре фраз. В этомслучае он кодируется посредством, так называемой, «нулевой фразы».

«Нулевая фраза» имеет вид [0, 0, символ] и при декодированиираспознается по двум стоящим рядом нулям.Еще одним интересным случаем является повторение символов,так называемое Character Rans. В этом случае, для замены символаиспользуются уже два флага. Первый «О» служит признаком по-6.3. Кодирование ЛемпеляЗиваявления некоторой особенности текста. Последующие «1» и символуказывают на то, что символ повторяется. Во втором флаге указывается число повторений и последующий символ.Затраты на кодирование определяются длиной окна, содержащего словарь фраз шр, длиной Look ahead буфера u>i и затратами надвоичное представление указателяКг— = log2 UJP + log2 uL + 8.бит(6.2)Кодирование Лемпеля - Зива приводит к сжатию данных в т,омслучае, если затраты на кодирование, т.е.

длина указателя в двоичном исчислении в среднем оказывается меньше, чем при непосредственном кодировании, например, кодом ASCII, что соответствует 8битам на один символ.В типичном случае LJV = 2 1 2 = 4096 и u>i = 24 = 16 и затраты надвоичное представление указателя составляют 24 бита. Для фразы,состоящей из четырех букв, которая уже содержится в словаре фраз,экономия, но сравнению с прямым кодированием кодом ASCII(32бита), составляет 25 %.Для кодирования Лемпеля - Зива установлено, что:• Часто появляющиеся цепочки символов кодируются очень эффективно;• Редко появляющиеся символы и последовательности символовс течением времени удаляются из словаря фраз;• Повторяющиеся символы также кодируются эффективно;• На кодирование нулевых фраз затрачивается относительно большое число бит;• Методы теории информации позволяют доказать, что кодирование методом Лемпеля - Зива асимптотически оптимально.Это означает, что для очень длинного текста избыточность исчезает, то есть среднее число бит, необходимое для кодированияодного символа, стремится к энтропии текста;• Практически достижимая степень сжатия для длинных текстов составляет 50 60%.ГЛАВА 7ДИСКРЕТНЫЕ КАНАЛЫБЕЗ ПАМЯТИ И ПЕРЕДАЧАИНФОРМАЦИИ7.1.