The reason why the Trie doesn't improve (and actually it does worse) is probably that the strings are too short. At an average of 5-6 characters per string, each one has size comparable to a single pointer.<p>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).<p>BTW, by using a fair amount of succinct data structures and bit tricks it is possible to do <i>way</i> 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 :)
It sounds like you need to build on the strengths of the JS implementations you care about, and encode your data structure in a string or something. Have a jump table in the beginning with the first characters, and then likewise for other characters, with some other convention to denote leafs. You won't be able to add to the trie, lookup won't be as fast, but it would still be O(log N) and parsing would be dead simple.
Here's an example of decoding and searching a DAWG in real-time in javascript.<p>It encodes a dictionary of 106,495 words (an old Scrabble dictionary) into 427,982 base64 characters.<p><a href="http://www.davidst.com/jsanagram/" rel="nofollow">http://www.davidst.com/jsanagram/</a>
I wrote a implementation of Ternary Search Trie[1] in Python and found that for insert/update/delete I could get my performance to be on the same order to one order of magnitude slower than python built in dict.<p>Considering that Tries offer a great base to build a flexible string matching algorithm off of I consider the prototype a success.<p>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.<p>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.<p>[1] <a href="https://github.com/timtadh/tst" rel="nofollow">https://github.com/timtadh/tst</a>
Great follow-up and appreciate the deep analysis with graphs. I am curious how you measure the Mobi Safari load times. Is there a tool (xcode?) to do this?