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

Перейти к навигации Перейти к поиску
Строка 71: Строка 71:




'''Пример 3.''' Рассмотрим суффиксное дерево на рис. 1. Листовой покрытие состоит из всех вершин, имеющих глубину 1. Разбиение s, порожденное этим листовым покрытием, выглядит как fi;pssm; $; pi; ssiig.
'''Пример 3.''' Рассмотрим суффиксное дерево на рис. 1. Листовой покрытие состоит из всех вершин, имеющих глубину 1. Разбиение <math>\hat{s}\;</math>, порожденное этим листовым покрытием, выглядит как {i, pssm, $; pi, ssii}.




Усиление степени сжатия текста, рис. 1
Усиление степени сжатия текста, рис. 1
Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е., в данном случае, s = bwt(s) = ipssm$pissii


Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е., в данном случае, <math>\hat{s} = bwt(s) = ipssm$pissii \;</math>.


Обозначим за C функцию, которая ассоциирует с каждой строкой x над S [ f$g положительное вещественное значение C(x). Для любого листового покрытия L определим его стоимость как C(L) = Pu2L С(Чи)) – иными словами, стоимость листового покрытия L равна сумме стоимостей строк в разбиении, порожденном L. Листовое покрытие Lmin называется оптимальным относительно C если C(Lmin) < C(L) для любого листового покрытия L.
 
Обозначим за C функцию, которая ассоциирует с каждой строкой x над <math>\Sigma \cup \{ $ \} \;</math> положительное вещественное значение C(x). Для любого листового покрытия <math>\mathcal{L} \;</math> определим его стоимость как <math>C(\mathcal{L}) = \sum_{u \in \mathcal{L}} C( \hat{s} \langle u \rangle) \;</math> – иными словами, стоимость листового покрытия <math>\mathcal{L} \;</math> равна сумме стоимостей строк в разбиении, порожденном <math>\mathcal{L} \;</math>. Листовое покрытие <math>\mathcal{L}_min \;</math> называется ''оптимальным'' относительно <math>C если C(\mathcal{L}_min) \le C(\mathcal{L}) \;</math> для любого листового покрытия <math>\mathcal{L} \;</math>.




Источник — http://pco.iis.nsk.su/wega/index.php/Усиление_степени_сжатия_текста