计算两个字符串相似度，它来了，后端集成多种算法

[guonaihong]

strsim

strsim 是 golang 实现的字符串相识度库，后端集成多种算法，主要解决现有相似度库不能很好的处理中文

项目地址

https://github.com/antlabs/strsim

构架

功能

• 可以忽略空白字符
• 可以大小写

  多种算法支持

  • 莱文斯坦-编辑距离(Levenshtein)
  • Hamming
  • Dice's coefficient
  • Jaro

内容

• 比较两个字符串相识度
• 从字符串数组里面找到相似度最高的字符串
• 选择不同算法
  • 莱文斯坦-编辑距离(Levenshtein)
  • [选择 Dice's coefficient](#选择 Dice's-coefficient)
  • [选择 jaro](#选择 jaro)
  • [选择 Hamming](#选择 Hamming)

比较两个字符串相识度

strsim.Compare("中国人", "中")
// -> 0.333333

从数组里找到相似度最高的字符串

strsim.FindBestMatchOne("海刘", []string{"白日依山尽", "黄河入海流", "欲穷千里目", "更上一层楼"})

选择不同算法

莱文斯坦-编辑距离(Levenshtein)

strsim.Compare("abc", "ab")
// -> 0.6666666666666667

选择 Dice's coefficient

strsim.Compare("abc", "ab", strsim.DiceCoefficient(1))
//-> 0.6666666666666666

选择 jaro

strsim.Compare("abc", "ab", strsim.Jaro())

选择 Hamming

strsim.Compare("abc", "ab", strsim.Hamming())

[liukangxu]

最后一个例子，两个不等长的字符串计算 Hamming distance ？

[guonaihong]

@liukangxu hamming 主要计算相等长度字符串。后面把例子修改下。

[stone666]

hutool 中有个相似的方法 StrUtil.similar(str1,str2); 看起来实现原理差不多

[GM]

选择的示例不好，看不出有什么特点和优势。主要是示例用的文本太短，随便弄个 strpos 也能算，没有对比优势。

[guonaihong]

@GM ok， 后面优化小示例。

[zcfnc]

如果是匹配的数组里面元素比较多，效率如何呢

[Mohanson]

刷题的时候写过 Levenshtein 算法，实现起来不难，20 行不到，很多用在命令行工具上，当你敲错了命令，就可以提示 command not found, did you mean "xxxxx xxxxx"

[Mohanson]

其实这种简单的算法我还是建议自己手写，维基百科上都有伪代码说明的

[guonaihong]

@zcfnc 会加上 benchmark，关注下就行。

[guonaihong]

@Mohanson wiki 上面的算法只是直译公式，工程上没有任何优化。太浪费空间。

[blless]

有拼音相似度算法吗

[guonaihong]

@blless 没关注过，可以到 github 上找找，我理解这种库，先用 mmseg 分词，然后决策出最佳读音，再根据国人的习惯，忽略后鼻音，前鼻音的。。。

[woostundy]

我以前做过类似的东西，中文相似度靠发音 + 按笔画拆解编码，看两个笔画编码的相似度。

[cladg123]

@woostundy 有相关的示例吗

[woostundy]

@cladg123 #14 在上上家公司做的反洗钱黑名单匹配算法。。没开源。

[selca]

@blless 记得百度还是哪家的语音识别里面给出过一个拼音相似度的算法实现，是基于上述的 Levenshtein 的一个实现，之前有参照这个写过一个东西，不过源码拿不回来了

[njushannon]

之前做过一套计算数据相似度的算法，不过是一套系统了

[takemeaway]

啥叫相似度？ 就是这个字符串在那个字符串里面的占比？？？

[superrichman]

丟一堆论文查重试试 doge

[xupefei]

几个意见：
1. 编辑距离有更快的 Ukkonen 算法： https://github.com/sunesimonsen/ukkonen
2. best_result 在不同算法下有不同的解法。比如在编辑距离下，相似度最高的字符串可以用前缀数拿到： https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/sigmod513.pdf

[guonaihong]

@xupefei 感谢感谢，又 get 新的玩法。

[fanyingmao]

今天面试就问到相似度算法，没做过我都没想出来。

[cuishuang]

不错！