Discussion :

[Tidus159]

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.

[bretus]

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

[Tidus159]

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.

[souviron34]

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).

[Jedai]

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ï

[souviron34]

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..

[Tidus159]

Bonsoir,

tout d'abord, merci pour vos réponses.
J'ai essayé toute la journée d'implémenter d'une autre façon, mais ça ne fonctionne pas, en tout cas, pas sur le fichier de 250 Mo (en fait ce n'est pas 80 Mo)
J'ai pris une structure de données de type arbre rangé alphabétiquement et j'ai stocké dans cet arbre pour clef : le trigramme (les 3 mots) et pour valeur le nombre d'occurences.
Cela rame et le programme ne se finit jamais (java : exception heap out of memory).

Donc je vais essayer ta technique, souviron, mais penses tu que je doive stocker tout ce que j'ai dans le fichier dans une liste ou un tableau ? Le tableau fera alors un sacré poids... Mais au niveau de la recherche, ça semble assez lourd aussi... Imaginons que je suis au milieu E du tableau que je doivent rechercher, je vais reparcourir l'ensemble du fichier jusqu'à l'endroit E ? Et comparer les 3 mots un à un ?

Jedai, je pense que l'opération qui doit être de plus faible complexité et la recherche car elle est utilisé lors de l'insertion (d'abord on recherche puis on insère soit en insérant un nouveau trigramme, soit j'incrémente le nombre d'occurrences dans ce trigramme).
La suppression n'a pas besoin d'être implémenté, réfléchie.
Au niveau de la mémoire, l'ordre de grandeur est de < 1 Go de ram pour le programme, je pense que cela est déjà suffisant...
Dans notre cas, effectivement on ne s'intéresse pas a la ponctuation...

L'algo que j'utilise pour le moment est le suivant :

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
 
Entree : fichier txt e
Sortie : fichier txt s
 
pour chaque ligne de e
   ranger les mots separes par espace dans la liste l
   pour i de 0 a longueur l
 
       si mot1 vide et mot2 vide et mot3 vide alors mot1 = l[i]
      sinon si mot1 non vide et mot2 vide et mot3 vide alors mot2 = l[i]
      sinon si mot1 non vide et mot2 non vide et mot3 vide alors mot3 = l[i]
      si aucun mot vide
          creation d un nouveau trigramme t
          t.mot1 = mot1 
          t.mot2 = mot2
          t.mot3 = mot3
          insertion(t, dansLarbre)
          mot1 = mot2 
          mot2 = mot3
       fsi
     fpour
fpour
 
l'algo d'insertion est tres facile
    si trigramme dans arbre alors incrementer value arbre
    sinon insererDansL'arbre(trigramme)

Voyez vous un problème ?

@+,
Tid.

[bretus]

Bonsoir,

La méthode de Jedai a l'air pas mal. Au cas où, j'espère que la machine java est "débridée" (options pour l'autoriser à utiliser plus de mémoire -Xms ou -Xmx je ne sais plus).

Niveau complexité, rechercher l'égalité entre une chaîne de caractères, ce n'est pas rechercher l'égalité entre deux entiers... Il y a des opérations cachées. Souvent, il y a comparaison caractères par caractères, donc tu multiplies rapidement ton temps de calcul par un facteur 10...

Par ailleurs, si ta structure de vecteur ne tenait pas en mémoire, comment vive, comment espérer faire tenir un arbre porteur d'un ordre alphabétique?

Ensuite, chaque mot, chaîne de caractères, apparait dans 3 trigrammes successifs au minimum. Une chaîne de caractères coutent cher à doubler en mémoire => Il faut indexer ces mots sans doublons si la mémoire est rare :

Tu peux essayer de procéder comme suit :

Tableau des mots : String[N_MAX_MOTS]

1 salut
2 comment
3 ca
4 va
5 ...
(maximum : taille du texte en mémoire => 250 Mo)

Ensuite, gérer un bon vieux tableau pour tes trigrammes :

Tableau des trigrammes : Integer[N_MAX_TRIGRAMME][4]

1 2 3 1 //salut comment ca
2 3 4 1 //comment ca va
...

(En mémoire : 3*N_MAX_TRIGRAMME*(4*taille d'un entier) )

Tu vois qu'a chaque nouveau mot lu dans le texte, il faut au pire parcourir en entier le vecteur des mots... Si le mot existe, tu récupères sa position, sinon, tu l'enregistres (tiens c'est forcément un nouveau trigramme). Tu conserves les identifiants des deux mots précédents... Ensuite, tu peux comparer le triplets d'entiers à ceux représentant les trigrammes existant et là, ça coutera beaucoup moins cher...


Quand les structures de données sont complexes, qu'elles ne tiennent pas en mémoire vive, on les ramène à des tableaux pour pouvoir les fractionner et les ranger par bloc sur le disque dur (où la mémoire ne manque pas). Cela fonctionne pour celle que je te propose ci-dessus si jamais tu devais traiter des fichiers de 3Go...

En jouant sur les swaps disque <-> mémoire vive, ça serait possible de faire des choses raffinées, des classements alphabétiques, des indexations par exemple... En restant cantonné à des structures implémentées la mémoire vive, ça devient vite impossible.

Je suis septique sur la méthode de souviron34. Si j'ai bien compris, tu devras passer ton temps à relire ton fichier texte => gaspillage de temps. Un accès disque coûte très cher en temps, plus cher que de se passer du tri...

En espérant que ça t'aide
Bon courage!

ps :
- se méfier des complexités, les opérations n'ont pas toujours les mêmes durées ; Une opération peut en masquer un tas d'autre.
- se méfier des arbres et structure complexes en mémoire vive. C'est peut être pas très classe un tableau, mais c'est ce qu'une machine supporte le mieux...

[souviron34]

Voyez vous un problème ?

Oui

La liste de mots et son rangement sont inutiles

D'autre part tu doubles le temps, car l'insertion se fait bien en vérifiant si cela existe ou non...

Et tu exploses la mémoire parce que tu as : le fichier, la liste, l'arbre

[souviron34]

Je suis septique sur la méthode de souviron34. Si j'ai bien compris, tu devras passer ton temps à relire ton fichier texte => gaspillage de temps. Un accès disque coûte très cher en temps, plus cher que de se passer du tri...

Euh....

C'est pratiquement ce que tu as décrit, ce que je décris...

Je ne vois pas de différences...

Toi :

Tu vois qu'a chaque nouveau mot lu dans le texte, il faut au pire parcourir en entier le vecteur des mots... Si le mot existe, tu récupères sa position, sinon, tu l'enregistres (tiens c'est forcément un nouveau trigramme).

Moi :

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.

ps :
- se méfier des complexités, les opérations n'ont pas toujours les mêmes durées ; Une opération peut en masquer un tas d'autre.
- se méfier des arbres et structure complexes en mémoire vive. C'est peut être pas très classe un tableau, mais c'est ce qu'une machine supporte le mieux...

Je suis entièrement d'accord, c'est bien ce que je proposais...

[bretus]

souviron34, ok j'avais mal compris désolé

BN
ciao

[pseudocode]

Pourquoi ne pas simplement utiliser des codes de hashage ?

|m1|m2|m3| --> hash = Hash(|m1|m2|m3|)

Le résultat est stocké dans une grande table à 3 colonnes:
hash1,|m1a|m2a|m3a|,occurence
hash2,|m1b|m2b|m3b|,occurence
...

Et pour alléger la mémoire, on peut créer des tables séparées en fonction de la valeur du hashcode (cela permettra aussi de paralléliser les opérations):

Table_1 : 0<=hash<2^8
Table_2 : 2^8<=hash<2^16
Table_3 : 2^16<=hash<2^24
Table_4 : 2^24<=hash<2^32

Une fois les tables construites, on peut les trier par hashcode afin d'accélérer les recherches (recherches par dichotomie).

[souviron34]

oui ce serait une solution

ou ce matin j'ai pensé à :

faire une première passe à travers tout le fichier pour ne stocker que les indices de début de mot (la séparation des mots va déjà prendre du temps, pour ne pas tenir compte de la ponctuation, des espaces, etc. Donc remplacer au vol tout ce qui est ponctuation ou espaces par un NULL).

Et ensuite analyser soit à la manière de pseudocode soit à la mienne...

[Tidus159]

Bonjour,

merci pour ces réponses très claires ! Je n'avais pas saisie l'idée de souviron au départ...
Bretus m'a permis de bien comprendre la technique.
Par contre Bretus, tu proposes de stocker dans un tableau tous les mots alors que souviron tu dis que ce n'est pas recommandé de stocker tous ces mots...

Que faire ?

L'implémentation étant en java, je ne sais pas si c'est possible de stocker le début de chaque mot et apriori l'idée de Bretus semble plus facile à programmer.

Par contre, ne connaissant pas bien ce qu'est une table de hashage, je n'ai absolument pas compris la solution de pseudocode.

@+,
Tid.

[souviron34]

Par contre Bretus, tu proposes de stocker dans un tableau tous les mots alors que souviron tu dis que ce n'est pas recommandé de stocker tous ces mots...

Que faire ?

je dirais qu'il y a 2 solutions :

ou tu stockes chaque mot (en mémoire ou sur disque), et tu fais un "dico", dans l'ordre d'arrivée, sans le ranger, mais en y mettant l'indice du mot au fur et à mesure.

ou tu stockes directement les indices.

J'aurais tendance , comme j'ai dit, à transformer "au vol" tout ce qui est ponctuation, espaces, etc, en NULL, en stockant les débuts de mots par indice (pour faciliter les comparaisons après).

(l'indice est soit le numéro du mot (mais ce sera plus long de s'y retrouver), soit le pointeur dans la chaine totale).


Là tu ne crées rien de plus qu'une table d'indices, en plus du fichier original.

Et tu crées tes trigrammes en 2ième passe, en comparant.


Je laisse le soin à pseudocode d'expliquer les tables de hashage..

[Tidus159]

Bonsoir,

après implémentation de la premiere solution :
- création d'un dictionnaire des mots
- création d'un tab de 4 int pour les index et le nombre d'occu...

Le résultat est plutôt décevant sur un gros fichier... En effet, le programme tourne maintenant depuis 30 h , j'hésite à l'arrêter... Et il n'a parcouru que 1/5 du fichier texte (le fichier de 300 Mo).

(j'estime a un peu moins d'une semaine le temps d'attente pour le résultat, c'est pas très beau ! )

Ce programme fonctionne pourtant sans problème sur un petit fichier (100Ko)...

J'aimerais juste vous éclaircir un point : la ponctuation ne nous intéresse pas car les fichiers de tests n'en comporte pas, donc pas de problème de ce coté.


J'aurais un problème dans ta deuxième solution, souviron

Le stockage du pointeur sur la chaine m'obligera a reparcourir entièrement le fichier a chaque insertion de trigramme... et ça, ça semble demander beaucoup de temps. (Soit dit en passant, en plus, coté implémentation, vu qu'on doit le faire en java, je ne sais pas du tout comment gérer ce pointeur...)
Pour l'indice c'est la même chose...

Voyez vous une manière de résoudre ces problèmes ou d'alléger mon implémentation ?

Est ce que passer par un fichier plutôt que de stocker mon dictionnaire en mémoire pourrait en être une ?
-> Question en plus : la lecture sur le disque va mettre encore plus de temps qu'en ram non, ça ne va sûrement pas aider...

En espérant que vous pourrez m'aider.

Cordialement,
Tid.

[Petite question un peu hors sujet] l'ordre des if et des else peut il améliorer la rapidité d'un programme ?
Si par exemple je mets if (cas qui arrive très peu souvent)
sinon si (cas qui arrive très peu souvent)
sinon (cas qui arrive très souvent)
ça fait faire au programme quelques opérations en plus (bon dans mon cas ce ne sont que des comparaisons d'entiers => O(1)....)

[souviron34]

J'aimerais juste vous éclaircir un point : la ponctuation ne nous intéresse pas car les fichiers de tests n'en comporte pas, donc pas de problème de ce coté.

Admettons pour les tests, mais ce ne sera pas le cas dans la réalité, si ?

Là, dans tes fichiers tests, tes mots sont séparés par des espaces ?

Le stockage du pointeur sur la chaine m'obligera a reparcourir entièrement le fichier a chaque insertion de trigramme... et ça, ça semble demander beaucoup de temps. (Soit dit en passant, en plus, coté implémentation, vu qu'on doit le faire en java, je ne sais pas du tout comment gérer ce pointeur...)

Et comment fais-tu de toutes façons, quand tu arrives à 40 Mo + xx, quand tu tombes sur un mot, pour vérifier qu'il est ou n'est pas le début d'un trigramme déjà existant ?

Mais pour répondre, non tu ne reparcourerais que les trigrammes déjà existants.

[Petite question un peu hors sujet] l'ordre des if et des else peut il améliorer la rapidité d'un programme ?
Si par exemple je mets if (cas qui arrive très peu souvent)
sinon si (cas qui arrive très peu souvent)
sinon (cas qui arrive très souvent)
ça fait faire au programme quelques opérations en plus (bon dans mon cas ce ne sont que des comparaisons d'entiers => O(1)....)

Oui ça peut accélerer. Un switch aussi.



Je note 3 points :

• primo Java n'est peut-être pas le mieux pour ce genre de choses.. Il te faut quelque chose le plus léger possible qui calcule le plus vite possible. Un sous-programme ou un module d'analyse en C (ou C++, je suis pas bégueule) serait sans doute plus efficace.
  
  
• secondo, si ce que tu veux c'est juste la liste des trigammes, uniques, et si tu es sur un système unixoide, une possibilité serait (mais ça prendra un peu de temps) d'écrire dans un fichier temporaire tous les trigrammes, un par ligne, et d'utiliser ensuite l'outil sort.
  
  ça pourra se faire en mémoire, mais c'est pour ça qu'on t'indiquais des solutions avec indices, car sinon tu exploseras la mémoire.
  
  
• Par contre, pour avoir le nombre d'occurences, il n'y a pas trop le choix que de tout parcourir et de vérifier dans quelle case tu tombes...

Je crois que tu commences à comprendre les vrais problèmes industriels : ce qui est beau en théorie peut tomber sur des os techniques en pratique... Et ce qui est compliqué prend du temps..

Qui d'une manière ou d'une autre sera incompressible (temps, mémoire, disque).

J'essaierais demain sur un truc à moi , en C...

[Tidus159]

Bonsoir souviron,

tout d'abord je tiens a te rappeler que c'est un projet ;-)... Donc malheureusement, il y a beaucoup de contrainte.

De ce fait, on ne souhaite nous, pour ce projet, n'analyser que 2 textes qui ne comportent pas de ponctuation, mais effectivement, dans la réalité, il est clair qu'il faudrait la supprimer... (encore que ?)

Le langage est imposé et c'est Java. Je travaille actuellement sur windows, mais je pense que l'utilisation de commandes unix n'est pas permise.
Mais effectivement, ça aurait pu être intéressant. De toute, le principe est clair :
on a en entrée un fichier comportant un texte, en sortie un fichier comportant tous les trigrammes et leur nombre d'occurrence dans le texte.


C'est clair que c'est un casse tête...
Si dans l'industrie c'est pareil, bonjour les maux de tête ! En plus, le principe est tout bête... je n'imagine même pas quand on est dans le flou !

Citation:
Envoyé par Tidus159 Voir le message
Le stockage du pointeur sur la chaine m'obligera a reparcourir entièrement le fichier a chaque insertion de trigramme... et ça, ça semble demander beaucoup de temps. (Soit dit en passant, en plus, coté implémentation, vu qu'on doit le faire en java, je ne sais pas du tout comment gérer ce pointeur...)
Et comment fais-tu de toutes façons, quand tu arrives à 40 Mo + xx, quand tu tombes sur un mot, pour vérifier qu'il est ou n'est pas le début d'un trigramme déjà existant ?

Mais pour répondre, non tu ne reparcourerais que les trigrammes déjà existants.

Deux cas comme l'a bien fait remarqué bretus :

• Soit le mot n'apparait pas dans le tableau des mots (mon "dictionnaire"), il y a nécessairement un nouveau trigramme.

• Soit le mot apparait, 2 sous cas :
  -> soit le trigramme existe déjà => on incrémente le nombre d'occurrence
  -> soit le trigramme n'existe pas => on l'insère la fin du tableau

Pour ce qui est des if et else quand je relancerai le programme (j'hésite toujours a l'arrêter... je crois que mon pc peut le faire tourner une semaine...[par contre lors de la soutenance j'aurai l'air fin si a coté de moi quelqu'un propose une solution qui fonctionne en 15 mins !] ) je modifierai l'ordre pour gagner un peu.

Bonne nuit,
Tid.

[souviron34]

d'abord il faut être précis dans l'exposé du problème..

Tu démarres par parler d'un fichier de 80 Mo, puis 250, puis 300... Les problématiques ne sont pas forcément les mêmes..


Il faut tester progressivement. Ton truc de 30h tu peux arrêter tout de suite.

500 ko, 4 Mo, 10 Mo, 20, 40, 80, 160..

Ensuite, on pourrait (si c'est possible) avoir un exemple de ton fichier (80 déjà ça irait) ?

[Jedai]

Voici une petite solution en Haskell implémentant ma proposition (dictionnaire des mots + Map des trigrammes) :

Code Haskell :

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
module Main () where
import StringTable.Atom
import qualified Data.Map as M
import qualified Data.ByteString.Lazy.Char8 as BL
import qualified Data.ByteString as BS
import Control.Arrow
import Data.List
import Data.Ord
 
data Trigram = Tri !Atom !Atom !Atom
               deriving (Eq, Ord)
 
main = do
    input <- BL.getContents
    let trigramsMap = fromListWith' (+) . map (flip (,) 1) . trigrams . map (toAtom . toStrictBS) . BL.words $ input
    print . take 10 . reverse . sortBy (comparing snd) . map (first transcribe) . M.toList . M.filter (> 200) $ trigramsMap
 
fromListWith' :: (Int -> Int -> Int) -> [(Trigram,Int)] -> M.Map Trigram Int
fromListWith' f = foldl' (\m (k,v) -> M.insertWith' f k v m) M.empty 
 
toStrictBS :: BL.ByteString -> BS.ByteString
toStrictBS = BS.concat . BL.toChunks
 
trigrams :: [Atom] -> [Trigram]
trigrams (a:b:c:ws) = Tri a b c : go b c ws
    where
        go a b (c:ws) = Tri a b c : go b c ws
        go _ _ _      = []
 
transcribe :: Trigram -> (BS.ByteString, BS.ByteString, BS.ByteString)
transcribe (Tri a b c) = (fromAtom a, fromAtom b, fromAtom c)

Je n'ai pas particulièrement cherché à optimiser (surtout sur la Map, on pourrait trouver des structures plus appropriées) donc on pourrait facilement divisé par 2 ou 3 l'occupation mémoire et/ou le temps de calcul par un changement de représentation. Pour 10 Mo de texte pur, issue du Projet Gutenberg anglais (donc représentatif d'un langage naturel), cette solution finit en 9s chez moi et prend 125 Mo de mémoire vive. Il est important de noter que l'occupation mémoire en fonction de la taille de l'entrée avec cette solution est sublinéaire, j'ai même constaté une diminution de la taille à l'approche des 10 Mo. Le temps de calcul est statistiquement à peu près linéaire en la taille de l'entrée, théoriquement il devrait être en O(n log m).

Il semblerait que l'un des trigrammes les plus populaires de la langue de Shakespeare soit "one of the"...

--
Jedaï