基于大量行（>50 000）的模糊匹配删除“几乎重复”的字符串行

Question

我有 50 000 个单词，例如：

• 添加
• 添加
• 鸡
• 一只鸡
• 吃鸡
• 吃饭
• ...

我想删除与其他线有很高模糊相似度的线。

那么输出应该是：

• 添加
• 吃饭
• 鸡
• ...

我无法计算每个模糊匹配（50 000 ** 2 个匹配太高），我搜索像 KD-Tree / Ball-Tree 这样的方法，但使用字符串距离（Levenstein 距离、模糊距离...）

我更喜欢只使用Python，但我思想开放！非常感谢:)

Answer 1

您可以尝试安装模块thefuzz。

from thefuzz import process

word_list = ['add', 'to add', 'chicken', 'eat the chicken', 'to eat']
deduped_word_list = process.dedupe(word_list, threshold=60)
print(deduped_word_list)

输出：

['to add', 'to eat', 'eat the chicken']

根据定义，他们保留一类重复项的最长字符串，因为他们期望它具有最大信息。如果你想要最短的字符串，你可以重构他们的代码:)

检查process.dedupe了解更多信息！

Answer 2

在对其他主题进行个人搜索后，我没有找到使用简单的 python librairie 的快速解决方案

但是我有两个想法来解决我的问题： 1.向量化每个“字符串”，例如： “一只鸡” -> (0,0,0,0,...1,0,...1,0,0) 并在 sklearn 中使用 KD-Tree/Ball-Tree（请参阅我的主题来实现它：在其他数据帧中查找最近的点（有大量数据））

2.对每个字符串进行词干并使用 pandas 应用 .drop_duplicates ;)