Discussion :

[étoile de mer]

Bon, visiblement, l'échantillon de donnée est d'une importance capitale pour le benchmark... j'ai des résultats intermédiaires déjà très contrastés : 11s pour l'algo "space_normalisation" et plusieurs dizaines d'heures pour l'algo "current" (celui dont tu disposes actuellement), et pas encore de données pour l'algo "first_word".

je garde l'espoir

[Philou67430]

J'ai mis à jour mon post précédent. Les résultats semblent encourageant avec "space_normalization" : avec ton exemple, j'obtiens 54s.
Par contre, je n'ai pas vérifié qu'il était fonctionnellement identique à la version actuelle (sur des plus petits échantillons, c'est correct.
L'algo "first_word" semble nettement moins bon.

J'ai ajouté un print permettant de suivre l'avancement de l'analyse du corpus, que tu devrais aussi ajouter chez toi.

[Philou67430]

J'ai lancé un benchmark avec les 1000 premières lignes du fichier corpus que tu as fournies. La version "current" devrait finir dans 27mn, je reviendrais alors d'ici 1h avec les résultats complets.

[étoile de mer]

J'ai lancé un benchmark avec les 1000 premières lignes du fichier corpus que tu as fournies. La version "current" devrait finir dans 27mn, je reviendrais alors d'ici 1h avec les résultats complets.

D'accord merci

[Philou67430]

Bon, je vais devoir revoir ma copie à nouveau, car les résultats des différentes versions sont différents, donc le code n'est pas fonctionnellement identique. Je vais donc d'abord corriger avant de donner les résultats, qui n'ont pas vraiment de sens sans cela.

[étoile de mer]

Bon, je vais devoir revoir ma copie à nouveau, car les résultats des différentes versions sont différents, donc le code n'est pas fonctionnellement identique. Je vais donc d'abord corriger avant de donner les résultats, qui n'ont pas vraiment de sens sans cela.

D'accord

[Philou67430]

En fait, je viens de me rendre compte d'une chose, suivant l'algorithme employé, le résultat peut être totalement différent.
Par exemple, la première ligne du fichier contient :

reprise de la session

et le dictionnaire contient "reprise de", "de la" et "la session".
Les différents algorithmes optimisés utilisant des tables de hashage pour un accès direct aux éléments du dictionnaire, perdent par conséquent la notion d'ordre dans le dictionnaire, et l'on peut obtenir différents résultats comme :

reprise de+la session

ou

reprise+de la+session

Il faudrait que tu (re)-précises le fonctionnement attendu, car les optimisations qu'on pourrait trouver risqueraient de modifier le comportement attendus, du fait de ce genre de subtilités.

Ceci me fait alors poser une question qui me brûlait déjà depuis un moment : quel est l'objectif "supérieur" de ce script ? Dans quel domaine travailles-tu (linguistique ? autre ?) Quel est l'objectif final du fichier résultat et à qui/comment va-t-il servir ?

[étoile de mer]

En fait, je dois bien respecter l'ordre des mots dans le fichier Dico, donc si "reprise de" apparaît en 1er donc, il faut bien faire la jointure de ces 2 mots dans le fichier texte

reprise+de la session

apres on poura pas joindre "de la" car le mot "de" est dejà collé au mot "reprise" etc...

Ceci me fait alors poser une question qui me brûlait déjà depuis un moment : quel est l'objectif "supérieur" de ce script ? Dans quel domaine travailles-tu (linguistique ? autre ?) Quel est l'objectif final du fichier résultat et à qui/comment va-t-il servir ?

Et oui je suis entrain de bosser sur un projet de recherche dans le domaine de la linguistique et plus spécialement la modélisation de langage pour la traduction automatique.

[Philou67430]

OK, donc difficile d'optimiser le fonctionnement si l'ordre du dictionnaire entre en ligne de compte. Je regarderai néanmoins la semaine prochaine s'il y a des solutions avec les idées lancées par Lolo et moi.

Pour l'instant, il me semble qu'il vaut mieux garder la version qui fonctionne, même si elle est très lente.

[Lolo78]

Sur ce genre de problèmes, les optimisations et les résultats des bench dépendent énormément des données en entrée (à la fois le texte en entrée et le dictionnaire). Une simulation avec des données différentes ou un dictionnaire partiel est vouée à donner des résultats absolument non fiables et probablement faux.

Par exemple, la première optimisation que j'ai proposée (premier mot d ela chaîne) peut fonctionner très efficacement si la vérification préalable très rapide dans un hash permet d'éliminer dans une grande majorité des cas le besoin de parcourir le tableau (opération beaucoup plus longue). Cela dépend fortement des données en entrée. Si les mots "le", "la", "un", "une" "les" et "des" constituent le premier mot possible de certaines des chaînes du dictionnaire, alors le hash renverra un résultat positif très souvent et le hash ne permettra pas de gagner beaucoup de temps.

Il faut dans ce cas envisager une autre méthode permettant dêtre plus discriminant. Par exemple stocker dans le hash les deux premiers mots, disons "le président", "la commission", etc. Mais seule une analyse assez détaillée du dictionnaire permet de prendre ce genre de décision.

En outre, si le dictionnaire change considérablement de nature, l'optimisation qui a marché dans un cas peut ne plus marcher dans un autre.

[Lolo78]

Bonsoir,

Bon, je me suis penché à nouveau sur ton cas en prenant un peu plus de temps. Notamment celui de télécharger ton dico et ton texte, et de les examiner un peu. Et aussi celui de lire de façon plus détaillée l'algo utilisé.

Hier, je disais ceci:

Il faut bien comprendre qu'en gros, chaque mot est testé contre le dictionnaire. Si ton fichier texte contient un gigaoctet, disons que ça fait peut-être 250 millions de mots (en prenant une moyenne purement arbitraire de 4 octets par mot). Si tu dois tester ces 250 millions de mots contre 10 ou 20 expressions, ça reste acceptable (ce sera long, mais on parle sans doute de quelques heures). Si le dictionnaire contient 10.000 ou 20.000 lignes, là on est complètement hors des clous: quelques heures, c'est gérable, quelques milliers d'heures, ça ne l'est plus.

Après avoir téléchargé les données que tu as mises à disposition, je me rends compte que j'étais en fait très très optimiste sur la taille de ton dictionnaire. Je pensais à 10.000 ou 20.000 lignes, il en a en fait plus d'un million et demi. Là, on ne parle plus de quelques milliers d'heures, mais plus probablement de plusieurs dizaines d'années, voire un bon siècle (ou deux), avec l'algorithme actuel. Si ton programme tourne toujours, tu peux aussi bien l'arrêter tout de suite, car nous serons tous les deux probablement décédés avant qu'il n'ait fini.

Je ne sais pas si tu as bien compris ce que fait l'algo de ton programme (celui qui a tourné 3 jours et tourne encore si tu ne l'as pas interrompu), mais, en gros, il fait ceci. Il charge le dico en mémoire après avoir formaté son contenu (ici, pas de problème); pour chaque ligne de ton fichier de quelques gigaoctets (disons, à la louche environ 50 à 100 millions de lignes), il la compare avec le tableau d'un million et demi d'entrées de ton dico. Tu te retrouves avec une explosion combinatoire dans les grandes largeurs. Il faut absolument changer d'algorithme. En gros, en terme de nombre d'opérations "élémentaires", il faut multiplier 100 millions de lignes par 1,5 million d'entrées dans le dictionnaire. Oublions.

