在子二次时间中删除"几乎重复"的字符串

我正在尝试在真实的数据集(酒店评论)上进行机器学习.不幸的是,它受到垃圾邮件的困扰,垃圾邮件的形式几乎完全相同,这对我来说非常重要.

我想基于编辑距离或类似的东西从数据集中删除"几乎重复",并且由于数据集大小> 100K,因此算法必须是数据集大小的次级二次.现在我只能想到标记过于频繁重复的单个句子或短语,然后删除所有带有它们的评论,但很容易看出这种策略如何适得其反.有一个更好的常见算法吗？