Поиск ближайшего приближенного совпадения между двумя наборами названий

Question

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

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

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

Мои сопоставимые критерии в идеальном случае были бы отношением см>> 0,85 с первым именем, которое было бы найдено во втором имени как целое слово. Если эти критерии не выполняются, имя должно соответствовать самому себе.

Последний шаг, который я хотел бы реализовать, - это заменить исходную серию на эти согласованные имена.

Вот код для моего нынешнего подхода, пожалуйста, дайте мне знать, если это неясно, как я могу помочь уточнить:

stop_words = [ 
      'pharmaceuticals', 
      'pharmaceutical', 
      'pharma', 
      'therapeutic', 
      'biopharma', 
      'therapeutics', 
      'international', 
      'biotechnology', 
      'vaccines', 
      '\&', 
      '&', 
      'co.', 
      'co', 
      'biotherapeutics', 
      'biotherapeutic', 
      'life science', 
      'life sciences', 
      'laboratories', 
      'biologics', 
      ] 

temp_db_companies = db['Company'] 

def approximate_match(s1, s2): 
    return str(sm(None, str(s1).lower().strip(), str(s2).lower().strip()).ratio()) + '|' + str(s2).strip() 


def replace_val_w_best_match(df, col_initial, series_final, stop_words): 
    init_names = df[col_initial].str.lower().str.split(" ", expand=True).replace(stop_words, "").fillna('') 

    init_names = pd.Series(['' for n in range(len(init_names))]).str.cat([init_names[col] for col in init_names.columns], sep= " ").str.replace(' ', ' ').reset_index() 

    matching_df = pd.DataFrame(columns = list(init_names.columns) + list(series_final), data = init_names) 

    matching_df = pd.melt(matching_df, 
          id_vars = ['index', 0], 
          value_vars = list(series_final), 
          var_name = 'Comparators', 
          value_name = 'Best match') 

# matching = matching_df.apply(lambda row: approximate_match(row[0], row['Comparators']), axis = 1) 

    l = [(matching_df[0]), list(matching_df['Comparators'])] 

    ratio = [sm(None, name1, name2) for name1 in l[0] for name2 in l[1]] 

    match = [name2 for name1 in l[0] for name2 in l[1]] 

    print(ratio[:5]) 
    print(match[:5]) 

Answer 1

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

Заканчивать эту библиотеку: https://github.com/ztane/python-Levenshtein/

Библиотека Левенштейна имеет класс с именем StringMatcher.py разработан, чтобы помочь вам с этой проблемой.

Эта библиотека также включает в себя подобную функциональность: https://github.com/gfairchild/pyxDamerauLevenshtein