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. Holding one is a proof that its buffers satisfy the structural invariants in this module’s documentation.

CompactDictionaryView

Borrowed, Copy 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).

OwnedDictionaryStorage

The default owned storage used by CompactDictionary.

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 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 a fixed seed.

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.

DictionaryStorage

Storage for a compact dictionary’s serialized buffers.

DictionaryView

A borrowed 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 dict into out, returning the bytes written. It over-reads a fixed 16 bytes per token, relying on the structural invariants guaranteed by DictionaryView. 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 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.