title: 字符串模糊匹配指南
subtitle: 字符串模糊匹配指南
date: 2020-11-23
author: NSX
catalog: true
tags:

  • 模糊匹配

字符串模糊匹配指南

  • textdistance: 30+传统的字面距离计算 √
  • difflib: Python自带的计算文本差异的辅助工具 √
  • fuzzywuzzy: 依据编辑算法计算两个序列之间的差异
  • strsimpy: 计算各种字符串距离的包
  • Fast Fuzzy Matching: 快

textdistance库 ❤❤❤

textdistance 库使用传统的字面匹配算法来综合评估两段文本的匹配程度！它使用30多种不同的算法计算序列的距离，提供了可用于模糊匹配算法的集合.

  1. # pip install textdistance
  2. import textdistance

All algorithms have some common methods:

  1. .distance(*sequences) — calculate distance between sequences.
  2. .similarity(*sequences) — calculate similarity for sequences.
  3. .maximum(*sequences) — maximum possible value for distance and similarity. For any sequence: distance + similarity == maximum.
  4. .normalized_distance(*sequences) — normalized distance between sequences. The return value is a float between 0 and 1, where 0 means equal, and 1 totally different.
  5. .normalized_similarity(*sequences) — normalized similarity for sequences. The return value is a float between 0 and 1, where 0 means totally different, and 1 equal.

Levenshtein距离

指两个字串之间，由一个转成另一个所需的最少编辑操作次数。

  1. textdistance.levenshtein("this test", "that test") # 2
  2. textdistance.levenshtein.normalized_similarity("this test", "that test") # 0.8

Jaccard 相似度

2020-11-23-字符串模糊匹配指南 - 图1

  1. >> textdistance.jaccard（tokens_1，tokens_2）

余弦相似度

余弦相似度是比较两个字符串的常用方法。该算法将字符串视为向量，并计算它们之间的余弦值。与上面的 Jaccard Similarity 相似，余弦相似度也忽略了要比较的字符串中的顺序。

  1. textdistance.cosine("apple", "ppale") # 1.0

2020-11-23-字符串模糊匹配指南 - 图2

difflib库 ❤❤❤

difflib —- 计算差异的辅助工具

此模块提供用于比较序列的类和函数，有以下内容：

class **difflib.SequenceMatcher**

这是一个灵活的类，可用于比较任何类型的序列对，只要序列元素为 hashable 对象。 其思路是找到不包含“垃圾”元素的最长连续匹配子序列；所谓“垃圾”元素是指其在某种意义上没有价值，例如空白行或空白符。然后同样的思路将递归地应用于匹配序列的左右序列片段。 这并不能产生最小编辑序列，但确实能产生在人们看来“正确”的匹配。

自动垃圾启发式计算: [SequenceMatcher](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher) 支持使用启发式计算来自动将特定序列项视为垃圾。 这种启发式计算会统计每个单独项在序列中出现的次数。 如果某一项（在第一项之后）的重复次数超过序列长度的 1% 并且序列长度至少有 200 项，该项会被标记为“热门”并被视为序列匹配中的垃圾。 这种启发式计算可以通过在创建 [SequenceMatcher](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher) 时将 autojunk 参数设为 False 来关闭。

class **difflib.Differ**

这个类的作用是比较由文本行组成的序列，并产生可供人阅读的差异或增量信息。 Differ 统一使用 [SequenceMatcher](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher) 来完成行序列的比较以及相似（接近匹配）行内部字符序列的比较。

[Differ](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.Differ) 增量的每一行均以双字母代码打头：

双字母代码 含义
'- ' 行为序列 1 所独有
'+ ' 行为序列 2 所独有
' ' 行在两序列中相同
'? ' 行不存在于任一输入序列

**difflib.get_close_matches**(word, possibilities, n=3, cutoff=0.6)

返回由最佳“近似”匹配构成的列表。