Comme je présupposais dans mon post précédent, l'idée de la première optimisation que j'avais proposée est également à exclure: même si tu divises par 50 ou 100 une durée d'exécution d'un siècle, c'est toujours trop long.

Il faut un gain bien plus important. J'ai remarqué que ton dictionnaire semblait avoir systématiquement deux mots par ligne. Je pense qu'il faut donc constituer un hash de paires de mots. C'était probablement ce à quoi pensait Philou quand il parlait de "normalisation". Donc, je pense charger ton dictionnaire dans un hash de "paires de mots" (les deux mots de chaque ligne séparés par un caractère, par exemple un espace). Ensuite il faut lire ton fichier texte par paires de mots et, pour chaque paire de mots existant dans le hash, faire la substitution voulue. Compte tenu de mon expérience sur des problèmes ayant des complexités similaires (le terme complexité ayant ici un sens technique ne voulant pas dire difficulté, mais signifiant en simplifiant une mesure du nombre d'opérations à réaliser pour résoudre un gros problème informatique), j'ai tout-à-fait confiance que ce mécanisme peut conduire à une durée de traitement tout-à-fait raisonnables (disons quelques heures, mais c'est juste un vague ordre de grandeur, il faut tester pour savoir vraiment, on verra bien quand on y sera).

Cela dit, là, il est tard, je ne vais pas tarder à aller me coucher., car je bosse demain. J'espère avoir le temps de te proposer une première solution samedi ou dimanche. J'ai une idée assez précise de ce que je veux faire, il faut juste que je la mette en pratique.

