一、背景介绍
1.1 Jaccard相似度是什么
Jaccard相似度（Jaccard Similarity），又称Jaccard系数，是衡量两个集合相似程度的指标。它定义为两个集合交集的大小与并集的大小之比。
公式：
J(A, B) = |A ∩ B| / |A ∪ B|
取值范围：[0, 1]
– J = 1：两个集合完全相同
– J = 0：两个集合完全不相交
例如：
– A = {1, 2, 3}, B = {2, 3, 4}
– A ∩ B = {2, 3}, |A ∩ B| = 2
– A ∪ B = {1, 2, 3, 4}, |A ∪ B| = 4
– J(A, B) = 2/4 = 0.5
1.2 应用场景
Jaccard相似度广泛应用于：
– 文本去重：检测网页/文档是否重复
– 推荐系统：基于用户行为的协同过滤
– 生物信息：基因序列相似度比较
– 图像检索：基于特征的图像相似度
– 抄袭检测：学术论文查重
– 近邻搜索：大规模高维数据的近似最近邻
1.3 为什么需要MinHash和LSH
直接计算Jaccard相似度的问题：
– 集合很大时，计算交集和并集的代价很高
– 需要比较的集合对很多时（如N个集合两两比较，O(N²)），计算量爆炸
解决方案：
– MinHash：用短签名（signature）近似表示集合，签名的相似度 ≈ Jaccard相似度
– LSH（局部敏感哈希）：将相似的集合哈希到同一个桶中，只比较同桶的集合，大幅减少比较次数
二、核心算法原理
2.1 MinHash（最小哈希）
核心思想：对于一个集合S和一个随机排列π，MinHash值是排列后集合中第一个元素的位置。
关键性质：
两个集合的MinHash值相等的概率 = 它们的Jaccard相似度
P(h(A) = h(B)) = J(A, B)
MinHash签名：使用k个不同的随机排列，得到k个MinHash值，组成k维签名向量。
签名的相似度（对应位置相等的比例）可以近似Jaccard相似度。
2.2 哈希函数模拟随机排列
实际中不用真的生成随机排列，而是用哈希函数模拟：
h(x) = (a × x + b) mod c
其中a、b是随机数，c是一个大素数。
对于每个哈希函数，集合的MinHash值 = min{ h(x) | x ∈ S }
2.3 LSH（局部敏感哈希）
核心思想：对于高维向量，设计哈希函数使得相似的向量有更高概率哈希到同一个桶中。
针对MinHash签名的LSH策略（带通带技术）：
– 将k维签名分成b个带（band），每个带包含r行（k = b × r）
– 每个带单独哈希，只要有一个带哈希值相同，就认为两个集合可能相似
– 调节b和r可以控制假阳性和假阴性的概率
S曲线效应：
– 当Jaccard相似度超过某个阈值时，候选对的概率急剧上升
– 阈值 ≈ (1/b)^(1/r)
三、完整Java实现
import java.util.*;
import java.util.stream.*;
/**
* Jaccard相似度完整实现
* 包含Jaccard系数计算、MinHash签名、LSH局部敏感哈希
*/
public class JaccardSimilarity {
// ==========================================
// 第一部分：基础Jaccard相似度计算
// ==========================================
/**
* 计算两个集合的Jaccard相似度
* @param set1 集合1
* @param set2 集合2
* @return Jaccard相似度 [0, 1]
*/
public static <T> double jaccardSimilarity(Set<T> set1, Set<T> set2) {
if (set1.isEmpty() && set2.isEmpty()) {
return 1.0; // 两个空集相似度为1
}
// 计算交集大小
Set<T> intersection = new HashSet<>(set1);
intersection.retainAll(set2);
int intersectionSize = intersection.size();
// 计算并集大小
Set<T> union = new HashSet<>(set1);
union.addAll(set2);
int unionSize = union.size();
return (double) intersectionSize / unionSize;
}
/**
* 优化版本：用较小的集合遍历计算交集
* 时间复杂度：O(min(|A|, |B|))
*/
public static <T> double jaccardOptimized(Set<T> set1, Set<T> set2) {
if (set1.isEmpty() && set2.isEmpty()) return 1.0;
// 确保遍历较小的集合
Set<T> small = set1.size() <= set2.size() ? set1 : set2;
Set<T> large = set1.size() > set2.size() ? set1 : set2;
int intersection = 0;
for (T item : small) {
if (large.contains(item)) {
intersection++;
}
}
int union = set1.size() + set2.size() - intersection;
return (double) intersection / union;
}
// ==========================================
// 第二部分：MinHash签名生成
// ==========================================
/**
* MinHash签名生成器
*/
static class MinHash {
private int numHashFunctions; // 哈希函数数量（签名维度）
private int[] a; // 每个哈希函数的a参数
private int[] b; // 每个哈希函数的b参数
private int prime; // 大素数（模数）
private Map<String, Integer> itemToIndex; // 元素到索引的映射
private int nextIndex;
public MinHash(int numHashFunctions) {
this.numHashFunctions = numHashFunctions;
this.prime = 2147483647; // 2^31 - 1，大素数
this.a = new int[numHashFunctions];
this.b = new int[numHashFunctions];
this.itemToIndex = new HashMap<>();
this.nextIndex = 0;
Random rand = new Random(42); // 固定种子，保证可复现
for (int i = 0; i < numHashFunctions; i++) {
a[i] = rand.nextInt(prime - 1) + 1; // a ∈ [1, prime-1]
b[i] = rand.nextInt(prime); // b ∈ [0, prime-1]
}
}
/**
* 获取元素的索引（不存在则分配新索引）
*/
private int getIndex(String item) {
if (!itemToIndex.containsKey(item)) {
itemToIndex.put(item, nextIndex++);
}
return itemToIndex.get(item);
}
/**
* 计算单个哈希函数的值
*/
private int hash(int x, int i) {
// h_i(x) = (a_i * x + b_i) mod prime
return (int) (((long) a[i] * x + b[i]) % prime);
}
/**
* 为集合生成MinHash签名
* @param items 集合元素（字符串形式）
* @return MinHash签名数组
*/
public int[] signature(Set<String> items) {
int[] sig = new int[numHashFunctions];
Arrays.fill(sig, Integer.MAX_VALUE);
for (String item : items) {
int x = getIndex(item);
for (int i = 0; i < numHashFunctions; i++) {
int h = hash(x, i);
if (h < sig[i]) {
sig[i] = h;
}
}
}
return sig;
}
/**
* 计算两个签名的相似度（近似Jaccard相似度）
*/
public double signatureSimilarity(int[] sig1, int[] sig2) {
if (sig1.length != sig2.length) {
throw new IllegalArgumentException("签名长度不同");
}
int match = 0;
for (int i = 0; i < sig1.length; i++) {
if (sig1[i] == sig2[i]) {
match++;
}
}
return (double) match / sig1.length;
}
public int getNumHashFunctions() {
return numHashFunctions;
}
}
// ==========================================
// 第三部分：LSH局部敏感哈希
// ==========================================
/**
* LSH局部敏感哈希（基于MinHash签名的带通带技术）
*/
static class LSH {
private int numBands; // 带的数量 b
private int rowsPerBand; // 每个带的行数 r
private int signatureSize; // 签名总维度 k = b * r
private List<Map<String, List<Integer>>> buckets; // 每个带的哈希桶
private List<int[]> signatures; // 存储所有签名
private int nextId;
public LSH(int numBands, int rowsPerBand) {
this.numBands = numBands;
this.rowsPerBand = rowsPerBand;
this.signatureSize = numBands * rowsPerBand;
this.buckets = new ArrayList<>();
this.signatures = new ArrayList<>();
this.nextId = 0;
// 初始化每个带的桶
for (int i = 0; i < numBands; i++) {
buckets.add(new HashMap<>());
}
}
/**
* 添加一个集合的签名到LSH索引中
* @param signature MinHash签名
* @return 集合ID
*/
public int add(int[] signature) {
if (signature.length != signatureSize) {
throw new IllegalArgumentException(
"签名长度应为 " + signatureSize + "，实际为 " + signature.length);
}
int id = nextId++;
signatures.add(signature);
// 对每个带计算哈希，放入对应桶
for (int band = 0; band < numBands; band++) {
String hashKey = getBandHash(signature, band);
buckets.get(band).computeIfAbsent(hashKey, k -> new ArrayList<>()).add(id);
}
return id;
}
/**
* 计算某个带的哈希键
*/
private String getBandHash(int[] signature, int band) {
StringBuilder sb = new StringBuilder();
int start = band * rowsPerBand;
for (int i = start; i < start + rowsPerBand; i++) {
sb.append(signature[i]).append(",");
}
return sb.toString();
}
/**
* 查询与给定签名相似的候选集合ID
* @param signature 查询签名
* @return 候选ID集合（可能相似的集合）
*/
public Set<Integer> queryCandidates(int[] signature) {
Set<Integer> candidates = new HashSet<>();
for (int band = 0; band < numBands; band++) {
String hashKey = getBandHash(signature, band);
List<Integer> bucket = buckets.get(band).get(hashKey);
if (bucket != null) {
candidates.addAll(bucket);
}
}
return candidates;
}
/**
* 获取签名
*/
public int[] getSignature(int id) {
return signatures.get(id);
}
/**
* 计算理论阈值（S曲线的拐点）
*/
public double getThreshold() {
return Math.pow(1.0 / numBands, 1.0 / rowsPerBand);
}
}
// ==========================================
// 第四部分：文本处理工具
// ==========================================
/**
* 将文本转换为Shingle（n-gram）集合
* 用于文本相似度计算
* @param text 文本
* @param k shingle大小（字符数）
* @return shingle集合
*/
public static Set<String> textToShingles(String text, int k) {
Set<String> shingles = new HashSet<>();
text = text.toLowerCase().replaceAll("\\s+", " ");
if (text.length() < k) {
shingles.add(text);
return shingles;
}
for (int i = 0; i <= text.length() - k; i++) {
shingles.add(text.substring(i, i + k));
}
return shingles;
}
/**
* 文本去重：找出相似度超过阈值的文档对
* 使用LSH加速
*/
public static List<int[]> findSimilarDocuments(List<String> documents,
double threshold,
int numHashFunctions,
int numBands,
int shingleSize) {
// 参数验证
if (numHashFunctions != numBands * (numHashFunctions / numBands)) {
throw new IllegalArgumentException("numHashFunctions 必须能被 numBands 整除");
}
int rowsPerBand = numHashFunctions / numBands;
// 1. 文本转shingle集合
List<Set<String>> docShingles = new ArrayList<>();
for (String doc : documents) {
docShingles.add(textToShingles(doc, shingleSize));
}
// 2. 生成MinHash签名
MinHash minHash = new MinHash(numHashFunctions);
List<int[]> signatures = new ArrayList<>();
for (Set<String> shingles : docShingles) {
signatures.add(minHash.signature(shingles));
}
// 3. 构建LSH索引
LSH lsh = new LSH(numBands, rowsPerBand);
for (int[] sig : signatures) {
lsh.add(sig);
}
// 4. 查询候选对并验证
List<int[]> similarPairs = new ArrayList<>();
Set<String> checked = new HashSet<>(); // 避免重复检查
for (int i = 0; i < documents.size(); i++) {
Set<Integer> candidates = lsh.queryCandidates(signatures.get(i));
for (int j : candidates) {
if (j <= i) continue; // 只检查j > i，避免重复
String pairKey = i + "-" + j;
if (checked.contains(pairKey)) continue;
checked.add(pairKey);
// 用签名相似度快速估计
double approxSim = minHash.signatureSimilarity(signatures.get(i), signatures.get(j));
if (approxSim >= threshold * 0.8) { // 留一些余量
// 精确计算Jaccard相似度
double exactSim = jaccardOptimized(docShingles.get(i), docShingles.get(j));
if (exactSim >= threshold) {
similarPairs.add(new int[]{i, j, (int) (exactSim * 1000)});
}
}
}
}
return similarPairs;
}
// ==========================================
// 主方法：演示
// ==========================================
public static void main(String[] args) {
System.out.println("╔══════════════════════════════════════╗");
System.out.println("║ Jaccard相似度与MinHash/LSH演示 ║");
System.out.println("╚══════════════════════════════════════╝\n");
// --- 第一部分：基础Jaccard相似度 ---
System.out.println("【一、基础Jaccard相似度计算】");
System.out.println("----------------------------");
Set<String> setA = new HashSet<>(Arrays.asList("苹果", "香蕉", "橙子", "葡萄"));
Set<String> setB = new HashSet<>(Arrays.asList("香蕉", "葡萄", "西瓜", "芒果"));
Set<String> setC = new HashSet<>(Arrays.asList("苹果", "香蕉", "橙子", "葡萄"));
System.out.println("集合A: " + setA);
System.out.println("集合B: " + setB);
System.out.println("集合C: " + setC);
System.out.println();
System.out.println("J(A, B) = " + String.format("%.4f", jaccardSimilarity(setA, setB)));
System.out.println("J(A, C) = " + String.format("%.4f", jaccardSimilarity(setA, setC)));
System.out.println("J(B, C) = " + String.format("%.4f", jaccardSimilarity(setB, setC)));
System.out.println();
// --- 第二部分：MinHash签名演示 ---
System.out.println("【二、MinHash签名近似计算】");
System.out.println("----------------------------");
int numHashFunctions = 100;
MinHash minHash = new MinHash(numHashFunctions);
int[] sigA = minHash.signature(setA);
int[] sigB = minHash.signature(setB);
int[] sigC = minHash.signature(setC);
double approxAB = minHash.signatureSimilarity(sigA, sigB);
double approxAC = minHash.signatureSimilarity(sigA, sigC);
System.out.println("哈希函数数量: " + numHashFunctions);
System.out.println("签名维度: " + sigA.length);
System.out.println();
System.out.println("J(A, B) 精确值: " + String.format("%.4f", jaccardSimilarity(setA, setB)));
System.out.println("J(A, B) 近似值: " + String.format("%.4f", approxAB));
System.out.println("误差: " + String.format("%.4f", Math.abs(approxAB - jaccardSimilarity(setA, setB))));
System.out.println();
System.out.println("J(A, C) 精确值: " + String.format("%.4f", jaccardSimilarity(setA, setC)));
System.out.println("J(A, C) 近似值: " + String.format("%.4f", approxAC));
System.out.println();
// --- 第三部分：文本相似度与去重 ---
System.out.println("【三、文本相似度计算（Shingle + Jaccard）】");
System.out.println("----------------------------");
String doc1 = "Java是一种广泛使用的编程语言，具有跨平台、面向对象、安全性高等特点。" +
"Java广泛应用于企业级开发、移动应用开发和大数据处理领域。";
String doc2 = "Java是一门面向对象的编程语言，拥有跨平台的特性。" +
"它在企业级开发、Android开发和大数据处理中应用广泛。";
String doc3 = "Python是一种解释型编程语言，以简洁的语法著称。" +
"Python在数据分析、机器学习和Web开发领域非常流行。";
String doc4 = "机器学习是人工智能的核心技术，通过数据训练模型来实现预测和分类。" +
"常见的机器学习算法包括线性回归、决策树和神经网络。";
List<String> documents = Arrays.asList(doc1, doc2, doc3, doc4);
int shingleSize = 3;
System.out.println("Shingle大小: " + shingleSize + " 字符");
System.out.println();
for (int i = 0; i < documents.size(); i++) {
Set<String> shingles = textToShingles(documents.get(i), shingleSize);
System.out.println("文档" + (i + 1) + " shingle数量: " + shingles.size());
}
System.out.println();
// 计算两两相似度
System.out.println("文档两两Jaccard相似度:");
for (int i = 0; i < documents.size(); i++) {
for (int j = i + 1; j < documents.size(); j++) {
Set<String> s1 = textToShingles(documents.get(i), shingleSize);
Set<String> s2 = textToShingles(documents.get(j), shingleSize);
double sim = jaccardOptimized(s1, s2);
System.out.printf(" 文档%d vs 文档%d: %.4f%n", i + 1, j + 1, sim);
}
}
System.out.println();
// --- 第四部分：LSH文本去重演示 ---
System.out.println("【四、LSH加速文本去重】");
System.out.println("----------------------------");
double threshold = 0.3;
int numBands = 20;
int hashFuncs = numBands * 5; // 每个带5行
System.out.println("相似度阈值: " + threshold);
System.out.println("哈希函数数: " + hashFuncs);
System.out.println("带数量: " + numBands);
System.out.println("每带行数: " + (hashFuncs / numBands));
LSH lsh = new LSH(numBands, hashFuncs / numBands);
System.out.println("理论阈值(S曲线拐点): " + String.format("%.4f", lsh.getThreshold()));
System.out.println();
List<int[]> similarPairs = findSimilarDocuments(
documents, threshold, hashFuncs, numBands, shingleSize);
System.out.println("发现相似文档对:");
if (similarPairs.isEmpty()) {
System.out.println(" 无");
} else {
for (int[] pair : similarPairs) {
System.out.printf(" 文档%d ↔ 文档%d (相似度: %.3f)%n",
pair[0] + 1, pair[1] + 1, pair[2] / 1000.0);
}
}
System.out.println();
// --- 第五部分：大规模性能对比 ---
System.out.println("【五、大规模数据性能对比（模拟）】");
System.out.println("----------------------------");
// 生成100个随机文档
Random rand = new Random(123);
List<String> largeDocs = new ArrayList<>();
String[] words = {"java", "python", "算法", "数据", "机器学习", "深度学习",
"编程", "开发", "系统", "网络", "数据库", "安全"};
for (int i = 0; i < 100; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < 50; j++) {
sb.append(words[rand.nextInt(words.length)]).append(" ");
}
largeDocs.add(sb.toString());
}
System.out.println("文档数量: " + largeDocs.size());
System.out.println("总比较对数: " + (largeDocs.size() * (largeDocs.size() - 1) / 2));
// 暴力法计时
long start = System.currentTimeMillis();
int bruteCount = 0;
for (int i = 0; i < largeDocs.size(); i++) {
for (int j = i + 1; j < largeDocs.size(); j++) {
Set<String> s1 = textToShingles(largeDocs.get(i), 3);
Set<String> s2 = textToShingles(largeDocs.get(j), 3);
jaccardOptimized(s1, s2);
bruteCount++;
}
}
long bruteTime = System.currentTimeMillis() - start;
// LSH法计时
start = System.currentTimeMillis();
List<int[]> lshResult = findSimilarDocuments(largeDocs, 0.4, 100, 20, 3);
long lshTime = System.currentTimeMillis() - start;
System.out.println("暴力法比较次数: " + bruteCount + "，耗时: " + bruteTime + "ms");
System.out.println("LSH候选对数: " + lshResult.size() + "，耗时: " + lshTime + "ms");
if (bruteTime > 0) {
System.out.println("加速比: " + String.format("%.1f", (double) bruteTime / lshTime) + "x");
}
}
}
四、复杂度分析
4.1 基础Jaccard计算
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 集合并交集法 | O( | A | + |
| 优化遍历法 | O(min( | A | , |
4.2 MinHash签名
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 生成签名 | O(k × n) | O(k) |
| 签名相似度 | O(k) | O(1) |
其中k是哈希函数数量，n是集合大小。
精度分析：
– k越大，近似精度越高
– 误差约为 O(1/√k)
– k=100时，典型误差约±0.1
– k=400时，典型误差约±0.05
4.3 LSH局部敏感哈希
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 构建索引 | O(N × k) | N个集合，每个k维签名 |
| 查询候选 | O(b × t) | b个带，t为平均桶大小 |
| 总查询时间 | O(N × t) | 远小于 O(N²) |
效果：
– 当数据量很大时，LSH可以将比较次数从O(N²)降低到接近O(N)
– 代价是存在一定的假阳性和假阴性
4.4 假阳性/假阴性权衡
- 增加带数b：更多机会哈希到同桶 → 假阴性↓，假阳性↑
- 增加行数r：每个带更严格 → 假阳性↓，假阴性↑
- 总维度k = b × r：k越大，S曲线越陡峭，区分度越好
五、应用拓展
5.1 实际应用场景
- 网页去重：搜索引擎爬取的网页中大量重复，用MinHash+LSH快速去重
- Google的SimHash算法（类似思想）
-
百度的网页去重系统
-
推荐系统：
- 基于物品的协同过滤：找出相似物品
-
用户行为相似度：找出相似用户
-
图像检索：
- 将图像特征转为集合表示
-
用LSH快速检索相似图像
-
生物信息：
- DNA序列相似度比较
- 蛋白质结构比对
5.2 相关算法对比
| 算法 | 类型 | 精度 | 速度 | 适用场景 |
|---|---|---|---|---|
| 精确Jaccard | 精确 | 100% | O(n) | 小数据、需要精确值 |
| MinHash | 近似 | 可调 | O(kn) | 中等数据、可接受近似 |
| MinHash+LSH | 近似 | 可调 | 接近O(N) | 大规模数据、快速筛选 |
| SimHash | 近似 | 中等 | 快 | 网页去重（Google） |
5.3 进阶方向
- 加权Jaccard：不同元素有不同权重
-
例如：TF-IDF加权的Jaccard相似度
-
多轮LSH：多组不同的b/r参数，提高召回率
-
动态集合：支持集合元素增删的MinHash
-
分布式LSH：基于MapReduce的大规模LSH实现
-
深度学习结合：用深度神经网络学习更好的哈希函数（Deep Hashing）
