4446
правок
Сжатие и индексация дерева: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 78: | Строка 78: | ||
Здесь <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]). | ||
Если более всего интересуют усложненные навигационные запросы над помеченными деревьями, а запросов о путях не предполагается, в этом случае больше всего подойдет подход Барбая и др. [1, 2]. Авторы предложили новое понятие сокращенного индекса, отличное от понятия сокращенного или сжатого кодирования, применяющегося во всех вышеприведенных решениях. Сокращенный индекс не затрагивает индексируемые данные; он обращается к ним только при помощи базовых операций, обеспечиваемых лежащим в его основе абстрактным типом данных (ADT), и требует асимптотически меньшего объема памяти в сравнении с теоретико-информационной нижней границей объема памяти для хранения самих данных. Авторы сводят задачу индексации помеченных деревьев к задаче индексации ординальных деревьев и строк, а задачу индексации деревьев с множественными метками – к задаче индексации ординальных деревьев и бинарных отношений. Затем они строят сокращенные индексы для строк и бинарных отношений. Для представления их результата нам потребуются следующие определения. Пусть m – общее количество символов в <math>\mathcal{T}</math>, | Если более всего интересуют усложненные навигационные запросы над помеченными деревьями, а запросов о путях не предполагается, в этом случае больше всего подойдет подход Барбая и др. [1, 2]. Авторы предложили новое понятие сокращенного индекса, отличное от понятия сокращенного или сжатого кодирования, применяющегося во всех вышеприведенных решениях. Сокращенный индекс не затрагивает индексируемые данные; он обращается к ним только при помощи базовых операций, обеспечиваемых лежащим в его основе абстрактным типом данных (ADT), и требует асимптотически меньшего объема памяти в сравнении с теоретико-информационной нижней границей объема памяти для хранения самих данных. Авторы сводят задачу индексации помеченных деревьев к задаче индексации ординальных деревьев и строк, а задачу индексации деревьев с множественными метками – к задаче индексации ординальных деревьев и бинарных отношений. Затем они строят сокращенные индексы для строк и бинарных отношений. Для представления их результата нам потребуются следующие определения. Пусть m – общее количество символов в <math>\mathcal{T}</math>, <math>t_c \;</math> – количество вершин, помеченных символом c в <math>\mathcal{T}</math>, а <math>\rho_c \;</math> – максимальное количество меток c на любом корневом пути <math>\mathcal{T}</math> (называемое рекурсивностью c). Определим <math>\rho \;</math> как среднюю рекурсивность <math>\mathcal{T}</math>, а именно: <math>\rho = (1 / m) \sum_{c \in \Sigma} (t_c \rho_c) \;</math>. | ||
Теорема 4 ([Барбай и др. 2007]). Рассмотрим дерево <math>\mathcal{T}</math>, состоящее из t вершин с (возможно, множественными) метками с максимально возможным числом символов из алфавита | '''Теорема 4 ([Барбай и др. 2007]). Рассмотрим дерево <math>\mathcal{T}</math>, состоящее из t вершин с (возможно, множественными) метками с максимально возможным числом символов из алфавита <math>\Sigma \;</math>. Пусть m – общее количество символов в <math>\mathcal{T}</math>. Предположим, что лежащий в его основе абстрактный тип данных обеспечивает выполнение базовых навигационных запросов за константное время и извлекает i-ю метку вершины за время f. Существует сокращенный индекс <math>\mathcal{T}</math>, использующий <math>m(log \; \rho + o(log \; | \Sigma | \; \rho)))</math> бит и поддерживающий для данной вершины u следующие операции (где <math>L = log \; log | \Sigma | \; log \; log \; log \; | \Sigma |</math>):''' | ||
• Каждый c-наследник или c-потомок u может быть получен за время O(L (f + log log | • Каждый c-наследник или c-потомок u может быть получен за время <math>O(L (f + log \; log \; | \Sigma |))</math>. | ||
• Множество A c-предков u может быть получено за время | • Множество A c-предков u может быть получено за время <math>O(L(f + log\; log \; | \Sigma |) + |A|(log \; log \; \rho_c + log \; log \; log \; | \Sigma | \; (f + log \; log \; | \Sigma |)))</math>. | ||
== Применение == | == Применение == | ||
