[Compression] Création d'un dictionnaire des récurrences

Des soucis pour hacker votre jeu ? C'est ici qu'il faut exposer votre problème.
Avatar de l’utilisateur
rid
Dieu Suprême du flood
Messages : 2046
Inscription : 04 janv. 2005, 22:17
Contact :
[Compression] Création d'un dictionnaire des récurrences

Message non lu par rid »

Bonsoir, certains d'entre vous savent que je bosse actuellement au hack du jeu Samouraï Pizza Cats. Ce thread s'intéresse à un problème de conception que je rencontre pour créer mon inséreur de texte.

Il se trouve que ce petit jeu utilise (du moins pour le dump que j'ai extrait) un dictionnaire de mot. Baha m'a parlé de MTE, j'ai cherché un peu sur la TRAF, il semble que cela corresponde à ça :)
Les MTE correspondent à ce que j'ai compris, à une sorte de mode de compression de données utilisant un dictionnaire de mots. Ces mots sont généralement des chaines souvent utilisées dans le texte comprimé. Lors du dump, un octet indique au parcourir que le prochain octet sera un index dans le dico d'un mot à lire. Et ça marche comme ça.

Je voudrais donc créer un dictionnaire des mots souvent utilisés dans la future traduction de mon dump. Et c'est là que ça se complique.
N'y connaissant quasiment rien en compression de données, je ne connais pas de bonne méthode me permettant de créer un tel dictionnaire, ni même savoir ce qu'est un bon dictionnaire (je dirai que c'est l'ensemble de chaines de taille variable répandues dans le texte avec beaucoup de répétition).
Je pensais donc au début, créer un algo qui parcourait mon texte et plaçait dans une collection la liste des plus petites chaines non encore lues par mon parcoureur de chaine. Mais comme vous devez bien vous en doutez, les résultats différent des conditions initiales, ce qui me fait dire que cet algo n'est pas du tout optimal.

Du coup, je suis un peu perdu. Alors si l'un d'entre vous, dans votre infinie science avait des axes (non routiers) de recherche à me donner pour réussir ce petit tour de force, je lui en serai vraiment reconnaissant :)

Avatar de l’utilisateur
FlashPV
Dieu Suprême du flood
Messages : 1759
Inscription : 15 sept. 2002, 23:44
Localisation : Un coin perdu dans la colline
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par FlashPV »

Moi je suis partisant de la facilité, aussi à ta place j'attendrai la traduction anglaise de Satsu. :-D
Maintenant, si tu veux du travail je peux toujours t'en trouver. :fouet:

Avatar de l’utilisateur
rid
Dieu Suprême du flood
Messages : 2046
Inscription : 04 janv. 2005, 22:17
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par rid »

Oui mais non, avec une solution de facilité c'est pas marrant :)

Et puis, vu le temps que j'ai passé dessus, j'aimerai y arriver à partir de mon code à moi :D, j'en tirerai une certaine fierté qui me poussera ensuite à me pencher sur le petit travail que tu m'avais donné il y a quelques mois :D

** Edit
Et puis même avec une traduction anglaise, je suis eu pour pas dire "baisé" car le même problème se pose à moi ;)

Avatar de l’utilisateur
Pixel
Codeur à l'irc dormant
Messages : 1946
Inscription : 17 avr. 2002, 17:30
Localisation : San Jose
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Pixel »

Cherche "radix tree" sur google.
pixel: A mischievous magical spirit associated with screen displays. The computer industry has frequently borrowed from mythology. Witness the sprites in computer graphics, the demons in artificial intelligence, and the trolls in the marketing department.

Avatar de l’utilisateur
rid
Dieu Suprême du flood
Messages : 2046
Inscription : 04 janv. 2005, 22:17
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par rid »

Donc si je comprends bien ( :tetemur: ), je charge mon texte dans un Radix Tree, ce qui va me créer un joli n'arbre dont la racine aura pour fils (a priori) toutes les lettres de l'alphabet (+ les chiffres et autres caractères de ponctuation). Et de ces lettres, découleront l'ensemble des mots.

Il ne me restera plus qu'à partir de cette nouvelle structure et de récupérer, par exemple, tous les noeuds du second niveau. J'ai bon, ou me fourvoie-je? :tomate:

Avatar de l’utilisateur
Pixel
Codeur à l'irc dormant
Messages : 1946
Inscription : 17 avr. 2002, 17:30
Localisation : San Jose
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Pixel »

Ca peut être une idée, oui.

Après, pour faire ça proprement, il faudrait en fait totalement coupler l'arbre radix avec un tas binaire (binary heap sur google) afin de savoir quels sont les entrées les plus élevées, et ainsi éviter une recherche exhaustive à la fin du parsing.


