Python中的模糊字符串匹配

Question

我有两个超过一百万个名称的列表,命名约定略有不同.这里的目标是匹配那些相似的记录,具有95%置信度的逻辑.

我知道有一些我可以利用的库,比如Python中的FuzzyWuzzy模块.

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

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

更新:

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

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用于获得最佳匹配.

结果仍然有点令人失望.在测试期间,上面的代码用于仅包含5千个名称的测试数据框,并且占用将近一个小时.

测试数据被拆分.

• 名称
• 出生日期的年月

我正在用他们的YM在同一桶中的桶进行比较.

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

Answer 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因为这样的名称变体与第一个字母很少存在.

然后你可以在这个方法(或模糊模糊模块)的行上使用一些东西来找到字符串相似百分比,你可以排除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