Crate bbse

bbse — Backward Binary Search Encoding

A minimal and deterministic encoding scheme for any sorted range, based on walking the binary search path to a target value.

Useful in scenarios requiring:

• compact, prefix-free representation of integers from a range;
• simple and reversible encoding for sorted domains;
• constant-time decoding without full table reconstruction (unlike Elias/Fano).

Example

use bbse::{encode, decode};
let path = bbse::encode(0, 16, 5);       // binary search path to 5 in [0..16)
let value = bbse::decode(0, 16, &path);  // == 5
assert_eq!(value, 5);

Functions

decode

Decodes a binary decision sequence into the value it encodes, given the original [start, end) range.

encode

Encodes a value as a binary decision sequence (left/right), given a sorted range [start, end) and the target value.