¿Alguien tiene, o conoce, una implementación de algoritmo de generación de parches binarios en C#?Generación de parches binarios en C#
Básicamente, comparar dos archivos (designados antigua y nueva ), y producir un archivo de revisión que se puede utilizar para actualizar el archivo de edad tener el mismo contenido que el nuevo archivo .
La implementación debería ser relativamente rápida y trabajar con archivos de gran tamaño. 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 parches pequeños pero tienen tiempo de ejecución O (n^2)).
Cualquier consejo o sugerencias 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 sólo funciona para los archivos que se pueden mantener en la memoria, es el siguiente:
- Coge los cuatro primeros bytes del archivo antiguo , llamar a esto el clave
- Añadir los bytes a un diccionario, donde clave -> posición, donde posición es la posición en la que cogí esos 4 bytes, 0, para empezar
- Saltar la primera de estas cuatro bytes, agarra otra 4 (3 solapamiento, 1 uno), y añadir al diccionario de la misma manera
- Repita los pasos 1-3 para todos los bloques de 4 bytes en el archivo de edad
- desde el comienzo del nuevo archivo , agarra 4 bytes, e intentar buscarlo en el diccionario
- Si lo encuentra, busque la medida más larga si hay varios, mediante la comparación de bytes de los dos archivos
- Codificar una referencia a esa ubicación en el archivo anterior, y omita el bloque coincidente en el nuevo archivo
- Si no lo encuentra, codificar 1 byte del archivo nuevo , e ignorar éste
- Repita los pasos 5-8 para el resto del archivo nueva
Esto es algo así como la compresión , sin ventanas, entonces 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 en cuanto a la memoria utiliza 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.
editar # 1: Aquí es una descripción mas 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, haga eso tome 4 bytes y agregue su posición al diccionario paso para todo en el archivo completo.
En tercer lugar, desde donde se inicia el archivo nueva, hacer el bucle de intentar localizar una combinación existente de 4 bytes, y busque la medida más larga. Asegúrese de que solo consideramos las posiciones del archivo anterior, o del anteriormente en el nuevo archivo, que actualmente estamos en. Esto garantiza que podamos reutilizar el material tanto en el archivo antiguo como en el nuevo durante la aplicación del parche.
Edición # 2: Source code to the above algorithm
Usted puede obtener una advertencia sobre el certificado teniendo algunos problemas. No sé cómo resolverlo, así que por el momento solo acepte el certificado.
La fuente utiliza una gran cantidad de otros tipos del resto de mi biblioteca para que los archivos no es todo lo que 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 que he encontrado dejar de mí lo que diga necesito saber.
O tal vez sólo soy densa ... :)
Me tomó un vistazo rápido en el algoritmo de ese sitio que le diste, y por desgracia no es utilizable. Un comentario del archivo de diferencias binarias 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, por lo que estoy buscando una solución más práctica.
Gracias por la respuesta, sin embargo, añaden un marcador en sus utilidades si alguna vez los necesito.
Edit # 1: Tenga en cuenta, 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 ese libro al que hace referencia y aunque la solución es buena para encontrar soluciones óptimas, su uso no es práctico debido a los requisitos de tiempo.
Editar # 2: Definitivamente voy a buscar la implementación de python xdelta.
El enlace del código fuente está muerto. ¿Puedes actualizarlo por favor? – lasseschou
Esa pieza de código en particular es posterior, aquí está mi versión actual, aunque no he mantenido esa biblioteca en años: https://lassevk.kilnhg.com/Code/LVK-for-NET/net-40/trunk/ Files/LVK.IO.Patching/Binary/Delta.cs –