Какой самый быстрый метод в python поиска наибольшего процентного расстояния Левенштейна между строкой и списком строк? - PullRequest
Новая
       9

Какой самый быстрый метод в python поиска наибольшего процентного расстояния Левенштейна между строкой и списком строк?

0 голосов
/ 01 марта 2020

Я пишу программу, которая сравнивает меньший список названий игр с основным списком многих игр, чтобы увидеть, какие игры в меньшем списке более точно соответствуют названиям игр в основном списке, чем другие. Чтобы сделать это, я проверил расстояние Левенштейна (в процентах) между каждой игрой в меньшем списке и каждой игрой в основном списке и взял максимум всех этих значений ( чем ниже максимальный процент, тем более уникальной должна быть игра) с использованием модулей difflib и fuzzywuzzy. Проблема, с которой я сталкиваюсь, состоит в том, что обычный поиск с использованием process.extractOne() или difflib.get_close_matches() занимает около 5+ секунд на игру (с 38000 строк в главном списке), и у меня есть около 4500 игр для поиска (5 * 4500 - это около 6 часов 15 минут, на что у меня нет времени).

В надежде найти лучший и более быстрый способ поиска по списку строк, я спрашиваю, что это за Самый быстрый метод в python поиска наибольшего процентного расстояния Левенштейна между строкой и списком строк - это. Если нет лучшего способа, чем использовать две функции, описанные выше, или написать какой-то другой код зацикливания, скажите, пожалуйста. 

metric = process.extractOne(name, master_names)[1] / 100
metric = fuzz.ratio(name, difflib.get_close_matches(name, master_names, 1, 0)[0]) / 100

1 Ответ

1 голос
/ 01 марта 2020

Путем экспериментов и дальнейших исследований я обнаружил, что самый быстрый метод проверки отношения Левенштейна - это сама библиотека python-Levenshtein. Функция Levenshtein.ratio() значительно быстрее (для одной игры весь поиск занимает в среднем всего 0,05 секунды) по сравнению с использованием любой функции в fuzzywuzzy или difflib, вероятно, из-за ее простоты и реализации C. Я использовал эту функцию в течение для l oop, перебирая каждое имя в главном списке, чтобы получить лучший ответ: 

from Levenshtein import ratio

metric = 0
for master_name in master_names:
    new_metric = ratio(name, master_name)
    if (new_metric > metric):
        metric = new_metric

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

...