當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

动态规划-时间规整算法

發(fā)布時(shí)間：2025/1/21 编程问答 54 豆豆

生活随笔收集整理的這篇文章主要介紹了动态规划-时间规整算法小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

在日常的生活中我們最經(jīng)常使用的距離毫無(wú)疑問應(yīng)該是歐式距離，但是對(duì)于一些特殊情況，歐氏距離存在著其很明顯的缺陷，比如說時(shí)間序列，舉個(gè)比較簡(jiǎn)單的例子，序列A：1,1,1,10,2,3，序列B：1,1,1,2,10,3，如果用歐氏距離，也就是distance[i][j]=(b[j]-a[i])*(b[j]-a[i])來(lái)計(jì)算的話，總的距離和應(yīng)該是128，應(yīng)該說這個(gè)距離是非常大的，而實(shí)際上這個(gè)序列的圖像是十分相似的，這種情況下就有人開始考慮尋找新的時(shí)間序列距離的計(jì)算方法，然后提出了DTW算法，這種方法在語(yǔ)音識(shí)別，機(jī)器學(xué)習(xí)方便有著很重要的作用。

這個(gè)算法是基于動(dòng)態(tài)規(guī)劃（DP）的思想，解決了發(fā)音長(zhǎng)短不一的模板匹配問題，簡(jiǎn)單來(lái)說，就是通過構(gòu)建一個(gè)鄰接矩陣，尋找最短路徑和。

還以上面的2個(gè)序列作為例子，A中的10和B中的2對(duì)應(yīng)以及A中的2和B中的10對(duì)應(yīng)的時(shí)候，distance[3]以及distance[4]肯定是非常大的，這就直接導(dǎo)致了最后距離和的膨脹，這種時(shí)候，我們需要來(lái)調(diào)整下時(shí)間序列，如果我們讓A中的10和B中的10 對(duì)應(yīng)，A中的1和B中的2對(duì)應(yīng)，那么最后的距離和就將大大縮短，這種方式可以看做是一種時(shí)間扭曲，看到這里的時(shí)候，我相信應(yīng)該會(huì)有人提出來(lái)，為什么不能使用A中的2與B中的2對(duì)應(yīng)的問題，那樣的話距離和肯定是0了啊，距離應(yīng)該是最小的吧，但這種情況是不允許的，因?yàn)锳中的10是發(fā)生在2的前面，而B中的2則發(fā)生在10的前面，如果對(duì)應(yīng)方式交叉的話會(huì)導(dǎo)致時(shí)間上的混亂，不符合因果關(guān)系。

接下來(lái)，以output[6][6](所有的記錄下標(biāo)從1開始，開始的時(shí)候全部置0)記錄A，B之間的DTW距離，簡(jiǎn)單的介紹一下具體的算法，這個(gè)算法其實(shí)就是一個(gè)簡(jiǎn)單的DP，狀態(tài)轉(zhuǎn)移公式是output[i][j]=Min(Min(output[i-1][j],output[i][j-1]),output[i-1][j-1])+distance[i][j];最后得到的output[5][5]就是我們所需要的DTW距離.

DTW的C語(yǔ)言實(shí)現(xiàn)

#include<iostream>
#include<string.h>
using namespace std;
#define NUM 5?//序列中樣本點(diǎn)的個(gè)數(shù)簡(jiǎn)單起見，假設(shè)2個(gè)序列的樣本點(diǎn)一樣多
#define Min(a,b) (a<b?a:b)