[Lolo78]

Bonsoir Etoile de Mer,

je viens de faire un test avec un petit sous-ensemble de tes données.

Comme je ne pouvais pas charger en mémoire l'ensemble de ton dictionnaire, j'en ai pris un sous-ensemble de 100.000 lignes (soit 6,7 fois plus petit). Pour le fichier en entrée, je n'ai pris que 1000 lignes (soit 183,7 kilooctets). J'ai ajouté à ton programme un chronométrage de la partie traitement du fichier en entrée (en excluant donc la durée prise par le chargement du dico en mémoire). e programme a pris à peu près 400 secondes (exactement 396 secondes) sur mon PC. Si j'extrapole à un dictionnaire complet et à un fichier en entrée de 5 gigaoctets, cela donne une durée d'exécution de 73 millions de secondes, soit 844 jours ou 2,3 ans.

(En fait, j'ai fait non pas 1, mais 5 ou 6 tests qui confirment que mes extrapolations sont correctes: la durée d’exécution est quasi proportionnelle à la fois à la taille du dico et à celle du fichier en entrée (et donc, au produit des deux).

J'étais trop pessimiste quand je parlais de dizaines d'années (j'avais fait une erreur quand j'avais estimé le nombre de lignes du fichier en entrée: j'avais confondu le nombre de lignes et le nombre de mots). Mais l'estimation n'était pas si déconnante que cela pour autant, on parle bien d eplusieurs années de traitement.

Donc, je confirme: si tu n'as toujours pas arrêté ton programme, tu peux le faire, ça ne sert à rien de le laisser tourner.

J'espère proposer demain ou au plus tard dimanche un code alternatif utilisant la solution du hash décrite précédemment, ainsi que les durées d'exécution résultantes. Mon expérience me rend plutôt très optimiste sur le résultat.

Pour le moment, je vais faire tourner cette nuit ton programme sur un fichier en entrée nettement plus gros, pour confirmer clairement l'idée (quasi certaine, à mon avis) de proportionnalité de la durée du traitement au volume de données en entrée.

[Lolo78]

Bonjour,

voilà, j'ai fait une version utilisant des hashes, j'obtiens des durées très encourageantes.

Je suis parti du programme que tu as posté, Etoile de mer. Sur mon PC portable, je ne parviens pas à charger la totalité de ton dictionnaire en mémoire. Je n'arrive à charger qu'environ 100.000 lignes. J'ai remplacé les deux "foreach" de lecture du fichier par des "while", ce qui permet de lire ligne par ligne au lieu de monter deux fois le fichier en mémoire, cela m'a permis de charger 200.000 lignes du dico, soit un fichier de 2995704 octets (environ 1/9 du dico total, ou 11,4% du dico total).

En faisant tourner ce programme avec un échantillon des 10000 premières lignes de ton fichier en entrée, j'obtiens une durée d'exécution de 7620 secondes.

Avec mon programme utilisant un hash pour stocker le dico, la durée d'exécution n'est plus que de 4 secondes la plupart du temps (parfois 5 secondes). Il est donc environ 1900 fois plus rapide dans ces conditions. Mais le point le plus important est que la durée d'exécution du script utilisant le hash ne dépend pas (ou pratiquement pas) de la taille du dictionnaire chargé en mémoire (je l'ai vérifié avec des dictionnaires de 50.000, 100.000 et 200.000 lignes, à chaque fois, j'ai eu 4 secondes de durée d'exécution). Autrement dit, en chargeant tout le dictionnaire en mémoire, tu aurais encore à peu près une durée d'exécution de 4 à 5 secondes, alors que le programme d'origine (tableau d'expressions régulières) prendrait 9 fois plus longtemps. Ce qui veut dire qu'avec le dico entier, le gain est de l'ordre de 1900 x 9 = 17100.

Je fais régulièrement de l'optimisation de performances, et ai parfois obtenu des gains de l'ordre de 50 ou 100, une fois 300 et une fois presque 1000. Avec un gain de l'ordre de 17000, je bats de très loin mon record personnel.

Le texte de 10.000 lignes que j'ai traité en 4 secondes contient 1.705.564 octets. Un texte d'un gigaoctet devrait donc durer environ 600 fois plus longtemps, soit à peu près 2400 secondes ou 40 minutes.

Pour le fichier de 100 mégas que tu as posté et sur lequel je faisais tourner mon programme pendant que j'écrivais ce qui précède, j'obtiens en fait une durée d'exécution de 265 secondes. Donc, pour un giga, ce serait plutôt 2650 secondes (44 minutes)

Voici le code de mon programme:

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
use strict;
use warnings;
use utf8;
use feature qw(:5.10); 
my ($in, $dico_txt) = @ARGV;
die "Bad infile $in" if !-r $in;
die "Bad dicofile $dico_txt" if !-r $dico_txt;
 
# load dico
my %dico;
my $outfile = "outfile.txt";
open my $OUT, ">", $outfile or die "Can't open $outfile $!\n";
open my $DICO, "<", $dico_txt or die "Can't open $dico_txt for reading: $!\n";
# Itération sur les lignes du dictionnaire
while (my $line = <$DICO>) {
  chomp($line);
  $line =~ s/\s+/ /g;
  $line =~ s/^\s+//g;
  $line =~ s/\s+$//g;
  $dico{$line} = undef;
}
 
close $DICO;
 
open my $IN, "<", $in or die "Can't open $in for reading: $!\n";
my @word;
my $start = time; 
# Itération sur les lignes du fichier d'entrée
while (my $line = <$IN>) {
	$line =~ s/\s+/ /g; # remarque: chomp inutile car cette substitution élimine le retour à la ligne
	my @words = split /\s/, $line;
	my $max = scalar @words - 2;
	foreach my $i (0..$max) {
		my $key = "@words[$i,$i+1]"; # on examine chaque paire de mots du texte
		if (exists $dico{$key}) { # c'est un remplacement à faire
			my $remplacement = join "+", @words[$i,$i+1];
			$line =~ s/$key/$remplacement/g;
		}
	}
	print $OUT "$line\n";
}
close $OUT; close $IN;
my $duration = time - $start;
print "The programm lasted $duration seconds.\n";

Et voici un échantillon du fichier produit:

reprise+de+la+session
je+déclare+reprise+la+session+du+parlement+européen+qui+avait+été+interrompue+le+vendredi+CARD+décembre+dernier+et+je+vous renouvelle tous+mes+voeux en+espérant+que+vous+avez passé+de+bonnes vacances
comme+vous+avez+pu+le+constater+le+grand bogue de l+an+date+ne+s+est+pas+produit+en+revanche+les+citoyens+d+un+certain+nombre+de+nos+pays+ont+été+victimes+de+catastrophes+naturelles+qui+ont+vraiment+été terribles
vous+avez+souhaité+un+débat+à+ce+sujet+dans+les+prochains+jours+au+cours+de+cette+période+de+session
en+attendant+je+souhaiterais comme+un+certain+nombre+de+collègues me+l+ont+demandé+que+nous observions une+minute+de+silence pour+toutes+les+victimes+des+tempêtes notamment+dans+les+différents+pays+de l+union+européenne+qui+ont+été+touchés
je+vous+invite+à+vous lever pour+cette minute+de+silence
le+parlement debout+observe+une+minute+de+silence
madame+la+présidente+c+est+une+motion+de+procédure
vous+avez probablement appris+par+la+presse+et+par+la+télévision que+plusieurs attentats+à+la+bombe et crimes ont+été perpétrés au+sri+lanka

Voilà, je pense donc que l'utilisation d'un hash rend ce script à nouveau utilisable même pour les très gros volumes de données que tu manipules.

[Lolo78]

En fait, je dois bien respecter l'ordre des mots dans le fichier Dico, donc si "reprise de" apparaît en 1er donc, il faut bien faire la jointure de ces 2 mots dans le fichier texte

apres on poura pas joindre "de la" car le mot "de" est dejà collé au mot "reprise" etc...

Oups, je n'avais pas vu cela. Du coup, ma solution ne fonctionne pas car elle cherchait à faire précisément le contraire: toutes les substitutions possibles.



Dans ce cas, il va falloir gérer des priorités. J'entrevois la solution comme suit. Au lieu de contenir undef, chaque élément du hash contiendra sa priorité (par exemple le numéro d'ordre dans le fichier en entrée). Mais l'algo de substitution devient plus complexe car, au lieu de faire les substitutions au fur et à mesure, il va falloir faire une liste de substitutions à réaliser, les effectuer dans l'ordre des priorités et interdire celles qui feraient intervenir des chaînes déjà modifiées.

OK, j'y réfléchis et reviens vers toi.

[étoile de mer]

Merci Lolo de vouloir l'aider

[Lolo78]

Bonsoir Étoile de mer,

je pense avoir trouvé une solution. Je suis presque étonné de la facilité avec laquelle je l'ai trouvée, moins de 30 min pour coder et tester, et le programme qui semble fonctionner d'entrée de jeu, une seule erreur de compil (un bête ";" oublié) et programme semblant marcher correctement et fournir les bons résultats du premier coup (malgré l'algo et les structures de données tous deux un peu plus complexes, et malgré... l'apéro et les deux verres de vin du repas du samedi soir).

Enfin, bon, je suis peut-être optimiste sur mes capacités réelles à cette heure tardive, vérifie bien le résultat.

C'est un tout petit peu plus long (normal, le traitement est plus compliqué), mais à peine, semble-t-il.

Donc, toujours avec un dictionnaire de 200.000 lignes, j'obtiens les chiffres suivants:
- 5 secondes pour les 10.000 premières lignes du fichier en entrée
- 308 secondes (un peu plus de 5 min) pour le fichier de 100 mégas.

L'extrapolation pour un fichier d'un giga est donc de l'ordre de 51 min.

Voici le code:

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
use strict;
use warnings;
use utf8;
use feature qw(:5.10); 
my ($in, $dico_txt) = @ARGV;
die "Bad infile $in" if !-r $in;
die "Bad dicofile $dico_txt" if !-r $dico_txt;
 
# load dico
my %dico;
my $outfile = "outfile.txt";
open my $OUT, ">", $outfile or die "Can't open $outfile $!\n";
open my $DICO, "<", $dico_txt or die "Can't open $dico_txt for reading: $!\n";
# Pour toutes les lignes du dictionnaire
while (my $line = <$DICO>) {
  chomp($line);
  $line =~ s/\s+/ /g;
  $line =~ s/^\s+//g;
  $line =~ s/\s+$//g;
  $dico{$line} = $.;
}
 
close $DICO;
 
open my $IN, "<", $in or die "Can't open $in for reading: $!\n";
my @word;
my $start = time; 
# Pour toutes les lignes du fichier d'entrée
while (my $line = <$IN>) {
	$line =~ s/\s+/ /g; # remarque: chomp inutile car cette substitution élimine le retour à la ligne
	my @words = split /\s/, $line;
	my $max = scalar @words - 2;
	# Etablir la liste des substitutions à envisager sur cette ligne
	my %substitutions;
	foreach my $i (0..$max) {
		my $key = "@words[$i,$i+1]";
		if (exists $dico{$key}) {
			my $remplacement = join "+", @words[$i,$i+1];
			$substitutions{$dico{$key}} = [$key, $remplacement, $i, $i+1];
		}
	}
	# prioriser les substitutions et éliminer celles qu'il ne faut pas faire
	my %sub_faite;
	foreach my $sub (sort {$a <=> $b} keys %substitutions) {
		my ($old, $new, $rank1, $rank2) = @{$substitutions{$sub}};
		next if defined $sub_faite{$rank1} or defined $sub_faite{$rank2};
		$sub_faite{$rank1} = 1;
		$sub_faite{$rank2} = 1;
		$line =~ s/$old/$new/;
	}
	print $OUT "$line\n";
}
close $OUT; close $IN;
my $duration = time - $start;
print "The programm lasted $duration seconds.\n";

Et voici le début du fichier de résultat:

reprise de+la session
je+déclare reprise la+session du parlement+européen qui avait+été interrompue le+vendredi CARD+décembre dernier et+je vous renouvelle tous+mes voeux en+espérant que+vous avez passé de+bonnes vacances
comme vous+avez pu+le constater le+grand bogue+de l+an date ne+s est+pas produit en+revanche les+citoyens d+un certain+nombre de+nos pays ont+été victimes+de catastrophes+naturelles qui+ont vraiment+été terribles
vous+avez souhaité un+débat à+ce sujet dans+les prochains+jours au+cours de+cette période+de session
en+attendant je+souhaiterais comme un+certain nombre+de collègues+me l+ont demandé que+nous observions une+minute de+silence pour toutes+les victimes+des tempêtes notamment dans+les différents pays+de l+union européenne+qui ont+été touchés
je+vous invite à+vous lever pour+cette minute+de silence
le+parlement debout+observe une+minute de+silence
madame+la présidente c+est une+motion de+procédure
vous+avez probablement appris+par+la+presse et par la télévision que+plusieurs attentats à+la bombe et crimes ont+été perpétrés+au sri+lanka
l+une des+personnes qui+vient d+être assassinée au sri+lanka est+m kumar ponnambalam qui+avait rendu visite+au parlement+européen il y+a quelques+mois à+peine

A première vue, cela me paraît correct. Je te laisse vérifier plus en détail.

[étoile de mer]

Bonsoir Lolo
Je vous remercie pour cet enorme travail et l'effort fourni

je pense avoir trouvé une solution. Je suis presque étonné de la facilité avec laquelle je l'ai trouvée, moins de 30 min pour coder et tester, et le programme qui semble fonctionner d'entrée de jeu, une seule erreur de compil (un bête ";" oublié) et programme semblant marcher correctement et fournir les bons résultats du premier coup (malgré l'algo et les structures de données tous deux un peu plus complexes, et malgré... l'apéro et les deux verres de vin du repas du samedi soir).

Tu as de la chance, moi j'ai passé mon samedi soir au boulot devant l'ecran ...
Bref
les statistique que tu affaiche sont trop trop biens
Ya une enorme evolution,
Je vais verifier demain (là je suis crevée) les resultat et je mettrai au courant
Merci encore

[Lolo78]

Bon courage, alors, pour ctte vérif.

[Lolo78]

Bonjour,

je viens de voir qu'il y a un bug dans mon programme, un cas de figure que je n'avais pas prévu. Ce bug se manifeste quand la même paire de mots revient plusieurs fois dans la même phrase.

L'exemple est le suivant:

vous+avez probablement appris+par+la+presse et par la télévision que+plusieurs attentats à+la bombe et crimes ont+été perpétrés+au sri+lanka

Alors que, d'après les priorités du dictionnaire, on devrait avoir:

vous+avez probablement appris par+la presse et par+la télévision que+plusieurs attentats à+la bombe et crimes ont+été perpétrés+au sri+lanka

Le groupe de mots "par la" revient deux fois, du coup, la substitution ne se fait qu'une seule fois ou se fait au mauvais endroit. (En fait, on peut même dire qu'il y a deux anomalies successives dans ce cas de figure.)

