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