NormalizedLevenshtein 是 strsimpy 库中的一个字符串相似度计算工具，基于 归一化编辑距离（Levenshtein Distance） 来比较两个字符串的相似程度。下面我会详细讲解它的原理、用法和应用场景。

1. Levenshtein Distance（编辑距离） #

Levenshtein 距离 是指将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数，操作包括：

• 插入（Insertion）
• 删除（Deletion）
• 替换（Substitution）

示例：

• kitten → sitting 的编辑距离是 3：
  • k → s（替换）
  • e → i（替换）
  • 在末尾添加 g（插入）

2. 归一化 Levenshtein 距离 #

原始 Levenshtein 距离是一个绝对数值，而归一化版本将其转换为 0~1 之间的相似度分数： $$ \text{Normalized Levenshtein} = 1 - \frac{\text{Levenshtein Distance}}{\max(\text{len}(s1), \text{len}(s2))} $$

特点：

• 0：完全不相似（两个字符串完全不同）。
• 1：完全相同。

3. strsimpy 库的 NormalizedLevenshtein #

(1) 安装 #

pip install strsimpy

(2) 基本用法 #

from strsimpy.normalized_levenshtein import NormalizedLevenshtein

nl = NormalizedLevenshtein()

s1 = "kitten"
s2 = "sitting"

# 计算相似度（0~1）
similarity = nl.similarity(s1, s2)
print(f"Similarity: {similarity:.4f}")  # 输出: 0.5714

# 计算距离（1 - similarity）
distance = nl.distance(s1, s2)
print(f"Distance: {distance:.4f}")      # 输出: 0.4286

4.实现 #

• editdistance

# 定义一个归一化的Levenshtein距离类
class NormalizedLevenshtein:
    # 定义计算相似度的方法，输入为两个字符串s1和s2
    def similarity(self, s1, s2):
        # 计算Levenshtein距离
        dist = self._levenshtein_distance(s1, s2)
        # 取两个字符串长度的最大值
        max_len = max(len(s1), len(s2))
        # 如果两个字符串都是空串，相似度为1
        if max_len == 0:
            return 1.0
        # 相似度 = 1 - (编辑距离 / 最大长度)，值在0~1之间
        return 1.0 - dist / max_len

    # 定义计算归一化距离的方法，输入为两个字符串s1和s2
    def distance(self, s1, s2):
        # 距离 = 1 - 相似度
        return 1.0 - self.similarity(s1, s2)

    # 定义私有方法，计算Levenshtein编辑距离
    def _levenshtein_distance(self, s1, s2):
        # 如果s1比s2短，交换它们，保证s1更长
        if len(s1) < len(s2):
            s1, s2 = s2, s1
        # 如果较短的字符串为空，距离就是较长字符串的长度
        if len(s2) == 0:
            return len(s1)
        # 初始化上一行的距离列表
        previous_row = list(range(len(s2) + 1))
        # 遍历s1的每个字符及其索引
        for i, c1 in enumerate(s1):
            # 当前行的第一个元素为i+1
            current_row = [i + 1]
            # 遍历s2的每个字符及其索引
            for j, c2 in enumerate(s2):
                # 插入操作：上一行j+1位置的值加1
                insertions = previous_row[j + 1] + 1
                # 删除操作：当前行j位置的值加1
                deletions = current_row[j] + 1
                # 替换操作：上一行j位置的值加（c1和c2是否相等，不等为1）
                substitutions = previous_row[j] + (c1 != c2)
                # 取三种操作的最小值，加入当前行
                current_row.append(min(insertions, deletions, substitutions))
            # 当前行变为上一行，进入下一轮
            previous_row = current_row
        # 返回最后一行的最后一个元素，即编辑距离
        return previous_row[-1]


# 创建NormalizedLevenshtein类的实例
nl = NormalizedLevenshtein()

# 定义第一个字符串
s1 = "kitten"
# 定义第二个字符串
s2 = "sitting"

# 计算两个字符串的相似度（值在0~1之间，越大越相似）
similarity = nl.similarity(s1, s2)
# 打印相似度，保留4位小数
print(f"Similarity: {similarity:.4f}")  # 输出: 0.5714

# 计算两个字符串的归一化距离（1-相似度，越小越相似）
distance = nl.distance(s1, s2)
# 打印距离，保留4位小数
print(f"Distance: {distance:.4f}")  # 输出: 0.4286

5. 示例对比 #

字符串 1	字符串 2	相似度	说明
"apple"	"apple"	1.0	完全相同
"apple"	"apples"	0.8333	差一个字符
"book"	"back"	0.5	替换两个字符
"python"	"java"	0.0	完全不同

6. 应用场景 #

6.1 (1) 拼写纠错 #

query = "googgle"
candidates = ["google", "goggle", "github"]

best_match = max(candidates, key=lambda x: nl.similarity(query, x))
print(best_match)  # 输出: "google"

6.2 (2) 模糊匹配（如搜索引擎） #

user_input = "深度学习"
database = ["深度学xi", "深度学习框架", "机器学习"]

# 找到最相似的条目
matches = sorted(database, key=lambda x: nl.similarity(user_input, x), reverse=True)
print(matches)  # 输出: ['深度学习框架', '深度学xi', '机器学习']

6.3 (3) 数据清洗（去重） #

data = ["用户1", "用户 1", "user1", "管理员"]

# 去重：相似度 > 0.7 视为重复
unique_data = []
for item in data:
    if not any(nl.similarity(item, existing) > 0.7 for existing in unique_data):
        unique_data.append(item)

print(unique_data)  # 可能输出: ['用户1', 'user1', '管理员']

7. 总结 #

• NormalizedLevenshtein 提供了一种简单直观的字符串相似度计算方法。
• 适合 短文本、拼写纠错、模糊匹配 等场景。
• 归一化后的结果更易解释（0~1 范围）。