J'essaierai de corriger cela dans l'après-midi.

[Lolo78]

Re-bonjour,

voilà, j'ai corrigé le problème des paires de mots venant en double.

Voici un extrait du fichier produit:

$ head outfile.txt
reprise de+la session
je+déclare reprise la+session du parlement+européen qui avait+été interrompue le+vendredi CARD+décembre dernier et+je vous renouvelle tous+mes voeux en+espérant que+vous avez passé de+bonnes vacances
comme vous+avez pu+le constater le+grand bogue+de l+an date ne+s est+pas produit en+revanche les+citoyens d+un certain+nombre de+nos pays ont+été victimes+de catastrophes+naturelles qui+ont vraiment+été terribles
vous+avez souhaité un+débat à+ce sujet dans+les prochains+jours au+cours de+cette période+de session
en+attendant je+souhaiterais comme un+certain nombre+de collègues+me l+ont demandé que+nous observions une+minute de+silence pour toutes+les victimes+des tempêtes notamment dans+les différents pays+de l+union européenne+qui ont+été touchés
je+vous invite à+vous lever pour+cette minute+de silence
le+parlement debout+observe une+minute de+silence
madame+la présidente c+est une+motion de+procédure
vous+avez probablement appris par+la presse+et par+la télévision que+plusieurs attentats à+la bombe et crimes ont+été perpétrés+au sri+lanka
l+une des+personnes qui+vient d+être assassinée au sri+lanka est+m kumar ponnambalam qui+avait rendu visite+au parlement+européen il y+a quelques+mois à+peine

