#  [](https://www.npmjs.com/package/@thi.ng/trie)  [](https://mastodon.thi.ng/@toxi) > [!NOTE] > This is one of 216 standalone projects. LLM-free, human-made and > cared for software, maintained as part of the > [@thi.ng/umbrella](https://codeberg.org/thi.ng/umbrella/) ecosystem and > anti-framework. > > 🚀 Please help me to work full-time on these projects by [sponsoring > me](https://codeberg.org/thi.ng/umbrella/src/branch/develop/CONTRIBUTING.md#donations). > Thank you! ❤️ - [About](#about) - [TrieMap](#triemap) - [MultiTrie](#multitrie) - [Status](#status) - [Related packages](#related-packages) - [Installation](#installation) - [Dependencies](#dependencies) - [API](#api) - [Authors](#authors) - [License](#license) ## About Trie-based ES6-like Map data structures with prefix search/query support. This package contains functionality which was previously part of and has been extracted from the [@thi.ng/associative](https://thi.ng/associative) package. ### TrieMap [Tries](https://en.wikipedia.org/wiki/Trie) (also called Prefix maps) are useful data structures for search based use cases, auto-complete, text indexing etc. and provide partial key matching (prefixes), suffix iteration for a common prefix, longest matching prefix queries etc. The implementations here too feature ES6 Map-like API, similar to other types in this package, with some further trie-specific additions. ```ts tangle:export/readme-1.ts import { defTrieMap } from "@thi.ng/trie"; // construct trie from given key-value pairs (optional) const trie = defTrieMap([ ["hey", "en"], ["hello", "en"], ["hallo", "de"], ["hallo", "de-at"], ["hola", "es"], ["hold", "en"], ["hej", "se"], ]); // find longest known prefix given key console.log(trie.knownPrefix("hole")); // "hol" // all known keys console.log([...trie.keys()]) // [ "hold", "hola", "hallo", "hej", "hello", "hey" ] // all keys starting with given prefix console.log([...trie.keys("he")]) // [ "hej", "hello", "hey" ] // suffixes of given key only console.log([...trie.keys("he", false)]) // [ "j", "llo", "y" ] // values of keys starting with prefix console.log([...trie.values("hol")]); // [ "en", "es" ] ``` ### MultiTrie The `MultiTrie` is similar to `TrieMap`, but uses array-like keys and supports multiple values per key. Values are stored in sets whose implementation can be configured via ctor options (e.g. using custom ES6-like Sets with value-based equality semantics from the [thi.ng/associative](https://thi.ng/associative) package). ```ts tangle:export/readme-2.ts import { defMultiTrie } from "@thi.ng/trie"; import { ArraySet } from "@thi.ng/associative"; // init w/ custom value set type (here purely for illustration) const t = defMultiTrie(null, { values: () => new ArraySet() }); t.add("to be or not to be".split(" "), 1); t.add("to be or not to be".split(" "), 2); t.add("to be and to live".split(" "), 3); console.log(t.get("to be or not to be".split(" "))); // Set(2) { 1, 2 } console.log(t.knownPrefix(["to", "be", "not"])); // [ "to", "be" ] // suffixes for given prefix console.log([...t.keys(["to", "be"], false)]); // [["and", "to", "live"], ["or", "not", "to", "be"]] ``` ## Status **STABLE** - used in production [Search or submit any issues for this package](https://codeberg.org/thi.ng/umbrella/issues?q=%5Btrie%5D) ## Related packages - [@thi.ng/associative](https://codeberg.org/thi.ng/umbrella/src/branch/develop/packages/associative) - ES Map/Set-compatible implementations with customizable equality semantics & supporting operations ## Installation ```bash yarn add @thi.ng/trie ``` ESM import: ```ts import * as trie from "@thi.ng/trie"; ``` Browser ESM import: ```html ``` [JSDelivr documentation](https://www.jsdelivr.com/) For Node.js REPL: ```js const trie = await import("@thi.ng/trie"); ``` Package sizes (brotli'd, pre-treeshake): ESM: 1.21 KB ## Dependencies - [@thi.ng/api](https://codeberg.org/thi.ng/umbrella/src/branch/develop/packages/api) Note: @thi.ng/api is in _most_ cases a type-only import (not used at runtime) ## API [Generated API docs](https://docs.thi.ng/umbrella/trie/) ## Authors - [Karsten Schmidt](https://thi.ng) If this project contributes to an academic publication, please cite it as: ```bibtex @misc{thing-trie, title = "@thi.ng/trie", author = "Karsten Schmidt", note = "https://thi.ng/trie", year = 2020 } ``` ## License © 2020 - 2026 Karsten Schmidt // Apache License 2.0