The Trigram Algorithm: Fuzzy Matching Without the Magic

#algorithms#databases#sql#python

A trigram is just three consecutive characters, and comparing the sets of trigrams of two strings gives you a fast, typo-tolerant similarity score between 0 and 1. It is the idea behind PostgreSQL's pg_trgm, and it fits in about thirty lines of Python. This post builds it from scratch, shows why it works well for search-as-you-type, and then maps it onto what Postgres does for you.

The core idea

Take a word, pad it, and slide a window of three characters across it. For cat, with two spaces in front and one behind, you get:

sorted(trigrams("cat"))
# ['  c', ' ca', 'at ', 'cat']

The padding matters. It makes the start and the end of a word count as features of their own: c only appears in words that begin with c, and at only in words that end in at. Without padding, the first and last letters of a word would appear in fewer trigrams than the letters in the middle.

To compare two strings, compute both trigram sets and take the ratio of what they share to what they have in total. This is the Jaccard index:

similarity(a, b) = |T(a) ∩ T(b)| / |T(a) ∪ T(b)|

Identical strings score 1.0, strings with no trigram in common score 0.0, and everything else lands in between.

A working implementation

Here is the whole thing, written in the style of pg_trgm: lowercase the input, split it into alphanumeric words, pad each word, and collect the trigrams of all words into one set.

import re

def trigrams(text):
    grams = set()
    for word in re.findall(r"[a-z0-9]+", text.lower()):
        padded = f"  {word} "
        grams.update(padded[i:i + 3] for i in range(len(padded) - 2))
    return grams

def similarity(a, b):
    ta, tb = trigrams(a), trigrams(b)
    if not ta or not tb:
        return 0.0
    return len(ta & tb) / len(ta | tb)

This version only recognizes ASCII letters and digits to keep it short. A real implementation has to decide what counts as a word character for umlauts and other scripts.

Some results from running it:

similarity("word", "two words")      # 0.3636
similarity("Kartoffel", "Kartofel")  # 0.7273
similarity("postgres", "postgresql") # 0.6667
similarity("postgres", "progress")   # 0.2

The first number matches the example in the PostgreSQL documentation for similarity('word', 'two words'), which is a useful sanity check that the padding rules are right.

The last two lines show the interesting part. postgres and postgresql are clearly related, and they score 0.67. postgres and progress use almost the same letters but in a different order, and they score only 0.2. A plain character-frequency comparison would call those two close. Trigrams capture local order, and that is exactly what makes them useful for names and words.

Why three?

The length of the window is a trade-off:

With bigrams (two characters), almost every pair of words shares something, so scores get noisy and the candidate lists get long.
With trigrams, the features are specific enough to discriminate, and a single typo only damages a few of them.
With four or more characters, short words produce very few features, and a typo destroys a larger share of the set.

A single wrong letter in the middle of a word breaks at most three trigrams, because only three windows cover that position. A longer word therefore survives a typo with most of its trigrams intact. That is why Kartofel still scores 0.73 against Kartoffel, even though one letter is missing.

Trigrams are not an edit-distance algorithm. They do not tell you how many operations separate two strings, and they work worst on very short strings, where there are hardly any features to compare. Their strength is something else: the trigram sets can be indexed.

Making it fast with an inverted index

Comparing a query against every row works for a few hundred entries and falls over for millions. The trick is to treat each trigram as a key in an inverted index that points to the entries containing it. A query then only has to look at entries that share at least one trigram with it:

from collections import defaultdict

class TrigramIndex:
    def __init__(self, items):
        self.items = list(items)
        self.grams = [trigrams(x) for x in self.items]
        self.postings = defaultdict(set)
        for i, g in enumerate(self.grams):
            for t in g:
                self.postings[t].add(i)

    def search(self, query, threshold=0.3):
        q = trigrams(query)
        candidates = set()
        for t in q:
            candidates |= self.postings.get(t, set())
        hits = []
        for i in candidates:
            g = self.grams[i]
            score = len(q & g) / len(q | g)
            if score >= threshold:
                hits.append((score, self.items[i]))
        return sorted(hits, reverse=True)

The index narrows the field cheaply, and the exact score only gets computed for the candidates. Try it on a small list of database names:

idx = TrigramIndex(["PostgreSQL", "MySQL", "MariaDB", "SQLite",
                    "Postgres-XL", "Redis", "MongoDB"])

idx.search("postgre")
# [(0.583, 'PostgreSQL'), (0.538, 'Postgres-XL')]

idx.search("postgress")
# [(0.615, 'PostgreSQL'), (0.571, 'Postgres-XL')]

Both the truncated postgre and the misspelled postgress find the right entries, and MySQL and SQLite stay out even though they share the letters sql with PostgreSQL. The threshold of 0.3 is the same default that pg_trgm uses.

The same thing in PostgreSQL

You do not need to build this yourself in a database. The pg_trgm extension ships with the standard contrib modules:

CREATE EXTENSION IF NOT EXISTS pg_trgm;

SELECT similarity('Kartoffel', 'Kartofel');
SELECT show_trgm('cat');

show_trgm returns the trigram set, and similarity the score, so you can check your own implementation against it. The % operator is true when the score is above the current threshold (pg_trgm.similarity_threshold, 0.3 by default), and <-> returns the distance, which is 1 minus the similarity:

CREATE TABLE products (id serial PRIMARY KEY, name text NOT NULL);

CREATE INDEX products_name_trgm_idx
  ON products USING gin (name gin_trgm_ops);

SELECT name, similarity(name, 'postgress') AS score
FROM products
WHERE name % 'postgress'
ORDER BY score DESC
LIMIT 10;

The GIN index is the inverted index from the Python example, maintained by the database. A bonus is that the same index also speeds up LIKE '%term%' and ILIKE queries, which normally force a sequential scan because a B-tree cannot help with a leading wildcard. If you mostly need nearest-neighbor ordering with ORDER BY name <-> 'postgress', a GiST index with gist_trgm_ops is the better fit.

When to use it, and when not

Trigram matching is a good fit for:

search-as-you-type on names, titles and product lists
typo-tolerant lookups, such as matching a user's input against a list of cities
finding likely duplicates in a table of customer or company names

It is a poor fit for:

very short strings, where one or two characters decide the whole score
semantic search, since car and automobile have no trigrams in common
long documents, where full-text search with stemming and ranking does a better job

Takeaways

The trigram algorithm turns fuzzy string matching into set arithmetic. Pad the words, cut them into three-character windows, and compare the sets with Jaccard. Because the sets can be put in an inverted index, the same idea scales from a Python list to a table with millions of rows. If you already run PostgreSQL, enable pg_trgm and add a GIN index before you reach for a separate search service.