Front-coded lexicons: store shared prefixes within sorted term blocks

Last updated: 5 Oct 20269 min read

tutorial

A front-coded term lexicon sorts distinct terms and divides them into small blocks. It retains the first term of each block in full, then stores each later term as the length of its common prefix with that anchor plus its remaining suffix. Searching compares the request with block anchors, reconstructs one candidate block, and checks whether the exact term occurs there. The anchor rule is explicit: every encoded term refers to its block's first term, not to the preceding term. This form is easy to inspect but does not pack lengths into bytes or guarantee a net memory saving in Python, where tuples and strings have object overhead. It is a static dictionary without postings or token-frequency data.

Operational case

Seven distinct incident terms include pressure, pressurize, pressurized, pump, pumps, valve, and valves. With blocks of three sorted terms, the first block reconstructs pressure, pressurize, pressurized. The exact term pressurized is present, while pressurizer is absent even though it shares a long prefix. A lookup for a string before the first anchor also fails. This demonstrates why prefix similarity is useful for storage but does not imply term membership. A new term inserted between existing anchors may change block boundaries and encoded suffixes, so this simple snapshot rebuilds rather than editing compressed storage in place.

Working Python program

from bisect import bisect_right


class FrontCodedIncidentTerms:
    def __init__(self, terms, block_size=4):
        if block_size < 1:
            raise ValueError("block size must be positive")
        ordered = sorted(set(terms))
        self.anchors = []
        self.blocks = []
        for start in range(0, len(ordered), block_size):
            group = ordered[start:start + block_size]
            anchor = group[0]
            self.anchors.append(anchor)
            encoded = []
            for term in group[1:]:
                shared = 0
                while shared < min(len(anchor), len(term)) and anchor[shared] == term[shared]:
                    shared += 1
                encoded.append((shared, term[shared:]))
            self.blocks.append(encoded)

    def block_terms(self, block):
        anchor = self.anchors[block]
        return [anchor] + [anchor[:shared] + suffix for shared, suffix in self.blocks[block]]

    def contains(self, term):
        block = bisect_right(self.anchors, term) - 1
        return block >= 0 and term in self.block_terms(block)


if __name__ == "__main__":
    lexicon = FrontCodedIncidentTerms([
        "pressure", "pressurized", "pressurize", "pump", "pumps", "valve", "valves"
    ], block_size=3)
    print("first-block=", lexicon.block_terms(0), sep="")
    print("pressurized=", lexicon.contains("pressurized"), sep="")
    print("pressurizer=", lexicon.contains("pressurizer"), sep="")

Output

first-block=['pressure', 'pressurize', 'pressurized']
pressurized=True
pressurizer=False

Time, space, and tradeoff

For U distinct terms with total character count C and block size K, sorting costs O(U log U) string comparisons and encoding scans shared prefixes up to O(C + U times anchor length) in a conservative bound. The stored payload consists of full anchors, prefix lengths, and suffixes; actual byte savings depend on term similarity and representation overhead. Searching anchors takes O(log(U/K)) string comparisons, then reconstructing at most K terms costs time proportional to their characters. This favors compact sorted vocabularies with common beginnings. A trie offers prefix traversal without rebuilding whole blocks, while a plain hash set often wins for simple in-memory exact membership.

Common Mistakes

Do not decode a suffix against the preceding term when this format uses the block anchor.
Do not report a shared prefix as an exact term hit.
Do not assume Python object storage is byte-compressed by this representation.
Do not change block size or sorted terms without rebuilding encoded blocks.

Connected lessons

Compare its query with Inverted indexes: intersect sorted incident postings, Positional postings: find exact token phrases, Trigram indexes: filter and verify substring candidates, then run the incident text index audit and index contract quiz.

LZ78 phrase tries: emit dictionary index and next symbol adds a related structure with a different operation boundary.

data structures

hash-tables