1 | /*
|
2 | Copyright (c) 2011 Andrei Mackenzie
|
3 |
|
4 | Permission is hereby granted, free of charge, to any person obtaining a copy of
|
5 | this software and associated documentation files (the "Software"), to deal in
|
6 | the Software without restriction, including without limitation the rights to
|
7 | use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
|
8 | the Software, and to permit persons to whom the Software is furnished to do so,
|
9 | subject to the following conditions:
|
10 |
|
11 | The above copyright notice and this permission notice shall be included in all
|
12 | copies or substantial portions of the Software.
|
13 |
|
14 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
15 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
|
16 | FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
|
17 | COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
|
18 | IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
|
19 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
20 | */
|
21 |
|
22 | // levenshtein distance algorithm, pulled from Andrei Mackenzie's MIT licensed.
|
23 | // gist, which can be found here: https://gist.github.com/andrei-m/982927
|
24 |
|
25 | // Compute the edit distance between the two given strings
|
26 | module.exports = function levenshtein (a, b) {
|
27 | if (a.length === 0) return b.length
|
28 | if (b.length === 0) return a.length
|
29 |
|
30 | const matrix = []
|
31 |
|
32 | // increment along the first column of each row
|
33 | let i
|
34 | for (i = 0; i <= b.length; i++) {
|
35 | matrix[i] = [i]
|
36 | }
|
37 |
|
38 | // increment each column in the first row
|
39 | let j
|
40 | for (j = 0; j <= a.length; j++) {
|
41 | matrix[0][j] = j
|
42 | }
|
43 |
|
44 | // Fill in the rest of the matrix
|
45 | for (i = 1; i <= b.length; i++) {
|
46 | for (j = 1; j <= a.length; j++) {
|
47 | if (b.charAt(i - 1) === a.charAt(j - 1)) {
|
48 | matrix[i][j] = matrix[i - 1][j - 1]
|
49 | } else {
|
50 | matrix[i][j] = Math.min(matrix[i - 1][j - 1] + 1, // substitution
|
51 | Math.min(matrix[i][j - 1] + 1, // insertion
|
52 | matrix[i - 1][j] + 1)) // deletion
|
53 | }
|
54 | }
|
55 | }
|
56 |
|
57 | return matrix[b.length][a.length]
|
58 | }
|