Random-Access Compressed String Store (RACSS)

RACSS is a hybrid technology positioned between compression and indexing. It is designed for compact storage of large collections of strings with true random access, allowing any individual string to be decompressed independently, without decoding the entire dataset.

RACSS is neither a general-purpose compressor nor a classical string indexing system. It represents a separate class of solutions: a compressed string retrieval subsystem.

What RACSS actually provides

RACSS enables:

• compact storage of thousands or tens of thousands of strings;
• deterministic extraction of any string by index;
• decompression without global state or adaptive models;
• predictable runtime behavior suitable for constrained systems.

In practice, RACSS behaves as a string store optimized for retrieval, not as a streaming compressor.

Core concept

Strings are stored using a recursive dictionary representation:

• dictionary entries may reference other entries;
• references are compact and efficiently encoded;
• decoding requires no auxiliary tables or external state.

Despite the recursive structure, real-world datasets exhibit very shallow recursion depth, even for large and highly redundant inputs.

This makes RACSS particularly suitable for systems where:

• stack depth is limited,
• memory usage must be predictable,
• decompression logic must remain simple and inspectable.

Example: how RACSS tokenizes real text

To make the core idea concrete, here is a minimal real-world example showing how RACSS processes and tokenizes text.
Input text (8 lines):

Jingle Bells, Jingle Bells
Jingle all the way
Oh what fun it is to ride in a
One horse open sleigh
Jingle Bells, Jingle Bells
Jingle all the way
Oh what fun it is to ride in a one
Horse open sleigh

After compression, RACSS produces two kinds of entries:

• L - logical input lines (stored as token sequences)
• D - dictionary entries (reusable substrings)

Tokens in square brackets ([n]) refer to dictionary entries by index.

Logical lines

L       1 :"[7]"
L       2 :"[3]"
L       3 :"[2]"
L       4 :"On[6]h[4]"
L       5 :"[7]"
L       6 :"[3]"
L       7 :"[2] one"
L       8 :"H[4]"

Each logical line is stored independently as a sequence of literals and dictionary references.

Dictionary entries

D       1 :"[5]Bells"
D       2 :"Oh what fu[8]it is to rid[6]i[8]a"
D       3 :"[5]all th[6]way"
D       4 :"ors[6]ope[8]sleigh"
D       5 :"Jingl[6]"
D       6 :"e "
D       7 :"[1], [1]"
D       8 :"n "

The dictionary is self-referential: dictionary entries may reference other dictionary entries. This allows RACSS to represent recurring substrings compactly without flattening them into a single global stream.

What this demonstrates

• No global stream dependency - Each line can be decoded on its own. There is no need to reconstruct all previous text.
• Fine-grained reuse - Common substrings like "Jingle", "ells", "e ", "n " are factored out once and reused everywhere.
• Recursive structure, not linear history - Unlike LZ-based compressors, RACSS builds a small directed acyclic graph of substrings instead of a sliding window over past output.
• True random access - Any logical line (L n) can be reconstructed directly by following its dictionary references - without decoding unrelated data.

How RACSS differs from gzip / LZ / zstd

RACSS does not aim to compete with a general-purpose compressors. It is designed for a different problem space, where stream-oriented compression is inherently inefficient, and fast random access to individual lines or records is required. The table below is provided solely for comparison purposes with gzip, one of the most widely used compressors in Linux environments. Keep in mind that RACSS files include indices to enable arbitrary line retrieval without decompressing the entire file. RACSS is particularly useful for game localization files, dictionaries, navigation databases, and embedded systems, where compact storage and efficient random access are critical.

Typical application areas

Game engines and consoles

• localization string tables,
• dialogs and UI text,
• tight storage constraints.

Navigation systems

• street names,
• POI databases,
• offline map metadata.

Embedded and legacy devices

• firmware with fixed flash size,
• security updates on old hardware,
• environments with strict stack and RAM limits.

Offline reference data

• dictionaries,
• help systems,
• static text databases.

Demo retrieval tool

The distribution includes a minimal demo retrieval program (rfetch), implemented in approximately 200 lines of C.

Its purpose is to:

• demonstrate that random access decompression works in practice;
• show that no additional in-memory data structures are required;
• allow performance measurement and inspection of decoding logic.

This program is not a full API and not a reference specification. It is intentionally minimal, serving as a proof-of-concept and a transparency tool.

Supported modes:

Usage:
  ./rfetch <file.rc>                    - unpack all lines (default)
  ./rfetch <file.rc>  N                 - unpack line N (1-based)
  ./rfetch <file.rc>  0                 - print raw lines and dictionary in debug format
  ./rfetch <file.rc> -N                 - unpack dict entry N (1-based)
  ./rfetch <file.rc> <out-of-range num> - print valid range and header

What is published

This release provides:

• an example of the RACSS binary format as produced by the toolchain;
• a minimal, self-contained decompression demo;
• sample datasets for comparison with gzip.

It intentionally does not include:

• a formal format specification;
• a full reference decoder API;
• dictionary construction algorithms.

The goal is to demonstrate feasibility, performance, and simplicity, not to disclose the full compression pipeline.

Why this is commercially relevant

RACSS enables:

• extending the lifetime of legacy hardware;
• reducing storage footprint without architectural changes;
• deterministic, low-risk runtime behavior;
• easy integration into existing embedded and firmware projects.

It is especially relevant for companies maintaining long-lived products where storage size, predictability, and backward compatibility matter more than peak compression ratio.