Revisión binaria de generación en C#
https://stackoverflow.com/questions/5831
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Alguien tiene o sabe de una revisión binaria de la generación de la implementación de algoritmos en C#?
Básicamente, comparar dos archivos (designado viejo y nuevo), y producir un archivo de parche que puede ser utilizada para actualizar la viejo archivo de tener el mismo contenido que el nuevo archivo.
La aplicación tendría que ser relativamente rápido, y trabajar con archivos de gran tamaño.Se debe exhibir O(n) o o(logn) tiempos de ejecución.
Mis propios algoritmos tienden a ser pésimo (rápido, pero producen grandes parches) o lento (se producen pequeños parches pero tiene O(n^2) tiempo de ejecución).
Cualquier consejo, o punteros para la aplicación sería bueno.
Específicamente, la aplicación será utilizada para mantener los servidores de sincronización de varias grandes ficheros de datos que tenemos un servidor maestro para.Cuando el maestro servidor de ficheros de datos de cambio, tenemos que actualizar varias apagado-sitio de servidores a la vez.
La mayoría de los ingenuos algoritmo que he hecho, que sólo funciona para los archivos que pueden guardarse en la memoria, es como sigue:
- Agarrar los primeros cuatro bytes de la viejo archivo, llamar a esto el clave
- Agregar los bytes a un diccionario, donde clave -> posición, donde posición es la posición en la que me agarró de los 4 bytes, 0 para comenzar con
- Saltar a la primera de estas cuatro bytes, toma otra 4, apartado 3, se superponen, 1), y agregar al diccionario de la misma manera
- Repita los pasos 1-3 para todos los 4 bytes de bloques en la viejo archivo
- Desde el inicio de la nuevo archivo, agarrar 4 bytes, y el intento de buscar en el diccionario
- Si lo encuentra, encuentra la coincidencia más larga, si hay varios, mediante la comparación de bytes de los dos archivos
- Codificar una referencia a su ubicación en la viejo archivo, y omitir la coincidencia de bloque en el nuevo archivo
- Si no se encuentra, codificar 1 byte desde el nuevo archivo y saltar
- Repita los pasos 5 a 8 para el resto de la nuevo archivo
Esto es un poco como la compresión, sin ventanas, por lo que se va a utilizar una gran cantidad de memoria.Es, sin embargo, bastante rápido, y produce muy pequeños parches, siempre trato de hacer los códigos de salida mínima.
Una memoria más eficiente algoritmo utiliza ventanas, pero produce mucho más grande de archivos de parche.
Hay más matices que el algoritmo anterior que me he saltado en este post, pero me pueden enviar más detalles si es necesario.Yo, sin embargo, siento que necesito un algoritmo diferente por completo, por lo que la mejora en el algoritmo anterior es, probablemente, no va a conseguir de mí lo suficiente.
Edición #1:Aquí está una descripción más detallada del algoritmo anterior.
En primer lugar, se combinan los dos archivos, de modo que usted tiene un archivo grande.Recuerde que el corte entre los dos archivos.
En segundo lugar, hacer que coge 4 bytes y agregar su posición en el diccionario paso de todo en todo el archivo.
En tercer lugar, desde donde el nuevo archivo comienza, hacer el bucle con el de intentar buscar una combinación existente de 4 bytes, y encontrar el más largo del partido.Asegúrese de considerar sólo a las posiciones de la edad de archivo, o de anteriormente en el nuevo archivo que actualmente estamos en.Esto asegura que podemos reutilizar el material en ambos el antiguo y el nuevo archivo durante la revisión de la aplicación.
Edición #2: El código fuente para el algoritmo anterior
Usted puede recibir una advertencia sobre el certificado de tener algunos problemas.No sé cómo resolver que así que por el momento solo aceptamos el certificado.
La fuente utiliza un montón de otros tipos del resto de mi biblioteca, de manera que el archivo no es todo lo que se necesita, pero esa es la implementación del algoritmo.
@lomaxx, he tratado de encontrar una buena documentación para el algoritmo utilizado en la subversión, llamado xdelta, pero a menos que usted ya sabe cómo funciona el algoritmo, los documentos en los que he encontrado no me digas lo que necesito saber.
O tal vez sólo estoy densa...:)
Me echó un rápido vistazo en el algoritmo desde el sitio de que se le dio, y que, desafortunadamente, no es utilizable.Un comentario desde el binario archivo diff dice:
La búsqueda de un conjunto óptimo de las diferencias requiere cuadrática tiempo con respecto a el tamaño de entrada, por lo que se convierte en inutilizable muy rápidamente.
Mis necesidades no son óptimas, aunque, así que estoy buscando una solución más práctica.
Gracias por la respuesta, aunque, añade un marcador para que sus utilidades si alguna vez me necesitan.
Edición #1:Nota, voy a mirar su código para ver si puedo encontrar algunas ideas, y también voy a enviar un correo electrónico más tarde con preguntas, pero he leído que el libro de referencias y a pesar de que la solución es buena para la búsqueda de soluciones óptimas, es poco práctico en el uso debido a los requerimientos de tiempo.
Edición #2:Definitivamente, voy a cazar a la de python xdelta aplicación.
Solución
Lo siento, no podía ser de más ayuda.Me gustaría definitivamente seguir buscando en xdelta porque lo he utilizado un número de veces para producir la calidad de los diffs de 600 MB+ archivo ISO que hemos generado para la distribución de nuestros productos y se desempeña muy bien.
Otros consejos
bsdiff fue diseñado para crear manchas muy pequeñas para archivos binarios.Como se indica en su página, se requiere max(17*n,9*n+m)+O(1) bytes de memoria y se ejecuta en O((n+m) log n) tiempo (donde n es el tamaño del archivo antiguo y m es el tamaño del nuevo archivo).
La implementación original está en C, pero C# puerto se describe aquí y disponible aquí.
Has visto VCDiff?Es parte de una Miscelánea de la biblioteca que parece ser bastante activo (última versión r259, 23 de abril de 2008).No lo he utilizado, pero pensé que valía la pena mencionar.
Podría ser vale la pena mirar lo que algunos de los otros chicos están haciendo en este espacio y no necesariamente en el C# arena bien.
Esta es una biblioteca escrita en c#
SVN también tiene un binario diff algoritmo y sé que hay una implementación en python, aunque no lo pude encontrar con una búsqueda rápida.Se podría dar algunas ideas sobre dónde mejorar su propio algoritmo
Si esto es para la instalación o distribución, se ha considerado el uso de la SDK de Windows Installer?Tiene la capacidad de revisión de archivos binarios.
http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx
Esta es una guía aproximada, pero la siguiente es para el algoritmo de rsync que puede ser utilizado para crear su binario parches.