word 为一个指定目标近似匹配的序列（通常为字符串），possibilities 为一个由用于匹配 word 的序列构成的列表（通常为字符串列表）。可选参数 n (默认为 3) 指定最多返回多少个近似匹配； n 必须大于 0；可选参数 cutoff (默认为 0.6) 是一个 [0, 1] 范围内的浮点数。 与 word 相似度得分未达到该值的候选匹配将被忽略。候选匹配中（不超过 n 个）的最佳匹配将以列表形式返回，按相似度得分排序，最相似的排在最前面。

  1. >>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
  2. ['apple', 'ape']

**difflib.ndiff**(a, b, linejunk=None, charjunk=IS_CHARACTER_JUNK)

比较 a 和 b (字符串列表)；返回 [Differ](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.Differ) 形式的增量信息 (一个产生增量行的 generator)。

可选关键字形参 linejunk 和 charjunk 均为过滤函数 (或为 None)

SequenceMatcher 对象

[SequenceMatcher](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher) 类具有这样的构造器：

  • class difflib.SequenceMatcher(isjunk=None, a=’’, b=’’, autojunk=True)

可选参数isjunk必须是none（默认值）等同于传递lambda x:0；换句话说，不忽略任何元素；可选参数 autojunk 可用于启用自动垃圾启发式计算。

[SequenceMatcher](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher) 对象具有以下方法：

  • find_longest_match(alo, ahi, blo, bhi) √

源码解析。找出 a[alo:ahi] 和 b[blo:bhi] 中的最长匹配块。如果 isjunk 被省略或为 None，[find_longest_match()](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher.find_longest_match) 将返回 (i, j, k) 使得 a[i:i+k] 等于 b[j:j+k]

  1. >>> import difflib
  2. >>> s = difflib.SequenceMatcher(None, 'abcd', 'abcd abcd')
  3. >>> s.find_longest_match(0,4,0,9)
  4. Match(a=0, b=0, size=4)
  5. >>>
  • get_matching_blocks()

返回描述非重叠匹配子序列的三元组列表。 每个三元组的形式为 (i, j, n)，其含义为 a[i:i+n] == b[j:j+n]。 这些三元组按 i 和 j 单调递增排列。

