每日算法 — 使用java实现SimHash：局部敏感哈希与海量文本近似去重

算法引入

在互联网时代，搜索引擎每天需要处理数十亿网页。一个核心挑战是：如何快速判断两个网页是否内容相似？ 传统的逐字符比较需要O(n)时间，无法在十亿级别网页上运行。SimHash由Moses Charikar于2002年提出，是一种局部敏感哈希（Locality Sensitive Hashing, LSH）算法，能将相似文档映射为相似的哈希值。Google利用SimHash在海量网页中实现了近实时的重复内容检测，将百亿级文本对的相似度比较转化为常数时间的汉明距离计算。

核心思想

SimHash的核心思想是：让哈希值本身携带内容的相似信息。传统哈希（如MD5）要求微小改动导致完全不同的哈希值（雪崩效应），而SimHash要求相似文档产生仅有少量位差异的哈希值。通过将文档的特征向量投影到随机超平面上，SimHash生成一个固定位数的指纹，两个文档的相似度可通过指纹的汉明距离直接估算。

算法流程

1. 特征提取：将文档切分为N-gram特征词，计算每个特征的权重（如TF-IDF）
2. 哈希映射：对每个特征词计算其传统哈希值（如64位MurmurHash）
3. 加权叠加：将每个特征的哈希值转换为+1/-1向量，乘以其权重后累加到总向量
4. 降维签名：对累加向量的每个维度，若值大于0则对应位为1，否则为0
5. 相似度判断：两个文档的SimHash指纹的汉明距离越小，文档越相似

Java完整实现

import java.util.*;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

/**
 * SimHash局部敏感哈希实现
 * 用于海量文档的近似重复检测与相似度计算
 */
public class SimHash {

    private final int hashBits; // 哈希位数，通常为64

    public SimHash() {
        this(64);
    }

    public SimHash(int hashBits) {
        this.hashBits = hashBits;
    }

    /**
     * 计算字符串的SimHash指纹
     * @param text 输入文本
     * @return SimHash指纹（大整数形式）
     */
    public long compute(String text) {
        // 1. 分词并统计词频
        Map<String, Integer> wordFreq = tokenizeAndCount(text);

        // 2. 初始化加权向量
        int[] weightedVector = new int[hashBits];

        // 3. 对每个特征词计算哈希并加权累加
        for (Map.Entry<String, Integer> entry : wordFreq.entrySet()) {
            String word = entry.getKey();
            int weight = entry.getValue();

            // 计算特征词的哈希值
            long wordHash = murmurHash64(word);

            // 将哈希值的每一位转换为+weight/-weight累加到向量
            for (int i = 0; i < hashBits; i++) {
                long bitMask = 1L << i;
                if ((wordHash & bitMask) != 0) {
                    weightedVector[i] += weight;
                } else {
                    weightedVector[i] -= weight;
                }
            }
        }

        // 4. 降维：根据加权向量的符号生成最终指纹
        long fingerprint = 0;
        for (int i = 0; i < hashBits; i++) {
            if (weightedVector[i] > 0) {
                fingerprint |= (1L << i);
            }
        }

        return fingerprint;
    }

    /**
     * 简单的中文/英文分词与词频统计
     * 实际应用中可替换为更精确的分词器（如Jieba、HanLP）
     */
    private Map<String, Integer> tokenizeAndCount(String text) {
        Map<String, Integer> freq = new HashMap<>();

        // 预处理：去除标点、转为小写
        String cleaned = text.replaceAll("[^\\u4e00-\\u9fa5a-zA-Z0-9]", " ").toLowerCase();

        // 英文按空格分词
        String[] englishWords = cleaned.split("\\s+");
        for (String word : englishWords) {
            if (word.length() >= 2 && word.matches("[a-z0-9]+")) {
                freq.merge(word, 1, Integer::sum);
            }
        }

        // 中文按字符N-gram分词（2-gram）
        String chineseOnly = text.replaceAll("[^\\u4e00-\\u9fa5]", "");
        for (int i = 0; i < chineseOnly.length() - 1; i++) {
            String bigram = chineseOnly.substring(i, i + 2);
            freq.merge(bigram, 1, Integer::sum);
        }

        return freq;
    }

