pyfuse : The Fuzzy Search Engine Python Never Had Case Study

Someone types stve hamilton into a search box. You have five thousand records sitting in a list. You want the right one back, ranked, with the matching bits highlighted.

That's it. That's the whole problem. And in Python it's weirdly annoying.

The gap

Python's fuzzy matching is fine when you're comparing two strings. rapidfuzz will happily tell you "stve" and "steve" are 89% similar, and it does it fast.

But that's not what I wanted. I wanted to search a collection. Which means:

Look at several fields per record — title, author, tags
Weight some of them higher than others, because a match in the title means more than a match in a footnote
Reach into nested data, like author.lastName
Rank everything by how good the match is
Tell me where it matched, so I can highlight it

None of that is string comparison. That's a small search engine.

Your options in Python are basically:

Write the ranking yourself. You'll get something working in an afternoon and spend the next two months discovering it ranks badly.
Stand up Elasticsearch. Now you operate a server, a schema, and an index lifecycle. For five thousand rows.

Both of those are silly for the size of the problem.

Meanwhile JavaScript has had exactly the right tool for years. It's called fuse.js, it's about 3,000 lines, it has zero dependencies, and it does precisely this.

So the capability isn't missing from computing. It's just sitting on the other side of a language boundary. And everything I work on is Python.

I decided to move it.

What the thing actually does

Before the porting story, a minute on how fuzzy search works, because it's neater than you'd think.

Matching with typos

The core is an algorithm called Bitap. The clever idea: instead of comparing characters one at a time, represent the state of the match as a number, and use bit operations to advance it.

You precompute a small map — for the pattern "abc", which positions does each letter live at? Then you slide through the text doing shifts and ANDs. When a particular bit lands in a particular place, you've found a match. Modern CPUs do 64 bit-operations in the time they'd do one string comparison, so this is fast.

To tolerate typos you keep several of these numbers at once: one for "matched perfectly", one for "matched with one mistake", one for "two mistakes", and so on.

Turning a match into a score

A match on its own isn't enough — you need to rank. fuse.js multiplies three things together:

How close the match was. How many typos, and how far from where you expected the match to be.
How important the field is. The weight you gave that key.
How long the field is. Matching "Steve" in a two-word name means more than matching it in a 400-word bio. This is the field-length norm, and it's literally 1 / sqrt(number of words).

Lower is better: 0.0 is perfect, 1.0 is unrelated.

That's the engine. Plus query operators (=exact, ^prefix, !not), $and / $or composition, and an alternative mode that ranks by word rarity instead of character matching.

Porting is the easy half

Here's the thing nobody tells you: translating the code is the boring part. TypeScript and Python are close enough that most of it is mechanical. A couple of days of careful work.

The hard part is the question that comes after:

How do I know it's right?

Because "I wrote a fuzzy search library" is worth almost nothing on its own. I could ship something that returns plausible results, and plausible-but-wrong is the worst outcome in search — nobody notices. The rankings are just quietly bad forever.

I had one enormous advantage, though, and it's the reason porting beats writing from scratch:

The original still exists, and it works. A decade of bug reports and fixes are baked into it. That makes it an oracle — something I can ask "what's the right answer?" as many times as I like.

So the project stopped being "write a search library" and became "prove two programs are the same program." Much more interesting.

I attacked it two ways.

Idea 1: run the original's tests against my code

fuse.js has a big test suite. Nearly 300 tests. It's JavaScript, run by vitest. My port is Python. Those two facts seem to rule each other out.

Then I noticed something. Every one of the thirteen behavioural test files starts the same way:

import Fuse from '../dist/fuse.mjs'

One import. Thirteen files. The tests never care what's behind that path. They just call search() and check what comes back.

So: don't touch the tests. Move what that path points at.

vitest lets you alias a module. I pointed it at a small shim that presents the same API and forwards every call into Python. The test files stay byte-for-byte identical — I never edited a character — and they now exercise the Python implementation without knowing it.

The bit that cost me an evening

The tests do this:

