模糊匹配算法

模糊字符串匹配是一种寻找近似匹配字符串的技术。它被广泛应用于拼写检查器、记录去重、主数据管理、抄袭检测、生物信息与 DNA 测序、垃圾邮件过滤、内容搜索、相似度匹配等场景。

本文将介绍几种用于此类模糊字符串匹配的算法——Levenshtein、Damerau-Levenshtein、Bitap 和 n-gram。详细的 Python 实现与代码可在 GitHub repo 的 Jupyter notebook 中找到。

（本内容曾作为 Women Who Code 数据科学会议于 2022 年 4 月进行分享。会议的录像已发布在 YouTube 上。）

字符串匹配或模糊匹配是一种用于寻找与给定模式或字符串近似匹配的文本的方法。它基于某些参数来评估两条记录真正匹配的可能性或概率。在下方的示例中，算法尝试将 5 个不同的变体与给定的字符串‘Microsoft Corporation’进行匹配，并根据它们与真实值的接近程度对每个变体进行评分。

按回车键或点击以查看完整图片

字符串/模糊匹配的应用示例

最常用的模糊匹配算法涉及计算字符串之间的编辑距离指标。Edit distance metric量化了_通过将其中一个字符串转换为另一个所需的最少操作次数，来衡量两个字符串的相异程度_。一些著名的距离度量标准包括：

• Levenshtein distance
• Damerau–Levenshtein distance
• Longest common subsequence
• Hamming distance
• Jaro distance

Bitap algorithm (shift-or, shift-and algorithm or Baeza-Yates–Gonnet algorithm) 用于判断给定文本中是否包含与给定模式“近似相等”的子串，同样利用了 Levenshtein 距离。它对相对较短的模式字符串非常高效。Bitap 算法是 Unix 系统中 agrep/grep 实用函数的核心。

n-gram 算法使用马尔可夫模型来预测文本序列中的下一个元素。n-gram 是以特定顺序排列的 n 个字符（单词、字母、符号等）的模式。在文本处理中，使用 n-grams 有助于捕捉与词序相关的信息。

Bitap 和 n-gram 算法的主要区别在于前者属于_在线（on-line）_方法，而后者属于_离线（off-line）_方法。在线算法无需索引即可进行搜索，因此在处理大规模数据时性能较低效。离线技术在搜索中引入索引机制，使搜索速度大幅提升，并广泛应用于文本处理领域。

其他常用的算法包括 Needleman–Wunsch 算法、Smith–Waterman 算法、BK Tree metric、Soundex 或 Metaphone（后者是一种语音算法）。

编辑距离metric（指标）用于衡量将其中一个词转换为另一个词所需的编辑操作次数。莱文斯坦距离是一种流行的计算编辑距离的方法。下图展示了莱文斯坦距离和达梅劳-莱文斯坦距离的工作原理以及两者之间的差异。

点击或按回车键全屏查看图片

莱文斯坦距离与达梅劳-莱文斯坦距离 点击或按回车键全屏查看图片

计算莱文斯坦距离与达梅劳-莱文斯坦距离 以下是该算法的数学原理说明。 点击或按回车键全屏查看图片

计算莱文斯坦距离背后的数学原理

莱文斯坦距离具有以下特性：

• 当且仅当两个字符串相等时，其值为零。
• 其值至少为两个字符串长度之差的绝对值。
• 其值不超过较长字符串的长度。
• 三角不等式：任意两个字符串之间的莱文斯坦距离不大于它们各自与第三个字符串的莱文斯坦距离之和。

点击或按回车键全屏查看图片

这是一种在线搜索方法（即无需索引的搜索），使用莱文斯坦距离来计算目标字符串与给定模式之间的近似匹配度。Bitap 算法对位掩码（bitmask，用于执行位运算的数据结构）进行位运算操作，速度极快。通过位掩码，多个位在单个位运算中可同时置为开或关，或在开和关之间翻转。该算法在短长度模式下表现最佳，这得益于其底层数据结构的支持。

注册 Medium 以免费获取该作者的更新。 订阅

记住我以便更快登录

_示例 1：
输入文本：womenwhocode，模式：code
输出：Pattern found at index: 8（在第 8 个索引处找到模式）

_示例 2：
输入文本：youareawesome，模式：youareamazing
输出：No Match（无匹配结果）

点击或按回车键全屏查看图片

这是我参考 GeekforGeeks 上的代码编写的 Bitap 搜索 Python 实现版本。 点击或按回车键全屏查看图片

这是我参考 GeekforGeeks 上的代码编写的 Bitap 搜索 Python 实现版本。

该算法以马尔可夫模型的形式预测文本序列中的下一个项目。它是一种离线搜索，即在索引上进行搜索，从而大幅提升了处理大数据时的计算效率。目前，n-gram 技术几乎被应用于所有的自然语言处理算法中。n-gram 是通过对字符串中连续出现的 n 个字符/词进行配对而生成的一组值。其目标是计算字符/词序列或句子的概率。 按回车键或点击查看全尺寸图片 n-gram 算法的数学原理 在本笔记本中，这些算法应用于一个简单的示例，以展示这些方法之间的相似之处与差异。