Site menu Algoritmos de diff

Algoritmos de diff

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 +_

Mas 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.

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 sempre o script mais curto, 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. 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.