Как изменить массив суффикса для поиска нескольких строк?

Question

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

Предположим, я пытаюсь реализовать простой поиск подстроки по списку слов и хочу вернуть список слов, соответствующих заданной подстроке. Наивный подход, казалось бы, заключается в том, чтобы вставить лексикографический конечный символ «$» между словами в моем списке, объединить их все вместе и создать дерево суффикса из результата. Но это, по-видимому, порождает большое количество нерелевантных записей. Если я создам исходную строку «банановый $ muffin», тогда я в конечном итоге создаю суффиксы для «ana $ muffin», которые я никогда не буду использовать.

Я хотел бы получить любые подсказки относительно того, как это сделать, или, еще лучше, указатель на некоторые тексты алгоритмов, которые обрабатывают этот случай.

Answer 1

В массивах суффикса вы обычно не используете строки, только одну строку. Это будет конкатенированная версия нескольких строк с некоторыми endtoken (другая для каждой строки). Для массивов суффикса вы используете указатели (или индекс массива) для ссылки на суффикс (требуется только позиция для первого маркера/символа). Таким образом, требуемое пространство - это массив + для каждого суффикса указатель. (это просто довольно простая реализация, вы должны сделать больше, чтобы получить больше производительности).

В этом случае вы можете оптимизировать алгоритм сортировки для суффиксов, так как вам нужно только отсортировать эти суффиксы, на которые ссылаются указатели, до конца. Все, что стоит за endtoken, не нужно использовать в алгоритме сортировки.

Answer 2

После прочтения большей части книги Алгоритмы на строках, деревьях и последовательностях Дэн Гусфилд, ответ кажется ясным.

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

Полученная структура по-прежнему полезна, но не так эффективна, как обычный массив суффикса.