simhash-- 一种文档去重的算法

2024-02-15 19:38:36

最早看数学之美的时候，书中就提到了这个算法，当时没有做过相关地工作，没什么具体的印象。一年前转岗时面试时别人提到了这个算法，知道了simhash可以用来解决网页等海量数据的去重问题，很高效。

然后自己大概实现了一下这个算法的python版本，试了一下，感觉还不错，mark下吧

# coding=utf-8

import os

single_bits = {}

for x in xrange(32):

    single_bits[x] = 1 << x

print single_bits

def simhash(str):

    simhash_map = {}

    for x in xrange(32):

        simhash_map[x] = 0

    for c in str:

        h = hash(c)

        for bit in single_bits:

            if h & single_bits[bit] == 0:

                simhash_map[bit] -= 1

            else:

                simhash_map[bit] += 1

    result = 0

    for x in xrange(32):

        if simhash_map[x] > 0:

            result |= single_bits[x]

    return result

def haiming_dis(simhash1, simhash2):

    dis = 0

    sh = simhash1 ^ simhash2

    for x in xrange(32):

        if sh & (1 << x) > 0:

            dis += 1

    return dis

if __name__ == "__main__":

    str = "事实上，传统比较两个文本相似性的方法，大多是将文本分词之后，转化为特征向量距离的度量，比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应，但这种方法的一个最大的缺点就是，无法将其扩展到海量数据。例如，试想像Google那种收录了数以几十亿互联网信息的大型搜索引擎，每天都会通过爬虫的方式为自己的索引库新增的数百万网页，如果待收录每一条数据都去和网页库里面的每条记录算一下余弦角度，其计算量是相当恐怖的。"

    str2 = "事实上，传统比较两个文本相似性的方法，大多是将文本分词之后，转化为特征向量距离的度量，比如常见的几何距离或者余弦角度等等。两两比较固然能很好地适应，但这种方法的一个最大的优点就是，无法将其扩展到海量数据。例如，试想像baidu那种收录了数以几十亿互联网信息的大型搜索引擎，每天都会通过爬虫的方式为自己的索引库新增的数百万网页，如果待收录每一条数据都去和网页库里面的每条学习算一下余弦角度，其计算量是相当恐怖的。"

    sh1 = simhash(str)

    sh2 = simhash(str2)

    print sh1

    print sh2

    print haiming_dis(sh1, sh2)

输出结果为：

码农公寓

相关文章