Изменения

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

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

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

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

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

# Выполняется кодирование, первый символ кодируется согласно стартовой схеме, все последующие – исходя из кодовых деревьев для контекстов (предыдущего символа).

# Выполняется кодирование, первый символ кодируется согласно стартовой схеме, все последующие — исходя из кодовых деревьев для контекстов (предыдущего символа).

Декодирование выполняется аналогично: из стартовой кодовой схемы получаем первый контекст, а затем переходим к соответствующему кодовому дереву. Более того декодеру необходима таблицу распределения вероятностей.

Декодирование выполняется аналогично: из стартовой кодовой схемы получаем первый контекст, а затем переходим к соответствующему кодовому дереву. Более того, декодеру необходима таблица распределения вероятностей.

'''Пример:'''

'''Пример:'''

Допустим, сообщение, которое надо закодировать "abcabcabc". Нам заранее известна таблица частот символов (на основе других данных):

Допустим, сообщение, которое надо закодировать '''«abcabcabc»'''. Нам заранее известна таблица частот символов (на основе других данных, например, статистических данных по словарю):

{| class="wikitable"

{| class="wikitable" style="text-align:center"

!

!

!a

!''a''

!b

!''b''

!c

!''c''

!Сумма

!Сумма

|-

|-

!a

!''a''

|3/16

|<math>\tfrac{3}{16}</math>

|1/16

|<math>\tfrac{1}{16}</math>

|1/16

|<math>\tfrac{1}{16}</math>

|5/16

|<math>\tfrac{5}{16}</math>

|-

|-

!b

!''b''

|1/8

|<math>\tfrac{1}{8}</math>

|1/16

|<math>\tfrac{1}{16}</math>

|1/8

|<math>\tfrac{1}{8}</math>

|5/16

|<math>\tfrac{5}{16}</math>

|-

|-

!c

!''c''

|1/8

|<math>\tfrac{1}{8}</math>

|1/8

|<math>\tfrac{1}{8}</math>

|1/8

|<math>\tfrac{1}{8}</math>

|6/16

|<math>\tfrac{6}{16}</math>

|}

|}

Имеем стартовую схему: (a = 5/16, b = 5/16, c = 6/16). Сортируем по убыванию: (c = 6/16, a = 5/16, b = 5/16) и строим кодовое дерево Хаффмана.

Имеем стартовую схему: <math>(a = \tfrac{5}{16}, b = \tfrac{5}{16}, c = \tfrac{6}{16})</math>. Сортируем по убыванию: <math>(c = \tfrac{6}{16}, a = \tfrac{5}{16}, b = \tfrac{5}{16})</math> и строим кодовое дерево Хаффмана.

Для контекста «a» имеем:

Для контекста «'''a'''» имеем:

* p(a / a) = p(a, a) / p(a) = (3/16) / (5/16) = 3/5,

* <math>p(a / a) = p(a, a) / p(a) = \tfrac{3}{16} \div \tfrac{5}{16} = \tfrac{3}{5}</math>,

* p(b / a) = p(b, a) / p(a) = (1/16) / (5/16) = 1/5,

* <math>p(b / a) = p(b, a) / p(a) = \tfrac{1}{16} \div \tfrac{5}{16} = \tfrac{1}{5}</math>,

* p(c / a) = p(c, a) / p(a) = (1/16) / (5/16) = 1/5.

* <math>p(c / a) = p(c, a) / p(a) = \tfrac{1}{16} \div \tfrac{5}{16} = \tfrac{1}{5}</math>.

Для контекста «b» имеем:

Для контекста «'''b'''» имеем:

* p(a / b) = p(a, b) / p(b) = (1/8) / (5/16) = 2/5,

* <math>p(a / b) = p(a, b) / p(b) = \tfrac{1}{8} \div \tfrac{5}{16} = \tfrac{2}{5}</math>,

* p(b / b) = p(b, b) / p(b) = (1/16) / (5/16) = 1/5,

* <math>p(b / b) = p(b, b) / p(b) = \tfrac{1}{16} \div \tfrac{5}{16} = \tfrac{1}{5}</math>,

* p(c / b) = p(c, b) / p(b) = (1/8) / (5/16) = 2/5.

* <math>p(c / b) = p(c, b) / p(b) = \tfrac{1}{8} \div \tfrac{5}{16} = \tfrac{2}{5}</math>.

Для контекста «c» имеем:

Для контекста «'''c'''» имеем:

* p(a / c) = p(a, a) / p(c) = (1/8) / (6/16) = 1/3,

* <math>p(a / c) = p(a, a) / p(c) = \tfrac{1}{8} \div \tfrac{6}{16} = \tfrac{1}{3}</math>,

* p(b / c) = p(b, a) / p(c) = (1/8) / (6/16) = 1/3,

* <math>p(b / c) = p(b, a) / p(c) = \tfrac{1}{8} \div \tfrac{6}{16} = \tfrac{1}{3}</math>,

* p(c / c) = p(c, a) / p(c) = (1/8) / (6/16) = 1/3.

* <math>p(c / c) = p(c, a) / p(c) = \tfrac{1}{8} \div \tfrac{6}{16} = \tfrac{1}{3}</math>.

Примечание: здесь p(x, y) не равно p(y, x). Строим кодовые деревья для каждого контекста. Выполняем кодирование и имеем закодированное сообщение: (00, 10, 01, 1, 10, 01, 1, 10, 01).

''Примечание: здесь '''p(x, y)''' не равно '''p(y, x)'''.''

* 00 – из кода буквы «a» для стартовой схемы,

 

* 10 – из кода буквы «b» для контекста «a»,

Строим кодовые деревья для каждого контекста. Выполняем кодирование и имеем закодированное сообщение: (00, 10, 01, 1, 10, 01, 1, 10, 01).

* 01 – из кода буквы «c» для контекста «b»,

* 00 — из кода буквы '''«a»''' для стартовой схемы,

* 1 – из кода буквы «a» для контекста «c».

* 10 — из кода буквы '''«b»''' для контекста '''«a»''',

* 01 — из кода буквы '''«c»''' для контекста '''«b»''',

* 1 — из кода буквы '''«a»''' для контекста '''«c»'''.

== Переполнение ==

== Переполнение ==