Алгоритм нечеткого поиска (алгоритм приблизительного сопоставления строк)

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

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

Это то, на что я смотрел до сих пор:

Большинство моих исследований постоянно указывают настроковые метрики"в Google и Stackoverflow, таких как:

Расстояние ЛевенштейнаРасстояние Дамерау-ЛевенштейнАлгоритм Нидлмана – Вунша

Однако это просто дает оценку того, каканалогичный 2 строки есть. Единственный способ, которым я могу думать о реализации этого какалгоритм поиска состоит в том, чтобы выполнить линейный поиск и выполнить алгоритм метрики строки для каждой строки и вернуть строки с оценками выше определенного порога. (Первоначально мои строки хранились в дереве trie, но это, очевидно, мне здесь не поможет!)

Хотя это не такая плохая идея для небольших списков, это было бы проблематично для списков с, скажем, 100 000 имен, и пользователь выполнил много запросов.

Другой алгоритм, на который я посмотрел, этоМетод проверки правописания, где вы просто делаете поиск всех потенциальных опечаток. Однако это также крайне неэффективно, так как требует более 75 000 слов для слова длиной 7 и количества ошибок только 2.

Что мне нужно?

Может кто-нибудь, пожалуйста, предложите мнехороший эффективный алгоритм нечеткого поиска, с:

Наименование алгоритмаКак это работает или ссылка на то, как это работаетПлюсы и минусы и когда это лучше всего использовать (необязательно)

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

Ответы на вопрос(4)

Ваш ответ на вопрос