Усиление степени сжатия текста: различия между версиями

Важнейшим компонентом алгоритма усиления степени сжатия является взаимосвязь между матрицей 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 эти символы представлены внутри кружков.