Sellers

Ideia

O algoritmo Sellers se vale de algumas características da matriz de Programação Dinâmica obtida para as distâncias de edição de um texto em relação a um padrão. A última linha da matriz contém todas as distâncias entre o padrão P e os prefixos T[:j] do texto. Logo, se

D[m:j] <= r # em que m é a última linha e r é o raio

então o prefixo T[:j] é uma ocorrência aproximada de interesse.

Para implementar a prescindibilidade de que ocorrências sejam necessariamente prefixos do texto, remoções de prefixos do texto T não são penalizadas (o que equivale, na prática, a inicializar a primeira linha da matriz de Programação Dinâmica com 0).

Exemplo

T = ABADAC; P = CADA

Matriz de Programação Dinâmica
  ε A B A D A C
ε 0 0 0 0 0 0 0
C 1 1 1 1 1 1 0
A 2 1 2 1 2 1 1
D 3 2 2 2 1 2 2
A 4 3 3 2 2 1 2

Algoritmo Sellers

Entrada: T, P, r
Saída: A(P, T, r) := { j | d(T[j-k:j], P) <= r para algum k >= 0 }
início
  A <- {}
  S, S' <- vetores coluna (s0, ..., sm)^T, (s0', ..., sm')^T
  para i <- 1, ..., m faça
    s'[i] <- i
  fim-faça
  para j <- 1, ..., n faça
    s[0] <- 0
    para i <- 1, ..., m faça
      s[i] <- min { s'[i-1] + φ(T[j], P[i]), s[i-1] + 1, s'[i] + 1 }
      s'[i-1] <- s[i-1]
    fim-faça
    s'[m] <- s[m]
    se s[m] <= r então
      A <- A U {i}
    fim-se
  fim-faça
  retorna A
fim