3 ms·
I first learned about Tries when I implemented a spell checker, almost 20 years ago now, with basic suggestions. It’s amazing how easy it is to get an efficient
by bitexploder 5y ago
I first learned about Tries when I implemented a spell checker, almost 20 years ago now, with basic suggestions. It’s amazing how easy it is to get an efficient, 80% spell checker and recommendation engine implemented from scratch once you dig into it. Tries make for an efficient enough in memory lookup structure (space, storage, and compute), and are an obvious part of a suggestion engine as well. Coupled with a basic soundex and some word mangling + edit distance checking and you have a very functional system. Solving the last 20% takes an order of magnitude more work :)
- fabiospampinato 5y agoI've learned recently that a trie can also be succinctly encoded, like encoded as a string that contains almost only the node values and ~nothing else. This way for some languages you can encode all the valid words of that language in less space that it would be needed for the Hunspell dictionary used to generate them. Plus you get instant start-up as the dictionary had already been processed at build time basically.