Python 中的模糊字符串匹配
Fuzzy string matching in Python
我有 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 模块吗？感谢任何帮助。
您必须索引或规范化字符串以避免 O(n^2) 运行。基本上，您必须将每个字符串映射到一个范式，并构建一个反向字典，将所有单词链接到相应的范式。
让我们考虑 'world' 和 'word' 的正规形式是相同的。因此，首先构建 Normalized -> [word1, word2, word3], 的反向字典，例如：
"world" <-> Normalized('world')
"word" <-> Normalized('wrd')
to:
Normalized('world') -> ["world", "word"]
好了 - 规范化字典中具有多个值的所有项目（列表）都是匹配的词。
归一化算法取决于数据，即文字。考虑其中之一：
- Soundex
- Metaphone
- Double Metaphone
- NYSIIS
- Caverphone
- 科隆注音
- MRA 抄本
这里有几个优化级别可以将这个问题从 O(n^2) 转化为更小的时间复杂度。
预处理：在第一遍中对列表进行排序，为每个字符串创建一个输出映射，映射的键可以是规范化字符串。
规范化可能包括：
- 小写转换，
- 没有空格，删除了特殊字符，
- 尽可能将 unicode 转换为 ascii 等价物，使用 unicodedata.normalize or unidecode 模块）
这将导致 "Andrew H Smith"、"andrew h. smith"、"ándréw h. smith" 生成相同的密钥 "andrewhsmith"，并将您的百万名称集减少到更小的 unique/similar 分组名称.
您可以使用此 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 个字符的密钥和 9 个字符的密钥以查看是否匹配 95% ？你不可以。
所以你可以创建匹配你的字符串的桶。例如5 个字符名称将匹配 4-6 个字符名称，6 个字符名称将匹配 5-7 个字符等。n 个字符键的 n+1，n-1 个字符限制对于大多数实际匹配来说是一个相当好的桶。
开始匹配：名称的大多数变体在规范化格式中将具有相同的第一个字符（例如Andrew H Smith、ándréw h. smith、和 Andrew H. Smeeth 分别生成密钥 andrewhsmith、andrewhsmith 和 andrewhsmeeth。
它们的第一个字符通常没有区别，因此您可以 运行 将以 a 开头的键与其他以 a 开头的键匹配，并落在长度范围内。这将大大减少您的匹配时间。无需将键 andrewhsmith 与 bndrewhsmith 匹配，因为这样的首字母变体名称很少存在。
然后你可以使用类似 method ( or FuzzyWuzzy module ) to find string similarity percentage, you may exclude one of 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
特定于 fuzzywuzzy，请注意目前 process.extractOne 默认为 WRatio，这是迄今为止最慢的算法，处理器默认为 utils.full_process。如果你传入 fuzz.QRatio 作为你的记分员，它会更快，但不会那么强大，具体取决于你要匹配的内容。不过，对于名字来说可能还不错。我个人对 token_set_ratio 很幸运，它至少比 WRatio 快一些。您也可以预先对所有选择 运行 utils.full_process() 然后 运行 它与 fuzz.ratio 作为您的记分员和处理器=None 跳过处理步骤. （见下文）如果您只是使用基本比率函数，那么 fuzzywuzzy 可能有点矫枉过正。 Fwiw 我有一个 JavaScript 端口（fuzzball.js），您也可以在其中预先计算令牌集并使用它们而不是每次都重新计算。）
这不会减少比较的绝对数量，但会有所帮助。 （这可能是 BK 树？我自己也在研究同样的情况）
另外一定要安装 python-Levenshtein 以便使用更快的计算。
**下面的行为可能会改变，正在讨论中的开放问题等**
fuzz.ratio 没有 运行 完整的过程，token_set 和 token_sort 函数接受 full_process=False 参数，如果你不't set Processor=None extract 函数无论如何都会尝试 运行 完整进程。可以使用 functools 的 partial 以 full_process=False 作为你的记分员，然后 运行 utils.full_process 预先选择 fuzz.token_set_ratio。
我有 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 模块吗？感谢任何帮助。
您必须索引或规范化字符串以避免 O(n^2) 运行。基本上，您必须将每个字符串映射到一个范式，并构建一个反向字典，将所有单词链接到相应的范式。
让我们考虑 'world' 和 'word' 的正规形式是相同的。因此，首先构建 Normalized -> [word1, word2, word3], 的反向字典，例如：
"world" <-> Normalized('world')
"word" <-> Normalized('wrd')
to:
Normalized('world') -> ["world", "word"]
好了 - 规范化字典中具有多个值的所有项目（列表）都是匹配的词。
归一化算法取决于数据，即文字。考虑其中之一：
- Soundex
- Metaphone
- Double Metaphone
- NYSIIS
- Caverphone
- 科隆注音
- MRA 抄本
这里有几个优化级别可以将这个问题从 O(n^2) 转化为更小的时间复杂度。
预处理：在第一遍中对列表进行排序，为每个字符串创建一个输出映射，映射的键可以是规范化字符串。 规范化可能包括：
- 小写转换，
- 没有空格，删除了特殊字符，
- 尽可能将 unicode 转换为 ascii 等价物，使用 unicodedata.normalize or unidecode 模块）
这将导致
"Andrew H Smith"、"andrew h. smith"、"ándréw h. smith"生成相同的密钥"andrewhsmith"，并将您的百万名称集减少到更小的 unique/similar 分组名称.
您可以使用此 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 个字符的密钥和 9 个字符的密钥以查看是否匹配 95% ？你不可以。 所以你可以创建匹配你的字符串的桶。例如5 个字符名称将匹配 4-6 个字符名称，6 个字符名称将匹配 5-7 个字符等。n 个字符键的 n+1，n-1 个字符限制对于大多数实际匹配来说是一个相当好的桶。
开始匹配：名称的大多数变体在规范化格式中将具有相同的第一个字符（例如
Andrew H Smith、ándréw h. smith、和Andrew H. Smeeth分别生成密钥andrewhsmith、andrewhsmith和andrewhsmeeth。 它们的第一个字符通常没有区别，因此您可以 运行 将以a开头的键与其他以a开头的键匹配，并落在长度范围内。这将大大减少您的匹配时间。无需将键andrewhsmith与bndrewhsmith匹配，因为这样的首字母变体名称很少存在。
然后你可以使用类似 method ( or FuzzyWuzzy module ) to find string similarity percentage, you may exclude one of 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
特定于 fuzzywuzzy，请注意目前 process.extractOne 默认为 WRatio，这是迄今为止最慢的算法，处理器默认为 utils.full_process。如果你传入 fuzz.QRatio 作为你的记分员，它会更快，但不会那么强大，具体取决于你要匹配的内容。不过，对于名字来说可能还不错。我个人对 token_set_ratio 很幸运，它至少比 WRatio 快一些。您也可以预先对所有选择 运行 utils.full_process() 然后 运行 它与 fuzz.ratio 作为您的记分员和处理器=None 跳过处理步骤. （见下文）如果您只是使用基本比率函数，那么 fuzzywuzzy 可能有点矫枉过正。 Fwiw 我有一个 JavaScript 端口（fuzzball.js），您也可以在其中预先计算令牌集并使用它们而不是每次都重新计算。）
这不会减少比较的绝对数量，但会有所帮助。 （这可能是 BK 树？我自己也在研究同样的情况）
另外一定要安装 python-Levenshtein 以便使用更快的计算。
**下面的行为可能会改变，正在讨论中的开放问题等**
fuzz.ratio 没有 运行 完整的过程，token_set 和 token_sort 函数接受 full_process=False 参数，如果你不't set Processor=None extract 函数无论如何都会尝试 运行 完整进程。可以使用 functools 的 partial 以 full_process=False 作为你的记分员，然后 运行 utils.full_process 预先选择 fuzz.token_set_ratio。