# 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.

For more information about the Burkhard-Keller Tree, you can head here.

```
const 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:

```
const suggestions = terms.filter((term) => 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.

```
const tree = BKTtree.from(terms, levenshtein);
// We can now query the tree easily:
const suggestions = tree.search(2, query);
```

**N.B.** you should probably also check the PassjoinIndex 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.

```
const 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:

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

## Members

## Methods

*Mutation*

*Read*

### #.size

Total number of items stored in the tree.

```
const tree = new BKTree(distance);
tree.add('hello');
tree.size
>>> 1
```

### #.add

Adds a single item to the tree.

```
const tree = new BKTree(distance);
tree.add('hello');
```

### #.clear

Completely clears the tree of its items.

```
const tree = new BKTree(distance);
tree.add('hello');
tree.clear();
tree.size
>>> 0
```

### #.search

Returns every item in the tree within the desired distance.

```
const tree = new BKTree(distance);
tree.add('hello');
tree.add('mello');
tree.add('roman');
tree.search(1, 'vello');
>>> [
{item: 'hello', distance: 1}
{item: 'mello', distance: 1}
]
```