    /**
     * MurmurHash 64位实现（种子固定为0）
     * 高质量的非加密哈希函数
     */
    private long murmurHash64(String key) {
        long seed = 0x12345678L;
        long m = 0xc6a4a7935bd1e995L;
        int r = 47;

        byte[] data = key.getBytes(java.nio.charset.StandardCharsets.UTF_8);
        int len = data.length;
        long h = seed ^ (len * m);

        int len8 = len >> 3;
        for (int i = 0; i < len8; i++) {
            int i8 = i << 3;
            long k = ((long) data[i8] & 0xff)
                    | (((long) data[i8 + 1] & 0xff) << 8)
                    | (((long) data[i8 + 2] & 0xff) << 16)
                    | (((long) data[i8 + 3] & 0xff) << 24)
                    | (((long) data[i8 + 4] & 0xff) << 32)
                    | (((long) data[i8 + 5] & 0xff) << 40)
                    | (((long) data[i8 + 6] & 0xff) << 48)
                    | (((long) data[i8 + 7] & 0xff) << 56);

            k *= m;
            k ^= k >>> r;
            k *= m;

            h ^= k;
            h *= m;
        }

        int remain = len - (len8 << 3);
        switch (remain) {
            case 7: h ^= (long) (data[len - 7] & 0xff) << 48;
            case 6: h ^= (long) (data[len - 6] & 0xff) << 40;
            case 5: h ^= (long) (data[len - 5] & 0xff) << 32;
            case 4: h ^= (long) (data[len - 4] & 0xff) << 24;
            case 3: h ^= (long) (data[len - 3] & 0xff) << 16;
            case 2: h ^= (long) (data[len - 2] & 0xff) << 8;
            case 1: h ^= (long) (data[len - 1] & 0xff);
                h *= m;
        }

        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;

        return h;
    }

    /**
     * 计算两个SimHash指纹的汉明距离
     * 距离越小，文档越相似
     */
    public int hammingDistance(long hash1, long hash2) {
        long xor = hash1 ^ hash2;
        return Long.bitCount(xor);
    }

    /**
     * 计算两个SimHash指纹的相似度
     * 返回0到1之间的值，1表示完全相同
     */
    public double similarity(long hash1, long hash2) {
        int distance = hammingDistance(hash1, hash2);
        return 1.0 - (double) distance / hashBits;
    }

    /**
     * 判断两个文档是否近似重复
     * 经验阈值：64位SimHash汉明距离<=3视为高度相似
     */
    public boolean isNearDuplicate(long hash1, long hash2, int threshold) {
        return hammingDistance(hash1, hash2) <= threshold;
    }

    /**
     * 在海量文档集合中查找与目标文档相似的文档
     * 使用分桶索引加速查找
     */
    public static class SimHashIndex {
        private final int bandCount; // 分桶的段数
        private final Map<String, List<DocumentEntry>> buckets;

        public SimHashIndex(int bandCount) {
            this.bandCount = bandCount;
            this.buckets = new HashMap<>();
        }

        /**
         * 将64位指纹分成bandCount段，每段作为桶的键
         */
        public void addDocument(String docId, long simHash) {
            int bitsPerBand = 64 / bandCount;
            for (int i = 0; i < bandCount; i++) {
                // 提取第i段的指纹
                long mask = (1L << bitsPerBand) - 1;
                long band = (simHash >>> (i * bitsPerBand)) & mask;
                String bucketKey = i + "_" + band;
                buckets.computeIfAbsent(bucketKey, k -> new ArrayList<>())
                       .add(new DocumentEntry(docId, simHash));
            }
        }