Par contre, "tous les noeuds de second degré" signifie que tu vas compresser deux caractères maximum.
pixel: A mischievous magical spirit associated with screen displays. The computer industry has frequently borrowed from mythology. Witness the sprites in computer graphics, the demons in artificial intelligence, and the trolls in the marketing department.

Avatar de l’utilisateur
rid
Dieu Suprême du flood
Messages : 2046
Inscription : 04 janv. 2005, 22:17
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par rid »

Ok, c'est un peu vague pour l'instant tout ça, mais je vais essayer de m'accrocher, et fouiller la question :)

Merci Pixel, rien que l'indication 'Radix Tree' m'a bien fait avancer ;)

Avatar de l’utilisateur
Jes
Pom pom pom
Messages : 5822
Inscription : 24 févr. 2002, 14:05
Localisation : Siège social de BessaB
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Jes »

Je crois que tu as posté un algorithme de recherche DTE en Java il n'y pas longtemps. Fondamentalement, calculer le meilleur dictionnaire MTE revient strictement à faire la même chose. Simplement, au lieu de compter seulement les doublets lors du parcours du texte, tu comptes aussi les triplets, les quadruplets, les quintuplets, ... jusqu'au n-uplets. La principale difficulté consiste à trouver la bonne structure de données susceptibles d'avaler le décompte des occurrences de tous les mots possibles (et y en a un paquet: un fichier de 64k par exemple peut contenir jusqu'à près d'un million de mots différents de 2 à 15 lettres...). Le radix tree est effectivement une possibilité, mais une simple hash table pourrait faire l'affaire aussi si le fichier source n'est pas trop gros. Quoiqu'il en soit, attention à la façon dont tu vas scorer les différents mots pour construire ton dictionnaire ensuite. Comparer juste les occurrences de chaque mots pour les départager (comme pour une simple DTE) risque fort de te mener à une solution suboptimale. Par exemple, imaginons qu'à la fin de ton scan, tu aies trouvé 200 occurrences du mot "ab" et 150 occurrences du mot "abc". Choisir abc te fera gagner à peu près 300 octets... Contre 200 seulement pour ab (en supposant que tu encodes les références au dictionnaire sur un seul octet).

Avatar de l’utilisateur
rid
Dieu Suprême du flood
Messages : 2046
Inscription : 04 janv. 2005, 22:17
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par rid »

Effectivement Jes, j'avais un peu vu le rapport entre DTE et MTE, mais je ne voyais pas par où commencer.
L'utilisation d'une structure de données telle que le Radix Tree proposée par Pixel, me semble une bonne pour :
- travailler mon niveau dans ce domaines (les arbres)
- faire ce que je compte faire :)

Ensuite, il est clair qu'il va falloir trouver une stratégie de détection intelligente des meilleurs mots pour mon dictionnaire. Je verrai cela le moment venu, d'abord, voir la faisabilité (étant donné mon niveau de programmation actuel) de mettre en place la structure de données (et surtout de la comprendre car je pourrais très bien chopper une source toute faite sur le web).

Avatar de l’utilisateur
Pixel
Codeur à l'irc dormant
Messages : 1946
Inscription : 17 avr. 2002, 17:30
Localisation : San Jose
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Pixel »

De toute façon, c'est pas "compter" qui est problématique. Au final, c'est un exercice facile. L'arbre radix sera probablement plus intéressant qu'une série de tables de hachages.