intmain()
{
int i,j,k;
int a[NUM],b[NUM];
int distance[NUM+1][NUM+1];
int output[NUM+1][NUM+1];

memset(distance,0,sizeof(distance));
memset(output,0,sizeof(output));
for(i=0;i<NUM;i++)?cin>>a[i];
for(i=0;i<NUM;i++)?cin>>b[i];
for(i=1;i<=NUM;i++)
for(j=1;j<=NUM;j++)
distance[i][j]=(b[j-1]-a[i-1])*(b[j-1]-a[i-1]);?//計(jì)算點(diǎn)與點(diǎn)之間的歐式距離

for(i=1;i<=NUM;i++)
{
for(j=1;j<NUM;j++)
cout<<distance[i][j]<<'\t';
cout<<endl;
} //輸出整個(gè)歐式距離的矩陣
cout<<endl;
for(i=1;i<=NUM;i++)
for(j=1;j<NUM;j++)
output[i][j]=Min(Min(output[i-1][j-1],output[i][j-1]),output[i-1][j])+distance[i][j];
//DP過程，計(jì)算DTW距離

for(i=0;i<=NUM;i++)
{
for(j=0;j<NUM;j++)
cout<<distance[i][j]<<'\t';
cout<<endl;
} //輸出最后的DTW距離矩陣，其中output[NUM][NUM]為最終的DTW距離和

return 0;
}

動(dòng)態(tài)時(shí)間規(guī)整DTW

動(dòng)態(tài)時(shí)間規(guī)整DTW(dynamic time warping)曾經(jīng)是語(yǔ)音識(shí)別的一種主流方法。
其思想是：由于語(yǔ)音信號(hào)是一種具有相當(dāng)大隨機(jī)性的信號(hào)，即使相同說話者對(duì)相同的詞，每一次發(fā)音的結(jié)果都是不同的，也不可能具有完全相同的時(shí)間長(zhǎng)度。因此在與已存儲(chǔ)模型相匹配時(shí)，未知單詞的時(shí)間軸要不均勻地扭曲或彎折，以使其特征與模板特征對(duì)正。用時(shí)間規(guī)整手段對(duì)正是一種非常有力的措施，對(duì)提高系統(tǒng)的識(shí)別精度非常有效。
動(dòng)態(tài)時(shí)間規(guī)整DTW是一個(gè)典型的優(yōu)化問題，它用滿足一定條件的的時(shí)間規(guī)整函數(shù)W(n)描述輸入模板和參考模板的時(shí)間對(duì)應(yīng)關(guān)系，求解兩模板匹配時(shí)累計(jì)距離最小所對(duì)應(yīng)的規(guī)整函數(shù)。

?將時(shí)間規(guī)整與距離測(cè)度結(jié)合起來(lái)，采用動(dòng)態(tài)規(guī)劃技術(shù)，比較兩個(gè)大小不同的模式，解決語(yǔ)音識(shí)別中語(yǔ)速多變的難題；
?一種非線性時(shí)間規(guī)整模式匹配算法；

DTW ( Dynamic Time Warping )，即「動(dòng)態(tài)時(shí)間扭曲」或是「動(dòng)態(tài)時(shí)間規(guī)整」。這是一套根基于「動(dòng)態(tài)規(guī)劃」（Dynamic Programming，簡(jiǎn)稱DP）的方法，可以有效地將搜尋比對(duì)的時(shí)間大幅降低。
DTW 的目標(biāo)就是要找出兩個(gè)向量之間的最短距離。一般而言，對(duì)于兩個(gè) n 維空間中的向量 x 和 y，它們之間的距離可以定義為兩點(diǎn)之間的直線距離，稱為尤拉距離（Euclidean Distance）。
dist(x, y) = |x – y| ，
但是如果向量的長(zhǎng)度不同，那它們之間的距離，就無(wú)法使用上述的數(shù)學(xué)式來(lái)計(jì)算。一般而言，假設(shè)這兩個(gè)向量的元素位置都是代表時(shí)間，由于我們必須容忍在時(shí)間軸的偏差，因此我們並不知道兩個(gè)向量的元素對(duì)應(yīng)關(guān)系，因此我們必須靠著一套有效的運(yùn)算方法，才可以找到最佳的對(duì)應(yīng)關(guān)系。

