V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
guonaihong
V2EX  ›  Go 编程语言

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

  •  1
     
  •   guonaihong ·
    guonaihong · 2020-08-17 09:27:02 +08:00 · 7144 次点击
    这是一个创建于 1543 天前的主题,其中的信息可能已经有所发展或是发生改变。

    strsim

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

    Go codecov

    项目地址

    https://github.com/antlabs/strsim

    构架

    strsim.png

    功能

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

      多种算法支持

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

    内容

    比较两个字符串相识度

    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())
    
    23 条回复    2023-04-23 22:05:38 +08:00
    liukangxu
        1
    liukangxu  
       2020-08-17 09:58:24 +08:00
    最后一个例子,两个不等长的字符串计算 Hamming distance ?
    guonaihong
        2
    guonaihong  
    OP
       2020-08-17 10:04:17 +08:00
    @liukangxu hamming 主要计算相等长度字符串。后面把例子修改下。
    stone666
        3
    stone666  
       2020-08-17 10:44:11 +08:00
    hutool 中有个相似的方法 StrUtil.similar(str1,str2); 看起来实现原理差不多
    GM
        4
    GM  
       2020-08-17 10:47:01 +08:00
    选择的示例不好,看不出有什么特点和优势。主要是示例用的文本太短,随便弄个 strpos 也能算,没有对比优势。
    guonaihong
        5
    guonaihong  
    OP
       2020-08-17 11:02:26 +08:00
    @GM ok, 后面优化小示例。
    zcfnc
        6
    zcfnc  
       2020-08-17 11:18:58 +08:00
    如果是匹配的数组里面元素比较多,效率如何呢
    Mohanson
        7
    Mohanson  
       2020-08-17 11:32:47 +08:00 via Android
    刷题的时候写过 Levenshtein 算法,实现起来不难,20 行不到,很多用在命令行工具上,当你敲错了命令,就可以提示 command not found, did you mean "xxxxx xxxxx"
    Mohanson
        8
    Mohanson  
       2020-08-17 11:35:00 +08:00 via Android
    其实这种简单的算法我还是建议自己手写,维基百科上都有伪代码说明的
    guonaihong
        9
    guonaihong  
    OP
       2020-08-17 11:39:35 +08:00
    @zcfnc 会加上 benchmark,关注下就行。
    guonaihong
        10
    guonaihong  
    OP
       2020-08-17 11:42:08 +08:00
    @Mohanson wiki 上面的算法只是直译公式,工程上没有任何优化。太浪费空间。
    blless
        11
    blless  
       2020-08-17 11:43:50 +08:00 via Android
    有拼音相似度算法吗
    guonaihong
        12
    guonaihong  
    OP
       2020-08-17 11:46:50 +08:00
    @blless 没关注过,可以到 github 上找找,我理解这种库,先用 mmseg 分词,然后决策出最佳读音,再根据国人的习惯,忽略后鼻音,前鼻音的。。。
    woostundy
        13
    woostundy  
       2020-08-17 13:42:37 +08:00
    我以前做过类似的东西,中文相似度靠发音 + 按笔画拆解编码,看两个笔画编码的相似度。
    cladg123
        14
    cladg123  
       2020-08-17 14:40:30 +08:00
    @woostundy 有相关的示例吗
    woostundy
        15
    woostundy  
       2020-08-17 14:48:01 +08:00
    @cladg123 #14 在上上家公司做的反洗钱黑名单匹配算法。。没开源。
    selca
        16
    selca  
       2020-08-17 14:59:54 +08:00
    @blless 记得百度还是哪家的语音识别里面给出过一个拼音相似度的算法实现,是基于上述的 Levenshtein 的一个实现,之前有参照这个写过一个东西,不过源码拿不回来了
    njushannon
        17
    njushannon  
       2020-08-17 15:00:51 +08:00
    之前做过一套计算数据相似度的算法,不过是一套系统了
    takemeaway
        18
    takemeaway  
       2020-08-17 15:02:59 +08:00
    啥叫相似度? 就是这个字符串在那个字符串里面的占比???
    superrichman
        19
    superrichman  
       2020-08-17 16:49:59 +08:00 via iPhone
    丟一堆论文查重试试 doge
    xupefei
        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
    guonaihong
        21
    guonaihong  
    OP
       2020-08-17 19:02:35 +08:00
    @xupefei 感谢感谢,又 get 新的玩法。
    fanyingmao
        22
    fanyingmao  
       2020-08-17 19:13:51 +08:00
    今天面试就问到相似度算法,没做过我都没想出来。
    cuishuang
        23
    cuishuang  
       2023-04-23 22:05:38 +08:00
    不错!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2490 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 15:53 · PVG 23:53 · LAX 07:53 · JFK 10:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.