散列相似性

散列的目標通常是將連續函數轉換爲離散函數：輸入中的小改變會導致輸出發生較大變化。然而，是否有任何散列算法可以（大致）粗略地說爲相似的輸入返回相似但仍然不同的哈希值？散列相似性

（使用此的一個例子是檢查兩個文件是否是通過檢查他們的相似性哈希「類似」。當然，有些失敗總是可以接受的。）

2011-01-29 Mehrdad

你如何定義「相似」？ – thkala 2011-01-29 00:32:02

兩個大致相同長度的數據流和大約相同數據的相同順序將被認爲是相似的。（請注意，我不需要說「這兩個相似嗎？」作爲一個布爾值，而是作爲某種數字評級系統。例如，[1,2,3,4]可能更相似到[1,2,3]，而不是[4，3，2，1] ...） – Mehrdad 2011-01-29 00:32:53

看Locality Sensitive Hashing（LSH）。例如，這是一種快速找到特定點附近的一堆點的概率方式。

2011-01-29 00:36:08

給定一個距離函數，告訴你如何相似或不同的是你的對象，你也可以使用距離排列： http://www.computer.org/portal/web/csdl/doi/10.1109/TPAMI.2007.70815 或素描： http://portal.acm.org/citation.cfm?id=1638180

對於後一種方法的實現： http://obsearch.net

2011-06-26 14:36:44

回答