Bonjour,
Dans le cadre d'un projet visant à créer un algorithme de différences binaires, j'ai besoin de votre aide pour m'aider dans une de ces étapes de cet algorithme.
Avant toute chose, je tiens à préciser que je ne peux pas réutiliser l'existant, comme bsdiff, xdelta3, voire même tout ce qui est zlib, bzip2, etc.
Pour illustrer mon problème, voici une image représentant la chose.
Les deux premières lignes représentent les points communs entre la chaîne A et la chaîne B, qui sont des suites d'octets ici.
Les deux lignes du dessous représentent le résultat que je souhaiterais obtenir.
Les principe est simple : à partir des points communs trouvés dans les deux premières lignes, trouver les points communs correspondant à certaines conditions et ayant la longueur totale la plus importante.
- Deux blocs ne peuvent aucunement se superposer
- Deux blocs ne peuvent pas «se croiser», donc ils doivent rester dans le même ordre
Si possible, il serait bien que l'algorithme me classe les points communs trouvés dans l'ordre (d'abord le premier, etc). Ça peut être par rapport à la chaîne A ou B, sachant que les points communs ne peuvent pas se croiser, si Aa > Ab, alors Ba > Bb.
Notez que je ne vous demande nullement de faire un de mes devoirs à ma place. Ce problème n'est pas universitaire, il ne vient pas d'un éventuel travail. C'est simplement la dernière pièce qui me manque pour créer un algorithme de différences binaires qui pourrait être pas mal.
Pourquoi ne pas réutiliser bsdiff ? Parce que une fois ce problème de rectangles résolu, l'algorithme produira des différences bien plus petites. En effet, bsdiff et autres ne sont pas «exacts» : quand le problème devient complexe, ou qu'ils ont du mal à trouver les points communs, ils abandonnent, ce qui fait grossir les diffs. Jusqu'à présent, je n'ai utilisé que des algorithmes exacts, ce qui fait que tous les points communs sont trouvés, absolument tous. Il suffit maintenant de trouver ces meilleurs blocs pour avoir un algorithme complet.
Une fois cette dernière pièce du puzzle rassemblée, le résultat sera disponible dans une application C pur, libre bien entendu.
Je publierai également le détail de l'algorithme utilisé. Vous pouvez demander pour avoir votre nom cité dedans. Bien évidemment, aucun brevet logiciel ne sera déposé dessus, et le nécessaire sera fait pour qu'il n'y en ai jamais.
Merci d'avance.
PS: Et pour ceux qui seraient tentés de me dire «cherche un peu, Google est ton ami», je suis en train de plancher là dessus depuis le soir de Noël, et j'ai été jusqu'à explorer le puzzle Gattaca de Facebook, ainsi que diverses solutions.
Partager