最后一个三元组用于占位，其值为 (len(a), len(b), 0)。 它是唯一 n == 0 的三元组。 如果 (i, j, n) 和 (i', j', n') 是在列表中相邻的三元组，且后者不是列表中的最后一个三元组，则 i+n < i' 或 j+n < j'；换句话说，相邻的三元组总是描述非相邻的相等块。

  1. >>> s = difflib.SequenceMatcher(None, 'abxcd', 'abcd')
  2. >>> s.get_matching_blocks()
  3. [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
  • get_opcodes() √

返回描述如何将 a 变为 b 的 5 元组列表，每个元组的形式为 (tag, i1, i2, j1, j2)。 在第一个元组中 i1 == j1 == 0，而在其余的元组中 i1 等于前一个元组的 i2，并且 j1 也等于前一个元组的 j2。

tag 值为字符串，其含义如下：

值 含义
'replace' a[i1:i2]
应由 b[j1:j2]
替换。
'delete' a[i1:i2]
应被删除。 请注意在此情况下 j1 == j2
。
'insert' b[j1:j2]
应插入到 a[i1:i1]
。 请注意在此情况下 i1 == i2
。
'equal' a[i1:i2] == b[j1:j2]
(两个子序列相同)。

代码如下：

  1. >>> a = "qabxcd"
  2. >>> b = "abycdf"
  3. >>> s = SequenceMatcher(None, a, b)
  4. >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
  5. ...     print('{:7}   a[{}:{}] --> b[{}:{}] {!r:>8} --> {!r}'.format(
  6. ...         tag, i1, i2, j1, j2, a[i1:i2], b[j1:j2]))
  7. delete    a[0:1] --> b[0:0]      'q' --> ''
  8. equal     a[1:3] --> b[0:2]     'ab' --> 'ab'
  9. replace   a[3:4] --> b[2:3]      'x' --> 'y'
  10. equal     a[4:6] --> b[3:5]     'cd' --> 'cd'
  11. insert    a[6:6] --> b[5:6]       '' --> 'f'
  • ratio()

返回一个取值范围 [0, 1] 的浮点数作为序列相似性度量。

其中 T 是两个序列中元素的总数量，M 是匹配的数量，即 2.0*M / T。 请注意如果两个序列完全相同则该值为 1.0，如果两者完全不同则为 0.0。

如果 [get_matching_blocks()](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher.get_matching_blocks) 或 [get_opcodes()](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher.get_opcodes) 尚未被调用则此方法运算消耗较大，在此情况下你可能需要先调用 [quick_ratio()](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher.quick_ratio) 或 [real_quick_ratio()](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.SequenceMatcher.real_quick_ratio) 来获取一个上界。

  1. >>> s = difflib.SequenceMatcher(None, 'abcd', 'bcde')
  2. >>> s.ratio()
  3. 0.75
  4. >>> s.quick_ratio()
  5. 0.75

Differ 对象

这个类的作用是比较由文本行组成的序列，并产生可供人阅读的差异或增量信息。 Differ 统一使用 SequenceMatcher 来完成行序列的比较以及相似（接近匹配）行内部字符序列的比较。

[Differ](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.Differ) 类具有这样的构造器：

  • class difflib.``Differ(linejunk=None, charjunk=None)
    可选关键字形参 linejunk 和 charjunk 均为过滤函数 (或为 None)：

[Differ](https://docs.python.org/zh-cn/3.7/library/difflib.html#difflib.Differ) 对象是通过一个单独方法来使用（生成增量）的：

  • compare(a, b)
    比较两个由行组成的序列，并生成增量（一个由行组成的序列）。
    每个序列必须包含一个以换行符结尾的单行字符串。 这样的序列可以通过文件类对象的 readlines() 方法来获取。 所生成的增量同样由以换行符结尾的字符串构成，可以通过文件类对象的 writelines() 方法原样打印出来。

fuzzywuzzy

FuzzyWuzzy 是一个简单易用的模糊字符串匹配工具包。它依据 Levenshtein Distance 算法 计算两个序列之间的差异。

https://github.com/seatgeek/fuzzywuzzy、

导入库

  1. from fuzzywuzzy import fuzz
  2. from fuzzywuzzy import process

简单匹配

  1. >>> fuzz.ratio("this is a test", "this is a test!")
  2.     97

非完全匹配

  1. >>> fuzz.partial_ratio("this is a test", "this is a test!")
  2.     100

忽略顺序匹配

  1. >>> fuzz.ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
  2.     91
  3. >>> fuzz.token_sort_ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
  4.     100

去重子集匹配

  1. >>> fuzz.token_sort_ratio("fuzzy was a bear", "fuzzy fuzzy was a bear")
  2.     84
  3. >>> fuzz.token_set_ratio("fuzzy was a bear", "fuzzy fuzzy was a bear")
  4.     100

Process返回模糊匹配的字符串和相似度

  1. >>> choices = ["Atlanta Falcons", "New York Jets", "New York Giants", "Dallas Cowboys"]
  2. >>> process.extract("new york jets", choices, limit=2)
  3.     [('New York Jets', 100), ('New York Giants', 78)]
  4. >>> process.extractOne("cowboys", choices)
  5.     ("Dallas Cowboys", 90)

可以传入附加参数到 extractOne 方法来设置使用特定的匹配模式，一个典型的用法是来匹配文件路径

  1. >>> process.extractOne("System of a down - Hypnotize - Heroin", songs)
  2.     ('/music/library/good/System of a Down/2005 - Hypnotize/01 - Attack.mp3', 86)
  3. >>> process.extractOne("System of a down - Hypnotize - Heroin", songs, scorer=fuzz.token_sort_ratio)
  4.     ("/music/library/good/System of a Down/2005 - Hypnotize/10 - She's Like Heroin.mp3", 61)

strsimpy

这是一个用于计算各种字符串距离的包。其使用方法如下：

  1. from strsimpy.levenshtein import Levenshtein
  2. levenshtein = Levenshtein()
  3. print(levenshtein.distance('My string', 'My $string'))
  6. from strsimpy.normalized_levenshtein import NormalizedLevenshtein
  7. normalized_levenshtein = NormalizedLevenshtein()
  8. print(normalized_levenshtein.distance('My string', 'My $string'))
  9. print(normalized_levenshtein.similarity('My string', 'My $string'))
  12. # 带权重的编辑距离
  13. from strsimpy.weighted_levenshtein import WeightedLevenshtein
  14. from strsimpy.weighted_levenshtein import CharacterSubstitutionInterface
  15. class CharacterSubstitution(CharacterSubstitutionInterface):
  16.     def cost(self, c0, c1):
  17.         if c0=='t' and c1=='r':
  18.             return 0.5
  19.         return 1.0
  20. weighted_levenshtein = WeightedLevenshtein(CharacterSubstitution())
  21. print(weighted_levenshtein.distance('String1', 'String2'))
  24. from strsimpy.damerau import Damerau
  25. damerau = Damerau()
  26. print(damerau.distance('ABCDEF', 'ABDCEF'))
  29. # 最优化对齐后的编辑距离
  30. from strsimpy.optimal_string_alignment import OptimalStringAlignment
  31. optimal_string_alignment = OptimalStringAlignment()
  32. print(optimal_string_alignment.distance('CA', 'ABC'))
  35. from strsimpy.jaro_winkler import JaroWinkler
  36. jarowinkler = JaroWinkler()
  37. print(jarowinkler.similarity('My string', 'My tsring'))
  40. # 最长公共子序列
  41. from strsimpy.longest_common_subsequence import LongestCommonSubsequence
  42. lcs = LongestCommonSubsequence()
  43. print(lcs.distance('AGCAT', 'GAC'))
  46. from strsimpy.metric_lcs import MetricLCS
  47. metric_lcs = MetricLCS()
  48. s1 = 'ABCDEFG'
  49. s2 = 'ABCDEFHJKL'
  50. print(metric_lcs.distance(s1, s2))
  53. # ngram
  54. from strsimpy.ngram import NGram
  55. twogram = NGram(2)
  56. print(twogram.distance('ABCD', 'ABTUIO'))
  57. s1 = 'Adobe CreativeSuite 5 Master Collection from cheap 4zp'
  58. s2 = 'Adobe CreativeSuite 5 Master Collection from cheap d1x'
  59. fourgram = NGram(4)
  60. print(fourgram.distance(s1, s2))
  63. from strsimpy.qgram import QGram
  64. qgram = QGram(2)
  65. print(qgram.distance('ABCD', 'ABCE'))
  68. from strsimpy.cosine import Cosine
  69. cosine = Cosine(2)
  70. s0 = 'My first string'
  71. s1 = 'My other string...'
  72. p0 = cosine.get_profile(s0)
  73. p1 = cosine.get_profile(s1)
  74. print(cosine.similarity_profiles

Fast Fuzzy Matching

通过 ngram 寻找紧密匹配的对象。这种查找紧密匹配的方法不仅应该非常有效，而且还可以通过其对整个数据中不太常见的字符组更加重视的能力来产生高质量的匹配项。

使用字符串相似性度量，例如Jaro-Winkler或Levenshtein距离度量，存在着一个明显的问题，就是所需的计算量呈二次方增长（必须将每个条目与数据集中的每个其他条目进行比较）。该方法最大的优势是速度，使用 TF-IDF、N-Grams 和稀疏矩阵乘法更快地完成模糊匹配！

示例代码：

https://bergvca.github.io/2017/10/14/super-fast-string-matching.html

参考

字符串模糊匹配的方法都有哪些