Discussion :

[kevinou55]

Bonsoir a tous,
pour mon projet de fin d'etude je dois réaliser un programme qui analyse un texte et qui enregistre chaque trigramme (suite de trois mots) dans un tableau trié ainsi que le nombre d'occurences de chacun.

Le probleme est qu'il me faut également trouver un autre moyen pour stocker et gérer ces trigrammes ainsi que leur insertion et recherche pour que la complexité soit moindre.

Auriez-vous une idée ?

[Obsidian]

Bonsoir a tous,

Bonjour,

pour mon projet de fin d'etude je dois réaliser un programme qui analyse un texte et qui enregistre chaque trigramme (suite de trois mots) dans un tableau trié ainsi que le nombre d'occurences de chacun.

En quel langage ?

Comment faut-il interpréter ce texte ? Est-ce que dans « un deux trois quatre cinq six », les trigrammes doivent être « un-deux-trois » et « quatre-cinq-six », ou bien faut-il prendre en compte également « deux-trois-quatre » et « trois-quatre-cinq » ?

Le probleme est qu'il me faut également trouver un autre moyen pour stocker et gérer ces trigrammes ainsi que leur insertion et recherche pour que la complexité soit moindre. Auriez-vous une idée ?

Il faut surtout que tu sois d'abord au clair sur la manière dont il faut TRIER ces trigrammes. Est-ce qu'ils doivent être manipulés comme s'ils formaient un seul long mot ou y a-t-il d'autres considérations à prendre en compte ?

Après, je dirais : tri par insertion, liste chaînée, et fonction de hachage. Pour la recherche, tu peux utiliser une approche ordinaire par dichotomie mais si tu connais l'ensemble des signes de tes mots (des lettres ?), tu peux aussi faire plusieurs listes pour classer directement les trigrammes qui commencent par un signe donné (comme les volumes d'un dictionnaire).

[kevinou55]

Bonjour,
Il faudra que je code tout ca en java.

En effet pour "un deux trois quatre cinq six" il faudra stocker "un deux trois" et "deux trois quatre" et ainsi de suite...

Pour le stockage, il faudrait un tableau de structures ayant dans chaque case [mot1, mot2, mot3, nbOccurences]

Concernant le tri, je voudrais tout d'abord trier sur le premier mot puis le deuxième et enfin sur le troisième

il faut également tenir compte que mon prof risque d'avoir un texte de plus de 50.000 caractères pour tester l'appli.

Je recherche en fait une autre structure qu'un tableau si cela existe pour améliorer la complexité.

Merci de ton aide
Cordialement.

[Obsidian]

Cyrine a eu le même problème, ici.

Ce qu'il te faut dans un premier temps, c'est trois buffers (des String si tu travailles en Java) pour tenir trace des trois derniers mots reconnus en permanence. Pour éviter d'avoir à les faire circuler, tu fais un tableau de trois chaînes, tu comptes les mots et tu stockes toujours le mot courant dans chaine[compte % 3]. De cette manière, tu obtiens automatiquement « un-deux-trois » puis « deux-trois-quatre », etc.

Ensuite, si tu tries sur le premier mot, puis le second et enfin le troisième, il te suffit de les concaténer dans une chaîne unique de traiter celle-ci comme un mot ordinaire.

Après, tu utilises une Map, avec ton mot comme clé et le nombre d'occurence par valeur.