有两个长度均为几千的字符串列表 A 和 B，其中 B 是对比列。现需要遍历 A，检查其中的每个字符串在 B 中是否存在相似。
我现在是按照这个批量遍历的： https://www.cnblogs.com/hforevery0/p/14375286.html
有啥更高效的方法呢？
This topic created in 1877 days ago, the information mentioned may be changed or developed.
 |
1
首先你要定义相似度的算法
|
1 |
2
编辑距离是比较常用吧
|
 |
3
大规模找重复可以用 MinLSH
|
 |
4
传统的: https://github.com/seatgeek/fuzzywuzzy (move to https://github.com/seatgeek/thefuzz ) 记得开 python-Levenshtein
新兴的: https://github.com/maxbachmann/RapidFuzz 当时作者还跑我 issue 里友好提醒我他们家的证书友好而且更快 |
 |
5
列表比列表的时间复杂度是 O(len(A)*len(B))，
这个只能并发 /并行，没有办法 |
 |
6
巧了，正好最近在准备这方面的 pre，大致有三种思路：
1. 如#1 所说，定义相似度，不同相似度的计算复杂度不一样，可以找个更高效的 2. 如#3 所说，用 LSH，先用低复杂度的算法去除明显不相似的，再用预先定义的相似度去找 3. 如#5 所说，并行，有不少 paper 用 GPU 来做 此外，这三种思路不互斥，完全可以一起用 一个 demo： https://github.com/SeSaMe-NUS/genie |
Select Language