局部敏感哈希實現？

在C/C++/Java/C＃中有沒有比較容易理解（也很容易實現）局部敏感的哈希例子？局部敏感哈希實現？

我想更多地瞭解這個概念，因此想嘗試的幾個文本文件的實施只是爲了看看它是如何工作的，所以我什麼都不需要高性能或任何...只是一個一個散列函數的例子，爲類似的輸入返回類似的散列。之後我可以通過示例瞭解更多信息。 :)

2011-04-24 Mehrdad

對於字符串即可使用近似匹配算法。

從隨機共享字符串計算它們的距離。如果字符串是等距離從參考串然後機會，他們彼此相似。在那裏，你有一個本地化的字符串散列實現。

可以爲一個距離範圍內創建不同的散列桶。

編輯：你可以試試串距離的其他變化。一個更簡單的算法只會返回no。兩個字符串之間的共同字符。

2011-04-24 11:02:37

+1它似乎*完全*我在找什麼，我會再看看它。非常感謝！ :) – Mehrdad 2011-04-24 19:07:53

@Hasan：我有點糊塗...字符串'「ABCD」'和'「XYZW」'都來自像'「6pGO」'一個隨機字符串的距離4，但他們是完全不同的。這是如何運作的？（對於任意*長度爲4的任意*字符串，它是4） – Mehrdad 2011-04-24 19:23:16

@Mehrdad此算法告訴您需要將輸入字符串轉換爲引用（隨機）字符串需要進行多少更改。你也可以嘗試一個更簡單的算法，其中距離不是。隨機字符串和輸入字符串之間共同的字符。 – 2011-04-24 19:59:38

而且至少有一次C++庫，您可以檢查這裏的源代碼：http://sourceforge.net/projects/lshkit/

2011-04-24 10:45:41

同樣的問題與@邁赫蘭的鏈接，但還是要謝謝你，+1。 – Mehrdad 2011-04-24 19:07:08

還有Hadoop的一個Java實現。它在文檔上做得很好。

這就是所謂的LikeLike

目前利剋剋只支持閩兩相互獨立排列。閩兩相互獨立的排列是應用於谷歌新聞

2011-04-24 13:37:01 Mehran

感謝您的鏈接，但它似乎有點太複雜，我的情況...我試圖避免大型圖書館，直到我明白了一個簡單的。 :-)無論如何，+1。 – Mehrdad 2011-04-24 19:06:10

我知道你明確要求對C/C++/C＃的建議，但在nilsimsa hash這可能是比其他更容易神交的a Python port，大型圖書館。

2011-05-27 15:57:05

+1這非常棒，我也在學習Python，所以它一舉擊敗了兩隻鳥。感謝分享！ :) – Mehrdad 2011-05-28 01:17:36

回答