ziftsieve

Search compressed data without full decompression.

Overview

ziftsieve extracts literal bytes from compressed blocks and builds indexes over them. This allows skipping decompression for blocks that provably cannot contain a search pattern.

Traditional:  SSD → Decompress (100GB/s) → Search (10GB/s) = 9GB/s effective
ziftsieve:    SSD → Search compressed (50GB/s) → Decompress 10% = 45GB/s effective
                                                         
                                              5× faster

Supported Formats

Installation

[dependencies]
ziftsieve = "0.1"

# Enable specific formats
ziftsieve = { version = "0.1", features = ["lz4", "gzip", "zstd"] }

Usage

use ziftsieve::{CompressionFormat, CompressedIndex};

// Build index from compressed file
let data = std::fs::read("logs.lz4")?;
let index = CompressedIndex::from_bytes(&data, CompressionFormat::Lz4)?;

// Search - only decompresses blocks that might match
let pattern = b"ERROR";
for block_id in index.candidate_blocks(pattern) {
    println!("Potential match in block {}", block_id);
    // Now decompress just this block to verify
}

How It Works

LZ-family compressors (LZ4, Snappy, Gzip, Zstd) use two techniques:

1. Literal bytes - Copied directly to output
2. Back-references - Copy from earlier in the output

ziftsieve parses the compressed stream and extracts only the literal bytes. For pattern matching, if your search pattern isn't in the literals, it can't be in the decompressed data (back-references only repeat earlier content).

This means:

• No false negatives - If pattern exists, it's found
• Possible false positives - Candidate blocks need verification
• 10-100× faster - Skip decompression for non-matching blocks

Performance

Benchmarks on AMD Ryzen 9 5950X, 1GB log file:

Architecture

Compressed Block
    │
    ├──► Literal Bytes ──► Bloom Filter ──► Index
    │
    └──► Match References ──► (ignored for indexing)

Safety

• #![forbid(unsafe_code)] - Pure Rust implementation
• Fuzz tested with arbitrary inputs
• Property-based tested for correctness

License

MIT License - See LICENSE for details.

Contributing

See CONTRIBUTING.md for guidelines.