用于字符串相似性的Python摘要/哈希

Question

我正在寻找一种算法，它可以从一个较长的字符串生成一个短的（fx16个字符（不重要）的hashcode/digest。在

主要的要求是几乎相同的字符串应该得到相同的摘要。在

Fx 2几乎相同的邮件：

嗨，马丁。这里有一些。。。给你发垃圾邮件。向XYZ问好。 =>；AAAA AAAA AAAA

嗨，波。这里有一些。。。给你发垃圾邮件。关于EFG。 =>；AAAA AAAA AAAA

返回相同的挖掘（或几乎相同），其中作为不同的邮件：

你好，芬恩。这是一封测试邮件。 =>；中交建交建

将返回不同的摘要。在

这个算法是垃圾邮件过滤器的一部分。过滤器将记住邮件摘要，它肯定是垃圾邮件。如果相同的摘要出现在有疑问的邮件中，相同的摘要将导致过滤器增加垃圾邮件的数量。在

我知道Levenshtein的事，但这需要我事先了解情况。在这种情况下，我没有这个信息。我可以有这个信息，但这将需要过滤器存储所有垃圾邮件和检查每一个，这将是一个非常缓慢的过程。在

也许一些松散的压缩算法加上计算两者之间的Levenshtein距离可以工作。在

有什么建议都可以。在

Answer 1

看起来你想要locality-sensitive hashing。考虑使用minhash或木瓦。拉贾拉曼和乌尔曼的书Mining Massive Datasets中对这两者都有很好的解释。您可以在python中找到大量简短的实现来搜索上面的关键字。在

似乎还有其他方法可以解决这个问题（我不太了解），但这可能会引起您的兴趣，因为它们是专门为垃圾邮件定制的，尤其是nilsimsa哈希：

• 解释了in that paper
• 它有一个python port on pypi