• Home
Name Date Size #Lines LOC

..--

bindings/03-May-2024-18,73815,168

docs/03-May-2024-1,7621,664

include/03-May-2024-828582

lib/03-May-2024-5,5554,774

m4/03-May-2024-

tests/03-May-2024-1,9891,543

tools/03-May-2024-1,6961,456

vs2008/03-May-2024-2,9032,888

.gitignoreD03-May-2024734 5857

AUTHORSD03-May-202436 21

Android.bpD03-May-20243 KiB10697

COPYING.mdD03-May-20242.2 KiB3523

LICENSED03-May-20242.2 KiB3523

METADATAD03-May-2024358 1816

MODULE_LICENSE_BSDD03-May-20240

Makefile.amD03-May-2024487 2521

README.mdD03-May-20242.2 KiB6241

configure.acD03-May-20248.5 KiB279259

marisa.pc.inD03-May-2024251 1210

README.md

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