Сжатый суффиксный массив: различия между версиями

Простым примером полнотекстового индекса является суффиксный массив A[1; n], содержащий перестановку интервала [1; n], такую, что T[A[i];n] < T[A[i + 1]; n] для всех 1 < i < n, где "<" между строками обозначает лексикографический порядок. Используя суффиксный массив, можно найти вхождения заданного шаблона P = p1p2 .. pm в T с помощью двух бинарных поисков за время O(m log n).

Формулировка связанной с суффиксными массивами задачи CFTI проста: необходимо найти экономичную по объему памяти структуру данных, поддерживающую эффективное извлечение значения A[i] для любого i. Такое решение и называется сжатым суффиксным массивом. Обычно сжатые суффиксные массивы также поддерживают получение обратного значения A~l [j] = i для любого заданного j.

Если сжатый полнотекстовый индекс функционирует без текста и содержит достаточно информации для получения любой подстроки T, такой индекс называется самоиндексом, так как его можно использовать в качестве представления T. См. статью «Индексирование сжатого текста» с изложением альтернативного подхода к самоиндексированию, а также [ ] с исчерпывающим обзором по данной теме. Задача CFTI может быть сформулирована для любого полнотекстового индекса при условии, что набор операций, которые должна поддерживать структура данных, строго определен. Например, сжатое суффиксное дерево должно воспроизводить все операции классических суффиксных деревьев.

Классические полнотекстовые индексы занимают O(nlog n) бит, обычно с поправкой на довольно большой константный коэффициент. Типичные цели задачи CFTI могут быть охарактеризованы степенью амбициозности; например, необходимо найти структуру, удовлетворяющую одному из следующих требований к объему памяти: 1) пропорционально размеру текста, т.е. O(n log a) бит; 2) асимптотически оптимально относительно размера текста, т.е. n log cr (1 + o(1)) бит; 3) пропорционально размеру сжатого текста, т.е. O(nHk) бит, где Hk — это (эмпирическая) энтропия k-го порядка строки T1; или даже 4) асимптотически оптимально относительно размере сжатого текста, т.е. nHk + o(n log a) бит.