Ответ 1
Существует несколько уровней оптимизации, чтобы превратить эту проблему из O (n ^ 2) в меньшую временную сложность.
-
Предварительная обработка. Сортировка списка в первом проходе, создание выходной карты для каждой строки, ключ для карты может быть нормированной строкой. Нормализация может включать:
- преобразование в нижнем регистре,
- нет пробелов, удаление специальных символов,
- преобразуйте unicode в эквиваленты ascii, если это возможно, используйте unicodedata.normalize или unidecode)
Это приведет к
"Andrew H Smith","andrew h. smith","ándréw h. smith"созданию одного и того же ключа"andrewhsmith"и уменьшит ваш набор миллионов имен до меньшего набора уникальных/похожих сгруппированных имен.
Вы можете использовать этот метод utlity для нормализации вашей строки (не включая часть unicode):
def process_str_for_similarity_cmp(input_str, normalized=False, ignore_list=[]):
""" Processes string for similarity comparisons , cleans special characters and extra whitespaces
if normalized is True and removes the substrings which are in ignore_list)
Args:
input_str (str) : input string to be processed
normalized (bool) : if True , method removes special characters and extra whitespace from string,
and converts to lowercase
ignore_list (list) : the substrings which need to be removed from the input string
Returns:
str : returns processed string
"""
for ignore_str in ignore_list:
input_str = re.sub(r'{0}'.format(ignore_str), "", input_str, flags=re.IGNORECASE)
if normalized is True:
input_str = input_str.strip().lower()
#clean special chars and extra whitespace
input_str = re.sub("\W", "", input_str).strip()
return input_str
-
Теперь аналогичные строки будут уже находиться в том же ведре, если их нормализованный ключ будет таким же.
-
Для дальнейшего сравнения вам нужно будет сравнивать только ключи, а не имена. например
andrewhsmithиandrewhsmeeth, так как это сходство имен потребуется нечеткая строка, отличная от нормализованной сравнение сделано выше. -
Bucketing: Вам действительно нужно сравнить 5-значный ключ с 9-значным ключом, чтобы узнать, соответствует ли это 95%? Нет, ты не. Таким образом, вы можете создавать ведра, соответствующие вашим строкам. например 5 имен символов будут сопоставляться с 4-6 символьными именами, 6 символами с 5-7 символами и т.д. Предел символа n + 1, n-1 для символьной клавиши является достаточно хорошим ведром для наиболее практичного сопоставления.
-
Начало совпадения. Большинство вариантов имен будут иметь один и тот же первый символ в нормализованном формате (например,
Andrew H Smith,ándréw h. smithиAndrew H. Smeethсгенерировать ключиandrewhsmith,andrewhsmithиandrewhsmeethсоответственно. Обычно они не будут отличаться от первого символа, поэтому вы можете запускать соответствие для клавиш, начинающихся сa, другим клавишам, начинающимся сa, и попадать в ведра длины. Это значительно сократит время согласования. Нет необходимости сопоставлять ключandrewhsmithсbndrewhsmith, поскольку такое изменение имени с первой буквой редко будет существовать.
Затем вы можете использовать что-то в строках этого метода (или модуль FuzzyWuzzy), чтобы найти процент сходства строк, вы можете исключить один из jaro_winkler или difflib для оптимизации скорости и качества результата:
def find_string_similarity(first_str, second_str, normalized=False, ignore_list=[]):
""" Calculates matching ratio between two strings
Args:
first_str (str) : First String
second_str (str) : Second String
normalized (bool) : if True ,method removes special characters and extra whitespace
from strings then calculates matching ratio
ignore_list (list) : list has some characters which has to be substituted with "" in string
Returns:
Float Value : Returns a matching ratio between 1.0 ( most matching ) and 0.0 ( not matching )
using difflib SequenceMatcher and and jellyfish jaro_winkler algorithms with
equal weightage to each
Examples:
>>> find_string_similarity("hello world","Hello,World!",normalized=True)
1.0
>>> find_string_similarity("entrepreneurship","entreprenaurship")
0.95625
>>> find_string_similarity("Taj-Mahal","The Taj Mahal",normalized= True,ignore_list=["the","of"])
1.0
"""
first_str = process_str_for_similarity_cmp(first_str, normalized=normalized, ignore_list=ignore_list)
second_str = process_str_for_similarity_cmp(second_str, normalized=normalized, ignore_list=ignore_list)
match_ratio = (difflib.SequenceMatcher(None, first_str, second_str).ratio() + jellyfish.jaro_winkler(unicode(first_str), unicode(second_str)))/2.0
return match_ratio