Изменения
Нет описания правки
|definition=
'''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], т.е. то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.
}}
*<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования.
'''struct''' Segment:
'''double''' left
right = newRight
'''return''' (left + right) / 2
'''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи.
** <math>\mathtt{character}\,</math> {{---}} значение символа.
'''struct''' Segment:
'''double''' left
'''for''' i = 0 '''to''' n - 1
'''for''' j = 0 '''to''' m - 1
'''if''' code <tex>\small{~\geqslant~}</tex>= segment[j].left '''and''' code < segment[j].right
s += segment[j].character
code = (code – segment[j].left) / (segment[j].right – segment[j].left)
'''break'''
'''return''' s
'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
Число бит в закодированном тексте:
<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...\ldots p_n)</tex>
}}
