Positionsindex

Positionsindex is a term used in information retrieval to denote a data structure that records the exact positions of terms within documents. It is typically implemented as a positional inverted index, an extension of the standard inverted index that adds position information for each term occurrence. For each term, the index stores a mapping from document identifiers to the list of positions where the term appears in that document. Positions are usually measured in word offsets within the document, though alternative measures can be used for different applications.

During indexing, each token is assigned a position in its document, and the index updates the postings lists accordingly. An example: in a document with the sequence "to be or not to be," the term 'to' occurs at positions 1 and 5; 'be' at positions 2 and 6; 'or' at 3; 'not' at 4. The index would record postings such as 'to' -> {doc1: [1, 5]}, 'be' -> {doc1: [2, 6]}, 'or' -> {doc1: [3]}, 'not' -> {doc1: [4]}.

Positionsindex supports advanced query capabilities, notably phrase queries and proximity queries. Phrase queries verify that terms occur in a specified order with fixed gaps, while proximity queries require terms to appear within a certain distance of each other. When combined with the inverted index, a positional index enables efficient evaluation of these queries and can improve ranking by incorporating term proximity signals.

Storage and performance considerations include increased index size due to position lists. Compression techniques such as delta encoding, gap encoding, and bit-packing are commonly used to mitigate this overhead. Updates are more complex and may require reorganization of stored postings. Related concepts include variations like n-gram indexes and suffix-based approaches, which trade off accuracy, latency, and storage for different workloads.