Autocomplete using Tries | Hacker News Reader

Autocomplete using Tries

dibaiee.ir

69 pointsmdibaiee23 comments

So tries are a really cool data structure and they're the natural fit for an autocomplete, but a while back I had to implement an autocomplete widget (over stock tickers) and it turns out that for many relatively small, dense data-sets, binary search over a sorted array with a linear scan to find suffixes is a much (10x+) faster approach.

The problem is that a trie is a very cache-loose data structure. Every node is connected to every other by pointers, and they may be spread all over main memory. Finding the first node usually involves chasing several pointers; enumerating each successive one involves chasing several more. Meanwhile, if you just had a sorted array, all subsequent results would be on the same page at least, and many would be on the same cache line.

YMMV, based on your data's size and shape. Sorted arrays usually work best when the full data set is small and dense (eg. stock tickers), while tries may work better for sparse data (eg. sentences typed in by users). Always benchmark before committing to an implementation.

Your conclusion is likely correct given your data, but did you happen to evaluate HAT-tries as well?

http://crpit.com/confpapers/CRPITV62Askitis.pdf

Nope I didn't - I did this work in 2006, and the HAT trie didn't come out until 2007. I did try a number of different variations on how to do the internal storage of nodes though - the fastest was what the paper described as a burst-trie - as well as other binary search tree structures. The speed difference was well over 5x though (IIRC, it was something like 17x from best string trie vs. binary search), so if the paper's conclusions hold it probably wouldn't have mattered.

Your comment provoked a quick search on pointer-less encoding of tries. It turns out one such implementation was patented in 2006

http://www.google.com/patents/US20060020638

Another problem is that tries are not stored as such in typical databases. You'd have to roll your own database system to support this.

If you're doing an autocomplete widget, you probably want to store all of your data in RAM rather than in any DB. Autocomplete queries fire on every keystroke from every user, so if you hit the DB at all, you've probably killed your server.

Well, I guess the DB already has caching logic to keep things in memory. Or otherwise, it is not such a good DB system.

Most have some sort of caching logic but you can't rely on it to do what you want. Always benchmark, and never assume that just because you're paying for something or that it's the industry standard, it does what you want. I've seen a number of devs completely surprised by the throughput & latency numbers they get from their databases because they assume everything is going to be cached in RAM and the database is really hitting disk for some obscure reason on every query.

This is all really hypothetical. Show me a DB that can do tries first.

Postgres with SP-GiST, for example

You're the one insisting that this technique has to involve a database. It really doesn't!

http://lucene.apache.org/solr/

Usually this is due to dev ignorance of the five-minute rule and/or a failure to properly account for size of data.

That being said, it really depends on the problem at hand and the overall workload of the database.

The database is doing row caching, though, and isn't going to be caching lower levels of the trie in close proximity to the higher ones. It's not the same logic in the general case. At a prior gig with a very heavily used typeahead, we loaded the entire thing into a memory cache inside our typeahead service, because even relying on memcache was too slow.

Hey, thanks for pointing these out, appreciated.

I'm not aiming for speed in this tutorial, it's just a tutorial to teach how Tries work, I knew arrays are faster in this kind of situation, even an array.filter can do the job, so you're right; but Tries are more flexible in my opinion, they can easily be customized for any use.

Anyway, I always like it when I get criticized, I learn something, thank you nostrademons!

There's no reason you have to scatter a trre all over the place. Dictionaries almost never change, so you can flatten the pointer data (and maybe even inline the words if you're a masochist) without worrying.

When you have more than a handful of strings, you will want to return only a small number (k) of completions, preferably sorted by some pre-assigned score. Depending on how you order the trie, you can only get the first k completions by lexicographic ordering, which could be very far from the "best" completions.

A common approach to solve this is to store in each internal node the maximum score among all its descendants, and sort the children of each node by maximum score. This way by doing a best-first search with a heap you can efficiently retrieve the top-k completions by score.

If you then have millions of strings, it becomes tricky to do this in a space-efficient and cache-efficient way. I wrote a paper a few years ago with different space-time tradeoffs: http://www.di.unipi.it/~ottavian/files/topk_completion_www13...

You may also want to check this spelling correction algo. I'm using it along with trie. Original is in C# but ports are available.

http://blog.faroo.com/2012/06/07/improved-edit-distance-base...

Speaking of autocomplete, how would you design a data structure and declaration syntax to feed to the autocomplete/parsing system of a constrained CLI?

By "constrained CLI", I mean the kind that controls a router or other piece of equipment which has a well-defined (um, somewhat) syntax, as opposed to the somewhat more free-form aspect of the shell.

I ask, because one of my jobs had me occasionally working in the CLI declarations for a type of router. The cli commands could be in the form "interface foo enable", where "interface" could be shortened its shortest non-ambiguous form ("int" IIRC), and "foo" was a string corresponding to one of the interfaces on the system. Pressing TAB after "int" would automatically suggest the list of interfaces that exist on the system. This command had an opposite in the form "no interface foo enable" (yeah, prefixing "no" instead of postfixing "disable", though to be fair that may have been possible as well). A declaration of such a syntax was done with something along the line of:

  node(id=interface, type=keyword, keyword=interface, no_prefix=yes, next=int_name);
  node(id=int_name, type=string, next=enable);
  node(id=enable, type=keyword, keyword=enable);

(with several extra bells and whistles to account for the int_name string referencing the existing interfaces on the system and to indicate that the command was only complete with "enable" at the end).

There were hundreds of declaration files containing lines like that, it was parsed by a humongous Perl script that output a 7MB source file containing the data structures fed to libinput. It was easily the slowest part of our compilation process, and Emacs would choke on that 7MB sourcefile.

It was terrible, but I never found examples of how to do it better. Anyone have any experience?

It seems you'd get more mileage out of a trie if you also compared it with a sort of zipper approach. The idea being that if I type "a", I should just focus the trie around "A". If I next type "l", then I focus the "l" around my new root, so I find all strings starting "Al". It doesn't change the complexity class of completion, but maybe the small optimisation is worth it.

I was watching this lecture last night about tries and suffix arrays. Pretty cool stuff!

http://youtu.be/NinWEPPrkDQ

This looks really cool.

Do you have any speed comparisons vs traditional autocomplete methods?

Tries are pretty much the tradition autocomplete method.

Reply on news.ycombinator.com