numero - Generación de parches binarios en C#
convertir un numero decimal a binario octal y hexadecimal en c# (6)
Lo siento, no podría ser más ayuda. Definitivamente seguiría buscando en xdelta porque lo he usado varias veces para producir diferencias de calidad en archivos de 600MB + ISO que hemos generado para distribuir nuestros productos y funciona muy bien.
¿Alguien tiene, o conoce, una implementación de algoritmo de generación de parches binarios en C #?
Básicamente, compare dos archivos (designados antiguos y nuevos ) y genere un archivo de parche que se pueda utilizar para actualizar el archivo antiguo y tener los mismos contenidos que el nuevo archivo.
La implementación debería ser relativamente rápida y trabajar con archivos enormes. Debería mostrar tiempos de ejecución O (n) u O (logn).
Mis propios algoritmos tienden a ser pésimos (rápidos pero producen parches enormes) o lentos (producen pequeños parches pero tienen O (n ^ 2) tiempo de ejecución).
Cualquier consejo o punteros para la implementación sería bueno.
Específicamente, la implementación se usará para mantener los servidores sincronizados para varios archivos de datos grandes para los que tenemos un servidor maestro. Cuando los archivos de datos del servidor maestro cambian, necesitamos actualizar también varios servidores fuera del sitio.
El algoritmo más ingenuo que he hecho, que solo funciona para los archivos que pueden guardarse en la memoria, es el siguiente:
- Coge los primeros cuatro bytes del archivo anterior, llama a esto la clave
- Agregue esos bytes a un diccionario, donde key -> position , donde position es la posición donde agarré esos 4 bytes, 0 para comenzar
- Omita el primero de estos cuatro bytes, tome otro 4 (3 solapados, 1 uno) y agregue al diccionario de la misma manera
- Repita los pasos 1-3 para todos los bloques de 4 bytes en el archivo anterior
- Desde el comienzo del nuevo archivo, tome 4 bytes e intente buscarlo en el diccionario
- Si se encuentra, encuentre la coincidencia más larga si hay varias, comparando los bytes de los dos archivos
- Codifique una referencia a esa ubicación en el archivo anterior y omita el bloque coincidente en el nuevo archivo
- Si no se encuentra, codifique 1 byte del nuevo archivo y omítalo
- Repita los pasos 5 a 8 para el resto del nuevo archivo
Esto es algo así como la compresión, sin ventanas, por lo que usará mucha memoria. Sin embargo, es bastante rápido y produce parches bastante pequeños, siempre que trate de hacer que los códigos de salida sean mínimos.
Un algoritmo más eficiente con la memoria usa ventanas, pero produce archivos de parches mucho más grandes.
Hay más matices en el algoritmo anterior que salté en esta publicación, pero puedo publicar más detalles si es necesario. Sin embargo, siento que necesito un algoritmo diferente por completo, por lo que mejorar el algoritmo anterior probablemente no me lleve demasiado lejos.
Edición # 1 : Aquí hay una descripción más detallada del algoritmo anterior.
Primero, combine los dos archivos, para que tenga un archivo grande. Recuerde el punto de corte entre los dos archivos.
En segundo lugar, tome 4 bytes y agregue su posición al paso del diccionario para todo en el archivo completo.
En tercer lugar, desde donde se inicia el nuevo archivo, haga el ciclo con el intento de localizar una combinación existente de 4 bytes y encuentre la coincidencia más larga. Asegúrese de que solo consideramos las posiciones del archivo anterior, o de las primeras en el nuevo archivo de las que estamos actualmente . Esto garantiza que podamos reutilizar el material tanto en el archivo antiguo como en el nuevo durante la aplicación del parche.
Editar # 2 : código fuente para el algoritmo anterior
Puede recibir una advertencia sobre el certificado que tiene algunos problemas. No sé cómo resolverlo, así que por el momento solo acepte el certificado.
La fuente utiliza muchos otros tipos del resto de mi biblioteca para que el archivo no sea 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 subversión, llamado xdelta, pero a menos que ya sepas cómo funciona el algoritmo, los documentos que he encontrado no me dicen lo que necesito saber.
O tal vez soy solo denso ... :)
Eché un vistazo rápido al algoritmo de ese sitio que me diste, y desafortunadamente no se puede usar. Un comentario del archivo binario diff dice:
Encontrar un conjunto óptimo de diferencias requiere un tiempo cuadrático relativo al tamaño de entrada, por lo que se vuelve inutilizable muy rápidamente.
Mis necesidades no son óptimas, así que estoy buscando una solución más práctica.
Gracias por la respuesta, agregó un marcador a sus utilidades si alguna vez las necesito.
Edición n. ° 1 : Nota, veré su código para ver si puedo encontrar algunas ideas, y también le enviaré un correo electrónico más tarde con preguntas, pero he leído el libro al que hace referencia y aunque la solución es buena para encontrar soluciones óptimas, no es práctico en uso debido a los requisitos de tiempo.
Editar # 2 : Definitivamente voy a buscar la implementación de python xdelta.
Podría valer la pena verificar lo que algunos de los otros chicos están haciendo en este espacio y no necesariamente en la arena C # tampoco.
Esta es una biblioteca escrita en c #
SVN también tiene un algoritmo de diferencia binaria y sé que hay una implementación en Python, aunque no pude encontrarlo con una búsqueda rápida. Podrían darle algunas ideas sobre dónde mejorar su propio algoritmo
Si esto es para instalación o distribución, ¿ha considerado utilizar el SDK de Windows Installer? Tiene la capacidad de parchar archivos binarios.
http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx
¿Has visto VCDiff ? Es parte de una biblioteca Misc que parece bastante activa (última versión r259, 23 de abril de 2008). No lo he usado, pero pensé que valía la pena mencionarlo.
Esta es una directriz aproximada, pero la siguiente es para el algoritmo rsync que se puede usar para crear sus parches binarios.
bsdiff fue diseñado para crear parches muy pequeños para archivos binarios. Como se indica en su página, requiere un 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 m es el tamaño del nuevo archivo).
La implementación original está en C, pero un puerto C # se describe aquí y está disponible aquí .