08 文章相似度 - simhash 计算

Wu Jun 2020-03-09 00:00:59
08 系统设计 > 1 通用设计

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

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 倍,但是将计算量减少了 216 倍。

再结合 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 去重查找