4551
правка
Сжатие и индексация дерева: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
Теорема 3 ([Ферраджина и др. 2005]). Рассмотрим дерево <math>\mathcal{T}</math>, состоящее из t вершин, помеченных символами алфавита | '''Теорема 3 ([Ферраджина и др. 2005]). Рассмотрим дерево <math>\mathcal{T}</math>, состоящее из t вершин, помеченных символами алфавита <math>\Sigma \;</math>. Существует схема индексации сжатого дерева, обеспечивающая следующие показатели эффективности:''' | ||
• Если \ | • Если <math>| \Sigma | = O(polylog(t)) \;</math>, индексация требует не более <math>tH_0(S_{\alpha}) + 2t + o(t) \;</math> бит, схема поддерживает выполнение базовых навигационных запросов за константное время, а (численных) запросов о подпутях – за время <math>O( | \Pi | ) \;</math>. | ||
• Для любого алфавита | • Для любого алфавита <math>\Sigma \;</math> индексация требует не менее <math>tH_k (S_{\alpha}) + 2t + o(t \; log \; | \Sigma | ))</math> бит, однако выполнение базовых навигационных запросов с метками и (численных) запросов о подпутях замедляется на коэффициент <math>o((log \; log \; | \Sigma | )3)</math>. | ||
Здесь | Здесь <math>H_k(s) \;</math> – эмпирическая энтропия k-го порядка для строки s, <math>H_k(s) \le H_{k - 1}(s)</math> для любого k > 0. | ||
Поскольку Hk(Sa) < Ho(Sa) < log \E\, индексация xbw[T] занимает не больше памяти, чем его стандартное представление, с точностью до членов более низкого порядка; зато это представление намного эффективнее для навигации и поиска по дереву <math>\mathcal{T}</math>. Это представление относится к классу представлений помеченного дерева <math>\mathcal{T}</math>, не имеющих указателей и поддерживающих дополнительные функции поиска (подробнее см. в [5]). | Поскольку Hk(Sa) < Ho(Sa) < log \E\, индексация xbw[T] занимает не больше памяти, чем его стандартное представление, с точностью до членов более низкого порядка; зато это представление намного эффективнее для навигации и поиска по дереву <math>\mathcal{T}</math>. Это представление относится к классу представлений помеченного дерева <math>\mathcal{T}</math>, не имеющих указателей и поддерживающих дополнительные функции поиска (подробнее см. в [5]). | ||