PrefixTree Documentation

0.1

A lighting fast bitwise prefix tree implementation. You can find information about this kind of structures under names trie, DAWG or minimal acyclic deterministic finite automata.

This library can be usefull for

• longest-prefix matching
• code completion
• dictionary compression
• spell checking

In compare to list based dictionaries the prefix tree structure is both faster and less memory consuming with the same funcionality.

Performance (tested on http://sjp.pl/slownik/growy/sjp-20111017.tar.gz):

• 32 MB polish dictionary containing almost 3.000.000 words is converted to prefix tree and compressed (to DAWG structure) in less than 2 seconds.
• After compression the dictionary occupies only 2.5 MB.
• Finding all 3.000.000 words in the structure takes 0.3 s on 64 bit machine with POPCNT instruction or 0.8 s without using this instruction.

You can download this library from http://sourceforge.net/projects/prefixtree/

If you have any problem with this software go on support page http://sourceforge.net/p/prefixtree/discussion

If these links don't work you should look at http://sites.google.com/site/thumren/home/prefixtree