| - Project name |
| |
| marisa-trie |
| http://code.google.com/p/marisa-trie/ |
| |
| - Project summary |
| |
| MARISA: Matching Algorithm with Recursively Implemented StorAge |
| |
| - Version |
| |
| 0.2.4 |
| |
| - Description |
| |
| *Matching Algorithm with Recursively Implemented !StorAge (MARISA)* is a static and space-efficient trie data structure. And *libmarisa* is a C++ library to provide an implementation of MARISA. Also, the package of *libmarisa* contains a set of command line tools for building and operating a MARISA-based dictionary. |
| |
| A MARISA-based dictionary supports not only lookup but also reverse lookup, common prefix search and predictive search. |
| |
| * Lookup is to check whether or not a given string exists in a dictionary. |
| * Reverse lookup is to restore a key from its ID. |
| * Common prefix search is to find keys from prefixes of a given string. |
| * Predictive search is to find keys starting with a given string. |
| |
| The biggest advantage of *libmarisa* is that its dictionary size is considerably more compact than others. See below for the dictionary size of other implementations. |
| |
| * Input |
| * Source: enwiki-20121101-all-titles-in-ns0.gz |
| * Contents: all page titles of English Wikipedia (Nov. 2012) |
| * Number of keys: 9,805,576 |
| * Total size: 200,435,403 bytes (plain) / 54,933,690 bytes (gzipped) |
| |
| || *Implementation* || *Size (bytes)* || *Remarks* || |
| || darts-clone || 376,613,888 || Compacted double-array trie || |
| || tx-trie || 127,727,058 || LOUDS-based trie || |
| || *marisa-trie* || 50,753,560 || MARISA trie || |
| |
| * Documentation |
| * marisa-0.2.4 |
| * [http://marisa-trie.googlecode.com/svn/trunk/docs/readme.en.html README (English)] |
| * [http://marisa-trie.googlecode.com/svn/trunk/docs/readme.ja.html README (Japanese)] |
| * marisa-0.1.5 (Japanese) |
| * HowTo |
| * ListOfTools |
| * LibraryInterface |
| * BenchmarkResults |
| |
| - Version control system |
| |
| Subversion |
| |
| - Source code license |
| |
| The BSD 2-clause License |
| The LGPL 2.1 or any later version |
| |
| - Project labels |
| |
| Patricia |
| Trie |
| Static |
| Dictionary |
| CPlusPlus |
