V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
alex321
V2EX  ›  问与答

Python 怎么高效批量对比字符串相似度

  •  
  •   alex321 · 2021-09-23 22:13:37 +08:00 · 1220 次点击
    这是一个创建于 917 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有两个长度均为几千的字符串列表 A 和 B,其中 B 是对比列。现需要遍历 A,检查其中的每个字符串在 B 中是否存在相似。

    我现在是按照这个批量遍历的: https://www.cnblogs.com/hforevery0/p/14375286.html

    有啥更高效的方法呢?

    6 条回复    2021-09-24 00:21:21 +08:00
    ch2
        1
    ch2  
       2021-09-23 23:43:42 +08:00   ❤️ 1
    首先你要定义相似度的算法
    mimzy
        2
    mimzy  
       2021-09-23 23:59:26 +08:00   ❤️ 1
    编辑距离是比较常用吧
    rpman
        3
    rpman  
       2021-09-24 00:04:00 +08:00 via iPhone   ❤️ 1
    大规模找重复可以用 MinLSH
    ClericPy
        4
    ClericPy  
       2021-09-24 00:06:36 +08:00   ❤️ 3
    传统的: https://github.com/seatgeek/fuzzywuzzy (move to https://github.com/seatgeek/thefuzz ) 记得开 python-Levenshtein

    新兴的: https://github.com/maxbachmann/RapidFuzz 当时作者还跑我 issue 里友好提醒我他们家的证书友好而且更快
    inframe
        5
    inframe  
       2021-09-24 00:08:14 +08:00   ❤️ 1
    列表比列表的时间复杂度是 O(len(A)*len(B)),
    这个只能并发 /并行,没有办法
    lv2016
        6
    lv2016  
       2021-09-24 00:21:21 +08:00   ❤️ 2
    巧了,正好最近在准备这方面的 pre,大致有三种思路:
    1. 如#1 所说,定义相似度,不同相似度的计算复杂度不一样,可以找个更高效的
    2. 如#3 所说,用 LSH,先用低复杂度的算法去除明显不相似的,再用预先定义的相似度去找
    3. 如#5 所说,并行,有不少 paper 用 GPU 来做
    此外,这三种思路不互斥,完全可以一起用
    一个 demo: https://github.com/SeSaMe-NUS/genie
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1530 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 17:09 · PVG 01:09 · LAX 10:09 · JFK 13:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.