#string #algorithm #dictionary #string-search #suffix-tree
Вопрос:
В настоящее время я сталкиваюсь с проблемой, связанной с наиболее эффективным способом поиска слов в корпусе, содержащем определенную подстроку.
Например, учитывая совокупность :
Apple Appstore Deapp macbook noapp карандаш ластик для мыши
и если я хочу найти слова, содержащие подстроку «приложение», я хочу получить слова, содержащие «приложение», среди корпуса, независимо от того, в какой позиции они находятся.
Похоже, что создание дерева суффиксов эффективно при поиске подстроки, но поскольку ввод состоит из нескольких чисел слов, я очень сомневаюсь, следует ли мне создавать несколько чисел дерева суффиксов, что кажется неэффективным.
Кто-нибудь может помочь, пожалуйста?
Большое Спасибо!
Комментарии:
1. Вы могли бы посмотреть через Ахо-Корасика. Это O(n). Википедия — хорошее начало en.wikipedia.org/wiki/Aho–Corasick_algorithm