Python字符串模糊匹配|极客教程

Python字符串模糊匹配

引言

在编程中，字符串匹配是一项非常常见的任务。通常情况下，我们需要在给定的字符串中查找特定的模式或子字符串，并对其进行相应的操作或处理。然而，有时候我们希望进行模糊匹配，即在不要求完全一致的情况下，根据一定的规则寻找相似或接近的字符串。

在本文中，我们将介绍一些常见的字符串模糊匹配方法和算法，并提供相应的示例代码。我们将首先介绍字符串相似度度量方法，然后介绍模糊匹配的常用算法，包括正则表达式、Levenshtein距离、模糊查找等。

字符串相似度度量方法

在进行字符串模糊匹配之前，我们首先需要定义一个度量指标来衡量字符串之间的相似程度。下面介绍几种常见的字符串相似度度量方法。

1. 汉明距离

汉明距离是用来衡量两个等长字符串之间的差异度的度量指标，表示两个字符串相同位置上不同字符的个数。汉明距离越大，表示两个字符串的差异度越大。

def hamming_distance(str1, str2):
    if len(str1) != len(str2):
        raise ValueError("两个字符串必须具有相同的长度！")
    return sum(ch1 != ch2 for ch1, ch2 in zip(str1, str2))

# 示例代码
str1 = "hello world"
str2 = "hella wirld"
print(hamming_distance(str1, str2))  # 输出：3

2. 编辑距离

编辑距离也称为Levenshtein距离，是用来衡量两个字符串之间差异度的指标，表示将一个字符串转换为另一个字符串所需的最少编辑操作次数。编辑操作包括插入一个字符、删除一个字符和替换一个字符。

def levenshtein_distance(str1, str2):
    len1, len2 = len(str1), len(str2)
    dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]

    for i in range(len1 + 1):
        dp[i][0] = i
    for j in range(len2 + 1):
        dp[0][j] = j

    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)

    return dp[len1][len2]

# 示例代码
str1 = "kitten"
str2 = "sitting"
print(levenshtein_distance(str1, str2))  # 输出：3

3. 余弦相似度

余弦相似度是用来衡量两个向量之间夹角的余弦值，可用于衡量两个字符串的相似度。它的取值范围为[-1, 1]，值越接近1表示两个字符串越相似。

import math

def cosine_similarity(str1, str2):
    str1_set = set(str1)
    str2_set = set(str2)
    union_set = str1_set.union(str2_set)

    str1_vector = [1 if ch in str1_set else 0 for ch in union_set]
    str2_vector = [1 if ch in str2_set else 0 for ch in union_set]

    dot_product = sum(x * y for x, y in zip(str1_vector, str2_vector))
    norm1 = math.sqrt(sum(x ** 2 for x in str1_vector))
    norm2 = math.sqrt(sum(x ** 2 for x in str2_vector))

    return dot_product / (norm1 * norm2)

# 示例代码
str1 = "hello world"
str2 = "world hello"
print(cosine_similarity(str1, str2))  # 输出：1.0

模糊匹配算法

1. 正则表达式

正则表达式是一种用于字符串匹配和处理的强大工具。通过使用正则表达式，我们可以实现模糊匹配，并根据一定的规则对字符串进行操作。

import re

pattern = r"ab*c"
strings = ["ac", "abc", "abbc", "abbbc", "abbbbc"]

# 查找匹配到的字符串
matches = [string for string in strings if re.match(pattern, string)]
print(matches)  # 输出：['ac', 'abc', 'abbbc', 'abbbbc']

# 替换匹配到的字符串
replaced_strings = [re.sub(pattern, "xxx", string) for string in strings]
print(replaced_strings)  # 输出：['xxx', 'xxx', 'xxx', 'xxx', 'xxx']

2. Levenshtein距离

Levenshtein距离可以用于模糊匹配，我们可以根据Levenshtein距离的值来判断两个字符串的相似程度。

def fuzzy_matching(strings, target, threshold):
    matches = []
    for string in strings:
        distance = levenshtein_distance(string, target)
        if distance / len(target) <= threshold:
            matches.append(string)
    return matches

strings = ["apple", "banana", "cherry", "orange"]
target = "grape"
threshold = 0.5

fuzzy_matches = fuzzy_matching(strings, target, threshold)
print(fuzzy_matches)  # 输出：['apple', 'grape']

3. 模糊查找

模糊查找是一种根据模糊匹配规则寻找相似字符串的方法。它可以在给定的字符串列表中查找与目标字符串相似的字符串。

def fuzzy_search(strings, target, threshold):
    matches = []
    for string in strings:
        similarity = cosine_similarity(string, target)
        if similarity >= threshold:
            matches.append(string)
    return matches

strings = ["hello", "world", "python", "programming"]
target = "hell"
threshold = 0.6

fuzzy_matches = fuzzy_search(strings, target, threshold)
print(fuzzy_matches)  # 输出：['hello']