Данные алгоритмы написаны на языке Python 3.7, для запуска можно использовать
стандартный интерпретатор CPython, но для достижения большей
производительности настоятельно рекомендуется использовать
PyPy, имеющий встроенный JIT-компилятор.
К примеру, тестовый файл pic, объемом 501Кб CPython сжимает за 25 минут, в
то время как PyPy выполняет эту операцию всего за 10 секунд.
Алгоритм компрессии состоит из двух последовательных алгоритмов начального преобразования, по результату работы которых получается много одинаковых символов. После этого над преобразованным текстом применяется кодирование Хаффмана, эффективность которого повышается из-за обилия одинаковых символов, чьи коды будут наиболее короткими.
Прочитанный файл разбивается на блоки. К полученному на вход блоку добавляется символ конца блока, гарантированно отсутствующий в пришедшем на вход блоке. После этого у полученного блока сортируются его циклические сдвиги, а на выход выдается последняя колонка получившейся матрицы сдвигов.
Было бы нецелесообразным генерировать все циклические сдвиги из-за больших затрат по памяти (n^2) и по времени (n^2), поэтому был написан компаратор сдвигов, который сравнивает два циклических сдвига, используя индексы, и проходит по самому блоку не создавая сдвиги.
После преобразования Барроуза-Уиллера блок содержит много подряд идущих одинаковых символов. Алгоритм перемещения к началу подразумевает наличие исходного упорядоченного алфавита. Далее читается символ из блока, возвращается его индекс в алфавите, а символ переставляется в начало алфавита. Таким образом, все подряд идущие одинаковые символы превращаются в 0, за исключением первого в серии, что сильно повышает количество нулей в блоке.
Алгоритм Хаффмана использует вероятности встретить символ в блоке. В данной работе использовался двухпроходный алгоритм, то есть за первый проход подсчитываются частоты символов, после этого составляется дерево кодовых слов, из которого впоследствии получается канонический код, содержащий длины кодовых слов для всех символов, из которого создается новое дерево кодовых слов, которое будет впоследствии восстановлено в алгоритме декомпрессии.
Поскольку после преобразований блок содержит большое число символов 0, алгоритм Хаффмана создаст для них наиболее короткий код, что позволит увеличить коэффициент сжатия. Для каждого символа в блоке будет записано его кодовое слово в выходной файл.
Помимо этого в начало выходного файла будет записан хэдер, содержащий необходимую информацию для декодирования. В данном примере записываются длины кодовых слов для каждого из символов.
Соответсвенно, в алгоритме декомпрессии будут декодированы символы из файла при помощи алгоритма Хаффмана, полученный символ будет являться индексом в алфавите из трансформации перемещия к началу, следовательно, найдется исходный символ, после чего полученный таким образом блок будет преобразован в исходный текст алгоритмом обратного преобразования Барроуза-Уиллера.
На основе информации, полученной из хэдера файла алгоритм декодирования восстанавливает дерево кодовых слов, используя канонический код. После этого поступающий на вход символ из тела файла декодируется проходом по этому дереву.
Декодированный алгоритмом Хаффмана символ является индексом в алгоритме перемещения к началу, следовательно применяя такую же логику как в алгоритме прямого преобразования вернется символ в алфавите по полученному индексу.
У преобразования Барроуза-Уиллера есть свойство, что одинаковые символы из
последней колонки идут в таком же порядке, как и в первой колонке.
Доказательство этого простое: предположим у нас есть последняя колонка
ccbacaa. Поскольку строки - отсортированные циклические сдвиги, то первая
колонка была бы aaabccc. При этом если мы пронумеруем одинаковые символы из
первой колонки - a1a2a3b1c1c2c3, то символ a1 окажется перед символами a2
и a3, поскольку строка, состоящая из следующих за ним символов будет в
результате сортировки выше, чем строки, состоящие из следующих за другими
символами a. Следовательно, одинаковые символы в последней колонке стоят в
порядке, в котором были отсортированы строки из символов, состоящих до
последнего. А поскольку представлены циклические сдвиги, то строка из символов
до символа в последней колонке - это та же строка, что и строка из символов
после символа в первой колонке. Значит, одинаковые символы в последней колонке
идут в таком же порядке, как и в первой колонке: c1c2b1a1c3a2a3.
Блок, пришедший на вход обратному преобразованию Барроуза-Уиллера - последняя колонка матрицы сдвигов. Поскольку известно, что последний символ исходного блока это символ конца блока, начав с него и используя переход от последнего символа к первому, получится восстановить исходный блок в правильной последовательности.
| file name | H(X) | H(X | X) | H(X | XX) | значение средних затрат на символ (в битах) | размер сжатого файла (в байтах) | размер исходного файла (в байтах) |
|---|---|---|---|---|---|---|
| bib | 5.20065 | 3.36413 | 2.30750 | 2.395017 | 33309 | 111261 |
| book1 | 4.52714 | 3.58451 | 2.81407 | 2.781270 | 267270 | 768771 |
| book2 | 4.79262 | 3.74520 | 2.73566 | 2.450096 | 187082 | 610856 |
| geo | 5.64637 | 4.26419 | 3.45769 | 5.428438 | 69484 | 102400 |
| news | 5.18962 | 4.09188 | 2.92274 | 2.834342 | 133607 | 377109 |
| obj1 | 5.94815 | 3.46364 | 1.40042 | 4.354167 | 11704 | 21504 |
| obj2 | 6.26035 | 3.87036 | 2.26541 | 2.873549 | 88654 | 246814 |
| paper1 | 4.98290 | 3.64606 | 2.33176 | 2.757059 | 18321 | 53161 |
| paper2 | 4.60138 | 3.52222 | 2.51353 | 2.747089 | 28226 | 82199 |
| pic | 1.21018 | 0.82365 | 0.70519 | 1.582102 | 101495 | 513216 |
| progc | 5.19893 | 3.60338 | 2.13400 | 2.785489 | 13792 | 39611 |
| progl | 4.77004 | 3.21158 | 2.04353 | 2.103565 | 18839 | 71646 |
| progp | 4.86871 | 3.18733 | 1.75509 | 2.093360 | 12921 | 49379 |
| trans | 5.53275 | 3.35478 | 1.93048 | 1.919761 | 22484 | 93695 |