Discussion :

[jarodxxx]

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]

Bonjour,

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

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

Z.

[jarodxxx]

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]

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]

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

Merci d'avance .

[Zwiter]

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";
		}
	}