Swift中计算字符串相似度百分比的最优算法？Levenshtein无法满足需求

嘿，咱们来拆解下你的问题，找个适配你需求的最优算法。Levenshtein编辑距离之所以不符合你的预期，核心原因是它衡量的是修改两个字符串使其一致的难度，而不是你真正想要的「内容重叠比例」或者「语序不敏感的匹配度」。针对你的两个核心痛点，给你几个针对性的方案：

1. 解决「语序不同但内容一致」的场景：词级Jaccard/Dice系数 #

如果你的字符串是用空格分隔的短语（比如"cat dog"这种），优先按词来拆分处理，而不是字符：

• Jaccard相似度：计算两个词集合的交集与并集的比例，公式是 J = |A ∩ B| / |A ∪ B|。比如"cat dog"和"dog cat"的词集合都是{cat, dog}，交集和并集的大小都是2，所以J=1，对应100%相似度，完全符合你的预期。
• 加权Dice系数（考虑词的重复次数）：如果需要区分词的出现频率（比如"cat cat dog"和"cat dog"），可以用这个：Dice = 2 * sum(min(count_A(w), count_B(w)) for w in 所有词) / (sum(count_A(w)) + sum(count_B(w)))。比如刚才的例子，计算后是(2*(1+1))/(3+2)=80%，更贴合实际内容的重叠程度。

2. 解决「重复子串相似度」的场景：最长公共子序列（LCS）比例 #

你的例子里"abcabc"和"abc"期望得到50%的相似度，本质是想要匹配内容的长度占较长字符串的比例，这时候用LCS再合适不过：

• 先计算两个字符串的最长公共子序列长度（LCS长度），然后用这个长度除以较长字符串的总长度，再乘以100得到百分比。
• 举几个你的例子验证：
  • "abcabc" vs "abc"：LCS长度是3，较长字符串长度是6 → 3/6*100=50%，完美符合你的期望；
  • "ab" vs "abc"：LCS长度是2，较长字符串长度是3 → 2/3*100≈66%，和你之前的预期一致。

3. 兼顾两种场景的组合方案 #

如果你的字符串既有连续字符的情况，又有语序不同的短语，建议做个简单的判断：

• 若字符串包含空格（或其他词分隔符），先拆成词，用词级的加权Dice/Jaccard计算；
• 若为连续字符，用LCS长度除以较长字符串长度的方式计算相似度。

补充：字符n-gram的Jaccard/Dice（适合无分隔符的模糊匹配） #

如果你的连续字符串需要更细腻的模糊匹配（比如拼写错误容忍），可以把字符串拆分成n-gram（比如2-gram："abc"拆成"ab","bc"），再用加权Dice系数计算：

• 比如"abcabc"和"abc"的2-gram集合，前者是["ab","bc","ca","ab","bc","ca"]，后者是["ab","bc"]，加权Dice计算后是(2*(1+1))/(6+2)=50%，也能符合你的重复子串预期；
• 对于"catdog"和"dogcat"，2-gram的交集是["ca","at","do","og"]，Jaccard相似度约67%，能体现内容的高度重叠。

最后给个小建议：如果用Python实现的话，LCS可以自己写动态规划代码，词级的统计用collections.Counter就能快速搞定，不需要复杂的第三方库。

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