Изменения

Перейти к: навигация, поиск

Арифметическое кодирование

101 байт убрано, 02:39, 24 июня 2021
Отмена правки 81085, сделанной Капелюшок Георгий Александрович ([[User talk:Капелюшок Георгий Ал…
== Оценка длины кодового слова ==
{{Теорема
|statement=При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строкиисходного текста.
||proof=В результате арифметического кодирования мы получили число Введём следующие обозначения: *<tex>\frac x 2 ^ ql</tex>{{---}} длина текста,*<tex>n</tex> {{---}} размер алфавита,*<tex>f_i</tex> {{---}} частота встречаемости символа,*<tex>p_i</tex> {{---}} вероятность вхождения символа.
 Энтропия: Размер сообщения <tex>H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_iL</tex>можно найти по формуле:  Длина кодового слова <tex>A(s) \leq log_2 L = -\sumprod\limits_{i=1}^n f_i\cdot \log_2 p_i l p_{fi} = -l \cdot \sumprod\limits_{i=1}^n p_i\cdot \log_2 p_i = l \cdot H(p_1 \ldots p_n)p_{i}^{f_{i}}</tex>
Число бит в закодированном тексте:

Навигация