Минимальное расстояние Левенштейна между несколькими словами

Question

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

Пример запроса будет

поиска = «BNA» лат & долгота близки по результату я искал.

Существует право паб широтой и долготой называется BNA Brewing Co., ища BNA мои надежды было бы, что это проявляется первый (как BNA == BNA)

Я попробовал два разных способа

m = min([editdistance.eval(search, place_split) for place_split in place.name.split(' ') 
        if place_split not in string.punctuation]) 

возвращается без рейтинга на основе географического расстояния, только расстояние Левенштейна

• Кофе & Книги In Town Center
• Talk 'п' Кофе
• Raggedy Энн & Энди

и с учетом географической удаленности, вторичной по отношению к Левенштейн

• Формирователи Hair Salon & Spa
• Амора Day Spa
• Чистая эстетика и микропигментация

И

m = editdistance.eval(search, place.name) 

Первый возвращает без рейтинга на основе географического расстояния, только расстояние Левенштейна

• KFC
• МОО
• & W

и с принятием учетом географической удаленности, вторичной по отношению к Левенштейн

• & W
• & W
• KFC

Таким образом, вы можете видеть, что ни один из способов возвращаются ничего близкого к BNA Brewing Co. Какую логику я должен использовать, чтобы заставить ее что-то вернуть, когда условия поиска точно соответствуют одному из имен мест в моей базе данных?

Answer 1

Напомним, что расстояния Левенштейна подсчитывают количество замен, дополнений и удалений, необходимых для преобразования одной строки в другую.Из-за этого они часто сводятся к минимуму при сравнении строк одинаковой длины (потому что, даже если требуется много подстановок, вам не нужно добавлять или удалять кучу символов). Вы можете увидеть это в своем втором примере, где ваши лучшие выходы имеют ту же длину, что и ваша строка поиска (len("bna") == len("A&W")).

Если ваша поисковая строка всегда будет одним словом, ваша идея рассчитать расстояние для каждого слова в строке является хорошей, поскольку каждое слово, скорее всего, будет иметь такую ​​же длину, что и ваша строка поиска. Однако в настоящее время вы делаете сравнение с регистром, которое означает, что editdistance.eval('bna', 'BNA') == 3, которого я предполагаю, вы не хотите.

попробовать:

m = min([editdistance.eval(search.lower(), place_split.lower()) for place_split in place.name.split(' ') if place_split not in string.punctuation]) 

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