4511
правок
Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 12:08, 20 января 2017
, 20 января 2017→Алгоритм усиления степени сжатия
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 71: | Строка 71: | ||
'''Пример 3.''' Рассмотрим суффиксное дерево на рис. 1. Листовой покрытие состоит из всех вершин, имеющих глубину 1. Разбиение s, порожденное этим листовым покрытием, выглядит как | '''Пример 3.''' Рассмотрим суффиксное дерево на рис. 1. Листовой покрытие состоит из всех вершин, имеющих глубину 1. Разбиение <math>\hat{s}\;</math>, порожденное этим листовым покрытием, выглядит как {i, pssm, $; pi, ssii}. | ||
Усиление степени сжатия текста, рис. 1 | Усиление степени сжатия текста, рис. 1 | ||
Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е., в данном случае, <math>\hat{s} = bwt(s) = ipssm$pissii \;</math>. | |||
Обозначим за C функцию, которая ассоциирует с каждой строкой x над | |||
Обозначим за 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>. | |||