Skip to content
← All posts
6 min read Dawid Skłodowski

A fuzzy full-text matching service in Ruby

Users misspell things, and exact matching fails them silently. A practical deep-dive into trigram-based fuzzy matching in Ruby — how it works, how to make it fast, and when to push it into Postgres instead.

Here is a problem that looks trivial until you ship it: a user types “Manchestr” into a city field, your WHERE name = ? returns nothing, and they conclude your product is broken. Exact matching is binary and unforgiving — it has no concept of “close”. Real input is full of typos, transpositions, missing letters, and alternate spellings, and a search that only understands exact equality fails all of them silently.

What you want is fuzzy matching: given a query, return the candidates that are close to it, ranked by how close. We have built this a few times, and the trigram-based approach is the one that keeps winning — it is simple, fast enough for interactive use, and easy to reason about. Here is how it works and how to build it in Ruby.

Why not edit distance?

The textbook answer to “how similar are two strings” is Levenshtein distance: the number of single-character insertions, deletions, or substitutions to turn one into the other. “Manchestr” → “Manchester” is distance 1. It is intuitive and accurate, and it has one fatal flaw at scale: computing it is O(n·m) per pair, and to find the best match in a list of a million city names you would compute it a million times per query. Edit distance is a great way to rank a handful of pre-filtered candidates; it is a terrible way to find them in a large set.

We need a method that can cheaply reduce a million candidates to a few dozen, and then we can rank those few with something precise. Trigrams are that method.

Trigrams: turning fuzziness into set overlap

A trigram is a run of three consecutive characters. Decompose a string into its set of trigrams (padding the ends so short strings and word boundaries behave):

def trigrams(string)
  s = "  #{string.downcase.gsub(/[^a-z0-9]/, ' ')} "
  (0..s.length - 3).map { |i| s[i, 3] }.uniq
end

trigrams("Manchester")
# => ["  m", " ma", "man", "anc", "nch", "che", "hes", "est", "ste", "ter", "er "]

The trick is what this buys you: two strings that are similar share most of their trigrams, and a typo only disturbs the two or three trigrams around the changed character. “Manchestr” and “Manchester” share almost every trigram, so their similarity — the size of the intersection over the size of the union (the Jaccard index) — is high:

def similarity(a, b)
  ta, tb = trigrams(a), trigrams(b)
  (ta & tb).size.to_f / (ta | tb).size
end

similarity("Manchestr", "Manchester")  # => ~0.8
similarity("Manchester", "Liverpool")  # => ~0.0

Fuzziness has become set overlap, and set overlap is something we can index.

The inverted index: finding candidates fast

The key insight that makes this fast is that we never compare the query against every record. Instead we build an inverted index from each trigram to the list of records containing it — exactly how a search engine maps words to documents:

# trigram => [record_id, record_id, ...]
index = Hash.new { |h, k| h[k] = [] }

cities.each do |city|
  trigrams(city.name).each { |tri| index[tri] << city.id }
end

Now a query is answered by looking up only the trigrams the query contains, gathering the records that share any of them, and counting how many each shares:

def search(query, index, limit: 20)
  counts = Hash.new(0)
  trigrams(query).each do |tri|
    index[tri].each { |id| counts[id] += 1 }
  end
  counts.sort_by { |_id, n| -n }.first(limit)
end

A record that shares ten trigrams with the query ranks above one that shares two. Crucially, records that share nothing with the query never get touched — we only ever visit the (usually small) candidate set reachable through the query’s own trigrams. That is the difference between scanning a million rows and scanning a few hundred.

Ranking: cheap filter, precise sort

The two-stage pattern is what makes the whole thing both fast and accurate:

  1. Filter with the trigram index — cheap, set-based, reduces a million to a few dozen.
  2. Rank that short list with a precise measure — the Jaccard similarity above, or Levenshtein if you want true edit distance — which you can now afford because the list is tiny.
def fuzzy_find(query, index, records_by_id, limit: 10)
  candidate_ids = search(query, index, limit: 100).map(&:first)
  candidate_ids
    .map     { |id| records_by_id[id] }
    .sort_by { |rec| -similarity(query, rec.name) }
    .first(limit)
end

This is the architecture behind libraries like blurrily and behind Postgres’s own trigram matching: a fast trigram pre-filter feeding a precise re-rank. Once you see the pattern you see it everywhere in search.

Making it production-ready

A toy in-memory hash works for thousands of records; a real service needs a few more things:

  • Normalisation matters more than the algorithm. Downcase, strip punctuation, collapse whitespace, fold accents (café → cafe), and consider transliterating to ASCII. A consistent normaliser applied to both the indexed text and the query removes a whole class of “why didn’t this match” bugs before trigrams even get involved.
  • A similarity threshold stops you returning nonsense. Below ~0.3, a “match” is usually noise; return nothing and let the UI say so, rather than confidently offering “Liverpool” for “xyzzy”.
  • Persistence and memory. An in-memory index is fast but must be rebuilt on boot and kept in sync on writes. blurrily solves this with a compact on-disk trigram index built in C for speed; the alternative, below, is to let the database own it.

When to let Postgres do it: pg_trgm

Before you build and operate a separate matching service, check whether your database can already do this — because in many cases it can. PostgreSQL’s pg_trgm extension implements exactly this trigram model, with a GiST or GIN index to make it fast:

CREATE EXTENSION pg_trgm;
CREATE INDEX index_cities_on_name_trgm
  ON cities USING gin (name gin_trgm_ops);

-- similarity-ranked fuzzy search, indexed:
SELECT name, similarity(name, 'Manchestr') AS sim
FROM cities
WHERE name % 'Manchestr'           -- the % operator: "similar enough"
ORDER BY sim DESC
LIMIT 10;

The % operator filters by a configurable similarity threshold and the index makes it quick, while similarity() gives you the score to sort by. For the very common case — fuzzy-matching a column you already store in Postgres — this is the right answer: no extra service to deploy, keep, and keep in sync; the data and the index live together; and writes update the index automatically. We reach for a dedicated Ruby/blurrily service only when the matching set is not in Postgres, or when we need the index detached from the primary database for scale or latency reasons.

The takeaway

Fuzzy matching feels like it should be hard, and the naive approach (compare the query to everything with edit distance) genuinely is too slow to be usable. The trigram trick reframes the problem: turn strings into sets, use an inverted index to find overlapping candidates cheaply, and re-rank the short list precisely. Build it in Ruby when you must, but reach for pg_trgm first — most of the time the database you already run will do the whole job, indexed and in sync, for the price of one CREATE EXTENSION.

#ruby #postgresql #search