Алгоритм нечеткого поиска (алгоритм приблизительного сопоставления строк)
Я хочу создать алгоритм нечеткого поиска. Тем не менее, после нескольких часов исследований я действительно борюсь.
Я хочу создать алгоритм, который выполняет нечеткий поиск по списку названий школ.
Это то, на что я смотрел до сих пор:
Большинство моих исследований постоянно указывают настроковые метрики"в Google и Stackoverflow, таких как:
Расстояние ЛевенштейнаРасстояние Дамерау-ЛевенштейнАлгоритм Нидлмана – ВуншаОднако это просто дает оценку того, каканалогичный 2 строки есть. Единственный способ, которым я могу думать о реализации этого какалгоритм поиска состоит в том, чтобы выполнить линейный поиск и выполнить алгоритм метрики строки для каждой строки и вернуть строки с оценками выше определенного порога. (Первоначально мои строки хранились в дереве trie, но это, очевидно, мне здесь не поможет!)
Хотя это не такая плохая идея для небольших списков, это было бы проблематично для списков с, скажем, 100 000 имен, и пользователь выполнил много запросов.
Другой алгоритм, на который я посмотрел, этоМетод проверки правописания, где вы просто делаете поиск всех потенциальных опечаток. Однако это также крайне неэффективно, так как требует более 75 000 слов для слова длиной 7 и количества ошибок только 2.
Что мне нужно?
Может кто-нибудь, пожалуйста, предложите мнехороший эффективный алгоритм нечеткого поиска, с:
Наименование алгоритмаКак это работает или ссылка на то, как это работаетПлюсы и минусы и когда это лучше всего использовать (необязательно)Я понимаю, что все алгоритмы будут иметь свои плюсы и минусы и нетЛучший алгоритм.