Улучшить нечеткость - Соответствие имен в 2 списках - PullRequest
Новая
       49

Улучшить нечеткость - Соответствие имен в 2 списках

0 голосов
/ 03 марта 2019

Мое требование - найти подходящие имена для 2 списка.Один список имеет 400 имен, а второй список 90000 имен.Я получил желаемый результат, но процесс занимает более 35 минут.Как очевидно, существует 2 цикла for, поэтому для этого требуется O (N * N) операций, что является узким местом.Я удалил дубликаты в обоих списках.Можете ли вы помочь улучшить это.Я проверил много других вопросов, но как-то не смог реализовать это.Если вы думаете, что я только что пропустил чтение уже существующего поста, пожалуйста, укажите на это.Я сделаю все возможное, чтобы понять и воспроизвести это.

Ниже мой код 

from fuzzywuzzy import fuzz
infile=open('names.txt','r')
name=infile.readline()
name_list=[]
while name:
    name_list.append(name.strip())
    name=infile.readline()

print (name_list)

infile2=open('names2.txt','r')
name2=infile2.readline()
name_list2=[]
while name2:
    name_list2.append(name2.strip())
    name2=infile2.readline()

print (name_list2)

response = {}
for name_to_find in name_list:
    for name_master in name_list2:
        if fuzz.ratio(name_to_find,name_master) > 90:
            response[name_to_find] = name_master
            break

for key, value in response.items():
    print ("Key is ->" + key + "  Value is -> " + value)

Ответы [ 2 ]

0 голосов
/ 04 марта 2019

Не зная алгоритма, стоящего за fuzz, я сомневаюсь, что мы можем многое сделать, чтобы сократить асимптотическое время выполнения.Там могут быть некоторые приемы, чтобы обрезать явно плохие пары, но, вероятно, не намного дальше.Другой ответ предполагает, что вы выполняете точное совпадение, и не будет работать для нечеткого сопоставления строк.

То, что вы можете попытаться сделать, это попытаться пакетировать ваши вызовы, и надеяться, что fuzzywuzzy оптимизировал некоторую логику для пакетов в своемprocess.Что-то вроде 

from fuzzywuzzy import process

for name in names400:
    matches = filter(lambda x: x[1] > 90, process.extract(name, names90000, limit=90000))
    for match_name, score in matches:
         response[match_name] = name

Также обратите внимание, что на странице github для fuzzywuzzy говорится, что использование python levenshtein может ускорить вычисления в 4-10 раз.

0 голосов
/ 03 марта 2019

Наиболее очевидный подход - использовать хеш-таблицу.Псевдокод:

  1. Определение меньшего списка

  2. Создание хеш-таблицы на основе меньшего списка:

    hash1 ={name: 1 for name in name_list}

  3. Итерация по второму списку и проверка наличия ключей имени в первом списке:

    l = [name for name in name_list2 if name in hash1]

и все.вы получаете список имен, которые существуют в обоих списках

...