如何快速去除相似字符串？

Question

现在，我有一个包含大约 70,000 条推文的数据集，我正在尝试删除过于相似的推文。我决定使用大于 0.9 的 Levenshtein 比率作为推文过于相似的阈值。然而，我当前的代码本质上是将每条推文与其他每条推文进行比较，得到 O(N^2)，这非常慢。到达运行需要 12 多个小时，这实在是太多了。我尝试将其并行化，这就是我现在运行正在做的事情，但我不知道这是否会将其加速到可接受的程度。有什么方法可以在 O(N) 内完成吗？

import json
import multiprocessing as mp
from pathlib import Path

import Levenshtein

def check_ratio(similar_removed, try_tweet):
    for tweet in similar_removed:
        if Levenshtein.ratio(try_tweet, tweet[1]) > 0.9:
            return 1
    return 0

def main():
    path = Path('C:/Data/Python/JobLoss')
    orig_data = []
    with open(path / 'Processed.json') as f:
        data = json.load(f)
        for tweet in data:
            orig_data.append(tweet[2])
    pool = mp.Pool(mp.cpu_count())
    similar_removed = []
    similar_removed.append((0, orig_data[0]))
    for i in range(1, len(orig_data)):
        print('%s / %s' % (i, len(orig_data)))
        too_similar = 0
        try_tweet = orig_data[i]
        too_similar = pool.apply(check_ratio, args=(similar_removed, try_tweet))
        if not too_similar:
            similar_removed.append((i, try_tweet))
    pool.close()
    final = [data[ind[0]] for ind in similar_removed]
    with open(path / 'ProcessedSimilarRemoved.json', 'w') as f:
            json.dump(final, f)

if __name__ == '__main__':
    main()

Answer 1

我最终使用了 this 问题的最佳答案中描述的方法，该方法使用 LSH 进行次线性时间查询，给出了次二次的总体复杂度；足够快满足我的需求。本质上，您使用 k-shingling 将每条推文变成一个集合，然后使用 min hash lsh 快速将相似的集合存储在一起。然后，无需将每条推文与其他所有推文进行比较，您只需在其存储桶中查找匹配项，这使得该方法比对所有对使用 Levenshtein 比率要快得多。

如何快速去除相似字符串？

How to Quickly Remove Similar Strings?

python

string

performance

tweets

levenshtein-distance