#community-help

Using Fuzzy Search in Typesense Search Algorithm

TLDR Gilbert asked about fuzzy search in typesense. It was clarified by Kishore Nallan that a trie data structure and levenshtein distance are used in the process. Harrison also contributed to the conversation.

Powered by Struct AI
+11
5
12mo
Solved
Join the chat
Oct 01, 2022 (12 months ago)
Gilbert
Photo of md5-0967abb5e5ad5a92810d6fd30ae1b7f7
Gilbert
04:39 PM
Hi, How fuzzy search works on the typesense search? I’ve read the article it uses damerau levenshtein distance, but I’ve check about the algorithm it just compare 2 strings and get the minimum distance between 2 strings. I’m curious how the algorithm works with the index data? I’m glad if u want to share, thanks.
Oct 02, 2022 (12 months ago)
Kishore Nallan
Photo of md5-4e872368b2b2668460205b409e95c2ea
Kishore Nallan
03:38 AM
We use a trie datastructure to store the words in the dataset. Then we compare the words in the query against trie and use that to get matching words.
Gilbert
Photo of md5-0967abb5e5ad5a92810d6fd30ae1b7f7
Gilbert
05:12 AM
I got it, thanks
Harrison
Photo of md5-43a35158b04c9c49110114370dbeae06
Harrison
02:35 PM
Interesting, so do you guys use levenshtein distance distance at all? Or is that computed as you go down the trie?
Oct 04, 2022 (12 months ago)
Kishore Nallan
Photo of md5-4e872368b2b2668460205b409e95c2ea
Kishore Nallan
02:37 AM
Computed during trie traversal.
+11