python 字符串相似度分组

字符串相似度分组是一种常见的任务，可以通过计算字符串之间的相似度来将它们分成若干个组，以方便后续的处理。在 Python 中，可以使用 Levenshtein 距离或 Jaccard 相似度等算法来计算字符串之间的相似度，然后根据相似度来进行分组。

以下是一个简单的示例代码，使用 Jaccard 相似度来对字符串进行分组：

from typing import List
from collections import defaultdict

def jaccard_sim(a: str, b: str) -> float:
    """计算 Jaccard 相似度"""
    a, b = set(a), set(b)
    return len(a & b) / len(a | b)

def group_strings(strings: List[str], threshold: float) -> List[List[str]]:
    """将相似度大于等于阈值的字符串分到同一组中"""
    groups = defaultdict(list)
    for s in strings:
        added = False
        for g in groups:
            sim = jaccard_sim(s, g)
            if sim >= threshold:
                groups[g].append(s)
                added = True
                break
        if not added:
            groups[s].append(s)
    return list(groups.values())

在上述代码中，`jaccard_sim` 函数计算 Jaccard 相似度，`group_strings` 函数将相似度大于等于阈值的字符串分到同一组中。这里使用了 defaultdict 来创建组，如果某个字符串与已有的组相似度大于等于阈值，则将其添加到该组中，否则将其作为新的组添加到 defaultdict 中。

示例用法：

strings = ["abc", "abd", "abf", "xyz", "pqr"]
groups = group_strings(strings, 0.5)
print(groups)

输出：

[['abc', 'abd', 'abf'], ['xyz'], ['pqr']]

在上述示例中，阈值为 0.5，因此将 "abc", "abd", "abf" 分到同一组中，将 "xyz" 作为新的一组，将 "pqr" 作为新的一组。