Broo algoritmo de compresión sin pérdida y codificación delta, comparación con Xdelta3. Desarrollo de proyectos en casa

Me alegra darte la bienvenida. Ha pasado casi un año desde que se publicó el último artículo y estamos listos para decirle qué sucedió con el algoritmo en sí y cómo está involucrada la codificación delta.

Entrada

Después del lanzamiento del artículo sobre mejoras al algoritmo Broo, nos enfrentamos con un obstáculo para mejorar el nivel de compresión y rendimiento, es decir, era imposible mejorar el nivel de compresión sin afectar la velocidad de descompresión y viceversa. Haré una reserva de inmediato, las mejoras se realizaron sin perjuicio de otras características del algoritmo, pero estos cambios son insignificantes, escribiremos sobre estos cambios más adelante. Entonces, después, pensamos en dónde podemos aplicar nuestra experiencia y conocimiento acumulados en una dirección similar. Y la elección recayó en codificación delta .

¿Qué es la codificación delta?

Codificación delta ( codificación delta del inglés ): una forma de representar los datos en forma de diferencia ( delta ) entre los datos en serie en lugar de los datos en sí.

En la práctica, si los algoritmos de compresión le permiten reducir el tamaño del archivo y almacenarlo o reenviarlo sin ninguna dependencia de otros archivos, entonces los algoritmos de codificación delta le permiten construir un parche (diferencia) de un tamaño más pequeño basado en dos archivos (conjunto de datos) y aplicar el parche para el archivo ( conjunto de datos) 1 : obtenga un archivo (conjunto de datos) 2 .

La aplicación más común para la codificación delta es actualizar las aplicaciones en sus teléfonos y PC. En lugar de descargar la aplicación por completo y luego reemplazar los archivos, se construye un parche mucho más pequeño (dependiendo del número de cambios), que le permite descargar la actualización mucho más rápido, y la velocidad de aplicar el parche afecta directamente la velocidad de actualización de la aplicación misma.

Si sabe dónde más se usa la codificación delta, escriba los comentarios.

Acerca de los cambios en el algoritmo Broo

Como dijimos, hay algunos de ellos:

• Se agregó soporte para archivos de tamaño 2 ^ 64 para x64 y 2 ^ 32 para x32.
• Relación de compresión mejorada.

Estos cambios todavía están en la etapa de experimentación y depuración. El problema principal: después de agregar soporte para archivos grandes, la velocidad de descompresión se redujo en un 20%, lo que es inaceptable para nosotros. Así que todavía estamos buscando una solución.

A continuación proporcionamos solo una tabla de comparaciones de la versión anterior del algoritmo, la versión experimental y algunos niveles de zstd. El archivo xml del artículo anterior .

Procesador: Intel i7-7700HQ

Memoria: DDR4-2400

Como muchos algoritmos, la velocidad depende del procesador, como podemos ver en la tabla, la velocidad de descompresión es más de 1.5 veces más rápida que la del zstd de primer nivel, en el procesador Intel i7-7700HQ. Mientras que en el antiguo Intel i3-550, la velocidad de descompresión era aproximadamente igual a la velocidad de descompresión zstd, puede ver las tablas de comparación aquí .

Esto sugiere que puede realizar una integración más estrecha con procesadores individuales. Depende de los detalles de la tarea.

Delta Coding y Broo

Como habrás adivinado, desarrollamos nuestro propio algoritmo de codificación delta y le pusimos el nombre de DBroo (Delta Broo).

Principales características y características:

• Soporte para tamaños de archivo 2 ^ 64 para x64 y 2 ^ 32 para x32.
• Trabajar con datos binarios.
• Se permite la modificación parcial del archivo de referencia al que se aplicará el parche.

Hay soluciones listas para usar como diff, bsdiff, xdelta y otras. El objetivo era encontrar lo mejor (así como asequible) en esta dirección y competir con él. El Xdelta3 resultó ser el principal competidor de una manera puramente experimental. Ofrece una buena compresión y una velocidad de aplicación de parches bastante rápida. Xdelta3 también se usa para actualizaciones de CyanogenMod (ahora LineageOS ).

Ahora veamos la tabla de comparación de DBroo y Xdelta3. Como archivo de referencia, se usa "xml", y como archivo nuevo, el mismo pero modificado al azar.

PS

El desarrollo se da solo a aquellos productos que tienen una demanda en el mercado. Por lo tanto, agradecemos sus comentarios. También creamos un canal de telegramas .

Gracias