Полный массив суффиксов

Question

Массив суффиксов будет индексировать все суффиксы для данного списка строк, но что, если вы пытаетесь проиндексировать все возможные уникальные подстроки?Я немного новичок в этом, поэтому вот пример того, что я имею в виду:

Учитывая строку

abcd

Индексы массива суффиксов (по крайней мере, насколько я понимаю)

(abcd,bcd,cd,d)

Я хотел бы проиндексировать (все подстроки)

(abcd,bcd,cd,d,abc,bc,c,ab,b,a)

Нужен ли массив суффиксов?Если это так, что мне делать, чтобы индексировать все подстроки?Если нет, то где мне искать?Кроме того, что бы я Google, чтобы противопоставить "все подстроки" против "подстрок суффикса"?

Answer 1

Суффиксный массив делает то, что вам уже нужно, потому что каждая подстрока является префиксом одного из суффиксов. В частности, учитывая ваш массив суффиксов

ABCD BCD CD д

и предположим, что вы ищете подстроку "bc", тогда вы можете найти это, отыскивая все суффиксы, начинающиеся с "bc" (в данном случае есть только один, "bcd"). Поскольку суффиксный массив отсортирован по лексикографии, поиск всех суффиксов, которые имеют определенный префикс, соответствует двоичному поиску по массиву суффиксов, и результатом будет один непрерывный диапазон записей массива суффиксов.

Однако существуют оптимизированные методы поиска, использующие массив суффиксов в сочетании со вспомогательными структурами данных, такими как массив LCP (самый длинный общий префикс) или вейвлет-деревья. См. Обзор Наварро 2007 года для описания таких методов (DOI 10.1145 / 1216370.1216372).

Чтобы учесть комментарии, сделанные ниже, я предлагаю объединить каждый суффикс с количеством подстрок, которые он представляет . В простом примере, подобном приведенному выше, это будет

4 abcd
3 bcd
2 bc
1 d

потому что, например, первый суффикс «abcd» представляет 4 подстроки «a», «ab», «abc», «abcd». Однако в более сложном примере, скажем, для строки «abcabxdabe», первые две записи массива суффиксов будут

10 abcabxdabe
1 abe

потому что вторая запись представляет подстроки "a", "ab" и "abe", но "a" и "ab" также представлены первой записью.

Как рассчитать количество подстрок, представленных в записи? -> Длина суффикса минус длина самого длинного префикса, который у него общий с предыдущим суффиксом. Например. в примере «abe» это 3 (его длина) минус 2 (длина «ab», самый длинный префикс, который он разделяет с предыдущей записью). Таким образом, эти числа могут быть сгенерированы за один проход по массиву суффиксов и даже быстрее, если вы также сгенерировали массив LCP (самый длинный общий префикс).

Следующим шагом будет генерация накопленных отсчетов:

10 abcabxdabe
11 abe
16 abxdabe
...

и затем найти эффективный способ использования накопленных отсчетов. Например. если вы хотите получить лексикографически 13-ю подстроку, вам нужно будет найти первую запись с накопленным счетчиком, большим или равным 13. Это будет «16 abxdabe» выше. Затем удалите префикс, который он разделяет с предыдущей записью (возвращает «xdabe»), а затем перейдите на позицию после 2-го символа (потому что предыдущая запись накопила количество 11 и 13-11 == 2), так что вы получите « abxd "как 13-я подстрока лексикографически.

Answer 2

Как уже было сказано, подстроки являются префиксами суффиксов.Иногда, возможно, вы захотите пойти другим путем и получить суффиксы префиксов.

Помимо этого, неясно, что вы ищете с помощью «уникальных подстрок».Я бы посоветовал вам поискать слова: тип, токен, максимальный, супермаксимальный.У вас не должно возникнуть проблем с их поиском в литературе по суффиксным массивам.

Answer 3

Вы должны использовать вариант «Три». По сути, если у вас есть ABCD, создайте дерево, которое представляет собой объединение путей: root-> A-> B-> C-> D, root-> B-> C-> D, root-> C-> D и root -> D. Теперь на каждом узле ведите список мест, где был обнаружен корень строки -> .-> .->.