# search-trie

> A simple trie structure to perform prefix search on texts in O(n) time, where n - number of characters in searched word. > Trie is a basic Tree structure, also known as [prefix tree](https://en.wikipedia.org/wiki/Trie) Super simple, Super fast, super comp

Latest version **3.0.0** (published 2023-10-12) · MIT license · 0 weekly downloads

## Install

```sh
npm install search-trie
pnpm add search-trie
yarn add search-trie
bun add search-trie
```

## Health

**Score 30/100 (F)** — status: abandoned.

Positive: has types; esm support; no vulnerabilities; high quality score.

Warnings: low downloads.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 3.0.0 |
| Published | 2023-10-12 |
| First published | 2018-02-11 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | bundled |
| Module format | ESM + CommonJS |
| Node | >=10 |
| Dependencies | 1 |
| Unpacked size | 26.5 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 7 |
| Author | Anton Korzunov |
| Maintainers | kashey |

## Links

- npm: https://www.npmjs.com/package/search-trie
- Repository: https://github.com/theKashey/search-trie
- Homepage: https://github.com/theKashey/search-trie#readme
- Issues: https://github.com/theKashey/search-trie/issues
- npm.io page: https://npm.io/package/search-trie

## Dependencies (1)

- [tslib](https://npm.io/package/tslib.md) ^2.0.0

## Recent versions

- 3.0.0 (latest) — 2023-10-12
- 2.1.0 — 2021-12-12
- 2.0.1 — 2020-11-23
- 2.0.0 — 2020-11-03
- 1.1.0 — 2019-01-02
- 1.0.0 — 2018-02-11

## README

# search-trie

A simple trie structure to perform prefix search on texts in O(n) time, where n - number of characters in searched word.
> Trie is a basic Tree structure, also known as [prefix tree](https://en.wikipedia.org/wiki/Trie)
Super simple, Super fast, super compact - less then 0.5kb.


### Search-trie

The single purpose of this package is to find longest match between given strings and the search key.
For example:
- given a couple of directories (`/src`, `/src/a`, `/src/b`, `/src/b/c`)
- find the best match for a given file (`/src/b/c/index.tx` -> `/src/b/c`)

## Usage

This package provides two functions to build two different tries:
- `buildCharacterTrie` - to create "per character" trie. Working great if you need to search something in the compressed json (short names)
- `buildWordTrie` - to create trie where "word" is a key. Working great if there are many "long keys", for example directories you want to traverse faster
> one has more smaller nodes, another one has fewer larger ones. It's all about memory locality and algorithm сonvergence. 

They have almost identical API, and if performance matters - you need to benchmark your data to understand which one is more efficient

# Example
```ts
import {buildWordTrie} from 'search-trie';

// map package info into trie
// using word trie as we operate with directory names
const trie = buildWordTrie(
    packages.map(pkg => ({key: pkg.dir.split(path.sep), value: pkg})
);
    
// it's always possible to insert new data. But `delete` operation is not defined    
trie.put({key:'another/package', value: pkg})

// find longest (nearest to the search key) package. It will be a package containing this file
const getOwnerPackage = (fileName) => trie.findNearest(fileName).value;
```

# Used in
- [proxy-equal](https://github.com/theKashey/proxyequal/blob/c0e167b932eb948f9b3fb15b0a56b40e492413bb/src/objectTrie.js) uses `buildCharacterTrie` to understand factual usage of an object.
- [eslint-plugin-relations](https://github.com/theKashey/eslint-plugin-relations/blob/b80d8a4a6222107d59034bddaa5fe2cb14baab55/src/utils/mapping/mapping.ts#L31) - uses `buildWordTrie` to trim long imports to the nearest allowed
- [idea-exclude](https://github.com/theKashey/idea-exclude/blob/a5f886a8298b909ef08108efd68e348bd0fb7907/src/utils.ts#L10) uses `buildWordTrie` to remove nested directories, ie creating trie containing shortest versions

# Licence

MIT

---
_Source: https://npm.io/package/search-trie · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._