Тема: Арифметическое кодирование.
План лекции.
1. Описание алгоритма арифметического кодирования.
2. Алгоритм декодирования арифметического кода.
Описание алгоритма арифметического кодирования
Как и в алгоритме Хаффмана, все начинается с таблицы элементов и соответствующих вероятностей. Допустим, входной алфавит состоит всего из трех элементов: a1, a2 и a3, и при этом:
,
,
.
Предположим также, что нам надо закодировать последовательность a1, a1, a2, a3 .
Разобьем полуинтервал [0, 1) на три части в соответствии с вероятностями элементов:
Элементу a1 будет соответствовать диапазон [0, 1/2); элементу a2 диапазон [1/2, 1/2 + 1/3), а элементу a3 – диапазон [1/2 +1/3 , 1).
Первый элемент сжимаемого файла равен а1. Выберем полуинтервал, соответствующий ему [0, 1/2 ):
Разобьем его таким же образом на три части:
Поскольку второй элемент сжимаемой последовательности тоже равен a1, снова выбираем самый нижний диапазон (точнее, теперь уже поддиапазон [0, 1/4)):
Аналогичным образом, продолжая процесс для оставшихся элементов входного файла а2 и а3, получаем такой рисунок:
Последним полученным диапазоном будет [5/24, 1/4).
Алгоритм декодирования арифметического кода
Любоечисло из диапазона [5/24, 1/4) (например, 0,22) однозначно описывает весьвходной файл. Зная вероятности появления элементов, декодер может правильно разбить диапазон [0, 1) на три части и определить, что число 0,22 находится в поддиапазоне [0, 1/2). В свою очередь, это означает, что первый элемент декодированного файла равена1. Затем декодер разобьет диапазон [0, 1/2) на три части и определит, что число 0,22 находится в поддиапазоне [0, 1/4), следовательно, следующий элемент выходного файла – снова а1 и т. д.
|
|
|
Поскольку декодер не можетточно определить,когда следует закончить работу (процесс при желании можно продолжать бесконечно), придется либо явно прописать во входном файле количество элементов, подлежащих декодированию, либо ввести специальный символ «конец файла», встретив который, распаковщик остановится.
Хотя для описания сжимаемого файла годится любое число конечного диапазона (0.22, 0.222, 0.222222222222,...), выбирать надо, разумеется, то, которое содержит меньше цифр, поскольку каждая лишняя цифра увеличивает размер выходного файла.
Лекция 9.
Тема: Алгоритмы эффективного кодирования неравновероятных взаимозависимых символов сообщений.
План лекции.
1. Кодирование по методу k-грамм.
2. Недостатки алгоритмов эффективного кодирования.
1. Кодирование по методу k-грамм
Устранение взаимной зависимости символов источника сообщения может быть осуществлено путем укрупнения алфавита исходного источника сообщения. Для этого подлежащие кодированию сообщения последовательно разбиваются на двух-, трех- или n-знаковые сочетания (блоки), вероятности которых известны, а затем эти сочетания кодируются в соответствии с алгоритмами Шеннона-Фано или Хаффмена.
|
|
|
Недостаток этого алгоритма состоит в том, что при его использовании не учитываются связи между символами, входящими в состав соседних сочетаний (блоков).
Этот недостаток может быть устранен кодированием по методу диграмм, триграмм или в общем случае k-грамм. k-граммой называют последовательность из k смежных символов сообщения. При k = 2сочетание смежных знаков называют диграммой, при k = 3– триграммой и т.д.
В процессе кодирования по методу k-грамм производят последовательное непрерывное перемещение k-граммы по сообщению с шагом, равным одному символу. Этот процесс (получение 3-х k-грамм) иллюстрируется рис. 14.1, где xi – символы сообщения.
Рис 14.1. Процесс последовательного непрерывного перемещения k-граммы
по сообщению
Если вероятности появления различных k-грамм известны, то их эффективное кодирование, в частности, может быть выполнено по алгоритмам Шеннона-Фано или Хаффмена. Конкретное значение k выбирается исходя из степени взаимозависимости между символами сообщения и сложности технической реализации кодирующих и декодирующих устройств.
|
|
|
Дата добавления: 2018-05-12; просмотров: 728; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!