字元串比對算法之SimHash算法

　　由于實驗室和網際網路基本沒啥關系，也就從來沒有關注過資料挖掘相關的東西。在實際工作中，第一次接觸到比對和聚類等工作，雖然用一些簡單的比對算法可以做小資料的聚類，但資料量達到一定的時候就束手無策了。 　　是以，趁着周末把這方面的東西看了看，做個筆記。

　　google的論文“detecting near-duplicates for web crawling”--------simhash。

　　google采用這種算法來解決萬億級别的網頁的去重任務。　　

　　simhash算法的主要思想是降維，将高維的特征向量映射成一個低維的特征向量，通過兩個向量的hamming distance來确定文章是否重複或者高度近似。

步驟：　　

對于給定的一段語句，進行分詞，得到有效的特征向量

為每一個特征向量設定一個權值

對每一個特征向量計算hash值，為01組成的n-bit簽名

所有特征向量進行權重（1則為正，0則為負），然後累加

對于n-bit簽名的累加結果，如果>0置1，否則置0

得到該語句的simhash值

根據不同語句simhash的海明距離就來判斷相似程度

　　simhash用于比較大文本，比如500字以上效果都還蠻好，距離小于3的基本都是相似，誤判率也比較低。

　　這樣的話，小文本呢？如何解決？

<a href="http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html">http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html</a>

<a href="http://www.cnblogs.com/zhengyun_ustc/archive/2012/06/12/sim.html">http://www.cnblogs.com/zhengyun_ustc/archive/2012/06/12/sim.html</a>

<a href="http://blog.jobbole.com/21928/">http://blog.jobbole.com/21928/</a>