DTW是用于與說話人有關(guān)（Speaker Dependent）的語(yǔ)音識(shí)別，使用者自行錄音然后再以自己的聲音來(lái)比對(duì)之前錄好的語(yǔ)音資料。此方法比較適合同一位說話人的聲音來(lái)進(jìn)行比較，因此應(yīng)用范圍比較狹隘，譬如目前手機(jī) Name Dialing 等等。

DTW的問題：
?運(yùn)算量大；
?識(shí)別性能過分依賴于端點(diǎn)檢測(cè)；
?太依賴于說話人的原來(lái)發(fā)音；
?不能對(duì)樣本作動(dòng)態(tài)訓(xùn)練；
?沒有充分利用語(yǔ)音信號(hào)的時(shí)序動(dòng)態(tài)特性；
DTW適合于特定人基元較小的場(chǎng)合，多用于孤立詞識(shí)別；

動(dòng)態(tài)規(guī)劃算法總體思想
動(dòng)態(tài)規(guī)劃算法基本思想是將待求解問題分解成若干個(gè)子問題
但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。
如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。

動(dòng)態(tài)規(guī)劃基本步驟
找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。
遞歸地定義最優(yōu)值。
以自底向上的方式計(jì)算出最優(yōu)值。
根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解

一、動(dòng)態(tài)時(shí)間規(guī)整的提出
　　語(yǔ)音信號(hào)具有很強(qiáng)的隨機(jī)性，不同的發(fā)音習(xí)慣，發(fā)音時(shí)所處的環(huán)境不同，心情不同都會(huì)導(dǎo)致發(fā)音持續(xù)時(shí)間長(zhǎng)短不一的現(xiàn)象。如單詞最后的聲音帶上一些拖音，或者帶上一點(diǎn)呼吸音，此時(shí)，由于拖音或呼吸音會(huì)被誤認(rèn)為一個(gè)音素，造成單詞的端點(diǎn)檢測(cè)不準(zhǔn)，造成特征參數(shù)的變化，從而影響測(cè)度估計(jì)，降低識(shí)別率，因此在語(yǔ)音識(shí)別時(shí)，首先有必要對(duì)語(yǔ)音信號(hào)進(jìn)行時(shí)間規(guī)整。

二、動(dòng)態(tài)時(shí)間規(guī)整的定義

　　一次正確的發(fā)音應(yīng)該包含構(gòu)成該發(fā)音的全部音素以及正確的音素連接次序。其中各音素持續(xù)時(shí)間的長(zhǎng)短與音素本身以及講話人的狀況有關(guān)。為了提高識(shí)別率，克服發(fā)同一音而發(fā)音時(shí)間長(zhǎng)短的不同，采用對(duì)輸入語(yǔ)音信號(hào)進(jìn)行伸長(zhǎng)或縮短直到與標(biāo)準(zhǔn)模式的長(zhǎng)度一致。這個(gè)過程稱為時(shí)間規(guī)整。

三、動(dòng)態(tài)時(shí)間規(guī)整的原理描述

　　60年代由日本學(xué)者提出，算法的思想是把未知量伸長(zhǎng)或縮短(壓擴(kuò))，直到與參考模板的長(zhǎng)度一致，在這一過程中，未知單詞的時(shí)間軸會(huì)產(chǎn)生扭曲或彎折，以便其特征量與標(biāo)準(zhǔn)模式對(duì)應(yīng)。

原理描述

　　DTW是把時(shí)間規(guī)整和距離測(cè)度計(jì)算結(jié)合起來(lái)。測(cè)試語(yǔ)音參數(shù)共有I幀矢量，而參考模板共有J幀矢量，I和J不等，尋找一個(gè)時(shí)間規(guī)整函數(shù)j=w(i)，它將測(cè)試矢量的時(shí)間軸i非線性地映射到模板的時(shí)間軸j上，并使該函數(shù)w(i)滿足：

公式

第i幀測(cè)試矢量T(i)和第j幀模板矢量R(j)之間的距離測(cè)度D。

