Distância de Levenstein e distorção dinâmica do tempo

7

Não sei como desenhar paralelo entre o algoritmo Wagner-Fischer e o dtw algo. Nos dois casos, queremos encontrar a distância de cada combinação de índice (i, j).

Em Wagner-Fischer, iniciamos a distância pelo número de inserções que teríamos que fazer de uma sequência vazia para outra.

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]

no DWT, iniciamos o limite em + infinito, porque não queremos "pular" nenhum número da sequência, sempre queremos combinar com outro item.

O que não vejo é o que muda entre o DWT e o WF algo que impede o uso para atualizar a distância de maneira homogênea. No DWT, adicionamos sistematicamente o custo, enquanto no WF algo, temos essa função não homegênea em diferentes casos

Eu entendo os dois algo, mas não faço a conexão entre essas diferenças na atualização da função de custo. Alguma idéia para entender a diferença intuitivamente?

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"
algorithms dynamic-programming string-metrics edit-distance time-series-analysis Nicolas
fonte
2
Você pode melhorar sua pergunta, livrando-se do código-fonte (basta um link), mas, em vez disso, você deve destacar as diferenças entre os dois algoritmos mais claramente. Eles usam a mesma recursão, mas processam a tabela em uma ordem diferente? Apenas a inicialização é diferente? Ninguém quer analisar o código fonte. Também deixe claro, o que os dois algoritmos calculam, a distância de Levenstein, certo?
A.Schulz
11
DWT = DTW? Não estou familiarizado com o "tempo dinâmico", você pode fazer o link para uma referência introdutória?
Raphael
11
(referência) David Sankoff, Joseph Kruskal: Time Warps, String Edits e Macromolecules: The Theory and Practice of Sequence Comparison. 1983, reeditado em 1999.
Hendrik Jan

Respostas:

5

De fato, existe um monte de algoritmos relacionados. No contexto moderno, acredito que "time warp" seria chamado de alinhamento de sequência . Dependendo se você deseja combinar cordas completas ou substrings ideais, obtém - se Needleman-Wunsch e Smith-Waterman .

No seu último algoritmo, os custos parecem variar, ou seja, é possível atribuir custos diferentes para exclusão e inserção de um caractere, bem como para a alteração de caracteres. Seu primeiro algoritmo parece corrigir esses custos para1 1 para todas as três alterações possíveis.

Hendrik Jan
fonte