GitHub - isabelmu/marisa-trie: Automatically exported from code.google.com/p/marisa-trie

isabelmu / marisa-trie Public

Notifications You must be signed in to change notification settings
Fork 0
Star 0

Automatically exported from code.google.com/p/marisa-trie

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 82 Commits
bindings		bindings
docs		docs
lib		lib
tests		tests
tools		tools
vs2008		vs2008
AUTHORS		AUTHORS
COPYING		COPYING
ChangeLog		ChangeLog
INSTALL		INSTALL
Makefile.am		Makefile.am
NEWS		NEWS
README		README
configure.ac		configure.ac
marisa.pc.in		marisa.pc.in

Repository files navigation

- 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