Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have been looking for an efficient String trie implementation. Mostly I have found code like this:

Referential implementation in Java (per wikipedia)

I dislike these implementations for mostly two reasons:

  1. They support only 256 ASCII characters. I need to cover things like cyrillic.
  2. They are extremely memory inefficient.

Each node contains an array of 256 references, which is 4096 bytes on a 64 bit machine in Java. Each of these nodes can have up to 256 subnodes with 4096 bytes of references each. So a full Trie for every ASCII 2 character string would require a bit over 1MB. Three character strings? 256MB just for arrays in nodes. And so on.

Of course I don't intend to have all of 16 million three character strings in my Trie, so a lot of space is just wasted. Most of these arrays are just null references as their capacity far exceeds the actual number of inserted keys. And if I add unicode, the arrays get even larger (char has 64k values instead of 256 in Java).

Is there any hope of making an efficient trie for strings? I have considered a couple of improvements over these types of implementations:

  • Instead of using array of references, I could use an array of primitive integer type, which indexes into an array of references to nodes whose size is close to the number of actual nodes.
  • I could break strings into 4 bit parts which would allow for node arrays of size 16 at the cost of a deeper tree.
share|improve this question

2 Answers 2

up vote 1 down vote accepted

What are you using this trie for? What is the total number of words that you plan to hold, and what is the sparseness of their constituent characters? And most important, is a trie even appropriate (versus a simple map of prefix to list of words)?

Your idea of an intermediate table and replacing pointers with indexes will work, provided that you have a relatively small set of short words and a sparse character set. Otherwise you risk running out of space in your intermediate table. And unless you're looking at an extremely small set of words, you won't really save that much space: 2 bytes for a short versus 4 bytes for a reference on a 32-bit machine. If you're running on a 64-bit JVM, the savings will be more.

Your idea about breaking the characters into 4-bit chunks probably won't save you much, unless all of your expected characters are in an extremely limited range (maybe OK for words limited to uppercase US-ASCII, not likely with a general Unicode corpus).

If you have a sparse character set, then a HashMap<Character,Map<...>> might be your best implementation. Yes, each entry will be much larger, but if you don't have many entries you'll get an overall win. (as a side note: I always thought it was funny that the Wikipedia article on Tries showed -- maybe still does -- an example based on a hashed data structure, completely ignoring the space/time tradeoffs of that choice)

Finally, you might want to avoid a trie altogether. If you're looking at a corpus of normal words in a human language (10,000 words in active use, with words 4-8 characters long), you'll probably be MUCH better off with a HashMap<String,List<String>, where the key is the entire prefix.

share|improve this answer
    
- References are 8 bytes on 32-bit, 16 bytes on 64-bit machines - It's for autocomplete functionality - Majority of characters in strings are in ASCII range, but there's a few Central European characters thrown in. This is why I wanted smaller branching than 256, because it will cut out large number of characters. I don't see HashMap<String, List<String>> being better or faster or less memory consuming, albeit really easy to write and use. But I will accept for the HashMap<Character,Map> idea. Would be ok for chars over 128 (rare in my case - would be bad for chinese text). –  U Mad Jul 6 '12 at 14:32

if you encode up the strings into UTF8 you can use the standard 256 branching trie and still be unicode compatible

also you should note that only 70 or so characters out of the possible 128 ascii characters (which all encode to 1 byte in UTF8) will be found most heavily you can optimize for that (like include the common digraphs in place of the unused control characters)

share|improve this answer
    
I know that UTF8 can be represented like that. However this still doesn't solve the memory consumption which is still quite high. Swapping characters into basic 256 range would require quite a bit of switch sentences, I am doubtful it would be worth it. As far as UTF-8 goes... this is actually an issue I'm pondering right now. Java String uses UTF-16 chars, which I can readily get, I can encode these byte by byte. Or I can convert to UTF-8 and use that. At this point it is unclear to me if cost of converting from UTF-16 to UTF-8 is prohibitive or not. –  U Mad Jul 5 '12 at 12:22
    
what is the language you envision using this on most of the time? trying to optimize for everything is impossible (or it would have been done already) so optimize for the common case –  ratchet freak Jul 5 '12 at 12:29
1  
This is one of the very few use cases where CESU-8 would be preferable to UTF-8: it's huge advantage here is that it's trivial to get from a UTF-8 codepoint to the corresponding CESU-8 codepoint (whereas you'd need to decode 1-2 UTF-16 codepoints to get to the corresponding UTF-8 codepoints). –  Joachim Sauer Jul 5 '12 at 12:39
1  
@ratchetfreak Java. Though I think the question can be generalized to most languages. I guess in C you could simply cast pointer to byte* to encode any type in a bitwise trie. –  U Mad Jul 5 '12 at 12:43
    
@UMad I meant what languages the input strings will be in (English, French, German,...) –  ratchet freak Jul 5 '12 at 13:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.