Crate bbse

BBSE — Backward Binary Search Encoding (Stack-based Concept)

BBSE encodes integer values from a known sorted range as a compact path of binary decisions — the same steps a binary search would take to locate the value.

This encoding is:

• Prefix-free and minimal;
• Deterministic and reversible;
• Stack-compatible — no headers, no length metadata;
• Range-aware — optimized for values near the center.

Overview

Each value is represented as a BitVec, encoding the binary decisions taken while performing binary search to locate the value in [start..end). The search terminates early if the midpoint equals the target value.

BBSE paths can be stored directly in a stack, enabling extremely compact storage.

Features

• Compact, unique encoding per value;
• No external data needed to decode (just start..end range);
• Zero allocation per path in streaming form;
• No statistical modeling — pure binary search geometry.

Examples

use bbse::{encode, decode};
let path = encode(0, 256, 128); // one step or even empty path
let value = decode(0, 256, &path);
assert_eq!(value, 128);

use bbse::{encode, BBSEStack};
let mut stack = BBSEStack::new();
for v in [0, 1, 2, 3, 4, 5, 6, 7] {
    stack.push(encode(0, 8, v));
}
let decoded = stack.decode_all(0, 8);
assert_eq!(decoded, vec![0, 1, 2, 3, 4, 5, 6, 7]);

Limitations

• Values must lie within the specified range.
• Encoded paths must be decoded with the same range.
• Not optimized for random-access decoding without range knowledge.

Structs

BBSEStack

Stack model — store multiple values as separate paths

Functions

decode

BBSE decoder: consumes a path and returns the corresponding value

decode_from

BBSE custom midpoint (optional for default midpoint encoding)

encode

BBSE stack-based encoding: returns a BitVec representing the path

encode_from

BBSE custom midpoint (optional)