1*ab8db090SAndroid Build Coastguard Worker### README 2*ab8db090SAndroid Build Coastguard Worker 3*ab8db090SAndroid Build Coastguard Worker#### Project name 4*ab8db090SAndroid Build Coastguard Worker 5*ab8db090SAndroid Build Coastguard Workermarisa-trie 6*ab8db090SAndroid Build Coastguard Worker 7*ab8db090SAndroid Build Coastguard Worker#### Project summary 8*ab8db090SAndroid Build Coastguard Worker 9*ab8db090SAndroid Build Coastguard WorkerMARISA: Matching Algorithm with Recursively Implemented StorAge 10*ab8db090SAndroid Build Coastguard Worker 11*ab8db090SAndroid Build Coastguard Worker#### Latest version 12*ab8db090SAndroid Build Coastguard Worker 13*ab8db090SAndroid Build Coastguard Worker0.2.6 14*ab8db090SAndroid Build Coastguard Worker 15*ab8db090SAndroid Build Coastguard Worker#### Description 16*ab8db090SAndroid Build Coastguard Worker 17*ab8db090SAndroid Build Coastguard WorkerMatching 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. 18*ab8db090SAndroid Build Coastguard Worker 19*ab8db090SAndroid Build Coastguard WorkerA MARISA-based dictionary supports not only lookup but also reverse lookup, common prefix search and predictive search. 20*ab8db090SAndroid Build Coastguard Worker 21*ab8db090SAndroid Build Coastguard Worker* Lookup is to check whether or not a given string exists in a dictionary. 22*ab8db090SAndroid Build Coastguard Worker* Reverse lookup is to restore a key from its ID. 23*ab8db090SAndroid Build Coastguard Worker* Common prefix search is to find keys from prefixes of a given string. 24*ab8db090SAndroid Build Coastguard Worker* Predictive search is to find keys starting with a given string. 25*ab8db090SAndroid Build Coastguard Worker 26*ab8db090SAndroid Build Coastguard WorkerThe biggest advantage of libmarisa is that its dictionary size is considerably more compact than others. See below for the dictionary size of other implementations. 27*ab8db090SAndroid Build Coastguard Worker 28*ab8db090SAndroid Build Coastguard Worker* Input 29*ab8db090SAndroid Build Coastguard Worker * Source: enwiki-20121101-all-titles-in-ns0.gz 30*ab8db090SAndroid Build Coastguard Worker * Contents: all page titles of English Wikipedia (Nov. 2012) 31*ab8db090SAndroid Build Coastguard Worker * Number of keys: 9,805,576 32*ab8db090SAndroid Build Coastguard Worker * Total size: 200,435,403 bytes (plain) / 54,933,690 bytes (gzipped) 33*ab8db090SAndroid Build Coastguard Worker 34*ab8db090SAndroid Build Coastguard Worker|Implementation|Size (bytes)|Remarks | 35*ab8db090SAndroid Build Coastguard Worker|:-------------|-----------:|--------------------------:| 36*ab8db090SAndroid Build Coastguard Worker|darts-clone | 376,613,888|Compacted double-array trie| 37*ab8db090SAndroid Build Coastguard Worker|tx-trie | 127,727,058|LOUDS-based trie | 38*ab8db090SAndroid Build Coastguard Worker|marisa-trie | 50,753,560|MARISA trie | 39*ab8db090SAndroid Build Coastguard Worker 40*ab8db090SAndroid Build Coastguard Worker#### Documentation 41*ab8db090SAndroid Build Coastguard Worker 42*ab8db090SAndroid Build Coastguard Worker* README (English): https://s-yata.github.io/marisa-trie/docs/readme.en.html 43*ab8db090SAndroid Build Coastguard Worker* README (Japanese): https://s-yata.github.io/marisa-trie/docs/readme.ja.html 44*ab8db090SAndroid Build Coastguard Worker 45*ab8db090SAndroid Build Coastguard Worker#### Build instructions 46*ab8db090SAndroid Build Coastguard Worker 47*ab8db090SAndroid Build Coastguard WorkerYou can get the latest version via `git clone`. Then, you can generate a `configure` script via `autoreconf -i`. After that, you can build and install libmarisa and its command line tools via `configure` and `make`. For details, see also documentation in `docs`. 48*ab8db090SAndroid Build Coastguard Worker 49*ab8db090SAndroid Build Coastguard Worker``` 50*ab8db090SAndroid Build Coastguard Worker$ git clone https://github.com/s-yata/marisa-trie.git 51*ab8db090SAndroid Build Coastguard Worker$ cd marisa-trie 52*ab8db090SAndroid Build Coastguard Worker$ autoreconf -i 53*ab8db090SAndroid Build Coastguard Worker$ ./configure --enable-native-code 54*ab8db090SAndroid Build Coastguard Worker$ make 55*ab8db090SAndroid Build Coastguard Worker$ make install 56*ab8db090SAndroid Build Coastguard Worker``` 57*ab8db090SAndroid Build Coastguard Worker 58*ab8db090SAndroid Build Coastguard Worker#### Source code license 59*ab8db090SAndroid Build Coastguard Worker 60*ab8db090SAndroid Build Coastguard Worker* The BSD 2-clause License 61*ab8db090SAndroid Build Coastguard Worker* The LGPL 2.1 or any later version 62