Anagramme complexe

**jarodxxx** · 14/08/2009, 12h41

bonjour a tous,

je viens poster ici car je butte sur une regex depuis trop longtemps , et j'espère que la communauté pourra m'aider ...
Voici l'exposer du problème:

Je dois comparer une chaine générée aléatoirement avec un dictionnaire existant pour vérifier si la chaine générée peut créer un mot réel issue du dictionnaire .

exemple :
Je genere : RBTOOS, je cherche a matcher ROBOTS , ou encore ROBOT , le nombre de caractere est variable entre 3 et 6 c'est a dire qu'avace ce meme lettre je doit pouvoir ecrire ROOTS ou encore ROT ( en supposant qu ces mots existe dans le dictionnaire.

Une des condition est que les lettre ne peut être utilisée qu'une fois , donc si je genrere une chaine contenant OO , on pourra utilisé 2 fois le O.

Le problème majeur viens du doublonage de lettres , en effet voila ma regex de base :

[RBTOS]{5} qui autorise donc un mot de 5 caractères avec les lettres listées
MAIS [RBTOOS]{5} ne fonctionne pas puisque l'intervalle ne considére qu'un seul O

Je ne voie donc pas comment spécifier a la regex que le O peut être utilisé 2 fois (pas forcement consécutivement) en plus de lettres spécifie..

J'espère que j'ai était assez claire parce que c pas évidement .

Merci d'avance a tous

**Zwiter** · 14/08/2009, 13h16

Bonjour,

A ma connaissance, ce n'est pas faisable en regex. Donc ce que je te propose :

Tu pourrais compter le nombre de chaque caractères de ta chaine aléatoire.
Ensuite, tu comptes pour chaque entrée du dictionnaire le nombre de chaque caractères.
Pour finir tu verifie pour chaque lettre du mot du dico, que tu as assez de lettre dans ta chaine aléatoire.

Z.

**jarodxxx** · 14/08/2009, 13h27

Le nombre de caractères générer aléatoirement est fixe (6 char) en base de données j'ai une liste de mots de 3 caractères ; une autre de 4 , puis une de 5 et enfin une liste de mots a 6 lettres.

Je doit au finale générer une liste contenant : la chaine aléatoire : avec la liste de tous les mots possible en 3 , 4 , 5 et 6 lettres,

une chaine aléatoire n'est valide que si on trouve au minimum 1 mot de 3 , 1 mot de 4 , un mot de 5 et un mot de 6 lettres.

Je devrais comparer toutes les combinaisons possible de la chaine aléatoire avec l'intégralité des mots de mes 4 dictionnaire ?

Sachant que mes chaines aléatoires sont pre-existante et au nombre de 272 500 ...
Il fraudais que je fasse une boucle de 8000 tours pour tester les combinaisons et que je comparer ces 8000 possibilité avec le diction , le tout 272000 fois ?

C impensable !! a moins que quelqu'un ai un contact a la NASA pour me prêter un de leurs serveur

**Zwiter** · 14/08/2009, 13h47

Ca va plutot vite chez moi 0.35 secondes (script en Perl sur un XEON 3,4 Ghz).
Donc 272000 fois, ca fait au max : 95200 secondes ou 26.5 heures. Faisable sans la nasa. Et pour peu que tu aies plusieurs coeurs sur ton proc, lance le plusieurs fois

En optimisant (dictionnaire toujours chargé en mémoire, le nombre de lettres deja calculé), tu devrais pouvoir baisser tres largement ce temps de calcule.

le regex consomme aussi du temps.

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
time perl find.pl RBTOOS
        robots
        boots
        borts
        robot
        bort
        bots
        robs
        rots
        rots
        sort
        tors
        bot
        ors
        rob
        rot
        rot
        sot
        or
        os
 
real    0m0.345s
user    0m0.336s
sys     0m0.009s

Z.

**jarodxxx** · 14/08/2009, 14h22

Pourais poster ton script que je voie comment tu a fait ?

Merci d'avance .

**Zwiter** · 14/08/2009, 14h44

C'est du perl, je ne sais pas si ca va te parler, mais le principe est facilement transposable en php ou en C (si la rapidité est recherchée).

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#!/usr/local/bin/perl
 
use warnings;
use strict;
use Data::Dump qw(dump);
 
my $start_time;
start_timer();
# my $dico_file = 'liste.de.mots.francais.frgut.txt'; #original dictionary
my $dico_file = 'inf_6.txt'; #6 max length word dico
 
###################################
#input
my $find = lc($ARGV[0]);
my %chars_ct;
 
foreach my $char (split(//, $find)) {
	$chars_ct{$char}++;
	}
 
###################################
# print "Cherche des mots\n";
my $dico;
my %alpha_ct;
my $manon;
my $flag;
my %result;
 
my $handle = open_file($dico_file);
#to construct a 6 max length word dico
# open(OUT, ">inf_6.txt");
while (my $line = <$handle>) {
	$line =~ s/\r//;
	chomp $line;
	if ($line eq '') { next; }
 
#to construct a 6 max length word dico
# 	if (length($line) <= 6) { print OUT lc($line), "\n"; }
# 	next;
 
	my %alpha_ct;
	$flag = 1;
 
	foreach my $char (split(//, $line)) {
		$alpha_ct{$char}++;
		}
 
	foreach my $char (keys %alpha_ct) {
		if (!defined($chars_ct{$char}) || ($alpha_ct{$char} > $chars_ct{$char})) {
			$flag = 0;
			last;
			}
		}
 
	if ($flag == 1) {
		push @{ $result{length($line)} }, $line;
		}
	}
#to construct a 6 max length word dico
# close OUT;
 
close($handle);
 
my $ct = 0;
foreach my $length (sort {$b<=>$a} keys %result) {
	foreach my $word (@{ $result{$length} }) {
		$ct++;
		print "\t$word\n";
		}
	}

**jarodxxx** · 14/08/2009, 14h53

aie c effectivement assez dur pour moi de trduire ca en php , je n'ai jamais fait de PERLE .

je reste convaincu qu'il existe une REGEX pour ce que je veux faire mais je vais regarder ton script tout de meme pour essaye de le convertir.

en tout cas merci

**jarodxxx** · 14/08/2009, 15h09

est il envisageable de te demander si tu pourais traduire le script ,

Je viesn d'essayer mais y a des tonnes de caracteres que je ne sais pas convertir :s

**Zwiter** · 14/08/2009, 15h29

je n'ai pas le temps maintenant car je parts en weekend.
La semaine prochaine si tu n'a pas trouver de meilleur solution.

Z.

**jarodxxx** · 14/08/2009, 15h30

Merci bien

et bon week end !!

**jarodxxx** · 17/08/2009, 09h31

J'y ai passé le week end , et j'ai réussi a créer un script qui retrouve les anagramme , c'est a dire toutes les combinaison de lettre possible avec les lettres données , donc si j'entre 6 lettres , j'obtiens toutes les combinaison de 6 lettres , mais j'ai toujours pas réussis a obtenir les combinaison de 3, 4 et 5 lettres avec ces 6 même lettres

**Zwiter** · 17/08/2009, 10h07

Salut,
Bien joué pour ton script. AS tu essayé de reprendre l'algorithme dont je parlais ?

Voici l'application en php de mon code en perl. LA structure est exactement la meme. Pour des histoires de variables s'initialisant pas pareil, il y a qqs trucs en plus ou en moins :

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
30
31
32
33
34
35
36
37
38
39
40
41
42
<?
header('Content-type: text/plain');
//##################################
//input
$str = $_GET['string'];
$find = strtoupper($str);
$dico_file = 'inf_6.txt';
 
for($i = 0; $i < strlen($find); $i++ ) {
	if (!isset($chars_ct[$find[$i]])) $chars_ct[$find[$i]] = 1;
	else $chars_ct[$find[$i]]++;
	}
// 	print_r($chars_ct);
 
//##################################
// print "Cherche des mots\n";
 
$handle = fopen("$dico_file", "r");
while (!feof($handle)) {
	$alpha_ct = array ();
	$line = fgets($handle);
	$line = trim($line);
	$line = strtoupper($line);
 
	$flag = true;
 
	for($i = 0; $i < strlen($line); $i++ ) {
		if (!isset($alpha_ct[$line[$i]])) $alpha_ct[$line[$i]] = 1;
		else $alpha_ct[$line[$i]]++;
		}
 
	foreach ($alpha_ct as $key => $value) {
		if (!array_key_exists($key, $chars_ct) || ($value > $chars_ct[$key])) {
			$flag = false;
			break;
			}
		}
 
	if ($flag) print "$line\n";
	}
fclose($handle);
?>

La requete :
php test2.php string=ABATSEE
doit retourner (si on a le meme dictionnaire) :

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
A
ABAT
ABATEE
ABATS
AS
BAS
BASA
BASAT
BASE
BASE
BASEE
BASTE
BAT
BATA
BATAS
BATE
BATE
BATEE
BATEES
BATES
BATES
BATS
BEA
BEAS
BEAT
BEAT
BEATE
BEATES
BEATES
BEATS
BEE
BEES
BETA
BETAS
BETE
BETES
EBAT
EBATS
ES
ES
EST
ET
ETE
ETES
ETES
SA
SE
SET
TA
TABES
TAS
TE
TE
TEE
TEES
TES
TES

Tu peux encore optimiser cela en suprimant du dictionnaire tous les mots supérieurs a 6 lettres, et inférieur a ton seuil minimal.

Z.

**jarodxxx** · 17/08/2009, 12h41

Merci pour ton script ...
Je suis en train d'adapter le format de mon dictionnaire pour le tester ,

en attendant je me suis endu compte d'un principe logique , une fois que la liste COMPLETE des anagramme d'une serie de lettre est genrée , il suffit de dupliqué cette liste en enlevant un caractere a chaque fin de mot, puis enlever 2 puis 3.

j'ai utilisé cette methode avec un array que j'ai dedoublonné avec array_unique ce qui me donne exactement la liste complete et dedoublonné. un peu moins lours que de regenerer une 3e , 4 et 5 liste d'anagrammes ...

qu'en penssez vous ?

**Zwiter** · 17/08/2009, 12h50

J'en pense pas grand chose, car ton principale souci semble le facteur temps. Il faut trouver la methode la plus rapide.

Concernant ton objectif, je ne comprends pas pourquoi il faut retirer des lettres aux mots. Car ducoup, ce ne serait plus un mot valide...
Explique-moi ca (on peut se tutoyer

) clairement car je pense qu'on peut encore faire plus simple. Comme par exemple utiliser le passage a 6 lettres pour aussi faire celui à 5, 4...

Z.

**jarodxxx** · 17/08/2009, 14h02

A chaque itération , si on considère que le mots générer est unique prenons l'exemple de ROBOTS en enlevant des lettres on obtient :
ROBOTS (6 lettres)
ROBOT (5 lettres)
ROBO (4 lettres)
ROB ( 3 lettres)

Ce sont autant de mot a ne pas calculer (mais a comparer au dictionnaire pour vérifier qu'ils existent.
Seulement les 6 lettres donne forcement des doublons de 3 ou 4 lettre par exemple en prennant toujours RBTSOO
on aura un de annagram qui donnera
ROBOST en 6 lettres
ce qui donnera en 3 et 4 lettres
ROBO
ROB

on a don des doublons très rapidement, c'est pour cela que je passe par un array que je filtre ...

au final j'obtiens une liste de 1200 mots maximum composée de 720 mots de 6 lettres , 120 mots de 5 lettres, 24 mots de 4 lettres et 6 mots de 3 lettres

Je dois ensuite et c'est maintenant que ca va faire péter la machine, comparer ces 1200 'chaines sans sens' pour en déduire les mot existant !

A partir de la, j'obtiens un mini -dictionnaire correspondant a une suite de lettres.

Pour information ces 'suite de lettres ne sont pas aléatoire , mais définie , en effet j'ai genere TOUTES les combinaison de lettres possible avec l'alphabet c'est a 272 528 chaines pour les quelles je doit générer les 1200 anagrammes que je vais comparer au dictonnaire de 27 710 mots (mot de langue francais compris entre 3 et 6 lettres.

Calcule rapide :
272 528 cobinaison alphabetique
x
1200 anangrammes
=
327 033 600 chaines a comparer
x
27 710 Mots du dictionnaire
===============================
9 062 101 056 000 tours de boucles a effectuer :s

**jarodxxx** · 17/08/2009, 14h08

Je viens de tester ton script , il marche parfaitement , j'ai les mêmes résultats que toi, mais mon dictionnaire ne comporte que les mot entre 3 et 6 lettres ...

**Zwiter** · 17/08/2009, 14h23

Plusieurs points que je ne saisi pas :
Pouruqoi retirer les doublons ?
Ces doublons sont bien des mots valides ?
Pouruquoi 272 528 chaines ("TOUTES les combinaison de lettres possible"), alors que 26^6 = 308 915 776 ?
La liste de 1200 est obtenue uniquement avec les lettres RBTSOO ?
9 062 101 056 000 tours de boucles a effectuer : as tu essayer d'en effectuer 100 000 ou 1 000 000 pour estimer le temps que prendra le travail entier ?

Mon dictionnaire contient les mots de 6 lettres et moins.

Si tu veux optimiser le truc, met ton dictionnaire dans la meme casse que les chaines de lettre a tester pour ne plus utiliser strtoupper.

Mon script 'marche parfaitement', est ce que ton probleme est résolut ?

**jarodxxx** · 17/08/2009, 14h34

Plusieurs points que je ne saisi pas :
Pouruqoi retirer les doublons ?
Ces doublons sont bien des mots valides ?

non il s'agit de doublons de chaines

Pouruquoi 272 528 chaines ("TOUTES les combinaison de lettres possible"), alors que 26^6 = 308 915 776 ?

c'est du a l'optimisation , je genere QUE les chaine logique, c'est a dire RBTSO et OTBSR donnerons les même anagramme , inutile donc de recomparer cette serie de lettres , on perdrais du temps pour obtenir un même resultats qu'il auras fallu déboulonner.
J'ai enlever aussi tous les Quadriple de lettre un mot de 6 lettres contenant 4 n ( ptnnnn ) n'est pas valable , de meme , pas de chaine sans au moins 2 voyelles ...ect ...

on obtient 272528 chaine de caractere uniques et probables...

La liste de 1200 est obtenue uniquement avec les lettres RBTSOO ?

en l'ocurence non a cause des double O , mais une chaine de 6 caractère differents , donne 1200 combinaisons

9 062 101 056 000 tours de boucles a effectuer : as tu essayer d'en effectuer 100 000 ou 1 000 000 pour estimer le temps que prendra le travail entier ?

J'y travaille , mais je suis partie sur la base de ton script qui est beaucoup plus rapide et logique, en bouclant , il me renvoie des resultat bizzard et incomprehenssible , je cherche le bug ^^

**Zwiter** · 17/08/2009, 14h47

hesite pas a demander de l'aide...
Au pire, j'ai de la puissance de calcule sous le coude

Z.

Anagramme complexe [RegEx]

Langage PHP

Discussions similaires

Partager

Partager