const result = fuse.search('old man')   // no await
expect(result.length).toBe(1)

No await. It's synchronous. Adding one would mean editing the tests, which defeats the whole point.

So my bridge had to block — send a request to Python and freeze until the answer arrives. Node really doesn't want you to do that. Its pipes are non-blocking and it won't hand you a raw file descriptor to wait on.

The way through is a trick borrowed from multithreading:

The main thread hands the request to a worker thread and then calls Atomics.wait() on a chunk of shared memory. That genuinely parks it.
The worker does the slow I/O the normal async way, which Node is happy with.
When the reply lands, the worker writes a 1 into that shared memory and pings it.
The main thread wakes up and returns the answer.

From the test's point of view, search() was synchronous. It never finds out that a Python process across an operating-system pipe did the work.

Result: 285 of 297 tests pass, with the test files untouched.

The twelve failures are all accounted for, and none is a bug in my code. Ten of them hand fuse.js a JavaScript function — a custom sort, a custom tokenizer. A function is a closure over a live JavaScript heap. You cannot serialise that and rebuild it in Python; it's not a limitation I can engineer around, it's a fact about language boundaries. The other two are places where I deliberately chose to differ, and wrote down why.

I made the bridge refuse those calls loudly instead of quietly substituting a default. A default would have turned twelve failures into twelve passes for completely the wrong reason. Green tests that lie are worse than red ones.

Idea 2: make them fight

Passing someone's test suite proves you handle the cases they thought of.

I wanted the cases nobody thought of.

So I built a fuzzer. It generates random datasets, random queries, and random option combinations, feeds the identical input to both engines, and compares the output field by field:

Same documents returned?
In the same order?
Same relevance scores?
Same highlight positions?

Then it runs that a few thousand times a second.

The first version was slow because I was starting a new Node process per test. Keeping one long-lived process and streaming JSON at it took it to about 859 cases a second.

60-second run: 51,569 cases. Zero structural divergences.

Same documents, same order, same match positions, every time.

The two bugs it caught

Both were mine, both were invisible, and both produced plausible wrong answers — exactly the failure mode I was worried about.

The loop that moves its own finish line

The original JavaScript looks roughly like:

for (let j = finish; j >= start; j -= 1) {
  // ...
  if (someCondition) {
    start = Math.max(1, 2 * location - bestLocation)   // ← changes the bound
  }
}

Look at that last line. The loop modifies its own lower bound while running, and JavaScript re-checks j >= start every single iteration, so the change takes effect immediately.

The natural Python translation is:

for j in range(finish, start - 1, -1):

which is wrong, and quietly so. Python's range() computes its bounds once, up front. Reassigning start inside the loop does nothing at all.

The fix is an explicit while. The bug's fingerprint was tiny — a slightly different score on some inputs — and there is no chance I'd have found it by reading. The fuzzer found it in seconds.

An empty list that isn't empty

In JavaScript, [] is truthy. In Python, [] is falsy.

The query parser leans on this. fuse.js treats {"$or": []} as a valid empty group. My port looked at [], decided it was falsy, took a completely different branch, and rejected the query as malformed.

One character of difference in how two languages feel about emptiness.

The wall: two computers disagree about arithmetic

This is my favourite part, so bear with me.

Scores came out almost identical. Same to about fifteen decimal places, then a disagreement in the last digit.

Both languages use the same 64-bit floating-point format. Same standard, same hardware. So where's the difference?

pow — raising a number to a power.

That sounds like it should have one answer. It doesn't, quite. Computing x**y for arbitrary decimals requires approximation, and different implementations approximate differently:

pow(0.1, 0.3846666666666666)

CPython : 0.4124139370464501     ← correctly rounded
V8      : 0.41241393704645002    ← off by one, in the last digit

I sampled 5,000 random pairs in the range my scorer actually uses: they disagree 10% of the time. Always by the smallest amount a float can express — one ULP, "unit in the last place." The next representable number along.

