Google Git
Sign in
android / platform / external / marisa-trie / d3f09fc
commitd3f09fc9e9b9bf78eec13e1b8dac5b6e4e313454[log] [tgz]
authorSusumu Yata <susumu.yata@gmail.com>Fri Mar 18 04:02:44 2016 +0900
committerSusumu Yata <susumu.yata@gmail.com>Fri Mar 18 04:02:44 2016 +0900
tree25f7d49445fc8e32aa7ede45fc33d72b66027d28
parent92f1bf2a873881cc85c3191f68d5b954c5bf7dcc [diff]
Add a missing Makefile.
1 file changed
tree: 25f7d49445fc8e32aa7ede45fc33d72b66027d28
  1. bindings/
  2. docs/
  3. include/
  4. lib/
  5. tests/
  6. tools/
  7. vs2008/
  8. .gitignore
  9. AUTHORS
  10. ChangeLog
  11. configure.ac
  12. COPYING
  13. INSTALL
  14. Makefile.am
  15. marisa.pc.in
  16. NEWS
  17. README.md
README.md

Project name

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

Documentation

Source code license

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