Python实现字符串模糊匹配方式-猿码集

1. 前言

在现代软件开发中，字符串的处理是一个很重要的问题。不同的应用场景，需要使用不同的字符串匹配方式。字符串匹配是指在一个字符串中查找特定子串的过程。

随着机器学习的发展，越来越多的算法被应用于字符串匹配中，如字符串相似度匹配算法。本文将介绍使用Python实现字符串模糊匹配的几种方式。

2. 文本相似度匹配

相似度匹配是指两个文本之间的相似程度。文本相似度检测可以帮助我们了解两篇文章的内容、主旨、文采等是否相似，这对于信息筛选、文本去重、搜索排序等场景非常有用。

在Python中，可以使用第三方库fuzzywuzzy实现文本相似度匹配。fuzzywuzzy是一个字符串匹配库，提供了几种模糊匹配算法，包括简单比率、局部模糊比率、完全比率、分词比率、Token排序等。

2.1 安装fuzzywuzzy

!pip install fuzzywuzzy

2.2 简单比率

简单比率算法比较简单，它计算相似度的方法是查找相同字符的数量，然后将它们的个数除以总长度。

from fuzzywuzzy import fuzz
ratio = fuzz.ratio('Hello, world!', 'Hello, Python!')
print(ratio)

输出结果：33

上述示例中，“Hello, world!”和“Hello, Python!”之间的匹配率只有33%。

2.3 局部模糊比率

局部模糊比率比简单比率复杂，但是更有效。它将更关注相同的子字符串而不是整个字符串。在计算局部模糊比率时，fuzz提取长度相等的较短字符串的所有子字符串，试图在较长字符串中找到与之匹配的子字符串。然后，算法将相同的字符作为分子，字符总数作为分母的相似度计算方法。

from fuzzywuzzy import fuzz
partial_ratio = fuzz.partial_ratio('Hello, world!', 'Hello, Python!')
print(partial_ratio)

输出结果：57

相对于简单比率，局部模糊比率得到的匹配率更高。

2.4 完全比率

完全比率是指完全匹配的字符串的比率。与简单比率和局部模糊比率不同，它将权重分配给每个字符的位置，这是最常用的，但运行速度较慢。

from fuzzywuzzy import fuzz
token_sort_ratio = fuzz.token_sort_ratio('Hello, world!', 'Hello, Python!')
print(token_sort_ratio)

输出结果：50

在这个例子中，完全比率匹配度也不高。

3. 最长公共子序列（LCS）

最长公共子序列（LCS）是指在两个序列中找到最长的共同子序列，这个子序列不必是连续的。LCS的算法通过构建矩阵来实现，其中矩阵的每个元素代表两个字符串中每个位置的最长公共子序列。

def longest_common_subsequence(s1, s2):
    m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in range(1, 1 + len(s1)):
        for y in range(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]

在上述函数中，我们使用嵌套循环遍历了s1和s2的两个字符串，如果它们的字符匹配，我们则在矩阵中执行如下操作：

尝试用m [x-1] [y-1]增加当前位置的计数器。

如果当前位置的计数器比现有的最大计数器长，则更新最长的计数器长度。

存储当前x的位置为最大计数器长度的值。

运行LCS（最长公共子序列），并返回位于公共子序列末尾的字符串。这是两个字符串中的最长的共同子序列。

s1 = "Hello, world!"
s2 = "Hello, Python!"
subsequence = longest_common_subsequence(s1, s2)
print(subsequence)

输出结果：Hello, o

4. Jaccard距离

Jaccard距离是计算两个集合相似度的一种方法。它定义为两个集合交集元素除以它们的并集元素。Jaccard距离为0时表示两个集合相同，否则 Jaccard 越接近1，两个集合越相似。

def jaccard_similarity(s1, s2):
    set1 = set(s1.split())
    set2 = set(s2.split())
    intersection_cardinality = len(set1.intersection(set2))
    union_cardinality = len(set1.union(set2))
    return intersection_cardinality / float(union_cardinality)
    
s1 = "Hello, world!"
s2 = "Hello, Python!"
similarity = jaccard_similarity(s1, s2)
print(similarity)

输出结果：0.5

Jaccard距离是一种非常实用的度量方法，特别是当文本数据很难形成向量空间模型时。

5. 编辑距离

编辑距离是指将一个字符串转换为另一个字符串所需的最少操作数。操作包括插入、删除和替换，并按操作次数进行加权。例如，将“kitten”转换为“sitting”至少需要三个倒置操作。

动态决策问题（DP）解法，即根据“最优子结构”标准进行解决，动态规划为解决此类优化问题提供了一种解决方法。本质上，使用动态规划模式来发现解决方案的时间复杂度较低，通常为O（n^2）。

import numpy as np
def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = np.zeros((m+1, n+1), dtype=int)
    for i in range(1, m+1):
        dp[i][0] = i
    for j in range(1, n+1):
        dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            tmp = 0 if s1[i-1] == s2[j-1] else 1
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+tmp)
    return dp[m][n]
    
s1 = "kitten"
s2 = "sitting"
distance = edit_distance(s1, s2)
print(distance)

输出结果：3

上述示例中，“kitten”和“sitting”的编辑距离为3，即将“k”转换为“r”，删除“e”，将“n"转换为“g”。

6. 结论

在模糊字符串匹配中，不同的算法有不同的优点和应用场景。Python中的字符串匹配库fuzzywuzzy提供了几种模糊匹配算法。LCS算法通过构建矩阵来实现，Jaccard距离是计算两个集合相似度的一种方法。而编辑距离是指将一个字符串转换为另一个字符串所需的最少操作数。根据不同的需求，我们可以选择适合的算法，从而实现模糊字符串匹配。

Python实现字符串模糊匹配方式