Trie
Does anyone know of a good open source implementation of a Trie. I've been assigned to look into the potential of using AJAX within our organization. As a test case, I'm trying to implement a simple auto-complete application for street addresses. The source of these addresses is a relational database. I'm not sure it makes sense to perform a query for each user key stroke. A trie is a sensible solution, but I can't seem to find a useable open source library. Something well-documented and in the form of a JAR would be nice...
-Bryan
[554 byte] By [
bjb1440a] at [2007-10-2 12:57:02]
Hmm. No takers on the topic.
Well, if anyone's interested, I realized that the whole trie thing falls apart if the user elects to use the arrow keys or mouse to reposition the cursor.
Anywho.. It's also neccessary to keep track of the location in the trie for each user-- which I suppose is possible.
In the meantime, I've been told that querying the database per each key stroke is not too much of a problem so long as there are sufficient indexes and a connection is opened only once... Maybe the easiest solution is also the most sensible in this case?
-Bryan
> Hmm. No takers on the topic.
I looked around a bit for this. I thought there might be one in the apache commons but I didn't see one. You should probably do some due-dilligence in Google but I came up empty-handed.
> Well, if anyone's interested, I realized that the
> whole trie thing falls apart if the user elects to
> use the arrow keys or mouse to reposition the cursor.
If you are using a DocumentListener, this should not be an issue.
> Anywho.. It's also neccessary to keep track of the
> location in the trie for each user-- which I suppose
> is possible.
Wait. what? I'm concerned that you even think this is a concern. What are you thinking of in terms of your design?
> In the meantime, I've been told that querying the
> database per each key stroke is not too much of a
> problem so long as there are sufficient indexes and a
> connection is opened only once...
Who says? Calling the database is a pretty heavy operation. It not only is inefficient in terms of your application, it puts more load on the DB. Have you asked a DBA whether this is OK? How many concurrent users are we talking about here?
http://www.graphbuilder.com/trie/
> Does anyone know of a good open source implementation
> of a Trie. I've been assigned to look into the
> potential of using AJAX within our organization.
AJAX and Tries have nothing to do with each other.
> Something well-documented and in the
> form of a JAR would be nice...
My understanding is the "J" in AJAX refers to JavaScript.
Google has an auto-complete feature. You may be able to research how they implemented it.
http://www.google.com/webhp?complete=1&hl=en
krippen,
Maybe I should have been more specific. The server-side technology for this implementation of AJAX here is a Servlet. The client-side technology is JavaScript and W3C DOM.
The trie would be used by the Servlet on the server side. If a user, for example, types 'A' the servlet would walk from the root of the trie accross the edge labeled 'A' to node x.If the user then types 'B', then the servlet would then walk from node x accross the edge labeled 'B' to node y. Perhaps at this point all leaves below node y are {"ALBANY", "ALLENVILLE"} the client should then see the options "ALBANY" and "ALLENVILLE". That's the idea in a nutshell.
-Bryan
dubwai,If user Jim Jones goes from node 'x' to node 'y' by typing 'B' and then from node 'y' to node 'z' by typing 'O' then then either the client or server need to remember that Jim Jones is at node 'z'.-Bryan
> dubwai,
>
> If user Jim Jones goes from node 'x' to node 'y' by
> typing 'B' and then from node 'y' to node 'z' by
> typing 'O' then then either the client or server need
> to remember that Jim Jones is at node 'z'.
Yes. This is very basic stuff for a web app. How many web apps do you know of that can only support one user at a time? You will need to store the user's state for lots of things. IIRC you use a session state for this.
dubwai,You seem to be looking for a reason to call me stupid. Give it a rest.-Bryan
> dubwai,
>
> You seem to be looking for a reason to call me
> stupid. Give it a rest.
>
> -Bryan
No. Get over yourself. You are implied that this was a problem that you weren't even sure had a solution. That doesn't bode well for your project. If you aren't sure if you can support current users, the datastructure you will be using should be the least of your worries. A sorted list and a binary search will likely provide more than acceptable performance for what you want to do.
> If user Jim Jones goes from node 'x' to node 'y' by
> typing 'B' and then from node 'y' to node 'z' by
> typing 'O' then then either the client or server need
> to remember that Jim Jones is at node 'z'.
No, the server and client doesn't really need to remember this.
Assume the client is typing in a text field. Then, each time the
content of the text field changes, a request is made to the
server to retrieve at most 10 entries that start with the prefix.
<Request>
<Action>getAddresses</Action>
<Prefix>...</Prefix>
</Request>
Servlet looks at trie or DB (most likely DB) to do a prefix
match and return at most 10 addresses.
<Response>
<Addresses>
<Address>...</Address>
<Address>...</Address>
<Addresses>
</Response>
krippen,You're right. This is exactly what I ended up doing-- came to the same conclusion. The full prefix should be sent with each request.-Bryan
"AJAX In Action" shows how to do autocomplete, and they don't go in for a trie. The concern about excessive database trips is valid, but I believe they show how to manage it without ruining the effect.I've also seen it done with Lucene. Performance was not a
> "AJAX In Action" shows how to do autocomplete, and
> they don't go in for a trie.
>
> The concern about excessive database trips is valid,
> but I believe they show how to manage it without
> ruining the effect.
>
> I've also seen it done with Lucene. Performance was
> not a problem.
>
> %
it seems to me that all you need is caching which you get with a package like Hibernate.