Le plus difficile reste l'optimisation de la table à la fin. Déjà avec ce que vous appelez DTE, c'est un casse-tête, et tout ceux qui pensent qu'il suffit de prendre les X occurences maximum se fourrent le doigt dans l'oeil jusqu'au coude. J'avais à l'époque fait un exemple "critique" de texte où prendre juste les couples maximum foutent en l'air totalement la compression. Basé sur ces observations, on était arrivé à trouver un algo pour faire une optimisation propre, et il me semble que c'était Orphis qui l'avait implémenté (pour une fois qu'il fait quelque chose celui-là).
pixel: A mischievous magical spirit associated with screen displays. The computer industry has frequently borrowed from mythology. Witness the sprites in computer graphics, the demons in artificial intelligence, and the trolls in the marketing department.

Avatar de l’utilisateur
Jonath lé là
Il est là !
Messages : 2006
Inscription : 01 mars 2002, 16:53
Localisation : Nancy
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Jonath lé là »

On est pas aussi obligé de prendre un optimum et en prendre une approximation. D'ailleurs j'aimerai bien qu'on définisse un optimum et qu'on prouve qu'un algo le/les trouve (ou une approximation).

Avatar de l’utilisateur
rid
Dieu Suprême du flood
Messages : 2046
Inscription : 04 janv. 2005, 22:17
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par rid »

Ben en gros, ça dépend fortement de comment sont codés les appels au dictionnaire à mon avis.

Par exemple, dans mon cas :
Appel du dictionnaire : <F5> + octet, octet étant un index pour la liste des pointeurs du dictionnaire
Fin du dictionnaire, et retour au script : <F6><F8> bien que le deuxième octet ne semble servir à rien.

Ce qui veut dire que si je veux coder un octet dans mon dictionnaire, il me faut 5 octets en tout!
Ca c'est un premier point.

Après, comme l'ont dit Jes puis Pixel, il faut arriver à trouver le juste milieu entre occurence du mot et longueur de ce mot.
Bon, ce ne sont que des axes de recherche pour l'instant, mais je trouve tout cela assez stimulant :)

Avatar de l’utilisateur
Jes
Pom pom pom
Messages : 5822
Inscription : 24 févr. 2002, 14:05
Localisation : Siège social de BessaB
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Jes »

Pixel a écrit :Le plus difficile reste l'optimisation de la table à la fin. Déjà avec ce que vous appelez DTE, c'est un casse-tête, et tout ceux qui pensent qu'il suffit de prendre les X occurences maximum se fourrent le doigt dans l'oeil jusqu'au coude.
Ca c'est pas un scoop. Mais déjà que c'est emmerdant à gérer juste avec des digrammes, bonne chance avec tous ces mots à longueurs variables.
Jonath lé là a écrit :On est pas aussi obligé de prendre un optimum et en prendre une approximation. D'ailleurs j'aimerai bien qu'on définisse un optimum et qu'on prouve qu'un algo le/les trouve (ou une approximation).
Faut pas non plus que ton approximation soit très éloignée de l'optimum théorique. Du reste, il faudrait effectivement définir un peu plus formellement ce qu'est un optimum pour ce genre de compression avec dictionnaire statique, mais chacun aura bien compris ce que je voulais dire avec mon petit exemple ci-dessus.

Avatar de l’utilisateur
Pixel
Codeur à l'irc dormant
Messages : 1946
Inscription : 17 avr. 2002, 17:30
Localisation : San Jose
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Pixel »

Jonath: c'est pas bien difficile. Quand je faisais ma thèse, j'avais discuté du problème avec des experts en problèmes style "knappsack". Ce n'est pas un problème NP-complet difficile, mais c'est un NP-complet quand même. J'avais fini par prouver l'équivalent entre la recherche d'un optimum d'une DTE, et une certaine forme de recherche de sous-graphe.

En clair, c'est le genre d'algo qui peut tourner longtemps sans jamais trouver d'optimum, vu qu'il peut osciller entre plusieurs positions.

Je vais essayer de retrouver mes notes sur le sujet.
Jes a écrit :Ca c'est pas un scoop. Mais déjà que c'est emmerdant à gérer juste avec des digrammes, bonne chance avec tous ces mots à longueurs variables.
Tout à fait. Mon conseil sur le sujet c'est de prendre simplement la façon "classique" de générer des dictionnaires. A savoir, sur ton exemple, si tu notes "abc", et bien tu ne notes ni "ab" ni "bc" dans tes tables.
pixel: A mischievous magical spirit associated with screen displays. The computer industry has frequently borrowed from mythology. Witness the sprites in computer graphics, the demons in artificial intelligence, and the trolls in the marketing department.

Avatar de l’utilisateur
Jonath lé là
Il est là !
Messages : 2006
Inscription : 01 mars 2002, 16:53
Localisation : Nancy
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Jonath lé là »

Oui ce problème sent bon la NP-complétude, d'où l'intèrêt de l'approximation et de bien formaliser le problème pour trouver une bonne méthode d'approximation. Mais si t'as déjà réfléchi dessus et que t'as des notes là-dessus, faut faire tourner :)
Promouvoir et soutenir le logiciel libre

Avatar de l’utilisateur
rid
Dieu Suprême du flood
Messages : 2046
Inscription : 04 janv. 2005, 22:17
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par rid »

On dit "S'il te plaît" :D

Avatar de l’utilisateur
Pixel
Codeur à l'irc dormant
Messages : 1946
Inscription : 17 avr. 2002, 17:30
Localisation : San Jose
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Pixel »

Je n'ai pas retrouvé mon exemple typique, je me souviens que j'avais un truc qui était bien descriptif du problème. Mais j'ai trouvé un deuxième exemple assez amusant en soit.

Considérons que l'on ne peut faire qu'un dictionnaire comportant que deux entrées. Considérons la phrase à compresser suivante:

