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

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

Для любой вершины суффиксного дерева u обозначим за <math>\hat{s}(u) \;</math> подстроку <math>\hat{s} \;</math>, полученную в результате конкатенации, слева направо, символов, ассоциированных с листьями, являющимися потомками вершины u. Разумеется, <math>\hat{s} \langle root( \mathcal{T} ) \rangle  = \hat{s} \;</math>. Подмножество <math>\mathcal{L} \;</math> вершин <math>\mathcal{T} \;</math> называется ''листовым покрытием'', если каждый лист суффиксного дерева имеет ''уникального'' предка в <math>\mathcal{L} \;</math>. Любое листовое покрытие <math>\mathcal{L} = \{ u_1, ..., u_p \} \;</math> естественным образом порождает разбиение  листьев <math>\mathcal{T} \;</math>. В силу взаимосвязи между <math>\mathcal{T} \;</math> и матрицей bwt также имеется разбиение <math>\hat{s} \;</math>, а именно – <math>\{ \hat{s} \langle u_1 \rangle , ..., \hat{s} \langle u_p \rangle \} \;</math>.