Socket
Socket
Sign inDemoInstall

search-trie

Package Overview
Dependencies
1
Maintainers
1
Versions
6
Alerts
File Explorer

Advanced tools

Install Socket

Detect and block malicious and high-risk dependencies

Install

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


Version published
Maintainers
1
Weekly downloads
2,926
decreased by-29.24%

Weekly downloads

Readme

Source

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

FAQs

Last updated on 12 Oct 2023

Did you know?

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc