Plus grandes sous-chaînes communes à deux chaînes

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.

Peut-être du côté de Algorithme de Needleman-Wunsch, remanié un peu pour tolérer le binaire ?

Bonjour,

Merci beaucoup, c'est très intéressant. C'est normalement l'algorithme que j'utiliserai si je n'en trouve pas d'autre, ou si le suivant ne marche pas.

En effet, je crois avoir trouvé quelque-chose d'intéressant :

On a la liste L des blocs, non-ordonnée. La première étape est de les ordonner, par rapport à la chaîne A, dans l'ordre des octets de départ.

Ensuite, on crée une deuxième liste M, vide au début. On prend le premier bloc de la liste L et on l'ajoute à M. Ensuite, on saute tous les blocs qui sont en conflit avec le premier. Puis, le bloc suivant qui va bien est ajouté à M.

Et ainsi de suite, on obtient une liste «bête mais qui marche» dans M.

Maintenant, il faut l'optimiser. L contient les blocs en conflit.

On explore chacun des blocs de L, et on compte, dans M, le nombre de blocs qu'il faudrait supprimer pour pouvoir ajouter ce bloc. Si c'est intéressant, donc qu'au final, on y gagne en taille totale, alors on fait ceci :

Tous les blocs de M qui sont en conflit avec le bloc qu'on veut ajouter voient leur "score" augmenté de 1. Ainsi, on sait qu'ils sont en conflit avec 1 bloc. Ensuite, le bloc est ajouté à la liste au bon endroit.

Et on recommence, on passe au bloc suivant. L'astuce ici est dans ce compteur, qui est gardé. Quand on "supprime" un bloc, donc qu'on passe son compteur de 0 à 1, on regarde tous les blocs qui sont en conflit avec lui mais pas avec le bloc qu'on veut ajouter, et on décrémente leur compteur. Ainsi, si le bloc A est masqué par B, mais qu'on ajoute C, qui supprime B, alors si A n'est pas en conflit avec C, il est remis comme étant bon.

Normalement, à la fin, on a la meilleure liste des blocs. Plus qu'à voir si ça marche, si ce n'est pas trop lent, et si c'est faisable sans prendre 10 000 lignes.

Ta méthode ressemble énormément a une exploration avec backtracking. :D

Je dé-résous mon sujet, ce n'est malheureusement pas encore bon avec ma technique.

Malheureusement, pour être efficace, il faut récursivement ajouter et supprimer des jetons aux blocs, ainsi qu'à ceux avec lesquels ils sont en conflit.

Comme dans un fichier normal, à peu près tous les blocs sont en conflits, on a donc une complexité encore pire que O(n^n) !

Bref, gérer le diff de deux fichiers de test de 11 et 14 octets marche très bien. Le diff de deux fichiers XML de 8Kio n'a jamais abouti : je l'ai arrêté au bout de 35 minutes de moulinage.

J'ai trouvé un joli petit algo de programmation dynamique qui me fait mon diff, mais il utilise O(nm) octets en mémoire. Le diff de mes deux fichiers XML de 8Kio a utilisé 72Mio de RAM, même s'il a été instantané. C'est beaucoup trop.

Je repars donc sur mes blocs, avec peut-être d'autres solutions. J'en ai une qui marchotte, possible à faire en O(n), ou en tous cas O(n²), mais faut voir comment l'exploiter.

EDIT :

Ok, je pense avoir trouvé un O(n) en temps, je suis content, et en plus c'est super simple :D .

Soit L la liste des blocs triés dans la chaîne A en fonction de leur octet de départ, M la liste des blocs triés dans la chaîne B en fonction de leur octet de départ, le tout dans une liste doublement chaînée (donc en fait chaque bloc a prev_a, prev_b, next_a, next_b)

Prendre B le premier bloc de la liste L.

Explorer tous les blocs qui suivent dans la chaîne A et qui sont en conflit avec lui, et leur ajouter la taille de B dans "bad". S'arrêter au premier bloc qui n'est pas en conflit avec. Recommencer avec les blocs qui suivent, mais dans la chaîne B. Il faut trouver un moyen de ne pas réajouter cette taille à ceux qui ont déjà été trouvés lors du premier tours.

Ainsi, en cas de blocs qui se croient "de loin", donc qui ne se suivent pas dans A mais bien dans B, on est certain d'avoir tous les conflits.

Cette partie est rapide, un bloc est généralement en conflit avec 2-3 autres seulement.

Ensuite, on passe au bloc suivant, toujours dans la liste L (la liste M ne sert qu'au deuxième tour décrit trois paragraphes au-dessus d'ici). Sauf que cette fois-ci, on regarde aussi dans les blocs précédants.

Le but est que chaque bloc ait comme score dans "bad" le nombre d'octets que son ajout dans la liste provoquerait comme suppression, donc son coût.

Le premier tour est fait, notre liste est prête. C'est quasi du O(n).

Ensuite, on réexplore une deuxième fois ces blocs. Pour chaque bloc, on regarde à nouveau avec lesquels il est en conflit. Si ce bloc a le plus petit score "bad" de tous les blocs avec lesquels il est en conflit, alors on le garde, on le met à l'état "ok".

Sinon, on le met à l'état "pas ok", et on retire à chacun de ses blocs conflit sa taille.

Et voilà, on continue. Sur le papier, le meilleur résultat s'obtient tout seul, avec une complexité qu'on pourraît qualifier de O(2n), donc O(n) si je ne me trompe pas.

Pour toujours une complexité mémoire de plus ou moins O(2n), ou n est la taille du plus grand des deux fichiers. Correct :) .