Google Git
Sign in
android / platform / external / marisa-trie / refs/tags/android-15.0.0_r16
tagd5eae6400fe100d22fe538f0e80ea756e86fa0f4
taggerThe Android Open Source Project <initial-contribution@android.com>Tue Feb 04 13:59:27 2025 -0800
objectc90fe3d1e4f69b3aebd24764868797e76f12dba4 
Android 15.0.0 Release 16 (AP4A.250205.002.B2)
commitc90fe3d1e4f69b3aebd24764868797e76f12dba4[log] [tgz]
authorXin Li <delphij@google.com>Fri Oct 08 08:59:48 2021 +0000
committerAutomerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>Fri Oct 08 08:59:48 2021 +0000
treef36e0f9da5855a1abb42f107a4e0733d79080e65
parent02c3e0d86dea74bd0cbab797d70d0b6899d1ea5f [diff]
parentd743d2b4f6f038eb5654b7fda1478958cf99db78 [diff]
[automerger skipped] Merge "Merge Android 12" am: 0056347f7d -s ours am: 1427082ca9 -s ours am: d6fb3b13f6 -s ours am: 0ba11cd54d -s ours am: d743d2b4f6 -s ours

am skip reason: Merged-In Ib84685c96ac6b9448656882a2ad963b7248f3804 with SHA-1 f1b61e748b is already in history

Original change: https://android-review.googlesource.com/c/platform/external/marisa-trie/+/1847633

Change-Id: Ia008903752f8943c32dde0a89cf4a6ceecc403fc
tree: f36e0f9da5855a1abb42f107a4e0733d79080e65
  1. bindings/
  2. docs/
  3. include/
  4. lib/
  5. m4/
  6. tests/
  7. tools/
  8. vs2008/
  9. LICENSE ⇨ COPYING.md
  10. .gitignore
  11. Android.bp
  12. AUTHORS
  13. configure.ac
  14. COPYING.md
  15. Makefile.am
  16. marisa.pc.in
  17. METADATA
  18. MODULE_LICENSE_BSD
  19. README.md
README.md

README

Project name

marisa-trie

Project summary

MARISA: Matching Algorithm with Recursively Implemented StorAge

Latest version

0.2.6

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)
ImplementationSize (bytes)Remarks
darts-clone376,613,888Compacted double-array trie
tx-trie127,727,058LOUDS-based trie
marisa-trie50,753,560MARISA trie

Documentation

Build instructions

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

Source code license

  • The BSD 2-clause License
  • The LGPL 2.1 or any later version