这里有几个级别的优化可以将这个问题从 O(n^2) 转变为更小的时间复杂度。
预处理：在第一遍对列表进行排序，为每个字符串创建一个输出映射，映射的键可以是标准化字符串。规范化可能包括：
这将导致"Andrew H Smith", "andrew h. smith","ándréw h. smith"生成相同的 key "andrewhsmith"，并将您的百万个名称集减少为一组较小的唯一/相似分组名称。
您可以使用此实用方法来规范化您的字符串（但不包括 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's SequenceMatcher and and jellyfish's 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