        /**
         * 查找与目标文档汉明距离不超过threshold的近似重复文档
         */
        public Set<String> findNearDuplicates(long targetHash, int threshold) {
            Set<String> candidates = new HashSet<>();
            int bitsPerBand = 64 / bandCount;

            for (int i = 0; i < bandCount; i++) {
                long mask = (1L << bitsPerBand) - 1;
                long band = (targetHash >>> (i * bitsPerBand)) & mask;
                String bucketKey = i + "_" + band;

                List<DocumentEntry> entries = buckets.get(bucketKey);
                if (entries != null) {
                    for (DocumentEntry entry : entries) {
                        int distance = Long.bitCount(targetHash ^ entry.simHash);
                        if (distance <= threshold) {
                            candidates.add(entry.docId);
                        }
                    }
                }
            }
            return candidates;
        }

        private static class DocumentEntry {
            String docId;
            long simHash;
            DocumentEntry(String docId, long simHash) {
                this.docId = docId;
                this.simHash = simHash;
            }
        }
    }

    /**
     * 将SimHash指纹格式化为二进制字符串
     */
    public String toBinaryString(long hash) {
        StringBuilder sb = new StringBuilder();
        for (int i = hashBits - 1; i >= 0; i--) {
            sb.append((hash & (1L << i)) != 0 ? '1' : '0');
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        SimHash simHash = new SimHash(64);

        // 测试文档
        String doc1 = "Java是一种广泛使用的面向对象编程语言，具有跨平台特性。" +
                      "它由Sun Microsystems于1995年发布，目前被广泛应用于企业级开发。";
        String doc2 = "Java是一种广泛应用的面向对象编程语言，具备跨平台特性。" +
                      "它由Sun公司于1995年发布，目前广泛应用于企业开发。";
        String doc3 = "Python是一种简洁优雅的编程语言，适合数据科学和人工智能开发。" +
                      "它拥有丰富的第三方库和活跃的社区。";

        long hash1 = simHash.compute(doc1);
        long hash2 = simHash.compute(doc2);
        long hash3 = simHash.compute(doc3);

        System.out.println("文档1 SimHash: " + simHash.toBinaryString(hash1));
        System.out.println("文档2 SimHash: " + simHash.toBinaryString(hash2));
        System.out.println("文档3 SimHash: " + simHash.toBinaryString(hash3));

        System.out.println("\n汉明距离:");
        System.out.println("  文档1 vs 文档2 (相似): " + simHash.hammingDistance(hash1, hash2));
        System.out.println("  文档1 vs 文档3 (不同): " + simHash.hammingDistance(hash1, hash3));

        System.out.println("\n相似度:");
        System.out.println("  文档1 vs 文档2: " + String.format("%.4f", simHash.similarity(hash1, hash2)));
        System.out.println("  文档1 vs 文档3: " + String.format("%.4f", simHash.similarity(hash1, hash3)));

        // 测试索引
        SimHashIndex index = new SimHashIndex(4); // 分成4段
        index.addDocument("doc1", hash1);
        index.addDocument("doc2", hash2);
        index.addDocument("doc3", hash3);

        Set<String> duplicates = index.findNearDuplicates(hash1, 5);
        System.out.println("\n与文档1近似重复的文档: " + duplicates);
    }
}

算法优化

加权SimHash

上述实现中使用词频作为权重。更精确的做法是使用TF-IDF权重，让高频但低区分度的词（如”的”、”是”）贡献更小。

多级索引

对于十亿级文档库，将64位指纹分成4段（每段16位）建立倒排索引，可将候选比较数量从十亿降至数千，再通过精确汉明距离筛选。

复杂度分析

应用场景

SimHash在以下场景有广泛应用：

• 搜索引擎去重：Google用SimHash识别内容相似的网页，避免重复结果出现在同一页
• 新闻聚类：实时检测改写稿和转载文章，进行事件聚合
• 版权检测：快速比对海量文档，识别抄袭和非法转载
• 日志去重：从海量系统日志中提取独特的错误模式
• 推荐系统去重：避免向用户推荐内容高度相似的物品

SimHash将高维文本相似度问题转化为低维位运算问题，是处理海量文本相似性检测的首选算法之一。