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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Декодирование)
(Кодирование)
Строка 10: Строка 10:
 
# Повторим пункт (3) до конца входного потока.
 
# Повторим пункт (3) до конца входного потока.
 
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.
 
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.
 +
 +
== Псевдокод ==
 +
 +
<tex>s</tex> {{---}} текст, подаваемый на вход
 +
 +
<tex>left</tex>, <tex>right</tex> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования
 +
 +
<tex>segment[i].left</tex>, <tex>segment[i].right</tex> {{---}} границы подотрезка отрезка <tex>[0; 1)</tex>, соответствующего символу <tex>i</tex>
 +
 
  '''double''' ArithmeticCoding (s: '''string'''):
 
  '''double''' ArithmeticCoding (s: '''string'''):
 
     left = 0
 
     left = 0
 
     right = 1
 
     right = 1
 
     '''for''' i = 0 '''to''' length(s)-1
 
     '''for''' i = 0 '''to''' length(s)-1
         '''read'''(s[i])
+
         symb = s[i]
         newRight = left + (right - left) * segment[symb].right <span style="color:green"> // segment[symb] — подотрезок отрезка [0; 1), соответствующий символу symb  </span>
+
         newRight = left + (right - left) * segment[symb].right
 
         newLeft = left + (right - left) * segment[symb].left
 
         newLeft = left + (right - left) * segment[symb].left
 
         left = newLeft
 
         left = newLeft

Версия 16:01, 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[i].left[/math], [math]segment[i].right[/math] — границы подотрезка отрезка [math][0; 1)[/math], соответствующего символу [math]i[/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 до тех пор, пока не получим ответ.

string ArithmeticCoding (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 = \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]

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