如何計算相似字符串的同等散列值？

Question

我創建Antiplagiat。我使用木瓦方法。例如，我有以下的帶狀皰疹：

1. 我去電影院
2. 我去電影1
3. 我去屆電影

是否有計算等的方法散列這些行？

我知道Levenshtein距離的存在。但是，我不知道我應該拿什麼來源字。也許有比考慮Levenshtein距離更好的方法。

Answer 1

哈希的問題在於，在邏輯上，您將碰到2個字符串，這些字符串會因散列爲不同值的單個字符而不同。

小證明：

考慮所有可能的字符串。
假設所有這些散列至少有2個不同的值。
取任何2個字符串A和B，以散列爲不同的值。
您顯然可以通過一次更改一個字符從A到B。
因此在某些時候哈希將會改變。
因此，在這一點上，單個字符變化的散列值將會不同。

我能想到的一些選項：字符串

• 哈希多個部分，並檢查這些哈希。可能不會工作得太好，因爲單個字符的省略會導致哈希值的顯着差異。

• 檢查散列的範圍。散列是一維的，但字符串相似性不是，因此這可能也不起作用。

總而言之，哈希可能不是要走的路。

Answer 2

這個問題是有點老，但在AT & T.他們採用的技術是讓人聯想到Nilsimsa散列時類似短信已被視爲「異常」號檢測到您可能感興趣的this paper由兩名研究人員時間窗口中的時間。

這聽起來Locality Sensitive hashing也將與您的問題有關。