Site menu Algoritmos de diff
e-mail icon
Site menu

Algoritmos de diff

e-mail icon

Imagino que muitos leitores já utilizaram o aplicativo diff, ou já lidaram com "patches" ou "commits" do Git cujo conteúdo é algo semelhante a isto:

--- Analytics.java.old	2016-04-03 00:07:40.000000000 -0300
+++ Analytics.java	2016-04-03 00:07:50.000000000 -0300
@@ -78,15 +78,13 @@

         in_flight = true;

-        JsonObjectRequest req = new JsonObjectRequest(Request.POST,
+        JsonObjectRequest rez = new JsonObjectRequest(Request.GET,
                 new Response.Listener<JSONObject>() {
                     @Override
                     public void onResponse(JSONObject response) {

O arquivo acima é um script de edição: uma lista de instruções que, aplicada ao arquivo original Analytics.java.old, torna-o igual ao arquivo Analytics.java. Fora os detalhes fantasmagóricos como as @@ e os números, é fácil ver que o script substitui uma linha terminada em POST por outra que termina em GET.

Existem diversos formatos de "diff". O formato acima é o "Universal" cuja descrição pode ser encontrada aqui e é o mais utilizado por estes dias. Certamente o uso generalizado do Git consolidou essa dianteira, e levou muita gente de fora do mundo Unix a ficar conhecendo os "diffs", por bem ou por mal.

Apesar de ter curiosidade sobre o algoritmo (ou algoritmos) do diff, nunca pesquisei mais a fundo, até precisar de um algoritmo análogo, porém numa situação em que usar o diff mesmo não seria viável.

Explico: tenho um conjunto de testes de um aplicativo. O framework de teste (caseiro) armazena um "filminho" com alguns dados essenciais, durante a execução de cada teste. Tornou-se importante detectar mudanças de comportamento durante a execução do teste, mesmo que o resultado final seja igual e válido. Digamos que, durante o teste, aconteça A,B,C,D,E. Se numa execução posterior acontecer A,D,C,B,E, tem de haver um bom motivo.

Precisei de uma ferramenta ergonômica que evidenciasse as diferenças, a fim de tratá-las. Gerar dois arquivos de texto e fazer diff não é suficiente, pois há muitos dados do "filminho", como timestamps, que não devem ser considerados como diferenças. Em resumo, por motivos presentes e futuros, resolvi implementar um "diff" específico para esta massa de dados.

O melhor algoritmo

Se você deseja apenas uma implementação do melhor algoritmo disponível, e não quer saber dos detalhes sórdidos, baixe e abra este Zip, e procure pelo script diff_myers.py. Esse script implementa o algoritmo Myers, utilizado por praticamente todos os utilitários (diff, Git, etc.).

O algoritmo "bobo"

O caminho racional seria usar um módulo pronto como este, mas que graça teria? :) Tentando reinventar a roda, cheguei no seguinte algoritmo, em Python-pseudocódigo:

# A e B são matrizes contendo elementos a serem diff'ados

# Corta o "rabo": parte final que coincide
while A and B and A[-1] == B[-1]:
	A.pop()
	B.pop()

while A or B:
	# Corta a "cabeça": parte inicial que coincide
	while A and B and A[0] == B[0]:
		A.pop(0)
		B.pop(0)

	minus = len(A)
	plus = len(B)
	cost = minus + plus

	# Acha a próxima coincidência com menos "custo"
	for i in range(0, len(A)):
		for j in range(0, len(B)):
			new_cost = i + j
			if new_cost > cost:
				break
			if A[i] == B[j]:
				if new_cost < cost:
					cost = new_cost	
					minus = i
					plus = j
				break

	# Transforma a lista em script de edição
	edita("-", A[0:i])
	edita("+", B[0:j])
	A = A[i:]
	B = B[j:]

(Uma implementação funcional pode ser obtida aqui. O arquivo correspondente no Zip é diff_naive.py. Essas implementações de brinquedo comparam duas strings passadas na linha de comando, mas o algoritmo é facilmente adaptável para comparar linhas de arquivos.)

A estratégia do algoritmo é: ir cortando a "cabeça", ou seja, a parte inicial que coincide; e então procurar a próxima posição onde algum elemento coincide. Pode haver diversas coincidências, então eu procuro a de menor "custo", ou seja, aquela que se alcança com o menor número de edições.

Por incrível que pareça, o algoritmo funcionou bem, e ainda está em uso na ferramenta de teste, porque foi perfeitamente suficiente.

Fraquezas do algoritmo "bobo"

Um primeiro problema é o tempo de execução O(mn) — diffar duas strings de 10K implica em 100M ciclos potenciais. Na prática, não vai ser tão ruim porque em geral comparamos strings meio semelhantes, o que reduz muito o esforço. Uma vantagem do algoritmo "bobo" é não gastar nenhuma memória, fora um punhado de variáveis.

O maior problema é gerar scripts de edição sub-ótimos, ou seja, maiores do que o estritamente necessário. Eis um caso que "enganou" o algoritmo:

./diff_naive.py _C_D_E  _CD_E_
 _  C +D  _ -D +E  _ -E

A solução encontrada tem 4 edições, mas poderia ter apenas 2. Qualquer um pode ver que bastaria mudar um underscore de lugar para transformar _C_D_E em _CD_E_.

O algoritmo bobo se perde porque o elemento underscore é muito comum, e há muitas coincidências "baratas" com ele. Se estivéssemos comparando dois arquivos de código-fonte, as linhas comuns que poderiam atrapalhar o algoritmo seriam as linhas vazias, linhas só com fecha-chaves, etc.

Esse é um bom exemplo de algoritmo "cobiçoso" (greedy): ele toma decisões de curto prazo. Às vezes esse tipo de algoritmo é perfeito, mas não neste caso.

Por outro lado, o algoritmo encontra facilmente soluções ótimas para strings com poucos elementos repetidos. Por exemplo, comparar ABCDE com BCDEXF não causa problemas, porque existe uma "ordem" intrínseca dos elementos. Procurar por C ou por BCDE dá no mesmo, só que procurar apenas por C é muito mais barato.

No meu caso de uso, onde a "string" é na verdade uma lista de estados do aplicativo durante a execução de um teste, praticamente não há estados repetidos — o que explica o bom desempenho.

Uma modificação fácil de fazer é "especular" recursivamente qual seria o custo dos próximos passos do algoritmo, simulando até o final do processo, e retornar o custo total para o chamador original. Até funciona, porém é extremamente custosa em processamento e consumo de pilha, então não serve para uso geral.

Outra tentativa: maior substring em comum

Também é possível fazer uma implementação sub-ótima de diff procurando por substrings em comum. O script diff_lcstr.py materializa essa ideia, usando recursão. Segue o pseudocódigo:

def lcstr(A, B):
	corte os elementos iniciais em comum
	corte os elementos finais em comum
	encontre a maior substring em comum "S"

	Se len(S) = 0:
		liste os elementos de A como "-"
		liste os elementos de B como "+"
		Encerrar

	lcstr(A[:A.indexOf(S)], B[:B.indexOf(S)])
	lcstr(A[A.indexOf(S)+len(S):], B[B.indexOf(S)+len(S):])

O algoritmo acima acha a maior substring em comum, que obviamente não vai entrar no script de edições, e recursivamente procura substrings comuns nas "sobras" anteriores e posteriores, até não sobrar nada.

À primeira vista ele parece ser mais esperto que o algoritmo "bobo":

./diff_lcstr.py _C_D_E  _CD_E_
 _  C -_  D  _  E +_

Porém ele também pode ser enganado, e chega a produzir resultados piores que o algoritmo "bobo":

./diff_naive.py _C_D_EFGH_  _CD_E_F_G_H_
 _  C +D  _ -D +E  _ -E  F +_  G +_  H  _

/Users/epx $ ./diff_lcstr.py _C_D_EFGH_  _CD_E_F_G_H_
 _  C -_  D  _  E -F -G +_ +F +_ +G +_  H  _

/Users/epx $ ./diff_myers.py _C_D_EFGH_  _CD_E_F_G_H_
 _  C -_  D  _  E +_  F +_  G +_  H  _

Imagino que, em algumas situações, esse algoritmo possa gerar scripts de edição subjetivamente agradáveis, justamente porque ele procura preservar as maiores seqüências comuns. Mas é apenas uma hipótese que não testo neste artigo.

Outras tentativas

Podemos hipotetizar que uma versão do "algoritmo bobo" que lidasse apenas com elementos únicos em ambos os textos poderia funcionar bem. Os elementos repetidos seriam inseridos depois que o "diff" fosse feito em cima dos elementos únicos. Invocando os exemplos anteriores como exemplo, faríamos o "diff" apenas levando em conta as letras, inserindo os underscores a posteriori conforme a necessidade.

Isso é o que se chama "heurística": um atalho baseado em considerações práticas que conduz a um bom resultado, mas não soluciona o problema de um ponto de vista teórico.

Definindo o que é um algoritmo "bom"

Em ciência da computação, o melhor script de edição é o mais curto possível. Um bom algoritmo de diff acha esse script, de preferência usando pouca CPU e pouca memória.

Há aplicações em que o "melhor" script de edição, subjetivamente falando, não é necessariamente o mais curto — principalmente quando um humano vai dar uma olhada no script. Por exemplo:

./diff_myers.py DILMA AECIO
-D -I -L -M  A +E +C +I +O

O script acima é "ótimo" por reaproveitar a letra A comum, gerando 8 alterações em vez de 10. Porém, subjetivamente, o melhor mesmo seria fazer -(DILMA) +(AECIO). Got the point? :)

A propósito, o Git implementa um comparador chamado Patience Diff com esse objetivo: gerar patches mais legíveis e bonitos, para serem lidos por humanos.

Modelando o problema

Nesse ponto, voltamos a adotar a definição que "o melhor diff é o mais curto". O problema do diff equivale a outro problema de ciência da computação: encontrar a subseqüência comum mais longa, conhecida como LCS.

A LCS é diferente da "maior substring comum" pois na LCS é permitido remover elementos. Por exemplo, a LCS de "_C_D_E" e "_CD_E_" é "_CDE", enquanto a maior substring comum é "D_E".

Por outro lado, LCS("AECIO","DILMA") só pode ser "A" ou "I", nesse caso as possíveis LCS coincidem com as substrings em comum. (O LCS não pode inverter elementos, então "IA" e "AI" não são soluções.)

Uma vez encontrada a LCS, basta reinterpretar as deleções como um script de edição. As deleções na primeira string viram "-", as deleções na segunda string viram "+". Basta constatar o que acontece com as strings-cobaia:

./diff_myers.py _C_D_E  _CD_E_
 _  C -_  D  _  E +_

Para os fins do resto do artigo, vou substituir os underscores por "X", o que não muda muito o resultado:

./diff_myers.py xCxDxE  xCDxEx
 x  C -x  D  x  E +x

O processo de encontrar a LCS pode ser modelado como um grafo:

Figura 1: Grafo LCS entre as strings xCxDxE e xCDxEx. As diagonais são pontos em que há coincidência de caractere.

O objetivo do "jogo" é mover o ponto vermelho do canto superior esquerdo para o canto inferior direito, fazendo o menor número possível de movimentos. O ponto pode andar para baixo, para a direita, e também na diagonal quando há uma diagonal disponível. O caminho mais curto corresponde à LCS.

Figura 2: Solução ótima do grafo LCS da figura anterior. Movimentos horizontais e verticais correspondem às edições necessárias para transformar uma string em outra.

O "comprimento" do caminho, que os artigos científicos chamam de D e eu chamei de "custo" no outro algoritmo, é a soma dos movimentos verticais e horizontais. Os movimentos diagonais não contam, então o caminho mais curto é o que inclui o maior número possível de diagonais. Por outro lado, o caminho mais longo nunca poderá ser maior que len(A) + len(B). O exemplo acima tem custo ou D=2.

A string "velha" (A) está na linha horizontal. A string "nova" (B) está na linha vertical. As diagonais representam elementos em comum entre as duas strings. Cada movimento para a direita representa uma deleção na string A (que será interpretada como uma deleção no script de edição). Cada movimento para baixo representa uma deleção na string B (que será interpretada como uma inserção no script de edição).

Podemos agora representar, e analisar, o caminho que o algoritmo "bobo" tinha encontrado:

Figura 3: Solução ótima do grafo LCS da figura anterior, mais uma solução sub-ótima (em azul) encontrada por um algoritmo trivial.

Como é um exemplo muito simples, houve uma dose de falta de sorte: na coordenada (2,2), o algoritmo "bobo" escolheu ir para baixo em vez de ir para a direita, embora naquele ponto ambas as diagonais mais próximas estivessem à mesma distância. O algoritmo encarou ambas as opções como igualmente boas, só que não eram. Se adicionarmos caracteres à string A (por exemplo, fazendo-a "xCx____DxE") o algoritmo sempre tomará o caminho errado, mesmo num dia de sorte.

Com esse grafo, podemos ver como o algoritmo "bobo" funciona: ele procura a diagonal mais próxima, a partir do ponto onde ele está, sem olhar o que existe mais adiante.

Já o algoritmo baseado em substrings comuns procura sempre a seqüência mais longa de diagonais, o que no exemplo acima seria acertado, porém erraria feio se, por exemplo, houvesse uma seqüência de 2 diagonais no canto superior direito, e diagonais simples espalhadas pelo resto do grafo:

Figura 4: Grafo LCS com as strings AGCDEFG e FGFDXF, com a solução ótima em vermelho, a solução do algoritmo trivial em azul, e a solução sub-ótima em verde encontrada pelo algoritmo de maior substring comum

Nesse caso o algoritmo "bobo" andou na cola do caminho ótimo, porque procurar pela diagonal mais próxima era a coisa certa a fazer. Segue os scripts de edição correspondentes a cada um:

./diff_lcstr.py AGCDEFG FGFDXF
Longest: FG
-A -G -C -D -E  F  G +F +D +X +F

./diff_myers.py AGCDEFG FGFDXF
-A +F  G -C +F  D -E +X  F -G

Note que, apesar do segundo script de edição ser mais curto, o primeiro é consideravelmente mais legível para um ser humano. Muita gente diria que o primeiro é (subjetivamente) "melhor" que o segundo.

O algoritmo Myers

O melhor algoritmo conhecido apoia-se no fato de que o número de grandes diagonais no grafo LCS cresce linearmente, não quadraticamente.

Figura 5: Grafo LCS, evidenciadas as grandes diagonais que são exploradas no algoritmo Myers

Na literatura, essas grandes diagonais são conhecidas por k e são numeradas, começando pela diagonal central k=0, números positivos para as diagonais superiores e negativos para as inferiores. Para um grafo NxM, não é preciso considerar mais que M+N diagonais.

O algoritmo cria diversos caminhos e vai estendendo os mesmos, "alimentando" cada um com um segmento horizontal ou vertical de cada vez, até um deles atingir o objetivo. Obviamente, a primeira preocupação é como armazenar todos esses caminhos na memória: o "pulo do gato" é que o número máximo deles nunca ultrapassa o número de grandes diagonais (M+N).

A figura a seguir ilustra como o algoritmo trabalha:

Figura 6: Funcionamento do algoritmo Myers. Cada cor representa a extensão de um possível caminho LCS, adicionando-se uma edição de cada vez

O grafo acima é o mesmo da comparação xCxDxE/xCDxEx. O "passo zero", em vermelho, não tem custo porque é a remoção da "cabeça" das duas strings, que coincidem. Só existe um caminho em k=0, e o algoritmo nem trabalhou ainda.

No passo 1 (verde), o algoritmo cria dois caminhos e "alimenta" cada um com uma edição. Um foi para a grande diagonal, k=1, o outro para k=-1. Ambos encontraram diagonais, que os fizeram avançar "de graça".

No passo 2 (azul escuro), os dois caminhos viram três. Porém não viram quatro — dois caminhos vão para a grande diagonal k=0, aí apenas o caminho mais promissor sobrevive. O outro é morto (vide os X azuis). Nesse ponto o algoritmo já pode parar, porque um caminho acaba de atingir o objetivo.

Se o grafo fosse maior, a extensão prosseguiria conforme os traços marrons (custo=3) e azul-turquesa (custo=4). Um aspecto explorado pelo algoritmo é que um caminho de custo D ocupa obrigatoriamente uma diagonal de número (-D, -D+2, ..., D-2, D). Então, a cada ciclo, apenas metade das grandes diagonais está na linha de frente.

O artigo original de Eugene Myers contém pseudocódigo e explica de forma muito mais rigorosa cada um desses detalhes. Se você comparar o script diff_myers.py com o artigo, vai ver que é praticamente uma cópia fiel — o artigo é amigável com os desenvolvedores, embora seja uma leitura bem pesada.

Um "problema" do algoritmo Myers é que ele apenas percorre e acha o melhor caminho sem armazenar os passos intermediários. Fica em aberto o problema de gerar o script de edição.

Na minha implementação (diff_myers.py) eu simplesmente vou armazenando o script de edição para cada caminho conforme o algoritmo prossegue, o que é fácil e simples, porém o uso de memória volta a ser quadrático, o que poderia ser proibitivo para algumas aplicações.

O utilitário diff do Unix e possivelmente todos os seus "descendentes espirituais", como o Git, usam uma interessante estratégia: executam o algoritmo a partir do início e também do final.

Figura 7: Algoritmo Myers implementado pelo utilitário diff e outros. Os caminhos são construídos simultaneamente a partir das duas pontas, até se encontrarem

Quando dois segmentos se sobrepõem (a totalidade das implementações chama essa sobreposição de "cobra do meio"), o trecho do script de edição correspondente a essa "cobra" é anotado. Os trechos antes e depois da "cobra do meio" são recursivamente tratados pelo mesmo algoritmo Myers bidirecional.

A vantagem desse método é usar muito menos memória, porque nunca é preciso armazenar todo um caminho. O script de edição vai sendo produzido conforme a recursão avança. Isso a troco de um pequeno consumo de pilha, e o dobro de trabalho de processamento.

O algoritmo Hunt-McIlroy

Um algoritmo mais antigo, que foi empregado no diff original, é o Hunt-McIlroy. Resolvi citá-lo por interesse histórico e por ser, talvez, mais fácil de entender que o algoritmo Myers. Ele gera bons resultados, mas não necessariamente o script de edição mais curto, como o Myers gera.

Figura 8: Ilustração do algoritmo básico LCS, que calcula o LCS parcial para cada ponto de cruzamento. O algoritmo otimizado Hunt-McIlroy apoia-se apenas nos pontos de coincidência entre as strings

O algoritmo "clássico" para encontrar a LCS é calcular uma matrix MxN com as LCS parciais até cada ponto, e então procurar pelo caminho mais curto. A figura acima ilustra o processo, mostrando as LCS em cada ponto (M, MJ, MJA, MJAU), embora uma implementação só precise armazenar seus comprimentos. As linhas verdes mostram as "fronteiras" onde muda o comprimento das LCS parciais.

O principal problema desse algoritmo é ocupar uma área MxN de memória, o que significaria 100 milhões de números para comparação de dois arquivos de 10 mil linhas.

O algoritmo Hunt-McIlroy concentra o trabalho nos chamados "candidatos-k", que são os pontos azuis onde há elementos em comum entre as duas strings. Estes pontos são importantes porque é onde a LCS parcial muda de tamanho (só pode haver subseqüências em comum se existem elementos individuais em comum, afinal de contas).

Gerar uma matriz apenas com os candidatos-k gasta muito menos memória que uma matrix MxN, então já se obtém de plano uma grande economia de memória.

Este algoritmo é um bom exemplo de "programação dinâmica", cujo significado na literatura especializada é: formar uma tabela em memória com resultados intermediários e depois trabalhar em cima dela. Neste caso a tabela contém os candidatos-k.

A procura de um caminho que conecte candidatos-k de todos os níveis é eficiente. Uma regra crucial do algoritmo é nunca regredir, para cima nem para a esquerda. Na figura, o candidato-k do canto superior direito é um beco sem saída, pois não existe um candidato-k de nível 2 abaixo e à direita dele. É proibido ir à esquerda.

A solução encontrada pode ou não ser ótima, dependendo da estratégia empregada para unir os candidatos-k. Estratégias simples tendem a medir apenas a distância de uma "camada" para a próxima, e podem produzir resultados sub-ótimos. Por outro lado, uma solução ótima (que explore todos os caminhos possíveis) tende a usar muita memória.

e-mail icon