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



         

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


Далее для каждого символа ch из алфавита выполняем шаги 6 и 7. Когда эти итерации завершены, V представляет собой отсортированные суффиксы S и работа алгоритма завершается.
  • Для каждого символа ch’ в алфавите выполняем сортировку элементов V, начинающихся с ch, за которым следует ch’. В процессе выполнения сортировки сравниваем элементы V путем сопоставления суффиксов, которые они представляют при индексировании массива W. На каждом шаге рекурсии следует отслеживать число символов, которые оказались равными в группе, чтобы не сравнивать их снова. Все суффиксы, начинающиеся с ch, отсортированы в рамках V.

  • Для каждого элемента V[i], соответствующего суффиксу, начинающемуся с ch (то есть, для которого S[V[i]] = ch), установить W[V[i]] значение с ch в старших битах и i в младших битах. Новое значение W[V[i]] сортируется в те же позиции, что и старые значения.

    Данный алгоритм может быть улучшен различными способами. Одним из самоочевидных методов является выбор символа ch на этапе 5, начиная с наименьшего общего символа в S и предшествующий наиболее общему.

    Ссылки

    1. M.Burrows and D.J.Wheeler. A block-sorting Lossless Data Compression Algorithm. Digital Systems Research Center. SRC report 124. May 10, 1994.

    2. J.L.Bently, D.D.Sleator, R.E.Tarjan, and V.K.Wei. A locally adaptive data compression algorithm. Communications of the ACM, Vol. 29, No. 4, April 1986, pp. 320-330

    3. E.M.McCreight. A space economical suffix tree construction algorithm. Journal of the ACM, Val. 32, No. 2, April 1976, pp. 262-272.

    4. U.Manber and E.W.Mayers, Suffix arrays: Anew method for on-line string searches. SIAM Journal on Computing, Vol. 22, No. 5, October 1993, pp. 935-948.

    Смотри также раздел 2.6.3 ,




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