#trie #double-array #nlp #text #search

no-std crawdad

Crawdad: ChaRActer-Wise Double-Array Dictionary

6 releases (3 breaking)

0.4.0 Sep 2, 2022
0.3.0 Aug 1, 2022
0.2.1 Jun 4, 2022
0.2.0 Apr 23, 2022
0.1.1 Apr 13, 2022

#1138 in Text processing

Download history 47/week @ 2024-01-03 154/week @ 2024-01-10 134/week @ 2024-01-17 152/week @ 2024-01-24 145/week @ 2024-01-31 91/week @ 2024-02-07 291/week @ 2024-02-14 230/week @ 2024-02-21 202/week @ 2024-02-28 239/week @ 2024-03-06 219/week @ 2024-03-13 263/week @ 2024-03-20 216/week @ 2024-03-27 211/week @ 2024-04-03 138/week @ 2024-04-10 156/week @ 2024-04-17

769 downloads per month
Used in 2 crates (via vibrato)


1.5K SLoC

🦞 Crawdad: ChaRActer-Wise Double-Array Dictionary

Crates.io Documentation Build Status


Crawdad is a library of natural language dictionaries using character-wise double-array tries. The implementation is optimized for strings of multibyte-characters, and you can enjoy fast text processing on strings such as Japanese or Chinese.

For example, on a large Japanese dictionary of IPADIC+Neologd, Crawdad has a better time-space tradeoff than other Rust libraries.

The detailed experimental settings and other results are available on Wiki.

What can do

  • Key-value mapping: Crawdad stores a set of string keys with mapping arbitrary integer values.
  • Exact match: Crawdad supports a fast lookup for an input key.
  • Common prefix search: Crawdad supports fast common prefix search that can be used to enumerate all keys appearing in a text.

Data structures

Crawdad contains the two trie implementations:

  • crawdad::Trie is a standard trie form that often provides the fastest queries.
  • crawdad::MpTrie is a minimal-prefix trie form that is memory-efficient for long strings.


Licensed under either of

at your option.

For softwares under bench/data, follow the license terms of each software.


The initial version of this software was developed by LegalForce, Inc., but not an officially supported LegalForce product.


Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

No runtime deps