ABBABBA - 7 symboles.

Un algorithme classique va procéder en lisant tous les digrammes et en calculant le dictionnaire suivant, dans cet ordre:

AB: 2
BB: 2
BA: 2

Tout étant exequo, le tri ne va rien changer. L'algo classique prendrait donc les deux premières entrées dans l'ordre d'apparition, ce qui consiste à faire [AB][BB] en tant que dictionnaire. Si l'on compresse, cela donne:

[AB]B[AB]BA - 5 symboles.

Vous remarquerez que [BB] n'est jamais utilisé; c'est un joli cas dégénéré.


Si l'on construit ce dictionnaire DTE sous la forme de graphe, cela donne la trace d'algo suivant:

On fait le noeud [AB] et on lui donne le poids 1.
On fait le noeud [BB] et on lui donne le poids 1. On fait un lien entre [AB] et [BB], et on donne un poids 1 à l'arète.
On fait le noeud [BA] et on lui donne le poids 1. On fait un lien entre [BB] et [BA], et on donne un poids 1 à l'arète.
On incrémente le poids de [AB]. On fait un lien entre [BA] et [BA] et on donne un poids 1 à l'arète.
On incrémente le poids de [BB]. On incrémente l'arète entre [AB] et [BB].
On incrémente le poids de [BA]. On incrémente l'arète entre [BB] et [BA].

Ce qui donne le graphe final suivant:
dte-example.png
dte-example.png (8.42 Kio) Consulté 8506 fois
Une fois ce graphe terminé, on établit le dictionnaire de base. On commence par colorier des noeuds du graphe suivant l'algo de base, ce qui fait que l'on colorie les noeuds [AB] et [BB]. On a le droit de colorier 2 noeuds maximum, vu que c'est la taille de notre dictionnaire de sortie. Ce faisant, on calcule le poids du sous-graphe, à savoir Sum(noeuds coloriés) - Sum(arètes entre les noeuds coloriés) = 2+2-2 = 2. Une fois ce coloriage terminé, on a notre dictionnaire "idiot". On commence l'optimisation, qui consiste en la manière suivante:

Considérons le noeud colorié [AB], et la liste des emplacements où l'on peut faire glisser sa couleur. On ne peut la faire glisser que vers [BA]. Ce glissement produirait un changement du poids du sous-graphe équivalent au poids du noeud destination - poids du noeud d'origine - somme des arètes (qui vont vers un noeud colorié) du noeud destination + somme des arètes (qui vont vers un noeud colorié) du noeud d'origine = 2 - 2 - 2 + 2 = 0. Gain nul ou négatif, on n'effectue pas le glissage.

Considérons le noeud colorié [BB]. On ne peut faire glisser sa couleur que vers [BA]. Ce glissement produirait un changement du poids du sous-graphe équivalent à 2-2+2-1=1. Gain positif, on effectue le glissage.

A partir de là, l'algo peut continuer, mais il a trouvé l'optimum en ayant colorié [AB] et [BA]. Il peut se rendre compte qu'il a trouvé l'optimum car tous les glissements de couleur donneraient un changement négatif ou nul du poids du sous-graphe.

Le poids du sous-graphe est la compression effective. En effet, si l'on compresse avec ce nouveau dictionnaire, on obtient:

[AB][BA]B[BA] - 4 symboles.
pixel: A mischievous magical spirit associated with screen displays. The computer industry has frequently borrowed from mythology. Witness the sprites in computer graphics, the demons in artificial intelligence, and the trolls in the marketing department.

Avatar de l’utilisateur
Pixel
Codeur à l'irc dormant
Messages : 1946
Inscription : 17 avr. 2002, 17:30
Localisation : San Jose
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Pixel »

Alternativement, vous remarquerez que ma suggestion précédente marche assez bien dans ce cas-ci, à savoir "Si on voit ABC, on marque [AB] et on ne marque pas [BC]" :P Mais c'est un coup de chance :)
pixel: A mischievous magical spirit associated with screen displays. The computer industry has frequently borrowed from mythology. Witness the sprites in computer graphics, the demons in artificial intelligence, and the trolls in the marketing department.

Avatar de l’utilisateur
Ti Dragon
Est devenu grand
Messages : 12441
Inscription : 25 févr. 2002, 18:25
Localisation : Dans mon lit c'est mieux
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Ti Dragon »

J'aime quand c'est expliqué de cette manière :)

