A Javascript library for fuzzy substring search.
- 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
A generator function which yields all fuzzy matches of 'needle' in 'haystack', matching to within the given maximum Levenshtein distance.
> [...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 } ]Computes the edit distance, a.k.a. the Levenshtein distance, between two strings.
> editDistance('elephant', 'relevant')
3
> editDistance('same', 'same')
0
> editDistance('error', 'erorr')
2This is optimized to do less computation than editDistance(),
much less when the given maximum distance is small compared to the
lengths of the inputs.
> isEditDistanceNoGreaterThan('elephant', 'relevant', 3)
true
> isEditDistanceNoGreaterThan('elephant', 'relevant', 2)
false- This is a partial Javascript port of the Python 'fuzzysearch' library, which is written by the same author and licensed under similar terms.
- Filtering of redundant results is currently not implemented.
© 2018 Tal Einat.
Licensed under the terms of the MIT license. See LICENSE for details.