哈希函數的索引類似的文本

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」編輯距離），並且距離本身將是散列值。可能這種方法在你的情況下不會是最好的，但也許在問題的一些額外信息我們可以提出一個更好的等價關係。