-
-
Save bperel/3d7dad5d7a0370d52a42a6f898ec938f to your computer and use it in GitHub Desktop.
Levenshtein distance between two given strings implemented in JavaScript and usable as a Node.js module
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // https://gist.github.com/andrei-m/982927#gistcomment-1931258 looks like the fastest Levenshtein implementation | |
| const levenshtein = (a, b) => { | |
| if (a.length === 0) return b.length | |
| if (b.length === 0) return a.length | |
| let tmp, i, j, prev, val | |
| // swap to save some memory O(min(a,b)) instead of O(a) | |
| if (a.length > b.length) { | |
| tmp = a | |
| a = b | |
| b = tmp | |
| } | |
| row = Array(a.length + 1) | |
| // init the row | |
| for (i = 0; i <= a.length; i++) { | |
| row[i] = i | |
| } | |
| // fill in the rest | |
| for (i = 1; i <= b.length; i++) { | |
| prev = i | |
| for (j = 1; j <= a.length; j++) { | |
| if (b[i-1] === a[j-1]) { | |
| val = row[j-1] // match | |
| } else { | |
| val = Math.min(row[j-1] + 1, // substitution | |
| Math.min(prev + 1, // insertion | |
| row[j] + 1)) // deletion | |
| } | |
| row[j - 1] = prev | |
| prev = val | |
| } | |
| row[a.length] = prev | |
| } | |
| return row[a.length] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment