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

Арифметическое кодирование (АК) — это статистический метод сжатия данных, работающий по принципу кодирования одного символа за один раз. Длина закодированного выходного кода каждого символа может варьироваться в зависимости от вероятности частоты появления символа. Меньшее количество битов используется для кодирования символов, которые встречаются с высокой вероятностью, а большее количество – с низкой вероятностью.

Идея алгоритма АК:

При арифметическом кодировании слово представляется в виде интервала действительных чисел от 0 до 1. С увеличением длины слова, уменьшается интервал для его представления и увеличивается число бит для его определения. Более вероятные символы уменьшают интервал на меньшую величину, чем маловероятные символы, и, следовательно, добавляют меньше битов к слову.

Описание алгоритма:

Пример:

Пусть дан алфавит A = {a,b}, m = 3. Построю отрезки для всех слов длины m, из символов данного алфавита.

Решение:

Рассмотрю множество всевозможных слов заданной длины m. Причем, расположу слова в лексикографическом порядке

где A-это алфавит, с количеством символов равным n.

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

Обозначу:

Теперь, когда известны отрезки всех слов длины 3, найду код слова aab. Но, для начала, введу следующие обозначения:

B(α)-координата начала слова α

E(α)-координата конца слова α

B(aab) = 0,216; E(aab) = 0,36.

Переведу числа из десятичной записи в двоичную:

Кодом слова aab выбираю общий префикс координат начала и конца в двоичной записи, а именно 01, так как он будет минимальной длины.

Реализаций алгоритма арифметического кодирования множество в интернете, и они немногим отличаются друг от друга. Ниже приведена ссылка на репозиторий с реализацией пользователя Izakharov https://gist.github.com/Lzakharov/31278ecb5159e7180f009c557e7a94a4

Я же буду заниматься улучшением, оптимизацией «наивного» алгоритма арифметического кодирования.

Оптимизация наивного алгоритма

Введу дополнительные определения в наивный алгоритм:

Интервалом буду считать для всех слов кроме последнего. Для последнего слова интервалом будет. Это дополнение вносит в алгоритм больше определенности, так как теперь, наверняка, удастся избежать случая, когда выбранные точки для разных слов совпадают, что влечет за собой нарушение условия разделимости кода.

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

Пусть известны координаты начала и конца слова.

B(α)= 0,r_1 r_2…r_k 0…
E(α)= 0,r_1 r_2…r_k 1…

Тогда кодом слова α будет общий префикс координат начала и конца в двоичной записи, то есть〖 r〗_1 r_2…r_k.

В том случае, когда общего префикса нет, а это возможно лишь при условии, что B(α)<0.5 и E(α) ≥0.5, кодом слова выбирается пустая строка. При арифметическом декодировании необходимо использовать данные о длине слов и текста в целом, так что пустая строка как код не вызывает никаких противоречий.

Нетрудно вывести формулы нахождения координат начала и конца слов.

α – некоторое слово, a_j символ из алфавита А.

Представлю числа в виде дробей со знаменателем

В программе буду хранить только целые числа: числители дробей и показатели степеней знаменателя (k и r). Это условие нужно для того, чтобы вычислять код, по крайней мере, с незначительной погрешностью. Если реализовать алгоритм арифметического кодирования «в лоб», то коды длинных слов будут вычисляться неверно как следствие накопления погрешностей.

Преобразования масштабирования

1. Предположу, что

Тогда, можно домножить

на 2 и зафиксировать полученные значения. Если после дальнейших вычислений ответ поделить на 2, то он не изменится. Это объясняется тем, что при данном условии первый символ кода гарантированно будет 0, т.к. если умножить два десятичных числа, которые меньше 0.5, на два, то целая часть не появится, значит, общий префикс начинается с нуля.

2. Предположу

Тогда можно приписать к коду 1, вычесть  1/2, умножить на 2 и продолжить алгоритм. Так как числа больше 0.5, то при умножении на 2, они станут больше единицы, следовательно, появится общий префикс равный единице.

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

