-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
63 lines (44 loc) · 2.02 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
- 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