原文

两千零七年发表的论文《Detecting Near-Duplicates for Web Crawling》中提到的一种指纹生成算法又或者叫指纹提取算法，被Google广泛应用于亿级的网页去重job，其主要思想就是降维，什么是降维呢！简单来说就是“通过多条信息确定一件事，变成一条信息确定一件事”，Simhash算法就能来做这件事儿!

我们的文章去重也需要这个东西，所以研究了一下，直接展示代码

算法工作流程图

logo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
from collections import Counter
import pprint

import pkuseg
import numpy as np


work_stops_path = 'stop_words.txt'

seg = pkuseg.pkuseg()

data = """青年是国家建设的栋梁之才，也是国际交往的活跃力量。近年来，习近平主席通过各种方式，亲自做青年友好的工作，以青年为纽带桥梁，深化中国与世界的友谊合作，推动不同文明的交流互鉴，为构建人类命运共同体凝聚蓬勃力量、汇聚希望之光。在大学发表演讲，给青年学生回信，同青年代表亲切交谈，向青年活动致贺信……一场场交流、一句句箴言，饱含习主席对各国青年的深切勉励、殷切期望。2015年4月，习主席在北京出席第十五届中越青年友好会见活动时讲过这样一句话：“‘国之交在于民相亲’，而‘民相亲’要从青年做起。”无论是面对面交流，还是信函互动，“友好”、“友谊”是习主席同各国青年谈心时反复出现的关键词。"""
text = seg.cut(data)

with open(work_stops_path, encoding="utf-8") as f:
        stopwords = f.read()

new_text = [w for w in text if w not in stopwords]


def string_hash(source):
    if source == "":
        return 0
    else:
        x = ord(source[0]) << 7
        m = 1000003
        mask = 2 ** 128 - 1
        for c in source:
            x = ((x * m) ^ ord(c)) & mask
        x ^= len(source)
        if x == -1:
            x = -2
        x = bin(x).replace('0b', '').zfill(64)[-64:]
        # print(source,x)

        return str(x)


def simhash(new_text):

    counter = Counter(new_text)  # 内容整理 [('今天': 3), ('明天': 2)]
    # pprint.pprint(counter.most_common())  # .most_common(数量可控)

    key_list = []
    for feature, weight in counter.most_common():
        weight = int(weight * 10)
        str_feature = string_hash(feature)
        temp = []
        for i in str_feature:
            if i == '1':
                temp.append(weight)
            else:
                temp.append(-weight)
        key_list.append(temp)
    lst = np.sum(np.array(key_list), axis=0)
    if key_list == []:
        return '00'
    simhash = ''
    for i in lst:
        if i > 0:
            simhash = simhash + '1'
        else:
            simhash = simhash + '0'
    
    return simhash


def hamming_dis(simhash):
    # 海明距离
    t1 = '0b' + '0010010010010000000110111101001001010010010001010001001110000000'
    t2 = '0b' + simhash
    print(t1)
    print(t2)
    n=int(t1, 2) ^ int(t2, 2)
    i=0
    while n:
        n &= (n-1)
        i+=1
    return i


def main():
    result = simhash(new_text)
    res = hamming_dis(result)
    print(res)


if __name__ == "__main__":
    main()

鸽巢原理

待实现 HBash