# Mnemonist

## Burkhard-Keller Tree

A `BKTree` is a data structure that makes possible to make efficient fuzzy query using arbitrary distance metrics such as the Levenshtein distance.

``````var BKTree = require('mnemonist/bk-tree');
``````

## Use case

Let’s say we want to build an autocomplete system.

When the user inputs a string, we are going to search for every term we know being at most at a Levenshtein distance of 2 of the user’s query.

The naive method would be to “brute-force” the list of terms likewise:

``````var suggestions = terms.filter(term => {
return levenshtein(term, query) <= 2;
});
``````

But, even if this works with few terms, it will soon become hard to compute if the list of terms grows too much.

Burkhard-Keller trees solves this problem by indexing the list of terms such as it becomes efficient to query them using a distance metric.

``````var tree = BKTtree.from(terms, levenshtein);

// We can now query the tree easily:
var suggestions = tree.search(2, query);
``````

N.B. you should probably also check the SymSpell structure, which is able to perform the same kind of job but is even more efficient for this precise use case.

## Constructor

The `BKTree` takes a single argument being the distance metric to use.

``````var tree = new BKTree(distance);
``````

N.B. the given distance metric must return integers. As such, the Jaccard index, for instance, is not suitable to use with this data strucure.

What’s more, only a true metric can be used.

### Static #.from

Alternatively, one can build a `BKTree` from an arbitrary JavaScript iterable likewise:

``````var tree = BKTree.from(['hello', 'mello'], distance);
``````

## Methods

Mutation

### #.size

Total number of items stored in the tree.

``````var tree = new BKTree(distance);

tree.size
>>> 1
``````

Adds a single item to the tree.

``````var tree = new BKTree(distance);

``````

Completely clears the tree of its items.

``````var tree = new BKTree(distance);

tree.clear();

tree.size
>>> 0
``````

Returns every item in the tree within the desired distance.

``````var tree = new BKTree(distance);