SimHash算法

SimHash 算法

参考资料：

• https://blog.csdn.net/qq_36488175/article/details/109788291
• https://zhuanlan.zhihu.com/p/81026564
• https://blog.csdn.net/madujin/article/details/53152619
• https://en.wikipedia.org/wiki/MinHash?useskin=vector
• 【实践】 https://github.com/ekzhu/datasketch
  • https://ekzhu.com/datasketch/lsh.html 【文档】
• 
  想象一个图书馆里的去重问题

假设你是一个图书管理员，有一大堆书，这些书有点麻烦：

• 有些书内容完全一样，但封面颜色不同。
• 有些书内容几乎一样，只是多了一点点修改，比如拼写改正或者增加了一两句话。
  你的任务是 快速找到内容相似的书并标记出来，而且你不能看完整本书，只能用一种快速的“指纹”来表示每本书的内容。SimHash 就是书的“内容指纹”。

每本书内容都会被转换成一个独特的指纹（一个由 0 和 1 组成的二进制数）。SimHash 的神奇之处在于：

• 如果两本书内容很相似，那么它们的指纹也会很接近（比如只有几位不同）。
• 如果两本书内容差异很大，它们的指纹会完全不一样。
  那么，SimHash 是怎么生成这些“指纹”的呢？接下来就一步步解释。

步骤 1：把书变成“关键词”

首先，书的内容需要拆分成很多“关键词”，比如一段话：“LLVM 是一个非常流行的编译器框架，用于优化和生成高效的代码。”你可以提取出关键词，比如：

• LLVM
• 编译器框架
• 优化
• 高效代码
  然后，把这些关键词当作“特征”。你可以把一整本书看成由一堆特征组成的集合。

步骤 2：给每个特征一个“随机标签”

假设我们有四个关键词：LLVM，编译器框架，优化，高效代码。为了方便处理，每个关键词都需要变成一个固定长度的“随机标签”（类似指纹）。比如，我们用一个简单的哈希函数把这些特征变成二进制的随机标签：

• LLVM → 1010
• 编译器框架 → 1100
• 优化 → 0011
• 高效代码 → 1011

步骤 3：考虑每个特征的重要性

不同的特征对这本书的内容描述重要性不同，比如：LLVM 这个词很重要，因为这是这本书的核心主题，所以给它 权重 5。编译器框架 也很重要，给它 权重 3。优化 和 高效代码 稍微次要，分别给 权重 2。

步骤 4：叠加权重，形成“特征向量”

现在，把这些二进制随机标签变成一个“加权向量”。看起来很复杂？没关系，假设我们逐位处理：
每个标签是 4 位二进制数，比如 LLVM 是 1010。我们逐位叠加：

• 第 1 位是 1，加上权重 +5。
• 第 2 位是 0，减去权重 -5。
• 第 3 位是 1，加上权重 +5。
• 第 4 位是 0，减去权重 -5。
  其他特征也一样，比如：编译器框架 → 1100（加权 +3 或 -3）；优化 → 0011（加权 +2 或 -2）；高效代码 → 1011（加权 +2 或 -2）

叠加所有特征后，我们得到一个向量：[+10, +0, +8, -6]。这就是这本书的“内容加权向量”。

步骤 5：把向量变成二进制指纹

最后一步，把向量里的每个数转化成 0 或 1：如果某一维度 >= 0，则是 1。如果某一维度 < 0，则是 0。
比如向量 [+10, +0, +8, -6] 会变成：1010。这就是这本书的 SimHash 指纹！

找相似的书

现在，每本书都有了一个 4 位二进制的 SimHash 指纹，比如：

• 书 A 的指纹是：1010
• 书 B 的指纹是：1011
• 书 C 的指纹是：0010

如果你想知道书 A 和书 B 是否相似，只需要比较它们的指纹，计算两者的“汉明距离”（也就是有几位不同）：

• 书 A 和书 B：1010 vs 1011，只有 1 位不同（非常相似！）。
• 书 A 和书 C：1010 vs 0010，有 2 位不同（差别稍大）。
• 一般来说，如果汉明距离小于一个阈值（比如 3），就认为它们是相似的。

LLVM IR 中的例子
在 LLVM IR 中，可以把一段代码看成一本“书”。我们用类似的步骤来生成 SimHash：

define i32 @add(i32 %a, i32 %b) {
entry:
  %1 = add i32 %a, %b
  ret i32 %1
}

特征提取：

• add：表示加法指令。
• ret：表示返回指令。
• %a, %b：表示操作数。
  特征权重：
• add 和 ret 很重要，权重高。
• %a, %b 作为操作数，权重低。

哈希生成和加权叠加：对 add、ret、%a, %b 等特征生成随机标签，并按权重叠加。得到加权向量 [+3, +1, -1, +4]。

最终 SimHash 指纹：转化为二进制指纹：1101。

SimHash使用方法

• pip3 install datasketch simhash
  测试代码：

from simhash import Simhash  
  
# 提取 LLVM IR 代码中的特征（假设我们简单提取指令和操作数作为特征）  
def extract_features(llvm_ir):  
    # 对每行 LLVM IR 代码提取指令和操作数作为特征  
    features = []  
    for line in llvm_ir.splitlines():  
        if line.strip() and not line.startswith(";"):  # 忽略空行和注释  
            parts = line.strip().split()  
            features.append(parts[0])  # 指令类型  
            features.extend(parts[1:])  # 操作数  
    return features  
  
# 第一段 LLVM IR 代码  
llvm_ir_1 = """  
define i32 @add(i32 %a, i32 %b) {  
entry:  
  %1 = add i32 %a, %b  ret i32 %1}  
"""  
  
