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

Алгоритм арифметического кодирования, также как и алгоритм сжатия Хаффмана, использует для уменьшения объема исходных данных разность в частоте встречаемости символов. В результате сжатия этим алгоритмом редко встречающиеся символы кодируются более длинными кодами по сравнению с более короткими кодами для часто встречающихся символов. Однако, в отличие от алгоритма Хаффмана, символы кодируются не обязательно целым числом битов, т. е. один бит сжатых данных может относиться к нескольким символам сжимаемых данных.

Для данных, в которых частоты встречаемости для разных символов не сильно отличаются, алгоритм арифметического кодирования дает результаты, сходные с результатами, получаемыми при сжатии алгоритмом Хаффмана. Но там, где частоты встречаемости разных символов при небольшом их числе резко отличаются, арифметическое кодирование дает лучший результат по сравнению с алгоритмом Хаффмана. В большинстве реальных случаев арифметическое кодирование даст несколько больший коэффициент сжатия.

До недавнего времени распространение данного алгоритма сдерживалось наличием на него патентов. В настоящее время срок действия патентов закончился и алгоритм широко используют.