Метод Хаффмана является простым и эффективным, однако, он порождает наилучшие коды переменной длины (коды, у которых средняя длина равна энтропии алфавита) только когда вероятности символов алфавита являются степенями числа 2, то есть равны 1/2, 1/4, 1/8 и т.п. Это связано с тем, что метод Хаффмана присваивает каждому символу алфавита код с целым числом битов. Теория информации предсказывает, что при вероятности символа, скажем, 0.4, ему в идеале следует присвоить код длины 1.32 бита. А метод Хаффмана присвоит этому символу код длины 1 или 2 бита. (Перед тем как углубиться в теорию арифметического кодирования, стоит указать две работы [Moffat et al. 98] и [Witter 87], где рассмотрены основные принципы этого метода и приведено множество примеров.)

Арифметическое кодирование решает эту проблему путем присвоения кода всему, обычно, большому передаваемому файлу вместо кодирования отдельных символов. (Входным файлом может быть текст, изображение или данные любого вида.) Алгоритм читает входной файл символ за символом и добавляет биты к сжатому файлу. Чтобы понять метод, полезно представлять себе получающийся код в виде числа из полуинтервала [0,1]. (Здесь [а, 6] обозначает числа от а до 6, включая а и исключая 6. Конец а замкнут, а конец b открыт.) Таким образом код «9746509» следует интерпретировать как число «0.9746509» однако часть «0.» не будет включена в передаваемый файл.

На первом этапе следует вычислить или, по крайней мере, оценить частоты возникновения каждого символа алфавита. Наилучшего результата можно добиться, прочитав весь входной файл на первом проходе алгоритма сжатия, состоящего из двух проходов. Однако, если программа может получить хорошие оценки частот символов из другого источника, первый проход можно опустить. В первом примере мы рассмотрим три символа a1, а2 и а3 с вероятностями P1 = 0.4, Р2 = 0.5 и Р3 = 0.1, соответственно. Интервал [0,1] делится между этими тремя символами на части пропорционально их вероятностям. Порядок следования этих подинтервалов не существенен. В нашем примере трем символам будут соответствовать подинтервалы [0,0.4], [0.4,0.9] и [0.9,1.0].

Чтобы закодировать строку «02020203», мы начинаем с интервала [0,1]. Первый символ 02 сокращает этот интервал, отбросив от него 40% в начале и 10% в конце. Результатом будет интервал [0.4,0.9]. Второй символ 02 сокращает интервал [0.4,0.9] в той же пропорции до интервала [0.6,0.85]. Третий символ 02 переводит его в [0.7,0.825]. Наконец, символ 03 отбрасывает от него 90% в начале, а конечную точку оставляет без изменения. Получается интервал [0.8125,0.8250]. Окончательным кодом нашего метода может служить любое число из этого промежутка. (Заметим, что подинтервал [0.6,0.85] получен из [0.4,0.9] с помощью следующих преобразований его концов: 0.4 + (0.9 - 0.4) X 0.4 = 0.6 и 0.4 + (0.9 - 0.4) х 0.9 = 0.85.)