　　最優(yōu)時(shí)間規(guī)整情況下所有矢量幀間的距離，也稱為代價(jià)函數(shù)。

公式2

計(jì)算兩倒譜矢量幀(i和j) 間的歐氏距離，兩矢量幀中分別具有p個(gè)倒譜參數(shù)。

　　為了使T（測(cè)試）的第i個(gè)樣本與R（參考）的第j個(gè)樣本對(duì)正，其對(duì)應(yīng)的點(diǎn)不在直線對(duì)角線上，得到一條彎曲的曲線j=w(i) 。j=w(i)稱為規(guī)整函數(shù)。

時(shí)間規(guī)整的依據(jù)

　　設(shè) T={a1 , a2 , …… , ai , …… , aI} i=1～I?　　R={b1 , b2 , …… , bj , …… , bJ} j=1～J?　　I≠J?　　時(shí)間規(guī)整要解決的問題是使元素a和元素b之間匹配，使每對(duì)匹配樣本之間的差別最小,達(dá)到歐氏距離最小。

Veeraraghavan等人用動(dòng)態(tài)時(shí)間規(guī)整（dynamic time warping，DTW）來(lái)匹配運(yùn)動(dòng)序列。DTW是一種時(shí)變數(shù)據(jù)序列匹配方法，常用于微生物學(xué)的DNA匹配、字符串和符號(hào)的比較以及語(yǔ)音分析[77]。DTW算法的思想是給定參考模板特征矢量序列與輸入特征矢量序列，尋找一個(gè)最佳的時(shí)間規(guī)整函數(shù)，使得輸入序列的時(shí)間軸映射到參考模板的時(shí)間軸上總的累計(jì)失真最小。對(duì)DTW而言，即使測(cè)試序列模式與參考序列模式的時(shí)間尺度不能完全一致，只要時(shí)間次序約束存在，它仍能較好地完成測(cè)試序列與參考序列之間的模式匹配。DTW具有概念簡(jiǎn)單、算法魯棒的優(yōu)點(diǎn)，能夠?qū)D像序列進(jìn)行分類。文獻(xiàn)[35]在形狀空間中用動(dòng)態(tài)時(shí)間規(guī)整方法計(jì)算兩個(gè)形狀序列之間的距離來(lái)識(shí)別動(dòng)作和步態(tài)，取得了很好的分類結(jié)果。然而，DTW算法計(jì)算量較大，缺乏考慮相鄰時(shí)序之間的動(dòng)態(tài)特性，而在實(shí)際中，運(yùn)動(dòng)序列中相鄰序列在時(shí)間和空間上有高度的相關(guān)性。

