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

由于Nginx必须调用第三方FastCGI来处理fcgi程序. 所以在此需要安装spawn-fcgi

当spawn-fcgi安装完毕后在/etc/systemd/system/smokeping-fcgi.service创建服务文件

[Unit]
Description=SmokePing FastCGI Service
After=network.target smokeping.service
Wants=smokeping.service

[Service]
StandardOutput=null
StandardError=syslog
ExecStart=/opt/spawn-fcgi/bin/spawn-fcgi -u smokeping -s /var/run/smokeping-fcgi.sock -M 600 -n -U www-data -- /opt/smokeping-www/smokeping.cgi
Restart=always

[Install]
WantedBy=multi-user.target

Nginx调用spawn-fcgi

server {
    listen 10000;

    root /opt/smokeping-www;
    index smokeping.cgi;

    location ~ \.cgi$ {
        include /opt/nginx/conf/fastcgi_params;
        fastcgi_pass unix:/var/run/smokeping-fcgi.sock;
    }
}