Изменения
Биграммная модель
После перестановки операция увеличения веса узлов продолжается дальше. Следующий узел, вес которого будет увеличен алгоритмом, — это новый родитель узла, увеличение веса которого вызвало перестановку.
После перестановки операция увеличения веса узлов продолжается дальше. Следующий узел, вес которого будет увеличен алгоритмом, — это новый родитель узла, увеличение веса которого вызвало перестановку.
== Биграммная модель ==
Существует разновидность алгоритма Хаффмана, использующая контекст. В данном случае размер контекста равен единице (биграммный - два символа, триграммный 0 три и так далее). Жто метод построения префиксного кода для моделей высших порядков, уже не источника без памяти. Он использует результат (предыдущей операции) операции над предыдущей буквой совместно с текущей буквой. Строится на основе [[Цепь Маркова|цепи Маркова]] с глубиной зависимости r = 1.<ref>{{Cite web|url = http://u.cs.biu.ac.il/~tomi/Postscripts/MathComp.pdf|title = Huffman Coding with Non-Sorted Frequencies|author = Shmuel T. Klein and Dana Shapira|work = |date = 2008|publisher = }}</ref>
'''Алгоритм:'''
# Строится таблица в виде квадрата – распределение вероятностей на биграммах. Сразу вычисляется стартовая схема, с помощью которой будет кодироваться только первая буква. Строками в таблице, например, является предыдущая буква, а столбцами текущая.
# Вычисляются вероятности для кодовых деревьев для контекстов.
# По контекстам длины r = 1 строятся остальные кодовые деревья, с помощью которых будут кодироваться все остальные символы (кроме первого).
# Выполняется кодирование, первый символ кодируется согласно стартовой схеме, все последующие – исходя из кодовых деревьев для контекстов (предыдущего символа).
Декодирование выполняется аналогично: из стартовой кодовой схемы получаем первый контекст, а затем переходим к соответствующему кодовому дереву. Более того декодеру необходима таблицу распределения вероятностей.
'''Пример:'''
Допустим, сообщение, которое надо закодировать "abcabcabc". Нам заранее известна таблица частот символов (на основе других данных):
{| class="wikitable"
!
!a
!b
!c
!Сумма
|-
!a
|3/16
|1/16
|1/16
|5/16
|-
!b
|1/8
|1/16
|1/8
|5/16
|-
!c
|1/8
|1/8
|1/8
|6/16
|}
Имеем стартовую схему: (a = 5/16, b = 5/16, c = 6/16). Сортируем по убыванию: (c = 6/16, a = 5/16, b = 5/16) и строим кодовое дерево Хаффмана.
Для контекста «a» имеем:
* p(a / a) = p(a, a) / p(a) = (3/16) / (5/16) = 3/5,
* p(b / a) = p(b, a) / p(a) = (1/16) / (5/16) = 1/5,
* p(c / a) = p(c, a) / p(a) = (1/16) / (5/16) = 1/5.
Для контекста «b» имеем:
* p(a / b) = p(a, b) / p(b) = (1/8) / (5/16) = 2/5,
* p(b / b) = p(b, b) / p(b) = (1/16) / (5/16) = 1/5,
* p(c / b) = p(c, b) / p(b) = (1/8) / (5/16) = 2/5.
Для контекста «c» имеем:
* p(a / c) = p(a, a) / p(c) = (1/8) / (6/16) = 1/3,
* p(b / c) = p(b, a) / p(c) = (1/8) / (6/16) = 1/3,
* p(c / c) = p(c, a) / p(c) = (1/8) / (6/16) = 1/3.
Примечание: здесь p(x, y) не равно p(y, x). Строим кодовые деревья для каждого контекста. Выполняем кодирование и имеем закодированное сообщение: (00, 10, 01, 1, 10, 01, 1, 10, 01).
* 00 – из кода буквы «a» для стартовой схемы,
* 10 – из кода буквы «b» для контекста «a»,
* 01 – из кода буквы «c» для контекста «b»,
* 1 – из кода буквы «a» для контекста «c».
== Переполнение ==
== Переполнение ==