Positional postings: find exact token phrases

Operational case

Incident 103 contains pump pressure low pressure. Incident 218 contains low pump pressure. Incident 347 contains pump pressure pressure low. The phrase pump pressure appears in all three. Pressure low appears in 103 and 347. Pressure pressure appears only in 347. A document-level AND index would consider both terms present but could not distinguish pump pressure from pressure pump or test repeated-term adjacency. This positional example makes that distinction concrete. A later edit to one incident changes token offsets beyond the edit and requires a rebuilt snapshot in this simple design.

Working Python program

from collections import defaultdict


class PositionalIncidentIndex:
    def __init__(self, documents):
        self.positions = defaultdict(lambda: defaultdict(list))
        for document_id, tokens in documents.items():
            for position, token in enumerate(tokens):
                self.positions[token][document_id].append(position)

    def phrase_documents(self, phrase):
        if not phrase:
            return []
        if any(token not in self.positions for token in phrase):
            return []
        candidates = set(self.positions[phrase[0]])
        for token in phrase[1:]:
            candidates.intersection_update(self.positions[token])
        found = []
        for document_id in sorted(candidates):
            positions = [set(self.positions[token][document_id]) for token in phrase]
            if any(all(start + offset in positions[offset] for offset in range(1, len(phrase)))
                   for start in positions[0]):
                found.append(document_id)
        return found


if __name__ == "__main__":
    incidents = PositionalIncidentIndex({
        103: ["pump", "pressure", "low", "pressure"],
        218: ["low", "pump", "pressure"],
        347: ["pump", "pressure", "pressure", "low"],
    })
    print("pump-pressure=", incidents.phrase_documents(["pump", "pressure"]), sep="")
    print("pressure-low=", incidents.phrase_documents(["pressure", "low"]), sep="")
    print("repeat=", incidents.phrase_documents(["pressure", "pressure"]), sep="")

Output

pump-pressure=[103, 218, 347]
pressure-low=[103, 347]
repeat=[347]

Time, space, and tradeoff

Let T be the number of tokens across the corpus and F the number of stored occurrences. Index construction takes O(T) expected dictionary work and O(F) position storage. For a query of K terms, candidate-set intersection costs work tied to participating posting sets; within each candidate document, creating K position sets and checking starting positions costs O(sum of relevant stored positions plus K times the first-term occurrences) expected hash work. The worst case can approach the number of indexed positions examined. Positional postings use more memory than document-level postings, but answer phrase and proximity questions that the smaller structure cannot. This example is immutable and does not implement ranking or phrase slop.

Common Mistakes

• Do not accept a document merely because all phrase terms appear somewhere in it.
• Do not collapse repeated token offsets into one position.
• Do not change tokenization rules between indexing and querying.
• Do not claim phrase order can be recovered from plain document ID lists.

Connected lessons

• Hashing
• Data Structures
• Inverted indexes: intersect sorted incident postings
• Failure-linked tries: find overlapping alert terms in one scan
• Suffix arrays: indexed substring search and adjacent LCP
• Projects
• Quizzes

Compare its query with Inverted indexes: intersect sorted incident postings, Trigram indexes: filter and verify substring candidates, Front-coded lexicons: store shared prefixes within sorted term blocks, then run the incident text index audit and index contract quiz.