On voit que la substitution se fait maintenant correctement dans la phrase sur le Sri Lanka.

L'algorithme et les structures de données sont un peu plus compliqués, mais, au final, le programme semble un peu plus rapide. (Le remplacement dans le tableau de mots d'une phrase est sans doute plus rapide que le remplacement par expression régulière dans la chaîne de caractères.)

Toujours avec un dictionnaire de 200.000 lignes, j'obtiens les chiffres suivants:
- 4 secondes pour les 10.000 premières lignes du fichier en entrée
- 253 secondes (un peu plus de 4 min) pour le fichier de 100 mégas.

L'extrapolation pour un fichier d'un giga est donc de l'ordre de 42 min.

Voici le code:

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
use strict;
use warnings;
use utf8;
use feature qw(:5.10); 
my ($in, $dico_txt) = @ARGV;
die "Bad infile $in" if !-r $in;
die "Bad dicofile $dico_txt" if !-r $dico_txt;
 
# load dico
my %dico;
my $outfile = "outfile.txt";
open my $OUT, ">", $outfile or die "Can't open $outfile $!\n";
open my $DICO, "<", $dico_txt or die "Can't open $dico_txt for reading: $!\n";
# Itération sur les lignes du dictionnaire
while (my $line = <$DICO>) {
  chomp($line);
  $line =~ s/\s+/ /g;
  $line =~ s/^\s+//g;
  $line =~ s/\s+$//g;
  $dico{$line} = $.;
}
 
