每日算法 — 使用java实现局部敏感哈希：MinHash签名与近似最近邻搜索

在海量高维数据中寻找相似项是传统哈希方法无法高效解决的难题。局部敏感哈希（Locality Sensitive Hashing, LSH）通过将相似数据映射到相同桶中的概率远高于不相似数据的特性，将精确相似度计算转化为高效的桶内搜索。本文用Java实现基于MinHash的LSH系统，用于快速估算Jaccard相似度并构建近似最近邻搜索索引，最后通过一个”游戏内容去重与推荐”案例展示其实际应用。

一、核心原理

1.1 Jaccard相似度

对于两个集合A和B：

$$J(A,B) = \frac{|A \cap B|}{|A \cup B|}$$

当数据量大时，直接计算交集和并集代价高昂。

1.2 MinHash思想

MinHash通过多个哈希函数将集合压缩为签名向量。关键性质：两个集合的MinHash签名相等的概率等于它们的Jaccard相似度。

1.3 LSH桶划分

将k维MinHash签名分为b个band，每个band包含r行（k = b × r）。两个集合在至少一个band上完全匹配的概率为：

$$P(\text{候选}) = 1 – (1 – J^r)^b$$

通过调整b和r，可以控制候选对的召回率与精确率。

二、MinHash签名生成

package com.algorithm.lsh;

import java.util.*;

/**
 * MinHash签名生成器
 * 使用多个哈希函数将集合映射为低维签名向量
 */
public class MinHash {
    private final int numHashFunctions;  // 签名维度k
    private final long[] seeds;          // 每个哈希函数的随机种子
    private final long prime = (1L << 61) - 1; // 大素数，用于哈希计算

    public MinHash(int numHashFunctions) {
        this.numHashFunctions = numHashFunctions;
        this.seeds = new long[numHashFunctions];
        Random random = new Random(42); // 固定种子保证可复现
        for (int i = 0; i < numHashFunctions; i++) {
            seeds[i] = random.nextLong();
        }
    }

    /**
     * 计算单个元素的哈希值（基于MurmurHash思想）
     */
    private long hash(long element, long seed) {
        long hash = seed;
        hash ^= element;
        hash *= 0x5bd1e9955bd1e995L;
        hash ^= hash >>> 47;
        hash *= 0x5bd1e9955bd1e995L;
        hash &= prime;
        return hash;
    }

    /**
     * 为集合生成MinHash签名
     * 对每个哈希函数，取集合中所有元素哈希值的最小值
     */
    public int[] computeSignature(Set<Long> set) {
        int[] signature = new int[numHashFunctions];
        Arrays.fill(signature, Integer.MAX_VALUE);

        for (long element : set) {
            for (int i = 0; i < numHashFunctions; i++) {
                int h = (int) (hash(element, seeds[i]) % Integer.MAX_VALUE);
                signature[i] = Math.min(signature[i], h);
            }
        }

        return signature;
    }

    /**
     * 估算两个签名的Jaccard相似度
     */
    public double estimateJaccardSimilarity(int[] sig1, int[] sig2) {
        if (sig1.length != sig2.length) {
            throw new IllegalArgumentException("签名维度不一致");
        }

        int matches = 0;
        for (int i = 0; i < sig1.length; i++) {
            if (sig1[i] == sig2[i]) {
                matches++;
            }
        }

        return (double) matches / sig1.length;
    }

    public int getNumHashFunctions() {
        return numHashFunctions;
    }
}

三、LSH桶索引构建

package com.algorithm.lsh;

import java.util.*;

/**
 * LSH索引：基于MinHash签名的局部敏感哈希桶索引
 * 将高维签名划分为多个band，相似项在至少一个band中碰撞的概率很高
 */
public class LSHIndex {
    private final int numBands;        // band数量b
    private final int rowsPerBand;     // 每个band的行数r
    private final int numHashFunctions;// 总哈希函数数k = b * r
    private final MinHash minHash;

    // 每个band对应一个哈希表：bandIndex -> (bandSignature -> itemIds)
    private final List<Map<BandSignature, Set<String>>> bands;

    // 存储所有项目的原始签名
    private final Map<String, int[]> signatures;

    public LSHIndex(int numBands, int rowsPerBand) {
        this.numBands = numBands;
        this.rowsPerBand = rowsPerBand;
        this.numHashFunctions = numBands * rowsPerBand;
        this.minHash = new MinHash(numHashFunctions);
        this.signatures = new HashMap<>();

        // 初始化每个band的哈希表
        this.bands = new ArrayList<>();
        for (int i = 0; i < numBands; i++) {
            bands.add(new HashMap<>());
        }
    }

