48
правок
Изменения
Нет описания правки
=== Псевдокод ===
*<tex>s</tex> {{---}} текст, подаваемый на вход*<tex>left</tex>, <tex>right</tex> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования*<tex>segment</tex> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:** <tex>left</tex> {{---}} левая граница подотрезка** <tex>right</tex> {{---}} правая граница подотрезка
left = 0
right = 1
=== Псевдокод ===
*<tex>code</tex> {{---}} вещественное число, подаваемое на вход *<tex>length</tex> {{---}} длина восстанавливаемого текста *<tex>segment</tex> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:** <tex>left</tex> {{---}} левая граница подотрезка** <tex>right</tex> {{---}} правая граница подотрезка** <tex>character</tex> {{---}} значение символа
<code>
'''string''' ArithmeticDecoding (code: '''double'''):
s = ""
'''for''' i = 1 '''to''' length
== Пример работы ==
Рассмотрим в качестве примера строку <tex>abacaba</tex>:
=== Кодирование ===
{|class="wikitable"
||proof=Если Введём следующие обозначения: <tex>l</tex> {{---}} длина текста; <tex>n</tex> {{---}} размер алфавита; <tex>f_i</tex> {{---}} частота встречаемости символа; <tex>p_i</tex> {{---}} вероятность вхождения символа, тогда размер ; Размер сообщения <tex>L</tex> можно найти по формуле: <tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex>
Число бит в закодированном тексте: <tex>\log_2 L = \sum\limits_{i=1}^n f_i\cdot \log_2 p_i = l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -l \cdot H(p_1...p_n)</tex>
