ngramindekser

ngramindekser (often translated as n-gram indexer) is a data structure and set of algorithms used to build an index of n-grams—contiguous sequences of n items—from a collection of text. The index maps each n-gram to the documents in which it appears, typically including positional information to support more complex queries. This enables efficient substring search and, with additional scoring, approximate matching.

Two main flavors exist: character-level n-grams and word-level n-grams. Character n-grams are derived from the raw text by sliding a window of size n over characters, which helps with substring queries and languages with rich morphology. Word-level n-grams are formed from sequences of adjacent words and are useful for phrase and near-phrase matching. The choice of n affects recall and precision and often depends on the application.

Construction and querying usually follow a similar workflow. Text is normalized (lowercased, diacritics handled) and tokenized into either characters or words before generating all n-grams. Each n-gram is inserted into an inverted index with postings that reference document IDs (and sometimes positions). To answer a query, the query string is processed into n-grams, posting lists are retrieved and intersected to produce candidate documents, which may then be ranked by coverage or other similarity metrics and optionally validated with an exact substring check.

Typical applications include full-text search with fuzzy matching, autocomplete, spell checking, and plagiarism detection. Key considerations are the choice of n, index size, update vs. batch indexing, and how positions are stored to support phrase and proximity queries.