Forum Programmation.autre [Algorithmie] Aire la plus grande de blocs se superposant

Posté par  (site web personnel) .
Étiquettes : aucune
4
14
jan.
2010
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.

La ligne du dessus représente une suite de rectangles, qui commencent tous à un certain caractère et ont une certaine taille, positive et non-nulle.

La ligne du dessous représente le résultat que je veux obtenir.

Le but est, parmi les rectangles de la ligne du dessus, de trouver la suite des rectangles qui ne se chevauchent pas, et qui forment la plus grande surface (longueur totale la plus importante).

La difficulté étant de trouver ces rectangles, et rapidement (il y en aura des milliers dans l'application finale). Il est capital que la somme de la taille des rectangles trouvés soit la plus importante.

Il serait aussi excellent que les rectangles trouvés soient dans l'ordre (donc d'abord celui qui commence le plus à droite, puis le suivant, etc).

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. Non, il servira à implémenter un algorithme de diff binaire dans mon gestionnaire de paquets Setup.

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.

Une fois cette dernière pièce du puzzle rassemblée, le résultat sera bien entendu disponible dans Setup, ainsi que dans une application C pur, libre bien entendu, à part.

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 :-) .

  • # réflexion inverse

    Posté par  . Évalué à 3.

    En 2min. A voir si c'est valable:

    Tu pars des espaces vides.
    Tu notes que chaque espace vide est défini par 2 limites extremes de rectangles, tu peux donc générer nV possilités d'espaces vides, donc certains sont corrects pour ton résultat final.
    Ensuite, tu prends les limites entre chaque vide, et tu tentes de faire correspondre un rectangle avec les mêmes limites, et dont ses limites ne sont pas contenues dans un autre.
    Tu as la maximisation des rectangles en commençant à chercher des correspondances en traitant les espaces vides les plus petits en premier.

  • # 1D / 2D ?

    Posté par  . Évalué à 4.

    Si on remplace les rectangles par des droites et qu'on met ça sur une seule dimension ça donne un problème plus simple à résoudre:
    http://www.facebook.com/careers/puzzles.php?puzzle_id=15

    Il se résoud en 0(n) si je me souviens bien. Si tu arrives à résoudre celui-là, ça doit assez facilement être adaptable à ton problème.

    • [^] # Re: 1D / 2D ?

      Posté par  (site web personnel) . Évalué à 1.

      Merci beaucoup, c'est effectivement très proche de ce que je cherche. Malheureusement, les gens qui résolvent ce puzzle ne devraient pas spécialement vouloir que le secret soit révélé, et le résoudre moi-même consisterait à résoudre mon problème, donc ça ne m'avance pas.

      Merci beaucoup tout de même :-) . Ça m'apprend que ça doit pouvoir se résoudre en O(n).

      • [^] # Re: 1D / 2D ?

        Posté par  (site web personnel) . Évalué à 3.

        Je me répond :

        Une solution trouvée ici : http://www.simmoril.com/blog/?p=293 semble très intéressante. Elle semble avoir une complexité O(n²), et utilise la récursivité ainsi que plein de listes (mais celui ayant codé ça en Python, il ne l'a peut-être pas vu, ou il s'en fiche un peu). Néanmoins, c'est déjà mieux que rien si je ne trouve rien de mieux.

  • # Réinventer la roue ?

    Posté par  (site web personnel) . Évalué à 5.

    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.
    J'ai bien vu que tu aimes réinventer la roue, mais je me demande ici pourquoi. Pourrais tu nous dire quelles sont les raisons qui te poussent à éliminer d'emblée ces outils ?

    Le diff binaire ça a l'air chaud, Mandriva avait tenté deltarpm dans le même but que toi, et cela avait été abandonné rapidement à cause des nombreux problèmes que cela soulevait. Tu peux trouver des infos à ce sujet sur la mailing list cooker.

    • [^] # Re: Réinventer la roue ?

      Posté par  (site web personnel) . Évalué à 6.

      DeltaRPM marche, et utilise l'algorithme décrit en bas de cette page : http://www.daemonology.net/bsdiff/ (lien «doctoral thesis»).

      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  (site web personnel) . Évalué à 1.

      Un souci d'un gestionnaire de paquets fonctionnant par deltas est la taille du dépôt des paquets (il me semble que sous Arch, ça avait été une opposition avancée contre le passage à une distribution par delta). En effet, si tu proposes la libtoto-1, quand la libtoto-2 sort, tu doit avoir sur ton dépôt non seulement libtoto-2, mais aussi libtoto-delta-1-2. Et quand libtoto-3 sort, tu dois avoir libtoto-delta-2-3, mais il serait aussi très intéressant d'avoir libtoto-delta-1-3 pour les utilisateurs qui ont raté une version (ou alors, les utilisateurs qui ratent une version sont obligés de reprendre un libtoto-3 tout frais ? mais dans ce cas on perd l'intérêt d'une distribution par delta...)

      Dans la même veine : il est de bon goût de garder (pour des raisons d'archivage, d'audit des évolutions, tout ça) les versions passées des paquets. Donc dans l'exemple précédent, on aurait sur le dépôt libtoto-1, libtoto-2, libtoto-3, libtoto-delta-1-2, libtoto-delta-1-3, libtoto-delta-2-3... Rapidement on ne s'en sort plus.

      Qu'est-ce que tu comptes faire pour ceci ? Ne supporter les mises à jour (donc la construction des delta) que entre la version courante et les 3 versions précédentes ?

      • [^] # Re: Réinventer la roue ?

        Posté par  (site web personnel) . Évalué à 3.

        C'est prévu.

        Un peu avant la sortie de Setup 0.1-alpha1, il était prévu de rassembler Sepa et Repoma (outils de création de paquets et de gestion des dépôts) dans Setup. Ceci amenait plusieurs avantages :

        * Pour Sepa, sachant que c'est dans la liblpackage, la création de paquet est facilité et un greffon KDevelop est envisageable. C'est typiquement un truc qui plaît au décideur pressé, un IDE qui permet de faire de l'élaboration à la distribution d'un projet
        * Pour Repoma, le C++ est largement plus puissant que le bash, et permet par exemple de gérer une base de donnée SQL en utilisant QtSql

        C'est ce dernier point qui est intéressant, car cette base de donnée peut servir à conserver plein d'informations, donc les deltas, leurs versions, etc.

        Du côté de l'arbre du dépôt, les informations de deltas seront ajoutées au fichier packages.xz, sous la forme

        Deltas=version_source~version_cible version_source~version_cible ...

        Ainsi, quand on a la version source et la version cible, Setup peut calculer les deltas qu'il appliquera, s'il doit en appliquer plusieurs, et dans quel ordre. Par exemple, pour passer de la version 1.1 à la version 1.4 du paquet proposant ceci :

        Deltas=1.1~1.2 1.1~1.3 1.2~1.3 1.2~1.4 1.3~1.4

        Setup sait qu'il doit par exemple appliquer 1.1~1.3 puis 1.3~1.4. Voilà, le dépôt n'est pas pollué par trop de deltas, mais l'utilisateur sera toujours facilement à jour :) .

  • # ...

    Posté par  . Évalué à 3.

    ne serait-ce pas un algorithme du même style ? À vue de nez ça ressemble un peu à ce que doit faire LaTeX quand il choisit correctement les espaces entre les mots pour obtenir le fameux "gris typographique", et il le fait en une seule passe (!).

    sinon peut-être regarder du côté de l'algorithme de Viterbi, mais celui-ci n'est pas efficace pour de grandes quantités de données...

  • # Mots clefs

    Posté par  (site web personnel) . Évalué à 2.

    Programmation dynamique
    minimisation
    maximisation
    heuristique


    Bon, je suis curieux… Tu veux avoir une représentation 2D de tes binaires ?
    Si oui, tu sais qu'un tout petit changement de code source peut faire de gros changements dans le code (comme une simple variable en plus qui chamboule toute ton allocation de registres…) ?

    Si non, alors je trouve sympa l'idée d'utiliser des quad-trees pour « patcher » une image, c'est visuel !

  • # Courgette

    Posté par  . Évalué à 1.

    Je ne sais pas sur quels objets binaires tu veux faire le diff, mais Google a créé Courgette [http://dev.chromium.org/developers/design-documents/software(...)] pour les mises à jour de Chrome.
    Courgette optimise le diff car il sait qu'il travaille sur des binaires exécutables. Si tu connais à l'avance sur quels objets binaires tu vas travailler, tu peux peut-être aussi faire des optimisations dans ce sens.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.