Discussion :

[Bruno13]

Bonjour à tous,

But : Je cherche à faire des regroupements de termes (mots, ou ensemble de mots) suivant leur ressemblance.

Mon problème n'est pas dans le calcul de ressemblance mais plutôt dans les deux boucles que j'effectue et qui à mon avis n'optimise pas du tout mon programme.

Hyp :
- un terme peut avoir plusieurs équivalents
- un équivalent peut se retrouver dans plusieurs groupes

J'utilise une liste d'objet, chaque objet est défini de la manière suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
KW = TObject
  Name : chaine; // Nom du terme
  Code : chaine; // Codification du terme (algo soundex)
  lKWEq : Liste de KWEq; // Liste des termes équivalents
end;
 
KWEq = TObject
  Name : chaine; // Nom du terme équivalent;
  Code : chaine; // Codification du terme equivalent (algo soudex aussi)
end;

List_KW = TList;

Et voici maintenant comment je fais mes boucles, (je n'ai pas mis la création des objets dans les boucles pour éclaircir le code) :

Une première Pass, qui n'est pas montrée ici, calcul les codes de chaque termes.

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
 
For i := 0 to List_KW-1 do
Begin
  oKW:=List_KW[i];
  For j:=0 to List_KW-1 do
  Begin
    pKW:=List_KW[j];
    IF oKW.Code = pKW.Code then
    Begin
      eqKW.Name:=pKW.Name;
      eqKW.Code:=pKW.code;
      oKW.lKWEq.Add(eqKW);
    End;
  End;
End;

Mais voilà, c'est :
1. Assez long en temps de traitement
2. Il y a de la redondance dans les résultats, c'est à dire que je retrouve plusieurs groupes ayant les mêmes équivalents (normal quoi , au vu de ma boucle)

Avez vous des conseils à me donner, ou même mieux une solution moins coûteuse en temps d'exécution.

D'avance merci à tous pour vos conseils,

Amicalement,
Bruno

[Zavonen]

Peut être indexer la liste traitée par la boucle extérieure par les codes.
Ensuite les mots clés sont regroupés par codes équivalents.
Tu parcoures ta liste de code en code et non de KW en KW si pour le premier tu rencontres un équivalent tu rajoutes TOUT le groupe (jusqu'au prochain code).
Maintenant il faut voir le temps d'indexation (au mieux nlog(n)).

[Graffito]

Une solution simple et performante consisterait à trier la liste en fonction des codes.

[SpiceGuid]

Ne me dis pas que personne ne t'as jamais conseillé d'allez voir du côté de Union-Find

La structure de donnée ressemble à un arbre d'héritage (c'est-à-dire un arbre n-aire inversé). Algorithmiquement il y a une optimisation dite de compression des chemins.

Voir le chapitre IX. Le type partition du cours de Denis Lapoire.