Character trigram search improves full-text matching by indexing overlapping three-character pieces of words. Unlike an exact word index, it can connect a query such as “cat” with documents containing “cats,” while avoiding a scan of every document. section 10.3.1 section 3.6.2
The technique fits into an inverted-index workflow:
- Store each trigram alongside the documents and positions where it occurs, much like a textbook index stores words with page numbers. section 3.6.2
- Use the index to narrow matching documents instead of reading every document sequentially; specialized full-text indexes can provide constant-time search performance for supported operations. section 10.3.1 section 3.6.2
- Rely on established search software rather than implementing the index from scratch; Whoosh, Apache Lucene, Elasticsearch, Solr, OpenSearch, Meilisearch, and Typesense are named options. section 10.3.1 section 3.6.2
Where character matching stops
A query requesting an algorithm with high precision and recall that “can’t be slow” may match documents containing “slow algorithm” and “low precision,” even though the intended meaning reverses those relationships. Character trigrams tolerate spelling variation, but they do not understand token order or semantics. section 10.3.2
