Skip to content

Dynamic word set with accelerated exact and fuzzy search based on trie data structure.

License

Notifications You must be signed in to change notification settings

SergeyFromHell/fuzzytrie

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 

Repository files navigation

fuzzytrie

Dynamic word set with accelerated exact and fuzzy search based on trie data structure.

Usage

Create FuzzyTrie

FuzzyTrie constructor has no parameters:

var FuzzyTrie = require('fuzzytrie');

var trie = new FuzzyTrie();

Insert

To insert into the trie use "add" method with single argument:

trie.add('hello');

Remove

Use "delete" method to remove a word from the trie:

trie.delete('hello');

Check existence

Use "has" to detemine that trie contains a word:

trie.add('word');
var b = trie.has('word'); // b == true
trie.delete('word');
b = trie.has('word'); // b == false

Search

Although you can use "has" to do exact search, there is also a method called "find" that can be used to find all words in the trie that "approximately" equals to the given word. In fact, "find" implements fuzzy search with UNRESTRICTED Damerau-Levenshtein Distance metric. It's accelerated with underlying trie data structure so it's performance is sublinear (in terms of number of words inside the trie). Maximal distance from given word is passed with second parameter of "find". It returns JavaScript Object with words within given maximal distance as keys and their distances as values. If there are no words in the trie within given distance, it returns empty Object({}).

var maxDistance = 2;
var result = trie.find('hello',maxDistance);
// result == { <word1>: <distance from 'hello' to word1>, <word2>: <distance from 'hello' to word2>,... };

You should remember that performance of the "find" method is critically depends on the maximal distance parameter.

Clear

You can clear the trie with "clear" method:

trie.clear();

All

Array of all words contained in the trie can be acquired with "all".

var a = trie.all();
// a = [...];

Empty

You can check that trie does not contain any word with "empty" method:

var b = trie.empty();
// b == true if trie is empty (has no words)
// else, b == false

About

Dynamic word set with accelerated exact and fuzzy search based on trie data structure.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published