哈希函数的索引类似的文本

Question

我在寻找有关一种散列函数的索引类似的文本。例如，如果我们有两个非常长的文本，称为“A”和“B”，其中A和B差异不大，那么应用于A和B的散列函数（称为H）应该返回相同的数字。

所以H（A）= H（B）其中A和B是类似的文本。

我尝试了“DoubleMetaphone”（我用意大利语语言文本），但我看到它依赖非常强从字符串前缀。例如：

A = “这是我想散列很长的文本” B = “这是非常”

==> doubleMetaPhone（A）= doubleMetaPhone（B）

这对我来说并不是那么好，因为具有相同前缀的字符串可以被比较为相似的，我不想这样做。

任何人都可以给我建议任何其他方式？

Answer 1

看到http://en.wikipedia.org/wiki/Locality_sensitive_hashing

Answer 2

你的问题是（接近）不溶性的字符串之间有许多距离函数。

最远距离功能（例如edit distance）允许您通过1-距离转换序列的字符串转换为另一个字符串：

"AAAA" -> "AAAB" -> "AAABC" 

根据您的要求，第一和第二串应具有相同的哈希值。但第二个和第三个必须如此，等等。因此，如果我们允许距离= 1的对具有相同的散列值，那么所有字符串将必须具有相同的散列，。

即使我们强加距离的门槛较高（也许相对于字符串长度），我们将用一个混乱的结果告终。

一个更好的（IMO）方法是在一组字符串上找到一个equivalence relation，这样每个等价类中的每个字符串都有相同的散列。一种可能性是通过它们到预定义字符串的距离来定义类（例如，从“AAAAA”编辑距离），并且距离本身将是散列值。可能这种方法在你的情况下不会是最好的，但也许在问题的一些额外信息我们可以提出一个更好的等价关系。