tag | 5d531839bef133b84580e66d239bb5841b855d15 | |
---|---|---|
tagger | The Android Open Source Project <initial-contribution@android.com> | Mon Aug 08 14:28:51 2022 -0700 |
object | 202ccc7cdef4b7d5c79dcfcc883083d2a9339a3b |
Android 12.1.0 release 26
commit | 202ccc7cdef4b7d5c79dcfcc883083d2a9339a3b | [log] [tgz] |
---|---|---|
author | Xin Li <delphij@google.com> | Sat Feb 20 12:22:10 2021 +0000 |
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | Sat Feb 20 12:22:10 2021 +0000 |
tree | f36e0f9da5855a1abb42f107a4e0733d79080e65 | |
parent | 8d7f446201a585685415bd742d5d5585d76de2fc [diff] | |
parent | f4457bc8f0a2fdbfd2378ba7a84b0cb40ef5dda9 [diff] |
[automerger skipped] Mark ab/7061308 as merged in stage. am: 189dd28362 -s ours am: f4457bc8f0 -s ours am skip reason: Change-Id Idfe5f25234cd6e6bd641d912524681304fa08752 with SHA-1 c9570b2a21 is in history Original change: undetermined MUST ONLY BE SUBMITTED BY AUTOMERGER Change-Id: I0e9307b76dfe9e0b9b5f1ad20ab52e84cc5f1b8b
marisa-trie
MARISA: Matching Algorithm with Recursively Implemented StorAge
0.2.6
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.
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.
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 |
You 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
.
$ git clone https://github.com/s-yata/marisa-trie.git $ cd marisa-trie $ autoreconf -i $ ./configure --enable-native-code $ make $ make install