JavaScript 动态时间规整 (DTW) 算法实现

判断声音相似度（音文对齐）有用到 DTW 算法

DTW（Dynamic Time Warping）动态时间规整算法，是一种计算 2 个时间序列尤其是不同长度序列相似度的一种动态规划算法。主要应用在时序数据上，比如孤立词语音识别、手势识别、数据挖掘以及信息检索等。

维基百科：https://en.wikipedia.org/wiki/Dynamic_time_warping

实现

( function() {
    "use strict";
    function DynamicTimeWarping ( ts1, ts2, distanceFunction ) {
        var ser1 = ts1;
        var ser2 = ts2;
        var distFunc = distanceFunction;
        var distance;
        var matrix;
        var path;

        var getDistance = function() {
            if ( distance !== undefined ) {
                return distance;
            }
            matrix = [];
            for ( var i = 0; i < ser1.length; i++ ) {
                matrix[ i ] = [];
                for ( var j = 0; j < ser2.length; j++ ) {
                    var cost = Infinity;
                    if ( i > 0 ) {
                        cost = Math.min( cost, matrix[ i - 1 ][ j ] );
                        if ( j > 0 ) {
                            cost = Math.min( cost, matrix[ i - 1 ][ j - 1 ] );
                            cost = Math.min( cost, matrix[ i ][ j - 1 ] );
                        }
                    } else {
                        if ( j > 0 ) {
                            cost = Math.min( cost, matrix[ i ][ j - 1 ] );
                        } else {
                            cost = 0;
                        }
                    }
                    matrix[ i ][ j ] = cost + distFunc( ser1[ i ], ser2[ j ] );
                }
            }

            return matrix[ ser1.length - 1 ][ ser2.length - 1 ];
        };

        this.getDistance = getDistance;

        var getPath = function() {
            if ( path !== undefined ) {
                return path;
            }
            if ( matrix === undefined ) {
                getDistance();
            }
            var i = ser1.length - 1;
            var j = ser2.length - 1;
            path = [ [ i, j ] ];
            while ( i > 0 || j > 0 ) {
                if ( i > 0 ) {
                    if ( j > 0 ) {
                        if ( matrix[ i - 1 ][ j ] < matrix[ i - 1 ][ j - 1 ] ) {
                            if ( matrix[ i - 1 ][ j ] < matrix[ i ][ j - 1 ] ) {
                                path.push( [ i - 1, j ] );
                                i--;
                            } else {
                                path.push( [ i, j - 1 ] );
                                j--;
                            }
                        } else {
                            if ( matrix[ i - 1 ][ j - 1 ] < matrix[ i ][ j - 1 ] ) {
                                path.push( [ i - 1, j - 1 ] );
                                i--;
                                j--;
                            } else {
                                path.push( [ i, j - 1 ] );
                                j--;
                            }
                        }
                    } else {
                        path.push( [ i - 1, j ] );
                        i--;
                    }
                } else {
                    path.push( [ i, j - 1 ] );
                    j--;
                }
            }
            path = path.reverse();

            return path;
        };

        this.getPath = getPath;
    }

    var root = typeof self === "object" && self.self === self && self ||
        typeof global === "object" && global.global === global && global ||
        this;

    if ( typeof exports !== "undefined" && !exports.nodeType ) {
        if ( typeof module !== "undefined" && !module.nodeType && module.exports ) {
            exports = module.exports = DynamicTimeWarping;
        }
        exports.DynamicTimeWarping = DynamicTimeWarping;
    } else {
        root.DynamicTimeWarping = DynamicTimeWarping;
    }

    if ( typeof define === "function" && define.amd ) {
        define( "dynamic-time-warping", [], function() {
            return DynamicTimeWarping;
        } );
    }
}() );

var ser1 = [ 9, 93, 15, 19, 24 ];
var ser2 = [ 31, 97, 81, 82, 39 ];
var distFunc = function( a, b ) {
    return Math.abs( a - b );
};

var dtw = new DynamicTimeWarping(ser1, ser2, distFunc);

var dist = dtw.getPath(); // [ [ 0, 0 ], [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 4 ], [ 4, 4 ] ]

Github: https://github.com/GordonLesti/dynamic-time-warping