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

Introduction

À 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 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É

Si on poursuit à plus soif on obtient à partir de la première liste des INAPP

• INAPP
  • ARENT
  • ÉTENCE
  • LI
    • CA
      • BLE
      • TION
    • QUÉ
  • RÉ
    • CI
      • ABLE
      • É
  • 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é $\epsilon$, celà nous conduit à quelque chose comme :

• BAL
  • $\epsilon$ =bal
  • S =bals
  • LE
    • $\epsilon$ =balle
    • S =balles

Transformer un arbre n-aire en arbre binaire