PHP's levenshtein in JavaScript

Here’s what our current JavaScript equivalent to PHP's levenshtein looks like.

module.exports = function levenshtein (s1, s2, costIns, costRep, costDel) {
// discuss at: https://locutus.io/php/levenshtein/
// original by: Carlos R. L. Rodrigues (https://www.jsfromhell.com)
// bugfixed by: Onno Marsman (https://twitter.com/onnomarsman)
// revised by: Andrea Giammarchi (https://webreflection.blogspot.com)
// reimplemented by: Brett Zamir (https://brett-zamir.me)
// reimplemented by: Alexander M Beedie
// reimplemented by: Rafał Kukawski (https://blog.kukawski.pl)
// example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld')
// returns 1: 3
// example 2: levenshtein("carrrot", "carrots")
// returns 2: 2
// example 3: levenshtein("carrrot", "carrots", 2, 3, 4)
// returns 3: 6
// var LEVENSHTEIN_MAX_LENGTH = 255 // PHP limits the function to max 255 character-long strings
costIns = costIns == null ? 1 : +costIns
costRep = costRep == null ? 1 : +costRep
costDel = costDel == null ? 1 : +costDel
if (s1 === s2) {
return 0
}
const l1 = s1.length
const l2 = s2.length
if (l1 === 0) {
return l2 * costIns
}
if (l2 === 0) {
return l1 * costDel
}
// Enable the 3 lines below to set the same limits on string length as PHP does
// if (l1 > LEVENSHTEIN_MAX_LENGTH || l2 > LEVENSHTEIN_MAX_LENGTH) {
// return -1;
// }
let split = false
try {
split = !('0')[0]
} catch (e) {
// Earlier IE may not support access by string index
split = true
}
if (split) {
s1 = s1.split('')
s2 = s2.split('')
}
let p1 = new Array(l2 + 1)
let p2 = new Array(l2 + 1)
let i1, i2, c0, c1, c2, tmp
for (i2 = 0; i2 <= l2; i2++) {
p1[i2] = i2 * costIns
}
for (i1 = 0; i1 < l1; i1++) {
p2[0] = p1[0] + costDel
for (i2 = 0; i2 < l2; i2++) {
c0 = p1[i2] + ((s1[i1] === s2[i2]) ? 0 : costRep)
c1 = p1[i2 + 1] + costDel
if (c1 < c0) {
c0 = c1
}
c2 = p2[i2] + costIns
if (c2 < c0) {
c0 = c2
}
p2[i2 + 1] = c0
}
tmp = p1
p1 = p2
p2 = tmp
}
c0 = p1[l2]
return c0
}
[ View on GitHub | Edit on GitHub | Source on GitHub ]

How to use

You you can install via npm install locutus and require it via require('locutus/php/strings/levenshtein'). You could also require the strings module in full so that you could access strings.levenshtein instead.

If you intend to target the browser, you can then use a module bundler such as Parcel, webpack, Browserify, or rollup.js. This can be important because Locutus allows modern JavaScript in the source files, meaning it may not work in all browsers without a build/transpile step. Locutus does transpile all functions to ES5 before publishing to npm.

A community effort

Not unlike Wikipedia, Locutus is an ongoing community effort. Our philosophy follows The McDonald’s Theory. This means that we don't consider it to be a bad thing that many of our functions are first iterations, which may still have their fair share of issues. We hope that these flaws will inspire others to come up with better ideas.

This way of working also means that we don't offer any production guarantees, and recommend to use Locutus inspiration and learning purposes only.

Examples

Please note that these examples are distilled from test cases that automatically verify our functions still work correctly. This could explain some quirky ones.

#codeexpected result
1levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld')3
2levenshtein("carrrot", "carrots")2
3levenshtein("carrrot", "carrots", 2, 3, 4)6

« More PHP strings functions


Star