Discussion :

[Gojippo]

Bonjour a tous. J'apprends Perl pour mon boulot, et je bloque sur un exercice qu'on m'a donne:
Je travaille sur des fichiers de dictionnaire, et un exercice qu'on m'a donne consiste a extraire des mots d'une base de donnees qui n'existent pas dans le dictionnaire. J'ai donc un fichier dictionnaire, compose d'un mot par ligne, et de bases de donnees, egalement 1 mot par ligne.

L'exercice qu'on m'a donne consiste a extraire les mots n'existant pas dans le dictionnaire, et de les printer. Tout cela sans utiliser de tableaux de hachage ni grep, et en composant le programme le moins gourmand en ressources possibles.

Donc, je fais :

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
#!/usr/bin/perl
use strict;
use warnings;
 
my $wordlist = shift;
my @allwords;
 
open WORDLIST, $wordlist; #J'ouvre d'abord le fichier dictionnaire.
while (<WORDLIST>){
  chomp;
 
  my $word = $_;
  push (@allwords,$word) #Je cree un tableau ou je mets chaque mot du fichier.
}
close WORDLIST; #je ferme le dico

Apres ca, j'ouvre le fichier de base de donnees, et c'est la que je coince parce qu'en dehors de grep et des tables de hachage, je ne sais pas comment chercher si un mot lu existe dans un tableau. Qu'est-ce qu'il serait possible de faire ?

[CKLN00]

bon alors ce que je vais te proposer relève du bricolage parce que je suis un débutant :p

moi je construirais pas un simple tableau avec tout les mot mais plus tot
un tableau de tableau :
le premier niveau du tableau servirais à déterminer la première lettre (0 pour le A 1pour le B etc.) des mot du tableau qu'il contiens. Comme je n'arrive pas à m'expliquer clairement je donne un exemple:
si j'ai les mot suivant dans le fichier dictionaire:
abruti, le mot abracadrabrantesque, et le mot zèbre
voila ou je les trouverais dans mon tableau de tableau :
@Tableau_de_tableau[0][0] contiendrais abracadrabrantesque,
@Tableau_de_tableau[0][1] contiendrais abruti
@Tableau_de_tableau[25][0] contiendrais zèbre

Tout ça pour arriver à quoi finalement ?
en fait si tu fait ça il te suffit de récupérer la première lettre du mot de la base de données (avec un substr par exemple ?) de la mettre en majuscule(fonction uc()), et de choper sont code ASCII (avec la fonction ord() ) d'y soustraire 65 (car ord(A) = 65) et tu à l'indice de premier niveau de ton tableau.
A partir de la tu parcoure tout le tableau de second niveau (donc tout les mots commençant par la même lettre se trouvant dans le dictionnaire) et tu les test.
Comme j'ai l'impression de pas être clair (un peu comme toujours je donne un exmple)

on va considérer que on as le même dictionnaires que précédemment,
on est dans la base de donnée et est sur la ligne ou se trouve le mot "nouille"
l'algorithme doit faire :

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
 
while <bdd>
{
  $indice = ord( uc( substr($_,0,1) ) ) - 65 ;
  $le_mot_est_a_printer = 1 ;
  foreach $mot_du_dico (@{$Tableau_de_tableau[$indice]})
  {
    if ($mot_du_dico eq $_)
    {
      $le_mot_est_a_printer = 0 ;
      last ; #on as trouver le mot pas la peine de continuer à chercher
    }
  }
  if ($le_mot_est_a_printer)
    {print;}
}

bon je sais pas si ça marche ni si ce que j'ai essayer d'expliquer est clair désoler j'aurais fait ce que j'ai pu !!

[iblis]

Tu peux aussi simuler un grep.

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
#!/usr/bin/perl
use strict; use warnings;
 
my @words = qw[abracadabrantesque rien tout];
 
while (<DATA>) {
    chomp;
    print $_ . "\n" if not inlist($_, \@words)
}
 
sub inlist {
    my ($word, $list) = @_;
    for (@$list) {
        return 1 if $word eq $_;
    }
    return 0;
}
 
__DATA__
politique
abracadabrantesque
truc
rien

En même temps pourquoi faire compliqué quand Perl fournit une structure adéquate (hash) ?

[CKLN00]

oui ce que propose iblis est une bonne idée, mais je pense que pour optimiser la vitesse du pseudo grep il vaut mieux utiliser un tableau de tableau cela permet au pseudo grep de ne parcourir qu'une toute petite partie du dictionaire pour touver (ou pas) son bonheur

(attention d'ailleurs dons mon exemple je considère que le dictionnaire contient des mots commençant par toute les lettres de l'alphabet et que donc les 25 tableau de second niveau sont définit)

[Jedai]

bon alors ce que je vais te proposer relève du bricolage parce que je suis un débutant :p

C'est pas du bricolage (bon l'implémentation est artisanale, faudrait en faire un objet), la structure de donnée que tu décris est parfaitement légitime et porte un nom : trie (ou arbre à lettre en français). Elle est très efficace pour stocker et consulter un dictionnaire (si elle est implémentée proprement, ce qui est difficile en Perl pur).

Néanmoins, dans le cas de ce problème précisément, il y a une meilleure solution.
Les fichiers dictionnaires sont normalement trié dans l'ordre lexical, est-ce le cas ? Si oui, alors la solution est en espace constant et en temps linéaire, sinon elle est en espace linéaire (pour faire simple) et temps linéaire.

Ce qui est mieux que d'utiliser un grep ou un hash en fait...

La solution consiste à avancer en parallèle dans le fichier dictionnaire et la liste de mots dans la base de donnée (tu fais ta requête pour que la BDD te renvoie cette liste de mot triée) : à chaque couple tu peux savoir si il te faut avancer dans la BDD ou dans le dictionnaire, et en passant tu détectes les mots qui ne sont pas dans le dictionnaire.

Tu vois comment faire ça ou tu veux que j'explicite ?

Si on t'a demandé le moins gourmant en ressource c'est sans doute ce qu'on attend de toi. (Et je suppose que je ne devrais pas t'aider plus avant puisqu'il s'agit d'un assignement...)

--
Jedaï

[iblis]

Tu vois comment faire ça ou tu veux que j'explicite ?

Ben en fait — une fois qu'il aura résolu l'exercice — moi je voudrais bien des détails sur l'implémentation (en particulier dans le cas d'une lecture séquentielle de fichiers triés).

Bon à l'occasion, je vais peut être déjà essayer de voir si j'y arrive par moi-même.