Crate onpair 

OnPair: dictionary-based short-string compression for fast random access.

Rust port of the algorithm described in arXiv:2508.02280. OnPair replaces recurring substrings (“tokens”) with fixed-width integer codes into a dictionary; decoding is a gather-copy, so individual rows decode in isolation at no extra cost.

Layout

A compressed Column is a CompactDictionary (token bytes + offsets), a code stream (one Token per emitted token), and a row layer (offsets into the code stream). Borrow it as a ColumnView — or build a view directly from buffers deserialized from storage — and decode into a caller-owned buffer: the whole column with ColumnView::decompress_into, one row with ColumnView::decompress_row_into, or decode_into over a reusable WideDictionary. The caller owns buffer sizing: size it from ColumnView::decoded_len or ColumnView::row_decoded_len (plus DECODE_PADDING).

Examples

use onpair::{Column, DECODE_PADDING, DEFAULT_CONFIG};
use std::mem::MaybeUninit;

// Compress an Arrow (bytes, offsets) value pair.
let bytes = b"catdogcat";
let offsets: [u32; 4] = [0, 3, 6, 9];
let col = Column::compress(bytes, &offsets, DEFAULT_CONFIG).unwrap();
let view = col.view();

// Random-access a single row into a caller buffer — no full decode, no
// wide-table build. Size it from the row's decoded length plus DECODE_PADDING.
let mut row = vec![MaybeUninit::uninit(); view.row_decoded_len(1) + DECODE_PADDING];
// SAFETY: `col` is valid by construction and `row` is sized as required.
let n = unsafe { view.decompress_row_into(1, &mut row) };
assert_eq!(unsafe { std::slice::from_raw_parts(row.as_ptr().cast::<u8>(), n) }, b"dog");

// Bulk-decode the whole column into a caller buffer, sized from the decoded length.
let mut buf = vec![MaybeUninit::uninit(); view.decoded_len() + DECODE_PADDING];
// SAFETY: `col` is freshly compressed (valid by construction) and `buf` is sized.
let n = unsafe { view.decompress_into(&mut buf) };
let out = unsafe { std::slice::from_raw_parts(buf.as_ptr().cast::<u8>(), n) };
assert_eq!(out, b"catdogcat");

The trained encoder is also available directly via Parser, to reuse one dictionary across several corpora.

Modules

search

Compressed-domain search: equality, prefix, and substring queries answered directly over the code stream, without decoding rows back to bytes.

Structs

Column

Owned compressed column, produced by Column::compress / Parser::parse. Self-contained: it carries its own dictionary, so it decodes without reference to the training corpus.

ColumnView

Borrowed, Copy view over a compressed column — obtained from a Column or built directly from buffers deserialized from storage.

CompactDictionary

Owned compact dictionary — trusted: holding one is a proof that its buffers satisfy the invariants in this module’s documentation.

CompactDictionaryView

Borrowed, Copy, trusted view over a compact dictionary’s buffers.

Config

Training configuration. See DEFAULT_CONFIG for a reasonable starting point.

MaxDictBits

Training-time upper bound on the dictionary: at most 2^bits tokens.

OutputTooSmall

try_decode_into’s out could not hold the decoded bytes. Nothing was written past the end of out; size it from decoded_len and retry (the checked decode needs no DECODE_PADDING slack — see try_decode_into).

Parser

A trained encoder. Holds the CompactDictionary (cloned into each Column so columns are self-contained) and a crate-private, encode-side longest-prefix matcher built from it.

Threshold

Dynamic-threshold sample fraction. Validated to (0.0, 1.0] at construction, so a Threshold always holds an in-range value.

TokenRange

Inclusive token-id range [begin, last] over the sorted dictionary.

WideDictionary

Owned wide dictionary: num_tokens rows of MAX_TOKEN_SIZE bytes plus per-token lengths.

WideDictionaryView

Borrowed, Copy, trusted view over a wide dictionary’s buffers.

Enums

Error

Error returned by the public training and encoding API.

InvalidColumn

A violation found while validating compressed buffers.

Constants

DECODE_PADDING

Trailing bytes a decode_into output buffer needs beyond the decoded length. The decoder over-stores a fixed MAX_TOKEN_SIZE-byte chunk for the final token — up to MAX_TOKEN_SIZE - 1 bytes past the logical end — so an output buffer is sized as decoded_len + DECODE_PADDING.

DEFAULT_CONFIG

Reasonable starting point: dictionary capped at 4 096 tokens, dynamic threshold sampling 15 %, and deterministic sampling with seed 42.

MAX_TOKEN_SIZE

Maximum byte length of any dictionary token, and the fixed width the decoder reads per token.

Traits

Dictionary

An owned dictionary that can lend its borrowed DictionaryView.

DictionaryView

A borrowed trusted dictionary’s token-read interface, abstracted over the layout (CompactDictionaryView or WideDictionaryView).

Offset

Width of a row offset. Sealed to u32 and u64 to match the Arrow binary and large-binary layouts.

Functions

code_bits_for_num_tokens

Minimum code width needed to address num_tokens distinct tokens: ceil(log2(num_tokens)).

compress

Compress an Arrow (bytes, offsets) value pair end-to-end. Equivalent to Parser::train(..)?.parse(..), but validates the offsets once instead of in both the train and parse steps. offsets has n + 1 entries.

decode_into^⚠

Decode codes against an already-validated dict into out, returning the bytes written. It over-reads a fixed 16 bytes per token, trusting the dictionary’s offsets/lengths (validated up front). Each code is bounds-checked in the loop (a near-free, predicted-not-taken branch); an out-of-range code panics with InvalidColumn::CodeOutOfRange.

decoded_len

Exact decoded byte length of codes against dict (the sum of token lengths) — sizes a decode buffer.

try_decode_into

Decode codes against an already-validated dict into out — the safe, buffer-checked counterpart of decode_into. Returns Ok(bytes_written), or Err(OutputTooSmall) if out cannot hold the result (in which case nothing is written past the end of out). Never reads or writes out of bounds.

Type Aliases

Token

Identifies a dictionary token: a token id, equivalently a code in a column’s code stream. Named Token for simplicity.