levenshtein-search

A Javascript library for fuzzy substring search.

Features

* Optimized for many use cases, including:
Long sub-strings with small* max. distance
Long sub-strings with large* max. distance
* Non-trivial, rarely implemented algorithms
* Simple interface, automatically uses the most appropriate algorithm.
* Extensive test suite
* No dependencies

Examples

#### fuzzySearch()

A generator function which yields all fuzzy matches of 'needle' in
'haystack', matching to within the given maximum Levenshtein distance.

``js
> [...fuzzySearch('PATTERN', '---PATERN---', 1)]
[ { start: 3, end: 9, dist: 1 } ]
> [...fuzzySearch('elephant', 'There is nothing relevant here', 1)]
[]
> [...fuzzySearch('elephant', 'There is nothing relevant here', 2)]
[ { start: 18, end: 25, dist: 2 } ]
> [...fuzzySearch('erors', 'Some text with errors in it', 1)]
[ { start: 17, end: 21, dist: 1 },
{ start: 15, end: 21, dist: 1 } ]
> var text = 'There are many strange words in this world, not all worth mentioning.'
> [...fuzzySearch('word', text, 0)]
[ { start: 23, end: 27, dist: 0 } ]
> [...fuzzySearch('word', text, 1)]
[ { start: 24, end: 27, dist: 1 },
{ start: 23, end: 27, dist: 0 },
{ start: 37, end: 41, dist: 1 },
{ start: 37, end: 42, dist: 1 },
{ start: 52, end: 56, dist: 1 } ]
> [...fuzzySearch('warts', text, 1)]
[]
> [...fuzzySearch('warts', text, 2)]
[ { start: 23, end: 28, dist: 2 },
{ start: 52, end: 57, dist: 2 } ]
`

#### editDistance()

Computes the edit distance, a.k.a. the Levenshtein distance, between
two strings.

`js
> editDistance('elephant', 'relevant')
3
> editDistance('same', 'same')
0
> editDistance('error', 'erorr')
2
`

#### isEditDistanceNoGreaterThan()

This is optimized to do less computation than editDistance(),
much less when the given maximum distance is small compared to the
lengths of the inputs.

`js
> isEditDistanceNoGreaterThan('elephant', 'relevant', 3)
true
> isEditDistanceNoGreaterThan('elephant', 'relevant', 2)
false
``

Notes

1. This is a partial Javascript port of the
Python 'fuzzysearch' library,
which is written by the same author and licensed under similar terms.
2. Filtering of redundant results is currently not implemented.

Licensing

© 2018 Tal Einat.

Licensed under the terms of
the MIT license.
See LICENSE for details.