Zhandos
@Zhandos

Как можно реализовать нечеткий поиск в строке?

Здравствуйте!
Как вы думаете, можно ли использовать суффиксные деревья для поиска скажем так, сочетания символов в строке. Например в строке abcdef должна найтись подстрока cab и ей будет соответствовать подстрока abcdef, или найтись fed и ей будет соответствовать подстрока abcdef. То есть поиск подстроки не в чётком порядке символов. Когда как в суффиксном дереве порядок символов один из ключевых моментов его высокой производительности на поиск.

Суффиксные деревья вкратце: дерево где есть ветви для каждого суффикса подстроки, например для abcdef будут ветви a, b, ab, c, abc, bc, d, abcd, bcd, cd и т.д. Соответственно если мы ищём какую-либо подстроку, просто от корня идём по символам, если такая ветвь есть, значит подстрока существует, то есть по сути один проход на поиск.

Я ещё думал разбивать изначальную строку на подстроки определенной длины и вычислять их хеши, дальше уже при поиске смотреть, есть ли такой хэш, но что-то явно таких подстрок и их хешей получится много, ведь например в строке abcdef так же должна найтись подстрока cbd, её позиция в начальной строке на первом индексе

Или есть какие-то другие способы? Самый тупой и прямой конечно это линейный поиск.

Реальный кейс задачи
Над данным алгоритмом работаю для реализации поиска фраз в тексте, в примере выше для простоты, слова обозначены отдельными символами. Конечно, все слова как в фразах как и в тексте нормализованы. Нужно найти вхождение фраз (их тысячи) в тексте, при этом положения слов в фразе и в тексте могут не совпадать. Например: фраза "хороший утро" должна найтись в тексте "сегодня утро хороший".
Про sphinx и прочие тоже думал, но т.к. искомых фраз тысячи, искать их будет затратно по каждой фразе.

Спасибо!
  • Вопрос задан
  • 540 просмотров
Пригласить эксперта
Ответы на вопрос 2
@lebron32rus
Senior Software Engineer
Ответ написан
Комментировать
Алгоритм n-gramm, расстояние лвенштейна, а вообще по этому поводу есть очень хорошая статья на хабре https://habr.com/post/114997/
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы