Изменения

{{Определение|definition= '''Арифметическое кодирование (Arithmetic coding) ''' {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.}} Данный метод (как и [[Алгоритм Хаффмана|алгоритм Хаффмана]]) является энтропийным т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-log_2(p(a))</tex>, следовательно при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки).== Оценка длины кодового слова =={{Теорема |statement=При арифметическом кодировании длина кодового слова не превышает энтропию случайного источника.  ||proof=Размер сообщения <tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex> (<tex>l</tex> - длина текста; <tex>n</tex> - размер алфавита; <tex>f_i</tex> - частота встречаемости символа; <tex>p_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...p_n)</tex>}}