動態調節演算法

A. 動態時間規整（DTW）演算法簡介

動態時間規整（DTW）演算法，主要應用於識別語音的相似性。通過數字表示音調的高低，如某單詞發音為1-3-2-4。若兩人發音時有不同拖音長度，如一人發音為1-1-3-3-2-4，另一人為1-3-2-2-4-4，我們需計算兩序列的相似性。傳統方法下，序列間距離等於對應點間距離總和。時間規整允許序列點與另一序列多個連續點對應，從而調整發音時間，計算距離。

引入時間規整後，使用6*6矩陣M表示序列A和B各點間距離，M(i, j)為A的第i點與B的第j點距離。在傳統方法下，對應點位於對角線，總和為序列長度。而在時間規整方法下，對應點形成從左上到右下的路徑，路徑總和為最小。

DTW演算法核心步驟在於尋找路徑總和最小的路徑。矩陣從左上到右下的路徑總和具有特性：相鄰元素間路徑長度的關系。通過遞歸演算法求解，起始條件為矩陣左上角元素，遞推規則為當前元素最短路徑等於其前一個元素最短路徑值加上當前元素值，取三者中的最小值。通過計算，即可得到兩序列間最小距離，從而判斷序列相似性。