    /**
     * Band签名的包装类，用于作为HashMap的key
     */
    static class BandSignature {
        final int[] values;

        BandSignature(int[] values) {
            this.values = values.clone();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof BandSignature)) return false;
            BandSignature that = (BandSignature) o;
            return Arrays.equals(values, that.values);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(values);
        }
    }

    /**
     * 添加项目到LSH索引
     */
    public void addItem(String itemId, Set<Long> shingles) {
        int[] signature = minHash.computeSignature(shingles);
        signatures.put(itemId, signature);

        // 将签名分成numBands个band，每个band有rowsPerBand行
        for (int bandIdx = 0; bandIdx < numBands; bandIdx++) {
            int[] bandValues = new int[rowsPerBand];
            for (int row = 0; row < rowsPerBand; row++) {
                bandValues[row] = signature[bandIdx * rowsPerBand + row];
            }

            BandSignature bandSig = new BandSignature(bandValues);
            bands.get(bandIdx)
                 .computeIfAbsent(bandSig, k -> new HashSet<>())
                 .add(itemId);
        }
    }

    /**
     * 查询与给定项目相似的候选项目
     */
    public Set<String> queryCandidates(String itemId) {
        int[] signature = signatures.get(itemId);
        if (signature == null) return Collections.emptySet();

        Set<String> candidates = new HashSet<>();

        for (int bandIdx = 0; bandIdx < numBands; bandIdx++) {
            int[] bandValues = new int[rowsPerBand];
            for (int row = 0; row < rowsPerBand; row++) {
                bandValues[row] = signature[bandIdx * rowsPerBand + row];
            }

            BandSignature bandSig = new BandSignature(bandValues);
            Set<String> bucket = bands.get(bandIdx).get(bandSig);
            if (bucket != null) {
                candidates.addAll(bucket);
            }
        }

        candidates.remove(itemId); // 移除自身
        return candidates;
    }

    /**
     * 查询与给定项目最相似的topK个项目（带精确Jaccard计算）
     */
    public List<SimilarityResult> queryTopK(String itemId, int topK) {
        Set<String> candidates = queryCandidates(itemId);
        int[] sig1 = signatures.get(itemId);

        PriorityQueue<SimilarityResult> topResults = new PriorityQueue<>(
            Comparator.comparingDouble(r -> r.similarity)
        );

        for (String candidateId : candidates) {
            int[] sig2 = signatures.get(candidateId);
            double sim = minHash.estimateJaccardSimilarity(sig1, sig2);

            topResults.offer(new SimilarityResult(candidateId, sim));
            if (topResults.size() > topK) {
                topResults.poll(); // 移除相似度最低的
            }
        }

        List<SimilarityResult> result = new ArrayList<>(topResults);
        result.sort((a, b) -> Double.compare(b.similarity, a.similarity));
        return result;
    }

    /**
     * 查找所有相似度超过threshold的项目对（用于去重）
     */
    public List<SimilarityResult> findDuplicates(double threshold) {
        List<SimilarityResult> duplicates = new ArrayList<>();
        Set<String> processed = new HashSet<>();

        for (String itemId : signatures.keySet()) {
            processed.add(itemId);
            int[] sig1 = signatures.get(itemId);
            Set<String> candidates = queryCandidates(itemId);

            for (String candidateId : candidates) {
                if (processed.contains(candidateId)) continue;

                int[] sig2 = signatures.get(candidateId);
                double sim = minHash.estimateJaccardSimilarity(sig1, sig2);

                if (sim >= threshold) {
                    duplicates.add(new SimilarityResult(itemId + " <-> " + candidateId, sim));
                }
            }
        }

        duplicates.sort((a, b) -> Double.compare(b.similarity, a.similarity));
        return duplicates;
    }

    static class SimilarityResult {
        String id;
        double similarity;

        SimilarityResult(String id, double similarity) {
            this.id = id;
            this.similarity = similarity;
        }

        @Override
        public String toString() {
            return String.format("%s: %.3f", id, similarity);
        }
    }
}

四、Shingling文本处理

package com.algorithm.lsh;

import java.util.*;

/**
 * Shingling工具：将文本转换为k-gram集合
 * 这是MinHash处理文本/序列数据的前置步骤
 */
public class Shingling {

