fuzzysearch: subsequence matching and relevance ranking in Go

Subsequence matching, not edit distance matching

Fuzzy searching allows flexibly matching a string with partial input, which is useful for filtering data very quickly based on lightweight user input. The matching rule is the part that trips people up, and the documentation's own examples define it precisely. Against cartwheel, the inputs twl, cart, cw, ee and art all match, while eeel does not, and dog does not. The pattern is a subsequence: the characters have to appear in the target in order, but not next to each other, and every character of the pattern must be consumed. That is a different rule from the one a spell checker uses. The clearest demonstration is the pair kitten and sitting, which the documentation shows as false, even though those two words are one edit apart. If you want the edit distance behaviour, this library is not the tool for it, and the fact that the library also does Levenshtein ranking makes the distinction easy to miss when you read the API list.

The four functions you will actually call

The public surface is four functions plus two variants. Match answers a yes or no question about a pattern and a target. RankMatch does the same match but returns a number instead, the rank or distance value, and it returns -1 when there is no match at all. Find applies a pattern across a list of words and returns the ones that match. RankFind does that and returns records instead of plain strings, each record holding the pattern, the matched word, a distance value and an index, so that you can order the results. The whole thing fits in one import:

package main

import "github.com/lithammer/fuzzysearch/fuzzy"

func main() {
	fuzzy.Match("twl", "cartwheel")  // true
	fuzzy.Match("cart", "cartwheel") // true
	fuzzy.Match("cw", "cartwheel")   // true
	fuzzy.Match("ee", "cartwheel")   // true
	fuzzy.Match("art", "cartwheel")  // true
	fuzzy.Match("eeel", "cartwheel") // false
	fuzzy.Match("dog", "cartwheel")  // false
	fuzzy.Match("kitten", "sitting") // false

That is the whole mental model. A pattern goes in, a boolean or a number comes out, and a list variant returns either strings or sortable records.

Ranking turns a list of matches into an order

Ranking uses Levenshtein distance, and it is the extra the library has over the JavaScript project that inspired it. The distance measures how many single character edits separate the pattern from the candidate, and the lower the number the closer the match, so a distance of 0 is an exact match and a large number means the match was loose. In the documentation's example, searching whl over the list cartwheel, foobar, wheel and baz, RankFind returns a record for cartwheel with the values 6 and 0, and a record for wheel with the values 2 and 2, where the second number is the record's position in the input list. The results come back in input order, so passing them to the standard library's sort makes ordering a one-liner:

matches := fuzzy.RankFind("whl", words) // [{whl cartwheel 6 0} {whl wheel 2 2}]
sort.Sort(matches) // [{whl wheel 2 2} {whl cartwheel 6 0}]

The effect is that wheel, which is two edits from the pattern, outranks cartwheel, which is six. That ordering is what makes a fuzzy finder feel right, and it takes one sort call on the records.

Two variants for accents and case

Two additional functions exist for the two cases where a plain byte comparison gives the wrong answer. MatchNormalized does Unicode normalized matching, and the example shows cartwheel matching cartwhéél, so a word with combining marks on the vowels still matches the unaccented pattern once the two are normalized to the same form. MatchFold does case insensitive matching, with ArTeeL matching cartwheel. Neither is the default, which is the right call for a library this small: a fuzzy matcher that silently folded case would surprise anyone who wanted a case sensitive filter, and the cost of two extra entry points is zero. The distinction between the two is also worth keeping straight in your own code, because case folding and normalization are different operations and a user who types a name without accents and a user who types it in capitals are two different problems.

Where the algorithm comes from

The lineage explains the design. The library was inspired by bevacqua/fuzzysearch, a fuzzy matching library written in JavaScript, and the readme credits it as the starting point, adding the extras of ranking by Levenshtein distance and finding matches in a list of words. The current implementation uses the algorithm suggested by Mr. Aleph, described as a Russian compiler engineer working at V8. That detail is more than a credit. A subsequence matcher written naively is quadratic in the length of the input, because for every character of the pattern you may walk the whole target, and in a fuzzy finder that runs on every keystroke over a list of thousands of items the cost is visible. An algorithm proposed by someone who works on a JavaScript engine is an algorithm that was written with the cost model of an interactive text field in mind, and the library's claim of being tiny and fast rests on it.

One dependency, a stable API, and a long gap between releases

The dependency list is one line, and the install is one command:

go get github.com/lithammer/fuzzysearch/fuzzy

The module is github.com/lithammer/fuzzysearch, it declares Go 1.26.0, and it requires golang.org/x/text at version 0.42.0, which is where the Unicode normalisation used by MatchNormalized comes from. That is the whole cost of adopting it, one well known module, and the tree is a single fuzzy directory with a go.mod and a go.sum. The release history is the thing to look at carefully. The tagged versions are v1.1.6 in April 2023, v1.1.7 in May 2023 and v1.1.8 on 2023-05-15, and the last push was on 2026-10-01, so the repository has been touched much more recently than the newest tag. A library whose public API has not moved in three years is either finished or abandoned, and in this case the push dates and the documentation on pkg.go.dev suggest a maintained but slow moving project. The licence is MIT, and the package documentation is where the fuller set of examples lives.

Editorial conclusion

The library is worth a dependency in a command line tool, a file picker or a filter box, because the algorithm is the same one that powers fuzzy finders people already understand, and the ranking functions give you a sensible order for free. It is the wrong choice if you want edit distance matching, since the example in the documentation shows kitten against sitting returning false, and it is the wrong choice if you need language specific transliteration. Before you adopt it, check the release history against the version you would pull, since the newest tag is from 2023 while the repository has been pushed to more recently, and read the package documentation on pkg.go.dev for the record types.

Frequently asked questions

Official sources

1. License: MIT
2. lithammer/fuzzysearch on GitHub
3. Project website
4. README
5. Releases