Изменения

== Биграммная модель ==

== Биграммная модель ==

Существует разновидность алгоритма Хаффмана, использующая контекст. В данном случае размер контекста равен единице (биграммный — два символа, триграммный — три и так далее). Жто метод построения префиксного кода для моделей высших порядков, уже не источника без памяти. Он использует результат (предыдущей операции) операции над предыдущей буквой совместно с текущей буквой. Строится на основе [[Цепь Маркова|цепи Маркова]] с глубиной зависимости 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.<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 строятся остальные кодовые деревья, с помощью которых будут кодироваться все остальные символы (кроме первого).

# По контекстам длины r = 1 строятся остальные кодовые деревья, с помощью которых будут кодироваться все остальные символы (кроме первого).