Je n'ai pas encore eu la possibilité de tester ce que j'ai trouvé, mais c'est bien plus complet que le petit morceau que je demande ici. La particularité de mon algorithme est qu'il a une petite chance de produire les patches les plus petits possibles, ou en tous cas de s'en approcher fortement.
En effet, les algos existants éliminent des données, comme la thèse que je donne plus haut qui contient un truc du genre «Si le bloc ne correspond pas à plus de 50%, faire comme s'il ne correspond pas, car il y a des chances qu'il ne corresponde pas».
Je me concentre sur la petitesse du patch, par sur la rapidité. J'ai déjà sorti des artilleries très lourdes pour préparer cette liste de blocs, mais pour le moment, ça va (moins d'une seconde pour les premières passes du delta d'un fichier de 300Kio).
L'application du patch est déjà codée (avec des patchs faits-mains), et est de complexité O(taille du patch), alors que bsdiff applique les patches en O(m+n), avec m et n les tailles des anciens nouveau fichiers.
Ce problème de blocs est vraiment le dernier truc que je dois résoudre. Je planche sur ce diff depuis un mois maintenant (il n'y à qu'à regarder de quand cesse le dernier gros commit de Setup, ici la sortie de l'alpha1), c'est bientôt fini.
[^] # Re: Réinventer la roue ?
Posté par steckdenis . En réponse au message [Algorithmie] Aire la plus grande de blocs se superposant. Évalué à 6.
Je n'ai pas encore eu la possibilité de tester ce que j'ai trouvé, mais c'est bien plus complet que le petit morceau que je demande ici. La particularité de mon algorithme est qu'il a une petite chance de produire les patches les plus petits possibles, ou en tous cas de s'en approcher fortement.
En effet, les algos existants éliminent des données, comme la thèse que je donne plus haut qui contient un truc du genre «Si le bloc ne correspond pas à plus de 50%, faire comme s'il ne correspond pas, car il y a des chances qu'il ne corresponde pas».
Je me concentre sur la petitesse du patch, par sur la rapidité. J'ai déjà sorti des artilleries très lourdes pour préparer cette liste de blocs, mais pour le moment, ça va (moins d'une seconde pour les premières passes du delta d'un fichier de 300Kio).
L'application du patch est déjà codée (avec des patchs faits-mains), et est de complexité O(taille du patch), alors que bsdiff applique les patches en O(m+n), avec m et n les tailles des anciens nouveau fichiers.
Ce problème de blocs est vraiment le dernier truc que je dois résoudre. Je planche sur ce diff depuis un mois maintenant (il n'y à qu'à regarder de quand cesse le dernier gros commit de Setup, ici la sortie de l'alpha1), c'est bientôt fini.