source: trip-planner-front/node_modules/yargs/lib/levenshtein.js@ 84d0fbb

Last change on this file since 84d0fbb was e29cc2e, checked in by Ema <ema_spirova@…>, 3 years ago

primeNG components

  • Property mode set to 100644
File size: 2.1 KB
Line 
1/*
2Copyright (c) 2011 Andrei Mackenzie
3
4Permission is hereby granted, free of charge, to any person obtaining a copy of
5this software and associated documentation files (the "Software"), to deal in
6the Software without restriction, including without limitation the rights to
7use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8the Software, and to permit persons to whom the Software is furnished to do so,
9subject to the following conditions:
10
11The above copyright notice and this permission notice shall be included in all
12copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION 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'use strict'
25// Compute the edit distance between the two given strings
26module.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}
Note: See TracBrowser for help on using the repository browser.