Discussion :

[GoustiFruit]

Bonjour,

Je voudrais savoir s'il existe des algorithmes (efficaces ) permettant de résoudre ce type de problème:

J'ai une liste de "séquences" simples (on pourrait faire l'analogie avec des séquences d'ADN par ex.), que je souhaite factoriser de façon à obtenir une nouvelle liste la plus courte possible. La factorisation consiste à regrouper deux ou plusieurs séquences qui ne diffèrent que par une "lettre", en une seule séquence "condensée".

Soit par exemple cette liste de séquences de départ:
0 AAAA
1 BAAC
2 ABAA
3 BCAA
4 ACAB
5 BAAA
6 ABAB
7 AAAB
8 ACAC

Si on compare la première séquence de la liste (indice 0: AAAA) aux suivantes, on voit qu'elle n'a qu'une différence avec la séquence 5 (BAAA) par ex., ce qui permet de les regrouper/factoriser en une nouvelle séquence qui serait [AB]AAA.
De même la séquence 2 (ABAA) et la séquence 6 (ABAB) ne diffèrent que d'une lettre et peuvent être regroupées en une séquence ABA[AB].
Puis la séquence 4 (ACAB) et la séquence 7 (AAAB) peuvent être regroupées en A[AC]AB.
Ce qui donnerait une solution de 6 éléments:
0 [AB]AAA
1 BAAC
2 ABA[AB]
3 BCAA
4 A[AC]AB
5 ABAB

Mais de façon optimale on pourrait factoriser la même liste de départ en une solution de 4 éléments seulement:
0 A[AB]A[AB]
1 BAAC
2 B[AC]AA
3 ACA[BC]

(Il est facile de retrouver la liste des séquences de départ en décomposant chaque séquence: A[AB]A[AB] donne les séquences AAAA/AAAB/ABAA/ABAB)

Bref, si je fais simplement une boucle pour comparer les grilles une par une, et de la première lettre vers la dernière, j'obtiens la première solution, qui est loin d'être la solution optimale; je cherche donc un algorithme qui pourrait améliorer mes résultats.

Je travaille en Delphi mais un pseudo-algorithme me suffit, si vous avez des idées ou des liens/références...

[guillemouze]

je sais pas si ca peut t'aider, mais tu peux peut etre utiliser un arbre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
       A
 A------B----C
 A      A    A
A-B    A-B   B
0 7    2 6   4   <--- indice de la ligne correspondant au chemin de l'arbre

[GoustiFruit]

Oui c'est un petit peu comme ça que je fais pour l'instant, je parcours l'ensemble des éléments "de haut en bas" pour les comparer à leurs voisins mais c'est loin de donner des solutions optimales, ça permet tout juste d'avoir une solution rapide: c'est ce qui me donne la première solution de mon exemple, comparé à la deuxième (optimale ?)... Je ne cherche pas non plus *la* solution parfaite, mais quelque chose de plus efficace quand même.
(Je ne sais pas si ce genre de problème porte un nom: si il y a des documents là-dessus, je prends aussi)

[Mac LAK]

Déjà, tu peux voir du côté de la distance de Levenshtein pour avoir des chiffres "objectifs". Ceci étant dit, c'est assez long à faire... Mais bon, si tu as peu de chaînes à factoriser, c'est pas l'enfer, surtout que tu n'autorise que la substitution dans ton cas.

Ceci étant dit, j'ai un peu peur que ta factorisation "ultime" tombe sur un truc du genre "[AB][ABC][AB][ABC]" par rapport à ton exemple...
J'ai l'impression que tu cherches à retrouver l'expression régulière correspondante à un ensemble de données, en lisant l'exposé de ton problème.

Ceci étant dit, toujours en fonction du nombre de données à traiter, partir sur la solution de construire une regexp puis de l'affiner en fonction des résultats incohérents pourrait être une solution... Mais je crains que ça ne soit très long et/ou prohibitif en terme d'occupation mémoire, car cela reviendrait à expander une regexp en toutes ses possibilités, et à éliminer une par une les possibilités générées qui n'existent pas dans la liste originale.

[pseudocode]

Ceci étant dit, j'ai un peu peur que ta factorisation "ultime" tombe sur un truc du genre "[AB][ABC][AB][ABC]" par rapport à ton exemple...
J'ai l'impression que tu cherches à retrouver l'expression régulière correspondante à un ensemble de données, en lisant l'exposé de ton problème.

Effectivement, ca ressemble beaucoup a de la minimisation d'automate à états finis.

[Mac LAK]

Effectivement, ca ressemble beaucoup a de la minimisation d'automate à états finis.

Merci pour l'expression exacte, peut-être que ça pourra aider l'OP un peu plus au passage.

Voici un petit lien "au cas où"...

[GoustiFruit]

Déjà, tu peux voir du côté de la distance de Levenshtein pour avoir des chiffres "objectifs". Ceci étant dit, c'est assez long à faire... Mais bon, si tu as peu de chaînes à factoriser, c'est pas l'enfer, surtout que tu n'autorise que la substitution dans ton cas.

Merci pour la lecture. Ça serait plutôt distance de Hamming dans mon cas, les "mots" ont tous la même longueur et il n'y a que des permutations de lettres.

Ceci étant dit, j'ai un peu peur que ta factorisation "ultime" tombe sur un truc du genre "[AB][ABC][AB][ABC]" par rapport à ton exemple...
J'ai l'impression que tu cherches à retrouver l'expression régulière correspondante à un ensemble de données, en lisant l'exposé de ton problème.

Il y a un peu de ça, mais alors ça serait une expression régulière *stricte* (ou plutôt une addition d'expressions régulières) qui ne doit donner en sortie que la liste de départ, et pas un "mot" de plus qui n'en fasse pas partie.

Ceci étant dit, toujours en fonction du nombre de données à traiter, partir sur la solution de construire une regexp puis de l'affiner en fonction des résultats incohérents pourrait être une solution... Mais je crains que ça ne soit très long et/ou prohibitif en terme d'occupation mémoire, car cela reviendrait à expander une regexp en toutes ses possibilités, et à éliminer une par une les possibilités générées qui n'existent pas dans la liste originale.

Et quand bien même... parmi toutes les sous-regexps générées à partir de l'expression régulière (qui serait [AB][ABC][AB][ABC] ici, pour définir l'univers des lettres possibles à chaque rang), il y a toujours plusieurs possibilités d'arrangements entre elles pour finir par couvrir la liste de départ. Et je cherche, sinon la solution optimale, du moins quelque chose qui s'en approche un peu ! (voir "solutions" 1 et 2: on peut considérer qu'il s'agit d'une somme d'expression régulières, elles sont elles-mêmes de sousensembles de l'expression régulière globale [AB][ABC][AB][ABC] mais une solution est meilleure que l'autre)...

[pseudocode]

Et je cherche, sinon la solution optimale, du moins quelque chose qui s'en approche un peu !

Si c'est ça, tu peux factoriser itérativement toutes les chaines qui n'ont qu'un caractère de différence.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
départ (trié):
AAAA, AAAB, ABAA, ABAB, ACAB, ACAC, BAAA, BAAC, BCAA
 
1ere factorisation possible:
AAAA, AAAB -> AAA[AB]
résultat:
AAA[AB], ABAA, ABAB, ACAB, ACAC, BAAA, BAAC, BCAA
 
1ere factorisation possible:
ABAA, ABAB -> ABA[AB]
résultat:
AAA[AB], ABA[AB], ACAB, ACAC, BAAA, BAAC, BCAA
 
1ere factorisation possible:
AAA[AB], ABA[AB] -> A[AB]A[AB]
résultat:
A[AB]A[AB], ACAB, ACAC, BAAA, BAAC, BCAA
 
