ngramindex

An ngram index, often simply called an n-gram index, is a data structure used in text retrieval and processing that stores occurrences of contiguous sequences of n characters (or, less commonly, n words) from a collection of documents. It supports fast substring search, approximate matching, and related text analysis tasks by enabling efficient lookup of documents containing specific sequences.

Construction typically involves two steps. First, each document is decomposed into overlapping n-grams using a sliding window. Second, an inverted index is built that maps each n-gram to a posting list of documents (and often frequencies, positions, or other metadata). The choice of n (and whether to use character or word n-grams) determines the balance between precision and recall and influences index size and noise.

Query processing relies on matching the query’s n-grams against the index. The system retrieves candidate documents by intersecting or aggregating the postings for the query n-grams and then ranks them using similarity measures such as Dice, Jaccard, or weighted scoring based on n-gram overlaps and positional information. This approach makes n-gram indexes useful for fuzzy search, autocomplete, spelling correction, and language-agnostic matching, especially in languages with flexible word boundaries.

Applications include search engines, spell checkers, plagiarism detection, and DNA or biosequence analysis where short, exact subcomponent matches are informative. Limitations include larger index sizes for small n, potential noise with very small n, and higher computational cost for long queries. Variants exist for word-level n-grams and for compressed or streaming implementations to improve efficiency.