slipper | Hacking Book | Free Online Hacking Learning

30 Jan 2014

Simhash is an algorithm used by Google to deal with massive text de duplication. Google products, you know. One of the most powerful points of simhash is to convert a document into a 64 bit byte, which is temporarily called a character word. Then, to judge the repetition, you only need to judge whether the distance of their character words is < n (generally, n is 3 according to experience), and then you can judge whether the two files are similar.

principle

The generation of simhash values is illustrated as follows

It will take about three minutes to understand the figure and realize the simhash algorithm. It's very simple. Google products, simple and practical.

The algorithm process is as follows:

Doc is used to extract keywords (including segmentation and calculation of weights), and N pairs (keywords, weights) are extracted, that is, features, weights in the graph. Record as feature "weight" pairs = [fw1, FW2 FWN], where FWN = (feature_n, weight_n `).

(feature, weight) feature_weight_pairs ，其中 fwn = ( ,

Hash ﹣ weight ﹣ pairs = [(hash (feature), weight) for feature, weight in feature ﹣ weight ﹣ pairs] generate the (hash, weight) in the graph. At this time, assume that the bits ﹣ count = 6 generated by hash (as shown in the graph);

hash_weight_pairs feature_weight_pairs (hash,weight) bits_count = 6

Then add up the bits of the hash ﹣ weight ﹣ pairs vertically. If the bit is 1, + weight, if it is 0, - weight, and finally generate bits ﹣ count numbers, as shown in the figure [13, 108, - 22, - 5, - 32, 55]. The value generated here is related to the algorithm used in the hash function.

hash_weight_pairs +weight -weight bits_count [13, 108, -22, -5, -32, 55]

[13108, - 22, - 5, - 32,55] - > 110001 this is very simple, positive 1 negative 0.

[13,108,-22,-5,-32,55] -> 110001

So far, how to move from a doc to a simhash value has been explained. But there's another important part,

"Calculation of Hamming distance of simhash value"

The Hamming distance between binary string a and binary string B is the number of 1 in binary after a XOR B.

A xor B

For example:

A = 100111;
B = 101010;
hamming_distance(A, B) = count_1(A xor B) = count_1(001101) = 3;

After we calculate the simhash value of all docs, we need to calculate whether doc A and DOC B are similar

Whether the Hamming distance between a and B is less than or equal to N, which is generally taken as 3 according to experience,

Simhash is essentially a locally sensitive hash, which is different from MD5 and the like. Because of its local sensitivity, we can use Hamming distance to measure the similarity of simhash value.

"Efficient calculation of number of 1 in binary sequence"

/* src/Simhasher.hpp */
bool isEqual(uint64_t lhs, uint64_t rhs, unsigned short n = 3)
{
    unsigned short cnt = 0;
    lhs ^= rhs;
    while(lhs && cnt <= n)
    {
        lhs &= lhs - 1;
        cnt++;
    }
    if(cnt <= n)
    {
        return true;
    }
    return false;
}

If calculated by the above function, the time complexity is O (n); the default value of N here is 3. This shows that it is quite efficient.

"Implementation of O (1) algorithm to calculate the number of 1 in binary sequence"

Thank you @ schatwang for your comments:

Thank you for the simhash library. It will be very convenient. There are various implementations of O (1) for finding the number of 1 in binary. Please refer to this place: http://stackoverflow.com/a/14682688

Project implemented by simhash

C + + version simhash
Golang version gosimhash

Mainly for Chinese documents, that is to say, before simhash for this project, word segmentation and keyword extraction are also carried out.

Compare other algorithms

"Baidu's de duplication algorithm"

Baidu's de recalculation method is the simplest, which is to directly find out the longest n sentences of this article and do a hash signature. N is generally taken as 3. It is said that the accuracy and recall rate can reach more than 80%.

"Shine algorithm"

The principle of shingle is a little complicated, not detailed. I think the algorithm is too academic, not friendly to engineering implementation, too slow, and basically unable to deal with massive data.

Other algorithms

See the discussion on Weibo

Reference resources

Similarity estimation techniques from rounding algorithms
Simhash and Google's web page de duplication
Simhash and Hamming distance for similarity calculation of massive data

Reprint please indicate the source: the principle and implementation of simhash algorithm