Изменения

{{Определение|definition= '''Арифметическое кодирование (Arithmetic coding) ''' {{---}} алгоритм сжатия информации без потерь.

Данный метод (как и алгоритм Хаффмана) является энтропийным т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>–log_2-log_2(p(a))</tex>, следовательно при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки).== Принцип действия ===== Кодирование ===Алгоритму передаются текст для кодирования и список частот встречаемости символов.# Рассмотрим отрезок <tex>[0; 1)</tex> на координатной прямой. # Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Этот отрезок разделим на части, пропорциональные частотам встречаемости символов.# Повторим пункт (3) до конца входного потока.# Выберем любое число из получившегося отрезка (предпочтительно степень двойки). Это и будет результат арифметического кодирования.<code> left = 0 right = 1 while !eof read(symb) newRight = left + (right - left) * segment[symb].right <span style="color:green"> //segment[symb] — подотрезок отрезка [0; 1), соответствующий символу symb </span> newLeft = left + (right - left) * segment[symb].left left = newLeft right = newRight ans = (left + right) / 2</code>=== Декодирование ===Алгоритм по вещественному числу восстанавливает исходный текст.# Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.# Нормируем подотрезок и вещественное число.# Повторим п. (1—2) до тех пор, пока не получим ответ (до конца файла).<code> do for i = 1 to n if code >= segment[i].left && code < segment[i].right write(segment[i].character) code = (code – segment[i].left) / (segment[i].right – segment[i].left) break while (segment[i].character != eof)</code>