如何捕獲相似基因（兩個(gè)相似哈希算法分析）
普通的哈希函數(shù)具有如下特點(diǎn)
- 可將任意長度的輸入映射為固定長度的輸出
- 不同的輸入較大概率映射為不同的輸出
可見，普通的哈希算法得到的輸出（哈希值）可以很好判定兩個(gè)文本是否相同。即哈希值雖然拋棄了文本的原始內(nèi)容，但其繼承了輸入文本的某種基因，能夠精確表達(dá)文本的內(nèi)容。
所謂相似哈希，就是一個(gè)特殊的映射函數(shù)，具有如下特點(diǎn)
- 可將任意長度的輸入映射為固定長度的輸出
- 相似的輸入具有相同或相似的輸出
與普通哈希算法不同，相似哈希算法繼承了原輸入文本更多的基因——相似基因。下面來介紹simhash算法。來看算法是如何捕獲相似基因的。后面會(huì)介紹LSH算法，可以看出其捕獲相似基因的方法是類似的。
以文本信息為例，simhash算法的大體思路是：
- 將文本分詞
- 統(tǒng)計(jì)每個(gè)詞出現(xiàn)的次數(shù)，假設(shè)有n個(gè)詞
- 設(shè)定一個(gè)普通hash函數(shù)，能將詞映射為一個(gè)固定長度（假設(shè)32bit）的數(shù)字，此處稱為摘要
- 計(jì)算每個(gè)詞的摘要。生成n個(gè)摘要（每個(gè)摘要為一個(gè)32bit數(shù)字）。
- 我們計(jì)算出的輸入文本的相似哈希值也是一個(gè)32bit數(shù)字，這個(gè)數(shù)字的每一個(gè)二進(jìn)制位是由步驟4計(jì)算出的n個(gè)摘要決定的。于是n個(gè)摘要對(duì)每一個(gè)二進(jìn)制位進(jìn)行了一次投票。少數(shù)服從多數(shù)。比如，當(dāng)n個(gè)摘要對(duì)相似哈希的第1個(gè)二進(jìn)制位進(jìn)行投票，其中有m個(gè)摘要第一個(gè)二進(jìn)制位為1，n-m個(gè)摘要的第一個(gè)二進(jìn)制位為0，則當(dāng)m>n-m時(shí)，則相似哈希的第1個(gè)二進(jìn)制位為1，m<=n-m時(shí)為0。
經(jīng)過如上5步，可以得到一個(gè)相似哈希值，還可以在第5步投票的時(shí)候考慮每個(gè)詞出現(xiàn)的頻次。即頻次高的數(shù)字摘要投票的結(jié)果要加倍考慮，倍數(shù)就是詞的頻次。
通過分析simhash算法可以得到捕獲相似基因的思路
- 將輸入進(jìn)行合理分割
- 每個(gè)分割單元基本不變，具有獨(dú)立的含義（每個(gè)詞有獨(dú)立的含義，變一個(gè)字可能整個(gè)意義都變了）
- 輸入的變化是分割單元的變化（若輸入文本發(fā)生相似變化，也是個(gè)別詞不一樣）
- 對(duì)分割單元進(jìn)行頻次統(tǒng)計(jì)，頻次越高的分割單元相似基因越強(qiáng)
- 采用投票方式找出最強(qiáng)的相似基因作為相似哈希
其中最重要的兩個(gè)步驟是合理分割變化單元和利用變化單元的統(tǒng)計(jì)特征。幾乎所有的相似哈希算法都是應(yīng)用了這兩個(gè)步驟。下面簡述一下LSH算法，可以看到其也是利用上述兩個(gè)步驟完成相似基因的捕獲的。
還是以文本信息為例，LSH算法的思路如下：
- 將輸入進(jìn)行分詞
- 生成n種不同的將詞映射到一個(gè)數(shù)字的映射方法。
- 針對(duì)n種映射方法的第i(i=1,...,n)種，進(jìn)行如下計(jì)算
- 將輸入文本的所有詞輸入第i種映射，每個(gè)詞計(jì)算出一個(gè)映射值
- 取所有映射值的最小值作為第i種映射方法計(jì)算出的輸入文本映射值
- 通過步驟3可計(jì)算出n個(gè)文本映射值。將這n個(gè)文本映射值作為文本的相似基因。
分析如上步驟，可以看出其也是對(duì)輸入信息進(jìn)行了合理的分割。由于n中映射方法完全是隨機(jī)的，則每種映射方法所得到的文本映射值相當(dāng)于從分詞中的隨機(jī)獲取一個(gè)詞。兩個(gè)相似文本通常是存在大量相同詞語的，僅有少數(shù)詞語不同的。如果進(jìn)行隨機(jī)抽取，抽取到相同部分詞語的概率會(huì)比不同詞語的概率大。故其也是利用到了分割單元的統(tǒng)計(jì)信息進(jìn)行相似基因的獲取的。
