simHash 簡介以及 java 實現

jopen 11年前發布 | 125K 次閱讀 simHash

傳統的 hash 算法只負責將原始內容盡量均勻隨機地映射為一個簽名值，原理上相當于偽隨機數產生算法。產生的兩個簽名，如果相等，說明原始內容在一定概率下是相等的；如果不相等，除了說明原始內容不相等外，不再提供任何信息，因為即使原始內容只相差一個字節，所產生的簽名也很可能差別極大。從這個意義上來說，要設計一個 hash 算法，對相似的內容產生的簽名也相近，是更為艱難的任務，因為它的簽名值除了提供原始內容是否相等的信息外，還能額外提供不相等的原始內容的差異程度的信息。
而 Google 的 simhash 算法產生的簽名，可以滿足上述要求。出人意料，這個算法并不深奧，其思想是非常清澈美妙的。

1、Simhash 算法簡介

simhash算法的輸入是一個向量，輸出是一個 f 位的簽名值。為了陳述方便，假設輸入的是一個文檔的特征集合，每個特征有一定的權重。比如特征可以是文檔中的詞，其權重可以是這個詞出現的次數。 simhash 算法如下：
1，將一個 f 維的向量 V 初始化為 0 ； f 位的二進制數 S 初始化為 0 ；
2，對每一個特征：用傳統的 hash 算法對該特征產生一個 f 位的簽名 b 。對 i=1 到 f ：
如果b 的第 i 位為 1 ，則 V 的第 i 個元素加上該特征的權重；
否則，V 的第 i 個元素減去該特征的權重。
3，如果 V 的第 i 個元素大于 0 ，則 S 的第 i 位為 1 ，否則為 0 ；
4，輸出 S 作為簽名。

2、算法幾何意義和原理

這個算法的幾何意義非常明了。它首先將每一個特征映射為f維空間的一個向量，這個映射規則具體是怎樣并不重要，只要對很多不同的特征來說，它們對所對應的向量是均勻隨機分布的，并且對相同的特征來說對應的向量是唯一的就行。比如一個特征的4位hash簽名的二進制表示為1010，那么這個特征對應的 4維向量就是(1, -1, 1, -1)T，即hash簽名的某一位為1，映射到的向量的對應位就為1，否則為-1。然后，將一個文檔中所包含的各個特征對應的向量加權求和，加權的系數等于該特征的權重。得到的和向量即表征了這個文檔，我們可以用向量之間的夾角來衡量對應文檔之間的相似度。最后，為了得到一個f位的簽名，需要進一步將其壓縮，如果和向量的某一維大于0，則最終簽名的對應位為1，否則為0。這樣的壓縮相當于只留下了和向量所在的象限這個信息，而64位的簽名可以表示多達264個象限，因此只保存所在象限的信息也足夠表征一個文檔了。

明確了算法了幾何意義，使這個算法直觀上看來是合理的。但是，為何最終得到的簽名相近的程度，可以衡量原始文檔的相似程度呢？這需要一個清晰的思路和證明。在simhash的發明人Charikar的論文中[2]并沒有給出具體的simhash算法和證明，以下列出我自己得出的證明思路。

