C++: Fuzzy Search with Trie

For a school project, I had to make a part of a spell-check program. Given a dictionnary of words, you have to determine all the words that are within K mistakes of the original word.

Trie

As input, we've got a list of words along with their frequency. For example, with the following list, we are going to build a trie.

do     100 000
dont    15 000
done     5 000
donald     400

In order to minimize the memory footprint, I've made a node structure that fits into 32 bits.

struct {
	unsigned short is_link : 1;
	unsigned short is_last_child : 1;
	union content {
		struct {
			unsigned short letter : 6; // 2^6  = 64 different charaters
			unsigned int next : 24;    // 2^24 = 16 777 216 nodes
		} link;
		struct {
			unsigned short is_overflow : 1;
			unsigned int freq : 29;    // 2^29 = 536 870 912
		} final;
	}
} node;

The frequence can be greater than 2^30. We're going to store values between 0 and 2^29 directly inside the node, and if it doesn't fit, we are going to retrieve the value in a separate memory location and store its corresponding id.

Damerau Levenshtein Distance

The distance between two words we use is Damerau Levenshtein. In order to calculate the distance, we compute the following table.

Where each slot D(i,j) is calculated using the following formula:

There are two things to tweak in order to use this distance with a trie.

Incremental computation

Obviously, we are not going to recompute the whole distance for each node. We can use one table for the whole search. For each node you explore, you are going to compute only the line corresponding to it's depth in the tree. For example, if you look for elephant and are currently at rel in the tree, you are only going to compute the 3rd row. The first two rows r and e are correct.

When to stop?

Now we need to find given a current table, when to stop. For example, if we search for elephant with 1 error and we are at zz, we can stop, there won't be any word that satisfy the request. I've found out that if the minimum value of the current row is bigger than the number of tolerated errors, we can stop the search. When searching for elephant with 1 error, we stop at the 4th row (rele) because the minimum is 2.

Heuristics

When we traverse the trie in a fuzzy way, we explore a lot of useless nodes. For example, when we fuzzy search for eve, we are going to explore the beginning of the word evening. Let's see some strategies to reduce the amount of nodes we explore.

Different trie per word length

Fuzzy search for the 5-letter word like happy with 1 error, you know that your results are going to be words of length 4, 5 or 6. In a generalized way, you are only going to look for words in the range [len - error; len + error]. You can create a trie for each length. Then you search in all the required tries and aggregate the results.

The downside with this approach is that you lose the high prefix compression of the trie.

Word length

Instead of making on trie per word length, you can encode the word lengths directly in the nodes. Each node is going to have a bitfield containing the lengths of the words in the sub-tree. For example in the example above, the first node leads to words of size 2, 4 and 6, therefore the field will have 0b010101....

If you are looking for a word of size 5 with 1 error, you are going to create a bitfield of word lengths you are interested in 0b000111.... For each node, you and both bitfields, if the result is not 0, then you've got a potential match.

Conclusion

In order to test for performance we search every word at a distance 2 of the 400 most popular english words. The dictionnary contains 3 millions words. It takes 22 seconds on my old 2Ghz server to run it. It takes an average of 55ms per fuzzy search and generates an average of 247 results.

Felix Abecassis, a friend of mine spent time working on parallelizing the search with Intel TBB. You might want to read it in order to improve by a factor your performance 🙂

Since it's a competitive school project, I'm not going to give the source publicly. Please ask them if you are interested 🙂

If you liked this article, you might be interested in my Twitter feed as well.
 
 

Related Posts

  • September 25, 2011 Javascript Object Difference (5)
    This article is about a difference algorithm. It extracts changes from one version of an object to another. It helps storing a smaller amount of information. Template In a project, I have a template object with all the default settings for a widget. var template = { […]
  • December 7, 2011 Automatic Links with Trie (0)
    On MMO-Champion, we often paste World of Warcraft patch notes taken from Blizzard. The main problem is that it's plain text. We want to be able to add links to all the spells, quests, zones ... This way people can mouseover and see the description. It helps figuring out what […]
  • September 24, 2011 Javascript: Cyclic Object Detection (15)
    URLON.stringify() suffer from a problem, when passed an object that contains a cycle, it will never stop. This article shows 3 techniques in order to detect if an object is cyclical. Edit the object: Mark In order to detect a cycle in an object, the method we learn at school is to […]
  • April 29, 2014 Simulate Closure in C (4)
    I'm implementing a layout algorithm in C and want to let the user specify a callback to compute the height based on the width. Using function pointers, we can provide the callback: typedef struct { float (*measure)(float width); } layout_node_t; void layout(layout_node_t […]
  • August 23, 2011 Javascript – Hook Technique (7)
    Let's go back 5 years ago during the World of Warcraft beta. I was working on Cosmos UI, a projects that aimed to improve the World of Warcraft interface. As interface modification was not officially supported by Blizzard, we went ahead and directly modify the game files written in […]