JavaScript Trie Performance Analysis
ejohn.org
ejohn.org
A way to make the plain string search faster would be to use binary search. It is possible to do it on a space separated string by jumping at a generic position of the string (which could be in the middle of a word) and going back to the rightmost space preceding the position. It is easy to see that the algorithm is correct and if the words have bounded length the runtime is still O(log n).
BTW, by using a fair amount of succinct data structures and bit tricks it is possible to do way better than this: a succinct (binary) representation of the trie can use around 3 bits per node, and the labels can be compressed to 5-6 bits per label. However I would not implement that in JS :)
Isn't that premature optimization, though? As I noted in my post - lookups, even in the worst case, take less than a millisecond. Presumably someone could do that if they wanted even faster lookup performance, although I don't need it in this case.
I definitely agree that a binary representation would probably get us pretty close to an ideal form - although I'm (as you are) skeptical that it could be done in a performant way in JavaScript.
Yes of course it is, I should have started the sentence with "if performance becomes a concern". Since in the post you say "if you were building a game that required multitudes of dictionary lookups you might want to go with a faster hash or Trie technique" I just wanted to point out that binary search would probably work fine as well, without the huge memory increase.
There is a slight chance of false positives, depending on how you choose your parameters, but it's a very compact way to store a set of strings.
To make the initial parsing fast, but retain easy lookup I would store the bit vector in an ascii string, 6 bits per character, adding 32 to the raw value to get the character.
The wikipedia article can guide you on the parameters needed to get an acceptable error rate and size.
Would there be some more enlightened way of computing such a list than just crunching through every combination of letters up to length n? That is to say, could one devise a bloom filter with hash functions such that given the configured filter, a list of all possible matching elements could be produced?
What I'm wondering, though, is if one could select a hashing function where the collisions were easily discoverable. For a "hash" function that's just m mod 8, the presence of a 1 bit means that you had to have had an input that was either 1, 9, 17, 25, 37, etc, up to the maximum word length. This may be a problem that's just as hard or harder than the rainbow table approach, but I'd be interested to explore its feasibility.
(On the other hand, it might not compare so favourably with "binary search until we've got it down to a smallish substring, then simple linear search".)
You also don't need to do a lot of independent hashes. You can just take a linear combination of the results of two hashes and get basically no performance degradation (see: http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf).
Also, you probably don't actually need a 1e-8 false positive rate, since you're going to fall back to a canonical (but slow) lookup table for positives in most use cases. Bloom filters are most useful when your real dictionary is slow and you're expecting a lot of 'no match' results.
Absolutely not. I just wanted to demonstrate that even if you do want a very low false-positive rate from your filter you don't need a very large data structure, contrary to jeresig's fears. Bloom filters are very, very space-efficient.
I haven't had a lot of cases where I was willing to tolerate errors, but I figured in a word game nobody would notice. :)
One other thing to look into if you're using eval() to parse your json data: A couple of years ago, the flickr developer blog observed that building their data structures with string.split() was much faster than parsing the json equivalent with eval(). YMMV on newer browsers.
http://code.flickr.com/blog/2009/03/18/building-fast-client-...
I actually wanted to do that. I've been following your dictionary posts because I'm doing something similar for an iPad PhoneGap app. I created a dictionary with 600k words & n-grams ( http://ktype.net/wiki/research:articles:progress_20110209 ) and want to make really smart predictions (not just basic spell-check/auto-correct). My raw dictionary is 6MB (too large for localStorage) and I load it from a string into a 1D JS array but it randomly crashes the iPad because of memory issues.
I was going to change my code to use a space-saving trie next week and lo and behold you posted your two posts and saved me a lot of ground work (so thanks for that!). But unlike you, I need to loop through large parts of the dictionary in order to make good predictions. E.g. 'mxm' should suggest 'maximum' and 'gd mrong' should suggest 'good morning'. While one could come up with really complex ways on minimizing the number of word lookups, it is far easier to just cycle through all dictionary words that begin with 'm' and filter for specific letters.
I'm still uncertain what I'll do. Maybe iOS Sqlite DB or iOS CoreData or JS optimized-trie. But once again, thanks for these posts. They've directly helped me.
It encodes a dictionary of 106,495 words (an old Scrabble dictionary) into 427,982 base64 characters.
Considering that Tries offer a great base to build a flexible string matching algorithm off of I consider the prototype a success.
The author's approach to optimizing the JavaScript trie is pretty good but there are still improvements that could be made. I would be curious to see if the Ternary approach could yield with interior node collapsing (like a Patricia Trie) would yield the performance the author is looking for.
Also as @ot noted using 5-6 characters per string is too short for a Trie's strengths to really shine. They work better as the average length of string increases.
IndexedDB may help a bit in this case. It'll cut down on memory usage (at the cost of additional reads on the disk - which will likely increase battery usage on mobile devices) and <em>may</em> decrease search time. Although easily the biggest benefit of my current technique is that it's capable of easily using <code>localStorage</code> - and that has fantastic cross-browsers support (in contrast with IndexedDB, which doesn't).