Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide | Shop Recherche
1475 connectés 

  FORUM HardWare.fr
  Programmation
  Python

  Recherche aide pour classe arbre des suffixe :)

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Recherche aide pour classe arbre des suffixe :)

n°2271453
bibjuju
Posté le 12-12-2015 à 20:26:39  profilanswer
 

Bonjours, je suis débutant en python et je voudrais savoir comment s'y prendre pour crée le constructeur d'un arbre des suffixe par la methode décrite dans le td.
J'y ai passer plus de 3 jours sans pouvoir arriver à quoi que ce soit :?
 
http://pdf2jpg.net/files/1fc87363837e476a69e237a00bb73618f39a4386/TD10-page-001.jpg
http://pdf2jpg.net/files/1fc87363837e476a69e237a00bb73618f39a4386/TD10-page-002.jpg
 
Merci beaucoup :) !

mood
Publicité
Posté le 12-12-2015 à 20:26:39  profilanswer
 

n°2271454
bibjuju
Posté le 12-12-2015 à 20:51:46  profilanswer
 

J'ai aussi accès à la correction de ce tp mais en le lisant c'est encore plus flou que lorsque je ne l'avais pas déjà lue..
 
la voici :
 
1) Nous allons adopter une solution qui se sert d'un tableau pour garder les
   arêtes étiquetés vers les fils. Au lieu d'exprimer les étiquettes explicitement,
   nous utiliserons la position d'une arête (= référence à  un fils) dans le tableau
   des arêtes comme son étiquette implicite.
   On pourra utiliser le code ASCII d'un caractère comme indice du tableau des fils,
   ce qui est facile mais susceptible de gâcher beaucoup de mémoire, surtout si
   l'alphabet effectivement utilisé dans le texte est réduit par rapport aux 256
   caractères de la table ASCII étendue. Un autre problème est que si notre texte
   utilise des caractères Unicode, dont le code peut consister en un entier de 16 bits
   ou plus, on aurait besoin de tableaux trop grands. Une solution à  ces deux problèmes
   consiste en créer au préalable un seul grand tableau contenant, aux positions qui
   correspondent aux caractères effectivement utilisés dans le texte, des nombres
   entiers progressifs, de 1 à  N, une sorte de codage alternatif, qui seront utilisés
   comme indices pour accéder aux tableaux des fils.
   Voici les attributs de la classe ArbreSuff:
   - profondeur, de type entier : cela nous permet de stocker la profondeur d'un noeud,
       et donc d'éviter de la recalculer à  chaque fois qu'on en a besoin ;
   - position, de type entier : position de début dans le texte du suffixe qui correspond
       au chemin de la racine à ce noeud ; on affectera la valeur 0 à  la racine (chaine vide) ;
   - parent, une référence au noeud parent, de type ArbreSuff ;
   - fils[N], un tableau de références au sous-arbres, de type ArbreSuff
 
Nous allons prévoir aussi un constructeur simple, qui prend comme argument
une référence à un ArbreSuff parent, qui nous permettra de créer des nouveaux noeuds vides.
 
ArbreSuff(ArbreSuff p)
  parent <- p
  si parent != NULL
    profondeur <- parent.profondeur + 1
  sinon
    profondeur <- 0
  position <- 0
  pour i de 1 à  N
    fils[i] <- NULL
 
2) Construction de l'arbre des suffixes
 
ArbreSuff(Texte t)
  self(NULL)                     # appel au constructeur simple, pour créer la racine
  ouvCour <- nouvelle Liste()   # liste des noeuds ouverts pour l'itération courante
  ouvCour.ajouter(self)         # au début, ouvCour ne contient que la racine
  pour i de 1 Ã  t.taille()
    c <- alphabet[t[i]]          # conversion ASCII -> code interne
    ouvSuiv <- nouvelle Liste()  # liste des noeuds ouverts pour l'itération suivante
    ouvSuiv.ajouter(self)        # la racine fait toujours partie des noeuds ouverts
    Itérateur ouverts <- ouvCour.itérateur()   # On utilise un itérateur pour parcourir la liste ouvCour
    tant que ouverts.hasNext()
      noeud <- ouverts.next()
      si noeud.fils[c] = NIL
        noeud.fils[c] <- nouveau ArbreSuff(noeud)
        noeud.fils[c].position <- i - noeud.profondeur
      ouvSuiv.ajouter(noeud.fils[c])
    ouvCour <- ouvSuiv           # on remplace par ouvSuiv la liste qui vient d'être parcourue
  # fin du constructeur, maintenant "self" est la racine de l'arbre des suffixes de t  
 
3) recherche d'un motif
 
entier rechercher(texte m)
  n <- self
  pour i de 1 à m.taille()
    c <- alphabet[m[i]]
    n <- fils[c]
    si n = NIL         # motif non trouvé
      renovoyer -1
  renvoyer n.position
  # remarque : si m.taille() = 0 (chaîne vide), la position renvoyée sera 0.


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Python

  Recherche aide pour classe arbre des suffixe :)

 

Sujets relatifs
intelligence artificielle aideMembre object statique dans classe template : souci
Aide pour commencée la programationRecherche de données excel sur 2 tableaux à la fois
aide pour finaliser un scriptLancement fonctions dont le nom est en variable dans une classe....
Moteur de recherche sur une tableAide programmation scripts / recherche FAI
Plus de sujets relatifs à : Recherche aide pour classe arbre des suffixe :)


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC / Shop HFR