:abacus: @edit-distance/myers-1986

Reasonably efficient implementation of Eugene W. Myers's exact longest common subsequence and minimum edit-distance algorithm for JavaScript. See docs.

:building_construction: Caveat emptor! This is work in progress. Code may be working. Documentation may be present. Coherence may be. Maybe.

:warning: Only signed 32-bit integers are supported for MAX, xi, xj, yi, yj. This is also true for the values xj - xi and yj - yi but is not enforced. You should be fine if the elements of each pair have the same sign. This means you cannot diff things with more than 2,147,483,647 parts (array elements, string characters, text words or lines).

// Example 1: compute Edit Distance.

import {makeScan, twoWay} from '@edit-distance/myers-1986';

const scan = makeScan(twoWay);

const ed = (x, y) => {
    const eq = (xi, yi) => x[xi] === y[yi];
    const xi = 0;
    const xj = x.length;
    const yi = 0;
    const yj = y.length;
    const MAX = xj - xi + (yj - yi);
    return scan(MAX, eq, xi, xj, yi, yj);
};

ed('BANANA', 'ATANA'); // 3

// Example 2: compute LCS.

import {diff} from '@edit-distance/myers-1986';

const rectangles = (x, y) => {
    const eq = (xi, yi) => x[xi] === y[yi];
    const xi = 0;
    const xj = x.length;
    const yi = 0;
    const yj = y.length;
    const MAX = xj - xi + (yj - yi);
    return diff(MAX, eq, xi, xj, yi, yj);
};

const lcs = (x, y) => {
    let result = x.slice(0, 0);
    let xp = 0;
    for (const [x0, x1] of rectangles(x, y)) {
        result = result.concat(x.slice(xp, x0));
        xp = x1;
    }

    return result.concat(x.slice(xp, x.length));
};

lcs('BANANA', 'ATANA'); // AANA

:bicyclist: Benchmark