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