bloomtool/README.md

# BloomTool - 布隆过滤器工具

BloomTool 是一个基于 Go 语言开发的布隆过滤器命令行工具，用于高效地创建、测试和管理布隆过滤器。

## 功能特性

- **高性能**: 使用 RoaringBitmap 库实现高效的位图存储
- **低误判率**: 支持自定义误判率，默认千万分之一
- **大容量**: 支持最多 100 亿个元素
- **简单易用**: 命令行界面，操作简单
- **位图运算**: 支持AND/OR位图运算，实现集合操作

## 安装

```bash
go install git.algo.com.cn/public/bloomtool@latest
```

## 命令说明

### 1. makebloom - 创建布隆过滤器

从文本文件创建布隆过滤器位图文件。

**语法:**
```bash
bloomtool makebloom -d <设备ID文件> -b <位图输出文件> [-e <最大元素数>] [-r <误判率>]
```

**参数:**
- `-d`: 设备ID文本文件路径（每行一个ID）
- `-o`: 布隆过滤器位图输出文件路径
- `-e`: 最大元素数量（0表示自动计算，最大100亿）
- `-r`: 误判率（0.01-0.000000001，默认0.00000001）

**示例:**
```bash
bloomtool makebloom -d devices.txt -b bloom.blm
bloomtool makebloom -d devices.txt -b bloom.blm -e 1000000 -r 0.001
```

### 2. hittest - 命中测试

测试文本文件中的行是否在布隆过滤器中存在。

**语法:**
```bash
bloomtool hittest -d <测试文件> -b <位图文件> -s <状态输出文件> [-f]
```

**参数:**
- `-d`: 测试文本文件路径（每行一个要测试的ID）
- `-b`: 布隆过滤器位图文件路径
- `-s`: 状态输出文件路径
- `-f`: 仅输出命中的行（过滤模式）

**输出格式:**
- 默认：每行输出 "<原始文本>\t<命中状态>"（0表示未命中，1表示命中）
- 使用 `-f` 参数：仅输出命中的原始文本行

**示例:**
```bash
bloomtool hittest -d test_ids.txt -b bloom.blm -s result.txt
bloomtool hittest -d test_ids.txt -b bloom.blm -s hits_only.txt -f
```

### 3. info - 查看位图信息

显示布隆过滤器位图文件的详细信息。

**语法:**
```bash
bloomtool info -b <位图文件>
```

**参数:**
- `-b`: 布隆过滤器位图文件路径

**示例:**
```bash
bloomtool info -b bloom.blm
```

### 4. and - 位图与运算（求交）

对两个布隆过滤器位图文件执行AND（与）运算，生成新的位图文件。

**注意：对两个文件进行与运算，并不等同于元素求交。请查阅bloomfilter的作用原理。**

**语法:**
```bash
bloomtool and -b1 <位图文件1> -b2 <位图文件2> -o <输出文件>
```

**参数:**
- `-b1`: 第一个布隆过滤器位图文件路径
- `-b2`: 第二个布隆过滤器位图文件路径
- `-o`: AND运算结果输出文件路径

**说明:**
- AND运算结果包含同时存在于两个布隆过滤器中的元素
- 要求两个位图文件的参数（元素数量上限和误判率）必须完全一致
- 运算结果仍然是一个布隆过滤器，可以继续用于其他操作

**示例:**
```bash
# 对两个布隆过滤器执行AND运算
bloomtool and -b1 bloom1.blm -b2 bloom2.blm -b result.blm
```

### 5. or - 位图或运算（求并）

对两个布隆过滤器位图文件执行OR（或）运算，生成新的位图文件。

**语法:**
```bash
bloomtool or -b1 <位图文件1> -b2 <位图文件2> -o <输出文件>
```

**参数:**
- `-b1`: 第一个布隆过滤器位图文件路径
- `-b2`: 第二个布隆过滤器位图文件路径
- `-o`: OR运算结果输出文件路径

**说明:**
- OR运算结果包含存在于任一布隆过滤器中的元素
- 要求两个位图文件的参数（元素数量上限和误判率）必须完全一致
- 运算结果仍然是一个布隆过滤器，可以继续用于其他操作

**示例:**
```bash
# 对两个布隆过滤器执行OR运算
bloomtool or -b1 bloom1.blm -b2 bloom2.blm -b result.blm
```

### 6. help - 帮助信息

显示命令使用帮助。

**语法:**
```bash
bloomtool help
bloomtool [command] -help
```

## 使用示例

### 完整工作流程

1. **创建布隆过滤器**
```bash
# 从设备ID列表创建布隆过滤器
bloomtool makebloom -d device_list.txt -b device_bloom.blm
```

2. **测试设备ID**
```bash
# 测试一批设备ID是否在过滤器中
bloomtool hittest -d test_devices.txt -b device_bloom.blm -s test_results.txt
```

3. **查看过滤器信息**
```bash
# 查看布隆过滤器的统计信息
bloomtool info -b device_bloom.blm
```

4. **位图运算示例**
```bash
# 创建两个不同的布隆过滤器
bloomtool makebloom -d devices1.txt -b bloom1.blm
bloomtool makebloom -d devices2.txt -b bloom2.blm

# AND运算：获取同时存在于两个集合中的元素
bloomtool and -b1 bloom1.blm -b2 bloom2.blm -b intersection.blm

# OR运算：获取存在于任一集合中的元素
bloomtool or -b1 bloom1.blm -b2 bloom2.blm -b union.blm

# 测试运算结果
bloomtool hittest -d test_ids.txt -b intersection.blm -s intersection_results.txt
bloomtool hittest -d test_ids.txt -b union.blm -s union_results.txt
```

## 文件格式说明

### 输入文件格式
- 文本文件，每行一个字符串（如设备ID）
- 支持任意文本格式，建议使用MD5等哈希值

### 输出文件格式
- 布隆过滤器位图文件：二进制格式，包含布隆过滤器数据
- 状态输出文件：文本格式，包含测试结果

## 性能特点

- **内存效率**: 使用压缩位图技术，节省内存空间
- **查询速度**: 常数时间复杂度的查询操作
- **误判率可控**: 可根据需求调整误判率
- **大容量支持**: 支持海量数据处理
- **集合运算**: 支持高效的位图AND/OR运算

## 注意事项

1. 布隆过滤器存在一定的误判率，但不会漏判
2. 不支持从布隆过滤器中删除元素
3. 位图文件大小与元素数量和误判率相关
4. 建议对输入数据进行哈希处理以提高性能
5. AND/OR运算要求两个位图文件的参数必须完全一致

## 依赖项

- Go 1.23+
- github.com/RoaringBitmap/roaring
- github.com/klauspost/compress
- google.golang.org/protobuf