• 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