close $DICO;
 
open my $IN, "<", $in or die "Can't open $in for reading: $!\n";
my @word;
my $start = time; 
# Itération sur les lignes du fichier d'entrée
while (my $line = <$IN>) {
	$line =~ s/\s+/ /g; # remarque: chomp inutile car cette substitution élimine le retour à la ligne
	my @words = split /\s/, $line;
	my $max = scalar @words - 2;
	# Etablir la liste des substitutions à envisager sur cette ligne
	my %substitutions;
	foreach my $i (0..$max) {
		my $key = "@words[$i,$i+1]";
		if (exists $dico{$key}) {
			my $remplacement = join "+", @words[$i,$i+1];
			push @{$substitutions{$dico{$key}}}, [$remplacement, $i, $i+1];
		}
	}
	my %sub_faite;
	foreach my $sub (sort {$a <=> $b} keys %substitutions) { # tri des remplacements par ordrede priorité
		foreach my $paire (@{$substitutions{$sub}}) { # plusieurs replacements possibles pour une même paire de mots
			my ($new, $rank1, $rank2) = @{$paire};
			next if defined $sub_faite{$rank1} or defined $sub_faite{$rank2}; # une substitution a déjà été faite
			$sub_faite{$rank1} = 1;
			$sub_faite{$rank2} = 1;
			$words [$rank1] = $new; # on remplace le premier mot par la paire de mots joints par un "+"
			$words [$rank2] = undef; # le second mot sera éliminé ultérieurement par le grep
		}
	}
	my $line_out = join " ", grep {defined } @words, "\n";
	print $OUT $line_out;
}
close $OUT; close $IN;
my $duration = time - $start;
print "The programm lasted $duration seconds.\n";