48
правок
Изменения
м
Алгоритму На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.
Ккодировщику Кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
Малые правки стилистики речи и пунктуации
'''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
Данный метод (, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]]) , является энтропийным , т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически , символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно , при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки).
== Принцип действия ==
=== Кодирование ===
# Рассмотрим отрезок <tex>[0; 1)</tex> на координатной прямой.
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Этот Разделим этот отрезок разделим на части, пропорциональные частотам встречаемости символов.
# Повторим пункт (3) до конца входного потока.
# Выберем любое число из получившегося отрезка. Это , которое и будет результат результатом арифметического кодирования.
left = 0
# Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
# Нормируем подотрезок и вещественное число.
# Повторим п. (пункты 1{{---}}2) до тех пор, пока не получим ответ (до конца файла).
<code>
do
</code>
=== Замечание ===
Для оптимизации размера кода необходимо выбрать из окончательного диапазона число, содержащее наименьшее количество знаков в двоичной записи.
