OnPair: Short Strings Compression for Fast Random Access

Go implementation of OnPair, a compression algorithm designed for efficient random access on sequences of short strings.

Overview

OnPair is a field-level compression algorithm designed for workloads requiring fast random access to individual strings in large collections. The compression process consists of two distinct phases:

• Training Phase: A longest prefix matching strategy is used to parse the input and identify frequent adjacent token pairs. When the frequency of a pair exceeds a predefined threshold, a new token is created to represent the merged pair. This continues until the dictionary is full or the input data is exhausted. The dictionary supports up to 65,536 tokens.
• Parsing Phase: Once the dictionary is constructed, each string is compressed independently into a sequence of token IDs by greedily applying longest prefix matching.

OnPair16 is a variant that limits dictionary entries to a maximum length of 16 bytes. This constraint enables further optimizations in both longest prefix matching and decoding.

Installation

go get github.com/seiflotfy/onpair

Quick Start

Reusable model (TrainModel -> Encode)

package main

import (
    "fmt"
    "github.com/seiflotfy/onpair"
)

func main() {
    trainRows := []string{
        "user_000001",
        "user_000002",
        "user_000003",
        "admin_001",
        "user_000004",
    }

    model, err := onpair.TrainModel(trainRows, onpair.WithMaxTokenLength(16))
    if err != nil {
        panic(err)
    }

    archive, err := model.Encode(trainRows)
    if err != nil {
        panic(err)
    }

    for i := 0; i < archive.Rows(); i++ {
        row, err := archive.AppendRow(nil, i)
        if err != nil {
            panic(err)
        }
        fmt.Printf("row %d: %s\n", i, string(row))
    }
}

Single-shot encode (Encoder)

enc := onpair.NewEncoder(
    onpair.WithMaxTokenLength(16), // optional
    onpair.WithMaxTokenID(4095),   // optional smaller dictionary cap
    onpair.WithTokenBitWidth(12),  // optional packed 12-bit token stream
    onpair.WithTrainingSampleBytes(8*1024*1024), // optional larger training sample
    onpair.WithTemplateStratifiedSampling(2048), // optional template-based stratified sampling
)
archive, err := enc.Encode([]string{"user_001", "user_002", "admin_001"})
if err != nil {
    panic(err)
}

WithTokenBitWidth(12) uses packed 12-bit token IDs in archive storage and automatically limits dictionary IDs to 4095. The serialized compressed_data stage now auto-selects the smallest among raw, flate(raw), byte-codebook+escape, and flate(codebook) for both 12-bit and 16-bit token streams. WithTemplateStratifiedSampling uses a lightweight template normalization heuristic for sample balancing; it is not a full log-template parser.

Advanced Features

Random access (decode one string at a time)

row, err := archive.AppendRow(nil, 42) // row index 42 only
if err != nil {
    panic(err)
}
fmt.Println(string(row))

Strict decoding into caller buffers

buf := make([]byte, 256)
n, err := archive.DecompressString(0, buf) // returns ErrShortBuffer if too small
if err != nil {
    panic(err)
}
fmt.Println(string(buf[:n]))

DecompressString and DecompressAllChecked treat buffer bytes beyond the returned length as scratch space: the fast decode path may overwrite them (never past len(buf)). Use buf[:n] only.

Bulk decode with error handling

all := make([]byte, 4096)
n, err := archive.DecompressAllChecked(all)
if err != nil {
    panic(err)
}
_ = all[:n]

Compressed-domain search

Equality, prefix, and substring queries run directly over the token streams, without decoding rows back to bytes. The dictionary is sorted at training time, so a Searcher validates once at construction and queries cannot fail on malformed data:

s, err := archive.Searcher()
if err != nil {
    panic(err)
}
equal := s.RowsEqualTo([]byte("user_000002"))     // row indices exactly equal
prefixed := s.RowsStartingWith([]byte("user_"))   // row indices with prefix
containing, err := s.RowsContaining([]byte("_00")) // row indices with substring

Archives serialized by versions that predate dictionary sorting fail Searcher() with ErrDictionaryNotSearchable; re-encode them to search.

Serialization

file, err := os.Create("archive.bin")
if err != nil {
    panic(err)
}
defer file.Close()

if _, err := archive.WriteTo(file); err != nil {
    panic(err)
}

loaded := &onpair.Archive{}
if _, err := file.Seek(0, io.SeekStart); err != nil {
    panic(err)
}
if _, err := loaded.ReadFrom(file); err != nil {
    panic(err)
}

API Reference

Recommended lifecycle (Model + Archive)

model, err := onpair.TrainModel(trainRows, onpair.WithMaxTokenLength(16))
if err != nil { /* ... */ }

archive, err := model.Encode(queryRows)
if err != nil { /* ... */ }

out, err := archive.AppendRow(nil, 0)
if err != nil { /* ... */ }
_ = out

Constructors and options

• NewEncoder(opts ...Option) *Encoder
• NewModel(opts ...Option) *Model
• TrainModel(strings []string, opts ...Option) (*Model, error)
• WithThreshold(t uint16) Option
• WithMaxTokenLength(n int) Option
• WithMaxTokenID(maxID uint16) Option
• WithTokenBitWidth(bits uint8) Option (12 or 16, default 16)
• WithTrainingSampleBytes(n int) Option (default 1 MiB)
• WithTemplateStratifiedSampling(maxClusters int) Option
• WithParallelism(n int) Option (compress with up to n goroutines on inputs over ~1 MiB; byte-identical output, n <= 0 means GOMAXPROCS. Encoding is single-goroutine unless this is set)

Encode/decode

• (*Encoder).Encode(strings []string) (*Archive, error) (single-shot train+encode)
• (*Model).Train(strings []string) error
• (*Model).Encode(strings []string) (*Archive, error)
• (*Model).Trained() bool
• (*Archive).Rows() int
• (*Archive).DecodedLen(index int) (int, error)
• (*Archive).AppendRow(dst []byte, index int) ([]byte, error)
• (*Archive).AppendAll(dst []byte) ([]byte, error)
• (*Archive).DecompressString(index int, buffer []byte) (int, error)
• (*Archive).DecompressAllChecked(buffer []byte) (int, error)

Compressed-domain search

• (*Archive).Searcher() (*Searcher, error)
• (*Searcher).Tokenize(text []byte) []uint16
• (*Searcher).RowsEqualTo(needle []byte) []int
• (*Searcher).RowsStartingWith(prefix []byte) []int
• (*Searcher).RowsContaining(pattern []byte) ([]int, error)

Serialization

• (*Archive).WriteTo(w io.Writer) (int64, error)
• (*Archive).ReadFrom(r io.Reader) (int64, error)

Building from Source

git clone https://github.com/seiflotfy/onpair
cd onpair

# Run tests
go test ./...

# Run benchmarks
go test -bench=. ./...

License

This project is licensed under the MIT License - see the LICENSE file for details.

Portions are derived from third-party projects; see THIRD_PARTY_LICENSES for their notices.