1)?dynamictime war ping (DTW)?
動(dòng)態(tài)時(shí)軸彎曲或動(dòng)態(tài)時(shí)間規(guī)正(DTW)
2)?DTW?
動(dòng)態(tài)時(shí)間規(guī)整(DTW)
3)?dynamic time warping?
動(dòng)態(tài)時(shí)間彎曲
1.Time series similar pattern matching based on wavelet and dynamic timewarping;?
基于小波和動(dòng)態(tài)時(shí)間彎曲的時(shí)間序列相似匹配
2.Similarity matching algorithm for interval-valued time series based ondynamic time warping;
基于動(dòng)態(tài)時(shí)間彎曲的區(qū)間值時(shí)間序列匹配算法
3.Through dynamic time warping analysis to the hot-fire test data and simulatedfault data of a certain liquid rocket engine,the warped path sets wereobtained.
對(duì)某大型液體火箭發(fā)動(dòng)機(jī)的熱試車數(shù)據(jù)及通過發(fā)動(dòng)機(jī)模型仿真得到的故障數(shù)據(jù)進(jìn)行動(dòng)態(tài)時(shí)間彎曲分析,得到彎曲路徑集,然后結(jié)合決策樹方法進(jìn)行了故障檢測(cè)和診斷。
更多例句>>
4)?Dynamic Time Warping(DTW)?
動(dòng)態(tài)時(shí)間彎曲
1.An efficient lower bounding technique is proposed based on Dynamic TimeWarping(DTW) for time series similarity search,which measures the distancebetween original sequence reduced dimensionality by Piecewise AggregateApproximation(PAA) approximation method and query sequence reduceddimensionality by Grid Minimum Bounding Rectangle(GMBR) representationapproach.
針對(duì)時(shí)間序列數(shù)據(jù),提出一種新的基于動(dòng)態(tài)時(shí)間彎曲的下界技術(shù),該技術(shù)首先基于分段聚集近似的線性表示對(duì)原始序列進(jìn)行降維,同時(shí)生成查詢序列的網(wǎng)格最小邊界矩形近似表示,然后利用基于動(dòng)態(tài)時(shí)間彎曲距離對(duì)兩者下界距離度量。
更多例句>>
5)?dynamictime alignment?
時(shí)間動(dòng)態(tài)規(guī)正
6)?dynamictime warping?
動(dòng)態(tài)時(shí)間規(guī)正
1.Gait contour by using Fourier descriptors was described,tomake quasi-periodic analysis on height and width ratio of gait image,and tosolve the problems resulting from image sequence of different gait cycle byusing dynamic time warping.
利用傅立葉描繪子對(duì)步態(tài)輪廓圖像進(jìn)行描述,用步態(tài)圖像的高寬比進(jìn)行步態(tài)的準(zhǔn)周期性分析,并采用動(dòng)態(tài)時(shí)間規(guī)正算法解決不同的步態(tài)周期的圖像序列之間的比較問題。
2.In the system, RelAtive SepeTrAl(RASTA) filter was used to reduce theconvolution channel noise mixed in speech signal, and the improved dynamic timewarping (DTW) algorithm was adopted for recognizing speech command.
該系統(tǒng)采用RASTA濾波方法去除語(yǔ)音信號(hào)中夾雜的卷積信道噪聲,采用改進(jìn)的動(dòng)態(tài)時(shí)間規(guī)正(DTW)算法對(duì)語(yǔ)音命令進(jìn)行識(shí)別。

DTW（Dynamic Time Warping，動(dòng)態(tài)時(shí)間歸整）算法，該算法基于動(dòng)態(tài)規(guī)劃（DP）的思想，解決了發(fā)音長(zhǎng)短不一的模板匹配問題，是語(yǔ)音識(shí)別中出現(xiàn)較早、較為經(jīng)典的一種算法。用于孤立詞識(shí)別，DTW算法與HMM算法在訓(xùn)練階段需要提供大量的語(yǔ)音數(shù)據(jù)，通過反復(fù)計(jì)算才能得到模型參數(shù)，而DTW算法的訓(xùn)練中幾乎不需要額外的計(jì)算。所以在孤立詞語(yǔ)音識(shí)別中，DTW算法仍然得到廣泛的應(yīng)用。

機(jī)群系統(tǒng)上并行計(jì)算時(shí)間序列的動(dòng)態(tài)彎曲距離
莫倩蕓　鐘誠(chéng)　
時(shí)間序列的相似性度量是衡量?jī)蓚€(gè)序列相似性的依據(jù).動(dòng)態(tài)時(shí)間彎曲距離計(jì)算方法具有較強(qiáng)的健壯性且可以度量不同長(zhǎng)度的時(shí)間序列間的相似性,但其十分耗時(shí).采用波前式推進(jìn)方法并行計(jì)算動(dòng)態(tài)時(shí)間彎曲距離并以流水線并行方式傳送局部子結(jié)果,提出一個(gè)在機(jī)群系統(tǒng)上實(shí)現(xiàn)的度量?jī)蓚€(gè)時(shí)間序列相似性的并行算法.PC機(jī)群系統(tǒng)上的實(shí)驗(yàn)結(jié)果表明,該并行算法高效,獲得了良好的加速和可擴(kuò)展性.
關(guān)鍵詞：時(shí)間序列;動(dòng)態(tài)時(shí)間彎曲;并行計(jì)算;機(jī)群系統(tǒng)

