文章相似度 - simhash 计算

Wu Jun 2020-01-09 07:43:49

Categories： > Tags：

比较两篇文章的相似度，传统思路是余弦相似度：先将两篇文章分别进行分词，得到一系列特征向量，然后计算特征向量之间的夹角余弦，从而判断两篇文章的相似度。缺点是文章量大了之后，要计算任意两篇文章之间的夹角余弦是不可想象的。

SimHash 是一种局部敏感哈希算法，它产生的哈希签名在一定程度上可以表征原内容的相似度。其主要思想是降维，将高维的特征向量转化成一个 f 位的指纹（fingerprint），通过算出两个指纹的海明距离（hamming distince）来确定两篇文章的相似度，海明距离越小，越相似。在文章量大了之后，可以通过设计减少海明距离的计算次数。

SimHash 的局限性：对短文本效果不显著，对 500 字以上的效果好一点，文本越长判断的准确率越高。

1 SimHash 算法

SimHash 算法分为 5 个步骤：分词、哈希、加权、合并、降维

1.1 分词

HanLP 分词，Maven 引包

<dependency>
    <groupId>com.hankcs</groupId>
    <artifactId>hanlp</artifactId>
    <version>portable-1.7.3</version>
</dependency>

使用分词

private static Segment SEGMENT = new DijkstraSegment().enableCustomDictionary(true).enableAllNamedEntityRecognize(true);

public List<Term> getTerms(String content) {
    List<Term> terms = SEGMENT.seg(tokens);
    CoreStopWordDictionary.apply(terms);
    return terms;
}

1.2 哈希

通过 hash 函数计算每个单词的 hash 值，hash 值为二进制数 01 组成的 n-bit 签名。

private BigInteger hash(String word) {
    if (null == word || word.length() == 0) {
        return new BigInteger("0");
    }

    char[] chars = word.toCharArray();
    BigInteger wordHash = BigInteger.valueOf(((long) chars[0]) << 7);

    BigInteger mask = new BigInteger("2").pow(64).subtract(new BigInteger("1"));
    
    for (char item : chars) {
        BigInteger temp = BigInteger.valueOf(item);
        wordHash = wordHash.multiply(new BigInteger("1000003")).xor(temp).and(mask);
    }

    wordHash = wordHash.xor(new BigInteger(String.valueOf(word.length())));

    if (wordHash.equals(new BigInteger("-1"))) {
        wordHash = new BigInteger("-2");
    }

    return wordHash;
}

1.3 加权

给单词 hash 值进行加权，即 W = Hash * weight，且遇到 1 则 hash 值和权值正相乘，遇到 0 则 hash 值和权值负相乘。

每个单词的权重是事先（按行业）计算好的。

private double[] getWeightedHash(BigInteger wordHash, Double weight) {
    double[] result = new double[64];
    for (int i = 0; i < 64; i++) {
        BigInteger bitmask = new BigInteger("1").shiftLeft(i);

        if (bigInteger.and(bitmask).signum() != 0) {
            result[i] = weight;
        } else {
            result[i] = -weight;
        }
    }
    return result;
}

1.4 合并

将每个单词的加权结果累加，变成整个文章的加权哈希序列串。

private String getArticleHash(List<Term> terms) {
    double[] result = new double[64];
    for (Term term : terms) {
        String word = term.word;
        double weight = getWordWeight(word);
        double[] wordResult = getWeightedHash(hash(word), weight);
        for (int i = 0; i < 64; i++) {
            result[i] += wordResult[i];
        }
    }
}

1.5 降维

处理文章的加权哈希序列串，如果大于 0 则置 1，否则置 0，从而得到 simhash 值


private String getSimHash(double[] articleHash) {
    StringBuffer simHashBuffer = new StringBuffer();
    for (int i = 0; i < 64; i++) {
        if (articleHash[i] >= 0) {
            simHashBuffer.append("1");
        } else {
            simHashBuffer.append("0");
        }
    }
    return simHashBuffer.toString();
}

2 计算海明距离

在根据文章内容分词、哈希、加权、合并、降维得到 simhash 之后，计算两篇文章的海明距离就可以得到文章相似度。

计算海明距离可用 jdk 自带的 bitCount 方法。

Long simHashLong = Long.parseLong(simHashString);
public int getHammingDistince(Long simHashLong1, Long simHashLong2) {
    return Long.bitCount(simHashLong1 ^ simHashLong2);
}

3 抽屉原理——优化比较流程

对于海量文章，如果要将新的文章跟每一篇文章都挨个计算海明距离，那计算量是不可想象的。

使用抽屉原理，将 64 位的 simhash 分成 4 块，每一块作为 key，另外 3 块合起来作为 value，这样存储将空间占用扩大了 4 倍，但是将计算量减少了 2¹⁶ 倍。

再结合 redis，使用 zset 来存储，用 simhash 中 1 的个数作为 score，可以进一步减少计算次数。

3.1 分块存储

将 64 位分成 4 块，可以直接以 1-16/17-32/33-48/49-64 位划分，也可以用其它的划分方法来使数据分布更均衡。例如将位数按 4 取余，第1、5、9…位为一块，2、6、10…为一块。

分成 4 块后，取第一块为 key，另 3 块为 value，存到 redis 的 zset 中，并且以 value 中 1 的个数为 score。再一次取第 2、3、4 块为 key 进行存储。

这样，将所有文章的 simhash 存储到 redis 中的 4 个桶中。

另外，以 simhash 为 key，文章 id 为 value，存储文章和 simhash 的关系。多篇文章相同有相同 simhash，则将文章 id 拼接。

3.2 去重查找

在查找一篇文章是否重复时，先计算文章的 simhash
然后将 simhash 分成 4 块，分别去 redis 的 4 个 zset 桶查找，寻找以这 4 块为 key 的 zset
因为 key 是一样的，所有海明距离都在 value 中，取出 zset 中 score 范围为（本篇文章 score - 海明距离阈值）~（本篇文章 score + 海明距离阈值）的 value
将 zset 中取出的 value 结合 key 恢复成 simhash，这些就是与新文章重复的 simhash
通过 simhash 就可以找到关联的文章了

使用 Java 进行爬虫

热加载实践