# Levenstein distance and dynamic time warp

I am not sure how to draw parallel between the Wagner–Fischer algorithm and dtw algo. In both case we want to find the distance of each index combination (i,j).

In Wagner–Fischer, 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 work
let 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"

• You could improve you question, by getting rid of the source code (a link suffices), but instead you should highlight the differences between the two algorithms more clearly. Do they use the same recursion but process the table in a different order? Is only the initialization different? Nobody wants to parse through the source code. Also make clear, what both algorithms compute, the Levenstein distance, right? Nov 6 '12 at 8:34
• DWT = DTW? I am not familiar with "dynamic time warp", can you please link to an introductory reference?
– Raphael
Nov 6 '12 at 10:42
• (reference) David Sankoff, Joseph Kruskal: Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. 1983, reissued in 1999. Nov 6 '12 at 15:29

In your latter algorithm the costs seem to vary, that is one can attribute different costs for deletion and insertion of a character, as well as for changing characters. Your first algorithm seems to fix these costs to $1$ for all three possible changes.