Typo tolerance: why one strategy is never enough
An optimal algorithm on 500 products becomes a bottleneck on 50,000, and the reverse is just as true. Here's why the right answer comes from measurement, never intuition.
A problem you can't see until you measure it
Tolerating a typo means comparing what the buyer typed against every known word in the catalog, to find the closest matches. On a small catalog, that work is trivial: a few hundred comparisons, no perceptible latency. On a large catalog, that same work, done naively, becomes the real bottleneck of the search. Not indexing, not ranking, just typo tolerance itself.
So the problem isn't the algorithm. It's whether it fits the actual size of what it has to process.
Two strategies, two opposite cost profiles
There are broadly two families of approach for tolerating typos across an entire vocabulary:
| Approach | Cost on a small vocabulary | Cost on a large vocabulary |
|---|---|---|
| Direct comparison, word by word | Negligible | Grows with vocabulary size: becomes the dominant factor |
| Pre-compiled automaton | Unnecessary build cost, for a gain you'd never notice | Near-constant, regardless of vocabulary size |
These two profiles are exact opposites. Using the automaton everywhere needlessly penalizes small catalogs with a build cost that buys nothing at that scale. Using direct comparison everywhere penalizes large catalogs with a slowness that's very much noticeable, and costs you abandoned searches.
Measure, don't guess
It's the same principle that led us to rule out vector search for Heurix: the right answer depends on what you actually have to process, never on a preference for a technique you happen to find elegant. We measured, on our own catalogs, the exact point where each approach becomes faster than the other. Not assumed, not extrapolated from some generic benchmark found elsewhere, which would have measured different hardware, a different vocabulary, and a different distribution of real-world typos.
That crossover point sits at several tens of thousands of distinct words in the catalog's vocabulary, an order of magnitude that most e-commerce catalogs, even large ones by product count, never reach in their own vocabulary (the number of distinct words, not the number of products, which largely repeat the same terms).
What this actually changes at Heurix
Below that threshold, Heurix compares directly: it's already instant, and building an automaton would cost more than it would ever save. Above it, the engine automatically switches to the pre-compiled automaton, which keeps response time near-constant even as the vocabulary keeps growing.
There's nothing to configure: the switch happens catalog by catalog, transparently, re-evaluated every time vocabulary size changes. It's the same logic behind the typo tolerance and explainable results already described on the features page: the engine picks its strategy based on measurement, never on a principle applied without checking it.
Going further
The same reasoning — measure before picking a tool, rather than generalizing a preference — is also what led us to rule out vector search on technical catalogs. The engine's principles are detailed on the homepage.