Try fst to support fuzzy search

[mre]

https://github.com/BurntSushi/fst
https://blog.burntsushi.net/transducers/#common-crawl

Expect that this blows up the index size significantly, but it might be an alternative backend that could be enabled with a feature flag, e.g. tinysearch --engine=fst or so.
@BurntSushi, do you think that a corpus like that would compress nicely with fst? https://github.com/tinysearch/tinysearch/blob/master/fixtures/index.json
Think I'll play around with your sample code on the main repository when I find the time.

[BurntSushi]

Not sure I know how to answer that without more details on how you're building the index. "fuzzy search" can refer to many different things... I'd be happy to say more if you shared more of your plan. :-)

[mre]

Sure, sorry. Here's a writeup. It's basically using a bloom filter now but only full words can be searched. What I like to have is an optional, alternative engine that could provide prefix matches and "typo correction" (e.g. configurable Levenshtein). From what I can tell, all of this is supported by fst and it was recommended to me by two independent people, so I thought about giving it a try. My only concern is that the output size of the final (wasm) package, which contains the index will be too big for serving it directly to the clients.

[BurntSushi]

I guess what I meant was, what specifically would be the keys in your FST? I see your JSON file, but there are many different things there. Is it every word in the body field? Every 3-gram in the body field? And what are the values that your keys map to?

Either way, it's hard for me to say up front. Just think of an FST as a finite state machine. If there are a lot of common prefixes or suffixes, then an FST should be able to exploit that. I would, however, expect a bloom filter to give you more control over the size of your index. e.g., You can make trade offs like "give me a smaller filter perhaps at the expense of a higher false positive rate" more easily than you can with an FST.

But yes, if your FST keys are words, then you could use levenshtein to find all matching words within an edit distance of 1, for example. And that's a pretty easy and well supported thing you can do via the fst crate.

[mre]

Okay, I see. The body field gets sanitized by removing non-alphabetic characters and lowercasing every word. Right now, this is what gets ingested into the bloom filter. I'd like to try fst and a 3-gram of the sanitized body to begin with and see how the package size changes if we go from a 3-gram to a 4-gram for example.

From my prior tests, I found that there are indeed a lot of common prefixes (at least for the sample dataset from my blog). I didn't even consider suffixes, but potentially exploiting that would be really nice.

Seeing that it's not an entirely weird idea, I'll go ahead and give it a shot (or somebody else that might find the time). Will report back here.

[BurntSushi]

Great! Would love to hear how it goes and bounce more ideas around.

[mre]

Thanks for the quick response and the encouragement. Stay tuned for updates.