Участник:Капелюшок Георгий Александрович

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

Теорема:

При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.

Доказательство:

[math]\triangleright[/math]

Условные обозначения: [math]A(s)[/math] — размер кодового слова [math]s[/math], [math]L[/math] — длина последнего отрезка в арифметическом кодировании [math]s[/math], [math]l[/math] — длина исходной строки [math]s[/math], [math]A(s)[/math] — размер кодового слова [math]s[/math], [math]n[/math] — размер алфавита, [math]f_i[/math] — частота встречаемости символа, [math]p_i = \dfrac{f i}{l}[/math] — вероятность вхождения символа, [math]H(p_1 \ldots p_n)[/math] — энтропия случайного источника с частотами [math](p_1 \ldots p_n)[/math]. Пусть в результате арифметического кодирования мы получили число [math]\dfrac{x}{2^q}[/math], где [math]q[/math] — количество бит в кодовом слове, т.е. [math]q = A(s)[/math]. Из алгоритма арифметического кодирования [math] L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}[/math]. Тогда [math]A(s) = q \leq -\log_2 L = -\log_2 \prod\limits_{i=1}^n p_{i}^{f_{i}} = -\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 [/math]. Энтропия источника вычисляется по следующей формуле [math]H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i[/math]. Следовательно, [math]A(s) \leq l \cdot H(p_1 \ldots p_n)[/math].

[math]\triangleleft[/math]