| 1 | # fastest-levenshtein :rocket:
|
|---|
| 2 | > Fastest JS/TS implemenation of [Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance).<br>
|
|---|
| 3 | > Measure the difference between two strings.
|
|---|
| 4 |
|
|---|
| 5 | [](https://travis-ci.org/ka-weihe/fastest-levenshtein)
|
|---|
| 6 | [](https://coveralls.io/github/ka-weihe/node-levenshtein?branch=master)
|
|---|
| 7 | [](https://lgtm.com/projects/g/ka-weihe/fastest-levenshtein/context:javascript)
|
|---|
| 8 | 
|
|---|
| 9 | ```bash
|
|---|
| 10 | $ npm i fastest-levenshtein
|
|---|
| 11 | ```
|
|---|
| 12 |
|
|---|
| 13 | ## Usage
|
|---|
| 14 | ### Node
|
|---|
| 15 | ```javascript
|
|---|
| 16 | const {distance, closest} = require('fastest-levenshtein')
|
|---|
| 17 |
|
|---|
| 18 | // Print levenshtein-distance between 'fast' and 'faster'
|
|---|
| 19 | console.log(distance('fast', 'faster'))
|
|---|
| 20 | //=> 2
|
|---|
| 21 |
|
|---|
| 22 | // Print string from array with lowest edit-distance to 'fast'
|
|---|
| 23 | console.log(closest('fast', ['slow', 'faster', 'fastest']))
|
|---|
| 24 | //=> 'faster'
|
|---|
| 25 | ```
|
|---|
| 26 |
|
|---|
| 27 | ### Deno
|
|---|
| 28 | ```javascript
|
|---|
| 29 | import {distance, closest} from 'https://deno.land/x/fastest_levenshtein/mod.ts'
|
|---|
| 30 |
|
|---|
| 31 | // Print levenshtein-distance between 'fast' and 'faster'
|
|---|
| 32 | console.log(distance('fast', 'faster'))
|
|---|
| 33 | //=> 2
|
|---|
| 34 |
|
|---|
| 35 | // Print string from array with lowest edit-distance to 'fast'
|
|---|
| 36 | console.log(closest('fast', ['slow', 'faster', 'fastest']))
|
|---|
| 37 | //=> 'faster'
|
|---|
| 38 | ```
|
|---|
| 39 |
|
|---|
| 40 | ## Benchmark
|
|---|
| 41 | I generated 500 pairs of strings with length N. I measured the ops/sec each library achieves to process all the given pairs. Higher is better.
|
|---|
| 42 |
|
|---|
| 43 | | Test Target | N=4 | N=8 | N=16 | N=32 | N=64 | N=128 | N=256 | N=512 | N=1024 |
|
|---|
| 44 | |---------------------------|-------|-------|-------|------|-------|-------|-------|-------|--------|
|
|---|
| 45 | | fastest-levenshtein | 44423 | 23702 | 10764 | 4595 | 1049 | 291.5 | 86.64 | 22.24 | 5.473 |
|
|---|
| 46 | | js-levenshtein | 21261 | 10030 | 2939 | 824 | 223 | 57.62 | 14.77 | 3.717 | 0.934 |
|
|---|
| 47 | | leven | 19688 | 6884 | 1606 | 436 | 117 | 30.34 | 7.604 | 1.929 | 0.478 |
|
|---|
| 48 | | fast-levenshtein | 18577 | 6112 | 1265 | 345 | 89.41 | 22.70 | 5.676 | 1.428 | 0.348 |
|
|---|
| 49 | | levenshtein-edit-distance | 22968 | 7445 | 1493 | 409 | 109 | 28.07 | 7.095 | 1.789 | 0.445 |
|
|---|
| 50 |
|
|---|
| 51 | ### Relative Performance
|
|---|
| 52 | This image shows the relative performance between `fastest-levenshtein` and `js-levenshtein` (the 2nd fastest). `fastest-levenshtein` is always a lot faster. y-axis shows "times faster".
|
|---|
| 53 |
|
|---|
| 54 | 
|
|---|
| 55 |
|
|---|
| 56 | ## License
|
|---|
| 57 | This project is licensed under the MIT License - see the [LICENSE.md](LICENSE.md) file for details
|
|---|