Simhash是由隨機超平面hash算法演變而來的，隨機超平面hash算法非常簡單，對于一個n維向量v，要得到一個f位的簽名(f<
1，隨機產生f個n維的向量r1,…rf；
2，對每一個向量ri，如果v與ri的點積大于0，則最終簽名的第i位為1，否則為0.

這個算法相當于隨機產生了f個n維超平面，每個超平面將向量v所在的空間一分為二，v在這個超平面上方則得到一個1，否則得到一個0，然后將得到的 f個0或1組合起來成為一個f維的簽名。如果兩個向量u, v的夾角為θ，則一個隨機超平面將它們分開的概率為θ/π，因此u, v的簽名的對應位不同的概率等于θ/π。所以，我們可以用兩個向量的簽名的不同的對應位的數量，即漢明距離，來衡量這兩個向量的差異程度。

Simhash算法與隨機超平面hash是怎么聯系起來的呢？在simhash算法中，并沒有直接產生用于分割空間的隨機向量，而是間接產生的：第 k個特征的hash簽名的第i位拿出來，如果為0，則改為-1，如果為1則不變，作為第i個隨機向量的第k維。由于hash簽名是f位的，因此這樣能產生 f個隨機向量，對應f個隨機超平面。下面舉個例子：
假設用5個特征w1,…,w5來表示所有文檔，現要得到任意文檔的一個3維簽名。假設這5個特征對應的3維向量分別為：
h(w1) = (1, -1, 1)T
h(w2) = (-1, 1, 1)T
h(w3) = (1, -1, -1)T
h(w4) = (-1, -1, 1)T
h(w5) = (1, 1, -1)T

按simhash算法，要得到一個文檔向量d=(w1=1, w2=2, w3=0, w4=3, w5=0) T的簽名，

先要計算向量m = 1*h(w1) + 2*h(w2) + 0*h(w3) + 3*h(w4) + 0*h(w5) = (-4, -2, 6) T，
然后根據simhash算法的步驟3，得到最終的簽名s=001。

上面的計算步驟其實相當于，先得到3個5維的向量，第1個向量由h(w1),…,h(w5)的第1維組成：

r1=(1,-1,1,-1,1) T；
第2個5維向量由h(w1),…,h(w5)的第2維組成：
r2=(-1,1,-1,-1,1) T；
同理，第3個5維向量為：
r3=(1,1,-1,1,-1) T.
按隨機超平面算法的步驟2，分別求向量d與r1,r2,r3的點積:
d T r1=-4 < 0，所以s1=0;
d T r2=-2 < 0，所以s2=0;
d T r3=6 > 0，所以s3=1.
故最終的簽名s=001，與simhash算法產生的結果是一致的。

從上面的計算過程可以看出，simhash算法其實與隨機超平面hash算法是相同的，simhash算法得到的兩個簽名的漢明距離，可以用來衡量原始向量的夾角。這其實是一種降維技術，將高維的向量用較低維度的簽名來表征。衡量兩個內容相似度，需要計算漢明距離，這對給定簽名查找相似內容的應用來說帶來了一些計算上的困難；我想，是否存在更為理想的simhash算法，原始內容的差異度，可以直接由簽名值的代數差來表示呢？

3、比較相似度

海明距離：兩個碼字的對應比特取值不同的比特數稱為這兩個碼字的海明距離。一個有效編碼集中, 任意兩個碼字的海明距離的最小值稱為該編碼集的海明距離。舉例如下： 10101 和 00110 從第一位開始依次有第一位、第四、第五位不同，則海明距離為 3.

異或：只有在兩個比較的位不同時其結果是1 ，否則結果為 0

對每篇文檔根據SimHash 算出簽名后，再計算兩個簽名的海明距離（兩個二進制異或后 1 的個數）即可。根據經驗值，對 64 位的 SimHash ，海明距離在 3 以內的可以認為相似度比較高。
假設對64 位的 SimHash ，我們要找海明距離在 3 以內的所有簽名。我們可以把 64 位的二進制簽名均分成 4塊，每塊 16 位。根據鴿巢原理（也成抽屜原理，見組合數學），如果兩個簽名的海明距離在 3 以內，它們必有一塊完全相同。
我們把上面分成的4 塊中的每一個塊分別作為前 16 位來進行查找。建立倒排索引。

simHash 簡介以及 java 實現

如果庫中有2^34 個（大概 10 億）簽名，那么匹配上每個塊的結果最多有 2^(34-16)=262144 個候選結果 (假設數據是均勻分布， 16 位的數據，產生的像限為 2^16 個，則平均每個像限分布的文檔數則 2^34/2^16 = 2^(34-16)) ，四個塊返回的總結果數為 4* 262144 （大概 100 萬）。原本需要比較 10 億次，經過索引，大概就只需要處理 100 萬次了。由此可見，確實大大減少了計算量。

4、示例代碼：

/**

Function: 注：該示例程序暫不支持中文

Date:     2013-8-4 下午11:01:45

@author   june: decli@qq.com
*/
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;


public class SimHash {

private String tokens;

private BigInteger intSimHash;

private String strSimHash;

private int hashbits = 64;

public SimHash(String tokens) {
    this.tokens = tokens;
    this.intSimHash = this.simHash();
}

public SimHash(String tokens, int hashbits) {
    this.tokens = tokens;
    this.hashbits = hashbits;
    this.intSimHash = this.simHash();
}

HashMap<STRING, integer=""> wordMap = new HashMap<STRING, integer="">();

public BigInteger simHash() {
    // 定義特征向量/數組
    int[] v = new int[this.hashbits];
    // 1、將文本去掉格式后, 分詞.
    StringTokenizer stringTokens = new StringTokenizer(this.tokens);
    while (stringTokens.hasMoreTokens()) {
        String temp = stringTokens.nextToken();
        // 2、將每一個分詞hash為一組固定長度的數列.比如 64bit 的一個整數.
        BigInteger t = this.hash(temp);
        for (int i = 0; i < this.hashbits; i++) {
            BigInteger bitmask = new BigInteger("1").shiftLeft(i);
            // 3、建立一個長度為64的整數數組(假設要生成64位的數字指紋,也可以是其它數字),
            // 對每一個分詞hash后的數列進行判斷,如果是1000...1,那么數組的第一位和末尾一位加1,
            // 中間的62位減一,也就是說,逢1加1,逢0減1.一直到把所有的分詞hash數列全部判斷完畢.
            if (t.and(bitmask).signum() != 0) {
                // 這里是計算整個文檔的所有特征的向量和
                // 這里實際使用中需要 +- 權重，而不是簡單的 +1/-1，
                v[i] += 1;
            } else {
                v[i] -= 1;
            }
        }
    }
    BigInteger fingerprint = new BigInteger("0");
    StringBuffer simHashBuffer = new StringBuffer();
    for (int i = 0; i < this.hashbits; i++) {
        // 4、最后對數組進行判斷,大于0的記為1,小于等于0的記為0,得到一個 64bit 的數字指紋/簽名.
        if (v[i] >= 0) {
            fingerprint = fingerprint.add(new BigInteger("1").shiftLeft(i));
            simHashBuffer.append("1");
        } else {
            simHashBuffer.append("0");
        }
    }
    this.strSimHash = simHashBuffer.toString();
    System.out.println(this.strSimHash + " length " + this.strSimHash.length());
    return fingerprint;
}

private BigInteger hash(String source) {
    if (source == null || source.length() == 0) {
        return new BigInteger("0");
    } else {
        char[] sourceArray = source.toCharArray();
        BigInteger x = BigInteger.valueOf(((long) sourceArray[0]) << 7);
        BigInteger m = new BigInteger("1000003");
        BigInteger mask = new BigInteger("2").pow(this.hashbits).subtract(new BigInteger("1"));
        for (char item : sourceArray) {
            BigInteger temp = BigInteger.valueOf((long) item);
            x = x.multiply(m).xor(temp).and(mask);
        }
        x = x.xor(new BigInteger(String.valueOf(source.length())));
        if (x.equals(new BigInteger("-1"))) {
            x = new BigInteger("-2");
        }
        return x;
    }
}

public int hammingDistance(SimHash other) {

    BigInteger x = this.intSimHash.xor(other.intSimHash);
    int tot = 0;

    // 統計x中二進制位數為1的個數
    // 我們想想，一個二進制數減去1，那么，從最后那個1（包括那個1）后面的數字全都反了，對吧，然后，n&(n-1)就相當于把后面的數字清0，
    // 我們看n能做多少次這樣的操作就OK了。

    while (x.signum() != 0) {
        tot += 1;
        x = x.and(x.subtract(new BigInteger("1")));
    }
    return tot;
}

public int getDistance(String str1, String str2) {
    int distance;
    if (str1.length() != str2.length()) {
        distance = -1;
    } else {
        distance = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                distance++;
            }
        }
    }
    return distance;
}

