如何將相似的字元串散列到相同的散列值？
假設 $ s_1 $ 和 $ s_2 $ 是兩個具有較小漢明距離的刺。是否有抗原像的“散列”功能（ $ H $ ) 可以將它們映射到相同的值，即 $ H(s_1) = H(s_2) $ ?
正如poncho 所指出的，散列函式 $ H(.) $ 這將始終映射兩個緊密的字元串 $ s_1 $ 和 $ s_2 $ 到相同的值，必須將所有字元串映射到相同的值。（因為您可以從一個字元串轉到下一個字元串，並且它總是必須映射到相同的值。）所以這沒有任何意義。
我認為，就像您還建議的那樣，糾錯碼可能是您想要的。這樣的程式碼由一組程式碼字定義 $ {c_1,…,c_n} $ 它們彼此之間有一定的（漢明）距離，並且在每個碼字周圍 $ c_i $ 有一個漢明球 $ S_i $ 包含那些更接近的詞 $ c_i $ 比任何其他程式碼字。一個完美的解碼器會將任何單詞映射到最接近的碼字，因此它將映射任何單詞 $ S_i $ 至 $ c_i $ . 所以如果你在同一個漢明球中有兩個詞 $ S_i $ ，您的解碼器會將它們解碼為相同的程式碼字 $ c_i $ . （你可以很容易地生成這樣的話 $ c_i $ 並隨機翻轉一些位。）
這不完全是您想要的雜湊函式，但我認為如果您想將兩個彼此相距很小的漢明距離的單詞映射到相同的值，這已經足夠了。
您可以結合局部敏感散列（ $ LSH $ ) 具有單向功能 $ H $ . 例如你可以做 $ H(LSH(x)) $ 用於數據 $ x $ . 這是單向的，並且具有滿足某些局部性條件的兩個值映射到相同值的特徵。與編碼方法相比，它具有適用於任何領域元素的優點。然而，這裡的局部性是根據域的子空間來定義的。因此，棘手的部分可能是讓你弄清楚你需要什麼樣的 LSH。
這種結構的單向性可以通過還原為原像來顯示 $ y $ 的 $ LSH \circ H $ 給出原像 $ y’=LSH(y) $ 的 $ H $ .