dictstr

Dictstr is a conceptual data structure and encoding format designed to compactly store strings by exploiting redundancy through a shared dictionary of substrings. In a dictstr representation, the data consists of a dictionary that maps frequently occurring substrings to compact tokens, and a sequence for each string that references those tokens along with any literals not present in the dictionary. The dictionary can be built from a corpus of strings (static dictionary) or grow dynamically as new substrings appear (adaptive dictionary). Encoding a string involves replacing occurrences of dictionary substrings with their tokens and emitting any remaining characters as literals. Decoding uses the token stream and the dictionary to reconstruct the original strings.

Dictstr is particularly useful when a collection contains many overlapping substrings, such as log files, natural-language corpora, or configuration data. It supports efficient storage and can enable fast comparisons for equality or prefix checks by comparing token sequences instead of raw text. Some implementations may support incremental updates, where new substrings are added to the dictionary without re-encoding existing data, though this can complicate decoding.

Performance characteristics vary with dictionary design and data characteristics. Strong redundancy yields high compression, while highly random data yields modest gains and increased dictionary size. Practical use typically involves a trade-off between encoding speed, decoding speed, and memory usage for the dictionary.

See also dictionary encoding, Lempel–Ziv, tokenization, and trie-based data structures.