I am not sure how to draw parallel between the WagnerFischer algorithm and dtw algo.In both case we want to find the distance of each index combination (i,j).In WagnerFischer, we initiate the distance by the number of insert we'd have to do from one empty string to another.let wagnerFischer (s: string) (t: string) =   let m, n = s.Length, t.Length   let d = Array2D.create (m + 1) (n + 1) 0   for i = 0 to m do d.[i, 0] <- i   for j = 0 to n do d.[0, j] <- j       for j = 1 to n do       for i = 1 to m do          d.[i, j] <- List.min [                           d.[i-1, j  ] + 1;                            d.[i  , j-1] + 1;                            d.[i-1, j-1] + if s.[i-1] = t.[j-1] then 0 else 1; ]   printfn edit matrix \n %A d    d.[m,n]in the DWT we initiate the boundary at +infinity because we dont want to 'skip' any numbers of the sequence, we always want to match with another item.What I dont see is what changes between the DWT and the WF algo that prevent use to update the distance in homogeneous way. In DWT we systematically add the cost, whereas in the WF algo, we have this non homegenous function wrt different cases I understand both algo, but dont make the connexion between those differences in the cost function update ..Any idea to understand the difference intuitively  ?let sequencebacktrack (s: 'a seq) (t:'a seq) (cost:'a->'a->double) (boundary:int->double)  =   let m, n = s |> Seq.length, t |> Seq.length   let d = Array2D.create (m + 1) (n + 1) 0.   for i = 0 to m do d.[i, 0] <- boundary(i)   for j = 0 to n do d.[0, j] <- boundary(j)   t |> Seq.iteri( fun j tj ->            s |> Seq.iteri( fun i si ->                         d.[1+i, 1+j] <- cost tj si + List.min [d.[1+i-1, 1+j  ];                                                                d.[1+i  , 1+j-1];                                                                d.[1+i-1, 1+j-1]; ] ))   printfn edit matrix \n %A d    d.[m,n]//does not worklet wagnerFischer2 (s: string) (t: string) =   sequencebacktrack s t (fun a b -> if a = b then 0. else 1.) (id >> double)let b = wagnerFischer2 ll la
Levenstein distance and dynamic time warp
algorithms;dynamic programming;string metrics;edit distance;time series analysis