public List subByDistance(SimHash simHash, int distance) {
    // 分成幾組來檢查
    int numEach = this.hashbits / (distance + 1);
    List characters = new ArrayList();

    StringBuffer buffer = new StringBuffer();

    int k = 0;
    for (int i = 0; i < this.intSimHash.bitLength(); i++) {
        // 當且僅當設置了指定的位時，返回 true
        boolean sr = simHash.intSimHash.testBit(i);

        if (sr) {
            buffer.append("1");
        } else {
            buffer.append("0");
        }

        if ((i + 1) % numEach == 0) {
            // 將二進制轉為BigInteger
            BigInteger eachValue = new BigInteger(buffer.toString(), 2);
            System.out.println("----" + eachValue);
            buffer.delete(0, buffer.length());
            characters.add(eachValue);
        }
    }

    return characters;
}

public static void main(String[] args) {
    String s = "This is a test string for testing";
    SimHash hash1 = new SimHash(s, 64);
    System.out.println(hash1.intSimHash + "  " + hash1.intSimHash.bitLength());
    hash1.subByDistance(hash1, 3);

    s = "This is a test string for testing, This is a test string for testing abcdef";
    SimHash hash2 = new SimHash(s, 64);
    System.out.println(hash2.intSimHash + "  " + hash2.intSimHash.bitCount());
    hash1.subByDistance(hash2, 3);

    s = "This is a test string for testing als";
    SimHash hash3 = new SimHash(s, 64);
    System.out.println(hash3.intSimHash + "  " + hash3.intSimHash.bitCount());
    hash1.subByDistance(hash3, 4);

    System.out.println("============================");

    int dis = hash1.getDistance(hash1.strSimHash, hash2.strSimHash);
    System.out.println(hash1.hammingDistance(hash2) + " " + dis);

    int dis2 = hash1.getDistance(hash1.strSimHash, hash3.strSimHash);
    System.out.println(hash1.hammingDistance(hash3) + " " + dis2);

    //通過Unicode編碼來判斷中文
    /*String str = "中國chinese";
    for (int i = 0; i < str.length(); i++) {
        System.out.println(str.substring(i, i + 1).matches("[\\u4e00-\\u9fbb]+"));
    }*/

}

}</STRING,></STRING,></pre> 
5、適用場景： 

