Материал из Викиконспекты
Оценка длины кодового слова
| Теорема: |
При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки. |
| Доказательство: |
| [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) = l \cdot H(p_1 \ldots p_n)[/math]. |
| [math]\triangleleft[/math] |
