Изменения

Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], т.е. то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).}}

# Повторим пункт <tex>(3) </tex> до конца входного потока.

=== Псевдокод ===

*<texmath>\mathtt{s}\,</texmath> {{---}} текст, подаваемый на вход;*<math>\mathtt{n}\,</math> {{---}} длина исходного текста;*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте; *<math>\mathtt{Segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:**<math>\mathtt{left}\,</math> {{---}} левая граница подотрезка;**<math>\mathtt{right}\,</math> {{---}} правая граница подотрезка;*<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования.

<tex> '''struct''' Segment: '''double''' left</tex>, <tex> '''double''' right</tex> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования

<tex> '''Segment'''[m] defineSegments(letters: '''char'''[m], probability: '''double'''[m]): '''Segment'''[m] segment '''double''' l = 0 '''for''' i = 0 '''to''' m - 1 segment[letters[i]].left</tex>, <tex>= l segment[letters[i]].right</tex> {{---}} границы подотрезка отрезка <tex>= l + probability[i] l = segment[letters[0; 1)</tex>, соответствующего символу <tex>i</tex>]].right '''return''' segment

'''double''' ArithmeticCoding arithmeticCoding(letters: '''char'''[m], probability: '''double'''[m], s: '''stringchar'''[n]): '''Segment'''[m] segment = defineSegments(letters, probability) '''double''' left = 0 '''double''' right = 1 '''for''' i = 0 '''to''' length(s)n -1 '''char''' symb = s[i] '''double''' newRight = left + (right - left) * segment[symb].right '''double''' newLeft = left + (right - left) * segment[symb].left

# Повторим пункты <tex>1</tex>{{---}}<tex>2 </tex> до тех пор, пока не получим ответ. === Псевдокод === *<math>\mathtt{code}\,</math> {{---}} вещественное число, подаваемое на вход;*<math>\mathtt{n}\,</math> {{---}} длина восстанавливаемого текста;*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте; *<math>\mathtt{segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:** <math>\mathtt{left}\,</math> {{---}} левая граница подотрезка;** <math>\mathtt{right}\,</math> {{---}} правая граница подотрезка;** <math>\mathtt{character}\,</math>{{---}} значение символа.  '''struct''' Segment: '''double''' left '''double''' right '''char''' character  '''Segment'''[m] defineSegments(letters: '''char'''[n], probability: '''double'''[n]): '''Segment'''[m] segment '''double''' l = 0 '''for''' i = 0 '''to''' m - 1 segment[i].left = l segment[i].right = l + probability[i] segment[i].character = letters[i] l = segment[i].right '''return''' segment  '''string''' ArithmeticCoding arithmeticDecoding(letters: '''char'''[m], probability: '''double'''[m], code: '''double''', n: '''int'''): '''Segment'''[m] segment = defineSegments(letters, probability) '''string''' s = "" '''for''' i = 1 0 '''to''' lengthn - 1 '''for''' j = 1 0 '''to''' nm - 1 '''if''' code <tex>\small{~\geqslant~}</tex>= segment[j].left '''and''' code < segment[j].right s += s + segment[j].character

'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.

Для оптимизации размера кода необходимо выбрать '''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из окончательного диапазона -за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>\dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его <tex>m</tex> подотрезков, кратных по длине <tex>n</tex>, а всего итераций <tex>n</tex>, в конечном результате знаменатель дроби не превысит <tex>n^{n}</tex>, а поскольку сумма всех вероятностей встречи символов равна <tex>1</tex>, содержащее наименьшее количество знаков полученная дробь будет находиться в двоичной записипромежутке <tex>[0; 1)</tex>.

Рассмотрим в качестве примера строку <tex>abacaba</tex>:

||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...\ldots p_n)</tex>