simHash在短文本的可行性：


測試相似文本的相似度與漢明距離

測試文本：20個城市名作為詞串：北京,上海,香港,深圳,廣州,臺北,南京,大連,蘇州,青島,無錫,佛山,重慶,寧波,杭州,成都,武漢,澳門,天津,沈陽 

 

相似度矩陣： 

 

simHash碼： 

 

勘誤：0.667, Hm:13 是對比的msg 1與2。

可見：相似度在0.8左右的Hamming距離為7，只有相似度高到0.9412，Hamming距離才近到4，此時，反觀Google對此算法的應用場景：網頁近重復。

鏡像網站、內容復制、嵌入廣告、計數改變、少量修改。

以上原因對于長文本來說造成的相似度都會比較高，而對于短文本來說，如何處理海量數據的相似度文本更為合適的？ 

測試短文本（長度在8個中文字符～45個中文字符之間）相似性的誤判率如下圖所示：








REF： 

1、simHash 簡介以及java實現 

http://blog.sina.com.cn/s/blog_4f27dbd501013ysm.html 

2、對simhash算法的一些思考 

http://2588084.blog.51cto.com/2578084/558873 

3、Simhash算法原理和網頁查重應用 

http://blog.sina.com.cn/s/blog_72995dcc010145ti.html 

4、其它 

http://www.cnblogs.com/zhengyun_ustc/archive/2012/06/12/sim.html 

http://tech.uc.cn/?p=1086 

http://jacoxu.com/?p=369  simHash是否適合短文本的相似文本匹配 

https://github.com/sing1ee/simhash-java 
</N)，算法如下：<></span>