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

Важнейшим компонентом алгоритма усиления степени сжатия является взаимосвязь между матрицей bwt и такой структурой данных, как суффиксное дерево. Обозначим за <math>\mathcal{T} \;</math> суффиксное дерево строки s$. У <math>\mathcal{T} \;</math> имеется |s| + 1 листьев, по одному на суффикс s$, а его ребра помечены подстроками s$ (см. рис. 1). Любая вершина u дерева <math>\mathcal{T} \;</math> ''неявно ассоциируется'' с подстрокой s$, задаваемой конкатенацией меток ребер на нисходящем пути от корня <math>\mathcal{T} \;</math> к u. В рамках этой неявной ассоциации листья <math>\mathcal{T} \;</math> соответствуют суффиксам s$. Предположим, что ребра суффиксного дерева лексикографически отсортированы. Поскольку каждая строка матрицы bwt имеет префикс в виде суффикса s$, а строки лексикографически отсортированы, i-й лист суффиксного дерева (считая справа налево) соответствует i-й строке матрицы bwt. Ассоциируем с i-м листом <math>\mathcal{T} \;</math> i-й символ <math>\hat{s} = bwt(s) \;</math>. На рис. 1 эти символы представлены внутри кружков.

Усиление степени сжатия текста, рис. 1