Here's the twist: Python is the correct one. CPython gives you the exact answer rounded properly. V8 uses an older, faster approximation inherited from a 1990s math library.

So to match fuse.js exactly, I'd have to make Python less accurate on purpose.

I tried. I transcribed V8's algorithm into Python — about 200 lines, 23 magic constants each verified bit by bit against the published originals. Got it to 95.6% agreement, up from 90%.

Then I stopped, and the reason matters more than the number.

The remaining 4.4% of mismatches were spread evenly across every branch of the algorithm — 3.5% here, 5.8% there. If I'd made a transcription mistake, the errors would clump in one branch. Even spread means the algorithm is right and my target is wrong: V8 isn't running textbook fdlibm, it's running its own variant.

Closing the gap meant reverse-engineering a JavaScript engine with nothing to diff against. Unbounded work, uncertain payoff, for a cosmetic last digit.

I shipped it as an off-by-default option instead. It's also 1,639× slower per call, and less accurate. It's a debugging tool, not a feature.

Final claim: structure matches exactly, scores agree to about 1e-13.

The part where the fuzzer proved me wrong

I'd written in my notes, early on, something reassuring:

The float difference only shows up in the last digits. It never changes the actual output.

That felt obviously true. A difference that small couldn't reorder anything.

It's wrong.

Think about what happens when two documents score exactly the same. There's a tie-break rule — original position wins. Now make one score differ by one ULP. They're no longer tied, so the tie-break never fires, and the two engines return the same documents in a different order.

If you asked for the top 3, a different document can make the cut.

It happens in 8 of 51,569 cases. 0.016%. Rare, real, and I'd have shipped the claim that it never happens.

The fuzzer caught me. Not a reviewer, not a user — a program I'd written specifically to disagree with me.

I gave it its own category in the log and corrected the claim in the docs instead of quietly deleting it. That's the whole argument for building the harness, honestly: it's the only part of the project with no ego in it.

It's slower, and I'm not going to dress that up

fuse.js is about 13× faster.

Expected. V8 compiles that inner loop to machine code. CPython interprets it instruction by instruction, and it's bit-twiddling in a tight loop — close to the worst case for an interpreter. I also added a masking operation per iteration to emulate JavaScript's 32-bit integer behaviour, which doesn't help.

I could close most of that gap with a C extension. That would also mean compilers, wheels per platform, and the end of "it just installs anywhere," which was the entire point.

So it's slower. It uses about 40% less memory, which is a nice consolation and not the thing anyone's optimising for. The full methodology is in the repo so you can check the numbers rather than take my word.

An honest regression is worth more than a benchmark you cherry-picked.

What I'd tell you if you're porting something

Find your oracle. If the original still runs, you have a machine that answers "what's correct?" on demand. That is an enormous advantage and most ports don't use it.

Look for the seam. I got the original test suite running against Python because every test imported the engine from one path. One well-placed redirect did what translating 297 tests would have done, with none of the risk that I'd mistranslate a test into passing.

Fuzz it, don't just test it. Example tests check the cases you imagined. Both real bugs I found lived outside that set.

Write down what you chose not to match. I have twenty entries explaining deliberate differences. Each one is a decision that would otherwise look like a bug to the next person — including future me.

Let the tools contradict you. The single most valuable thing that happened was a program I built proving a claim I'd already written down was false.

Try it

pip install pyfusejs

from pyfuse import Fuse

books = [
    {"title": "Old Man's War", "author": "John Scalzi"},
    {"title": "The Lock Artist", "author": "Steve Hamilton"},
]

fuse = Fuse(books, {"keys": ["title", "author"], "include_score": True})
for hit in fuse.search("stve hamilton"):
    print(hit.item["title"], hit.score)

Zero dependencies. Python 3.10+.

There's also a live demo that runs the real package in your browser — Python compiled to WebAssembly — and diffs it against fuse.js side by side while you type. You can watch the two engines agree, or catch them disagreeing, without installing anything.

Code: github.com/ayanbag/pyfuse

pyfuse : The Fuzzy Search Engine Python Never Had