的Python消化/散列

我正在寻找一种算法能够生成短（FX 16个字符（不重要）哈希码/从一个更长的字符串消化。的Python消化/散列

的主要要求是该串是几乎相同的应导致相同摘要

Fx的2几乎相同的邮件：。

嗨马丁这里有一些...垃圾邮件对您的问候XYZ => AAAA AAAA AAAA AAAA

。 Hi Bo，这里有一些...垃圾邮件给你。问候EFG。 => AAAA AAAA AAAA AAAA

返回相同diges（或几乎相同），其中，作为一个不同的邮件：

你好芬兰。这是一封测试邮件。 => CCCC CCCC CCCC CCCC

将返回不同的摘要。

该算法将成为垃圾邮件过滤器的一部分。过滤器会记住来自邮件的摘要，这些摘要肯定是垃圾邮件。如果相同的摘要出现在有疑问的邮件中，则相同的摘要将导致过滤器增加垃圾邮件。

我知道Levenshtein，但它需要我知道前面的字符串。在这种情况下，我没有这个信息。我可以得到这些信息，但这需要过滤器来存储所有垃圾邮件，并对每一封邮件进行检查，这将是一个非常缓慢的过程。

也许一些松散的压缩算法加上两者之间Levenshtein距离的计算值可能会有效。

任何指针赞赏。

2012-01-13 Drewes

关于“相似串散列” A简单搜索返回这个问题的重复的分数。 – 2012-01-16 03:06:23

它看起来像你想locality-sensitive hashing。考虑使用minhash或shingling。在拉贾拉曼&乌尔曼的书，Mining Massive Datasets有一个很好的解释。您可以在python搜索上面关键字的博客中找到很多简短的实现。

似乎有被其他方法来这（我不知道很多有关），但可能是你的兴趣，因为他们是专门针对垃圾邮件量身定制，特别是nilsimsa哈希：

2012-01-13 10:45:52 huitseeker

这是pypi不是pypy，pypy是一个python解释器，pypi是python包的索引。 – fijal 2012-01-13 17:34:09

当然！抱歉。纠正。 – huitseeker 2012-01-13 18:00:23

回答