4551
правка
Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 23:01, 10 января 2017
, 10 января 2017→Алгоритм усиления степени сжатия
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 65: | Строка 65: | ||
== Алгоритм усиления степени сжатия == | == Алгоритм усиления степени сжатия == | ||
Важнейшим компонентом алгоритма усиления степени сжатия является взаимосвязь между матрицей bwt и такой структурой данных, как суффиксное дерево. Обозначим за T суффиксное дерево строки s$. У T |s| + 1 листьев, по одному на суффикс s$, а его ребра помечены подстроками s$ (см. рис. 1). Любая вершина u дерева T неявно ассоциируется с подстрокой s$, задаваемой конкатенацией меток ребер на нисходящем пути от корня T к u. В рамках этой неявной ассоциации листья T соответствуют суффиксам s$. Предположим, что ребра суффиксного дерева лексикографически отсортированы. Поскольку каждая строка матрицы bwt имеет префикс в виде суффикса s$ , а строки лексикографически отсортированы, i-й лист суффиксного дерева (считая справа налево) соответствует i-й строке матрицы bwt. Ассоциируем с i-м листом T i-й символ s = bwt(s). На рис. 1 эти символы представлены внутри кружков. | |||
Для любой вершины суффиксного дерева u обозначим за s(u) подстроку J, полученнуюв результате конкатенации, слева направо, символов, ассоциированных с листьями, являющимися потомками вершины u. Разумеется, s(root(T)) = J. Подмножество L вершин T называется листовым покрытием, если каждый лист суффиксного дерева имеет уникального предка в L. Любое листовое покрытие L = fu1..: ; upg естественным образом порождает разбиение листьев T. В силу взаимосвязи между T и матрицей bwt также имеется разбиение s, а именно, {J(MI},. .. ,s(up}}. | |||
'''Пример 3.''' Рассмотрим суффиксное дерево на рис. 1. Листовой покрытие состоит из всех вершин, имеющих глубину 1. Разбиение s, порожденное этим листовым покрытием, выглядит как fi;pssm; $; pi; ssiig. | |||
Усиление степени сжатия текста, рис. 1 | |||
Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е., в данном случае, s = bwt(s) = ipssm$pissii | |||