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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
{{Определение
+
'''Арифметическое кодирование (Arithmetic coding)''' {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
|definition= '''Арифметическое кодирование (Arithmetic coding) ''' {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
+
Данный метод (как и [[Алгоритм Хаффмана|алгоритм Хаффмана]]) является энтропийным т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-log_2(p(a))</tex>, следовательно при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки).
}}
 
Данный метод (как и алгоритм Хаффмана) является энтропийным т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-log_2(p(a))</tex>, следовательно при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки).
 
== Оценка длины кодового слова ==
 
{{Теорема
 
|statement=При арифметическом кодировании длина кодового слова не превышает энтропию случайного источника.
 
 
 
 
 
||proof=Размер сообщения <tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex> (<tex>l</tex> - длина текста; <tex>n</tex> - размер алфавита; <tex>f_i</tex> - частота встречаемости символа; <tex>p_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>
 
}}
 
 
== Принцип действия ==
 
== Принцип действия ==
 
=== Кодирование ===
 
=== Кодирование ===
Строка 125: Строка 114:
  
 
|}
 
|}
 +
== Оценка длины кодового слова ==
 +
{{Теорема
 +
|statement=При арифметическом кодировании длина кодового слова не превышает энтропию случайного источника.
 +
 +
 +
||proof=Размер сообщения <tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex> (<tex>l</tex> - длина текста; <tex>n</tex> - размер алфавита; <tex>f_i</tex> - частота встречаемости символа; <tex>p_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>
 +
}}
 
== Ссылки ==
 
== Ссылки ==
 
* [http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Арифметическое кодирование (wikipedia)]
 
* [http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Арифметическое кодирование (wikipedia)]

Версия 23:03, 13 января 2012

Определение

Арифметическое кодирование (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. Выберем любое число из получившегося отрезка. Это и будет результат арифметического кодирования.

left = 0
right = 1
while !eof
    read(symb)
    newRight = left + (right - left) * segment[symb].right  //segment[symb] — подотрезок отрезка [0; 1), соответствующий символу symb  
    newLeft = left + (right - left) * segment[symb].left
    left = newLeft
    right = newRight
ans = (left + right) / 2

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

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

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

do
for i = 1 to n
    if code >= segment[i].left && code < segment[i].right
        write(segment[i].character)
        code = (code – segment[i].left) / (segment[i].right – segment[i].left)
        break  
while (segment[i].character != eof)

Замечание

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

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

Рассмотрим в качестве примера строку [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 = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}[/math] ([math]l[/math] - длина текста; [math]n[/math] - размер алфавита; [math]f_i[/math] - частота встречаемости символа; [math]p_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]

Ссылки