Mathjax

пятница, 1 марта 2013 г.

"Архиватор" Бабушкина

Ставший недавно интернет-знаменитостью барнаульский студент Алексей Бабушкин, среди прочих изобретений предложил идею новаторского алгоритма сжатия данных.  Мне этот алгоритм показался хоть и бесперспективным с точки зрения сжатия, но достаточно любопытным, чтобы попробовать его реализовать.

Работающий код можно скачать с Github: babushkin_arch.

Примеры использования программы

Кодирование (сжатие)

$ python babushkin_arch.py original.txt encoded.dat

Декодирование:

$ python babushkin_arch.py -d encoded.dat decoded.txt

Сложность алгоритма достаточно быстро растёт по мере роста объёма файла, практический верхний предел размера - около 100Кб, при этом требуется порядка 10-20 минут времени. Файлы размером несколько килобайт преобразуются за секунды.

Алгоритм

Рассмотрим работу алгоритма на примере сжатия строки с текстом “hello world”

  1. Байты исходного сообщения записываются в 16-ричной системе счисления:
    “68 65 6c 6c 6f 20 77 6f 72 6c 64”.
  2. К получившемуся длинному 16-ричному числу спереди дописывается десятичная точка, тем самым получается конечная 16-ричная дробь, значение которой лежит в полуинтервале [0;1):
    X = 0.68656c6c6f20776f726c6416 = 0.4077976...10
  3. Подбирается (способ описан ниже) простейшее рациональное число P/Q, которое с достаточной точностью приближает X. В данном случае минимальной дробью будет число:
    X* = 9a808e9d26316 / 17adea82373616 
  4. Числитель и знаменатель найденной дроби, а также длина исходного сообщения и являются результатом "сжатия".
Несложно заметить, что качество "сжатия" невелико: исходная последовательность из 22 шестнадцатеричных цифр заменяется двумя последовательностями из 11 и 12 цифр соответственно.

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

Реализация

Автор полагал, что поиск подходящей дроби P/Q≈X может занять огромное время, однако это не так. Используя подходящие алгоритмы и современные компьютеры, несложно найти простейшие рациональные представления дроби для чисел с сотнями тысяч 16-ричных знаков после запятой.

Математика

Как найти ближайшую рациональную аппроксимацию к заданной дроби? Решение этой задачи перебором потребует астрономического времени, но известен инструмент, при помощи которого подобные аппроксимации можно находить сравнительно быстро даже для очень длинных чисел (разумеется, при помощи компьютера). Это цепные дроби:

Любое число можно единственным образом представить в виде подобной "многоэтажной" дроби с натуральными коэффициентами. При этом для рациональных чисел “лестница” всегда будет конечной и наоборот.

Замечательным свойством цепных дробей является то, что, отбрасывание нижних “этажей” даёт наилучшие рациональные аппроксимации для числа x. Тем самым, задача построения рациональной аппроксимации может быть решена так:

  1. Записать для исходного числа цепную дробь.

  2. Отбрасывать у цепной дроби нижние этажи, пока сохраняется достаточная точность.

  3. Свернуть последнюю цепную дробь в обычную – это и есть наилучшая аппроксимация.

Например, для числа x=0.2941=2941/10000 цепная дробь запишется так:

Оставив в этой дроби 4 верхних этажа, получим аппроксимацию:

Таким образом, нужные 4 десятичные цифры числа x можно получить, вычислив гораздо более простую дробь: 5/17.

Нужное количество этажей определить несложно. Достаточно рассмотреть цепные дроби для двух чисел: нижней (0.2941) и верхней (0.294199999...=0.2942) границ подходящих чисел. Первый различающийся коэффициент двух разложений покажет место отсечения. (Последним коэффициентом в сокращённой цепочке будет меньший из двух различающихся коэффициентов, увеличенный на 1)

Анализ алгоритма

Первый приведённый пример показывает, что на небольших объёмах данных сжатия не наблюдается. Увы, как несложно убедиться, для большинства файлов более солидного объёма результат тот же самый: результат "сжатия" на несколько байт больше исходного файла. Впрочем, для некоторых файлов "архиватор" всё-же работает.

Например, рассмотрим файл helloworlds.txt размером 126 байт со следующим текстом (без переноса строки в конце!):

Hello world world world world world world world world world world world world world world world world world world world world
Сжатый файл имеет размер 30 байт, налицо сжатие в 4 раза! Однако даже единственный перенос строки, добавленный в конце файла, разрушает эффект.

Причины такого поведения понять несложно, если знать свойства n-ичных представлений рациональных чисел. Известно, что десятичная запись любого рационального числа после некоторого момента начинает повторяться. Например:

$$\frac 5 {14} = 0.357142857142857142857... = 0.3(571428)$$

То же самое верно и для любой другой системы счисления. Верно и обратное: десятичная дробь, которая с некоторого момента содержит повторяющуюся последовательность - рациональна. Как правило, чем короче период и непериодическая часть, тем меньше числитель и знаменатель рационального числа. Таким образом, файлам, которые заканчиваются многократным повтором одной последовательности символов, соответствуют простые рациональные дроби, и наблюдается хорошее сжатие. Алгоритм Бабушкина действительно способен уменьшить размер файла, но обнаруживает только очень специфичные закономерности, сильно уступая более "всеядным" традиционным алгоритмам сжатия.