Algoritmo para diffing eficiente de grandes arquivos

Question

Eu tenho que armazenar dois arquivos A e B que são ambos muito grande (como 100GB). No entanto B é provável que seja semelhante em grandes partes de A para poderia armazenar A e diff (A, B). Há dois aspectos interessantes a este problema:

1. Os arquivos são grandes demais para ser analisado por qualquer biblioteca diff eu conheço, porque eles são na memória
2. Eu não realmente precisa de um diff - um diff normalmente tem inserções, edições e exclusões porque ele é feito para ser lido por seres humanos. I pode ir longe com menos informações:. Eu só preciso "nova gama de bytes" e "cópia bytes do arquivo antigo de arbitrária compensar"

Atualmente, estou em uma perda para a forma de calcular o delta de A para B nestas condições. Alguém sabe de um algoritmo para isso?

Mais uma vez, o problema é simples:. Escrever um algoritmo que pode armazenar os arquivos A e B com tão poucos bytes possível dado o fato de que ambos são bastante semelhantes

Informações adicionais: Embora grandes peças podem ser idênticos que são susceptíveis de ter diferentes deslocamentos e estar fora de ordem. O último fato é por isso que um diff convencional pode não economizar muito.

Answer 1

Dê uma olhada algoritmo RSYNCs, como ele é projetado praticamente para fazer exatamente isso para que ele possa eficientemente copiar deltas. E o algoritmo é muito bem documentado, se bem me lembro.

Answer 2

Você pode usar rdiff, que funciona muito bem com arquivos grandes. Aqui eu criar um diff em dois arquivos grandes A e B:

1. Criar uma assinatura de um arquivo, com por exemplo.

   rdiff signature A sig.txt
   

2. usando o sig.txt assinatura arquivo gerado e o outro arquivo grande, criar o delta:

   rdiff delta sig.txt B delta
   

3. Agora delta contém todas as informações que você precisa para recriar B arquivo quando você tem tanto A e delta. Para recriar B, run

   rdiff patch A delta B
   

No Ubuntu, basta executar sudo apt-get install rdiff para instalá-lo. É muito rápido, eu recebo cerca de 40 MB por segundo no meu PC. Eu apenas tentei-o em um arquivo de 8GB, e a memória usada pelo rsync foi de cerca de 1MB.

Answer 3

Isso é exatamente o problema conhecido como "desduplicação de dados" . A abordagem mais comumente utilizado é:

• Leia sobre os arquivos em blocos:
  • Split os dados dos chamados "blocos". A abordagem mais frequentemente utilizado é chamado de "conteúdo definido Chunking usando o método Rabins Fingerprinting" ( Código ). Utilizando essa fragmentação conduz a uma melhor aproximação de redução de redundância na maioria dos dados ajustados, em seguida, utilizando pedaços de tamanho estáticas (por exemplo, mostrado aqui ).
  • Fingerprint os pedaços usando um método de impressão digital criptográfica, por exemplo SHA-256.
  • Loja as impressões digitais em um índice e pesquisa para cada pedaço se a impressão digital já é conhecido. Se a impressão digital é conhecido, não há necessidade de armazenar o pedaço uma segunda vez. Somente quando a impressão digital não é conhecida, os dados têm de ser armazenados.

Tal algoritmo desduplicação de dados não é tão exata como por exemplo xdelta , mas é mais rápido e mais escalável para grandes conjuntos de dados. A impressão digital de fragmentação e é realizada com cerca de 50 Mb / s por núcleo (Java). O tamanho do índice depende das redundâncias, o tamanho do bloco e o tamanho dos dados. Para 200 GB, deve caber na memória para tamanhos pedaço de exemplo 16KB.

Bentley e Mciloys é muito semelhante (por exemplo, usado por Googles BigTable), porém não estou ciente de quaisquer ferramentas de linha de out-of-the comando caixa utilizando a técnica de compressão.

O "fs-c" projeto de código aberto contém a maior parte do código que é necessário. No entanto, a própria fs-c tenta apenas para medir os despedimentos e os arquivos analzye na memória ou usando um Hadoop aglomerado .

Answer 4

uma pergunta é qual é o tamanho de registro em seus arquivos, ou seja, pode o byte mudança compensações por byte ou fazer os arquivos consistem em, digamos, blocos 1024B. Supondo que os dados são orientadas para o byte, você pode fazer o seguinte:

1. Criar uma matriz de sufixo para o ficheiro A. Esta matriz é uma permutação de todos os valores do índice para o ficheiro R. Se uma tem 2 ^ 37 bytes, em seguida, a matriz é mais fácil índice representados por números inteiros de 64 bits, então cada byte (offset para o arquivo) corresponde a 8 bytes na matriz índice, de modo que o índice de matriz vai ser de 2 ^ 40 bytes de comprimento, em seguida. Por exemplo. 800 GB, por exemplo. Você também pode indexar apenas cada posição 1024, por exemplo, para reduzir o tamanho da matriz índice. Isso, então, deteriora a qualidade da embalagem dependendo de quanto tempo as pistas médios de fragmentos copiáveis ??são.

2. Agora, em seguida, a avidez embalar o arquivo B de começar desde o seu início no deslocamento o = 0 e, em seguida, usar a matriz de índice para encontrar o jogo mais longo da A que coincide com os dados a partir de 'o'. Você saída do par no arquivo compactado. Isso leva no seu caso, sem qualquer codificação 16 bytes, por isso, se o prazo é <16 bytes-lhe espaço realmente perder. Isto pode ser facilmente remediado através da utilização, em seguida, codifica bits de nível e usando um marcador de bit de marca quer codificar um byte isolado (marcador + 8 bits = 9 bits) ou um par de deslocamento / comprimento (marcador + 40 bits + 40 bits = 81 bits), dizem. Após a embalagem do fragmento mais longo em o, aumento o para o próximo byte após o fragmento e repetir até que no final do arquivo.

A construção e uso de uma matriz sufixo é fácil e você deve encontrar referências facilmente. Em alta velocidade aplicações as pessoas usam árvores de sufixo ou tentativas sufixo ao invés, que são mais complexos para manipular, mas fornecem mais rápido de pesquisa. No seu caso, você vai ter a matriz no armazenamento secundário e se a velocidade de corrida da fase de embalagem não é um problema uma matriz sufixo deve ser suficiente.

Answer 5

Dependendo de suas necessidades de desempenho, você poderia fugir com amostragem os pedaços você impressão digital, e crescente-los quando eles combinam. Dessa forma, você não tem que executar uma verificação em seu arquivo grande inteiro.

Se precisar de alinhamentos arbitrários de bytes e você realmente se preocupam com o desempenho, olhar para o simhash < a href = "http://svcs.cs.pdx.edu/gitweb/simhash.git" rel = "nofollow noreferrer"> algoritmo , e usá-lo para encontrar blocos semelhantes, mas não alinhados.