基于分段線性動(dòng)態(tài)時(shí)間彎曲的時(shí)間序列聚類算法研究
翁穎鈞?朱仲英?
時(shí)間序列是一類重要的復(fù)雜類型數(shù)據(jù) ,時(shí)間序列知識(shí)發(fā)現(xiàn)正成為知識(shí)發(fā)現(xiàn)的研究熱點(diǎn)之一。歐幾里德距離及其擴(kuò)展作為相似測(cè)度被廣泛應(yīng)用于時(shí)間序列的比較中 ,但是這種距離測(cè)度對(duì)數(shù)據(jù)沒有好的魯棒性。動(dòng)態(tài)時(shí)間彎曲技術(shù)是基于非線性動(dòng)態(tài)編程的一種模式匹配算法 ,但是其計(jì)算復(fù)雜性相當(dāng)高。本文提出了基于時(shí)間序列分段線性表示的動(dòng)態(tài)時(shí)間彎曲算法 ,通過計(jì)算線性分段序列數(shù)據(jù)之間的最短彎曲路徑來(lái)獲得序列的匹配。對(duì)綜合控制時(shí)間序列數(shù)據(jù)進(jìn)行基于不同距離測(cè)度的聚類分析對(duì)比結(jié)果表明本文提出的算法有很高的精度和對(duì)振幅差異、嘈聲和線性漂移有強(qiáng)的魯棒性 ,大大降低計(jì)算復(fù)雜性 ,具有良好的應(yīng)用價(jià)值

1)?SegmentedDynamic Time Warping Distance?
分段動(dòng)態(tài)彎曲距離
1.After finding similar segmented subsequence by Segmented Dynamic Time WarpingDistance,this method then search this subsequence point by point,by which thesubsequence is acquired accurately.
該算法首先通過中線距離閾值和極值點(diǎn)兩個(gè)約束條件分段線性擬合時(shí)間序列,利用分段動(dòng)態(tài)彎曲距離度量獲得相似的分段子序列,逐點(diǎn)檢索該子序列實(shí)現(xiàn)序列的精確查詢。
2)?Time Warping Distance?
動(dòng)態(tài)彎曲距離
3)?segmented time warping distance?
分段時(shí)間彎曲距離
4)?Dynamic Time Warping distance?
動(dòng)態(tài)時(shí)間彎曲距離
5)?range curvature distortion?
距離彎曲
1.In this dissertation, the presence of range curvature distortion inconventional PFA is analyzed from data format perspective.
本文對(duì)聚束模式經(jīng)典算法極坐標(biāo)格式算法(Polar Format Algorithm, PFA)進(jìn)行討論,從信號(hào)格式角度分析了PFA中距離彎曲對(duì)高分辨率成像區(qū)域大小的限制,并給出補(bǔ)償距離彎曲的一般方法,但距離彎曲的空變性使得補(bǔ)償復(fù)雜且運(yùn)算量大。
更多例句>>
6)?range curvature distinction?
距離彎曲差
1.Effect caused by range curvature distinction for deception jamming under SARimaging
距離彎曲差對(duì)SAR欺騙干擾成像的影響

動(dòng)態(tài)時(shí)間歸整算法http://www.doc88.com/p-91694157837.html
動(dòng)態(tài)時(shí)間歸整算法http://www.docin.com/p-86210991.html

機(jī)群系統(tǒng)上并行計(jì)算時(shí)間序列的動(dòng)態(tài)彎曲距離http://wenku.baidu.com/view/c40dabba1a37f111f1855b60.html

Dynamic time warping

Not to be confused with the Time Warp mechanism for discrete eventsimulation, or the Time Warp Operating System that used this mechanism.

