Um pouco sobre correspondência de cadeias e árvores

Gravatar publicou em

Programação Ciência de Dados

Árvores estão entre as estruturas de dados mais estudadas dentro da Ciência da Computação. Diversas são as áreas em que comparações entre árvores são necessárias, como por exemplo em análise de imagens, comparação de textos estruturados, otimização de compiladores, inclusive algumas utilizações nem são exclusivas da computação, como é o caso da comparação de estruturas de RNA secundário em computação biológica.

No entanto, antes de vermos sobre este assunto, vamos começar vendo um pouco de comparação entre cadeias de caracteres, a base por trás de um dos algoritmos voltados a comparações com árvores que será visto mais a frente.

Suponha que tenhamos duas cadeias quaisquer de caracteres e que podemos operar sobre elas de apenas três maneiras: substituição de um carácter por outro na mesma posição; remoção de um carácter, ou adição de um carácter. Queremos agora descobrir a menor sequência de ações (dentro da restrição anterior) que nos possibilite transformar uma das cadeias na outra.

Como exemplo considere as cadeias S1 = "abcde" e S2 = "acc" e, na tabela abaixo, três sequências de operações para obtermos S2 a partir de S1:

Passo

Sequência 1

Sequência 2

Sequência 3

1.

remover "b" de S1

substituir "b" por "c" em S1

remover "a" de S1

2.

remover "d" de S1

remover "d" de S1

remover "b" de S1

3.

remover "e" de S1

remover "e" de S1

remover "d" de S1

4.

adicionar "c" a S1

 

remover "e" de S1

5.

   

adicionar "a" a S1

6.

   

adicionar "c" a S1

7.

   

adicionar "c" a S1

   

considerar que há um jeito melhor

A segunda maneira acima nos poupa um passo em relação a primeira; enquanto a terceira é a mais direta: simplesmente apague tudo e comece do zero. Apesar desta última ter seus méritos, ser eficiente não é um deles, lembre-se: estamos atrás da menor (leia: mais eficiente) sequência!

Bem, deve haver algum jeito de descobrir quais passos precisamos tomar para converter uma cadeia em outra sem precisar testar todas as possibilidades. Considerando que queremos comparar duas cadeias quaisquer, é melhor pensar em duas cadeias genéricas de caracteres e denominá-las A e B, com A tendo tamanho m e B de tamanho n, onde m > 0 e n > 0. Agora vamos seguir por terreno familiar, isto é, comparando A com B, porém não aleatoriamente. As comparações serão entre todos os prefixos1 de A com todos prefixos de B com auxílio de uma matrix M que é montada seguindo o algoritmo abaixo, conhecido como algoritmo de Levenshtein:

   Levenshtein(A, B, m, n, M)
1:    M(i, 0) = i [i = 0…m];
2:    M(0, j) = j [j = 0...n];
3:    for i = 1 to m do
4:      for j = 1 to n do
5:        if A(i) == B(j) do
6:          M(i, j) = M(i - 1, j - 1)
7:        else do
8:          del = M(i - 1, j) + 1
9:          ins = M(i, j - 1) + 1
10:        sub = M(i - 1, j - 1) + 1
11:        M(i, j) = min{ del, ins, sub }
12:      end
13:    end
14:    return M(m, n)
15:  end

Após executarmos o algoritmo obtemos uma matriz L onde cada célula L(i, j) nos dá a quantidade mínima de operações para transformarmos a1...ai de A em b1...bj de B. Tomando i = m e j = n, encontramos quantas operações são necessárias para conseguirmos B a partir de A. Por exemplo, suponha que A = "abcde" e B = "acc" no algoritmo, temos L resultante na tabela abaixo, na qual $ indica um caractere vazio:

 

$

a1

a2

a3

$

0

1

2

3

b1

1

0

1

2

b2

2

1

1

2

b3

3

2

1

1

b4

4

3

2

2

b5

5

4

3

3

Através da tabela acima vemos que são necessárias 3 operações para conseguir "acc" a partir de uma cadeia vazia ( L(1,3) ); 2 para obtermos "ac" de "abcd" ( L(4,2) ); 1 para obtermos "abc" de "acc" ( L(3,3) ), e por aí em diante. É bom notar que, como as operações de adição e remoção de caractere são complementares entre si e a de substituição é simétrica,  transformar de A para B dá o mesmo trabalho que B para A.

Por fim, é analisando como L foi construída que obtemos qual a sequência de operações transforma A em B. Para isso, levamos em conta que cada célula foi preenchida com base em outra (linhas 6 e 11 do algoritmo), isso nos dá um vetor com origem na célula e direção à célula "base". Montamos então uma tabela L2 com estes vetores, e caminhamos de L2(m,n) a L2(1,1), sempre seguindo a direção dos vetores. A sequência de operações para converter A em B é dada considerando a seguinte lógica:

  • Se ↖: substitua ai por bj, a menos que ai igual a bj

  • Se ←: adicione bj entre ai e ai+1

  • Se ↑: remova ai

Para o exemplo anterior, temos a tabela abaixo:

 

$

a

c

c

$

-

-

-

-

a

-

b

-

c

-

d

-

e

-

E a sequência de operações resultante:

Passo

Sequência

1.

remover "e" de A

2.

remover "d" de A

3.

substituir "b" por "c" em A

É importante ressaltar que as operações foram tomadas como tendo custo 1 (linhas 8, 9, 10 no algoritmo), mas nada impede que os custos sejam diferentes. Nessa situação, o algoritmo priorizaria operações com custos menores (linha 11).

