Арифметическое кодирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод)
Строка 13: Строка 13:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
<tex>s</tex> {{---}} текст, подаваемый на вход
+
*<tex>s</tex> {{---}} текст, подаваемый на вход
 +
*<tex>left</tex>, <tex>right</tex> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования
 +
*<tex>segment</tex> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
 +
** <tex>left</tex> {{---}} левая граница подотрезка
 +
** <tex>right</tex> {{---}} правая граница подотрезка
  
<tex>left</tex>, <tex>right</tex> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования
+
  '''double''' ArithmeticCoding(s: '''string'''):
 
 
<tex>segment</tex> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
 
* <tex>left</tex> {{---}} левая граница подотрезка
 
* <tex>right</tex> {{---}} правая граница подотрезка
 
 
 
  '''double''' ArithmeticCoding (s: '''string'''):
 
 
     left = 0
 
     left = 0
 
     right = 1
 
     right = 1
Строка 40: Строка 38:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
<tex>code</tex> {{---}} вещественное число, подаваемое на вход
+
*<tex>code</tex> {{---}} вещественное число, подаваемое на вход
 
+
*<tex>length</tex> {{---}} длина восстанавливаемого текста
<tex>length</tex> {{---}} длина восстанавливаемого текста
+
*<tex>segment</tex> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
 
+
** <tex>left</tex> {{---}} левая граница подотрезка
<tex>segment</tex> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
+
** <tex>right</tex> {{---}} правая граница подотрезка
* <tex>left</tex> {{---}} левая граница подотрезка
+
** <tex>character</tex> {{---}} значение символа
* <tex>right</tex> {{---}} правая граница подотрезка
 
* <tex>character</tex> {{---}} значение символа
 
  
 
<code>
 
<code>
  '''string''' ArithmeticDecoding (code: '''double'''):
+
  '''string''' ArithmeticDecoding(code: '''double'''):
 
     s = ""
 
     s = ""
 
     '''for''' i = 1 '''to''' length
 
     '''for''' i = 1 '''to''' length
Строка 66: Строка 62:
  
 
== Пример работы ==
 
== Пример работы ==
Рассмотрим в качестве примера строку <tex>abacaba</tex>
+
Рассмотрим в качестве примера строку <tex>abacaba</tex>:
 
=== Кодирование ===
 
=== Кодирование ===
 
{|class="wikitable"
 
{|class="wikitable"
Строка 147: Строка 143:
  
  
||proof=Если <tex>l</tex> {{---}} длина текста; <tex>n</tex> {{---}} размер алфавита; <tex>f_i</tex> {{---}} частота встречаемости символа; <tex>p_i</tex> {{---}} вероятность вхождения символа, тогда размер сообщения <tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</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...p_n)</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...p_n)</tex>

Версия 17:36, 17 июня 2016

Арифметическое кодирование (англ. Arithmetic coding) — алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка [math][0; 1)[/math]. Данный метод, как и алгоритм Хаффмана, является энтропийным, т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу [math]a[/math] с вероятностью появления [math]p(a)[/math] допустимо ставить в соответствие код длины [math]-\log_2 p(a)[/math], следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).

Принцип действия

Кодирование

На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.

  1. Рассмотрим отрезок [math][0; 1)[/math] на координатной прямой.
  2. Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
  3. Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
  4. Повторим пункт (3) до конца входного потока.
  5. Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.

Псевдокод

  • [math]s[/math] — текст, подаваемый на вход
  • [math]left[/math], [math]right[/math] — границы отрезка, содержащего возможный результат арифметического кодирования
  • [math]segment[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math], соответствующего конкретному символу на основе частотного анализа. Имеет поля:
    • [math]left[/math] — левая граница подотрезка
    • [math]right[/math] — правая граница подотрезка
double ArithmeticCoding(s: string):
    left = 0
    right = 1
    for i = 0 to length(s)-1
        symb = s[i]
        newRight = left + (right - left) * segment[symb].right
        newLeft = left + (right - left) * segment[symb].left
        left = newLeft
        right = newRight
    return (left + right) / 2

Декодирование

Алгоритм по вещественному числу восстанавливает исходный текст.

  1. Выберем на отрезке [math][0; 1)[/math], разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
  2. Нормируем подотрезок и вещественное число.
  3. Повторим пункты 1—2 до тех пор, пока не получим ответ.

Псевдокод

  • [math]code[/math] — вещественное число, подаваемое на вход
  • [math]length[/math] — длина восстанавливаемого текста
  • [math]segment[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math], соответствующего конкретному символу на основе частотного анализа. Имеет поля:
    • [math]left[/math] — левая граница подотрезка
    • [math]right[/math] — правая граница подотрезка
    • [math]character[/math] — значение символа

string ArithmeticDecoding(code: double):
    s = ""
    for i = 1 to length
        for j = 1 to n
            if code >= segment[j].left and code < segment[j].right
                s = s + segment[j].character
                code = (code – segment[j].left) / (segment[j].right – segment[j].left)
                break
    return s

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

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

Пример работы

Рассмотрим в качестве примера строку [math]abacaba[/math]:

Кодирование

Символ Частота появления

[math]a[/math]

[math]0.571429[/math]

[math]b[/math]

[math]0.285714[/math]

[math]c[/math]

[math]0.142857[/math]

Пример работы кодировщика
Считанный символ Левая граница отрезка Правая граница отрезка

[math]0[/math]

[math]1[/math]

[math]a[/math]

[math]0[/math]

[math]0.571429[/math]

[math]b[/math]

[math]0.326531[/math]

[math]0.489796[/math]

[math]a[/math]

[math]0.326531[/math]

[math]0.419825[/math]

[math]c[/math]

[math]0.406497[/math]

[math]0.419825[/math]

[math]a[/math]

[math]0.406497[/math]

[math]0.414113[/math]

[math]b[/math]

[math]0.410849[/math]

[math]0.413025[/math]

[math]a[/math]

[math]0.410849[/math]

[math]0.412093[/math]

Код: [math]0.411471[/math]

Декодирование

Код: [math]0.411471[/math]

Пример работы декодировщика
Декодируемый символ Код

[math]a[/math]

[math]0.411471[/math]

[math]b[/math]

[math]0.720074[/math]

[math]a[/math]

[math]0.520259[/math]

[math]c[/math]

[math]0.910454[/math]

[math]a[/math]

[math]0.373178[/math]

[math]b[/math]

[math]0.653061[/math]

[math]a[/math]

[math]0.285714[/math]

Замечание: при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.

Декодирование (второй способ)

Код: [math]0.411471[/math]

Пример работы декодировщика (второй способ)
Декодируемый символ Границы отрезка

[math]a[/math]

[math]0[/math]

[math]0.571429[/math]

[math]0.857143[/math]

[math]1[/math]

[math]b[/math]

[math]0[/math]

[math]0.326531[/math]

[math]0.489796 [/math]

[math]0.571429[/math]

[math]a[/math]

[math]0.326531 [/math]

[math]0.419825 [/math]

[math]0.466472 [/math]

[math]0.489796 [/math]

[math]c[/math]

[math]0.326531[/math]

[math]0.379842[/math]

[math]0.406497[/math]

[math]0.419825[/math]

[math]a[/math]

[math]0.406497[/math]

[math]0.414113[/math]

[math]0.417921 [/math]

[math]0.419825[/math]

[math]b[/math]

[math]0.406497[/math]

[math]0.410849[/math]

[math]0.413025[/math]

[math]0.414113[/math]

[math]a[/math]

[math]0.410849[/math]

[math]0.412093[/math]

[math]0.412714[/math]

[math]0.413025[/math]

Оценка длины кодового слова

Теорема:
При арифметическом кодировании длина кодового слова не превышает энтропии исходного текста.
Доказательство:
[math]\triangleright[/math]

Введём следующие обозначения: [math]l[/math] — длина текста; [math]n[/math] — размер алфавита; [math]f_i[/math] — частота встречаемости символа; [math]p_i[/math] — вероятность вхождения символа;

Размер сообщения [math]L[/math] можно найти по формуле: [math] L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}[/math]

Число бит в закодированном тексте: [math]\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...p_n)[/math]
[math]\triangleleft[/math]

См. также

Источники информации