在次二时间内删除“几乎重复”的字符串

Question

我试图对一份真实的数据集（旅馆评论）进行机器学习。不幸的是，它受到垃圾信息的困扰，这些垃圾信息以几乎完全相同的评论形式出现，给我的工作带来了很大的复杂性。

我想要基于编辑距离或类似的算法从数据集中删除“几乎重复”的内容，并且因为数据集的大小超过100K, 算法必须是对数据集大小亚二次的。目前，我只能考虑标记经常重复的单个句子或短语，然后删除所有包含这些内容的评论，但这种策略很容易出问题。是否有更好的常见算法？

- Alexei Averchenko

---

这感觉像是一堆最近邻查询，尽管使用了一个不寻常的距离度量（我认为编辑距离不满足三角不等式）。我建议研究一下通常用于加速最近邻搜索的数据结构。 - user395760

手动使用一些选定的垃圾邮件条目来种子贝叶斯过滤器怎么样？ - JimR

这是“近似重复”检测问题。一种常见的技术称为分词。如果您搜索这些术语，您应该会找到一些有用的算法。 - Dave

@delnan 实际上，编辑距离确实满足度量的公理。 - Alexei Averchenko

“局部敏感哈希（LSH）”似乎是一种吸引人的启发式方法，例如可以参考高维近似最近邻哈希算法的近似优化。但我只能赞同ElKamina的看法，“解决这个问题可能需要撰写一篇不错的研究论文。”基本思想是使用LSH，相似的条目（相对于阈值）可能会被放置在同一个桶中，但足够不同的条目则会被放置在不同的桶中。 - Ali

Answer 1

显然，要完全解决这个问题可能需要撰写一篇不错的研究论文。这是我的建议。

在生物信息学中，我们经常面临这个问题。最常用的算法是BLAST (http://en.wikipedia.org/wiki/BLAST)。请仔细阅读该算法，您可能会了解其中涉及的内容。

- ElKamina

Answer 2

一个快速而粗略的方法是找到评论中出现的关键词并将它们存储在通用字典中，然后扫描每个文档以查找这些词。为每个文档创建一个关键词的哈希表。然后比较所有文档对，计算每对文档中相似关键字的数量，如果大于阈值，则标记它们为相似的文档。如果需要找到相似的文档，则可以使用快速联合查找数据结构来查找两个文档的联合。最后，您会得到一组相似的文档。

注意：我想不到任何方法使其次二次方，但如果您需要查找是否有相似的文档，则在最坏情况下需要检查所有文档对。

- Vikram Bhat