O algoritmo de Levenshtein também pode ser usado para encontrar a quantidade e sequência de operações para transformar uma árvore em outra, assim como para cadeias de caracteres, porém, as duas árvores a serem comparadas precisam ser enraizadas, ordenadas e de altura 2.

E o que seria uma "árvore enraizada e ordenada de altura 2"?

Uma árvore é um grafo conexo, isto é, todos vértices estão conectados diretamente ou indiretamente, e acíclico, ou seja, existe apenas um caminho entre dois vértices. Uma árvore é enraizada se um dos seus vértices é tomado como ancestral comum a todos outros vértices e é ordenada se a ordem dos filhos é importante em comparações com outras árvores. Altura, também conhecida como profundidade, indica o número de níveis da árvore. Abaixo alguns exemplos de grafos com diferentes características:

Daqui em diante o termo árvore será utilizado como sinônimo para árvore enraizada e ordenada. Quando o sentido for outro será dito explicitamente.

Agora que temos definidos os pré-requisitos necessários para usarmos o algoritmo com árvores de altura 2, o processo é bem simples: tome a notação pré-fixa, ou polonesa, das duas árvores e passe as cadeias resultantes para o algoritmo. Essa notação pode ser obtida pelo seguinte algoritmo:

1:  comece na raiz e anote o valor do vértice
2:  enquanto há vértices abaixo não visitados
3:     entre no vértice abaixo mais a esquerda
4:     anote o valor do vértice
5:     repita 2
6:  suba um nível e repita 2 até toda árvore ser percorrida

Para árvores com altura maior que 2 não podemos utilizar este algoritmo, pois não temos como garantir que duas árvores diferentes terão notação pré-fixa diferentes. Por exemplo, na imagem abaixo duas árvores e suas notações:

Encontrar o conjunto de operações que transforma uma árvore em outra não é tarefa simples e ainda hoje não há um algoritmo ótimo para isso. A solução mais direta, através de comparações entre subárvores, é impraticável pois o tempo de execução cresce exponencialmente para o tamanho das árvores. Em 1979, Tai [1] surgiu com o primeiro algoritmo que não leva tempo exponencial, mas sim O(m3n3), onde m e n são os tamanhos das árvores. Desde então, diversos outras incursões neste território foram realizadas, vale citar: Zhang e Shasha [2] (1989), Klein [3] (1998) e Demaine [4] (2009). A solução mais recente é de Pawlik e Augsten [5] (2011) com complexidade O(n3).

Sugiro a leitura dos artigos referenciados para aqueles que tem interesse no assunto. Não vou tentar explicar devido à complexidade das soluções propostas, ao invés disso, vou seguir por outro caminho e apresentar um algoritmo para encontrar o grau de semelhança entre duas árvores.

Começamos modificando o algoritmo de Levenshtein, resultando no pseudo-código abaixo:

   aproximate_string_match(A, B, m, n, M)
1:    M(i, 0) = 0 [i = 0…m];
2:    M(0, j) = 0 [j = 0...n];
3:    for i = 1 to m do
4:      for j = 1 to n do
5:        if A(i) == B(j) do
6:          M(i, j) = M(i - 1, j - 1) + 1
7:        else do
8:        M(i, j) = min{ M(i - 1, j), M(i, j - 1), M(i - 1, j - 1) }
9:      end
10:    end
11:    return M(m, n)
11:  end

As modificações são simples e por elas obtemos um novo algoritmo que encontra a maior subcadeia de caracteres composta por caracteres semelhantes entre as duas cadeias originais, respeitando a sequência em que eles aparecem. Por exemplo, se tivermos "abcde" e "abdef" a subcadeia comum será "abde", e nosso algoritmo retornará 4.

O grau de semelhança entre duas árvores pode ser encontrado aplicando recursão ao novo algoritmo de modo que sejam feitas comparações entre subárvores de altura 2 localizadas em cada nível das árvores originais; esses resultados são então utilizados na comparação de subárvores maiores, no estilo "dividir para conquistar". O algoritmo final se encontra abaixo:

Para encerrar, tomemos as duas árvores com notações prefixa iguais apresentadas anteriormente como entradas para o algoritmo. Como resultado  3, como podemos comprovar pela imagem abaixo:

 

1 prefixo é usado aqui como termo para uma subcadeia xi...xj de X, onde i = 1 e j <= |X|, |X| sendo o tamanho de X.

 

Referências

[1] K.-C. Tai. The tree-to-tree correction problem. J. ACM. 1979.[1] K.-C. Tai. The tree-to-tree correction problem. J. ACM. 1979. http://www.techfak.uni-bielefeld.de/ags/pi/lehre/PatTreesWS11/tree-to-tree_tai.pdf

[2] K.Zhang and D.Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput. 1989. http://bit.ly/1DbRKP2

[3] P.N. Klein. Computing the edit-distance between unrooted ordered trees. In European Symposium on Algorithms (ESA). 1998. http://128.148.32.110/research/pubs/pdfs/1998/Klein-1998-CED.pdf

[4] E.D. Demaine, S. Mozes, B. Rossman and O. Weimann. An optimal decomposition algorithm for tree edit distance. ACM Trans. on Alg. 2009. http://www.cs.haifa.ac.il/~oren/Publications/TEDinTALG.pdf

[5] M.Pawlik and N.Augsten. RTED: A Robust Algorithm for the Tree Edit Distance. PVLDB. 2011. http://vldb.org/pvldb/vol5/p334_mateuszpawlik_vldb2012.pdf


 





Leia mais sobre: