Apprendre Maple Arbres n-aires

 
  Page d'accueilPage d'accueil   RechercherRechercher   Forum de discussionForum de discussion   ContactContact   SommaireSommaire 
  Cours MapleCours Maple   Travaux dirigésTravaux dirigés   Thèmes d'activitésThèmes d'activités   Thèmes d'activitésMaplets
Ecran MapleEcran Maple  TéléchargementTéléchargement  BibliographieBibliographie  LiensLiens  

 

 

Page d'accueil   Thèmes d'activités   << Thème précédent    


 

Dans cette feuille de calcul, nous définirons une structure représentant un arbre n-aire (arbre tel que chaque nœud donne naissance à au plus n fils).
Notre application étant le codage d'un dictionnaire, nous supposerons que chaque nœud de l'arbre est étiqueté par une chaîne de caractères.
Ainsi, par exemple l'arbre n-aire suivant représente le codage du dictionnaire: "EPI","EPIER","EPIERA","EPIERAI","EPIERAS","EMU","SU","SALI","JEU".
Le point à la suite d'une lettre indiquera la fin d'un mot, ainsi "EPIE" n'est pas un mot du dictionnaire, mais est un préfixe pour les mots
"EPIER","EPIERA","EPIERAI","EPIERAS".
 

L'arbre sera représenté par une structure de listes imbriquées:

[Maple Plot]

 

>    restart;
 

La racine de l'arbre est un noeud étiqueté par une chaîne de caractères vide:

>    tree:=[""]:
 

La procédure récursive insert  permet d'ajouter le mot word à un arbre tree . Le booléen b  indique s'il a la valeur true  le rajout d'un point à la fin du mot dans l'arbre,
sinon aucun point n'est rajouté à la fin du mot.
 

>    insert:=proc(tree::list,word::string,b::boolean)
local letter,i,s,M;
if word="" then return `if`(b,subsop(1=cat(tree[1],"."),tree),tree) end if;
letter:=word[1]:
for i from 2 to nops(tree) do
  if op(1,tree[i])[1]=letter then
     return(subsop(i=procname(tree[i],word[2..length(word)],b),tree))
  end if
end do;
M:=[op(tree),[letter]]:
return(subsop(nops(M)=procname(M[nops(M)],word[2..length(word)],b),M))
end proc:
 
>    tree:=insert(tree,"EPI",false);

