Re: Patricia trie vs binary search.

From:

Daniel Pitts <newsgroup.nospam@virtualinfinity.net>

Newsgroups:

comp.lang.java.programmer

Date:

Sat, 26 May 2012 17:30:17 -0700

Message-ID:

<uAewr.45671$On2.38133@newsfe16.iad>

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.