这是一个创建于 1163 天前的主题，其中的信息可能已经有所发展或是发生改变。
有两个长度均为几千的字符串列表 A 和 B，其中 B 是对比列。现需要遍历 A，检查其中的每个字符串在 B 中是否存在相似。
我现在是按照这个批量遍历的： https://www.cnblogs.com/hforevery0/p/14375286.html
有啥更高效的方法呢？
 |
1
ch2 2021-09-23 23:43:42 +08:00  1
首先你要定义相似度的算法
|
 |
2
mimzy 2021-09-23 23:59:26 +08:00 1
编辑距离是比较常用吧
|
 |
3
rpman 2021-09-24 00:04:00 +08:00 via iPhone 1
大规模找重复可以用 MinLSH
|
 |
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 里友好提醒我他们家的证书友好而且更快 |
 |
5
inframe 2021-09-24 00:08:14 +08:00 1
列表比列表的时间复杂度是 O(len(A)*len(B))，
这个只能并发 /并行，没有办法 |
 |
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 |
Select Language