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

Материал из Викиконспекты
Перейти к: навигация, поиск
(added adaptive coding)
 
(не показано 77 промежуточных версий 13 участников)
Строка 1: Строка 1:
== Определение ==
+
{{Определение  
{{Определение
+
|definition=
|definition= '''Арифметическое кодирование (Arithmetic coding) ''' {{---}} алгоритм сжатия информации без потерь.
+
'''Арифметическое кодирование''' (англ. ''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>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).
 
=== Кодирование ===
 
=== Кодирование ===
Алгоритму передаются текст для кодирования и список частот встречаемости символов.
+
На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.
 
# Рассмотрим отрезок <tex>[0; 1)</tex> на координатной прямой.  
 
# Рассмотрим отрезок <tex>[0; 1)</tex> на координатной прямой.  
 
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
 
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Этот отрезок разделим на части, пропорциональные частотам встречаемости символов.
+
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
# Повторим пункт (3) до конца входного потока.
+
# Повторим пункт <tex>(3)</tex> до конца входного потока.
# Выберем любое число из получившегося отрезка (предпочтительно степень двойки). Это и будет результат арифметического кодирования.
+
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.
<code>
+
 
  left = 0
+
=== Псевдокод ===
right = 1
+
 
  while !eof
+
*<math>\mathtt{s}\,</math> {{---}} текст, подаваемый на вход;
     read(symb)
+
*<math>\mathtt{n}\,</math> {{---}} длина исходного текста;
     newRight = left + (right - left) * segment[symb].right <span style="color:green"> //segment[symb] — подотрезок отрезка [0; 1), соответствующий символу symb  </span>
+
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
    newLeft = left + (right - left) * segment[symb].left
+
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
    left = newLeft
+
*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте;
    right = newRight
+
*<math>\mathtt{Segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
ans = (left + right) / 2
+
**<math>\mathtt{left}\,</math> {{---}} левая граница подотрезка;
</code>
+
**<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
 +
 
 +
'''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи.
 +
 
 
=== Декодирование ===
 
=== Декодирование ===
 
Алгоритм по вещественному числу восстанавливает исходный текст.
 
Алгоритм по вещественному числу восстанавливает исходный текст.
 
# Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
 
# Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
 
# Нормируем подотрезок и вещественное число.
 
# Нормируем подотрезок и вещественное число.
# Повторим п. (1—2) до тех пор, пока не получим ответ (до конца файла).
+
# Повторим пункты <tex>1</tex>{{---}}<tex>2</tex> до тех пор, пока не получим ответ.
<code>
+
 
  do
+
=== Псевдокод ===
  for i = 1 to n
+
 
    if code >= segment[i].left && code < segment[i].right
+
*<math>\mathtt{code}\,</math> {{---}} вещественное число, подаваемое на вход;
        write(segment[i].character)
+
*<math>\mathtt{n}\,</math> {{---}} длина восстанавливаемого текста;
        code = (code – segment[i].left) / (segment[i].right – segment[i].left)
+
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
        break
+
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
while (segment[i].character != eof)
+
*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте;
</code>
+
*<math>\mathtt{segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
=== Замечание ===
+
** <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<tex>\small{~\geqslant~}</tex>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
 +
 
 +
'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
 +
 
 +
'''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <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>.
 +
 
 
== Пример работы ==
 
== Пример работы ==
Рассмотрим в качестве примера строку <tex>abacaba</tex>
+
Рассмотрим в качестве примера строку <tex>abacaba</tex>:
 
=== Кодирование ===
 
=== Кодирование ===
[[Файл:Code_png.png|thumb|right|400px|Пример работы кодировщика ]]
 
 
{|class="wikitable"
 
{|class="wikitable"
 
!Символ||Частота появления
 
!Символ||Частота появления
Строка 52: Строка 114:
 
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.142857</tex></p>
 
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.142857</tex></p>
 
|}
 
|}
 +
[[Файл:Code_png.png|thumb|right|200px|Пример работы кодировщика ]]
 
{|class="wikitable"
 
{|class="wikitable"
 
!Считанный символ||Левая граница отрезка||Правая граница отрезка
 
!Считанный символ||Левая граница отрезка||Правая граница отрезка
Строка 93: Строка 156:
 
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.285714</tex></p>
 
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.285714</tex></p>
 
|}
 
|}
=== Замечание ===
+
 
При декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.
+
'''Замечание:''' при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.
 
=== Декодирование (второй способ)===
 
=== Декодирование (второй способ)===
 
Код: <tex>0.411471</tex>
 
Код: <tex>0.411471</tex>
Строка 116: Строка 179:
  
 
|}
 
|}
== Ссылки ==
+
== Оценка длины кодового слова ==
 +
{{Теорема
 +
|statement=При арифметическом кодировании длина кодового слова не превышает энтропии исходного текста.
 +
 
 +
 
 +
||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 \ldots p_n)</tex>
 +
}}
 +
 
 +
== Адаптивное арифметическое кодирование ==
 +
 
 +
Необходимость применения адаптивного алгоритма возникает в том случае, если вероятностные оценки символов сообщения не известны до начала работы алгоритма. Преимущество такого подхода кодирования заключается в том, что декодировщику не нужно передавать вероятностные оценки для символов, он будет строить их по мере декодирования сообщения, что может сильно сократить вес такого сообщения.
 +
 
 +
=== Алгоритм кодирования ===
 +
 
 +
На вход алгоритму передаётся последовательность символов и алфавит. Каждому символу алфавита <tex>\alpha \in \sum</tex> сопоставляется его вес  <tex>w_\alpha</tex>. В начале работы алгоритма все веса символов равны <tex>1</tex>.
 +
Вероятность каждого символа <tex>\alpha</tex> {{---}} <tex>p(\alpha)</tex> устанавливется равной его весу, делённому на суммарный вес всех символов: <tex dpi="180">p(\alpha) = \dfrac{w_\alpha}{\sum_{i=1}^n w_i}</tex>. После получения очередного символа и построения нужного интервала, вес символа увеличивается на <tex>1</tex>. Когда все символы последовательности будут обработаны, необходимо либо записать маркер конца последовательности, либо запомнить её длину, чтобы позже передать декодировщику. После получения нужных границ <tex>[l, r]</tex>, в котором будет лежать код, необходмо выбрать число <tex>x</tex>, описывающее кодирование:
 +
<tex>x \in [l, r]</tex>. Выбор числа <tex>x</tex> производится также, как и в неадаптивном алгоритме. Выбирается число вида <tex>\dfrac{x}{2^p}: x,p \in \mathbb N</tex>.
 +
 
 +
=== Псевдокод алгоритма ===
 +
 
 +
* <tex>\mathtt{in}</tex> {{---}} текст, подаваемый на вход
 +
* <tex>\mathtt{n}</tex> {{---}} длина исходного текста
 +
* <tex>\mathtt{Segment}</tex> {{---}} структура, задающая подотрезок отрезка <tex>[0, 1)</tex>, соответствующая конкретному символу. Имеет следующие поля:
 +
** <tex> \mathtt{left} </tex> {{---}} левая граница подотрезка
 +
** <tex> \mathtt{right} </tex> {{---}} правая граница подотрезка
 +
* <tex> \mathtt{m} </tex> {{---}} мощность алфавита
 +
* <tex> \mathtt{weight} </tex> {{---}} веса символов алфавита
 +
* <tex> \mathtt{segments} </tex> {{---}} набор подотрезков, соответствующих символам алфавита
 +
* <tex> \mathtt{left, right} </tex> {{---}} границы отрезка, содержащие возможный результат арифметического кодирования
 +
* <tex> \mathtt{getAlphabet(in : char[n])}</tex> {{---}}  функция возвращает множество различных символов в тексте <tex> \mathtt{in} </tex>
 +
 
 +
==== Подотрезок ====
 +
 
 +
'''struct''' Segment:
 +
    '''double''' left;
 +
    '''double''' right;
 +
 
 +
==== Определение начальных границ подотрезков ====
 +
 
 +
'''map<char,''' '''Segment'''> defineSegments'''('''set<char>''' alphabet):
 +
    <font color=green>// определяем размер подотрезков </font>
 +
    double p = 1 / alphabet.size()   
 +
    '''Segments'''[m] segments
 +
    <font color=green>// задаём левую и правую границы каждого из отрезков </font>
 +
    '''double''' curLeft = 0 
 +
    '''double''' curRight = p
 +
    <font color=green>// разбиваем отрезок [0,1) на подотрезки, соответсвующие символам алфавита </font>
 +
    '''for''' i = 0 '''to''' m - 1
 +
        segments[i].left = curLeft
 +
        segments[i].right = curRight
 +
        curLeft = curRight
 +
        curRight = curRight + p
 +
    '''return''' segments
 +
 
 +
==== Перестройка подотрезков ====
 +
'''map<char''', '''Segment'''> '''resizeSegments'''(alphabet : '''char'''[m], weight : '''map<char''', '''int>''', segments : '''map<char''', '''Segment>''')
 +
    <font color=green>// новая левая граница подотрезка</font>
 +
    '''double''' l = 0   
 +
    <font color=green>// сумма весов символов алфавита</font>
 +
    '''int''' sum = 0   
 +
    <font color=green>//  подсчет суммы весов символов алфавита</font>
 +
    '''for''' i = 0 '''to''' m - 1 
 +
        sum = sum + weight[i]
 +
    <font color=green>// перестроение подотрезков, для символов алфавита</font>
 +
    '''for''' i = 0 '''to''' m - 1 
 +
        '''char''' c = alphabet[i]
 +
        segments[c].left = l
 +
        segments[c].right = l + (weight[c] / sum)
 +
        l = segments[c].right;
 +
    '''return''' segments
 +
 
 +
==== Определение начальных весов символов алфавита ====
 +
'''map<char''', '''int> defineWeights'''(alphabet : '''set<char>'''):
 +
    '''map<char''', '''int>''' weight
 +
    <font color=green>// проход по всем символам алфавита и установка начального веса</font>
 +
    '''for''' i = 0 '''to''' m - 1
 +
        '''char''' c = alphabet[i]
 +
        weight[c] = 1
 +
    '''return''' weight
 +
 
 +
==== Кодирование строки ====
 +
'''double''' '''adaptiveCoding'''(in : '''char'''[n], alphabet : '''set<char>'''):
 +
    '''int'''[m] weight = defineWeights(alphabet)
 +
    '''int'''[m] segments = defineSegments(alphabet)
 +
    <font color=green>// начальные границы отрезка</font>
 +
    '''double''' left = 0     
 +
    '''double''' right = 1
 +
    '''for''' i = 0 '''to''' n - 1
 +
        '''char''' c = in[i]
 +
        <font color=green>// увеличение веса символа строки</font>
 +
        weight[c]++ 
 +
        <font color=green>// определение новых границ диапазона с искомым кодом, с учётом полученного символа c</font>
 +
        '''double''' newRight = left + (right - left) * segments[c].right
 +
        '''double''' newLeft = left + (right - left) * segments[c].left
 +
        left = newLeft
 +
        right = newRight
 +
        resizeSegments(alphabet, weight, segments)
 +
    '''return''' (left + right) / 2;
 +
 
 +
=== Алгоритм декодирования ===
 +
При декодировании последовательности символов также используется множество весов <tex>w</tex> символов алфавита <tex>\sum</tex>. В начале работы алгоритма все веса символов равны <tex>1</tex>.  На каждом шаге определяется интевал, содержащий данный код, по интервалу находится символ, который потом записывается в выходную последовательность. Вес полученного символа <tex>\alpha</tex> увеличивается на <tex>1</tex>. Отрезки, соответствующие символам алфавита, перестраиваются в зависимости от изменённых весов символов и размера текущего подотрезка. При получении символа конца последовательности или обработки нужного числа символов алгоритм завершает работу.
 +
 
 +
==== Декодирование ====
 +
* <tex>\mathtt{code}</tex> {{---}} вещественное число, подаваемое на вход;
 +
* <tex>\mathtt{n}</tex> {{---}} длина декодируемой строки;
 +
* <tex>\mathtt{m}</tex> {{---}} мощность алфавита;
 +
* <tex>\mathtt{weight}</tex> {{---}} веса символов алфавита;
 +
* <tex>\mathtt{segments}</tex> {{---}} веса символов алфавита;
 +
 
 +
'''string''' '''decode('''code : '''double''', alphabet : '''set<char>''', '''int''' len):
 +
    '''map<char, int>''' weight = '''defineWeights('''alphabet''')'''
 +
    '''map<char, Segment>''' segments = '''defineSegments('''alphabet''')'''
 +
    '''string''' ans = ""
 +
    <font color=green>// декодирование строки</font>
 +
    '''for''' i = 0 '''to''' n - 1:
 +
        <font color=green>// поиск нужного символа исходной строки по текущему значению кода</font>
 +
        '''for''' j = 0 '''to''' m - 1:
 +
            '''char''' c  = alphabet[j]
 +
            '''if''' code >= segments[c].left '''and''' code < segments[c].right
 +
                ans = ans + c
 +
                weight[c]++
 +
                <font color=green>// вычисление следующего значения кода, с учетом декодированного символа c</font>
 +
                code = (code - segments[c].left) / segments[c].right - segments[c].left)
 +
                <font color=green>// перестроение подотрезков, с учётом декодированного символа c </font>
 +
                resizeSegments(alphabet, weight, segments)
 +
                '''break;'''
 +
    '''return''' ans
 +
 
 +
=== Оценка минимальной и максимальной длины кода ===
 +
 
 +
{{Теорема
 +
|id = th1.
 +
|statement= При адаптивном арифметическом кодировании строки длины <tex>\mathtt{l}</tex>, символы которой принадлежат алфавиту мощности <tex>\mathtt{n}</tex>, полученный код будет лежать в диапазоне <tex>[\dfrac{(n-1)!}{(n+l-1)!}, \dfrac{l!(n-1)!}{(n+l-1)!}]</tex>
 +
|proof=
 +
Во время кодирования строки алгоритм выбирает необходимый подотрезок, увеличивает вес символа и перестраивает подотрезки.
 +
Пусть <tex>L</tex> {{---}} результат кодирования строки длины <tex>l</tex>, использующей алфавит длины <tex>n</tex>. Код <tex>L</tex> формируется следующим образом: на каждом из шагов <tex>k=1, 2, \dots, l</tex>
 +
он изменяется в <tex>\dfrac{w_{\alpha_k}}{n+k-1}</tex> раз. На каждом шаге <tex>k</tex>-й символ <tex>\alpha</tex> будет иметь вес <tex>\alpha_k</tex> (каждый раз больший на <tex>1</tex>, потому что алгоритм адаптивный).
 +
Значит, на каждом шаге суммарный вес символов будет увеличиваться на <tex>1</tex>, т.е. на шаге <tex>k</tex> суммарный вес символов будет равен <tex>n+k-1</tex>
 +
Во время перестроения подотрезков, по алгоритму, каждому символу ствавится в соответствие подотрезок длины <tex>\dfrac{w_{\alpha_k}}{n+k-1}</tex>.
 +
 
 +
В общем виде его можно представить так:
 +
 
 +
<tex>
 +
L = \prod_{i=1}^l \dfrac{w_{\alpha_i}}{n+i-1}
 +
</tex>
 +
 
 +
Знаменатель каждого следующего члена произведения  будет увеличиваться на <tex>1</tex>, так как на каждом шаге увеличивается вес одного из символов алфавита.
 +
Соответственно, чтобы минимизировать произведение, необходимо минимизировать числители его членов.
 +
Этого можно достичь, если передать на вход алгоритму строку, состоящую из неповторяющихся символов.
 +
В таком случае вес каждого из полученных символов будет равен <tex>1</tex>, а значение кода на каждом из шагов <tex>k=1, 2, \dots, l</tex> будет изменяться в <tex>\dfrac{1}{n+k-1}</tex> раз.
 +
 
 +
Соответственно, формула примет вид:
 +
 
 +
<tex>
 +
L_{min} = \prod_{i=1}^l \dfrac{1}{n+i-1} = \dfrac{1}{\dfrac{(n+l-1)!}{(n-1)!}} = \dfrac{(n-1)!}{(n+l-1)!}
 +
</tex>
 +
 
 +
Можно записать, используя формулы комбинаторики:
 +
 
 +
<tex>
 +
L_{min} = \dfrac{1}{{\binom{l}{n+l-1}}l!} = \dfrac{1}{C_{n+l-1}^{l}l!}
 +
</tex>
 +
==== Верхняя граница ====
 +
 
 +
Для того, чтобы максимизировать произведение, необходимо увеличить числитель каждого члена произведения. Этого можно достичь, если передать на вход алгоритму строку, состоящую из одинаковых символов. В таком случае, на каждом из шагов <tex>k=1, 2, \dots, l</tex> вес символа будет равен k, а значение кода будет изменяться в <tex>\dfrac{k}{n+k-1}</tex> раз.
 +
 
 +
Соответственно, формула будет иметь следующий вид:
 +
 
 +
<tex>
 +
L_{max} = \prod_{i=1}^l \dfrac{i}{n+i-1} = \dfrac{l!(n-1)!}{(n+l-1)!}
 +
</tex>
 +
 
 +
Можно записать, используя формулы комбинаторики:
 +
 
 +
<tex>
 +
L_{max} = \dfrac{1}{\binom{n+l-1}{l}} = \dfrac{1}{C_{n+l-1}^{l}}
 +
</tex>
 +
 
 +
}}
 +
 
 +
{{Утверждение
 +
|id = th1.
 +
|statement=При адаптивном арифметическом кодировании строки длины <tex>l</tex>, символы которой принадлежат алфавиту мощности <tex>n</tex>, количество бит, необходимых для кодирования сообщения будет лежать в диапазоне <tex>[-\sum_{i=1}^{l} log_2{\dfrac{1}{n+i-1}}, -\sum_{i=0}^{l-1}log_2\dfrac{i+1}{n+i}]</tex>
 +
|proof=
 +
Произведём оценку количества бит, необходимых для записи кода $L$ в общем случае:
 +
 
 +
<tex>
 +
log_2 L = -\sum_{i=1}^{l} log_2 \frac{w_{\alpha_i}}{n+i-1}
 +
</tex>
 +
 
 +
Все коды лежат в диапазоне <tex>[0, 1)</tex>.
 +
 
 +
Таким образом:
 +
 
 +
Максимальное количество бит будет затрачено при записи кода, являющегося минимальной дробью:
 +
 
 +
<tex>
 +
log_2 L_{min} = -\sum_{i=1}^{l} log_2 \frac{1}{n+i-1}
 +
</tex>
 +
 
 +
Минимальное число бит будет затрачено в случае записи кода максимального размера:
 +
 
 +
<tex>
 +
log_2 L_{max} = -\sum_{i=0}^{l-1} log_2 \frac{i+1}{n+i}
 +
</tex>
 +
}}
 +
 
 +
== См. также ==
 +
* [[Алгоритм_Хаффмана | Алгоритм Хаффмана]]
 +
* [[Алгоритмы_LZ77_и_LZ78 | Алгоритмы LZ77 и LZ78]]
 +
* [[Энтропия_случайного_источника | Энтропия случайного источника]]
 +
 
 +
== Источники информации ==
 +
* [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 Википедия {{---}} Арифметическое кодирование]
 +
* [https://en.wikipedia.org/wiki/Arithmetic_coding Wikipedia {{---}} Arithmetic coding]
 +
* [http://www.sernam.ru/cod_3.php Арифметическое кодирование]
 +
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/arithmetic-coding-2006 Визуализатор арифметического кодирования]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятностей]]
+
[[Категория: Теория вероятности]]
 +
[[Категория: Алгоритмы сжатия]]

Текущая версия на 16:26, 5 апреля 2020

Определение:
Арифметическое кодирование (англ. 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]

Адаптивное арифметическое кодирование[править]

Необходимость применения адаптивного алгоритма возникает в том случае, если вероятностные оценки символов сообщения не известны до начала работы алгоритма. Преимущество такого подхода кодирования заключается в том, что декодировщику не нужно передавать вероятностные оценки для символов, он будет строить их по мере декодирования сообщения, что может сильно сократить вес такого сообщения.

Алгоритм кодирования[править]

На вход алгоритму передаётся последовательность символов и алфавит. Каждому символу алфавита [math]\alpha \in \sum[/math] сопоставляется его вес [math]w_\alpha[/math]. В начале работы алгоритма все веса символов равны [math]1[/math]. Вероятность каждого символа [math]\alpha[/math][math]p(\alpha)[/math] устанавливется равной его весу, делённому на суммарный вес всех символов: [math]p(\alpha) = \dfrac{w_\alpha}{\sum_{i=1}^n w_i}[/math]. После получения очередного символа и построения нужного интервала, вес символа увеличивается на [math]1[/math]. Когда все символы последовательности будут обработаны, необходимо либо записать маркер конца последовательности, либо запомнить её длину, чтобы позже передать декодировщику. После получения нужных границ [math][l, r][/math], в котором будет лежать код, необходмо выбрать число [math]x[/math], описывающее кодирование: [math]x \in [l, r][/math]. Выбор числа [math]x[/math] производится также, как и в неадаптивном алгоритме. Выбирается число вида [math]\dfrac{x}{2^p}: x,p \in \mathbb N[/math].

Псевдокод алгоритма[править]

  • [math]\mathtt{in}[/math] — текст, подаваемый на вход
  • [math]\mathtt{n}[/math] — длина исходного текста
  • [math]\mathtt{Segment}[/math] — структура, задающая подотрезок отрезка [math][0, 1)[/math], соответствующая конкретному символу. Имеет следующие поля:
    • [math] \mathtt{left} [/math] — левая граница подотрезка
    • [math] \mathtt{right} [/math] — правая граница подотрезка
  • [math] \mathtt{m} [/math] — мощность алфавита
  • [math] \mathtt{weight} [/math] — веса символов алфавита
  • [math] \mathtt{segments} [/math] — набор подотрезков, соответствующих символам алфавита
  • [math] \mathtt{left, right} [/math] — границы отрезка, содержащие возможный результат арифметического кодирования
  • [math] \mathtt{getAlphabet(in : char[n])}[/math] — функция возвращает множество различных символов в тексте [math] \mathtt{in} [/math]

Подотрезок[править]

struct Segment:
    double left;
    double right;

Определение начальных границ подотрезков[править]

map<char, Segment> defineSegments(set<char> alphabet):
    // определяем размер подотрезков 
    double p = 1 / alphabet.size()    
    Segments[m] segments
    // задаём левую и правую границы каждого из отрезков 
    double curLeft = 0  
    double curRight = p
    // разбиваем отрезок [0,1) на подотрезки, соответсвующие символам алфавита 
    for i = 0 to m - 1 
        segments[i].left = curLeft
        segments[i].right = curRight
        curLeft = curRight
        curRight = curRight + p
    return segments

Перестройка подотрезков[править]

map<char, Segment> resizeSegments(alphabet : char[m], weight : map<char, int>, segments : map<char, Segment>)
   // новая левая граница подотрезка
   double l = 0    
   // сумма весов символов алфавита
   int sum = 0    
   //  подсчет суммы весов символов алфавита
   for i = 0 to m - 1  
       sum = sum + weight[i] 
   // перестроение подотрезков, для символов алфавита
   for i = 0 to m - 1   
       char c = alphabet[i]
       segments[c].left = l
       segments[c].right = l + (weight[c] / sum)
       l = segments[c].right;
   return segments

Определение начальных весов символов алфавита[править]

map<char, int> defineWeights(alphabet : set<char>):
   map<char, int> weight
   // проход по всем символам алфавита и установка начального веса
   for i = 0 to m - 1
       char c = alphabet[i]
       weight[c] = 1
   return weight

Кодирование строки[править]

double adaptiveCoding(in : char[n], alphabet : set<char>):
   int[m] weight = defineWeights(alphabet)
   int[m] segments = defineSegments(alphabet)
   // начальные границы отрезка
   double left = 0      
   double right = 1
   for i = 0 to n - 1
       char c = in[i]
       // увеличение веса символа строки
       weight[c]++  
       // определение новых границ диапазона с искомым кодом, с учётом полученного символа c
       double newRight = left + (right - left) * segments[c].right 
       double newLeft = left + (right - left) * segments[c].left
       left = newLeft
       right = newRight
       resizeSegments(alphabet, weight, segments)
   return (left + right) / 2;

Алгоритм декодирования[править]

При декодировании последовательности символов также используется множество весов [math]w[/math] символов алфавита [math]\sum[/math]. В начале работы алгоритма все веса символов равны [math]1[/math]. На каждом шаге определяется интевал, содержащий данный код, по интервалу находится символ, который потом записывается в выходную последовательность. Вес полученного символа [math]\alpha[/math] увеличивается на [math]1[/math]. Отрезки, соответствующие символам алфавита, перестраиваются в зависимости от изменённых весов символов и размера текущего подотрезка. При получении символа конца последовательности или обработки нужного числа символов алгоритм завершает работу.

Декодирование[править]

  • [math]\mathtt{code}[/math] — вещественное число, подаваемое на вход;
  • [math]\mathtt{n}[/math] — длина декодируемой строки;
  • [math]\mathtt{m}[/math] — мощность алфавита;
  • [math]\mathtt{weight}[/math] — веса символов алфавита;
  • [math]\mathtt{segments}[/math] — веса символов алфавита;
string decode(code : double, alphabet : set<char>, int len):
   map<char, int> weight = defineWeights(alphabet)
   map<char, Segment> segments = defineSegments(alphabet)
   string ans = ""
   // декодирование строки
   for i = 0 to n - 1:
       // поиск нужного символа исходной строки по текущему значению кода
       for j = 0 to m - 1:
           char c  = alphabet[j]
           if code >= segments[c].left and code < segments[c].right
               ans = ans + c
               weight[c]++
               // вычисление следующего значения кода, с учетом декодированного символа c
               code = (code - segments[c].left) / segments[c].right - segments[c].left)
               // перестроение подотрезков, с учётом декодированного символа c 
               resizeSegments(alphabet, weight, segments)
               break;
   return ans

Оценка минимальной и максимальной длины кода[править]

Теорема:
При адаптивном арифметическом кодировании строки длины [math]\mathtt{l}[/math], символы которой принадлежат алфавиту мощности [math]\mathtt{n}[/math], полученный код будет лежать в диапазоне [math][\dfrac{(n-1)!}{(n+l-1)!}, \dfrac{l!(n-1)!}{(n+l-1)!}][/math]
Доказательство:
[math]\triangleright[/math]

Во время кодирования строки алгоритм выбирает необходимый подотрезок, увеличивает вес символа и перестраивает подотрезки. Пусть [math]L[/math] — результат кодирования строки длины [math]l[/math], использующей алфавит длины [math]n[/math]. Код [math]L[/math] формируется следующим образом: на каждом из шагов [math]k=1, 2, \dots, l[/math] он изменяется в [math]\dfrac{w_{\alpha_k}}{n+k-1}[/math] раз. На каждом шаге [math]k[/math]-й символ [math]\alpha[/math] будет иметь вес [math]\alpha_k[/math] (каждый раз больший на [math]1[/math], потому что алгоритм адаптивный). Значит, на каждом шаге суммарный вес символов будет увеличиваться на [math]1[/math], т.е. на шаге [math]k[/math] суммарный вес символов будет равен [math]n+k-1[/math] Во время перестроения подотрезков, по алгоритму, каждому символу ствавится в соответствие подотрезок длины [math]\dfrac{w_{\alpha_k}}{n+k-1}[/math].

В общем виде его можно представить так:

[math] L = \prod_{i=1}^l \dfrac{w_{\alpha_i}}{n+i-1} [/math]

Знаменатель каждого следующего члена произведения будет увеличиваться на [math]1[/math], так как на каждом шаге увеличивается вес одного из символов алфавита. Соответственно, чтобы минимизировать произведение, необходимо минимизировать числители его членов. Этого можно достичь, если передать на вход алгоритму строку, состоящую из неповторяющихся символов. В таком случае вес каждого из полученных символов будет равен [math]1[/math], а значение кода на каждом из шагов [math]k=1, 2, \dots, l[/math] будет изменяться в [math]\dfrac{1}{n+k-1}[/math] раз.

Соответственно, формула примет вид:

[math] L_{min} = \prod_{i=1}^l \dfrac{1}{n+i-1} = \dfrac{1}{\dfrac{(n+l-1)!}{(n-1)!}} = \dfrac{(n-1)!}{(n+l-1)!} [/math]

Можно записать, используя формулы комбинаторики:

[math] L_{min} = \dfrac{1}{{\binom{l}{n+l-1}}l!} = \dfrac{1}{C_{n+l-1}^{l}l!} [/math]

Верхняя граница

Для того, чтобы максимизировать произведение, необходимо увеличить числитель каждого члена произведения. Этого можно достичь, если передать на вход алгоритму строку, состоящую из одинаковых символов. В таком случае, на каждом из шагов [math]k=1, 2, \dots, l[/math] вес символа будет равен k, а значение кода будет изменяться в [math]\dfrac{k}{n+k-1}[/math] раз.

Соответственно, формула будет иметь следующий вид:

[math] L_{max} = \prod_{i=1}^l \dfrac{i}{n+i-1} = \dfrac{l!(n-1)!}{(n+l-1)!} [/math]

Можно записать, используя формулы комбинаторики:

[math] L_{max} = \dfrac{1}{\binom{n+l-1}{l}} = \dfrac{1}{C_{n+l-1}^{l}} [/math]
[math]\triangleleft[/math]
Утверждение:
При адаптивном арифметическом кодировании строки длины [math]l[/math], символы которой принадлежат алфавиту мощности [math]n[/math], количество бит, необходимых для кодирования сообщения будет лежать в диапазоне [math][-\sum_{i=1}^{l} log_2{\dfrac{1}{n+i-1}}, -\sum_{i=0}^{l-1}log_2\dfrac{i+1}{n+i}][/math]
[math]\triangleright[/math]

Произведём оценку количества бит, необходимых для записи кода $L$ в общем случае:

[math] log_2 L = -\sum_{i=1}^{l} log_2 \frac{w_{\alpha_i}}{n+i-1} [/math]

Все коды лежат в диапазоне [math][0, 1)[/math].

Таким образом:

Максимальное количество бит будет затрачено при записи кода, являющегося минимальной дробью:

[math] log_2 L_{min} = -\sum_{i=1}^{l} log_2 \frac{1}{n+i-1} [/math]

Минимальное число бит будет затрачено в случае записи кода максимального размера:

[math] log_2 L_{max} = -\sum_{i=0}^{l-1} log_2 \frac{i+1}{n+i} [/math]
[math]\triangleleft[/math]

См. также[править]

Источники информации[править]