Que efeito tem a opção “-d” com diff?

Question

A implementação diff no OpenBSD tem uma opção -d não padrão com a seguinte documentação:

-d

Try very hard to produce a diff as small as possible. This may consume a lot of processing power and memory when processing large files with many changes.

A implementação diff do GNU tem a mesma opção com a documentação mais curta

-d, --minimal

try hard to find a smaller set of changes

De tempos em tempos, usei essa opção apenas para ver se ela gera uma saída que esteja em qualquer formato ou forma diferente do mesmo comando diff sem a opção, mas nunca viu qualquer diferença (sem trocadilhos).

Alguém poderia fornecer ou apontar para um exemplo em que essa opção realmente produz um resultado diferente do mesmo comando sem -d ? Alternativamente, se alguém puder explicar as circunstâncias necessárias para essa opção entrar em ação, também estou incerto se "mínimo" significa "menos linhas de saída" ou "menos pedaços".

Um palpite incerto é que tem a ver com pedaços muito grandes.

    

Answer 1

No GNU diff , também usado no FreeBSD, o sinalizador --minimal aciona uma variação do algoritmo de Paul Eggert que faz com que ele "limite o custo a O(N**1.5 log N) ao preço de produzir saída abaixo do ideal para grandes entradas com diferenças ". Mais especificamente, faz com que não aplique várias heurísticas que lidam em encontrar apenas fechar as soluções ótimas e em lançar linhas "confusas" como diferenças extras.

No OpenBSD diff , que usa o antigo algoritmo diff do Unix dos anos 70, o algoritmo empregado é creditado a Harold Stone, e o --minimal flag aciona uma pesquisa que é (efetivamente não) delimitada pelo valor máximo de um inteiro não assinado em vez de pela raiz quadrada do tamanho do intervalo de linhas que estão sendo comparadas (ou 256, se for maior).

Leitura adicional

• Eugene W. Myers (novembro de 1986). " Um algoritmo de diferença O (ND) e suas variações ". Algoritmica . Volume 1. Edição 1–4. p. 251-266. DOI 10.1007 / BF01840446 .
• J. W. Hunt e M. D. McIlroy (junho de 1976). " Um Algoritmo para Comparação Diferencial de Arquivos ". Relatório 41. Ciência da Computação . Laboratórios Bell.
• Richard Hartman (1988-01-13). Algoritmo Unix diff (1) . [email protected]. comp.unix.questions.
• link
• link
• Revisão abrangente de algoritmos de diff, sua história e implementações