1ere factorisation possible:
ACAB, ACAC -> ACA[BC]
résultat:
A[AB]A[AB], ACA[BC], BAAA, BAAC, BCAA
 
1ere factorisation possible:
BAAA, BAAC -> BAA[AC]
résultat:
A[AB]A[AB], ACA[BC], BAA[AC], BCAA
 
plus de factorisation possible -> fini

[GoustiFruit]

A part pour le tri, c'est ce que je fais pour l'instant: est-ce que le tri est sensé apporter quelque chose ? Parce que c'est vrai que sur cet exemple on arrive à une meilleure solution que sans le tri, mais est-ce que c'est le hasard ? Si je fais la même itération avec un tri inverse j'obtiens une solution différente mais de même longueur: B[AC]AA, BAAC, ACA[BC], A[AB]A[AB]...

[10_GOTO_10]

Pour trouver la solution optimale (mais pas la plus rapide, c'est vrai), moi je partirais plutôt des chaînes finales.

Je m'explique: je commence à tester chaîne [ABC][ABC][ABC][ABC], ce qui implique la présence des 3 * 3 * 3 * 3 sous-chaînes dans la liste. Si elles existent, je sais qu'il ne peut pas y avoir de façon plus concises de les représenter. Je les élimine donc de la liste et je rajoute [ABC][ABC][ABC][ABC] dans ma seconde liste. Si une seule des 81 chaînes n'est pas dans la liste 1, j'essaie ensuite les sous-ensembles [ABC][ABC][ABC][AB], [ABC][ABC][ABC][AC], [ABC][ABC][ABC][BC], et ansi de suite (dans l'ordre décroissant du nombre de combinaisons possible), jusqu'à épuisement des chaînes de la liste 1.

En me relisant, je ne suis pas sûr qu'on trouve toujours LA solution optimale, mais je ne trouve pas de contre-exemple.

[pseudocode]

A part pour le tri, c'est ce que je fais pour l'instant: est-ce que le tri est sensé apporter quelque chose ? Parce que c'est vrai que sur cet exemple on arrive à une meilleure solution que sans le tri, mais est-ce que c'est le hasard ? Si je fais la même itération avec un tri inverse j'obtiens une solution différente mais de même longueur: B[AC]AA, BAAC, ACA[BC], A[AB]A[AB]...

Non, ce n'est pas vraiment du hasard. Pour bien factoriser, il faut faire des groupes de mots "proches" les uns des autres. Dans ce cas, il y a moins de chance qu'une factorisation locale "inattendue" gène la factorisation globale d'un groupe.

Le tri alphabétique est une heuristique très simpliste pour faire ce regroupement. Mais visiblement, elle suffit pour ton exemple. Pour des cas plus complexes, il faudra tester d'autres heuristiques de regroupement (k-mean, mean shift, cluster, ...)

[Mac LAK]

Pour trouver la solution optimale (mais pas la plus rapide, c'est vrai), moi je partirais plutôt des chaînes finales.

C'est ce que je pense aussi, je me cite : "cela reviendrait à expander une regexp en toutes ses possibilités, et à éliminer une par une les possibilités générées qui n'existent pas dans la liste originale."

Pour des chaînes de 4 caractères sur 3 lettres, ça va, c'est pas énorme. Par contre, en fonction de la taille de l'alphabet utilisé et de la longueur des chaînes, ça risque de devenir folklorique côté occupation mémoire.

Le point le plus difficile du problème reviendra à décider à quel moment il est nécessaire de rajouter une regexp à la liste, c'est à dire d'augmenter de 1 le nombre de chaînes factorisées (qui commence à 1 avec la regexp "complète").

[GoustiFruit]

Non, ce n'est pas vraiment du hasard. Pour bien factoriser, il faut faire des groupes de mots "proches" les uns des autres. Dans ce cas, il y a moins de chance qu'une factorisation locale "inattendue" gène la factorisation globale d'un groupe.

Mais même après avoir trié, on peut se retrouver avec une liste genre
AAAA
(...) // nombreux termes
(...)
(...)
ACAA
CAAA
CAAB
CABA
CBAA
où AAAA factoriserait avec des éléments éloignés (ACAA, CAAA) empêchant la factorisation entre CAAA, CAAB, CABA et CBAA qui pourrait s'avérer meilleure.

[GoustiFruit]

C'est ce que je pense aussi, je me cite : "cela reviendrait à expander une regexp en toutes ses possibilités, et à éliminer une par une les possibilités générées qui n'existent pas dans la liste originale."

Pas certain que ça mène à la meilleure solution car après avoir éliminé les regexps les plus importants, je vais me retrouver avec des regexps moins complexes mais de "même niveau" du genre [AB]A[AB][AC] vs [AB]A[BC][BC] qui chacun de leur côté pourraient être acceptés sur un cas précis (c'est-à-dire que l'ensemble des éléments qu'ils génèrent seraient effectivement présents dans la liste), mais qui pourraient induire des sous-regexps moins efficaces. Comment savoir lequel choisir à ce moment là ? Faire la simulation sur chaque regexp de même niveau ? Puis sur chaque regexp de niveau inférieur, jusqu'à ce qu'une solution soit trouvée, et comparer toutes les solutions de tous les ensembles de regexps, etc., etc., etc.

Pour des chaînes de 4 caractères sur 3 lettres, ça va, c'est pas énorme. Par contre, en fonction de la taille de l'alphabet utilisé et de la longueur des chaînes, ça risque de devenir folklorique côté occupation mémoire.

Si je vous dit que les mots peuvent faire jusqu'à 16 caractères et que l'alphabet est de 3 lettres (ça fait dans les 45 millions de séquences possibles au maximum), ça vous fait peur ou ça vous rassure ? :-D
En fait j'ai déjà une première optimisation qui me permet de travailler sur des entiers (32 bits) au lieu de chaînes de caractères, vu que l'alphabet de 3 lettres peut être représenté par 2 bits (00, 01, et 10). Donc occupation mémoire maxi de 45 Mo pour la liste de séquence la plus longue possible.

[Mac LAK]

Pas certain que ça mène à la meilleure solution car après avoir éliminé les regexps les plus importants, je vais me retrouver avec des regexps moins complexes mais de "même niveau" du genre [AB]A[AB][AC] vs [AB]A[BC][BC] qui chacun de leur côté pourraient être acceptés sur un cas précis (c'est-à-dire que l'ensemble des éléments qu'ils génèrent seraient effectivement présents dans la liste), mais qui pourraient induire des sous-regexps moins efficaces. Comment savoir lequel choisir à ce moment là ? Faire la simulation sur chaque regexp de même niveau ? Puis sur chaque regexp de niveau inférieur, jusqu'à ce qu'une solution soit trouvée, et comparer toutes les solutions de tous les ensembles de regexps, etc., etc., etc.

C'est ce que je soulignais en disant que le point critique serait la phase d'ajout d'une regexp à la liste (ou la séparation d'une regexp en deux, au choix)...
Idéalement, il faudrait explorer toutes les possibilités, et donc avoir un arbre de décision... Toutefois, le temps de calcul risque de devenir exponentiel, il faudra donc à un moment ou à un autre "trancher" et abandonner une regexp particulière au profit d'une alternative.

Si je vous dit que les mots peuvent faire jusqu'à 16 caractères et que l'alphabet est de 3 lettres (ça fait dans les 45 millions de séquences possibles au maximum), ça vous fait peur ou ça vous rassure ? :-D

Je dirais plutôt que ça me rassure : en gros, une centaine de mégas de RAM utilisés, c'est loin d'être insurmontable (même si ce sera long quand même ! )

En fait j'ai déjà une première optimisation qui me permet de travailler sur des entiers (32 bits) au lieu de chaînes de caractères, vu que l'alphabet de 3 lettres peut être représenté par 2 bits (00, 01, et 10). Donc occupation mémoire maxi de 45 Mo pour la liste de séquence la plus longue possible.

C'est déjà pas mal, mais reste un seul souci : comment coder un [ABC] sur deux bits ?? A ta place, j'utiliserais 3 bits en masque binaire (A=001, B=010, C=100), étendu à 4 bits pour raison de simplicité de découpage.
Ainsi, 4 bits = une regexp ou un caractère au choix, 16 caractères = 64 bits = ça tient sur un entier long...

De plus, ton problème étant séparable, tu peux travailler sur des nombres de 32 bits et doubler l'algo pour la partie "haute" et la partie "basse" de la chaine, ça n'aura pas d'incidence.

[GoustiFruit]

Oui oui, excuse-moi, j'ai effectivement codé les séquences simples sur des entiers de 32 bits, mais prévu de coder les séquences factorisées sur des entiers de 64 bits (je programme en Delphi et il n'y a pas d'entiers en 48 bits permettant des opérations "bitwise" efficaces) exactement comme tu l'as décrit !

Sinon les 43 millions et quelques de possibilités, c'est vraiment dans le pire des cas, la plupart du temps ça devrait tourner entre quelques centaines et quelques (10aines de) milliers de séquences.

[Mac LAK]

Je pense que ça vaut le coup d'essayer au moins une fois la méthode "totale", qui pourrait en fait s'apparenter à un crible d'ailleurs, histoire de voir ce que ça donne comme résultats...

[SpiceGuid]

Puis la séquence 4 (ACAB) et la séquence 7 (AAAB) peuvent être regroupées en A[AC]AB.

Ta notation est incomplète, dans ton exemple l'opération AC n'est pas de même nature que ton opération AB. La bonne notation c'est A[A|C]AB où le caractère | se lit "ou bien".

Il existe une structure de données optimale pour factoriser le plus long préfixe commun, c'est le Trie.

À partir de l'ensemble ACAB | AAAB :

• de gauche à droite, un Trie te renvoie l'arbre A[CAB|AAB], l'opération complémentaire consiste à détecter les sous-arbres communs (ici AB) pour les partager, ce qui donne le graphe A[A|C]AB
• ou bien dans l'autre sens, de droite à gauche, un Trie te renvoie l'arbre [AC|AA]AB, l'opération complémentaire consiste à détecter les sous-arbres communs (ici A) pour les partager, ce qui donne le graphe A[A|C]AB

Détecter les sous-arbres commun se fait simplement en utilisant un Trie dans le sens opposé.

[GoustiFruit]

Ah merci, maintenant je sais de quel côté chercher.

Pour la notation, je ne cherchais pas à être exact, j'ai fait au feeling ;-)

[SpiceGuid]

La notation est très importante vu la proximité du sujet avec les langages formels.
Un autre exemple pour bien illustrer la méthode et la notation.

Le dictionnaire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

RACE | RAT | RAY | RICE | RIDE | ROLE | ROME | ROPE | ROSE | ROW | RUDE | RULE

Après la mise en arbre par un Trie :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

R[A[T|Y|CE]|I[CE|DE]|O[LE|ME|W|PE|SE]|U[DE|LE]]

Après partage des sous-arbres communs; il faut plusieurs équations pour écrire un graphe sous forme textuelle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
c = CE
d = DE
l = LE
main = R[A[T|Y|c]|I[c|d]|O[l|ME|W|PE|SE]|U[d|l]]

Graphiquement, le graphe/automate obtenu ressemble à ceci :



Une implantation en OCaml du Ternary Search Trie.

Effectivement, ca ressemble beaucoup à de la minimisation d'automate à états finis.

Tout à fait. Les automates c'est une autre approche (plus abstraite et à mon avis plus difficile à implanter) du même problème.