Арифметическое кодирование — различия между версиями
Migan (обсуждение | вклад) (Intro bugfix) |
|||
(не показаны 22 промежуточные версии 7 участников) | |||
Строка 1: | Строка 1: | ||
+ | {{Определение | ||
+ | |definition= | ||
'''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>. | '''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>. | ||
− | Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], | + | Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. |
+ | }} | ||
== Принцип действия == | == Принцип действия == | ||
+ | При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки). | ||
=== Кодирование === | === Кодирование === | ||
На вход алгоритму передаются текст для кодирования и список частот встречаемости символов. | На вход алгоритму передаются текст для кодирования и список частот встречаемости символов. | ||
Строка 8: | Строка 12: | ||
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления. | # Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления. | ||
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов. | # Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов. | ||
− | # Повторим пункт (3) до конца входного потока. | + | # Повторим пункт <tex>(3)</tex> до конца входного потока. |
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования. | # Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования. | ||
Строка 14: | Строка 18: | ||
*<math>\mathtt{s}\,</math> {{---}} текст, подаваемый на вход; | *<math>\mathtt{s}\,</math> {{---}} текст, подаваемый на вход; | ||
− | *<math>\mathtt{n}\,</math> {{---}} мощность алфавита исходного текста; | + | *<math>\mathtt{n}\,</math> {{---}} длина исходного текста; |
− | *<math>\mathtt{letters[ | + | *<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста; |
− | *<math>\mathtt{probability[ | + | *<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста; |
− | *<math>\mathtt{ | + | *<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте; |
+ | *<math>\mathtt{Segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля: | ||
**<math>\mathtt{left}\,</math> {{---}} левая граница подотрезка; | **<math>\mathtt{left}\,</math> {{---}} левая граница подотрезка; | ||
**<math>\mathtt{right}\,</math> {{---}} правая граница подотрезка; | **<math>\mathtt{right}\,</math> {{---}} правая граница подотрезка; | ||
*<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования. | *<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования. | ||
− | + | '''struct''' Segment: | |
− | '''struct''' | ||
'''double''' left | '''double''' left | ||
'''double''' right | '''double''' right | ||
− | |||
− | ''' | + | '''Segment'''[m] defineSegments(letters: '''char'''[m], probability: '''double'''[m]): |
+ | '''Segment'''[m] segment | ||
'''double''' l = 0 | '''double''' l = 0 | ||
− | '''for''' i = | + | '''for''' i = 0 '''to''' m - 1 |
segment[letters[i]].left = l | segment[letters[i]].left = l | ||
segment[letters[i]].right = l + probability[i] | segment[letters[i]].right = l + probability[i] | ||
+ | l = segment[letters[i]].right | ||
+ | '''return''' segment | ||
− | '''double''' | + | '''double''' arithmeticCoding(letters: '''char'''[m], probability: '''double'''[m], s: '''char'''[n]): |
+ | '''Segment'''[m] segment = defineSegments(letters, probability) | ||
'''double''' left = 0 | '''double''' left = 0 | ||
'''double''' right = 1 | '''double''' right = 1 | ||
− | '''for''' i = 0 '''to''' | + | '''for''' i = 0 '''to''' n - 1 |
'''char''' symb = s[i] | '''char''' symb = s[i] | ||
'''double''' newRight = left + (right - left) * segment[symb].right | '''double''' newRight = left + (right - left) * segment[symb].right | ||
Строка 44: | Строка 51: | ||
right = newRight | right = newRight | ||
'''return''' (left + right) / 2 | '''return''' (left + right) / 2 | ||
− | |||
'''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи. | '''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи. | ||
Строка 52: | Строка 58: | ||
# Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ. | # Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ. | ||
# Нормируем подотрезок и вещественное число. | # Нормируем подотрезок и вещественное число. | ||
− | # Повторим пункты 1{{---}}2 до тех пор, пока не получим ответ. | + | # Повторим пункты <tex>1</tex>{{---}}<tex>2</tex> до тех пор, пока не получим ответ. |
=== Псевдокод === | === Псевдокод === | ||
*<math>\mathtt{code}\,</math> {{---}} вещественное число, подаваемое на вход; | *<math>\mathtt{code}\,</math> {{---}} вещественное число, подаваемое на вход; | ||
− | *<math>\mathtt{ | + | *<math>\mathtt{n}\,</math> {{---}} длина восстанавливаемого текста; |
− | *<math>\mathtt{ | + | *<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста; |
− | *<math>\mathtt{letters[ | + | *<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста; |
− | *<math>\mathtt{probability[ | + | *<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте; |
*<math>\mathtt{segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля: | *<math>\mathtt{segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля: | ||
** <math>\mathtt{left}\,</math> {{---}} левая граница подотрезка; | ** <math>\mathtt{left}\,</math> {{---}} левая граница подотрезка; | ||
Строка 66: | Строка 72: | ||
** <math>\mathtt{character}\,</math> {{---}} значение символа. | ** <math>\mathtt{character}\,</math> {{---}} значение символа. | ||
− | + | '''struct''' Segment: | |
− | '''struct''' | ||
'''double''' left | '''double''' left | ||
'''double''' right | '''double''' right | ||
'''char''' character | '''char''' character | ||
− | |||
− | ''' | + | '''Segment'''[m] defineSegments(letters: '''char'''[n], probability: '''double'''[n]): |
+ | '''Segment'''[m] segment | ||
'''double''' l = 0 | '''double''' l = 0 | ||
− | '''for''' i = | + | '''for''' i = 0 '''to''' m - 1 |
segment[i].left = l | segment[i].left = l | ||
segment[i].right = l + probability[i] | segment[i].right = l + probability[i] | ||
segment[i].character = letters[i] | segment[i].character = letters[i] | ||
+ | l = segment[i].right | ||
+ | '''return''' segment | ||
− | '''string''' | + | '''string''' arithmeticDecoding(letters: '''char'''[m], probability: '''double'''[m], code: '''double''', n: '''int'''): |
+ | '''Segment'''[m] segment = defineSegments(letters, probability) | ||
'''string''' s = "" | '''string''' s = "" | ||
− | '''for''' i = | + | '''for''' i = 0 '''to''' n - 1 |
− | '''for''' j = | + | '''for''' j = 0 '''to''' m - 1 |
− | '''if''' code > | + | '''if''' code<tex>\small{~\geqslant~}</tex>segment[j].left '''and''' code < segment[j].right |
− | s = | + | s += segment[j].character |
code = (code – segment[j].left) / (segment[j].right – segment[j].left) | code = (code – segment[j].left) / (segment[j].right – segment[j].left) | ||
'''break''' | '''break''' | ||
'''return''' s | '''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>. | ||
== Пример работы == | == Пример работы == | ||
Строка 176: | Строка 185: | ||
||proof=Введём следующие обозначения: | ||proof=Введём следующие обозначения: | ||
− | <tex>l</tex> {{---}} длина текста | + | *<tex>l</tex> {{---}} длина текста, |
− | <tex>n</tex> {{---}} размер алфавита | + | *<tex>n</tex> {{---}} размер алфавита, |
− | <tex>f_i</tex> {{---}} частота встречаемости символа | + | *<tex>f_i</tex> {{---}} частота встречаемости символа, |
− | <tex>p_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>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 | + | Число бит в закодированном тексте: |
+ | <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> | ||
}} | }} | ||
Версия 21:08, 31 октября 2019
Определение: |
Арифметическое кодирование (англ. Arithmetic coding) — алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка алгоритм Хаффмана, является энтропийным, то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. | . Данный метод, как и
Содержание
Принцип действия
При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу
с вероятностью появления допустимо ставить в соответствие код длины , следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).Кодирование
На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.
- Рассмотрим отрезок на координатной прямой.
- Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
- Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
- Повторим пункт до конца входного потока.
- Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.
Псевдокод
- — текст, подаваемый на вход;
- — длина исходного текста;
- — мощность алфавита исходного текста;
- — массив символов, составляющих алфавит исходного текста;
- — массив вероятностей обнаружения символа в тексте;
- — левая граница подотрезка;
- — правая граница подотрезка;
— структура, задающая подотрезок отрезка , соответствующего конкретному символу на основе частотного анализа. Имеет поля:
- , — границы отрезка, содержащего возможный результат арифметического кодирования.
struct Segment: double left double right
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 = 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 double newLeft = left + (right - left) * segment[symb].left left = newLeft right = newRight return (left + right) / 2
Замечание: для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона
число, содержащее наименьшее количество знаков в двоичной записи.Декодирование
Алгоритм по вещественному числу восстанавливает исходный текст.
- Выберем на отрезке , разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
- Нормируем подотрезок и вещественное число.
- Повторим пункты — до тех пор, пока не получим ответ.
Псевдокод
- — вещественное число, подаваемое на вход;
- — длина восстанавливаемого текста;
- — мощность алфавита исходного текста;
- — массив символов, составляющих алфавит исходного текста;
- — массив вероятностей обнаружения символа в тексте;
- — левая граница подотрезка;
- — правая граница подотрезка;
- — значение символа.
— структура, задающая подотрезок отрезка , соответствующего конкретному символу на основе частотного анализа. Имеет поля:
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 arithmeticDecoding(letters: char[m], probability: double[m], code: double, n: int):
Segment[m] segment = defineSegments(letters, probability)
string s = ""
for i = 0 to n - 1
for j = 0 to m - 1
if code
segment[j].left and code < segment[j].right
s += segment[j].character
code = (code – segment[j].left) / (segment[j].right – segment[j].left)
break
return s
Замечание: кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
Замечание: Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера — поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например,
), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его подотрезков, кратных по длине , а всего итераций , в конечном результате знаменатель дроби не превысит , а поскольку сумма всех вероятностей встречи символов равна , полученная дробь будет находиться в промежутке .Пример работы
Рассмотрим в качестве примера строку
:Кодирование
Символ | Частота появления |
---|---|
| |
| |
|
Считанный символ | Левая граница отрезка | Правая граница отрезка |
---|---|---|
| ||
| ||
| ||
| ||
| ||
| ||
| ||
|
Код:
Декодирование
Код:
Декодируемый символ | Код |
---|---|
| |
| |
| |
| |
| |
| |
|
Замечание: при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.
Декодирование (второй способ)
Код:
Декодируемый символ | Границы отрезка | |||
---|---|---|---|---|
| ||||
| ||||
| ||||
| ||||
| ||||
| ||||
|
Оценка длины кодового слова
Теорема: |
При арифметическом кодировании длина кодового слова не превышает энтропии исходного текста. |
Доказательство: |
Введём следующие обозначения:
Размер сообщения можно найти по формуле:Число бит в закодированном тексте: |