4446
правок
Сжатый суффиксный массив: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Простым примером полнотекстового индекса является суффиксный массив A[1 | Простым примером полнотекстового индекса является [[суффиксный массив]] A[1, n], содержащий перестановку интервала [1, n], такую, что T[A[i], n] < T[A[i + 1], n] для всех <math>1 \le i < n</math>, где отношение "<" между строками обозначает лексикографический порядок. Используя суффиксный массив, можно найти вхождения заданного шаблона <math>P = p_1 p_2 ... p_m</math> в строке T с помощью двух бинарных поисков за время O(m log n). | ||
Формулировка связанной с суффиксными массивами задачи CFTI проста: необходимо найти экономичную по объему памяти структуру данных, поддерживающую эффективное извлечение значения A[i] для любого i. Такое решение и называется сжатым суффиксным массивом. Обычно сжатые суффиксные массивы также поддерживают получение обратного значения A | Формулировка связанной с суффиксными массивами задачи CFTI проста: необходимо найти экономичную по объему памяти структуру данных, поддерживающую эффективное извлечение значения A[i] для любого i. Такое решение и называется ''сжатым суффиксным массивом''. Обычно сжатые суффиксные массивы также поддерживают получение обратного значения <math>A^{-1} [j] = i</math> для любого заданного j. | ||
Если сжатый полнотекстовый индекс функционирует без текста и содержит достаточно информации для получения любой подстроки T, такой индекс называется самоиндексом, так как его можно использовать в качестве представления T. См. статью | Если сжатый полнотекстовый индекс функционирует без текста и содержит достаточно информации для получения любой подстроки T, такой индекс называется ''самоиндексом'', так как его можно использовать в качестве представления T. См. статью «[[Индексирование сжатого текста]]» с изложением альтернативного подхода к самоиндексированию, а также работу [9] с исчерпывающим обзором по данной теме. | ||
Классические полнотекстовые индексы занимают O( | Задача CFTI может быть сформулирована для любого полнотекстового индекса при условии, что набор операций, которые должна поддерживать структура данных, строго определен. Например, ''сжатое суффиксное дерево'' должно воспроизводить все операции классических ''суффиксных деревьев''. | ||
Классические полнотекстовые индексы занимают O(n log n) бит, обычно с поправкой на довольно большой константный коэффициент. Типичные цели задачи CFTI могут быть охарактеризованы степенью амбициозности; например, необходимо найти структуру, удовлетворяющую одному из следующих требований к объему памяти: | |||
1) пропорционально размеру текста, т. е. <math>O(n \; log \; \sigma)</math> бит; | |||
2) асимптотически оптимально относительно размера текста, т. е. <math>n \; log \; \sigma (1 + o(1))</math> бит; | |||
3) пропорционально размеру ''сжатого'' текста, т.е. O(nHk) бит, где Hk — это (эмпирическая) энтропия k-го порядка строки T1; или даже 4) асимптотически оптимально относительно размере сжатого текста, т.е. nHk + o(n log a) бит. | |||
== Основные результаты == | == Основные результаты == | ||
