计算两个字符串相似度，它来了，后端集成多种算法
guonaihong · guonaihong · 2020-08-17 09:27:02 +08:00 · 7229 次点击这是一个创建于 1593 天前的主题，其中的信息可能已经有所发展或是发生改变。
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())
 |
1
liukangxu 2020-08-17 09:58:24 +08:00
最后一个例子，两个不等长的字符串计算 Hamming distance ？
|
 |
2
guonaihong OP @liukangxu hamming 主要计算相等长度字符串。后面把例子修改下。
|
 |
3
stone666 2020-08-17 10:44:11 +08:00
hutool 中有个相似的方法 StrUtil.similar(str1,str2); 看起来实现原理差不多
|
 |
4
GM 2020-08-17 10:47:01 +08:00
选择的示例不好，看不出有什么特点和优势。主要是示例用的文本太短，随便弄个 strpos 也能算，没有对比优势。
|
|
5
guonaihong OP @GM ok， 后面优化小示例。
|
 |
6
zcfnc 2020-08-17 11:18:58 +08:00
如果是匹配的数组里面元素比较多，效率如何呢
|
 |
7
Mohanson 2020-08-17 11:32:47 +08:00 via Android
刷题的时候写过 Levenshtein 算法，实现起来不难，20 行不到，很多用在命令行工具上，当你敲错了命令，就可以提示 command not found, did you mean "xxxxx xxxxx"
|
|
8
Mohanson 2020-08-17 11:35:00 +08:00 via Android
其实这种简单的算法我还是建议自己手写，维基百科上都有伪代码说明的
|
|
9
guonaihong OP @zcfnc 会加上 benchmark，关注下就行。
|
|
10
guonaihong OP @Mohanson wiki 上面的算法只是直译公式，工程上没有任何优化。太浪费空间。
|
 |
11
blless 2020-08-17 11:43:50 +08:00 via Android
有拼音相似度算法吗
|
|
12
guonaihong OP @blless 没关注过，可以到 github 上找找，我理解这种库，先用 mmseg 分词，然后决策出最佳读音，再根据国人的习惯，忽略后鼻音，前鼻音的。。。
|
 |
13
woostundy 2020-08-17 13:42:37 +08:00
我以前做过类似的东西，中文相似度靠发音 + 按笔画拆解编码，看两个笔画编码的相似度。
|
 |
16
selca 2020-08-17 14:59:54 +08:00
@blless 记得百度还是哪家的语音识别里面给出过一个拼音相似度的算法实现，是基于上述的 Levenshtein 的一个实现，之前有参照这个写过一个东西，不过源码拿不回来了
|
 |
17
njushannon 2020-08-17 15:00:51 +08:00
之前做过一套计算数据相似度的算法，不过是一套系统了
|
 |
18
takemeaway 2020-08-17 15:02:59 +08:00
啥叫相似度？ 就是这个字符串在那个字符串里面的占比？？？
|
 |
19
superrichman 2020-08-17 16:49:59 +08:00 via iPhone
丟一堆论文查重试试 doge
|
 |
20
xupefei 2020-08-17 17:09:13 +08:00
几个意见：
1. 编辑距离有更快的 Ukkonen 算法： https://github.com/sunesimonsen/ukkonen 2. best_result 在不同算法下有不同的解法。比如在编辑距离下，相似度最高的字符串可以用前缀数拿到： https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/sigmod513.pdf |
|
21
guonaihong OP @xupefei 感谢感谢，又 get 新的玩法。
|
 |
22
fanyingmao 2020-08-17 19:13:51 +08:00
今天面试就问到相似度算法，没做过我都没想出来。
|
 |
23
cuishuang 2023-04-23 22:05:38 +08:00
不错！
|
Select Language