Après, dans des cas pratiques de ROMhacking pour débutants (c'est mon cas, bien entendu), on a parfois recours à de la bidouille lors de la construction des tables puisque les mots sont pointés. Je donne en exemple Gargoyle's Quest II (après, je dis pas que c'était mega optimisé, vu mon niveau ; j'avais quand même compté "à la main", l'optimisation qui résulterait de la suppression de "ROI", par exemple, dans "PALAIS DU ROI" qui était également beaucoup utilisé ; j'ai fait des tests avec et sans et, finalement, mon taux de compression était meilleur avec cette astuce) :

La table :

Code : Tout sélectionner

F347=PALAIS DU ROI
F348=ROI
F34E=PLUS HAUT QU'AVANT
F34F=AVANT
F511=HIPPOGRIFFE
F379=GRIFFE
L'insertion dans le dictionnaire MTE :

Code : Tout sélectionner

   D30D
PALAIS DU 
    D30E
ROI<FF>
    D314
PLUS HAUT QU'
    D315
AVANT<FF>
    D33F
HIPPOGRIFFE<FF>
On a tous compris que le $FF est là pour indiquer la fin d'un mot. Ne pas en mettre permet de continuer sa lecture. Bon, bien sûr, en DTE, ça perd un peu plus de son intérêt, je suppose.
"Heureusement qu'il n'avait que deux mots à nous dire... je plains son auditoire lorsqu'il doit faire un long discours"
(c) Le gardien du square
--
La scène de la traduction francophone : http://traf.romhack.org/

Avatar de l’utilisateur
rid
Dieu Suprême du flood
Messages : 2046
Inscription : 04 janv. 2005, 22:17
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par rid »

Pixel, je ne comprends pas bien cette histoire de glissement de couleur : pourquoi au début ne peut-on pas tester le glissement de [AB] vers [BA] ?
Le graphe est-il en fait orienté?

Avatar de l’utilisateur
Jes
Pom pom pom
Messages : 5822
Inscription : 24 févr. 2002, 14:05
Localisation : Siège social de BessaB
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Jes »

Pixel a écrit :Une fois ce graphe terminé, on établit le dictionnaire de base. On commence par colorier des noeuds du graphe suivant l'algo de base, ce qui fait que l'on colorie les noeuds [AB] et [BB]. On a le droit de colorier 2 noeuds maximum, vu que c'est la taille de notre dictionnaire de sortie. Ce faisant, on calcule le poids du sous-graphe, à savoir Sum(noeuds coloriés) - Sum(arètes entre les noeuds coloriés) = 2+2-2 = 2. Une fois ce coloriage terminé, on a notre dictionnaire "idiot". On commence l'optimisation, qui consiste en la manière suivante:

Considérons le noeud colorié [AB], et la liste des emplacements où l'on peut faire glisser sa couleur. On ne peut la faire glisser que vers [BA]. Ce glissement produirait un changement du poids du sous-graphe équivalent au poids du noeud destination - poids du noeud d'origine - somme des arètes (qui vont vers un noeud colorié) du noeud destination + somme des arètes (qui vont vers un noeud colorié) du noeud d'origine = 2 - 2 - 2 + 2 = 0. Gain nul ou négatif, on n'effectue pas le glissage.

Considérons le noeud colorié [BB]. On ne peut faire glisser sa couleur que vers [BA]. Ce glissement produirait un changement du poids du sous-graphe équivalent à 2-2+2-1=1. Gain positif, on effectue le glissage.

A partir de là, l'algo peut continuer, mais il a trouvé l'optimum en ayant colorié [AB] et [BA]. Il peut se rendre compte qu'il a trouvé l'optimum car tous les glissements de couleur donneraient un changement négatif ou nul du poids du sous-graphe.
Pourquoi tu compares la recherche du meilleur sous-graphe au coloriage d'un graphe? Le modèle et ses contraintes n'ont quand même rien à voir. D'un côté, on a un graphe avec noeuds et liens pondérés, le but étant de rechercher le sous-graphe de poids maximum. De l'autre, on a un graphe tout bête dont on cherche à colorier les noeuds, de telle sorte que deux noeuds adjacents ne soient jamais de la même couleur. Je vois pas trop comment tu peux réduire le premier problème au second. Après, l'algorithme que tu décris, c'est ni plus ni moins que de la recherche locale (ou plus exactement, du hill climbing): tu pars d'une solution plus ou moins aléatoire, que tu essaies ensuite d'améliorer (selon une fonction de scorage qui ici correspond au poids du sous-graphe) d'itération en itération, par changements progressifs. Là d'accord, on peut éventuellement faire un parallèle avec la coloration d'un graphe, problème qui peut aussi se résoudre par hill climbing. Cela dit, le soucis avec cette méthode, c'est que la recherche locale peut très bien mener à un optimum local, et pire, elle peut même boucler. Pour prouver que ton algorithme tombe effectivement systématiquement sur l'optimum global, il faudrait prouver que pour ce problème, tout optimum local est forcément un optimum global. Je ne sais pas si tu l'as fait, mais ça mérite réflexions en tout cas.
Ridculle a écrit :Pixel, je ne comprends pas bien cette histoire de glissement de couleur : pourquoi au début ne peut-on pas tester le glissement de [AB] vers [BA] ?
En réalité, ce glissement est bel et bien testé. Par contre, il n'est pas réalisé parce que ça n'augmente pas le score de la solution courante (le poids du sous-graphe courant, si tu préfères).
Ridculle a écrit :Le graphe est-il en fait orienté?
Mmmh, est-ce que tu as bien compris ce que modélisait le graphe? Chaque lien représente en fait des "conflits" entre les digrammes. Par exemple, le lien de poids 1 entre les digrammes AB et BA signifie qu'une occurrence de AB chevauche une occurrence de BA. Donc, si on faisait le remplacement de toutes les occurrences [AB] par une entrée dans le dictionnaire, on tuerait par la même occasion une occurrence de BA. Si je reprends l'exemple de Pixel:

Code : Tout sélectionner

ABBABBA
J'ai deux occurrences de AB et deux de BA de départ. Effectuons le remplacement de AB:

Code : Tout sélectionner

xBxBA
Tu vois, le remplacement de AB a bien provoqué la perte d'une occurrence de BA, comme l'indique le graphe.

Si tu as bien compris ça, tu devrais pouvoir répondre facilement à ta propre question :D

Avatar de l’utilisateur
Pixel
Codeur à l'irc dormant
Messages : 1946
Inscription : 17 avr. 2002, 17:30
Localisation : San Jose
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Pixel »

Ti: de toute façon, une compression "MTE" comme vous dites fonctionne sur un tout autre principe. Il s'agit de créer un dictionnaire d'occurences comme justement vont le faire des algorithmes comme deflate, lzo ou ucl. La "force" de la compression est déterminée par la taille en mémoire du dictionnaire. L'idée que je présente n'est pas adapté

Jes a écrit :Pourquoi tu compares la recherche du meilleur sous-graphe au coloriage d'un graphe? Le modèle et ses contraintes n'ont quand même rien à voir. D'un côté, on a un graphe avec noeuds et liens pondérés, le but étant de rechercher le sous-graphe de poids maximum. De l'autre, on a un graphe tout bête dont on cherche à colorier les noeuds, de telle sorte que deux noeuds adjacents ne soient jamais de la même couleur. Je vois pas trop comment tu peux réduire le premier problème au second. Après, l'algorithme que tu décris, c'est ni plus ni moins que de la recherche locale (ou plus exactement, du hill climbing): tu pars d'une solution plus ou moins aléatoire, que tu essaies ensuite d'améliorer (selon une fonction de scorage qui ici correspond au poids du sous-graphe) d'itération en itération, par changements progressifs. Là d'accord, on peut éventuellement faire un parallèle avec la coloration d'un graphe, problème qui peut aussi se résoudre par hill climbing. Cela dit, le soucis avec cette méthode, c'est que la recherche locale peut très bien mener à un optimum local, et pire, elle peut même boucler. Pour prouver que ton algorithme tombe effectivement systématiquement sur l'optimum global, il faudrait prouver que pour ce problème, tout optimum local est forcément un optimum global. Je ne sais pas si tu l'as fait, mais ça mérite réflexions en tout cas.
Alors. Tentons de rester amis, ou du moins, de faire en sorte de ne pas commencer à se taper dessus physiquement lorsque l'on se croise :P Contrairement aux apparances, je n'ai jamais réussi à piffrer la théorie des graphes (enfin, en général, c'est plutôt les gens qui font de la théorie des graphes), et j'utiliserai toujours des termes à tort et à travers. En gros, "je me comprends", mais j'admets parfaitement que le vocabulaire que j'utilise n'est absolument pas correct; j'aurais probablement dû le dire avant. Après, en général, les gens qui me saoulaient la tête avec leur nerdisme pendant que j'étais à l'université me donnaient envie de leur nouer les jambes derrière la nuque en leur hurlant "TA GUEUUUUUUUUUUUUUUUUUUUUUUUUUUUUULE" dans l'oreille. Bref, à bon entendeur... :P

Dans tous les cas, j'avais discuté de ce problème avec un de mes profs à l'université, qui m'avait sorti un truc du style "ach ach oui z'est indéressant ze broplème, mais z'est vazile en vait, regarde" et il est parti sur 1h30 de gribouillis sur le tableau où j'ai décroché au bout des 38 premières minutes (oui, il est allemand). A la base, mon but quand j'avais fait l'équivalence entre "le problème d'optimiser une DTE" et "un problème de graphe quelconque que je ne sais pas ce que c'est", c'était surtout pouvoir exposer le problème à mes profs histoire qu'ils me sortent la définition ou l'outil mathématique pour me permettre de prouver aux gens d'ici et autres Meradrin que trouver l'optimum DTE n'était pas en O(n) contrairement à ce qu'ils disaient. Le reste, je m'en fichais totalement :P

Mais au final, la traduction de ce problème sous cette forme permet en effet d'y appliquer des solutions en théorie des graphes existantes, et de trouver une solution appréciable concrète. Après, les mots comme "hill climbing" me rappellent en effet des choses (où l'usage d'ailleurs d'une batte de baseball n'est pas à exclure). Si tu as envie de faire quelque chose pour ça, je t'en prie, n'hésite pas à creuser. Oui, il faut une heuristique pour éviter que ça ne boucle (voire un deuxième coloriage). Oui, la preuve de l'optimum est pas forcément évidente, et je suis certain d'avoir un cas où il y aurait 3 optimums possibles, et où l'algo oscillerait en rond sur ces 3 solutions. Oui, le mot "coloriage de graphe" n'est pas adapté, je me souviens d'ailleurs que j'avais travaillé pendant ma math-sup à un algo de coloriage en 5 et en 4 couleurs, ça m'a laissé quelques cicatrices que je vais tenter d'oublier encore une fois, merci bien. Amuse-toi à y donner une autre définition si tu as envie, je m'en branle. Mon rôle ici se limite à reformuler le problème sous une autre forme, plus accessible par les matheux nerdiens qui font des graphes toute la journée et qui sautent partout quand ils arrivent à gagner 0.3% de temps sur leur algo quand ils arrivent à exclure un cas avec un test supplémentaire dans leurs boucles. Je sais aussi qu'Orphis a fait une implémentation basée sur ce modèle je crois bien. Mais bon, voilà, moi je ne vais pas plus loin que ça :P

Ah, et il ne faut pas oublier que l'on peut avoir des bouts de graphe disjoints dans ce modèle.
pixel: A mischievous magical spirit associated with screen displays. The computer industry has frequently borrowed from mythology. Witness the sprites in computer graphics, the demons in artificial intelligence, and the trolls in the marketing department.

Avatar de l’utilisateur
Jes
Pom pom pom
Messages : 5822
Inscription : 24 févr. 2002, 14:05
Localisation : Siège social de BessaB
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Jes »

Pixel a écrit :Alors. Tentons de rester amis, ou du moins, de faire en sorte de ne pas commencer à se taper dessus physiquement lorsque l'on se croise :P Contrairement aux apparances, je n'ai jamais réussi à piffrer la théorie des graphes (enfin, en général, c'est plutôt les gens qui font de la théorie des graphes), et j'utiliserai toujours des termes à tort et à travers. En gros, "je me comprends", mais j'admets parfaitement que le vocabulaire que j'utilise n'est absolument pas correct; j'aurais probablement dû le dire avant. Après, en général, les gens qui me saoulaient la tête avec leur nerdisme pendant que j'étais à l'université me donnaient envie de leur nouer les jambes derrière la nuque en leur hurlant "TA GUEUUUUUUUUUUUUUUUUUUUUUUUUUUUUULE" dans l'oreille. Bref, à bon entendeur... :P

Dans tous les cas, j'avais discuté de ce problème avec un de mes profs à l'université, qui m'avait sorti un truc du style "ach ach oui z'est indéressant ze broplème, mais z'est vazile en vait, regarde" et il est parti sur 1h30 de gribouillis sur le tableau où j'ai décroché au bout des 38 premières minutes (oui, il est allemand). A la base, mon but quand j'avais fait l'équivalence entre "le problème d'optimiser une DTE" et "un problème de graphe quelconque que je ne sais pas ce que c'est", c'était surtout pouvoir exposer le problème à mes profs histoire qu'ils me sortent la définition ou l'outil mathématique pour me permettre de prouver aux gens d'ici et autres Meradrin que trouver l'optimum DTE n'était pas en O(n) contrairement à ce qu'ils disaient. Le reste, je m'en fichais totalement :P

Mais au final, la traduction de ce problème sous cette forme permet en effet d'y appliquer des solutions en théorie des graphes existantes, et de trouver une solution appréciable concrète. Après, les mots comme "hill climbing" me rappellent en effet des choses (où l'usage d'ailleurs d'une batte de baseball n'est pas à exclure). Si tu as envie de faire quelque chose pour ça, je t'en prie, n'hésite pas à creuser. Oui, il faut une heuristique pour éviter que ça ne boucle (voire un deuxième coloriage). Oui, la preuve de l'optimum est pas forcément évidente, et je suis certain d'avoir un cas où il y aurait 3 optimums possibles, et où l'algo oscillerait en rond sur ces 3 solutions. Oui, le mot "coloriage de graphe" n'est pas adapté, je me souviens d'ailleurs que j'avais travaillé pendant ma math-sup à un algo de coloriage en 5 et en 4 couleurs, ça m'a laissé quelques cicatrices que je vais tenter d'oublier encore une fois, merci bien. Amuse-toi à y donner une autre définition si tu as envie, je m'en branle. Mon rôle ici se limite à reformuler le problème sous une autre forme, plus accessible par les matheux nerdiens qui font des graphes toute la journée et qui sautent partout quand ils arrivent à gagner 0.3% de temps sur leur algo quand ils arrivent à exclure un cas avec un test supplémentaire dans leurs boucles. Je sais aussi qu'Orphis a fait une implémentation basée sur ce modèle je crois bien. Mais bon, voilà, moi je ne vais pas plus loin que ça :P
Tu es le premier à reprendre les gens sur la manière dont ils expriment leurs idées, je crois. Je ne vois nulle trace de "nerdisme" dans mon post, je tentais juste de comprendre et reformuler tes idées en ajoutant ma petite pierre à l'édifice, histoire d'enrichir le débat. Démarche scientifique. Visiblement tu as choisi de prendre ça comme une vulgaire tentative d'enfermement sur la sémantique, et c'est bien dommage parce que du même coup, moi ça me donne plus envie de discuter.
Pixel a écrit :Ah, et il ne faut pas oublier que l'on peut avoir des bouts de graphe disjoints dans ce modèle.
C'est parfaitement impossible par construction, mais bon t'occupe, laisse ça aux "nerds".

Avatar de l’utilisateur
Jonath lé là
Il est là !
Messages : 2006
Inscription : 01 mars 2002, 16:53
Localisation : Nancy
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Jonath lé là »

Ce n'est pas grave de formuler incorrectement le problème, tant qu'au fur et à mesure cette formulation est améliorée. Je suis pas un expert en théorie des graphes donc je connais pas d'algorithmes spécifiques, mais je vais essayer d'y réfléchir ce soir.
Promouvoir et soutenir le logiciel libre

Avatar de l’utilisateur
Pixel
Codeur à l'irc dormant
Messages : 1946
Inscription : 17 avr. 2002, 17:30
Localisation : San Jose
Contact :
Re: [Compression] Création d'un dictionnaire des récurrences

Message non lu par Pixel »

Pixel a écrit :j'admets parfaitement que le vocabulaire que j'utilise n'est absolument pas correct; j'aurais probablement dû le dire avant.
Pixel a écrit :Après, en général, les gens qui me saoulaient la tête avec leur nerdisme pendant que j'étais à l'université me donnaient envie de leur nouer les jambes derrière la nuque en leur hurlant "TA GUEUUUUUUUUUUUUUUUUUUUUUUUUUUUUULE" dans l'oreille. Bref, à bon entendeur... :P
Tant que tu ne viens pas à me seriner tout content parce qu'il faut absolument que tu me montres le raccourci que tu as trouvé pour une preuve que Pi est irrationnel, ou que tu n'essayes pas de m'expliquer la magnifique subtilité dans le rajout d'un test supplémentaire dans le code d'une boucle de recherche de minima dans l'algo pouetpouet écrit par Jean Dutreux dans son papier numéro 15683, tu ne rentres pas dans cette catégorie.

Ces gens sont en général tellement en dehors des réalités à souler leur monde en disant des conneries du style "tu vas voir, je vais réécrire le noyau Linux en CAML et d'un coup tout sera plus rapide, plus stable et plus sécurisé!" que c'en est pathétique. Quand je travaillais sur ma thèse, là où certains étaient tout content car ils gagnaient un temps exponentiel par un test supplémentaire ce qui faisait un gain total sur l'exécution maximum des entrées que l'on avaient de 0.2%, j'arrivais à des speed-ups linéaires de 80% sur les mêmes entrées en changeant simplement les méthodes d'accès et en virant des monstruosités de langages grosses comme des maisons.

Je pense pas que tu sois totalement en dehors des réalités, non.
pixel: A mischievous magical spirit associated with screen displays. The computer industry has frequently borrowed from mythology. Witness the sprites in computer graphics, the demons in artificial intelligence, and the trolls in the marketing department.


Répondre