48
правок
Изменения
Реализация для дробей
'''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки). Однако, несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>\dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число.
== Принцип действия ==
*<math>\mathtt{code}\,</math> {{---}} вещественное число, подаваемое на вход;
*<math>\mathtt{lengthn}\,</math> {{---}} длина восстанавливаемого текста;
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
segment[i].character = letters[i]
'''string''' arithmeticDecoding(code: '''double''', lengthn: '''int'''):
defineSegments(letters, probability)
'''string''' s = ""
'''for''' i = 0 '''to''' length n - 1
'''for''' j = 0 '''to''' m - 1
'''if''' code >= segment[j].left '''and''' code < segment[j].right ''<font color=green>// segment {{---}} массив, заполненный в результате выполнения метода defineSegments</font>''
'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>\dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде дроби, числитель которой представляет количество использований символа в тексте, знаменатель {{---}} длину <tex>n</tex> исходного текста. Поскольку в каждой итерации будет переход из текущего отрезка в один из его <tex>m</tex> подотрезков, кратных по длине <tex>n</tex>, а всего итераций <tex>n</tex>, в конечном результате в качестве знаменателя дроби будет <tex>n^{n}</tex>, а числитель можно найти, рассматривая отрезок <tex>[0; n^{n})</tex> на первой итерации.
== Пример работы ==
Рассмотрим в качестве примера строку <tex>abacaba</tex>:
