Diferenciação de dados - Data differencing

Na ciência da computação e na teoria da informação , a diferenciação de dados ou compressão diferencial está produzindo uma descrição técnica da diferença entre dois conjuntos de dados - uma origem e um destino. Formalmente, um algoritmo de diferenciação de dados toma como dados de origem de entrada e dados de destino e produz dados de diferença de modo que, dados os dados de origem e os dados de diferença, pode-se reconstruir os dados de destino (" remendar " a origem com a diferença para produzir o destino) .

Exemplos

Um dos exemplos mais conhecidos de diferenciação de dados é o utilitário diff , que produz diferenças linha por linha de arquivos de texto (e em algumas implementações, arquivos binários , sendo, portanto, uma ferramenta de diferenciação de propósito geral). A diferenciação de arquivos binários gerais está sob a rubrica de codificação delta , com um exemplo amplamente usado sendo o algoritmo usado em rsync . Um formato de diferenciação genérico padronizado é o VCDIFF , implementado em utilitários como o Xdelta versão 3. Um programa de diferenciação de alta eficiência (pequenos arquivos de patch) é o bsdiff, que usa bzip2 como uma etapa de compactação final no delta gerado.

Preocupações

As principais preocupações para diferenciação de dados são usabilidade e eficiência de espaço (tamanho do patch).

Se alguém deseja simplesmente reconstruir o destino com base na origem e no patch, pode simplesmente incluir o destino inteiro no patch e "aplicar" o patch descartando a origem e gerando o destino que foi incluído no patch; da mesma forma, se a origem e o destino tiverem o mesmo tamanho, pode-se criar um patch simples fazendo o XOR da origem e do destino. Em ambos os casos, o patch será tão grande quanto o alvo. Como esses exemplos mostram, se a única preocupação for a reconstrução do destino, isso será feito facilmente, às custas de um grande patch, e a principal preocupação para a diferenciação binária de uso geral é reduzir o tamanho do patch.

Especialmente para dados estruturados, temos outras preocupações, que se enquadram em grande parte na "usabilidade" - por exemplo, se alguém está comparando dois documentos, geralmente deseja-se saber quais seções foram alteradas, ou se algumas seções foram movidas - deseja-se entender como os documentos diferem. Por exemplo, "aqui, 'gato' foi alterado para 'cão' e o parágrafo 13 foi transferido para o parágrafo 14". Pode-se também desejar ter diferenças robustas - por exemplo, se dois documentos A e B diferem no parágrafo 13, pode-se desejar ser capaz de aplicar este patch mesmo que tenha alterado o parágrafo 7 de A. Um exemplo disso está em diff , que mostra quais linhas foram alteradas e onde o formato do contexto permite robustez e melhora a legibilidade humana.

Outras preocupações incluem a eficiência computacional, quanto à compactação de dados - encontrar um pequeno patch pode consumir muito tempo e muita memória.

Os melhores resultados ocorrem quando se tem conhecimento dos dados que estão sendo comparados e outras restrições: diff é projetado para arquivos de texto orientados por linha, particularmente código-fonte, e funciona melhor para eles; o algoritmo rsync é usado com base no fato de a origem e o destino estarem em uma rede um do outro e a comunicação ser lenta, de modo que minimiza os dados que devem ser transmitidos; e as atualizações para o Google Chrome usam um algoritmo personalizado para o arquivo e formato executável dos dados do programa.

Conexão com compressão de dados

A compressão de dados pode ser vista como um caso especial de diferenciação de dados - a diferenciação de dados consiste em produzir uma diferença dada uma fonte e um destino , com o patch produzindo um destino dado uma fonte e uma diferença, enquanto a compressão de dados consiste em produzir um arquivo compactado dado um alvo, e a descompactação consiste em produzir um alvo dado apenas um arquivo compactado. Assim, pode-se considerar a compactação de dados como uma diferenciação de dados com dados de origem vazios, o arquivo compactado correspondendo a uma "diferença de nada". Isso é o mesmo que considerar a entropia absoluta (correspondendo à compressão de dados) como um caso especial de entropia relativa (correspondendo à diferenciação de dados) sem dados iniciais.

Quando se deseja enfatizar a conexão, pode-se usar o termo compactação diferencial para se referir à diferenciação de dados.

Um dicionário que traduz a terminologia dos dois campos é dado como:

Referências