Algoritmo para diferenciar eficiente de archivos de gran tamaño

Question

Tengo que guardar dos archivos A y B, que son a la vez muy grande (como de 100 GB). Sin embargo B es probable que sea similar en grandes partes a A por lo que podía almacenar A y diff (A, B). Hay dos aspectos interesantes a este problema:

1. Los archivos son demasiado grandes para ser analizados por cualquier biblioteca diff no conozco porque están en memoria
2. No necesita realmente un diff - un diff tiene típicamente insertos, edita y elimina porque está destinado a ser leído por los seres humanos. Puedo salir con menos información:. Sólo necesito "nueva gama de bytes" y "bytes de copia de archivo antiguo de desplazamiento arbitrario"

Actualmente estoy en una pérdida en la forma de calcular el delta de A a B en estas condiciones. ¿Alguien sabe de un algoritmo para esto?

Una vez más, el problema es simple:. Escribir un algoritmo que puede almacenar los archivos A y B con el menor número de bytes como sea posible, dado el hecho de que ambos son bastante similares

Otros detalles: A pesar de las grandes piezas pueden ser idénticos que son propensos a tener diferentes desplazamientos y estar fuera de orden. El último hecho es la razón por un diff no convencional podría ahorrar mucho.

Answer 1

Tome un vistazo a rsyncs algoritmo, ya que está diseñada más o menos para hacer exactamente esto lo que se puede copiar de manera eficiente los deltas. Y el algoritmo está muy bien documentada, por lo que recuerdo.

Answer 2

Puede utilizar rdiff, que funciona muy bien con archivos de gran tamaño. Aquí se crea un diff de dos archivos de gran tamaño y A B:

1. Crea una firma de un archivo, con por ejemplo.

   rdiff signature A sig.txt
   

2. utilizando el sig.txt archivo de firma generada y el otro archivo grande, crear el delta:

   rdiff delta sig.txt B delta
   

3. Ahora delta contiene toda la información que necesita para recrear B archivo cuando se tiene tanto A y delta. Para recrear B, dirigido

   rdiff patch A delta B
   

En Ubuntu, tan sólo ejecute sudo apt-get install rdiff para instalarlo. Es bastante rápido, me sale alrededor de 40 MB por segundo en mi PC. He intentado en un archivo de 8 GB y la memoria utilizada por rsync fue alrededor de 1 MB.

Answer 3

Esto es exactamente el problema conocido como "duplicación de datos" . El método más comúnmente utilizado es:

• Leer sobre los archivos en bloques:
  • dividir los datos de los llamados "bloques". El enfoque más utilizado se llama "contenido definido operaciones de fragmentación utilizando el método Rabins Fingerprinting" ( Código ). Usando este enfoque fragmentación conduce a una mejor eliminación de datos duplicados en la mayoría de conjunto de datos a continuación, utilizando trozos del tamaño estáticos (por ejemplo, se muestra aquí ).
  • huellas dactilares Las trozos utilizando un método de toma de huellas dactilares criptográfica, por ejemplo SHA-256.
  • Guarde las huellas dactilares en un índice y de búsqueda para cada trozo si la huella es ya conocido. Si se conoce la huella digital, no hay necesidad de almacenar el trozo por segunda vez. Sólo cuando la huella digital no se conoce, los datos tienen que ser almacenados.

Tal algoritmo duplicación de datos no es tan exacta como por ejemplo xdelta , pero es más rápido y más escalable para grandes conjuntos de datos. El CHUNKING y huellas digitales se lleva a cabo con alrededor de 50 MB / s por núcleo (Java). El tamaño del índice depende de las redundancias, el tamaño del fragmento y el tamaño de los datos. Para 200 GB, que debe encajar en la memoria para los tamaños de fragmento de, por ejemplo, 16KB.

Bentleys y Mciloys enfoque de compresión es muy similar (utilizado por ejemplo, por googles BigTable), sin embargo no estoy al tanto de alguna línea de fuera de la caja de comandos utilizando la técnica de compresión.

El "fs-c" proyecto de código abierto contiene la mayor parte del código que es necesario. Sin embargo, sí fs-c trata solamente de medir los despidos y los archivos analzye en memoria o utilizando un clúster Hadoop .

Answer 4

una pregunta es ¿cuál es el tamaño del registro en sus archivos, es decir, puede cambiar las compensaciones de byte a byte o hacer los archivos consisten en, digamos, 1024b bloques. Suponiendo que los datos están orientadas a byte, se puede hacer lo siguiente:

1. Crea una matriz de sufijo para el archivo A. Esta matriz es una permutación de todos los valores de índice para el archivo de A. Si A tiene 2 ^ 37 bytes entonces la matriz índice se más fácil representados por números enteros de 64 bits, por lo cada byte (desplazamiento en el fichero) se corresponde con 8 bytes de la matriz de índice, por lo que la matriz de índice será de 2 ^ 40 bytes de longitud entonces. P.ej. 800 GB, por ejemplo. Puede también índice sólo cada lugar 1024a, por ejemplo, para reducir el tamaño de la matriz de índice. Esto entonces detoriates la calidad de embalaje dependiendo de cuánto tiempo se ejecuta el promedio de los fragmentos son copiables.

2. Ahora bien para empacar con avidez el archivo B se inicia desde su inicio en el offset o = 0 y luego usar la matriz de índice para encontrar la combinación más larga de A que coincide con los datos a partir de 'O'. Usted salida de la pareja en el archivo empaquetado. Esto toma en su caso sin ningún tipo de codificación de 16 bytes, por lo que si la carrera es <16 bytes en realidad se pierde espacio. Esto puede ser fácilmente remediado mediante el uso de la codificación a nivel de bit a continuación, y el uso de un marcador de bit para marcar ya sea que codifican un byte aislado (marcador + 8 bits = 9 bits) o un par offset / longitud (marcador de + 40 bits + 40 bits = 81 bits), dicen. Después de empacar el fragmento más largo en O, aumentar o al siguiente byte después del fragmento y repetir hasta que al final del archivo.

La construcción y el uso de un arreglo de sufijos es fácil y usted debe encontrar referencias fácilmente. En aplicaciones de alta velocidad de la gente usa sufijo árboles o sufijo intenta en cambio, que son más complejos de manipular, sino proporcionar las operaciones de búsqueda más rápido. En el caso de que vas a tener la matriz de almacenamiento secundario y si la velocidad de ejecución de la fase de embalaje no es un problema de un arreglo de sufijos debería ser suficiente.

Answer 5

En función de sus requisitos de rendimiento, podría salirse con el muestreo de los trozos que la huella digital, y el crecimiento de ellos cuando coincidan. De esa manera usted no tiene que ejecutar una suma de comprobación en el archivo de gran tamaño entero.

Si necesita alineaciones tamaños arbitrarios y que realmente se preocupan por el rendimiento, mira el simhash < a href = "http://svcs.cs.pdx.edu/gitweb/simhash.git" rel = "nofollow noreferrer"> algoritmo , y lo utilizan para encontrar bloques similares pero no alineados.