4446
правок
Сжатие и индексация дерева: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 73: | Строка 73: | ||
Здесь <math>H_k(s) \;</math> – эмпирическая энтропия k-го порядка для строки s, <math>H_k(s) \le H_{k - 1}(s)</math> для любого k > 0. | Здесь <math>H_k(s) \;</math> – эмпирическая энтропия k-го порядка для строки s, <math>H_k(s) \le H_{k - 1}(s)</math> для любого k > 0. | ||
Поскольку <math>H_k(S_{\alpha}) \le H_0(S_{\alpha}) \le log \; | \Sigma |</math>, индексация <math>xbw[\mathcal{T}]</math> занимает не больше памяти, чем его стандартное представление, с точностью до членов более низкого порядка; зато это представление намного эффективнее для навигации и поиска по дереву <math>\mathcal{T}</math>. Это представление относится к классу представлений помеченного дерева <math>\mathcal{T}</math>, не имеющих указателей и поддерживающих дополнительные функции поиска (подробнее см. в [5]). | Поскольку <math>H_k(S_{\alpha}) \le H_0(S_{\alpha}) \le log \; | \Sigma |</math>, индексация <math>xbw[\mathcal{T}]</math> занимает не больше памяти, чем его стандартное представление, с точностью до членов более низкого порядка; зато это представление намного эффективнее для навигации и поиска по дереву <math>\mathcal{T}</math>. Это представление относится к классу представлений помеченного дерева <math>\mathcal{T}</math>, ''не имеющих указателей'' и поддерживающих дополнительные функции поиска (подробнее см. в [5]). | ||
