flashsieve 0.1.1

Storage-level pre-filtering for pattern matching — skip blocks that can't contain matches
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

# flashsieve

[![crates.io](https://img.shields.io/crates/v/flashsieve.svg)](https://crates.io/crates/flashsieve)
[![docs.rs](https://docs.rs/flashsieve/badge.svg)](https://docs.rs/flashsieve)
[![license](https://img.shields.io/crates/l/flashsieve.svg)](LICENSE)

**Storage-level pre-filtering for pattern matching.**

`flashsieve` builds per-block byte histograms and 2-byte n-gram bloom filters,
then uses them to answer which blocks *might* contain matches. If a block cannot
contain a pattern, it is skipped entirely—saving CPU, I/O, and memory at scale.

---

## Installation

```toml
[dependencies]
flashsieve = "0.1"
```

Minimum supported Rust version: **1.85**.

---

## Quick Start

```rust
use flashsieve::{BlockIndexBuilder, ByteFilter, NgramFilter};

let mut block_a = vec![b'x'; 256];
let mut block_b = vec![b'y'; 256];
block_a[..6].copy_from_slice(b"secret");
block_b[..5].copy_from_slice(b"token");
let patterns: [&[u8]; 2] = [b"secret", b"token"];

let index = BlockIndexBuilder::new()
    .block_size(256)
    .bloom_bits(512)
    .build_streaming([block_a, block_b].into_iter())?;

let byte_filter = ByteFilter::from_patterns(&patterns);
let ngram_filter = NgramFilter::from_patterns(&patterns);

let candidates = index.candidate_blocks(&byte_filter, &ngram_filter);
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].length, 512);
# Ok::<(), flashsieve::Error>(())
```

---

## What It Does

| Component | Purpose |
|-----------|---------|
| `BlockIndexBuilder` | Constructs indexes from raw bytes or streaming blocks |
| `BlockIndex` | In-memory index with per-block histograms & bloom filters |
| `FileBloomIndex` | File-level bloom union for fast n-gram rejection before per-block scans |
| `MmapBlockIndex` | Zero-parse, zero-copy queries over serialized indexes |
| `IncrementalBuilder` | Append new blocks to existing indexes without rebuilding |
| `ByteFilter` | Reject blocks that don't contain all required bytes |
| `NgramFilter` | Reject blocks that don't contain all required 2-byte n-grams |

---

## Bloom Filter Math

The theoretical false-positive rate for a Bloom filter with:

- `m` = number of bits  
- `n` = number of distinct n-grams inserted  
- `k` = number of hash functions (`k = 3` in this crate)

is approximately:

```text
FPR ≈ (1 - e^(-kn/m))^k
```

For the optimal number of hash functions `k = (m/n) × ln(2)`:

```text
FPR ≈ 0.6185^(m/n)
```

For filters with **≥4096 bits**, `flashsieve` allocates an exact 65,536-bit pair
table, giving **zero false positives** for all possible 2-byte n-gram queries.

---

## Safety

This crate keeps `unsafe` usage narrowly scoped to hot-path bloom-filter word
loads where index validity is proven by construction. All serialized input is
validated (magic, version, checksum, bounds) before use—corrupt files return
typed errors rather than panicking.

---

## License

Licensed under the MIT license ([LICENSE](LICENSE) or https://opensource.org/licenses/MIT).