JavaScript-计算两个数组之间的DTW距离

// 归一化
function normalizeSegment(arr) {
    let min = Math.min(...arr.map(row => Math.min(...row)));
    let max = Math.max(...arr.map(row => Math.max(...row)));
    return arr.map(row => row.map(value => (value - min) / (max - min)));
}

// 计算二维数组的距离
function euclideanDistance(a, b) {
    let sum = 0;
    for (let i = 0; i < a.length; i++) {
        sum += (a[i] - b[i]) ** 2;
    }
    return Math.sqrt(sum);
}

// 计算DTW距离
function dtw(s, t, dist) {
    let n = s.length;
    let m = t.length;
    let DTW = new Array(n + 1);
    for (let i = 0; i <= n; i++) {
        DTW[i] = new Array(m + 1).fill(Infinity);
    }
    DTW[0][0] = 0;

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            let cost = dist(s[i - 1], t[j - 1]);
            DTW[i][j] = cost + Math.min(DTW[i - 1][j], DTW[i][j - 1], DTW[i - 1][j - 1]);
        }
    }

    return DTW[n][m];
}

// 去重，保留相似序列片段中相似度最大的值
function deduplication(obj) {
    let keys = Object.keys(obj).map(Number);
    keys.sort((a, b) => a - b);

    let result = {};
    let maxKey = keys[0];
    let maxValue = obj[maxKey];
    for (let i = 1; i < keys.length; i++) {
        if (keys[i] - keys[i - 1] === 1) {
            if (obj[keys[i]] > maxValue) {
                maxKey = keys[i];
                maxValue = obj[maxKey];
            }
        } else {
            result[maxKey] = maxValue;
            maxKey = keys[i];
            maxValue = obj[maxKey];
        }
    }
    result[maxKey] = maxValue;

    return result
}

// 计算两个数组之间的DTW距离，找出与inputArr的所有相似序列片段
function findSimilarSegmentsDTW(inputArr, largeArr, threshold = 0.1, windowSize = null) {
    windowSize = windowSize || inputArr.length;
    let nInputArr = normalizeSegment(inputArr);
    let similarityDict = {};
    for (let i = 0; i < largeArr.length - windowSize + 1; i++) {
        let subArr = normalizeSegment(largeArr.slice(i, i + windowSize));
        let similarity = dtw(nInputArr, subArr, euclideanDistance)
        similarity = 1 / (1 + similarity)
        if (similarity > threshold) {
            similarityDict[i] = similarity;
        }
    }

    // return deduplication(similarityDict);
    return similarityDict;
}