Algorithme de compression sans perte Broo et codage delta, comparaison avec Xdelta3. Développement de projets à domicile

Heureux de vous accueillir. Près d'un an s'est écoulé depuis la publication du dernier article et nous sommes prêts à vous dire ce qui est arrivé à l'algorithme lui-même et comment le codage delta est impliqué.

Entrée

Après la publication d'un article sur les améliorations de l'algorithme Broo, nous avons été confrontés à un obstacle pour améliorer le niveau de compression et les performances, à savoir, il était impossible d'améliorer le niveau de compression sans affecter la vitesse de décompression et vice versa. Je ferai une réservation tout de suite, des améliorations ont été apportées sans préjudice d'autres caractéristiques de l'algorithme, mais ces changements sont insignifiants, nous écrirons sur ces changements plus tard. Donc, après, nous avons pensé où nous pouvons appliquer notre expertise et nos connaissances accumulées dans une direction similaire. Et le choix est tombé codage delta .

Qu'est-ce que le codage delta?

Encodage delta ( Encodage delta Eng ) - une façon de représenter les données sous la forme de la différence ( delta ) entre les données série au lieu des données elles-mêmes.

En pratique, si les algorithmes de compression vous permettent de réduire la taille du fichier et de le stocker ou de le transférer sans aucune dépendance sur d'autres fichiers, les algorithmes de codage delta vous permettent de créer un patch (différence) d'une taille plus petite en fonction de deux fichiers (ensemble de données) et d'appliquer le patch pour le fichier ( ensemble de données) 1 - obtenir un fichier (ensemble de données) 2 .

L'application la plus courante pour le codage delta est la mise à jour des applications sur vos téléphones et PC. Au lieu de télécharger complètement l'application puis de remplacer les fichiers, un correctif d'une taille beaucoup plus petite est construit (en fonction du nombre de modifications), ce qui vous permet de télécharger la mise à jour beaucoup plus rapidement, et la vitesse d'application du correctif affecte directement la vitesse de mise à jour de l'application elle-même.

Si vous savez où le codage delta est utilisé, écrivez dans les commentaires.

À propos des modifications apportées à l'algorithme Broo

Comme nous l'avons dit, il y en a peu:

• Ajout de la prise en charge des fichiers de taille 2 ^ 64 pour x64 et 2 ^ 32 pour x32.
• Amélioration du taux de compression.

Ces changements sont encore au stade d'expérimentation et de débogage. Le principal problème - après avoir ajouté la prise en charge des fichiers volumineux, la vitesse de décompression a chuté de 20%, ce qui est inacceptable pour nous. Nous cherchons donc toujours une solution.

Ci-dessous, nous ne fournissons qu'un seul tableau de comparaisons de l'ancienne version de l'algorithme, celui expérimental et certains niveaux de zstd. Le fichier xml de l' article précédent .

Processeur: Intel i7-7700HQ

Mémoire: DDR4-2400

Comme de nombreux algorithmes, la vitesse dépend du processeur, comme nous pouvons le voir dans le tableau, la vitesse de décompression est plus de 1,5 fois plus rapide que celle du premier niveau zstd, sur le processeur Intel i7-7700HQ. Alors que sur l'ancien Intel i3-550, la vitesse de décompression était approximativement égale à la vitesse de décompression zstd, vous pouvez voir les tableaux de comparaison ici .

Cela suggère que vous pouvez effectuer une intégration plus étroite avec les processeurs individuels. Dépend des spécificités de la tâche.

Delta Coding et Broo

Comme vous l'avez peut-être deviné, nous avons développé notre propre algorithme de codage delta et lui avons donné le nom DBroo (Delta Broo).

Caractéristiques et caractéristiques principales:

• Prise en charge des tailles de fichier 2 ^ 64 pour x64 et 2 ^ 32 pour x32.
• Travaillez avec des données binaires.
• Une modification partielle du fichier de référence auquel le patch sera appliqué est autorisée.

Il existe des solutions toutes faites telles que diff, bsdiff, xdelta et autres. L'objectif était de trouver le meilleur (ainsi que abordable) dans cette direction et de rivaliser avec lui. Le Xdelta3 s'est avéré être le principal concurrent de manière purement expérimentale. Il donne une bonne compression et une vitesse d'application de patch assez rapide. Xdelta3 est également utilisé pour les mises à jour de CyanogenMod (maintenant LineageOS ).

Voyons maintenant le tableau de comparaison de DBroo et Xdelta3. En tant que fichier de référence, "xml" est utilisé, et en tant que nouveau fichier, le même mais modifié de manière aléatoire.

PS

Le développement est donné uniquement aux produits qui ont une demande sur le marché. Par conséquent, nous apprécions vos commentaires. Nous avons également créé une chaîne de télégramme .

Je vous remercie