Изменения
Нет описания правки
{{Определение
|definition=
'''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], т.е. то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки). Однако, несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>\dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число.
== Принцип действия ==
При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).
=== Кодирование ===
На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
# Повторим пункт <tex>(3) </tex> до конца входного потока.
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.
*<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования.
'''struct''' Segment:
'''double''' left
'''double''' right
'''voidSegment''' [m] defineSegments(letters: '''char'''[m], probability: '''double'''[m]):
'''Segment'''[m] segment
'''double''' l = 0
segment[letters[i]].left = l
segment[letters[i]].right = l + probability[i]
l = segment[letters[i]].right
'''return''' segment
'''double''' arithmeticCoding(letters: '''char'''[m], probability: '''double'''[m], s: '''char'''[n]): '''Segment'''[m] segment = defineSegments(letters, probability)
'''double''' left = 0
'''double''' right = 1
'''for''' i = 0 '''to''' n - 1
'''char''' symb = s[i]
'''double''' newRight = left + (right - left) * segment[symb].right ''<font color=green>// segment {{---}} массив, заполненный в результате выполнения метода defineSegments</font>''
'''double''' newLeft = left + (right - left) * segment[symb].left
left = newLeft
right = newRight
'''return''' (left + right) / 2
'''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи.
# Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
# Нормируем подотрезок и вещественное число.
# Повторим пункты <tex>1</tex>{{---}}<tex>2 </tex> до тех пор, пока не получим ответ.
=== Псевдокод ===
*<math>\mathtt{code}\,</math> {{---}} вещественное число, подаваемое на вход;
*<math>\mathtt{lengthn}\,</math> {{---}} длина восстанавливаемого текста;
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
** <math>\mathtt{character}\,</math> {{---}} значение символа.
'''struct''' Segment:
'''double''' left
'''char''' character
'''voidSegment''' [m] defineSegments(letters: '''char'''[n], probability: '''double'''[n]): '''Segment''' segment[m]segment
'''double''' l = 0
'''for''' i = 0 '''to''' m - 1
segment[i].right = l + probability[i]
segment[i].character = letters[i]
l = segment[i].right
'''return''' segment
'''string''' arithmeticDecoding(letters: '''char'''[m], probability: '''double'''[m], code: '''double''', lengthn: '''int'''): '''Segment'''[m] segment = defineSegments(letters, probability)
'''string''' s = ""
'''for''' i = 0 '''to''' length n - 1
'''for''' j = 0 '''to''' m - 1
'''if''' code <tex>\small{~\geqslant~}</tex>= segment[j].left '''and''' code < segment[j].right ''<font color=green>// segment {{---}} массив, заполненный в результате выполнения метода defineSegments</font>''
s += segment[j].character
code = (code – segment[j].left) / (segment[j].right – segment[j].left)
'''break'''
'''return''' s
'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
'''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <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>.
== Пример работы ==
||proof=Введём следующие обозначения:
*<tex>l</tex> {{---}} длина текста;,*<tex>n</tex> {{---}} размер алфавита;,*<tex>f_i</tex> {{---}} частота встречаемости символа;,
*<tex>p_i</tex> {{---}} вероятность вхождения символа.
Размер сообщения <tex>L</tex> можно найти по формуле:
Число бит в закодированном тексте:
}}
