<< Предыдущая

стр. 14
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

В соответствии с таблицей 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- ООО'ООО
Е
Символ S G L R
0 0,5 0,7 0,8 0,9
LS(-)
HS(-) 0,5 0,7 0,8 0,9 1

Алгоритм
Ширина интервала В=Ш-Ш+1
Нижняя граница LO=LO - B L S
HI-LO+BHS-1
Верхняя граница




Для второй буквы «Е» ширина интервала равна В = l'000'OOO,
поэтому, получаем LO = 0 + l'000'OOO = О О О и HI = 0+ l'000'OOO-
ООО
'
0,5 — 1 = 499'999. Кодирование последующих букв проводится ана-
логично. В завершении работы алгоритма выдается некоторое число
из последнего интервала. Для этого мы округляем верхнюю грани-
цу интервала HI, отбрасывая младшие разряды до тех пор, пока
это возможно. В результате получаем число с минимальным количе-
ством цифр, принадлежащее последнему интервалу.


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

2. Такое разложение хранится в памяти и используется в даль-
нейшем в качестве словаря.
3. Кодирование осуществляется при помощи указателей на фразы
из уже сформированного словаря фраз. .
81
6.3. Кодирование Лемпсля - Зива

Таблица 6.3. Арифметическое фразы
кодирование
«GELEEESSER».

Символ LO III Выход Символ LO HI Выход
Старт ООО'ООО 999'999 Е ООО'ООО 062'499
G 700'000 799'999 Выход/ сдвиг ООО'ООО 624'999 0
Выход/сдвиг ООО'ООО 999'999 7 S 312'500 437'499
Е ООО'ООО 499'999 S 375'000 399'999
L 400'000 449'999 Выход/сдвиг 750'000 999'999 3
Выход/сдвиг ООО'ООО 499'999 4 Е 750'000 874'999
'Е ООО'ООО 249'999 R 87
862'500 874'999
Е Конец
ООО'ООО 124'999




4. Кодирование является динамической процедурой, ориентиро-
ванной на блоки. Сам процесс кодирования может быть допол-
нен скользящими окнами, содержащими текущий словарь фраз
и Look-ahead буфером.


Фраза Буфер Look-ahead
F A|C|H|H|O|C|H|S|C|H|U|L|E ? А С Н|В|Е R Е
lF|U|LlD А
21
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5|4 3



Рис. 6.3. Скользящее окно алгоритма LZ77, соответствую-
щее фразе FACH.

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


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


Рис. 6.4. Структура указателей.
82 Глава 6. Сжатие данных


Буфер Look-ahead
Фраза
I !N'F[6iRiMJA r f]!lON-NdT-MATTRR-'NOR-'ENFROY:

JiilillEElL
] jTj˜l2[l I j IOi 4 [ Й [ 7 fft [ Д' pt" J '2 Г I
1I5.7.TI


Фраза ^ Look-ahead_
|
:
j IO'N -"N]OJX! -

|I5,4.N|


fyrfep Look-ahead^
)t-NOR-ENERGY rzi
1iji11iTTi] 1111 Oj 9 p J 7 Щ 5 VJ2˜T˜4 Д"б[7'|
110.1.T1


Фраза Буфер Look-ahead

1 ' З Д . 4 5 I6 7 ,
!
15.14 13j 12 II 1 0 . 9 8 7 6 5 4 1 J | 2 I 1
I4.1.M)


Фраза Буфер Look-ahead
А ? О Ж ? Г - Л Й IQI ^ENERGY
l5;l4}i?|T2TTi]7o|T[8
112
[П.2.Т]


Фраза Буфер Look-ahead
ERGY
мГХГтЩрИ -"Шо 1 TUM1A1T]?HRPNTOTRI-.IE
2 1 I 2|3'4.. 5 [ 6 | 7 |
I 5 i l 4 1.1 I 2 J I I 1 0 9 | 8 7 6 5 4 | 3
[O,O,EJ Нулевая фраза


Фраза Буфер Look-ahead
f ]E |RGY
АТТЛОЩ - f RI -"N O7
i
6 [S [4
[0,0,R] Нулевая фраза



Р и с . 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. Введение
В главе 4 были рассмотрены два связанных источника информации.
Были введены такие ключевые понятия как совместные, взаимные
и условные информации пар событий (символов) для связанных ис-
точников. На их основе мы пришли к фундаментальным понятиям
информации - совместной, взаимной и условной энтропии. (См. табл.
4.3). Там же было отмечено, что совместная и условная энтропии
имеют аналоги в теории вероятностей и определяются как матема-
тические ожидания совместных и условных информации всех пар
событий двух источников.

Передатчик Приемник

Источник
Источник
К
X




Рис. 7.1. Модель передачи.

Мы продолжим эти рассуждения, уделив основное внимание вза-
имной энтропии. Для описания каналов передачи информации ис-
пользуем концепцию двух связанных источников. Оказывается, что
с помощью понятий, введенных в главе 4, удается полностью описать
процесс передачи информации по каналам без памяти. В результа-
те, мы оценим возможность передачи информации по каналу, т.е.
пропускную способность канала.
В Шенноновской модели канала связи информация одного ис-
точника (передатчика) передается по каналу приемнику и выдается
потребителю. Для потребителя имеет значение только выход прием-
ника, т.е. приемник сам является источником информации, поэтому,
7.2. Двоичный симметричный канал

модель связанных источников полностью применима к цепочке Пе-

<< Предыдущая

стр. 14
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>