Discussion :

[Bruno13]

Bonjour à tous,

Voici la suite de mes contraintes en temps d'execution pour mon programme, ici il s'agit de supprimer d'un texte les mots vides.

Je vais essayer de tout vous donner pour que l'on puisse faire les testes identiques (du moins sans tenir compte des processeurs) :

Voici le lien/texte à utiliser :
http://www.american.edu/ia/cfer/report/report.html
Voici ma fonction :

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
function DeleteEmptyWord2(CONST Texte, sLang: String): String;
var
   StringListMotsDuTexteAAusculter, lMotsVides : TStringList;
   i, j : integer;
Begin
  result:='';
  StringListMotsDuTexteAAusculter:=TStringList.Create;
  lMotsVides:=TStringList.Create;
  Try
    StringListMotsDuTexteAAusculter.Text:=Texte;
    if StringListMotsDuTexteAAusculter.Count>0 then
    Begin
      // 1. Virer les mots vides
      lMotsVides.LoadFromFile(ExtractFilePath(Application.ExeName)+'\'+cPathStopWord+'\'+sLang+'.fstw');
      for i:=0 to lMotsVides.Count-1 do
      Begin
        j :=StringListMotsDuTexteAAusculter.IndexOf(lMotsVides[i]);
        While j>=0 do
        Begin
          StringListMotsDuTexteAAusculter.Delete(j);
          j :=StringListMotsDuTexteAAusculter.IndexOf(lMotsVides[i]);
        End;
      End;
      result:=StringListMotsDuTexteAAusculter.Text;
    End;
  Finally
    lMotsVides.Free;
    StringListMotsDuTexteAAusculter.Free;
  End;
End;

Et voici la liste des mots vides :

a
about
above
after
again
against
all
am
an
and
any
are
aren't
as
at
be
because
been
before
being
below
between
both
but
by
can't
cannot
com
could
couldn't
de
did
didn't
do
does
doesn't
doing
don't
down
during
each
en
few
for
from
further
had
hadn't
has
hasn't
have
haven't
having
he
he'd
he'll
he's
her
here
here's
hers
herself
him
himself
his
how
how's
i
i'd
i'll
i'm
i've
if
in
into
is
isn't
it
it's
its
itself
la
let's
more
most
mustn't
my
myself
no
nor
not
of
off
on
once
only
or
other
ought
our
ours
ourselves
out
over
own
same
shan't
she
she'd
she'll
she's
should
shouldn't
so
some
such
than
that
that's
the
their
theirs
them
themselves
then
there
there's
these
they
they'd
they'll
they're
they've
this
those
through
to
too
und
under
until
up
very
was
wasn't
we
we'd
we'll
we're
we've
were
weren't
what
what's
when
when's
where
where's
which
while
who
who's
whom
why
why's
will
with
won't
would
wouldn't
www
you
you'd
you'll
you're
you've
your
yours
yourself
yourselves

[tourlourou]

pourrait-on voir les mots vides comme un arbre ? avec un parcours de lettre en lettre, jusqu'à arriver sur un espace (c'est sûrement réducteur, disons un caractère de ponctuation : ', ;. etc.)

[Pierre Castelain]

Comme l'a dit tourlourou, tu aurais certainement intérêt à changer de méthode et à construire un dictionnaire (au sens structure de données) pour améliorer le temps de recherche.
Mais si on considère que tu veux continuer à utiliser de simples stringlists, tu peux déjà améliorer sérieusement ton code.
1 - Au lieu de boucler sur chaque mot "vide" et rechercher une correspondance dans le texte, tu ferais mieux de faire l'inverse. Il y a de grande chance que le texte soit plus long que la liste de mots vides, la recherche ira donc plus vite dans ce sens.
2 - Une fois le premier point réglé, tu devrais trier la liste de mots vides en positionnant la propriété Sorted de la TStringList à true. Cela aura pour effet d'améliorer le temps d'exécution de la méthode IndexOf puisqu'elle va basculer sur un algorithme de recherche dichotomique.

Une dernière remarque, tu n'as pas indiqué comment tu passais du texte de la page web à une stringlist. Je présume que tu obtiens bien une liste de mots uniques (un mot par élément de la liste), sinon ton algorithme ne fonctionnera pas, à moins que je n'ai pas bien compris la situation.

[Graffito]

Bonjour,

2 petites remarques sur le IndexOf :

• reprendre le code de Tstrings.IndexOf pour faire un code IndexOf en remplaçant le CompareString par une simple comparaison de chaine,
• Trier la TstringList de mots pour que IndexOf fasse une recherche dichotomique (cf Castellain), dans ce cas il faudra reprendre le code de TstringList.find et remplacer le CompareString.

[Bruno13]

Bonjour tout le monde,

alors j'ai suivi quelques conseils, et tout d'abord :

Une dernière remarque, tu n'as pas indiqué comment tu passais du texte de la page web à une stringlist. Je présume que tu obtiens bien une liste de mots uniques (un mot par élément de la liste), sinon ton algorithme ne fonctionnera pas, à moins que je n'ai pas bien compris la situation.

Oui j'ai d'abord fait un HTMLToText où la string renvoyée est du genre :
coucou#13#10vous#13#10avez#13#10le#13#10bonjour etc...

1 - Au lieu de boucler sur chaque mot "vide" et rechercher une correspondance dans le texte, tu ferais mieux de faire l'inverse. Il y a de grande chance que le texte soit plus long que la liste de mots vides, la recherche ira donc plus vite dans ce sens.

Et là effectivement de plus de 2 minutes je passe à 7 secondes, c'est déjà trés bien, mais je suis sûr qu'avec les autres infos je vais pouvoir faire mieux :

Voici la fonction :

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
function DeleteEmptyWord2(CONST Texte, sLang: String): String;
var
   StringListMotsDuTexteAAusculter, lMotsVides : TStringList;
   i, j : integer;
Begin
  result:='';
  StringListMotsDuTexteAAusculter:=TStringList.Create;
  lMotsVides:=TStringList.Create;
  Try
    StringListMotsDuTexteAAusculter.Text:=Texte;
 
    if StringListMotsDuTexteAAusculter.Count>0 then
    Begin
      // 1. Virer les mots vides
      lMotsVides.LoadFromFile(ExtractFilePath(Application.ExeName)+'\'+cPathStopWord+'\'+sLang+'.fstw');
      lMotsVides.Sorted := True;
 
      i:=StringListMotsDuTexteAAusculter.Count-1;
      While i>=0 do
      Begin
         while lMotsVides.IndexOf(StringListMotsDuTexteAAusculter[i])>=0 do
           StringListMotsDuTexteAAusculter.Delete(i);
         dec(i);
      End;
      result:=StringListMotsDuTexteAAusculter.Text;
    End;
  Finally
    lMotsVides.Free;
    StringListMotsDuTexteAAusculter.Free;
  End;
End;

Ensuite :

* reprendre le code de Tstrings.IndexOf pour faire un code IndexOf en remplaçant le CompareString par une simple comparaison de chaine,

Alors là j'ai besoin de votre aide car, le surclassement n'est pas ma tasse de thé.

* Trier la TstringList de mots pour que IndexOf fasse une recherche dichotomique (cf Castellain), dans ce cas il faudra reprendre le code de TstringList.find et remplacer le CompareString.

Impossible pour moi de faire cela car si je trie la liste des mots de la page je perds l'ordre du texte, et si je perd l'ordre du texte je perds les co-occurrences. Par contre j'ai mis la liste des mots vides à Sorted:=True;

Merci pour vos conseils
Bruno

[Gilbert Geyer]

Bonjour,

1) A propos de la remarque de Graffito disant "reprendre le code de Tstrings.IndexOf pour faire un code IndexOf en remplaçant le CompareString par une simple comparaison de chaine" :

Bruno13 a écrit :
Alors là j'ai besoin de votre aide car, le surclassement n'est pas ma tasse de thé

... là je ne pige plus car dans ton message du 16/07/2007, 02h40 dans une autre discussion Bruno tu m'as répondu et joint le code que tu as retenu pour remplacer la version standard de IndexOf :

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
... IndexOfSL3 mais hélas chez moi je commence à croire que ce n'est pas spécialement lui qui prend du temps dans mon traitement.
Ma liste n'est pas triée donc j'ai même pu simplifier celle-ci pour mon cas :

function TKeywordList.IndexOfSL3(Item : TKeywordClass): Integer;
var      I: Integer;
begin
               Result := -1;
               I:=FItems.Count-1;
               While I>=0 do
               Begin
                  if Items[i].Name = Item.Name then
                  Begin
                     Result:= I;
                     EXIT;
                  End;
                  Dec(i);
               End;
end;

... on constate bien que CompareString a disparu au profit d'une recherche d'égalité de chaines
... en plus le choix de travailler sur des listes non triées avait été effectué dans un contexte de comparaisons de gains de vitesse sur la variante précédente d'IndexOfSL3 qui traitait aussi bien le cas de listes-triées que des listes-non-triées dont je résume ici les résultats pour ceux qui n'avaient pas participé aux autres discussions :

A titre indicatif les temps d'exécution comparatifs avec la version standard d'IndexOf, et une liste SLTexte comportant 2000 mots non accentués du dictionnaire la boucle (for i:=0 to SLTexte.count-1 do index:=IndexOfSL3(SLTexte,SLTexte[i]) ) où l'on recherche à tour de rôle l'index de chacun des 2000 mots de la liste ont été (Pentium III à 1,13 MHz) :
- Version standard d'IndexOf : 332 ms pour Sorted=False, et 13 ms pour Sorted=True.
- Version [complète dichotomique et sans CompareString] d'IndexOfSL3 : 79 ms pour Sorted=False, et 6 ms pour Sorted=True.

... mais comme entre-temps tu as opté pour la conversion des caractères-accentués en caractères-non-accentués la version complète d'IndexOfSL3 est alors efficace même avec des listes triées et surtout avec des listes triées vu le gain de rapidité par rapport à la version standard d'IndexOf qui ré-apparaît dans ton code au début de la présente discussion.

2) A propos de trier les listes :

Bruno 13 a écrit : Impossible pour moi de faire cela car si je trie la liste des mots de la page je perds l'ordre du texte, et si je perd l'ordre du texte je perds les co-occurrences.

... Suggestion : pourquoi ne pas :
1 ) mémoriser l'ordre initial des mots du texte lors du chargement de la liste-des-mots-de-la-page-non-triée avec maListe.AddObject(monMot,monObject) en mémorisant l'indice de monMot dans monObject,
2) trier ensuite la liste avec maListe.Sort;
3) confirmer cet état avec maListe.Sorted:=true; pour utiliser IndexOfSL3-version-dichotomique lors de la phase de "suppression" des mots vides où au lieu de supprimer le mot-vide avec Delete(i) tu le remplaces par une chaine vide;
4) et après cette pseudo-suppression des mots vides tu rétablis l'ordre-initial de la liste à partir des indices-initiaux-mémorisés-dans chacun des monObject en permutant les lignes vers l'ordre-initial.
A+

EDIT P.S de 15h50 : Suite du point 2) : Résultats d'un test de vitesse effectué à partir d'une liste de 2000 mots sur Pentium III 1,13 GHz :
- création d'une liste de 2000 mots avec AddObject qui mémorise l'indice-de-l'ordre-initial : mis moins de 1 ms
- tri de cette liste avec méthode Sort : 28ms
- rétablissement de l'ordre-initial par création d'une liste (sans Objects pour virer ensuite la liste-source et ses Objects) : mis moins de 1 ms
Il est donc possible de trier la liste des mots et de rétablir l'ordre du texte, pour l'histoire des co-occurrences. En bref, en combinant cette possibilité avec l'utilisation d'IndexOfSL3-version-dichotomique-sur-liste-triée-de-mots-non-accentués lors de la phase de remplacement des mots vides par des chaines vides tu serais débarassé des lenteurs d'IndexOf-version-standard.
A+