python - Python中的模糊字符串匹配

Question

我有 2 个超过一百万个名字的列表，它们的命名约定略有不同。这里的目标是匹配那些相似的记录，具有 95% 置信度的逻辑。

我知道我可以利用一些库，例如 Python 中的 FuzzyWuzzy 模块。

然而，就处理而言，将 1 个列表中的每个字符串与另一个列表进行比较似乎会占用太多资源，在这种情况下，这似乎需要 100 万次乘以另一百万次迭代。

对于这个问题还有其他更有效的方法吗？

更新:

所以我创建了一个分桶函数并应用了一个简单的规范化来删除空格、符号并将值转换为小写等...

for n in list(dftest['YM'].unique()):
    n = str(n)
    frame = dftest['Name'][dftest['YM'] == n]
    print len(frame)
    print n
    for names in tqdm(frame):
            closest = process.extractOne(names,frame)

通过使用 pythons pandas，数据被加载到按年份分组的较小桶中，然后使用 FuzzyWuzzy 模块，process.extractOne 用于获得最佳匹配。

结果还是有些令人失望。在测试期间，上面的代码用于仅包含 5000 个名称的测试数据框，并且占用了将近一个小时。

测试数据被拆分。

• 姓名
• 出生日期年月

我正在按桶比较他们，他们的 YM 在同一个桶中。

问题可能是因为我使用的 FuzzyWuzzy 模块吗？感谢任何帮助。

Answer 1

这里有几个优化级别可以将这个问题从 O(n^2) 转化为更小的时间复杂度。

• 预处理:在第一遍中对列表进行排序，为每个字符串创建一个输出映射，映射的键可以是标准化字符串。规范化可能包括:

  • 小写转换，
  • 没有空格，去除特殊字符，
  • 尽可能将 unicode 转换为 ascii 等价物，使用 unicodedata.normalize或 unidecode模块)

  这将导致 "Andrew H. Smith"、"andrew h. smith"、"ándréw h. smith" 生成相同的 key “andrewhsmith”，并将您的数百万个名称集合减少为一组较小的唯一/相似分组名称。

您可以使用这个 utlity method规范化您的字符串(尽管不包括 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 个字符的 key 和 9 个字符的 key 以查看是否匹配 95%？你不可以。所以你可以创建匹配你的字符串的桶。例如5 个字符名称将匹配 4-6 个字符名称，6 个字符名称将匹配 5-7 个字符等。n 个字符键的 n+1，n-1 个字符限制对于大多数实际匹配来说是一个相当好的桶。

• 开始匹配:名称的大多数变体在规范化格式中将具有相同的第一个字符(例如 Andrew H Smith、ándréw h.smith 和 Andrew H. Smeeth 分别生成 key andrewhsmith、andrewhsmith 和 andrewhsmeeth。它们的第一个字符通常没有区别，因此您可以对以 a 开头的键与以 a 开头并落在长度范围内的其他键进行匹配。这将大大减少您的匹配时间。无需将键 andrewhsmith 与 bndrewhsmith 匹配，因为这样的首字母变体名称很少存在。

然后你可以使用类似 method 的东西(或 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