# marisa-trie: a space-efficient static trie in C++ > MARISA is a static, space-efficient trie, and libmarisa is the C++ library that implements it together with command line tools for building and operating the dictionaries. It suits anyone holding a large read-only key set such as a dictionary or an identifier table, and its appeal is size: on a Wikipedia title list it is roughly a third of the size of the nearest alternative in the comparison. **s-yata/marisa-trie** — MARISA: Matching Algorithm with Recursively Implemented StorAge - Repository: https://github.com/s-yata/marisa-trie - Stars: 635 · Forks: 104 - Language: C++ - License: NOASSERTION - Published: 2026-10-21 · Updated: 2026-10-21 · Language: en - Canonical page: https://hysenlabs.com/projects/s-yata-marisa-trie ## What MARISA is: a trie optimised for static dictionaries MARISA stands for Matching Algorithm with Recursively Implemented StorAge, and the README describes it as a static and space-efficient trie data structure. libmarisa is the C++ library that provides an implementation of it, and the package of libmarisa also contains a set of command line tools for building and operating a MARISA-based dictionary. The word static is the whole design constraint, and it is a constraint rather than a limitation in disguise. A static trie is built once and then queried, and MARISA's contribution is a representation that stores that fixed set of keys in a fraction of the space a conventional trie or a double-array implementation would use. The tradeoff is that adding a key means building a new dictionary. That is exactly the shape of the problems MARISA fits. Dictionaries, word lists, identifier tables, domain name sets, chromosome or taxonomy names: large sets of keys that are read far more often than they are written. A trie also buys you prefix queries for free, which is what makes it useful for autocomplete, and MARISA keeps that while shrinking the footprint. The project comes from s-yata, with English and Japanese documentation on the project site, and the repository layout is a conventional C++ library with the expected parts: include/ for the public headers, lib/ for the implementation, tools/ for the command line programs, bindings/ for language bindings, tests/, cmake/, a CMakeLists.txt, a pkg-config template in marisa.pc.in, a CMake package template in Marisa.cmake.in, and both .clang-format and .clang-tidy configuration files. The latest version is 0.3.1, and the published releases are v0.3.1 from 2025-07-20, v0.3.0 from 2025-05-26 and v0.2.7 from 2025-05-17. The last push to the repository was on 2026-07-28 and the repository is not archived. ## The four operations a MARISA dictionary supports The README lists what a MARISA-based dictionary can do, and the list is where the difference from a plain key-value store shows up. Lookup is to check whether or not a given string exists in a dictionary. That is the ordinary operation, and the one a hash table would also do. Reverse lookup is to restore a key from its ID. That is the operation that makes MARISA more than a set of strings: the dictionary assigns identifiers to keys, and those identifiers are what a compact on-disk format can store, so a record can reference key 4711 and the dictionary turns it back into the string. That is the property that makes the structure useful in indexes and compressed formats where the key itself is the expensive part. Common prefix search is to find keys from prefixes of a given string. Note the direction: given a longer string, it returns the keys that are prefixes of it. That is the operation you want for a typeahead that matches what the user has typed so far against a dictionary of known completions. Predictive search is to find keys starting with a given string, which is the mirror image: given a shorter string, return everything that continues it. That is the operation behind autocomplete over a large vocabulary. Between them, the two search directions cover the two halves of prefix matching, and they are the reason a trie is used here rather than a sorted list or a hash table, neither of which can answer them without scanning. ## The size advantage, measured on Wikipedia titles The README's argument for the structure is a measurement, and it uses a dataset that anyone can reproduce. The input is the file enwiki-20121101-all-titles-in-ns0.gz, and the contents are all page titles of English Wikipedia as of November 2012. That is 9,805,576 keys, and the plain size of the data is 200,435,403 bytes, or 54,933,690 bytes gzipped. The comparison is between three implementations of a trie: | 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 | The numbers are the argument. The MARISA dictionary is smaller than the gzipped input itself, at 50.7 megabytes against 54.9 megabytes for the compressed original, while the compacted double-array implementation needs 376.6 megabytes and the LOUDS-based one 127.7 megabytes. Against the closest alternative that is roughly a factor of two and a half, and against the double-array implementation something closer to seven. The honest caveat is that the input is page titles: short, highly overlapping strings with a shared vocabulary structure, which is close to the worst case for a naive trie and close to the best case for a structure that exploits shared suffixes and recursive structure. If your keys are random identifiers rather than words, the relative advantage will be different, and the README does not claim otherwise. ## Building and installing with CMake, library or tools only The build is standard CMake, and the README's instructions are short enough to follow exactly. You get the latest version with git clone, and then build and install libmarisa and its command line tools via cmake. ```bash $ git clone https://github.com/s-yata/marisa-trie.git $ cd marisa-trie $ cmake -S. -Bbuild-rel -DCMAKE_BUILD_TYPE=Release -DENABLE_NATIVE_CODE=ON -DBUILD_TESTING=OFF $ cmake --build build-rel $ sudo cmake --install build-rel ``` Two of those options are worth understanding. ENABLE_NATIVE_CODE=ON asks the build to compile with the host's instruction set, which is what you want for a dictionary library that will run on the same machine you built it on, and a bad idea if you ship the binary to a different CPU. BUILD_TESTING=OFF skips the test targets, which is what you want for an installation build. The install step is component-aware, which is the useful part. To install just the library without the binaries: ```bash $ sudo cmake --install build-rel --component Library ``` And to install just the binaries: ```bash $ sudo cmake --install build-rel --component Binaries ``` That matters for packaging. A service that only links libmarisa does not need the command line tools on the target machine, and a container image that only runs the tools does not need the development files. The same component machinery is also what a distribution packager would use to split the package into library and tools pieces, and the marisa.pc.in file in the repository is the pkg-config template that lets a dependent project find the installed library the ordinary way. ## Licensing, tools and where MARISA is the wrong choice On licensing, the source code is offered under a dual licence: BSD-2-Clause OR LGPL-2.1-or-later, with the details in the COPYING file. The project itself carries a licence entry that the hosting platform cannot classify, so the LICENSE file in the repository is the authority to read rather than a badge on the page. A dual licence like this lets you pick the terms that suit your distribution model, since the permissive option is there when you want it and the LGPL option when you want to be explicit about how modifications are shared. The tools in the package cover building and operating a dictionary, and the README's documentation links point to a project site with both English and Japanese versions of the documentation. The first wrong case is a changing key set. MARISA is static, so a dictionary that gains or loses keys means rebuilding it and redistributing it. If your keys change continuously, a dynamic structure is the right answer, and the space advantage does not help you. The second wrong case is a small key set. If a thousand keys fit in a hash table in a few kilobytes, the engineering cost of a build step, a static artefact and a library is not repaid by the memory you saved. The third wrong case is a workload with no prefix queries. If you only ever ask whether a key exists, a compact hash table or a sorted array is simpler and faster, and the reverse lookup property, which is MARISA's most distinctive feature, goes unused. The realistic alternative is one of the two alternatives in the README's own comparison table: a compacted double-array trie, which is fast to look up but far larger, or a LOUDS-based trie, which sits in between on size. The difference in approach between them is the representation: MARISA stores the structure recursively rather than as a flat array of indices, which is what compresses the repeated suffix structure that dominates a large word list, at the cost of a more expensive build. ## Conclusion marisa-trie earns its place wherever a large key set is looked up often and rarely changed, because the whole point of the structure is that the static layout costs less memory than a dynamic trie while still answering prefix queries, and the size difference on a ten-million-key dictionary is not marginal. It is the wrong choice for a set that changes every day, since building a new dictionary is a rebuild rather than an update, and it is the wrong choice for a small key set where memory was never the problem. Verify first that the compression ratio holds for your own keys, since the published figure comes from English Wikipedia page titles and identifier-shaped data may compress differently, that your build links the native code path only on the CPUs you actually deploy on, and which of the two source licences your distribution model can live with. ## FAQ ### What is MARISA and what does libmarisa provide? MARISA, Matching Algorithm with Recursively Implemented StorAge, is a static and space-efficient trie data structure, and libmarisa is the C++ library that implements it. The package also contains a set of command line tools for building and operating a MARISA-based dictionary. ### Which searches does a MARISA dictionary support? Four: lookup, which checks whether a string exists; reverse lookup, which restores a key from its ID; common prefix search, which finds keys that are prefixes of a given string; and predictive search, which finds keys starting with a given string. ### How do I build and install marisa-trie? Clone the repository, then configure with cmake using -S. -Bbuild-rel -DCMAKE_BUILD_TYPE=Release -DENABLE_NATIVE_CODE=ON -DBUILD_TESTING=OFF, build with cmake --build build-rel, and install with sudo cmake --install build-rel. The install supports components, so --component Library installs only the library and --component Binaries only the command line tools. ### How much smaller is a MARISA dictionary than the alternatives? On the README's dataset of 9,805,576 English Wikipedia page titles, marisa-trie takes 50,753,560 bytes against 127,727,058 for tx-trie and 376,613,888 for darts-clone. The gzipped input itself is 54,933,690 bytes. ### Under what licence is marisa-trie released? The source code is offered under BSD-2-Clause OR LGPL-2.1-or-later, with the details in the COPYING file. The project entry itself carries a licence that the hosting platform cannot classify, so the LICENSE file in the repository is the document to check. ### What is the latest version of marisa-trie? Version 0.3.1, published on 2025-07-20, preceded by v0.3.0 on 2025-05-26 and v0.2.7 on 2025-05-17. The last push to the repository was on 2026-07-28 and the repository is not archived. ## Sources - [Issues](https://github.com/s-yata/marisa-trie/issues) - [README](https://github.com/s-yata/marisa-trie/blob/master/README.md) - [Releases](https://github.com/s-yata/marisa-trie/releases) - [s-yata/marisa-trie on GitHub](https://github.com/s-yata/marisa-trie) --- Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/s-yata-marisa-trie