5 ms·

Not a dumb question at all. Im working on a project to do this right now in fact, since it seeems all the open-source autocomplete implementations I can find j

Not a dumb question at all. Im working on a project to do this right now in fact, since it seeems all the open-source autocomplete implementations I can find just come down to doing a "SELECT bla where bla like bla", which is pretty slow. The one major issue is that tries are prefix-based, so it has to match starting from the beginning of the query. My sort of solution around that is to break up the terms your matching against into groups of phrases, and allow prefix matching on any of those phrases. As a question to HN-I was planning on using Radix Trees, but now Ive read this article it seems like there might be some other good options. Are any of those structures noticeable better for storing lots of strings?

apgwoz 16y ago
http://en.wikipedia.org/wiki/Directed_acyclic_word_graph http://en.wikipedia.org/wiki/Directed_acyclic_word_graph have you considered a DAWG? One win here is you save on storing suffixes, with added complexity of course.
sunir 16y ago
I thought that most of the time since users are typing one character at a time that would be efficient. Even pasting at the end of the string is easy to manage as it might only be O(q) where q is the length of the query string (depending on the structure of the underlying trie). The worst cases are editing midstring, and worst, pasting to the start of the query string. Still, those are O(q) rather than O(N) where N are the total number of strings in the database. In my case, N will have millions of records where q will rarely exceed 250 characters.
- whakojacko 16y ago
  the problem is not efficiency, its relevancy. Say you have a result "hacker news". If its a pure prefix trie, this wont match the query "news", even though you probably want to return this as a suggestion. My hack around this would be to add both "hacker news" and "news" in the trie-Its still not perfect, since it wouldn't match "acker" or "ws" etc.
bmm6o 16y ago
Do you have a plan for handling non-ascii characters in your trie? The descriptions I've seen usually involve having a character index into an array, and it seems like a waste if you used 2-byte characters. I guess you would use an encoding (like UTF-8), with a particular canonicalization.

apgwoz 16y ago

http://en.wikipedia.org/wiki/Directed_acyclic_word_graph http://en.wikipedia.org/wiki/Directed_acyclic_word_graph have you considered a DAWG? One win here is you save on storing suffixes, with added complexity of course.

sunir 16y ago

I thought that most of the time since users are typing one character at a time that would be efficient. Even pasting at the end of the string is easy to manage as it might only be O(q) where q is the length of the query string (depending on the structure of the underlying trie). The worst cases are editing midstring, and worst, pasting to the start of the query string. Still, those are O(q) rather than O(N) where N are the total number of strings in the database. In my case, N will have millions of records where q will rarely exceed 250 characters.

whakojacko 16y ago
the problem is not efficiency, its relevancy. Say you have a result "hacker news". If its a pure prefix trie, this wont match the query "news", even though you probably want to return this as a suggestion. My hack around this would be to add both "hacker news" and "news" in the trie-Its still not perfect, since it wouldn't match "acker" or "ws" etc.

bmm6o 16y ago

Do you have a plan for handling non-ascii characters in your trie? The descriptions I've seen usually involve having a character index into an array, and it seems like a waste if you used 2-byte characters. I guess you would use an encoding (like UTF-8), with a particular canonicalization.