如何利用Levenshtein算法实现相似字符串列表分组？

核心思路 #

既然你已经实现了Levenshtein算法，接下来要做的是用它完成聚类分组：遍历列表里的每个字符串，和已有的组代表计算相似度，超过阈值就归入该组，否则新建组。

具体步骤（C#示例） #

1. 预处理字符串：先统一格式（转小写、去掉剂量、包装这类无关信息），减少干扰。比如把"TAB PARACETAMOL 500MG"处理成"paracetamol"，"PANADOL TABS 4X20"处理成"panadol"。
2. 设定相似度阈值：根据需求定，比如Levenshtein距离≤2，或者相似度（1 - 距离/最长字符串长度）≥0.8。
3. 遍历分组：
   • 初始化空的分组列表，每个组包含一个代表字符串和成员列表。
   • 对每个预处理后的字符串，和每个组的代表算相似度。
   • 找到符合阈值的组就加进去，没找到就新建组。

代码示例 #

// 假设你已经实现了Levenshtein距离计算方法：int CalculateLevenshteinDistance(string a, string b)
public class StringGroup
{
    public string GroupName { get; set; }
    public List<string> Items { get; set; } = new List<string>();
}

public List<StringGroup> GroupSimilarStrings(List<string> rawItems)
{
    var groups = new List<StringGroup>();
    
    // 预处理：转小写、移除无关关键词、数字和多余空格
    Func<string, string> Preprocess = s => 
    {
        var processed = s.ToLower();
        // 移除药品名里的常见无关词
        var irrelevantWords = new[] { "tab", "tabs", "extra", "mg", "x" };
        foreach (var word in irrelevantWords)
        {
            processed = processed.Replace(word, "");
        }
        // 去掉数字和多余空格
        processed = new string(processed.Where(c => !char.IsDigit(c)).ToArray()).Trim();
        return processed;
    };

    // 相似度阈值：Levenshtein距离≤1，可根据实际调整
    int distanceThreshold = 1;

    foreach (var item in rawItems)
    {
        var processedItem = Preprocess(item);
        bool added = false;

        foreach (var group in groups)
        {
            var processedGroupRep = Preprocess(group.GroupName);
            int distance = CalculateLevenshteinDistance(processedItem, processedGroupRep);
            // 也可以用相似度比例判断，比如相似度≥0.8
            double similarity = 1 - (double)distance / Math.Max(processedItem.Length, processedGroupRep.Length);
            
            if (distance <= distanceThreshold || similarity >= 0.8)
            {
                group.Items.Add(item);
                added = true;
                break;
            }
        }

        if (!added)
        {
            groups.Add(new StringGroup { GroupName = item, Items = new List<string> { item } });
        }
    }

    // 优化组名：选每个组里最简洁的成员作为组名
    foreach (var group in groups)
    {
        group.GroupName = group.Items.OrderBy(i => Preprocess(i).Length).First();
    }

    return groups;
}

优化建议 #

• 强化预处理：用正则表达式移除所有非字母字符，或者直接提取核心关键词（比如药品的通用名）。
• 换算法试试：如果Levenshtein效果不好，可试试Jaccard相似度（基于字符/词的交集），或者Soundex/Metaphone（基于发音相似性），适合处理品牌名和通用名这类发音/拼写相近的情况。
• 调整阈值：根据实际数据测试调整，比如Panadol和Paracetamol这类情况，可能需要放宽阈值，或者单独做规则匹配（因为这俩本身就是同一种药的不同名称）。

内容的提问来源于stack exchange，提问作者elfico