A = 'abcd'
P = [2, 5, 5, 4]
r = 4


def coding(text):
    beg, end = 0, 1
    prob = 1
    k = k1 = 0
    code = ''

    for symbol in text:
        pos = A.find(symbol)
        end = beg*(2**r) + prob*sum(P[0:pos+1])
        beg = beg*(2**r) + prob*sum(P[0:pos])
        prob = prob*P[pos]
        k += r        
        k1 += r

        while True:
            if end < 2**(k-1):
                k -= 1
                code += '0'
            elif beg >= 2**(k-1):
                beg -= 2**(k-1)
                end -= 2**(k-1)
                k -= 1
                code += '1'
            elif beg % 2 == 0 and end % 2 == 0:
                beg /= 2
                end /= 2
                prob /= 2
                k -= 1
            elif k > 30:
                beg //= 2
                end //= 2
                prob = end - beg
                k -= 1
            else:
                break    
    return code

Листинг программы:

Эти два условия есть не что иное, как преобразования масштабирования. Так как в программе хранятся только целые числа, числитель и знаменатель, то сравнение проводится не с 1/2, а с 2^(k-1)

if end < 2**(k-1):
    k -= 1
    code += '0'
elif beg >= 2**(k-1):
    beg -= 2**(k-1)
    end -= 2**(k-1)
    k -= 1
    code += '1'

Данный кусок кода служит для того, чтобы упростить дробь, знаменатель которой является числом большим, чем

elif k > 30:
    beg //= 2
    end //= 2
    prob = end - beg
    k -= 1

Назначение следующего условия очевидно. Здесь, если числитель дроби кратен двум, то он сокращается на два, а степень знаменателя уменьшается на единицу. Такие сокращения делают вычисления проще и увеличивают скорость работы программы.

elif beg % 2 == 0 and end % 2 == 0:
    beg /= 2
    end /= 2
    prob /= 2
    k -= 1

Практическое применение

В данном участке кода составляется входное тестовое сообщение, которое затем будет кодироваться.

s = ''
for i in range(1_000_000):
    ln = random.randint(1, 7)
    for j in range(ln):
        s += random.choice('abcd')
    s += ' '

Ниже входное сообщение записывается в файл, а затем кодируется методом арифметического кодирования.

with open('s.txt', 'w') as f:
    f.write(s)

code = coding(s)

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

pack = b''
for i in range(0, len(code), 8):
    pack += struct.pack('B', int(code[i:i+8], 2))


with open('pack_code.txt', 'wb') as f:
    f.write(pack)

Чтобы проверить, что все сделано правильно, попробую извлечь поток байтов из файла и преобразовать его в исходный код.

with open('pack_code.txt', 'rb') as f:
    unpack = f.read()

code_unpack = ''
for i in unpack:
    code_unpack += '{0:08b}'.format(i)

print(f'Is the original code equal to the code converted from bytes: {code_unpack == code}')

Результат работы программы

Несмотря на то, что количество символов в закодированном сообщении больше, чем в исходном тексте сообщения, в памяти компьютера закодированное сообщение занимает в 3 раза меньше места. Более того, оптимизированный алгоритм кодирует входное сообщение в ~2 раза быстрее «наивного».

Вывод

В результате на языке python реализован алгоритм арифметического кодирования, методы декодирования для него, а также для увеличения скорости сжатия и уменьшения погрешности, он был оптимизирован с помощью представления чисел в виде дробей и преобразованиями масштабирования. Код доступен по ссылке https://github.com/Pyt-Sergei/InformationCoding

В своей профессиональной деятельности я использовал алгоритм АК для сжатия текстовых документов. Это решение было принято для того, чтобы уменьшить количество занимаемой памяти на носителе и для дальнейшей быстрой передачи этих файлов по сети Интернет.