tree := [

>    tree:=insert(tree,"EPI",true);

tree := [

Notez la différence suivant la valeur booléenne de b : dans le premier cas "EPI" n'est pas un mot du dictionnaire puisque son dernier caractère "I" n'est pas suivi

d'un point dans tree , mais pourra servir de préfixe pour d'autres mots à ajouter.

Dans le second cas, "EPI" est un mot du dictionnaire puisque son dernier caractère "I" est suivi d'un point dans tree .

>    tree:=insert(tree,"EPIER",true);

tree := [

>    tree:=insert(tree,"EMU",true);

tree := [

>    tree:=insert(tree,"SU",true);

tree := [

>    tree:=insert(tree,"SALI",true);

tree := [

>    tree:=insert(tree,"EPIERAI",true);

tree := [

>    tree:=insert(tree,"EPIERA",true);

tree := [

>    tree:=insert(tree,"EPIERAS",true);

tree := [

>    tree:=insert(tree,"JEU",true);

tree := [

On obtient la représentation en listes imbriquées correspondant à l'exemple précédent.

 

La procédure width , utilisée par la procédure drawtree , calcule la largeur de l'arbre tree :

>    width:=proc(tree::list)
local s,nb,level,maxlevel,i;
level:=-1: maxlevel:=0: s:=convert(tree,string);
for i to length(s) do
  if s[i]="[" then
    level:=level+1:
    if level>maxlevel then maxlevel:=level end if:
    if assigned(nb[level]) then nb[level]:=nb[level]+1 else nb[level]:=1 end if
  elif s[i]="]" then
    level:=level-1
  end if:         
end do:
`if`(maxlevel>0,max(seq(nb[k],k=1..maxlevel)),1)
end proc:
 
>    width(tree);

5

>    with(plottools): with(plots): 
Warning, the names arrow and changecoords have been redefined

La procédure drawtree permet une représentation graphique de l'arbre tree :
>    drawtree:=proc(tree::list)
local dr,P;

dr:=proc(t::list,leftlim,oldx,oldy)
 local x,y,nb,i,l;
  l:=leftlim;
  nb:=width(t);
  x:=l+iquo(50*nb,2);
  y:=oldy+80;
  if op(1,t)<>"" then
    P:=P,textplot([x,y+10,op(1,t)],color=blue,font=[HELVETICA,BOLD,12]),display(line([x,y-5],[oldx,oldy]))
  end if;
  for i from 2 to nops(t) do
    dr(t[i],l,x,y+20):
    nb:=max(nb,width(t[i]));
    l:=l+(nb-1)*50;
  end do
end proc:
 
P:=NULL: dr(tree,0,0,0): display(P,axes=none)
end proc:        
 
>    drawtree(tree);

[Maple Plot]

La procédure delete  permet de supprimer le mot word  de l'arbre tree : en fait la procédure ne fait que supprimer dans tree  le point suivant le dernier caractère de word .
Le mot disparaît ainsi du dictionnaire mais garde son rôle de préfixe éventuel pour d'autres mots.

>    delete:=proc(tree::list,word::string)
local del,t;

del:=proc(a::list,s::string)
local m,i;
m:=s:
for i from 2 to nops(a) do
  m:=cat(m,op(1,a[i])[1]):
  if op(1,a[i])[2]="." then
    t:=insert(t,m,`if`(m=word,false,true))
  end if;
  procname(a[i],m):
  m:=s
  end do:
end proc:

t:=[""]: del(tree,""); t
end proc:
 
>    tree; delete(tree,"EPIER");

[

[

Le point derrière le "R" de "EPIER" a été supprimé.
 


La procédure deletenode  permet de supprimer de l'arbre tree  tous les descendants de node , c'est à dire tous les mots dont node  était un préfixe:

>    deletenode:=proc(tree::list,node::string)
local del,n,t;

del:=proc(a::list,s::string)
local m,i,l,b;
m:=s:
for i from 2 to nops(a) do
  m:=cat(m,op(1,a[i])[1]): l:=length(m):
  if op(1,a[i])[2]="." then b:=true else b:=false end if:
  if l<n or (l>=n and m[1..n]<>node ) then t:=insert(t,m,b) end if;
  procname(a[i],m):
  m:=s
  end do:
end proc:

t:=[""]: n:=length(node): del(tree,""); t
end proc:
 
>    tree; deletenode(tree,"EPIER"); drawtree(%);

[

[

[Maple Plot]

 

Parcours récursif en préordre de l'arbre tree , dans le sens: nœud - fils 1  - fils 2  ... - fils n .

>    preorder:=proc(tree::list)
local path, disp;

disp:=proc(t::list)
 local k;
 path:= path,op(1,t);
 for k from 2 to nops(t) do
   procname(t[k]);
 end do;
end proc;
      
path:=NULL; disp(tree); path
end proc:
 
>    tree;

[

>    preorder(tree);

La procédure récursive find permet de trouver word  dans l'arbre tree : elle retourne true  (ou false ) suivant que word  a été (ou non) trouvé dans tree .

>    find:=proc(tree::list,word::string)
local letter,i;
if word="" and op(1,tree)[2]="." then return true end if;
letter:=word[1];
for i from 2 to nops(tree) do
  if op(1,tree[i])[1]=letter then return procname(tree[i],word[2..length(word)]) end if
end do;
false
end proc:
 
>    find(tree,"EPI"),find(tree,"EPIE"),find(tree,"EPIER"),find(tree,"EPIERAI"),
find(tree,"JE"),find(tree,"JEU");

true, false, true, true, false, true

Procédure permettant de constituer un dictionnaire de mots à partir de l'arbre tree :

>    makedict:=proc(tree::list)
local dict,words;

dict:=proc(t::list,s::string)
local word,i;
word:=s:
for i from 2 to nops(t) do
  word:=cat(word,op(1,t[i])[1]):
  if op(1,t[i])[2]="." then words:=words,word end if;
  procname(t[i],word):
  word:=s
  end do:
end proc:

words:=NULL: dict(tree,""): [words]
end proc:
    
>    makedict(tree);

[

Second exemple à partir d'une liste triée comportant davantage de mots:

>    tree1:=[""]:
txt:=sort(["ENTRER","FIL","EGEEN","EGAL","GRASSES","EMULE","FINE","FINAL","EMUE","FILS","EGEE",
"GRASSE","FINES","EMUS","FILE","GRAS","GRAPPE","EGO","EMU","ENTREE","FINS"]);
for k in txt do tree1:=insert(tree1,k,true) od: tree1;

txt := [
txt := [

[
[

>    makedict(tree1);

[
[

>    drawtree(tree1);

[Maple Plot]

Troisième exemple à partir d'un texte-source (ici un poème de Léo Ferré):

>    txt:="La mémoire et la mer
 
La marée, je l'ai dans le cœur
Qui me remonte comme un signe
Je meurs de ma petite sœur,
de mon enfance et de mon cygne
Un bateau, ça dépend comment
On l'arrime au port de justesse
Il pleure de mon firmament
Des années lumières et j'en laisse
Je suis le fantôme jersey
Celui qui vient les soirs de frime
Te lancer la brume en baiser
Et te ramasser dans ses rimes
Comme le trémail de juillet
Où luisait le loup solitaire
Celui que je voyais briller
Aux doigts de sable de la terre

Rappelle-toi ce chien de mer
Que nous libérions sur parole
Et qui gueule dans le désert
Des goémons de nécropole
Je suis sûr que la vie est là
Avec ses poumons de flanelle
Quand il pleure de ces temps là
Le froid tout gris qui nous appelle
Je me souviens des soirs là-bas
Et des sprints gagnés sur l'écume
Cette bave des chevaux ras
Au raz des rocs qui se consument
Ö l'ange des plaisirs perdus
Ö rumeurs d'une autre habitude
Mes désirs dès lors ne sont plus
Qu'un chagrin de ma solitude

Et le diable des soirs conquis
Avec ses pâleurs de rescousse
Et le squale des paradis
Dans le milieu mouillé de mousse
Reviens fille verte des fjords
Reviens violon des violonades
Dans le port fanfarent les cors
Pour le retour des camarades
Ö parfum rare des salants
Dans le poivre feu des gerçures
Quand j'allais, géométrisant,
Mon âme au creux de ta blessure
Dans le désordre de ton cul
Poissé dans des draps d'aube fine
Je voyais un vitrail de plus,
Et toi fille verte, mon spleen

Les coquillages figurant
Sous les sunlights cassés liquides
Jouent de la castagnette tant
Qu'on dirait l'Espagne livide
Dieux de granits, ayez pitié
De leur vocation de parure
Quand le couteau vient s'immiscer
Dans leur castagnette figure
Et je voyais ce qu'on pressent
Quand on pressent l'entrevoyure
Entre les persiennes du sang
Et que les globules figurent
Une mathématique bleue,
Sur cette mer jamais étale
D'où me remonte peu à peu
Cette mémoire des étoiles

Cette rumeur qui vient de là
Sous l'arc copain où je m'aveugle
Ces mains qui me font du fla-fla
Ces mains ruminantes qui meuglent
Cette rumeur me suit longtemps
Comme un mendiant sous l'anathème
Comme l'ombre qui perd son temps
À dessiner mon théorème
Et sous mon maquillage roux
S'en vient battre comme une porte
Cette rumeur qui va debout
Dans la rue, aux musiques mortes
C'est fini, la mer, c'est fini
Sur la plage, le sable bêle
Comme des moutons d'infini...
Quand la mer bergère m'appelle

Léo Ferré":
 
>    txt:=sort(StringTools[Split](txt," :!,.';\n")):
>    tree2:=[""]:
for k in txt do tree2:=insert(tree2,k,true) od:
>    makedict(tree2);

[
[
[
[
[
[
[
[
[
[
[
[

>    find(tree2,"fjord"),find(tree2,"fjords");

false, true

 

haut de cette page

 

 


©  - Alain Le Stang - Navigation optimisée pour une résolution 1024 x 768.