1- Project name
2
3marisa-trie
4http://code.google.com/p/marisa-trie/
5
6- Project summary
7
8Matching Algorithms with Recursively Implemented StorAge
9
10- Version
11
120.1.4
13
14- Description
15
16This project *marisa-trie* provides a C++ library *libmarisa* and command line tools *`marisa-*`* for building and operating nesting patricia tries. The brand-new dictionary structure is designed to be static and space efficient. Also, *marisa-trie* enables not only simple lookups but also prefix searches and predictive searches.
17
18 * Prefix searches are to find keys from prefixes of a given query.
19 * Predictive searches are to find keys starting with a given query.
20
21The biggest advantage of *marisa-trie* is that it can build a considerably compact dictionary. See below for the size of dictionaries built with various trie implementations.
22
23 * Input
24  * Source: enwiki-20110115-all-titles-in-ns0.gz
25  * Contents: all page titles of English Wikipedia (Jan. 2011)
26  * Number of keys: 8,279,325
27  * Total size: 167,223,035 bytes (plain) / 46,344,646 bytes (gzipped)
28
29|| *Implementation* || *Size (bytes)* || *Remarks*                   ||
30||  darts-clone     ||   316,065,792  || Compacted double-array trie ||
31||  tx-trie         ||   107,119,864  || LOUDS-based trie            ||
32|| *marisa-trie*    ||   *42,688,271* || Nesting patricia trie       ||
33
34 * Documentation (in Japanese)
35  * HowTo
36  * ListOfTools
37  * LibraryInterface
38  * BenchmarkResults
39
40- Version control system
41
42Subversion
43
44- Source code license
45
46New BSD License
47
48- Project labels
49
50Nesting
51Patricia
52Trie
53Static
54Dictionary
55CPlusPlus
56