如何运用python完成Sim哈希算法

Simhash算法详解

本文主要介绍如何使用Python完成Simhash算法，该算法属于部分比较敏感哈希，可用于测算规模性语义相似度和大量文本内容去重。

如何运用python完成Sim哈希算法

为何需用Simhash？

传统的相关性优化算法，如语义相似度测算，复杂度较高，而Simhash适用于大规模语料的去重。该算法基于hash值的相关性，将二进制比较后获得相距的数量，数据越多则差别越多。

Simhash基本原理

Simhash将文本文档中的中文进行分词，取最高前20个词的权重值（TF-IDF），并将涉及的词汇进行hash，得到长为20的hash值。接着，对相应位置的值进行正、负权重的取值，获得20个长为64的目录，再进行列向累加和之后取0或1即可得到该文本文档的Simhash值。最后，通过计算Simhash值之间的海明距离判断文本文档相似性。

Simhash的不足

Simhash算法对于完全无关的文本存在相同的Simhash值，精确度并不是很高，并且更适用于较长的文本。但在大规模语料进行去重时，计算速度优势较为明显。

Python代码实现如下：

class Simhash:
    def __init__(self, tokens='', hashbits=128):
        self.hashbits = hashbits
        self.hash = self.simhash(tokens)

    def __str__(self):
        return str(self.hash)

    def simhash(self, tokens):
        v = [0]*self.hashbits
        for t in [self._string_hash(x) for x in tokens]:
            for i in range(self.hashbits):
                bitmask = 1 <= 0:
                fingerprint += 1 << i
        return fingerprint

    def hamming_distance(self, other):
        x = (self.hash ^ other.hash) & ((1 << self.hashbits) - 1)
        tot = 0
        while x:
            tot += 1
            x &= x - 1
        return tot

    def similarity(self, other):
        a = float(self.hash)
        b = float(other.hash)
        if a > b:
            return b / a
        else:
            return a / b

    def _string_hash(self, source):
        if source == '':
            return 0
        else:
            x = ord(source[0]) << 7
            m = 1000003
            mask = 2**self.hashbits - 1
            for c in source:
                x = ((x * m) ^ ord(c)) & mask
            x ^= len(source)
            if x == -1:
                x = -2
            return x

原创文章，作者：小编小本本，如若转载，请注明出处：https://www.benjiyun.com/yunzhujiyunwei/vps-yunwei/6808.html