Hacks and stuff

# Linear Edit Distance/Needleman-Wunsch calculation in Javascript

The project I am working on requires me to make a function to calculate edit distance between two arbitrary sentences. I just happen to have a very good understand on this topic and hereby write a function to do just that, in linear memory requirement, in other words Hirschberg's algorithm. I actually have a much beefier implementation with a lot of clever tricks of the same problem in CUDA, which was published last year.

You can adapt, edit, improve, whatever you want to do with this code. I would appreciate it if you could credit me, but that's optional. I know you could just have come up with this yourself, but why waste time duplicating efforts?

``````// Needleman-Wunsch linear alignment of two arrays
// 2015 Huan Truong - htruong@tnhh.net
function align(a, b) {
var current = [];
var lookback = [];

var nw_match = 2;
var nw_mismatch = -1;
var nw_indel = -1;

for (var j = 0; j < b.length + 1; j++) {
current[j] = j * nw_indel;
}

for (var i = 1; i < a.length + 1; i++) {
for (var j = 0; j < b.length + 1; j++) {
lookback[j] = current[j];
}
current = i * nw_indel;
for (var j = 1; j < b.length + 1; j++) {
if (a[i-1] === b[j-1]) {
current[j] = lookback[j-1] + nw_match;
} else {
current[j] = Math.max(lookback[j-1] + nw_mismatch,
Math.max(lookback[j] + nw_indel,
current[j-1] + nw_indel));
}
}
}

return current[b.length];
}
``````