Телекоммуникационные технологии. Том 1



         

Локально адаптивный алгоритм сжатия - часть 2


После этого используется стандартный алгоритм к строке S’. Так как EOF отличается от прочих символов в S, суффиксы S’ сортируются в том же порядке, как и вращения S’. Это может быть сделано путем построения дерева суффиксов, которое может быть затем обойдено в лексикографическом порядке для сортировки суффиксов. Для этой цели может быть использован алгоритм формирования дерева суффиксов Мак-Крейгта. Его быстродействие составляет 40% от наиболее быстрой методики в случае работы с текстами. Алгоритм работы с деревом суффиксов требует более четырех слов на каждый исходный символ. Манбер и Майерс предложили простой алгоритм сортировки суффиксов строки. Этот алгоритм требует только двух слов на каждый входной символ. Алгоритм работает сначала с первыми i символами суффикса а за тем, используя положения суффиксов в сортируемом массиве, производит сортировку для первых 2i символов. К сожалению этот алгоритм работает заметно медленнее.

В работе предложен несколько лучший алгоритм сортировки суффиксов. В этом алгоритме сортируются суффиксы строки 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,…,i+k-1] упорядоченные таким образом, что целочисленное сравнение слов согласуется с лексикографическим сравнением для k-символьных строк. Упаковка символов в слова имеет два преимущества: это позволяет для двух префиксов сравнить сразу k байт и отбросить многие случаи, описанные ниже.

  3. Инициализируется массив V из N целых чисел. Если элемент V содержит j, он представляет собой суффикс S’, чей первый символ равен S’[j]. Когда выполнение алгоритма завершено, суффикс V[i] будет i-ым суффиксом в лексикографическом порядке.

  4. Инициализируем целочисленный массив V так, что для каждого i = 0,…,N-1 : V[i]=i.

  5. Сортируем элементы V, используя первые два символа каждого суффикса в качестве ключа сортировки.


    Содержание  Назад  Вперед