3.3 Clifford Algebra
3.3.2 Some Instructive Examples
Nesta seção, é proposta uma i-quasi-métrica µ no espaço das cadeias de caracteres sobre um alfabeto finito. Esta proposta de distância para cadeias de caracteres é influ- enciada pela chamada distância de edição, ou de Levenshtein (ver [Levenshtein 1965] e [Dasgupta et al, 2006]), a qual coloca como distância entre duas cadeias o número mí- nimo de operações de edição para transformar uma cadeia na outra. A distância de edição é usada até hoje como medida de similaridade em bancos de dados de cadeias de caracte- res ([Seraphim 2005]).
Por ser uma distância (métrica) no sentido usual, o valor da distância entre duas ca- deias é um número real. Na proposta a ser apresentada nesta seção, a distância será um par ordenado de números, o que já possibilita uma informação maior sobre a similaridade entre as cadeias.
O principal aspecto sobre esta função µ a ser abordado é o prático, já que, como será visto abaixo, a topologia gerada por esta i-quasi-métrica é trivial. Sob o ponto de vista prático, será demonstrado que está função possui algumas propriedades e a partir destas desenvolve-se um algoritmo para calculá-la.
Definição 4.19. Considere ∑ = {a1, a2, ..., an} um alfabeto, ou seja, um conjunto finito e
não vazio. Cada elemento de ∑ é chamado caractér. Uma cadeia de caracteres sobre ∑ é uma lista finita e ordenada de elementos de ∑. O conjunto de todas as cadeias sobre o alfabeto ∑ será denotado por ∑∗. O comprimento de uma cadeia é a quantidade
(contando repetições) de caracteres da cadeia e será denotado por |w|, onde w ∈ ∑∗. O
símbolo ε denotará a cadeia vazia, a qual é a única com comprimento 0.
Exemplo 4.12. Se ∑ = {a1, a2, a3}, então são cadeias de caracteres: a1a2, a2a3, ....
Notem que a1a26= a2a1e se w = a1a1a1a1a1, então |w| = 5.
Observação 4.11. Dado w ∈ ∑∗, será denotado por w
co conjunto dos caracteres usados
para formar a cadeia w, por exemplo, se ∑ = {a,b,c,...,z} e w = assassino, então wc=
{a, s, i, n, o}.
Definição 4.20. Seja ∑ um alfabeto. Uma função f : ∑∗−→ ∑∗é chamadaoperação de
Capítulo 4. i-Distâncias
Exemplo 4.13. Seja ∑ = {a1, a2, ..., an} um alfabeto. A concatenação de duas cadeias em
∑∗é definida da seguinte maneira: se w = ar1...arm e t = as1..asn, então a concatenação
de w com t é a cadeia wt = ar1...armas1..asne de t com w é a cadeia tw = as1..asnar1...arm.
Sendo assim, fixada uma cadeia w a função f : ∑∗−→ ∑∗ definida por f (t) = wt é uma
operação de edição em ∑∗.
Definição 4.21. Fixado k ∈ N, a função Rk: ∑∗−→ ∑∗definida, para cada w = a
r1...arm∈ ∑∗, por: Rk(w) = ar1...ark−1ark+1...arm , se k < m ar1...arm−1 , se k = m w , se k > m
é chamada operação deremoção do k-ésimo caractér. Fixados k ∈ N e a ∈ ∑, a função Iak: ∑∗−→ ∑∗definida, para cada w = a
r1...arm, por: Iak(w) = ar1...ark−1aark...arm , se k ≤ m wa , se k = m + 1 w , se k > m + 1 é chamadaoperação de inserção do caractér a como k-ésimo caractér. Exemplo 4.14. Se ∑ = {a,b,c,...,z}, então R5(casar) = casa e I3
u(casa) = causar.
Neste trabalho as únicas operações de edição consideradas serão as de remoção e inserção de caracteres. Uma observação imediata sobre estas operações é que se Rk(w) 6=
w, então |Rk(w)| = |w| − 1 e se Ik
a(w) 6= w, então |Iak(w)| = |w| + 1.
Definição 4.22. Uma sequência de operações de edição é a composição de operações de remoção e inserção. Será usada a notação T(y)(x) para indicar que a sequência de operações de edição possui x inserções e y remoções. Uma sequência será dita bem formada quando T(y)(x)= Irx
arx◦ ... ◦ Iar1r1◦ Rs1◦ ... ◦ Rsy, com ar1, ..., arx∈ ∑, r1, ...rx, s1, ...sy∈
N, com r1< ... < rxe s1< ... < sy. A função identidade em ∑∗será considerada como uma sequência de operações de edição, a qual será denotada por T(0)(0). Dada uma sequência de operações de edição T(y)(x)= Irx
arx◦ ... ◦ Iar1r1◦ Rs1◦ ... ◦ Rsy, será usada a notação T(y)(x)para
o conjunto {Irx
arx, ..., Iar1r1, Rs1, ..., Rsy} de todas as operações de edição de T(y)(x).
Exemplo 4.15. Seja ∑ = {a,b,...,z} e w = santana. Considere T(2)(3)= Io8◦ Ig7◦ Ii5◦ R6◦ R7, então T(2)(3)(santana) = santiago.
Capítulo 4. i-Distâncias
Definição 4.23. Seja T(y)(x)= T1◦ ... ◦ Tx◦ Tx+1◦ ... ◦ Tx+y uma sequência de operações de
edição. Considere w ∈ ∑∗. Será dito que T(x)
(y) modifica totalmente w quando:
Tk((Tk+1◦ ... ◦ Tx+y)(w)) 6= (Tk+1◦ ... ◦ Tx+y)(w), , para cada k = 1, 2, ..., x + y − 1
e Tx+y(w) 6= w.
Observação 4.12. Seja T(y)(x) uma sequência de operações de edição que modifica total- mente a cadeia w, então |T(y)(x)(w)| = |t| + x − y.
A seguir, será definida a i-quasi-métrica em ∑∗. Para isso, será definidoa VID que
será usado na definição desta i-distância.
Definição 4.24. Seja Z+= {0, 1, 2, ...} o conjunto dos inteiros não negativos. Considere
em Z+× Z+ a ordem lexicográfica definida por (a,b) ≤
l (c, d) se, e somente se, a <
b ∨ (a = b) ∧ (c ≤ d).
Observação 4.13. A ordem lexicográfica é uma relação de ordem total em Z+×Z+. Com
isso, a estrutura hZ+× Z+, ≤
l, <l, (0, 0)i é um reticulado com menor elemento separável
sendo, portanto, uma VID.
Considere duas cadeias w e t. Usando apenas remoções e inserções é possível trans- formar t em w. Por exemplo, a sequência de operações formada pelas operações de remo- ção de todos os caracteres de t e inserção de todos os caracteres de w claramente trans- forma t em w. Sendo assim, o conjunto Twt = {(x, y) ∈ Z+× Z+; ∃ T(y)(x)tal queT(y)(x)(t) =
w} é não vazio quaisquer que sejam as cadeias w e t. Dessa forma, o conjunto {x ∈ Z+; existe y ∈ Z+ com (x,y) ∈ Twt} também é não vazio, logo pelo princípio da boa or- denação, este conjunto possui menor elemento. Seja a este elemento. O conjunto {y ∈ Z+; (a,y) ∈ Twt} também é não vazio, logo possui menor elemento, digamos b. Assim, temos que (a,b) ∈ Twt e, além disso, (a,b) ≤l (x, y), para todo (x, y) ∈ Twt, ou seja, (a,b)
é o mínimo (com relação a ordem ≤l) do conjunto Twt. A notação (a,b) = min≤lTwt será
usada. Defina µs: ∑∗× ∑∗−→ Z+× Z+ por:
µs(w,t) = min ≤l Twt
A função µstem as seguintes propriedades imediatas:
1. Dado w ∈ ∑∗, temos que µ
s(w, w) = (0, 0). De fato, T(0)(0)(w) = w.
2. Sejam w,t ∈ ∑∗tais que µ
s(w,t) = (0, 0). Isso significa que T(0)(0)(t) = w, mas T(0)(0)é
Capítulo 4. i-Distâncias
3. Segue das duas primeiras propriedades que se µs(w,t) = µs(t, w) = (0, 0), então
w = t.
Exemplo 4.16. A função µsnão é simétrica. De fato, se ∑ = {a,b,c,...,z}, então µs(ab, c) =
(2, 1) e µs(c, ab) = (1, 2).
Teorema 4.22. Sejam w,t ∈ ∑∗ tais que µ
s(w,t) <l (α, β) para algum (α, β) ∈ Z+×
Z+− {(0, 0)}. Dessa forma, então existe (ϕ, γ) ∈ Z+× Z+, com (0,0) <l (ϕ, γ) tal que se µs(t, v) <l(ϕ, γ), então µs(w, v) <l(α, β).
Demonstração. Basta tomar (ϕ,γ) = (0,1). Dessa forma, se µs(t, v) <l (0, 1), então
µs(t, v) = (0, 0), logo, pela propriedade 2, t = v, o que implica em µs(w, v) = µs(w,t) <l
(α, β).
Observação 4.14. Segue das propriedades 1 e 3 e do teorema anterior que a função µs
é uma i-quasi-métrica relativa à VID hZ+× Z+, ≤
l, <l (0, 0)i. Note que dado w ∈ ∗
∑
, tem-se B(w,(0,1) = {w}, ou seja, todo subconjunto unitário de∑
∗ é aberto na topologia gerada por µse, portanto, esta topologia é a topologia discreta em∗
∑
. Abaixo, são listadas mais algumas propriedades da função µs:a) Se µs(w,t) = (x, y) 6= (0, 0), então toda sequência de operações de edição T(y)(x) tal que
T(y)(x)(t) = w modifica totalmente t. De fato, se existisse uma sequência T(y)(x) tal que T(y)(x)(t) = w sendo que T(y)(x)não modifica totalmente t, então ao se excluir a operação de edição que faz parte da sequência e que não modifica sua entrada, obtem-se uma outra sequência T(v)(z)tal que T(v)(z)(t) = w e (z, v) <l(x, y), o que contradiz µs(w,t) =
(x, y) 6= (0, 0). b) Se a1, a2∈ ∑, então µs(a1, a2) = ( (0, 0) , se a1= a2 (1, 1) , se a16= a2 . c) Para cada t ∈ ∑∗, tem-se µ
s(ε,t) = (0, |t|). De fato, para t = ε, o resultado é imediato.
Para t 6= ε, considere T(|t|)(0) = R1◦ ... ◦ R|t|, assim T(|t|)(0)(t) = ε. Se (x, y) <l (0, |t|),
então x = 0 e y < |t|, assim, se T(y)(x) é uma sequência que modifica totalmente t, então |T(y)(x)(t)| = |t| − y > 0, logo T(y)(x)(t) 6= ε. Sendo assim, (0, |t|) = min≤lTε,t ⇒
µs(ε,t) = (0, |t|). De modo análogo, mostra-se que µs(w, ε) = (|w|, 0).
d) Se µs(w,t) = (x, y), então existe uma sequência bem formada de operações de edição
T(y)(x) tal que T(y)(x)(t) = w.
Teorema 4.23. Se w,t ∈ ∑∗e a ∈ ∑, então µ
Capítulo 4. i-Distâncias
Demonstração. Suponha µs(w,t) = (x, y) e seja T(y)(x) uma sequência tal que T(y)(x)(t) =
w. Assim, T(y)(x)(ta) = wa o que implica em µs(wa,ta) ≤l (x, y). Suponha µs(wa,ta) =
(z, v) <l (x, y). Seja G(z)(v) uma sequência tal que G(z)(v)(ta) = wa, logo G(z)(v)(t) = w, assim
µs(w,t) ≤l(z, v) ⇒ µs(w,t) <l(x, y), o que é uma contradição.
Lema 4.3. Se w ∈ ∑∗e a ∈ ∑, então µ s(w, a) = ( (|w|, 1) , se a /∈ wc (|w| − 1, 0) , se a ∈ wc .
Demonstração. Suponha que a /∈ wc e µs(w, a) = (x, y), então, existe uma sequência de
operações T(y)(x)tal que T(y)(x)(a) = w. Como a /∈ wc, então y = 1, logo |T(y)(x)(a)| = 1+x−y =
xe de T(y)(x)(a) = w segue que |T(y)(x)(a)| = |w| ⇒ x = |w|.
Agora, suponha que a ∈ wce seja µs(w, a) = (x, y). Dessa forma, existe uma sequência
de operações T(y)(x)tal que T(y)(x)(a) = w. Como é possível transformar a em w sem nenhuma remoção e fazendo a inserção de todos os outros caracteres de w , então µs(w, a) = (x, y) ≤l
(|w|−1, 0). Suponha x < |w|−1. Assim, |T(y)(x)(a)| = 1+x−y < 1+|w|−1+y = |w|−y ≤ |w|, logo |T(y)(x)(a)| < |w| ⇒ T(y)(x)(a) 6= w, o que é uma contradição. Logo, deve-se ter x = |w| − 1 e, portanto, y = 0.
Teorema 4.24. Se w ∈ ∑∗e a,b ∈ ∑, com µ
s(w, b) = (x, y), então:
µs(wa,t) =
(
µs(w, b) − (0, 1) , se a = b e y = 1
µs(w, b) + (1, 0) , caso contrário
Demonstração. Considere os seguintes casos:
Primeiro, suponha a = b e y = 1. Dessa forma, b /∈ wc, logo, do lema anterior segue
que µs(w, b) = (|w|, 1). Como a = b, então b ∈ (wa)c, donde segue:
µs(wa, b) = (|wa| − 1, 0) = (|w| + 1 − 1, 0) = (|w|, 0)
= (|w|, 1) − (0, 1) = µs(w, b) − (0, 1).
Agora, considere o caso em que a = b e y = 0. Portanto b ∈ wc, o que implica em
µs(w, b) = (|w| − 1, 0) e, como b ∈ (wa)c, segue que:
µs(wa, b) = (|wa| − 1, 0) = (|w| + 1 − 1, 0) = (|w|, 0)
= (|w| − 1, 0) + (1, 0) = µs(w, b) + (1, 0).
Capítulo 4. i-Distâncias
então b /∈ (wa)c, portanto:
µs(wa, b) = (|wa|, 1) = (|w| + 1, 0)
= (|w|, 1) + (1, 0) = µs(w, b) + (1, 0).
Finalmente, considere o caso em que a 6= b e y = 0. Dessa forma, b ∈ wc, logo
µs(w, b) = (|w| − 1, 0). Como b ∈ (wa)c, segue:
µs(wa, b) = (|wa| − 1, 0) = (|w| + 1 − 1, 0) = (|w|, 0)
= (|w| − 1, 0) + (1, 0) = µs(w, b) + (1, 0).
Lema 4.4. Sejam (z,v),(x,y) ∈ Z+× Z+ com (z,v) <
l (x, y), então (z, v) + (c, d) <l
(x, y) + (c, d), para todo (c, d) ∈ Z+× Z+.
Demonstração. Caso z < x, então z+c < x+c, logo (z,v)+(c,d) <l(x, y)+(c, d). Se z =
xe v < y, então z + c = x + c e v + d < y + d), portanto (z,v) + (c,d) <l(x, y) + (c, d).
Lema 4.5. Suponha a 6= b e µs(wa,tb) = (x, y) e seja T(y)(x)uma sequência bem formada de
operações de edição tal que T(y)(x)(tb) = wa. Sendo assim, pelo menos uma das operações de edição R|t|ou I|w|+1
a está em T(y)(x).
Demonstração. Suponha que R|t|∈ T/ (x)
(y). Dessa forma, como a 6= b e a cadeia wa apre-
senta o carácter a na posição |w| + 1, então deve ser inserido o caractér a nesta posi- ção.
Teorema 4.25. Se w,t ∈ ∑∗e a,b ∈ ∑, com a 6= b, então:
µs(wa,tb) = min
≤l {µs(wa,t) + (0, 1), µs(w,tb) + (1, 0)}.
Demonstração. Considere µs(wa,tb) = (x, y) e seja T(y)(x) uma sequência bem formada de
operações de edição tal que T(y)(x)(tb) = wa.
Primeiro, suponha que a operação R|t|+1 é uma das operações de T(x)
(y). Considere,
então, G(x)(y−1) a sequência bem formada obtida de T(y)(x) excluindo-se a operação R|t|+1,
ou seja, G(x)(y−1)= T(y)(x)− {R|t|+1}. Dessa forma, G(x)(y−1)(t) = wa. Note que µs(wa,t) =
Capítulo 4. i-Distâncias
(z, v) <l(x, y − 1). Considere H(v)(z)uma sequência bem formada de operações de edição tal
que H(v)(z)(t) = wa e defina a sequência de operações F(v+1)(z) obtida de H(v)(z)acrescentando- se a operação R|t|+1. Dessa forma, F(z)
(v+1)(tb) = wa, portanto µs(wa,tb) ≤l (z, v + 1) =
(z, v) + (0, 1). Como (z, v) <l (x, y − 1), do lema 4.4 segue que (z, v) + (0, 1) <l (x, y −
1) + (0,1) = (x,y) ⇒ µs(wa,tb) <l (x, y), o que contradiz o fato de µs(wa,tb) = (x, y).
Portanto µs(wa,t) = (x, y − 1) ⇒ µs(wa,tb) = (x, y) = µs(wa,t) + (0, 1).
Agora, suponha que R|t|+1 não é uma das operações de T(x)
(y). Dessa forma, segue do
lema 4.5 que a operação Ia|w|+1 é uma das operações de T(y)(x). Considere a sequência de
operações G(x−1)(y) obtida de T(y)(x) excluindo-se a operação Ia|w|+1. Segue que G(x−1)(y) (tb) =
wa. Note que µs(w,tb) = (x − 1, y). De fato, G(x−1)(y) (tb) = w, então µs(w,tb) ≤l(x − 1, y).
Suponha µs(w,tb) = (z, v) <l(x − 1, y). Seja H(v)(z)uma sequência bem formada de opera-
ções de edição tal que H(v)(z)(tb) = w. Defina F(v)(z+1)como a sequência bem formada obtida de H(v)(z) acrescentando-se a operação Ia|w|+1. Assim, F(v)(z+1)(tb) = wa, logo µs(wa,tb) ≤l
(v, z+1) = (z, v)+(1, 0). Como (z, v) <l(x−1, y), segue do lema 4.4 que (z, v)+(1, 0) <l
(x − 1, y) + (1, 0) = (x, y), logo µs(wa,tb) <l (x, y) o que contradiz µs(wa,tb) = (x, y).
Portanto, µs(w,tb) = (x − 1, y) ⇒ µs(wa,tb) = (x, y) = µs(w,tb) + (1, 0).
Com isso, ficou provado que µs(wa,tb) = µs(wa,t) + (0, 1) ou µs(wa,tb) = µs(w,tb) +
(1, 0). Considere µs(wa,t) = (z, v) e µs(w,tb) = (u, r) e sejam G(z)(v) e H(r)(u) sequências de
operações de edição tais que G(z)(v)(t) = wa e H(r)(u)(tb) = w. Defina as sequências Γ(z)(v+1) obtida de G(z)(v) acrescentando-se a operação R|t|+1e Π(u+1)
(r) obtida de H (u)
(r) acrescentando-
se a operação Ia|w|+1. Dessa forma, segue que Γ(z)(v+1)(tb) = wa e Π(u+1)(r) (tb) = wa. Sendo
assim, com z inserções e v + 1 remoções ou com u + 1 inserções e r remoções é possível transformar a cadeia tb na cadeia wa. Como já vimos que µs(wa,tb) é igual a (z, v + 1)
ou igual a (u + 1,r), pode-se concluir que µs(wa,tb) = min≤l{(z, v + 1), (u + 1, r)} =
min≤l{µs(wa,t) + (0, 1), µs(w,tb) + (1, 0)}.
Estes últimos resultados sobre µs provam que o algoritmo a seguir calcula efetiva-
mente o valor de µs.
Algoritmo µ
sFunção: medida µs(Character: Str1[1..lenStr1],
Character: Str2[1..lenStr2],vector: integer[2]) Início
“Mat é uma matriz com lenStr2 linhas e lenStr1 + 1 colunas" Para i = 1..lenStr2
Capítulo 4. i-Distâncias
Mat[i,1] = (0,i)
Para j = 2..lenStr1+1 Se Str1[ j −1] = Str2[1] e (Mat[1, j −1])2= 1, então Mat[1, j] =
Mat[1, j − 1] − (0,1)
Se não, então Mat[1, j] = Mat[1, j − 1] + (1,0) Para i = 2..lenStr2
Para j = 2..(lenStr1 + 1)
Se Str1[i] = Str2[ j], então Mat[i, j] = Mat[i − 1, j − 1]
Se Str1[i] 6= Str2[ j], então Mat[i, j] = min≤l{Mat[i − 1, j] + (0, 1), Mat[i, j − 1] +
(1, 0)}
µs= Mat[lenStr2, lenStr1 + 1].
Fim
Este algoritmo constrói uma matriz de ordem m × n cujo termo de índice mn é o valor de µs. O algoritmo que calcula a distância de Levenshtein também constrói uma
matriz cujo o último termo é o valor da distância. Os dois algoritmos possuem a mesma complexidade, a saber, da ordem de O(mn), onde m e n são os comprimetos das cadeias.
A seguir, tal matriz é apresentada para dois exemplos. − − P A T T E R N L (0,1) (1,1) (2,1) (3,1) (4,1) (5,1) (6,1) (7,1) E (0,2) (1,2) (2,2) (3,2) (4,2) (4,1) (5,1) (6,1) T (0,3) (1,3) (2,3) (2,2) (3,2) (4,2) (5,2) (6,2) T (0,4) (1,4) (2,4) (2,3) (2,2) (3,2) (4,2) (5,2) E (0,5) (1,5) (2,5) (2,4) (2,3) (2,2) (3,2) (4,2) R (0,6) (1,6) (2,6) (2,5) (2,4) (2,3) (2,2) (3,2) S (0,7) (1,7) (2,7) (2,6) (2,5) (2,4) (2,3) (3,3) Neste caso, µs(pattern, letters) = (3, 3).
Capítulo 4. i-Distâncias − − A A B B A C S B (0,1) (1,1) (2,1) (2,0) (3,0) (4,0) (5,0) (6,0) A (0,2) (0,1) (1,1) (2,1) (3,1) (3,0) (4,0) (5,0) A (0,3) (0,2) (0,1) (1,1) (2,1) (3,1) (4,1) (5,1) A (0,4) (0,3) (0,2) (1,2) (2,2) (2,1) (3,1) (4,1) B (0,5) (0,4) (0,3) (0,2) (1,2) (2,2) (3,2) (4,2) B (0,6) (0,5) (0,4) (0,3) (0,2) (1,2) (2,2) (3,2) B (0,7) (0,6) (0,5) (0,4) (0,3) (1,3) (2,3) (3,3) C (0,8) (0,7) (0,6) (0,5) (0,4) (1,4) (1,3) (2,3)
Neste caso, µs(AABBACS, BAAABBBC) = (2, 3). No decorrer desta seção, serão vistas
ligações entre µs e o importante conceito de subsequências de cadeias de caracteres.
Definição 4.25. Sejam w,t ∈ ∑∗. A cadeia w é umasubsequência de t quando t = w ou
quando é possível transformar t em w fazendo-se apenas remoções de caracteres de t ou, equivalentemente, quando é possível transformar w em t fazendo-se apenas inserções de caracteres em w.
Exemplo 4.17. abcde f é subsequência de xyabecopdine f , enquanto abcde f não é sub- sequência de abcde.
A distância de Levenshtein mencionada no início desta seção é definida como a menor quantidade de operações de edição que transforma uma cadeia na outra. Seja dL esta
distância e ∑ = {a,c,t,g} o alfabeto a ser considerado. Como exemplo, considere as cadeias acctg, cactga e cag. Tem-se dL(acctg, cactga) = 3 e dL(cag, cactga) = 3. Note
que cag é subsequência de cactga mas acctg não é subsequência de cactga, o que mostra que o simples cálculo do valor de dL não é suficiente para determinar quando uma cadeia
é subsequência de outra. Isso aponta uma pequena vantagem da função µs sobre dL, que
é estabelecida no teorema abaixo.
Teorema 4.26. Seja ∑ um alfabeto e w,t ∈ ∑∗. A cadeia w é subsequência de t se, e
somente se, µs(w,t) = (0, y) ou, equivalentemente , µs(w,t) <l(1, 0).
Demonstração. Imediata.
Um outro relacionado a subsequências de cadeias de caracteres é o de determinar o tamanho da maior subsequência comum a duas cadeias dadas (notação |LCS|). Este é um problema clássico de computação(algoritmos). Tal problema tem aplicações na área de bioinformática (ver [Paleo 2007]), onde se deseja saber o quão duas cadeias de DNA são similares através de |LCS|. A seguir, é feita a ligação entre |LCS| e µs.
Capítulo 4. i-Distâncias
Definição 4.26. Dadas w,t ∈ ∑∗, diz-se que s ∈ ∑∗é umamaior subsequência comum
para w e t se qualquer outra subsequência r comum a w e t é tal que |r| ≤ |s|. Neste caso |s| = |LCS|.
Teorema 4.27. Dadas w,t ∈ ∑∗, se µ
s(w,t) = (x, y), então |LCS(w,t)| = |t| − y.
Demonstração. Seja T(y)(x) = Isx
asx◦ ... ◦ Ias1s1 ◦ Rr1◦ ... ◦ Rry tal que T(y)(x)(t) = w. Considere
T(y)(0)= Rr1◦ ... ◦ Rry, assim T(0)
(y)(t) = s, onde s é uma subsequência comum a w e a t. Note
que |s| = |t|−y, ou seja, y = |s|−|t| e que |w| = |s|+x, ou seja, x = |w|−|s|. suponha que exista uma outra subsequência s′comum a w e a t tal que |s′| > |s|. Dessa forma, tem-se
µs(s′,t) = (0, |t| − |s′k) e com |w| − |s′| inserções de caracteres podemos transformar s′
em w, portanto µs(w,t) ≤l(|w| − |s′|, |t| − |s′|) <l(x, y), já que |w| − |s′| < |w| − |s| = x.
Mas isso contradiz o fato de µs(w,t) = (x, y). Dessa forma, não pode haver subsequência
comum a w e a t com comprimento maior do que |s|, portanto |LCS(w,t)| = |s| = |t| − y.
Capítulo 5
Métricas Intervalares
Neste capítulo, toda a matemática desenvolvida nos capítulos anteriores é aplicada para prover uma distância cujos valores sejam intervalos e que capture o importante con- ceito de representação intervalar.
Para fazer isso, será construído uma VID baseada na ordem de Kulisch-Miranker.