string - fuzzy search js




Нечеткий алгоритм поиска(приближенный алгоритм сопоставления строк) (2)

Вы вводите в заблуждение алгоритмы нечеткого поиска с реализацией: нечеткий поиск слова может вернуть 400 результатов всех слов, которые имеют расстояние Левенштейна, скажем, 2. Но для пользователя вам нужно отображать только верхние 5-10.

Поэтапно, вы предварительно обработаете все слова в словаре и сохраните результаты в БД. Популярные слова (и их нечеткие) будут сохранены в кэш-слое, поэтому вам не придется ударять DB для каждого запроса.

Вы можете добавить слой AI, который добавит самые распространенные орфографические ошибки и добавит их в БД. И так далее.

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

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

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

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

  • Расстояние Левенштейн
  • Расстояние Дамерау-Левенштейн
  • Алгоритм Needleman-Wunsch

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

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

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

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

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

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

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


Учитывая, что вы пытаетесь сделать нечеткий поиск в списке школьных имен, я не думаю, что вы хотите пойти на традиционное сходство строк, например, расстояние Левенштейна. Мое предположение заключается в том, что вы вводите пользовательский ввод (либо ввод с клавиатуры, либо разговор по телефону), и вы хотите быстро найти подходящую школу.

Показатели расстояния указывают, как похожие две строки основаны на подстановках, удалениях и вставках. Но эти алгоритмы на самом деле не говорят вам о том, насколько похожи строки как слова на человеческом языке.

Рассмотрим, например, слова «кузнец», «smythe» и «smote». Я могу перейти от «smythe» к «кузнецу» двумя шагами:

smythe -> smithe -> smith

И от «ударить» до «кузнеца» двумя шагами:

smote -> smite -> smith

Таким образом, они имеют то же расстояние, что и строки , но, как слова , они существенно отличаются друг от друга. Если кто-то сказал вам (разговорный язык), что он ищет «Колледж Симте», вы почти наверняка скажете: «О, я думаю, вы имеете в виду Смита». Но если бы кто-то сказал «Колледж Смотта», ты бы не знал, о чем он говорит.

Вам нужен фонетический алгоритм, например Soundex или Metaphone . В принципе, эти алгоритмы разбивают слово на фонемы и создают представление о том, как слово произносится на разговорном языке. Затем вы можете сравнить результат с известным списком слов, чтобы найти совпадение.

Такая система будет намного быстрее, чем использование метрики расстояния. Учтите, что с метрикой расстояния вам нужно сравнить вход пользователя с каждым словом в вашем списке, чтобы получить расстояние. Это вычислительно дорого, и результаты, которые я продемонстрировал с помощью «кузнец» и «удар», могут быть смехотворно плохими.

Используя фонетический алгоритм, вы создаете представление фонемы каждого из ваших известных слов и помещаете его в словарь (хеш-карту или, возможно, три). Это одноразовая стоимость запуска. Затем, всякий раз, когда пользователь вводит поисковый запрос, вы создаете представление фонемы своего ввода и просматриваете его в своем словаре. Это намного быстрее и дает гораздо лучшие результаты.

Учтите также, что, когда люди ошибочно набирают имена, они почти всегда получают первую букву вправо, и чаще, чем не произнесение орфографических звуков, похожее на фактическое слово, которое они пытались записать. Если это так, то фонетические алгоритмы - определенно путь.





fuzzy-search