    /**
     * 生成文本的k-gram集合
     * @param text 输入文本
     * @param k gram大小
     * @return 哈希后的shingle集合
     */
    public static Set<Long> textToShingles(String text, int k) {
        Set<Long> shingles = new HashSet<>();

        // 预处理：转小写、移除多余空格
        String normalized = text.toLowerCase().replaceAll("\\s+", " ").trim();

        if (normalized.length() < k) {
            shingles.add((long) normalized.hashCode());
            return shingles;
        }

        // 字符级k-gram
        for (int i = 0; i <= normalized.length() - k; i++) {
            String shingle = normalized.substring(i, i + k);
            shingles.add(hashString(shingle));
        }

        return shingles;
    }

    /**
     * 生成词级k-gram集合
     */
    public static Set<Long> wordsToShingles(String text, int k) {
        Set<Long> shingles = new HashSet<>();
        String[] words = text.toLowerCase().split("\\s+");

        if (words.length < k) {
            shingles.add((long) text.hashCode());
            return shingles;
        }

        for (int i = 0; i <= words.length - k; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < k; j++) {
                if (j > 0) sb.append(" ");
                sb.append(words[i + j]);
            }
            shingles.add(hashString(sb.toString()));
        }

        return shingles;
    }

    private static long hashString(String s) {
        long hash = 5381;
        for (char c : s.toCharArray()) {
            hash = ((hash << 5) + hash) + c; // hash * 33 + c
        }
        return hash;
    }
}

五、游戏内容去重与推荐系统

package com.algorithm.lsh;

import java.util.*;

/**
 * 游戏内容去重与推荐系统
 * 应用场景：检测重复玩家昵称、相似公会名、推荐相似装备/技能描述
 */
public class GameContentLSH {

    private final LSHIndex lshIndex;
    private final int shingleSize;

    public GameContentLSH(int numBands, int rowsPerBand, int shingleSize) {
        this.lshIndex = new LSHIndex(numBands, rowsPerBand);
        this.shingleSize = shingleSize;
    }

    /**
     * 添加游戏内容项
     */
    public void addContent(String contentId, String text) {
        Set<Long> shingles = Shingling.textToShingles(text, shingleSize);
        lshIndex.addItem(contentId, shingles);
    }

    /**
     * 查找与指定内容相似的其他内容
     */
    public List<LSHIndex.SimilarityResult> findSimilar(String contentId, int topK) {
        return lshIndex.queryTopK(contentId, topK);
    }

    /**
     * 检测所有重复/相似内容
     */
    public List<LSHIndex.SimilarityResult> detectDuplicates(double threshold) {
        return lshIndex.findDuplicates(threshold);
    }

    public static void main(String[] args) {
        GameContentLSH system = new GameContentLSH(20, 5, 3);

        System.out.println("=== 游戏内容LSH去重与推荐系统 ===\n");

        // 模拟玩家提交的公会名/昵称
        String[][] contents = {
            {"player_001", "暗影猎手"},
            {"player_002", "暗影 猎手"},
            {"player_003", "火焰法师"},
            {"player_004", "火焰 法师"},
            {"player_005", "暗影刺客"},
            {"player_006", "暗影之刃"},
            {"player_007", "冰霜女巫"},
            {"player_008", "冰霜 女巫"},
            {"player_009", "雷电法王"},
            {"player_010", "雷电 法王"},
            {"player_011", "暗影猎手之王"},
            {"player_012", "圣光骑士"},
        };

        for (String[] content : contents) {
            system.addContent(content[0], content[1]);
        }

        // 检测重复内容
        System.out.println("相似度 > 0.3 的内容对（潜在重复/抄袭）:");
        List<LSHIndex.SimilarityResult> duplicates = system.detectDuplicates(0.3);
        for (LSHIndex.SimilarityResult dup : duplicates) {
            System.out.println("  " + dup);
        }

        // 推荐相似玩家
        System.out.println("\n与 'player_001'（暗影猎手）最相似的3个玩家:");
        List<LSHIndex.SimilarityResult> similar = system.findSimilar("player_001", 3);
        for (LSHIndex.SimilarityResult s : similar) {
            System.out.println("  " + s);
        }
    }
}

六、复杂度分析

其中k为签名维度，b为band数，s为Jaccard相似度阈值，d为原始维度。

七、参数调优指南

八、扩展应用

局部敏感哈希的思想可扩展到多种距离度量：
– SimHash：余弦相似度，用于海量文本去重
– p-stable LSH：欧几里得距离，用于图像/向量搜索
– Multi-probe LSH：减少哈希表数量，节省内存
– ** learned LSH**：结合机器学习自适应哈希函数

在游戏开发中，LSH可用于：玩家行为模式聚类、地图资源相似性检测、反作弊中的脚本相似度分析、社交推荐中的兴趣匹配等场景。