Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #14825
| From | Daniel Pitts <newsgroup.nospam@virtualinfinity.net> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Patricia trie vs binary search. |
| References | <jpmev4$63l$1@dont-email.me> |
| Message-ID | <uAewr.45671$On2.38133@newsfe16.iad> (permalink) |
| Date | 2012-05-26 17:30 -0700 |
On 5/24/12 4:07 PM, markspace wrote: > For some reason I was thinking about sub-string searches today. I looked > up Patricia tries (a kind of radix tree) to see if they would help. > While interesting, the radix tree seems to have a lot of overhead for > large numbers of entries. > > The radix tree uses a bucket at each level to hold all children (and > there could be quite a lot of children). Each child if present requires > a pointer (an object in Java) to hold it. For the example given, this > could be as much as one object per character in each string, plus the > bucket to hold it and its siblings. If the number strings is very large, > this could really result in an explosion of memory usage. I tend to use a Deterministic Finite State Automata for this. You can load the entire English dictionary fairly easily with that scheme. Yes, you use a bit of memory, but unless you're doing this on an embedded device, its probably not enough memory to be concerned about. Most of what I know about "searching" and "parsing", I've learned from "Parsing Techniques - A Practical Guide" <http://dickgrune.com/Books/PTAPG_1st_Edition/>. Free PDF or PS downloads on that page. Very worth a read. I'm sure parsing theory has been much extended since this book was written, however it is definitely a good introduction to the concepts in the space. HTH, Daniel.
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Patricia trie vs binary search. markspace <-@.> - 2012-05-24 16:07 -0700
Re: Patricia trie vs binary search. glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-05-24 23:39 +0000
Re: Patricia trie vs binary search. markspace <-@.> - 2012-05-24 17:56 -0700
Password quality (Was: Patricia trie vs binary search.) Lew <lewbloch@gmail.com> - 2012-05-25 09:41 -0700
Re: Password quality (Was: Patricia trie vs binary search.) markspace <-@.> - 2012-05-25 12:17 -0700
Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-26 17:30 -0700
Re: Patricia trie vs binary search. markspace <-@.> - 2012-05-26 18:17 -0700
Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-27 18:44 -0700
Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-27 22:00 -0700
Re: Patricia trie vs binary search. markspace <-@.> - 2012-05-28 08:20 -0700
Re: Patricia trie vs binary search. markspace <-@.> - 2012-05-28 14:38 -0700
Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-28 09:20 -0700
Re: Patricia trie vs binary search. Lew <noone@lewscanon.com> - 2012-05-28 21:54 -0700
Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 09:14 -0700
Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 09:55 -0700
Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 11:17 -0700
Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 11:22 -0700
Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 14:44 -0700
Re: Patricia trie vs binary search. Lew <lewbloch@gmail.com> - 2012-05-29 14:03 -0700
Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 14:49 -0700
Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 15:23 -0700
Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 15:39 -0700
Re: Patricia trie vs binary search. Gene Wirchenko <genew@ocis.net> - 2012-05-29 16:08 -0700
Re: Patricia trie vs binary search. Lew <lewbloch@gmail.com> - 2012-05-29 18:25 -0700
Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 09:16 -0700
Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 13:37 -0400
Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 10:49 -0700
Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 13:58 -0400
Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 14:20 -0400
Re: Patricia trie vs binary search. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-29 11:21 -0700
Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 14:29 -0400
Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 15:00 -0400
Re: Patricia trie vs binary search. Jeff Higgins <jeff@invalid.invalid> - 2012-05-29 09:24 -0400
csiph-web