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

[alex321]

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

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

有啥更高效的方法呢？

[ch2]

首先你要定义相似度的算法

[mimzy]

编辑距离是比较常用吧

[rpman]

大规模找重复可以用 MinLSH

[ClericPy]

传统的: https://github.com/seatgeek/fuzzywuzzy (move to https://github.com/seatgeek/thefuzz ) 记得开 python-Levenshtein

新兴的: https://github.com/maxbachmann/RapidFuzz 当时作者还跑我 issue 里友好提醒我他们家的证书友好而且更快

[inframe]

列表比列表的时间复杂度是 O(len(A)*len(B))，
这个只能并发 /并行，没有办法

[lv2016]

巧了，正好最近在准备这方面的 pre，大致有三种思路：
1. 如#1 所说，定义相似度，不同相似度的计算复杂度不一样，可以找个更高效的
2. 如#3 所说，用 LSH，先用低复杂度的算法去除明显不相似的，再用预先定义的相似度去找
3. 如#5 所说，并行，有不少 paper 用 GPU 来做
此外，这三种思路不互斥，完全可以一起用
一个 demo： https://github.com/SeSaMe-NUS/genie