# 第二段 LLVM IR 代码  
llvm_ir_2 = """  
define i32 @add(i32 %x, i32 %y) {  
entry:  
  %1 = add i32 %x, %y  %2 = mul i32 %1, 2  ret i32 %2}  
"""  
  
# 提取特征  
features_1 = extract_features(llvm_ir_1)  
features_2 = extract_features(llvm_ir_2)  
  
# 生成 SimHash 指纹  
simhash_1 = Simhash(features_1)  
simhash_2 = Simhash(features_2)  
  
# 打印指纹值  
print("SimHash 1:", simhash_1.value)  
print("SimHash 2:", simhash_2.value)  
  
# 计算汉明距离（相似性）  
hamming_distance = simhash_1.distance(simhash_2)  
print("汉明距离:", hamming_distance)  
  
# 根据距离判断相似性  
if hamming_distance <= 3:  # 阈值可以根据需求调整  
    print("两段代码相似")  
else:  
    print("两段代码不相似")

得到：

SimHash 1: 6127369203268732162
SimHash 2: 1517954785662206988
汉明距离: 14
两段代码不相似

DataSketch 功能介绍

MinHash 和 SimHash 的基本区别

特性	MinHash	SimHash
适用数据类型	稀疏集合（Set），如关键词、指令、基本块	加权向量（Vector），如频率或权重分布的特征
相似性度量	Jaccard 相似度（两个集合的交集与并集的比值）	汉明距离（两个指纹二进制值的不同位数量）
容忍局部改动	对少量特征的改动非常敏感	对少量局部改动有一定的容忍能力（取决于权重和特征数量）
计算复杂度	适合处理稀疏特征的大规模比较，内存占用较低	适合处理稠密或加权特征，尤其是短文本或短代码
适用场景	文档去重、关键词匹配、集合相似度计算	文本、短代码的语义相似性计算，特征加权时表现更好

上述展示了使用 SimHash 处理 LLVM IR 的相似性，但是事实是 MinHash 更好。MinHash 非常适合处理 稀疏特征集合，因此在以下场景中适用于 LLVM IR：

（1）将 LLVM IR 表示为特征集合

我们可以将 LLVM IR 的某些组成部分提取为稀疏集合，例如：

• 指令集合：如 add, mul, store, call 等，忽略变量名和具体参数。
• 基本块集合：每个基本块可以看作一个特征。
• 操作符集合：如 i32, float, %var 等。
• 函数签名集合：函数名和参数类型可以作为集合特征。

（2）计算特征集合的 Jaccard 相似度

MinHash 是通过压缩特征集合来高效计算 Jaccard 相似度的。适用场景包括：

• 去重：例如，判断两个 LLVM IR 代码是否包含相同的指令集合。
• 代码片段聚类：将相似度高的代码片段归为一类。

（3）对局部变化的敏感性

MinHash 对局部变化（如添加或删除某些指令）较为敏感。如果一段代码新增了一些指令，其特征集合的变化可能导致相似性大幅降低。因此，MinHash 更适合处理需要精确匹配的场景。

SimHash 在 LLVM IR 中的适配性

SimHash 更适合处理 加权特征分布，因此在以下场景中适用于 LLVM IR：

（1）将 LLVM IR 表示为加权特征分布

我们可以将 LLVM IR 提取为加权向量，例如：

• 指令频率分布：统计每种指令的出现次数（如 add 出现 3 次，mul 出现 2 次）。
• 指令重要性权重：对某些关键指令（如 ret 或 call）赋予更高权重。
• 操作数权重：统计不同类型操作数（如 i32，常量）的使用权重。

（2）计算指纹并比较相似性

SimHash 通过将加权向量映射为二进制指纹，比较指纹的汉明距离来计算相似性。适用场景包括：

• 代码变体检测：检测经过轻微修改但功能类似的 LLVM IR 代码。例如，变量名的更改或操作数的微调不会显著影响 SimHash。
• 代码聚类：根据功能相似性将代码片段聚类。

（3）对局部变化的容忍性

SimHash 对局部变化（如变量名替换、新增或删除几条指令）具有较强的鲁棒性，因为这些变化通常只会引起少量特征的权重变化，不会显著影响最终的指纹。

MinHash 与 SimHash 的选择建议

根据 LLVM IR 的特性和应用场景，我们可以选择适合的算法：

（1）选择 MinHash 的场景

• 指令集合比较：当目标是判断代码中使用的指令类型是否相似时（例如完全相同的指令集合）。
• 去重任务：需要精确判断代码片段是否包含相同的特征。
• 稀疏特征场景：代码被表示为稀疏集合（如指令集合或基本块集合）。

（2）选择 SimHash 的场景

• 代码变体检测：当目标是检测经过轻微修改但逻辑功能类似的代码时（如变量名变化、指令顺序调整）。
• 指令频率分布：当特征可以表示为频率或权重分布时（如统计指令的使用频率）。
• 鲁棒性需求：需要对局部变化（新增或删除几条指令）具有一定的容忍性。

• MinHash 更适合处理稀疏特征集合，适用于需要精确匹配的场景，比如代码片段去重、指令集合比较。

• SimHash 更适合处理加权特征分布，适用于需要容忍局部变化的场景，比如代码变体检测或功能聚类。
  两者的选择应根据特征的表示方式和对局部变化的容忍需求来决定。如果场景允许，甚至可以结合两种方法：先用 MinHash 进行初筛，再用 SimHash 进行更精细的相似性判断。

GPT 推荐的方法

对于大规模的LLVM IR去重任务，MinHash结合LSH（Locality Sensitive Hashing）索引是一个合适的选择。

[!a]
API 和实际文档里提供的不一样

合适的选择。

[!a]
API 和实际文档里提供的不一样