Python字符串相似度的摘要/哈希

Question

我正在寻找一种算法，可以从较长的字符串中生成一个短的（例如16个字符（不重要））哈希码/摘要。

主要要求是几乎相同的字符串应该产生相同的摘要。

例如，两个几乎相同的邮件：

Hi Martin. Here are some ... spam for you. Regards XYZ. => AAAA AAAA AAAA AAAA

Hi Bo. Here are some ... spam for you. Regards EFG. => AAAA AAAA AAAA AAAA

将返回相同的摘要（或几乎相同），而另一个不同的邮件：

Hello Finn. This is a test mail. => CCCC CCCC CCCC CCCC

将返回不同的摘要。

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

我知道Levenshtein算法，但它要求我预先知道字符串。在这种情况下，我没有这些信息。我可以拥有这些信息，但这将需要过滤器存储所有垃圾邮件并检查每个垃圾邮件，这将是一个非常缓慢的过程。

也许一些松散的压缩算法和计算两者之间Levenshtein距离的算法可以起作用。

任何指针都将不胜感激。

- Drewes

---

一个简单的搜索“相似字符串哈希”会返回大量重复的这个问题。 - Nick Johnson

Answer 1

看起来你想使用局部敏感哈希。考虑使用最小哈希或shingling。在Rajaraman和Ullman的书Mining Massive Datasets中有很好的解释。在博客中搜索上述关键字，你会找到许多短小的Python实现。

似乎还有其他方法（我不太了解），但可能会对你有兴趣，因为它们专门针对垃圾邮件，特别是nilsimsa哈希:

• 在这篇论文中解释了
• pypi上有Python版本的端口

- Francois G

---

那是 PyPI 而不是 PyPy，PyPy 是 Python 解释器，而 PyPI 则是 Python 包索引。 - fijal