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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Pseudocode bugfix)
(не показана 21 промежуточная версия 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>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки). Однако, несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>\dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число.
+
Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.
 +
}}  
  
 
== Принцип действия ==
 
== Принцип действия ==
 +
При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).
 
=== Кодирование ===
 
=== Кодирование ===
 
На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.
 
На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.
Строка 8: Строка 12:
 
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
 
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
 
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
 
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
# Повторим пункт (3) до конца входного потока.
+
# Повторим пункт <tex>(3)</tex> до конца входного потока.
 
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.
 
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.
  
Строка 23: Строка 27:
 
*<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования.
 
*<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования.
  
<code>
 
 
  '''struct''' Segment:
 
  '''struct''' Segment:
 
     '''double''' left
 
     '''double''' left
 
     '''double''' right
 
     '''double''' right
  
  '''void''' defineSegments(letters: '''char'''[m], probability: '''double'''[m]):
+
  '''Segment'''[m] defineSegments(letters: '''char'''[m], probability: '''double'''[m]):
     '''Segment''' segment[]
+
     '''Segment'''[m] segment
 
     '''double''' l = 0
 
     '''double''' l = 0
     '''for''' i = 1 '''to''' m
+
     '''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''' ArithmeticCoding(s: '''char'''[n]):
+
  '''double''' arithmeticCoding(letters: '''char'''[m], probability: '''double'''[m], s: '''char'''[n]):
     defineSegments()
+
     '''Segment'''[m] segment = defineSegments(letters, probability)
 
     '''double''' left = 0
 
     '''double''' left = 0
 
     '''double''' right = 1
 
     '''double''' right = 1
     '''for''' i = 0 '''to''' n-1
+
     '''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
Строка 46: Строка 51:
 
         right = newRight
 
         right = newRight
 
     '''return''' (left + right) / 2
 
     '''return''' (left + right) / 2
</code>
 
  
 
'''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи.
 
'''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи.
Строка 54: Строка 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{length}\,</math> {{---}} длина восстанавливаемого текста;
+
*<math>\mathtt{n}\,</math> {{---}} длина восстанавливаемого текста;
 
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
 
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
 
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
 
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
Строка 68: Строка 72:
 
** <math>\mathtt{character}\,</math> {{---}} значение символа.
 
** <math>\mathtt{character}\,</math> {{---}} значение символа.
  
<code>
 
 
  '''struct''' Segment:
 
  '''struct''' Segment:
 
     '''double''' left
 
     '''double''' left
Строка 74: Строка 77:
 
     '''char''' character
 
     '''char''' character
  
  '''void''' defineSegments(letters: '''char'''[n], probability: '''double'''[n]):
+
  '''Segment'''[m] defineSegments(letters: '''char'''[n], probability: '''double'''[n]):
     '''Segment''' segment[m]
+
     '''Segment'''[m] segment
 
     '''double''' l = 0
 
     '''double''' l = 0
     '''for''' i = 0 '''to''' m-1
+
     '''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''' ArithmeticDecoding(code: '''double''', length: '''int'''):
+
  '''string''' arithmeticDecoding(letters: '''char'''[m], probability: '''double'''[m], code: '''double''', n: '''int'''):
     defineSegments()
+
     '''Segment'''[m] segment = defineSegments(letters, probability)  
 
     '''string''' s = ""
 
     '''string''' s = ""
     '''for''' i = 0 '''to''' length-1
+
     '''for''' i = 0 '''to''' n - 1
         '''for''' j = 0 '''to''' m-1
+
         '''for''' j = 0 '''to''' m - 1
             '''if''' code >= segment[j].left '''and''' code < segment[j].right
+
             '''if''' code<tex>\small{~\geqslant~}</tex>segment[j].left '''and''' code < segment[j].right
                 s = s + segment[j].character
+
                 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
</code>
 
  
 
'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
 
'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
 +
 +
'''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <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>.
  
 
== Пример работы ==
 
== Пример работы ==
Строка 179: Строка 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...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 \ldots p_n)</tex>
 
}}
 
}}
  

Версия 21:08, 31 октября 2019

Определение:
Арифметическое кодирование (англ. 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. Повторим пункт [math](3)[/math] до конца входного потока.
  5. Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.

Псевдокод

  • [math]\mathtt{s}\,[/math] — текст, подаваемый на вход;
  • [math]\mathtt{n}\,[/math] — длина исходного текста;
  • [math]\mathtt{m}\,[/math] — мощность алфавита исходного текста;
  • [math]\mathtt{letters[m]}\,[/math] — массив символов, составляющих алфавит исходного текста;
  • [math]\mathtt{probability[m]}\,[/math] — массив вероятностей обнаружения символа в тексте;
  • [math]\mathtt{Segment}\,[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math], соответствующего конкретному символу на основе частотного анализа. Имеет поля:
    • [math]\mathtt{left}\,[/math] — левая граница подотрезка;
    • [math]\mathtt{right}\,[/math] — правая граница подотрезка;
  • [math]\mathtt{left}\,[/math], [math]\mathtt{right}\,[/math] — границы отрезка, содержащего возможный результат арифметического кодирования.
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

Замечание: для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона [math][left; right][/math] число, содержащее наименьшее количество знаков в двоичной записи.

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

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

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

Псевдокод

  • [math]\mathtt{code}\,[/math] — вещественное число, подаваемое на вход;
  • [math]\mathtt{n}\,[/math] — длина восстанавливаемого текста;
  • [math]\mathtt{m}\,[/math] — мощность алфавита исходного текста;
  • [math]\mathtt{letters[m]}\,[/math] — массив символов, составляющих алфавит исходного текста;
  • [math]\mathtt{probability[m]}\,[/math] — массив вероятностей обнаружения символа в тексте;
  • [math]\mathtt{segment}\,[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math], соответствующего конкретному символу на основе частотного анализа. Имеет поля:
    • [math]\mathtt{left}\,[/math] — левая граница подотрезка;
    • [math]\mathtt{right}\,[/math] — правая граница подотрезка;
    • [math]\mathtt{character}\,[/math] — значение символа.
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[math]\small{~\geqslant~}[/math]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

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

Замечание: Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера — поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, [math]\dfrac{1}{3}[/math]), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его [math]m[/math] подотрезков, кратных по длине [math]n[/math], а всего итераций [math]n[/math], в конечном результате знаменатель дроби не превысит [math]n^{n}[/math], а поскольку сумма всех вероятностей встречи символов равна [math]1[/math], полученная дробь будет находиться в промежутке [math][0; 1)[/math].

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

Рассмотрим в качестве примера строку [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 \ldots p_n)[/math]
[math]\triangleleft[/math]

См. также

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