4511
правок
Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 12:03, 20 января 2017
, 20 января 2017→Алгоритм усиления степени сжатия
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 68: | Строка 68: | ||
Для любой вершины суффиксного дерева u обозначим за s(u) подстроку | Для любой вершины суффиксного дерева 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>. | ||