DP Edit Distance

Edit Distance使用DP解决可以大幅度提高计算性能在对比递归解决情况下.

function editDistance(str1: string, str2: string): number {

    var str1len: number = str1.length;
    var str2len: number = str2.length;

    if (str1len === 0) return str2len;
    if (str2len === 0) return str1len;

    var matrix: Array<Array<number>> = []

    matrix[0] = new Array(str1len + 1);

    for (let i = 0; i <= str1len; i++) {
        matrix[0][i] = i;
    }

    for (let i = 1; i <= str2len; i++) {
        matrix[i] = Array(str1len + 1);
        matrix[i].fill(0);
        matrix[i][0] = i;
    }

    for (let i = 1; i <= str2len; i++) {
        const yChar: string = str2[i - 1];
        for (let j = 1; j <= str1len; j++) {
            const xChar: string = str1[j - 1];
            const a: number = matrix[i - 1][j] + 1;
            const b: number = matrix[i][j - 1] + 1;
            const c: number = matrix[i - 1][j - 1] + (yChar === xChar ? 0 : 1);
            matrix[i][j] = Math.min(a, b, c);
        }
    }

    printMatrix(matrix);

    return matrix[str2len][str1len];
}

function printMatrix(matrix: Array<Array<number>>) {
    for (let i = 0; i < matrix.length; i++) {
        process.stdout.write("[ ");
        for (let j = 0; j < matrix[i].length; j++) {
            process.stdout.write(`${matrix[i][j]} `);
        }
        process.stdout.write("]\n");
    }
}

console.log("edit distance:", editDistance("GCTATAC", "GCGTATGC"));

Edit distance核心在于:

const a: number = matrix[i - 1][j] + 1;
const b: number = matrix[i][j - 1] + 1;
const c: number = matrix[i - 1][j - 1] + (yChar === xChar ? 0 : 1);

参考:
Using dynamic programming for edit distance