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

Maxime, 29.4.96

Метод арифметического кодирования, по сравнению с методами Хаффмана и Шеннона-Фано, в общем случае, обладает лучшей степенью сжатия. Но главным недостатком этого метода является очень низкое быстродействие по сравнению с другими методами. Это объясняется тем, что, как явствует из приведенного ниже алгоритма, для его реализации используются операции умножения и деления, которые являются самыми медленными для основной массы компьютеров.

Кратко опишем метод арифметического кодирования: обрабатываемый текст представляется как интервал вещественных чисел, входящий в интервал (0..1). Если размер сообщения увеличивается, то интервал, необходимый для его представления, становится все меньше и меньше, а число бит для записи этого интервала - увеличивается. Каждый поступающий на обработку символ данных уменьшает этот интервал пропорционально своей вероятности появления. Наиболее часто встречаемый символ сокращает этот интервал меньше всех, т.е. добавляет меньше бит в представление этого интервала. Пустому сообщению соответствует исходный интервал (0..1).

Пусть N - количество символов алфавита и пусть Pi - вероятность появления в тексте символа с номером i. Тогда i-му символу поставим в соответствие полуинтервал:

             i-1       i                                                      
        ( SUM   Pk, SUM   Pk ],         i = 1..N; P0 = 0                      
             k=0       k=0

Если первым на вход поступает символ Pk, то вместо исходного мы берем k-ый интервал и делим его на N частей в тех же пропорциях, что и исходный. Теперь мы готовы к приему второго символа и т.д.

Обозначив HIGH(j) - правую границу интервала, соответствующего уже закодированному фрагменту текста к моменту поступления на вход j-го символа текста, а LOW(j) - левую, можно записать описанный выше алгоритм кодирования:

        RANGE(i) = HIGH(i-1) - LOW(i-1)                                       
        HIGH(i) = LOW(i-1) + RANGE(i) * Q(Ci+1)                (*)   
        LOW(i) = LOW(i-1) + RANGE(i) * Q(Ci)

Ci - номер буквы алфавита, соответствующей i-му символу сообщения.

Пусть VALUE - число, полученное на входе алгоритмом декодирования, тогда каждый символ можно раскодировать применяя следующую последовательность действий:
Найдем символ С, такой, что:

                  VALUE - LOW(j)                                              
        Q(C-1) <= --------------- < Q(C)                                      
                  HIGH(j) - LOW(j)

Это и будет очередной символ закодированного текста. После этого необходимо выполнить действия (*) и переходить к раскодированию очередного символа.

Изменена 19.03.2011 06:45 MSK