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 和实际文档里提供的不一样