Изменения

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

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

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

Навигация