Blog Projects Bio RSS
PENSIEVE.LST

PENSIEVE.DOCFAST-EDIT-DISTANCE-JAVASCRIPTSEQ 0007

2015-07-013 MIN

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
// WTFPL license
// 2015 Huan Truong - [email protected]
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[0] = 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];
}

*** END OF DOCUMENT 0007 ***

SEE ALSO

  1. 2023-07Notes on installing Rollo/Beeprt CUPS driver for Raspberry Pi OS (Arm64)
  2. 2021-07Is your computer too slow to keep up with your typing?
  3. 2021-05Lullaby of the artillery

< ALL DOCUMENTS

COMMENTS

Open comments

© 2026 HUAN TRUONG · CC BY-NC-SAGITHUB VCARD
CREDITSThe calculator, slide rule and punch cards were drawn by Claude, Anthropic’s AI, from measurements of photographs of real ones. The coffee ring is cut from a photograph by Nevit Dilmen (CC BY-SA 3.0) and stays under that licence.