Здравствуйте!
Как вы думаете, можно ли использовать суффиксные деревья для поиска скажем так, сочетания символов в строке. Например в строке abcdef должна найтись подстрока cab и ей будет соответствовать подстрока abcdef, или найтись fed и ей будет соответствовать подстрока abcdef. То есть поиск подстроки не в чётком порядке символов. Когда как в суффиксном дереве порядок символов один из ключевых моментов его высокой производительности на поиск.
Суффиксные деревья вкратце: дерево где есть ветви для каждого суффикса подстроки, например для abcdef будут ветви a, b, ab, c, abc, bc, d, abcd, bcd, cd и т.д. Соответственно если мы ищём какую-либо подстроку, просто от корня идём по символам, если такая ветвь есть, значит подстрока существует, то есть по сути один проход на поиск.
Я ещё думал разбивать изначальную строку на подстроки определенной длины и вычислять их хеши, дальше уже при поиске смотреть, есть ли такой хэш, но что-то явно таких подстрок и их хешей получится много, ведь например в строке abcdef так же должна найтись подстрока cbd, её позиция в начальной строке на первом индексе
Или есть какие-то другие способы? Самый тупой и прямой конечно это линейный поиск.
Реальный кейс задачи
Над данным алгоритмом работаю для реализации поиска фраз в тексте, в примере выше для простоты, слова обозначены отдельными символами. Конечно, все слова как в фразах как и в тексте нормализованы. Нужно найти вхождение фраз (их тысячи) в тексте, при этом положения слов в фразе и в тексте могут не совпадать. Например: фраза "хороший утро" должна найтись в тексте "сегодня утро хороший".
Про sphinx и прочие тоже думал, но т.к. искомых фраз тысячи, искать их будет затратно по каждой фразе.
sim3x, регулярные выражение в данном кейсе едва ли применимы, но интересно будет почитать исходный код регулярных выражений и их алгоритмы, всё равно спасибо!
sim3x, я понимаю. Для примера в вакууме в топика возможно это применимо, но это просто упрощённый пример. Едва ли, например системы нечеткого поиска используют регулярки
sim3x, реальный кейс описан в конце вопроса. Слова в фразе и в тексте конечно все будут нормализованы.
В целом начальный алгоритм я думаю такой, для уменьшения количества потенциальных фраз. Сперва идёт поиск в базе фраз по всем словам из текста. Так мы получаем фразы, в которых присутствуют слова из текста. Дальше мы уже должны искать фразы в тексте, порядок слов в тексте и в фразе может не совпадать. При этом пересечения фраз быть не должно (это тривиально вычисляется по позициям).
