Récursivité dans l'algorithmique et la programmation/Exercices/Structure de données récursives
Structure de données récursives : une structure de type dictionnaire
[modifier | modifier le wikicode]Introduction
[modifier | modifier le wikicode]
|
À lire absolument, avant de commencer l'exercice |
Nous nous proposons ici de créer une structure de données permettant de contenir un dictionnaire, c'est-à-dire tout simplement une liste de mots. Si nous ouvrons un dictionnaire nous observons une liste[1] telle que :
- A, subst. masc. : ... définition
- À, prép, : ... définition
- AALÉNIEN, IENNE, adj. et subst. masc. : ... définition
- AB-, préf. : ... définition
- ABA, subst. masc. : ... définition
- ABACA, subst. masc. : ... définition
- ... ainsi de suite
- ZYMOTIQUE, adj. : ... définition
- ZYTHUM, subst. masc. : ... définition
- ZZZ, onomat. : ... définition
Dans cet exercice, nous nous limiterons uniquement aux vedettes (le mot dont la définition est donnée à la suite, une entrée du dictionnaire), sans conserver ni leurs genres, ni leurs définitions, ni leur casse (tous les mots seront écris en minuscules). Un tel lexique pourra être tiré du dictionnaire mis à disposition par le CNAMCNAM. Il comprend 251307 mots différents (~2,6 Mo, ce qui fait une moyenne 9.8 caractères par mot).
Un tel lexique peut être stocké dans un tableau à 251307 entrées (une par mot) ou dans une liste chaînée de mots. Mais en y regardant de plus près, on remarque que des mots consécutifs dans le lexique trié ont souvent un préfixe commun :
- INAPPARENT
- INAPPÉTENCE
- INAPPLICABLE
- INAPPLICATION
- INAPPLIQUÉ
- INAPPRÉCIABLE
- INAPPRÉCIÉ
- INAPPRÊTÉ
- INAPPRIVOISABLE
- INAPPRIVOISÉ
- INAPPROCHABLE
Il est tentant de factoriser les préfixe INAPP sur toute cette liste :
- INAPP
- ARENT
- ÉTENCE
- LICABLE
- LICATION
- LIQUÉ
- RÉCIABLE
- RÉCIÉ
- RÊTÉ
- RIVOISABLE
- RIVOISÉ
- ROCHABLE
On peut réitérer le procédé dans la sous-liste
- LICABLE
- LICATION
- LIQUÉ
pour la transformer en
- LI
- CABLE
- CATION
- QUÉ
- LI
Si on poursuit à plus soif on obtient à partir de la première liste des INAPP
- INAPP
- ARENT
- ÉTENCE
- LI
- CA
- BLE
- TION
- QUÉ
- CA
- RÉ
- CI
- ABLE
- É
- CI
- RÊTÉ
- RIVOISA
- BLE
- SÉ
- ROCHABLE
On reconnaît là la naissance d'une structure arborescente. Mais il subsiste un petit problème, celui d'un mot entièrement contenu dans un autre. Considérons la liste
- BAL
- BALS
- BALLE
- BALLES
La construction nous conduit à
- BAL
- S
- LE
- S
Pour simplifier les choses, nous ajoutons à la fin de chaque mot un marqueur de fin de mot qui sera noté , celà nous conduit à quelque chose comme :
- BAL
- =bal
- S =bals
- LE
- =balle
- S =balles
Arbre n-aire
[modifier | modifier le wikicode]Transformer un arbre n-aire en arbre binaire
[modifier | modifier le wikicode]Question de point de vue
[modifier | modifier le wikicode]Arbre binaire
[modifier | modifier le wikicode]Le dictionnaire sous forme arbre binaire
[modifier | modifier le wikicode]Notes
[modifier | modifier le wikicode]
