search-trie
v3.0.0
Published
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
Downloads
30,645
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 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
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 uses
buildCharacterTrie
to understand factual usage of an object. - eslint-plugin-relations - uses
buildWordTrie
to trim long imports to the nearest allowed - idea-exclude uses
buildWordTrie
to remove nested directories, ie creating trie containing shortest versions
Licence
MIT