4551
правка
Сжатие и индексация дерева: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
Схема индексации дерева из работы [5] основана на преобразовании помеченного дерева <math>\mathcal{T}</math>, которое обозначается как <math>xbw[\mathcal{T}]</math> и линеаризует дерево в два массива координат <math>\langle S_{last}, S_{\alpha} \rangle</math>: первый из них хранит структуру дерева, а второй – перестановку меток <math>\mathcal{T}</math>. <math>xbw[\mathcal{T}]</math> имеет оптимальный (с точностью до членов более низкого порядка) размер <math>2t + t \; log \; | \Sigma |</math> бит и может быть | Схема индексации дерева из работы [5] основана на ''преобразовании'' помеченного дерева <math>\mathcal{T}</math>, которое обозначается как <math>xbw[\mathcal{T}]</math> и линеаризует дерево в два массива координат <math>\langle S_{last}, S_{\alpha} \rangle</math>: первый из них хранит структуру дерева, а второй – перестановку меток <math>\mathcal{T}</math>. <math>xbw[\mathcal{T}]</math> имеет оптимальный (с точностью до членов более низкого порядка) размер <math>2t + t \; log \; | \Sigma |</math> бит и может быть построено и инвертировано за оптимальное линейное время. При разработке алгоритма XBW-Transform авторы вдохновлялись элегантным преобразованием Барроуза-Уилера для строк [4]. Мощь преобразования <math>xbw[\mathcal{T}]</math> определяется тем фактом, что оно позволяет преобразовать задачи сжатия и индексации на помеченных деревьях в более простые задачи на строках. Следующие два примитива поиска по строке являются основными инструментами для индексации <math>xbw[\mathcal{T}]: rank_c(S, i)</math> возвращает количество вхождений символа c в префиксе строки S[1, i], а <math>select_c(S, j) \;</math> возвращает позицию j-го вхождения символа c в строке S. В литературе встречается множество эффективных по времени и объему памяти реализаций данных примитивов, которые могут трактоваться как черные ящики в задаче сжатой индексации <math>xbw[\mathcal{T}]</math> (см., например, [2, 14] и ссылки в этих работах). | ||
| Строка 68: | Строка 68: | ||
• Если <math>| \Sigma | = O(polylog(t)) \;</math>, индексация требует не более <math>tH_0(S_{\alpha}) + 2t + o(t) \;</math> бит, схема поддерживает выполнение базовых навигационных запросов за константное время, а (численных) запросов о подпутях – за время <math>O( | \Pi | ) \;</math>. | • Если <math>| \Sigma | = O(polylog(t)) \;</math>, индексация требует не более <math>tH_0(S_{\alpha}) + 2t + o(t) \;</math> бит, схема поддерживает выполнение базовых навигационных запросов за константное время, а (численных) запросов о подпутях – за время <math>O( | \Pi | ) \;</math>. | ||
• Для любого алфавита <math>\Sigma \;</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. | Здесь <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]). | ||