Dynamic time warping (DTW) is analgorithm for?measuring similaritybetween two sequences which may vary in time or speed. For instance,similarities in walking patterns would be detected, even if in one video theperson was walking slowly and if in another he or she were walking morequickly, or even if there were accelerations and decelerations during thecourse of one observation. DTW has been applied to video, audio, and graphics —indeed, any data which can be turned into a linear representation can beanalyzed with DTW. A well known application has been automatic?speech recognition, to cope with different speaking speeds.

In general, DTW is a method that allows a computer to find an optimal matchbetween two given sequences (e.g.timeseries) with certainrestrictions.?The sequences are"warped" non-linearly in the time dimension to determine a measure oftheir similarity independent of certain non-linear variations in the timedimension. This?sequence alignment?method is often used in the context of?hidden Markov models.

One example of the restrictions imposed on the matching of the sequences ison the?monotonicity?of the mapping in the time dimension.?Continuityis less important in DTW?than in other?patternmatching?algorithms; DTW is an algorithmparticularly suited to?matching sequenceswith missing information, provided there are long enough segments formatching to occur.

The extension of the problem for?two-dimensional "series" likeimages?(planar warping) is?NP-complete, while the problem for?one-dimensionalsignals?like time series can be solved in?polynomial time.

Example of one of the many forms of thealgorithm

This example illustrates the implementation of dynamic time warping whenthe two sequences are strings of discrete symbols.?d(x, y)?is a distance between symbols, i.e.?d(x, y)?= |?x - y?|.

int DTWDistance(char s[1..n], char t[1..m]) { declare int DTW[0..n, 0..m] declare int i, j, cost for i := 1 to m DTW[0, i] := infinity for i := 1 to n DTW[i, 0] := infinity DTW[0, 0] := 0 for i := 1 to n for j := 1 to m cost:= d(s[i], t[j]) DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertion DTW[i , j-1], // deletion DTW[i-1, j-1]) // match return DTW[n, m] } ?

We sometimes want to add a locality constraint. That is, we require thatif?s[i]?is matched with?t[j], then |?i - j| is no larger than?w, a window parameter.

We can easily modify the above algorithm to add a locality constraint(differences marked in?bold italic). However, the above given modification works only if |n - m| is no larger than?w, i.e. the end point is within the windowlength from diagonal. In order to make the algorithm work, the windowparameter?w?must be adapted so that |n - m ≤ w| (see the line marked with (*) in the code).

int DTWDistance(char s[1..n], char t[1..m], int w) { declare int DTW[0..n, 0..m] declare int i, j, cost w := max(w, abs(n-m)) // adapt window size (*) for i := 0 to n for j:= 0 to m DTW[i, j] := infinity DTW[0, 0] := 0 for i := 1 to n for j := max(1, i-w) to min(m, i+w) cost := d(s[i], t[j]) DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertion DTW[i , j-1], // deletion DTW[i-1, j-1]) // match return DTW[n, m] } ?

Open Source software

The?lbimproved?C++ library implements Fast Nearest-Neighbor Retrieval algorithms under the Dynamic Time Warping (GPL). It also provides a C++ implementation of Dynamic Time Warping as well as various lower bounds.
The?R package dtw?implements most known variants of the DTW algorithm family, including a variety of recursion rules (also called step patterns), constraints, and substring matching.
The?mlpy?Python library implements DTW.

References

Sakoe, H. and Chiba, S.,?Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1) pp. 43- 49, 1978, ISSN: 0096-3518
C. S. Myers and L. R. Rabiner. A comparative study of several dynamic time-warping algorithms for connected word recognition. The Bell System Technical Journal, 60(7):1389-1409, September 1981.
L. R. Rabiner and B. Juang. Fundamentals of speech recognition. Prentice-Hall, Inc., 1993 (Chapter 4)

總結(jié)

以上是生活随笔為你收集整理的动态规划-时间规整算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。