Локально
адаптивный алгоритм сжатия
Этот алгоритм
используется для кодирования (L,I), где L строка длиной N, а I ндекс. Это
кодирование содержит в себе несколько этапов.
1. Сначала кодируется
каждый символ L с использованием локально адаптивного алгоритма для каждого из
символов индивидуально. Определяется вектор целых чисел R[0],…,R[N-1], который
представляет собой коды для символов L[0],…,L[N-1]. Инициализируется список
символов Y, который содержит в себе каждый символ из алфавита Х только один
раз. Для каждого i = 0,…,N-1 устанавливается R[i] равным числу символов,
предшествующих символу L[i] из списка Y. Взяв Y = [в качестве исходного и L =
aabвычисляем вектор R: (2 1 3 1 0 3).
2. Применяем
алгоритм Хафмана или другой аналогичный алгоритм сжатия к элементам R,
рассматривая каждый элемент в качестве объекта для сжатия. В результате
получается код OUT и индекс I.
Рассмотрим
процедуру декодирования полученного сжатого текста (OUT,I).
Здесь на основе
(OUT,I) необходимо вычислить (L,I). Предполагается, что список Y известен.
1.
Сначала
вычисляется вектор R, содержащий N чисел: (2 1 3 1 0 3).
2.
Далее
вычисляется строка L, содержащая N символов, что дает значения R[0],…,R[N-1].
Если необходимо, инициализируется список Y, содержащий символы алфавита X (как
и при процедуре кодирования). Для каждого i = 0,…,N-1 последовательно
устанавливается значение L[i], равное символу в положении R[i] из списка Y
(нумеруется, начиная с 0), затем символ сдвигается к началу Y. Результирующая
строка L представляет собой последнюю колонку матрицы M. Результатом работы
алгоритма будет (L,I). Взяв Y = [вычисляем строку L = aabLI>
Наиболее важным
фактором, определяющим скорость сжатия, является время, необходимое для
сортировки вращений во входном блоке. Наиболее быстрый способ решения проблемы
заключается в сортировке связанных строк по суффиксам.
Для того чтобы
сжать строку S, сначала сформируем строку Sкоторая является объединением S c
EOF, новым символом, который не встречается в S. После этого используется
стандартный алгоритм к строке SТак как EOF отличается от прочих символов в S,
суффиксы Sортируются в том же порядке, как и вращения SЭто может быть сделано
путем построения дерева суффиксов, которое может быть затем обойдено в
лексикографическом порядке для сортировки суффиксов. Для этой цели может быть
использован алгоритм формирования дерева суффиксов Мак-Крейгта. Его
быстродействие составляет 40% от наиболее быстрой методики в случае работы с
текстами. Алгоритм работы с деревом суффиксов требует более четырех слов на
каждый исходный символ. Манбер и Майерс предложили простой алгоритм сортировки
суффиксов строки. Этот алгоритм требует только двух слов на каждый входной
символ. Алгоритм работает сначала с первыми i символами суффикса а за тем,
используя положения суффиксов в сортируемом массиве, производит сортировку для
первых 2i символов. К сожалению этот алгоритм работает заметно медленнее.
В работе [1] предложен
несколько лучший алгоритм сортировки суффиксов. В этом алгоритме сортируются
суффиксы строки S, которая содержит N символов S[0,…,N-1].
1.
Пусть
k число символов, соответствующих машинному слову. Образуем строку Sз S путем добавления
k символов EOF в строку S. Предполагается, что EOF не встречается в строке S.
2.
Инициализируем
массив W из N слов W[0,…,N-1] так, что W[i] содержат символы S+,i+k-1]
упорядоченные таким образом, что целочисленное сравнение слов согласуется с лексикографическим
сравнением для k-символьных строк. Упаковка символов в слова имеет два
преимущества: это позволяет для двух префиксов сравнить сразу k байт и
отбросить многие случаи, описанные ниже.
3.
Инициализируется
массив V из N целых чисел. Если элемент V содержит j, он представляет собой
суффикс Sчей первый символ равен S. Когда выполнение алгоритма завершено,
суффикс V[i] будет i-ым суффиксом в лексикографическом порядке.
4.
Инициализируем
целочисленный массив V так, что для каждого i = 0,…,N-1 : V[i]=i.
5.
Сортируем
элементы V, используя первые два символа каждого суффикса в качестве ключа
сортировки. Далее для каждого символа ch из алфавита выполняем шаги 6 и 7.
Когда эти итерации завершены, V представляет собой отсортированные суффиксы S и
работа алгоритма завершается.
6.
Для
каждого символа ch алфавите выполняем сортировку элементов V, начинающихся с
ch, за которым следует chВ процессе выполнения сортировки сравниваем элементы V
путем сопоставления суффиксов, которые они представляют при индексировании
массива W. На каждом шаге рекурсии следует отслеживать число символов, которые
оказались равными в группе, чтобы не сравнивать их снова. Все суффиксы,
начинающиеся с ch, отсортированы в рамках V.
7.
Для
каждого элемента V[i], соответствующего суффиксу, начинающемуся с ch (то есть,
для которого S[V[i]] = ch), установить W[V[i]] значение с ch в старших битах и
i в младших битах. Новое значение W[V[i]] сортируется в те же позиции, что и
старые значения.
Данный алгоритм
может быть улучшен различными способами. Одним из самоочевидных методов
является выбор символа ch на этапе 5, начиная с наименьшего общего символа в S
и предшествующий наиболее общему.