-
Notifications
You must be signed in to change notification settings - Fork 4
/
LevenshteinDistance.js
60 lines (50 loc) · 1.52 KB
/
LevenshteinDistance.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// Levenshtein distance algorithm
// edited from https://github.com/sindresorhus/leven
const arr = []
const charCodeCache = []
const getLevenshteinDistance = (a, b) => {
if (a === b) return 0
// Swapping the strings if `a` is longer than `b` so we know which one is the shortest & which one is the longest
if (a.length > b.length) [ a, b ] = [ b, a ]
// Performing suffix trimming: We can linearly drop suffix common to both strings since they don't increase distance at all
// Note: `~-` is the bitwise way to perform a `- 1` operation
let aLen = a.length
let bLen = b.length
while (aLen > 0 && (a.charCodeAt(~-aLen) === b.charCodeAt(~-bLen))) {
aLen--
bLen--
}
// Performing prefix trimming: We can linearly drop prefix common to both strings since they don't increase distance at all
let start = 0
while (start < aLen && (a.charCodeAt(start) === b.charCodeAt(start))) start++
aLen -= start
bLen -= start
if (aLen === 0) return 0
let i = 0
while (i < aLen) {
charCodeCache[ i ] = a.charCodeAt(start + i)
arr[ i ] = ++i
}
let bCharCode, ret, tmp, tmp2
let j = 0
while (j < bLen) {
bCharCode = b.charCodeAt(start + j)
tmp = j++
ret = j
for (i = 0; i < aLen; i++) {
tmp2 = bCharCode === charCodeCache[ i ]
? tmp
: tmp + 1
tmp = arr[ i ]
ret = arr[ i ] = tmp > ret
? tmp2 > ret
? ret + 1
: tmp2
: tmp2 > tmp
? tmp + 1
: tmp2
}
}
return ret
}
export { getLevenshteinDistance }