Skip to content

Instantly share code, notes, and snippets.

@OriPekelman OriPekelman/dlq.js
Created May 31, 2015

Embed
What would you like to do?
quantized Damreau Lehvenstein in Javascript
(function() {
'use strict';
/**
* Extend an Object with another Object's properties.
*
* The source objects are specified as additional arguments.
*
* @param dst Object the object to extend.
*
* @return Object the final object.
*/
var _extend = function(dst) {
var sources = Array.prototype.slice.call(arguments, 1);
for (var i=0; i<sources.length; ++i) {
var src = sources[i];
for (var p in src) {
if (src.hasOwnProperty(p)) dst[p] = src[p];
}
}
return dst;
};
/**
* Based on the algorithm at http://en.wikipedia.org/wiki/Levenshtein_distance.
*/
var Levenshtein = {
/**
* Calculate levenshtein distance of the two strings.
*
* @param str1 String the first string.
* @param str2 String the second string.
* @return Integer the levenshtein distance (0 and above).
*/
get: function(str1, str2) {
// base cases
if (str1 === str2) return 0;
if (str1.length === 0) return str2.length;
if (str2.length === 0) return str1.length;
// two rows
var prevRow = new Array(str2.length + 1),
curCol, nextCol, i, j, tmp;
// initialise previous row
for (i=0; i<prevRow.length; ++i) {
prevRow[i] = i;
}
// calculate current row distance from previous row
for (i=0; i<str1.length; ++i) {
nextCol = i + 1;
for (j=0; j<str2.length; ++j) {
curCol = nextCol;
// substution
nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
// insertion
tmp = curCol + 1;
if (nextCol > tmp) {
nextCol = tmp;
}
// deletion
tmp = prevRow[j + 1] + 1;
if (nextCol > tmp) {
nextCol = tmp;
}
// copy current col value into previous (in preparation for next iteration)
prevRow[j] = curCol;
}
// copy last col value into previous (in preparation for next iteration)
prevRow[j] = nextCol;
}
return nextCol;
},
/**
* Asynchronously calculate levenshtein distance of the two strings.
*
* @param str1 String the first string.
* @param str2 String the second string.
* @param cb Function callback function with signature: function(Error err, int distance)
* @param [options] Object additional options.
* @param [options.progress] Function progress callback with signature: function(percentComplete)
*/
getAsync: function(str1, str2, cb, options) {
options = _extend({}, {
progress: null
}, options);
// base cases
if (str1 === str2) return cb(null, 0);
if (str1.length === 0) return cb(null, str2.length);
if (str2.length === 0) return cb(null, str1.length);
// two rows
var prevRow = new Array(str2.length + 1),
curCol, nextCol,
i, j, tmp,
startTime, currentTime;
// initialise previous row
for (i=0; i<prevRow.length; ++i) {
prevRow[i] = i;
}
nextCol = 1;
i = 0;
j = -1;
var __calculate = function() {
// reset timer
startTime = new Date().valueOf();
currentTime = startTime;
// keep going until one second has elapsed
while (currentTime - startTime < 1000) {
// reached end of current row?
if (str2.length <= (++j)) {
// copy current into previous (in preparation for next iteration)
prevRow[j] = nextCol;
// if already done all chars
if (str1.length <= (++i)) {
return cb(null, nextCol);
}
// else if we have more left to do
else {
nextCol = i + 1;
j = 0;
}
}
// calculation
curCol = nextCol;
// substution
nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
// insertion
tmp = curCol + 1;
if (nextCol > tmp) {
nextCol = tmp;
}
// deletion
tmp = prevRow[j + 1] + 1;
if (nextCol > tmp) {
nextCol = tmp;
}
// copy current into previous (in preparation for next iteration)
prevRow[j] = curCol;
// get current time
currentTime = new Date().valueOf();
}
// send a progress update?
if (null !== options.progress) {
try {
options.progress.call(null, (i * 100.0/ str1.length));
} catch (err) {
return cb('Progress callback: ' + err.toString());
}
}
// next iteration
setTimeout(__calculate(), 0);
};
__calculate();
}
};
// amd
if (typeof define !== "undefined" && define !== null && define.amd) {
define(function() {
return Levenshtein;
});
}
// commonjs
else if (typeof module !== "undefined" && module !== null) {
module.exports = Levenshtein;
}
// web worker
else if (typeof self !== "undefined" && typeof self.postMessage === 'function' && typeof self.importScripts === 'function') {
self.Levenshtein = Levenshtein;
}
// browser main thread
else if (typeof window !== "undefined" && window !== null) {
window.Levenshtein = Levenshtein;
}
}());
// Make first string the same length as second string
String.downSample = function (__this, that) {
var thisLength = __this.length,
thatLength = that.length;
var new_this = [];
if (thisLength === thatLength) return that;
aspectRatio = thisLength / thatLength;
for (j = 0; j <= thatLength; ++j) {
pos = Math.floor(j * aspectRatio);
new_this[j] = __this[pos];
}
return new_this.join("");
}
a = "NNNWWWSSS";
b = "NNNNNNNNNNNWWWWWWWWWSSSSSSS";
aa = String.downSample(a, b);
res = Levenshtein.get(aa,b);
console.log(res);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.