Ferramentas para desenvolvedores · Comparação de texto
Como uma comparação de texto encontra linhas alteradas: LCS e o algoritmo Myers
· Como funciona
diferença de texto algoritmos fluxo de trabalho do desenvolvedor
Explica a ideia de subsequência comum mais longa por trás da comparação baseada em linhas e por que o algoritmo de Myers a tornou rápida o suficiente para ser executada instantaneamente, mesmo dentro de uma guia do navegador.
Dois arquivos, uma pergunta: quais linhas sobreviveram? - comparação de quadros como encontrar a maior sequência de linhas comum a ambas as versões, em vez de combinar números de linha
Duas revisões não chegam com rótulos informando quais linhas sobreviveram. ToolAcre primeiro divide cada texto em uma lista ordenada e, em seguida, procura uma longa subsequência que aparece em ambas as listas na mesma ordem. As linhas fora dessa lombada compartilhada tornam-se adições ou remoções, em vez de modificações adivinhadas.
O resultado traz posições originais de base única para ambos os lados. Uma linha inalterada possui um número em cada lado, uma retirada somente à esquerda, e uma adição somente à direita. Essa contabilidade torna a história exibida passível de revisão mesmo quando linhas repetidas fornecem mais de um alinhamento plausível.
Por que diff funciona em linhas, não em caracteres — como a divisão em novas linhas transforma um texto em uma sequência de unidades comparáveis e por que isso faz com que a prosa se comporte de maneira diferente do código
A implementação trata uma linha completa como unidade de comparação. Os limites da nova linha, portanto, moldam o resultado: uma edição de uma palavra dentro de um parágrafo armazenado em uma linha substitui toda a linha, enquanto a mesma prosa organizada frase por frase pode isolar uma região muito menor.
A comparação de linhas não é uma análise de caracteres escondida atrás de uma exibição diferente. `splitLines` cria matrizes e a tabela LCS compara uma chave de linha com outra. Essa granularidade previsível se adapta aos arquivos de origem e de configuração, mas não pode destacar as letras exatas alteradas em uma substituição de aparência correspondente.
Subsequência comum mais longa em termos simples — percorre a ideia LCS em um exemplo de cinco linhas e mostra como tudo fora da subsequência se torna uma inserção ou exclusão
Imagine as linhas esquerdas A, B, C, D, E e as linhas direitas A, C, E. A, C e E formam uma subsequência comum ordenada. B e D ficam fora dele, portanto o resultado relata duas remoções e três linhas inalteradas sem a necessidade de emparelhar qualquer linha removida com uma substituição.
A tabela registra, para cada par de posições restantes, o melhor comprimento compartilhado disponível a partir daí. A reconstrução avança através desses valores. Chaves iguais avançam ambos os lados; caso contrário, o valor vizinho maior decide se deve emitir uma remoção à esquerda ou uma adição à direita.
O algoritmo Myers e por que a velocidade é importante — explica, sem fórmulas, como rastrear o script de edição mais curto mantém a comparação rápida em arquivos com milhares de linhas
A pasta de trabalho nomeia Myers, mas `diff.js` implementa explicitamente a programação dinâmica simples de subsequência comum mais longa. Seu comentário indica tempo e memória O(n·m) para o meio diferente. Reivindicar o comportamento de Myers ou de edição mais curta do gráfico substituiria um algoritmo familiar pelo código que realmente é enviado.
ToolAcre limita esse custo antes da alocação. Prefixos e sufixos iguais são removidos em passagens lineares, e qualquer meio diferente pode conter no máximo 2,000 linhas. A matriz é `Uint32Array`; o pior quadrado permitido documentado ocupa cerca de dezesseis megabytes, em vez de valores em caixa ilimitados.
ToolAcre usa uma tabela LCS, não o algoritmo Myers mencionado no esboço
Compare um changelog contendo “Pesquisa adicionada”, “Exportação fixa” e “Ajuda atualizada” com uma revisão que mantém a primeira e a terceira entradas, mas insere “Filtros adicionados” antes da última. As entradas comuns ancoram o caminho, “Exportação fixa” é removida e “Filtros adicionados” são adicionados.
O algoritmo não chama esse par de linha modificada. Seu vocabulário de linhas é apenas igual, adicionar e remover, portanto, uma substituição textual aparece como uma remoção seguida de uma adição. O resumo conta essas operações separadamente e marca os textos como idênticos apenas quando ambas as contagens são zero.
Por que duas diferenças corretas podem parecer diferentes — mostra como as ligações entre scripts de edição igualmente curtos explicam por que uma ferramenta culpa uma linha em branco e outra culpa um colchete de fechamento
Linhas repetidas ou intercambiáveis podem produzir várias subsequências comuns do mesmo comprimento. ToolAcre resolve um empate preferindo uma remoção quando os dois valores da tabela vizinha são iguais. Outra implementação correta pode escolher primeiro uma adição e apresentar um alinhamento de aparência diferente com o mesmo custo de edição.
É por isso que uma linha em branco ou chave de fechamento pode aparecer anexada a um pedaço diferente nas ferramentas. A discrepância não significa automaticamente nenhuma comparação de conteúdo perdido. Leia os números das linhas originais e as linhas adjacentes inalteradas antes de tratar as diferenças de apresentação como afirmações factuais concorrentes.
O que isso não cobre - comparação semântica ou estrutural, detecção de movimento e realce em nível de palavra estão fora do que uma comparação baseada em linha calcula
Nada neste caminho analisa árvores de sintaxe, reconhece identificadores renomeados, rotula blocos movidos ou entende o significado da prosa. Um parágrafo movido viola o requisito de ordem compartilhada e pode aparecer uma vez como removido e uma vez como adicionado. A ferramenta também não calcula realces em nível de caractere ou palavra dentro das linhas.
Essas omissões são limites, não modos ocultos. Use um revisor com reconhecimento de idioma para declarações semânticas e controle de versão para histórico de mesclagem. A diferença de texto responde à questão mais restrita de como duas sequências de linhas ordenadas diferem e, em seguida, permite que o ser humano interprete se essas edições textuais são importantes.
Conclusão: o que as linhas destacadas realmente significam - resume como ler uma diferença de linha como a história mais curta de edições e como a comparação de texto de ToolAcre executa isso em sua guia sem fazer upload de nada
Leia as linhas verdes e vermelhas como uma explicação derivada de LCS, não como prova da intenção do autor. O corte de prefixo e sufixo altera a quantidade de trabalho, mas não a contabilização da linha final. O texto original permanece em todas as linhas, mesmo quando as opções de maiúsculas e minúsculas ou espaços em branco fornecem chaves mais flexíveis para correspondência.
A comparação é executada por meio de módulos de navegador importados e renderizada com nós de texto DOM; não há ponto final de conversão no caminho da ferramenta. Experimente um exemplo de cinco linhas, troque os lados e baixe a saída em forma de patch para ver como a direção muda as adições em remoções sem inventar a semântica.