Front Coding the Term Dictionary

The vocabulary of a text collection is stored sorted, and sorted words share prefixes heavily: “compress”, “compressed”, “compressing”, “compression”, “compressor” all begin with “compress”. A dictionary that stores each term in full pays for the shared prefix once per term. Front coding eliminates the repetition by storing, for each term, only the number of leading characters it shares with its predecessor plus the novel suffix.

The idea predates search engines — it is the dictionary compression in any sorted string table — but it sits at a specific point in the index design: the dictionary is kept in memory and consulted once per query term, so its compression must not destroy random access to individual terms. That tension between size and random access is the whole subject.

The encoding and the block structure

In the simplest form, the first term of a block is stored in full. Each subsequent term is stored as a pair: an integer length of the common prefix with its predecessor, and the remaining characters. “compress” followed by “compressed” shares eight characters and adds “ed”, so the second entry is (8, “ed”), which costs one length byte plus two character bytes instead of ten.

def front_code(terms):
    out = [('full', terms[0])]
    for i in range(1, len(terms)):
        prev = terms[i - 1]
        cur = terms[i]
        k = 0
        while k < len(prev) and k < len(cur) and prev[k] == cur[k]:
            k += 1
        out.append((k, cur[k:]))
    return out

The prefix length must be capped at 255 for a single-byte length, and real vocabularies produce shared prefixes longer than that only rarely; a two-byte length or a continuation byte covers the pathological case. The suffix length is implied by the term’s total length, which is not stored, so a decoder reconstructs each term by copying its predecessor’s prefix and appending the suffix.

The crucial design choice is that front coding is applied within blocks, not across the whole vocabulary. Each block stores its first term in full — the block anchor — and then front-codes the rest of the block against the chain of predecessors. To decode any single term, a reader starts at the anchor and decodes forward. A block of b terms therefore costs O(b) work for a random access, and the block size trades compression against access cost.

Why not just one block for the whole vocabulary? Because then reading the last term requires decoding every term before it, an O(V) operation. Why not a block of one? Because then nothing is compressed. The useful range is b between a few terms and a few dozen, and the choice is driven by two facts: the anchor overhead of one full term per block is amortised over b − 1 front-coded entries, and the average shared-prefix length depends on how alphabetically clustered the vocabulary is.

Where the savings come from

The compression ratio of front coding depends on the average shared-prefix length, which depends on vocabulary size and language. A larger vocabulary has longer shared prefixes on average, because more words means more tight clusters of related forms; a smaller vocabulary is sparser in dictionary order and shares less. For a typical English vocabulary of a few hundred thousand to a few million terms, the average term length is on the order of ten characters and the average shared prefix is around a third to a half of that, which puts the dictionary at roughly half to two-thirds of its uncompressed size before the length bytes are counted.

The length bytes are a real overhead that the naive account misses. Every front-coded entry pays at least one byte for the prefix length, and short terms pay that byte even when it saves little. A vocabulary with many very short terms — “a”, “an”, “it”, “to” — gets little prefix sharing and pays the length byte per term, so front coding can inflate rather than compress the shortest terms. The fix is to store the length byte only where the sharing is nonzero, or to use a variable-length integer for the prefix length, which is where the technique connects to the byte codes in delta encoding and variable-byte postings.

There is a subtlety about what “predecessor” means. The chain of predecessors is within the block, so the first front-coded term shares a prefix with the anchor, and each later term shares with the immediately previous term. Sharing only with the immediate predecessor is the standard form; sharing with the maximal prefix of any earlier term in the block saves a little more but complicates decode, because the reference must then carry which predecessor to use. Immediate-predecessor sharing is what the name refers to and what every implementation uses.

Random access and the block index

A front-coded dictionary is not directly searchable. Binary search over the terms is impossible without materialising them, and materialising is O(b) per probe. The access structure is therefore a separate array of anchors: for each block, the byte offset of its first term and that term’s decoded value. Lookup binary-searches the anchors to find the block containing the target, then decodes forward within that block.

The anchor array is itself a sorted list of terms, one per block, so it can be searched with the same techniques as the term dictionary structures — binary search over inline prefix bytes, or a hash table keyed on the anchor’s first bytes. The anchor array is small relative to the dictionary: with b = 8, one entry in eight, which is a few hundred kilobytes for a million-term vocabulary and stays resident.

Decoding forward within a block is a linear scan of b terms, but it is a cheap linear scan: each step copies a prefix and appends a suffix, and the whole block is contiguous, so it runs at memory speed. The comparison that terminates the scan is against the target term, and because the terms in a block are sorted, the scan can stop early when it passes the target lexicographically.

The practical choice of b balances two things. Small b makes random access fast and the anchor array large; large b makes random access slow and the anchor array small. The anchor array’s own overhead — a full term per block — is a second compression tax, so the total size has a minimum at some intermediate b. That minimum is shallow, and access cost is the binding constraint in a query engine, so implementations pick b toward the small end, commonly between 4 and 16, and accept a dictionary a few percent larger than the space-optimal point.

Prefix-aware alternatives

Front coding is one of a family of prefix-sharing schemes, and it is worth knowing what it is not doing. A radix tree shares prefixes structurally, with one node per shared character, and a minimal automaton shares suffixes as well. Front coding shares only consecutive prefixes within a block and shares nothing structurally, so it is a compression transform, not an index in its own right: the anchor array is the index, and the front-coded blocks are the payload.

The transform composes badly with other compression in one specific way: a front-coded block is a sequence of (length, suffix) pairs, and those integers and strings could themselves be compressed, but doing so reintroduces random-access problems inside the block. In practice the length bytes are left as raw bytes and the suffixes as raw characters, which is why the technique is described as “front coding” rather than “front coding plus entropy coding”. The interaction that does matter is with the postings: the dictionary pointer in each entry points into a postings file that is itself compressed with bit packing or a byte code, and the dictionary’s job is to make that pointer cheap to reach.

What front coding costs in a live index

Two consequences follow from the block-and-anchor structure, and both matter in an index that updates.

First, appending terms is cheap only at the end of the last block. A new term that sorts before the end of a block requires rewriting that block, and because block boundaries are fixed by count, an insertion can cascade. Dictionaries built by a merge process are immutable, so this cost is paid at build time and not per update; dictionaries that accept in-place updates either rebuild blocks or keep an unsorted delta on top.

Second, the prefix chain means a single-byte corruption in a suffix changes every later term in the block, because each term’s full form is reconstructed from its predecessor. A full-term dictionary localises a corruption to one entry; a front-coded dictionary propagates it to the rest of the block. With block sizes under sixteen, the blast radius is small, but it is nonzero, and it is the reason checksums, when used, are computed per block rather than per entry.

Front coding earns its place because the dictionary is a real fraction of index size when documents are short — web snippets, log lines, messages — and a negligible fraction when documents are long. The choice to use it is therefore a statement about the collection’s average document length, and the block size is the one real parameter it exposes.