cours sur les tables d'association

Description

-1-INF 421 Luc [e-mail]://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-2-Les tables d’associations◮ Qu’est-ce que c’est ? Des associations de n’importe quoi a`n’importe quoi.◮ Comment c¸a marche ? Trois impl´ementations.⊲ Avec des listes.⊲ Avec notre table de hachage.⊲ Avec les tables de hachage de la biblioth`eque.-3-La table d’associationSoit des ( informations ), munies d’une ( cl´e )).◮ La cl´e identifie d’information.⊲ Nom (et pr´enom)→ num´ero de t´el´ephone dans l’annuaire.⊲ Matricule→ soldat.⊲ Num´ero d’immatriculation→ v´ehicule, dans le fichier descartes grises.◮ On se place dans le cas ou` la cl´e identifie une informationunique (par ex. fichier des cartes grises).-4-La table d’associationEnsemble dynamique d’informations.Type abstrait de donn´ees, d´efini par les op´erations.◮ Trouver l’information associ´ee `a une cl´e donn´ee.◮ Ajouter une nouvelle association entre une cl´e et uneinformation.◮ Retirer une cl´e de la table (avec l’information associ´ee).Et plus pr´ecis´ement (unicit´e des cl´es)◮ S’il existe d´ej`a une information associ´ee `a la cl´e dans la table,alors la nouvelle information remplace l’ancienne.◮ Sinon, une nouvelle association est ajout´ee `a la table.-5-ApplicationOn veut produire une statistique des mots d’un texte.◮ Voici par exemple un texte bien connu.% cat marseillaise.txtAllons ! Enfants de la Patrie !Le jour de gloire est arrive´ ...

Sujets

• informatique

Informations

• Publié par: Thuen
• Nombre de lectures: 52
• Langue: Français

Extrait

-1-

INF

421

Luc

Associations

Maranget

[e-mail] http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/

-2-

◮

◮

Les tables d’associations

Qu’est-cequec’est?Desassociationsden’importequoi`a n’importe quoi.

Comme¸simpl´ementations. nt ca marche ? Troi

⊲Avec des listes.

⊲Avec notre table de hachage.

⊲Avec lestables de hachagebabidle`hqeilto.eu

-3-

La table d’association

Soit des✭informations✮, munies d’une✭ecl´✮.

◮maornf’i.onti´lieLcafiideedtn

⊲Noe´rpte(m)mon→mun´erodet´el´ephondenalsa’nnauri.e

⊲atMcurile→soldat.

⊲oinlutartciNe´mu’dorammi→sedre´vhefichinslee,daicul cartes grises.

◮nsdacelaepnsOnoitallce´dielacosu`einformaentifieun unique (par ex. fichier des cartes grises).

-4-

La table d’association

Ensembledynamiqueind’sn.taoiofmr

Typeabstraitdedonnees,d´efiniparlesop´erations. ´

◮`l´esdsooncni´´eeeemrtaoianre’lniofTuvro a une c .

◮Ajouteleelsaosurenonvurentecunatcineioee´lenut information.

◮unecirerReta(evbaelleta´ldeasontimaornf’icl.)ee´icos

Etplusp´ie´ment(unicit´edescl´es) rec s

◮`´ie´adallctablnslae,Seli’tsixe´deua`jinnermfoioatssna oc ee a alors la nouvelle information remplace l’ancienne.

◮ssaeaicouonellevnoSiunn,.latabaeljout´ee`tionesta

-5-

Application

On veut produire une statistique des mots d’un texte.

◮Voici par exemple un texte bien connu.

% cat marseillaise.txt Allons ! Enfants de la Patrie ! Lejourdegloireestarriv´e! etc.

◮sdotaMelesncsmde(esistomesraalliStatifs´rqeeutsqieueded taille≤jasu4m,senlculees).ev´e

% java Freq marseillaise.txt nous: 10 vous: 8 franc¸ais:7 etc.

-6-

Entrois´etapes.

Conception de

1. Lire le texte mot ` mot -a- .

2. Compter les occurences des mots.

Freq

3.Produireunbelaffichage(parfr´equencesde´croisantes).

Pluspr´ecis´ement.

1.Proce´derselonleprincipeduReader.

2.Parunetabled’associationdesmotsauxcomptes.(cle´=un mot→information = un compte).

3.Paruntri`alafin.

-7-

Lecture des mots, tri

Onsupposedonne´s:

◮Une classe des objets✭lecteur de mots✮(WordReader).

⊲ConstructeurWordReader(String name)euop´rcrlree lecteur des mots d’un fichier de nomname.

⊲etM´dehoString read(), renvoie le mot suivant (ounull quand c’est fini).

◮Un tri des paires, mot×e´setempot(ncow→c l’ordre). Selon total :

(w 1 →c 1 )<(w 2 →c 2 ) m

(c 1 > c 2 )∨(c 1 =c 2 ∧w 1 < w 2 )

-8-

D´efinitionpre´cisedenotretable

Une table est un objetAssoc une table d’association des. C’est mots (String) auxint.

◮deteoh´Mintget(String w)eassoci´e`aer,iovnceletpmow.

⊲Ou bien 0 siwn’est pas dans la table.

◮e´Meodthvoidput(String w,intc), associe le comptecau motw.

Spe´cificationenJava,paruneinterfacemmnetee).(oc ´

interfaceAssoc{ /*Cr´eer/remplacerl’associationkey→val */ voidput(String key,intval) ; /*Trouverl’entierassocie´akey,ouze´ro.*/ ` intget(String key) ; }

-9-

Code de

main

classFreq{ . . . static voidcountFile(String name,Assoc t) { WordReader wr=newWordReader(name) ; count(wr,t) ; wr.close() ;meer/F/tn´rlre’ulpseep(e)ropr Sort.println(t) ;e´teirchagAffi// }

}

public static voidmain(String[]arg) { countFile(arg[0],. . .) }

-10-

Code decount static voidcount(WordReader in,Assoc t) { for(String word=in.read() ; word!=null; word=in.read()) { i f(word.length() >= 4) { word=word.weLotoeasrC() ; t.put(word,t.get(word)+1) ; } } }

Remarquer :Assocn’est pas une classe, mais on peut l’utiliser commeuntype,celuidudeuxie`meargumentdecount.

-11-

Les listes d’associations

Lafa¸conlaplussimpled’associeruncompte`aunmot?

Une liste de pairesString→int. classAList{ privateString word; private intcount; privateAList next;

AList(String word,intcount,AList next) { this.word=word;this.count=count;this.next=next; } }

Attention

◮iectet´snsuaoomss’uunau`usaolqpetseu.ppcomOpn

◮blevLataertseeditnese´rp..arep´e. null.

◮blevLataertseeditnese´rp..arep´e.