IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Quelle structure de données ? Analyse des occurrences d'un trigramme


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    311
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 311
    Par défaut Quelle structure de données ? Analyse des occurrences d'un trigramme
    Bonjour,

    dans le cadre d'un projet universitaire, je dois implémenter un programme me permettant de dénombrer le nombre d'occurrences d'un trigramme.
    Pour vous aider à comprendre, voici un petit exemple :

    "Salut, comment ça va? Bof j'ai besoin d'aide."
    donne en résultat :
    Salut|comment|ça|1
    comment|ça|va|1
    ça|va|bof|1
    va bof||j'ai|1
    etc.
    (on ne s'inquiète pas de la ponctuation)

    En gros, nous avons mot1|mot2|mot3|nombreOccurenceDansLeTexte

    Après avoir lu ce topic qui ressemble à mon problème : http://www.developpez.net/forums/d70...odele-langage/, j'ai implémenter une première solution utilisant une simple liste de trigrammes (en java).
    Malheureusement, et c'est le but de la manoeuvre, il faut pouvoir analyser et stocker des données de "gros" textes. Nous avons par exemple, un fichier de 80 Mo.
    Mon implémentation en liste montre que ma structure de données ne peut pas gérer cette masse de données. (exception heap stack ou non lancement du programme) Car, effectivement, sur une petite texte de 200 mots, ça fonctionne bien...

    J'aimerais savoir si vous avez une idée de structure ? En sachant qu'on ne supprimer jamais dans l'implémentation.
    J'ai pensé à plusieurs structures que l'on a vu en cours :
    - les AVL, où la complexité de la recherche pourrait permettre de gagner du temps... (j'utiliserais dans ce cas l'ordre alphabétique du mot1 puis du mot2 et du mot3 pour le stockage)
    - les skip listes
    et après quelques recherches google - les arbres 2 3 4 (même si je ne connais pas bien cette structure)

    Qu'en pensez vous ? Avez vous besoin de plus d'explications ?

    Merci par avance.
    Cordialement,
    Tid.

  2. #2
    Membre émérite
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mars 2009
    Messages : 552
    Par défaut
    Bonjour,

    80 Mo avec les mémoires qu'on a, c'est pas énorme. Ensuite, il faut conserver uniquement ce qui est utile dans ta mémoire. Là, il vient deux solutions :

    Brutale :

    Tu fais un vecteur de Trigramme où tu réalises à mesure le compte.
    Le trigramme est alors représenté par une classe :
    Trigramme :
    - mot1 : String
    - mot2 : String
    - mot3 : String
    - nbr_occurence : Integer

    Un peu plus fine :

    Tu fais un vecteur de mot et tu représentes comme un Trigramme :
    -pt_mot1 : Integer //position du mot1 dans le vecteur de mots
    -pt_mot2 : Integer
    -pt_mot3 : Integer
    -nbr_occurence : Integer

    La deuxième méthode est pas très compliquée, moins gourmande en mémoire, et devrait permettre des recherches plus rapide...

    bye

  3. #3
    Membre éclairé
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    311
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 311
    Par défaut
    Bonsoir,
    merci pour ta réponse.

    Ta première méthode est celle que j'ai implémenté, ça ne fonctionne pas.
    Apriori la deuxième méthode sera équivalente à la première au niveau complexité. Il me faudra quand même un vecteur de trigramme pour stocker l'ensemble des trigrammes, et la recherche, au pire des cas, sera la même.

    Même au niveau de la mémoire, au pire des cas, cela sera pareil... le pire des cas arrivant quand il n'y aura jamais deux fois le même trigramme...

    C'est pour cela que je crois qu'il ne faut pas utiliser de vecteurs (liste) mais une autre structure de données.

    @+,
    Tid.

  4. #4
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    Je ne sais pas.

    Si tes trigrammes se suivent, et que tout ce que tu as à faire est stocker les occurences, c'est assez facile.

    Tu as au maximum N mots

    Tu fais juste une mini-structure de 2 entiers par trigramme ;

    • la position du premier mot dans le total du fichier
    • le nombre d'occurences




    Dans ton exemple :

    "Salut, comment ça va? Bof j'ai besoin d'aide."
    donne en résultat :
    Salut|comment|ça|1
    comment|ça|va|1
    ça|va|bof|1
    va bof||j'ai|1
    etc.
    ça donnerait

    "Salut, comment ça va? Bof j'ai besoin d'aide."
    donne en résultat :
    0 |1
    1 |1
    2 |1
    3 |1
    etc.
    Comme ce sont des trigrammes, pour vérifier les occurences à chaque fois il te faudrait regarder si le premier mot sur lequel tu tombes là où tu en es correspond au mot indiqué par l'index dans les trigrammes déjà trouvés, puis regarder le mot suivant etc.

    L'algo d'insertion sera en O(N2) (à chaque fois il faut vérifier les indices précédents)...

    Mais en mémoire ça me semble quasiment le plus simple..

    Si vraiment on veut encore compacter la mémoire, on peut remplacer l'indice du mot par un pointeur (pourrait peut-être tenir sur un short), et le nombre d'occurences sans doute aussi (nettement plus certainement)...

    Maintenant pour accélerer l'algo d'insertion, je laisse les spécialistes...

    Mais ensuite l'algo de recherche reviendra en O(N), et même en O(N trigrammes).

  5. #5
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Comme le dit Souviron, un "trigramme" peut être représenté simplement par un index dans le texte. Reste à voir si cela est optimal en mémoire, si certains trigrammes sont très courants il y aura probablement un certain gaspillage.

    Je pense que la première chose à faire pour toi est d'établir tes priorités : quelles sont les opérations qui doivent absolument être de faible complexité ? Quelles opérations peuvent être négligées ? Combien de mémoire peux-tu utiliser ?

    Le schéma simple proposé par Souviron a des performances médiocres mais un encombrement mémoire potentiellement bon : au pire à peu près (Taille du texte + 2 * nombre de mots dans le texte) mots mémoire. On peut essayer de raffiner pour obtenir mieux en moyenne toutefois... il est difficile de croire que les trigrammes se répètent rarement dans un fichier de 80Mo par exemple.

    Un schéma alternatif pourrait être de créer un dictionnaire des mots présents dans le fichier et d'utiliser 3 pointeurs dans ce dictionnaire pour représenter un trigramme, rangé dans un hash ou une map d'une quelconque saveur. Pourvu que les fichiers soient bien du texte pur en langage naturel et supposant qu'on fasse abstraction de tout ce qui est capitalisation et ponctuation, le dictionnaire sera forcément infiniment plus petit que 80Mo et bien que chaque trigramme prenne nettement plus de place, un tel schéma aura potentiellement des performances très supérieures pour ce qui est de l'insertion et recherche.

    --
    Jedaï

  6. #6
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Un schéma alternatif pourrait être de créer un dictionnaire des mots présents dans le fichier et d'utiliser 3 pointeurs dans ce dictionnaire pour représenter un trigramme, rangé dans un hash ou une map d'une quelconque saveur. Pourvu que les fichiers soient bien du texte pur en langage naturel et supposant qu'on fasse abstraction de tout ce qui est capitalisation et ponctuation, le dictionnaire sera forcément infiniment plus petit que 80Mo et bien que chaque trigramme prenne nettement plus de place, un tel schéma aura potentiellement des performances très supérieures pour ce qui est de l'insertion et recherche.
    Sauf que je pense que si sa définition de trigramme est "3 mots qui se suivent" tu auras beaucoup plus de mal à analyser avec un dico distinct...

    Si c'est "combinaison de 3 mots", là oui ton schéma est bon..

  7. #7
    Membre éclairé
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    311
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 311
    Par défaut
    Depuis le début c'est cette parti qui semble tout me ralentir...... pourtant mon implémentation semble correct !

    La voici (c'est en java) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    	public void pass1(String s) throws IOException{
     
    		long time1 = System.currentTimeMillis();
    File f = new File("C:/Users/Emilien/Desktop/eclipseWorkspace/complexite/parts"+s+"/partfile");
    		File p = f.getParentFile();
    		if (!p.exists())
    			  p.mkdirs();
    		for (int i=0; i<256; i++){
    			File f2 = new File("C:/Users/Emilien/Desktop/eclipseWorkspace/complexite/parts"+s+"/partfile"+i);
    			if (!f2.exists())
    			f2.createNewFile();
    		}
     
    		long time2 = System.currentTimeMillis();
    		System.out.println ("Durée de création des fichiers: "+ Long.toString ((time2 - time1)) + " millisecondes.");
     
    //fin creation fichiers
    		BufferedReader LecteurBufferise = null;
    	    String ligneDonnee;   
    	    String Mot1="", Mot2="", Mot3="";
    		int hashCodeTrigramme=-1, octetPoidsFaible=-1;
    		boolean eof = false, debut1erMot=true, debut2emeMot=true;
    		MotMotMot m = new MotMotMot(Mot1, Mot2, Mot3);
        	ArrayList<String> part = new ArrayList<String>();
    	    try {
     
    	      //Ouverture du Fichier // le chemin est a modifier dans FileReader
    	      LecteurBufferise = new BufferedReader(new FileReader(s)); //s chemin
     
    	      while (eof != true) {
    	      //Lecture de la ligne
    	        ligneDonnee = LecteurBufferise.readLine();
    	        if (ligneDonnee != null) {
    	        	// on split chaque ligne en utilisant une regex
    	        	String[] part1=ligneDonnee.split("[ \t\n]");
     
    	        	int longueurPart1 = part1.length;
    	        	for (int i=0; i<longueurPart1; i++){
    	        		if(!part1[i].equals("")) part.add(part1[i]);
    	        	}
    	        	int longueurPart = part.size();
     
    	        	// pour chaque mot de la ligne
    	        	for (int k=0; k<longueurPart; k++ ){
     
    	        		// premier cas : on est au debut du fichier
    	        		if (debut1erMot) {
    	        			Mot1 = part.get(k);
    	        			debut1erMot = false;
    	        		}
    	        		// on est au deuxieme mot
    	        		else if (debut2emeMot) {
    	        			Mot2 = part.get(k);
    	        			debut2emeMot = false;
    	        		}
    	        		else {
    	        		// dans tous les autres cas
    	        			Mot3 = part.get(k);
    	        			m.setMot1(Mot1); m.setMot2(Mot2); m.setMot3(Mot3);
    	        			hashCodeTrigramme = m.hashCode();
    	        			octetPoidsFaible = hashCodeTrigramme&0xFF;
    	        			ecrireDansFichier(s, octetPoidsFaible, m);
    	        			Mot1 = Mot2;
    	        			Mot2 = Mot3;
    	        			Mot3= "";
    	        		}     			
    	        	}
    	        	part.clear();
    	        }
    	        else {
    	          eof = true;
    	        }
    	      }
    	    }
    	    catch (FileNotFoundException ex) {
    	      System.out.println("Fichier non trouvé !!");
    	    }
    	    catch (IOException ex) {
    	      System.out.println("Erreur lecture ligne fichier !!");
    	    }
    	    finally {
    	      try {
    	        LecteurBufferise.close();
    	      }
    	      catch (IOException ex1) {
    	        System.out.println("Erreur fermeture fichier !!");
    	      }
    	    }
    	}
     
    public void ecrireDansFichier(String s, int numFichier, MotMotMot trig) throws IOException{
    		PrintWriter sortie =  new PrintWriter(new BufferedWriter(new FileWriter("C:/Users/Emilien/Desktop/eclipseWorkspace/complexite/parts"+s+"/partfile"+numFichier, true)));
    		sortie.println(trig); 
    		sortie.close();
    	}
    Je ne vois pas du tout ce qui peut clocher...
    Le pire c'est que depuis le début, je n'ai pas beaucoup changer la structure de cette lecture du fichier

    [EDIT] Après 2 h de traitement du programme sur le fichier des 22 livres, je l'arrête...... J'comprends vraiment pas...

  8. #8
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Bon déjà ouvrir/refermer un fichier à chaque écriture est peu susceptible d'aider niveau vitesse... D'autre part la partie lecture est horriblement et probablement inutilement compliquée, je suspecte qu'elle est aussi fort inefficiente mais j'avoue ne pas avoir eu le courage de me plonger dans la masse...

    Note que toute ta partie lecture est globalement équivalente à :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    main = do trigramsList <- liftM (trigrams . words) getContents
     
    trigrams (a:b:ws) = go a b ws
      where
       go a b (c:ws) = (a,b,c) : go b c ws
       go _ _ _ = []
    trigrams _ = []
    en Haskell...

    Il doit donc y avoir moyen de faire plus simple en Java aussi, non ?

    --
    Jedaï

  9. #9
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Bon déjà ouvrir/refermer un fichier à chaque écriture est peu susceptible d'aider niveau vitesse...
    +1. Les I/O sont plutot long en Java, donc il vaut mieux ouvrir les 256 fichiers avant d'entrer dans la boucle principale (en sockant les BufferedWriter dans un tableau), et en les fermant tous en sortant de la boucle.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #10
    Membre éclairé
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    311
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 311
    Par défaut
    Bonsoir,

    résultat :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Programme de test.
    Durée de création des fichiers: 216 millisecondes.
    Durée de pass1 : 166882 millisecondes.
    Durée de pass2 : 91655 millisecondes.
    Et voici le trigramme vainqueur avec le plus d'occurrences : 225316|229476|164156=>155874
    :-) !
    Super, merci à tous de votre aide !
    J'ai compris et expérimenté plein de choses grâce à vous, et finalement obtenu un résultat plus que satisfaisant !

    C'était mon premier exercice sur un "projet industriel" et c'est très enrichissant !

    @+,
    Tid.

    [résolu]

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Quelle structure de données pour mon projet ?
    Par stallaf dans le forum Langage
    Réponses: 4
    Dernier message: 13/04/2010, 17h12
  2. [MySQL] Quelle structure choisir pour commentaires des articles
    Par Happy dans le forum PHP & Base de données
    Réponses: 5
    Dernier message: 17/11/2008, 16h41
  3. Quelle structure de données ?
    Par SebSplo dans le forum Développement 2D, 3D et Jeux
    Réponses: 5
    Dernier message: 27/01/2008, 03h52
  4. quelle structure de donnée par un arbre?
    Par rdh123 dans le forum C#
    Réponses: 1
    Dernier message: 31/12/2007, 15h27
  5. [C++] quelle structure de donnée utiliser pour stocker des vertices ?
    Par johnnyjohnny dans le forum Développement 2D, 3D et Jeux
    Réponses: 14
    Dernier message: 14/07/2007, 21h44

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo