Discussion :

[vodevil]

Bonjour , je travaille sur un petit moteur de recherche pour mon site, et j'aimerai qu'il soit le plus précis possible j'ai déjà conçue le bot et l'indexeur mais je n'arrive pas a trouver un méthode potable pour calculer le poids des mots les paramètres dont je dispose sont :

> Le nombre de mots dans la page
> Le poucentage de chaque mot (dans se page de provenance)
> Le nombre d'occurence de chaque mot
> Présence ou non dans les headers de page : titre , description, keywords
> Présence ou non dans les liens interne a mon site

Je cherche depuis près d'une semaine une façon de faire un algo avec tout sa qui soit le meilleur possible , j'ai lue des doc sur google et comment il fesait pour calculer sa mais j'ai rien trouvé de très concluants (dise tous un truc différent).

Si vous avez une idée meme farfelue je suis preneur

Merci de votre aide

[nako]

Salut, c'est sûr que google va pas donner son algorithme de ranking !
T'imagines les conséquences économiques ?
D'ailleurs, il me semble qu'ils le changent régulièrement.

Bref, si c'est pour ton propre site, le mieux est de procéder de manière empirique. Tu attribues à chacun de tes paramaètres un poid, de façon à former une combinaison linéaire. Et puis tu testes !

L'avantage, c'est que c'est ton site, que c'est toi qui l'a programmé, alors tu sais comment tu l'as conçu et surtout comment tu l'as référencé !
De sorte, tu dois savoir intuitivement l'importance d'un mot dans le titre, par rapport à sa présence dans le texte.

Bon courage.
a+

[Strab]

Voici une formule trouvée (essentiellement en bidouillant) par une personne très renommée dans ce domaine, mais dont j'ai oublié le nom :

Soient :
- m le mot cherché.
- x(m) le nombre de documents qui contiennent m
- y(m,d) le nombre d'occurences du mot m dans le document d
- n le nombre de documents indexés
- t(d) la taille d'un document

On note :
- tf(m,d) = log(y(m,d))/log(t(d))
- idf(m) = - log(x(m)/n)

Alors, le scrore d'un document pour une recherche sur le mot m est :
score(m,d) = tf * idf

Il existe d'autres façons de calculer tf et idf, tu devrais en trouver pas mal sur le net. tf signifie Term Frequency et idf Inverted Document Frequency.

Cette méthode n'utilise pas les propriétés des pages web comme les headers et les liens, mais elle devrait déjà donner quelque chose de pas mal.

[Graffito]

Bonjour,

Dans la pratique, les différentes formules (comme celle indiquée par Strab) donnent des résultats assez peu différents dans la mesure où :
- les mots "pertinents" (ceux que l'on trouve dans peu de documents) ont une pondération forte,
- les mots "outils" (que l'on retrouve partout) ont une pondération faible.

Les vrais améliorations à apporter se trouvent :
- dans les aspects de synonymie (mines=mine, zéro=ZERO, envellope=enveloppe=ENVELOPE, travail=boulot),
- dans l'élimination des mots vides (article, auxiliaire, adverbe courant),
- dans le traitement des co-occurences (mots situés dans la même phrase),
- dans la présentation du résultat : il est très sympa pour l'utilisateur de classe les réponses par les ensembles de mots communs à la question.

[cryptorchild]

Bonjour,

Dans la pratique, les différentes formules (comme celle indiquée par Strab) donnent des résultats assez peu différents dans la mesure où :
- les mots "pertinents" (ceux que l'on trouve dans peu de documents) ont une pondération forte,
- les mots "outils" (que l'on retrouve partout) ont une pondération faible.

Les vrais améliorations à apporter se trouvent :
- dans les aspects de synonymie (mines=mine, zéro=ZERO, envellope=enveloppe=ENVELOPE, travail=boulot),
- dans l'élimination des mots vides (article, auxiliaire, adverbe courant),
- dans le traitement des co-occurences (mots situés dans la même phrase),
- dans la présentation du résultat : il est très sympa pour l'utilisateur de classe les réponses par les ensembles de mots communs à la question.

Connais tu un algo qui permette de calculer les co-occurences, je cherche désespérement un algo comme sa , ca je n'arrive pas as en faire un (c pas drole )

thanks

[Graffito]

Bonjour,

Pour les co-occurences, l'approche la plus simple consiste lors de la recherche ou de l'indexation de considérer la phrase ou le paragraphe comme un sous-document et de garder le n° de la phrase dans le document avec chaque mot (une autre option consisterait à conserver la position du mot dans le texte, par exemple caractère 823 du texte).

Cette approche est évidement plus gourmande en resources que de compter simplement le nombre de mots dans le document puisqu'un aura pour chaque occurence le n° de phrase.

Lors de la pondération des réponses, il faudra regarder si dans les doc retenus des phrases comportent plusieurs mots de la question (ou si pour chaque mot de la question, il y a une position qui est proche de celle d'un autre mot de la question).

La technique phrase est à peine plus compliquée à implémenter, mais un découpage logique du texte permettra d'afficher la ou les phrases "pertinentes" du document, un peu comme google.

[vodevil]

J'ai pensé a différente formule mais elle ne rime a rien du genre

Code :

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

1
2
Ra = (densité*nombre_total_mot_dans_doc)/(occurence)
Ra = Racine carre[ Ra ];

[vodevil]

Je dispose d'un nouvelle info sur les page je peut maintenant savoir le nombre de lien pointant vers elle
J'ai donc comme paramètres

Code :

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

1
2
3
4
5
6
> Le nombre de mots dans la page 
> Le poucentage de chaque mot (dans se page de provenance) 
> Le nombre d'occurence de chaque mot 
> Présence ou non dans les headers de page : titre , description, keywords 
> Présence ou non dans les liens interne a mon site
> Nombre de lien pointant vers elle

Bref, si c'est pour ton propre site, le mieux est de procéder de manière empirique. Tu attribues à chacun de tes paramaètres un poid, de façon à former une combinaison linéaire. Et puis tu testes !

L'avantage, c'est que c'est ton site, que c'est toi qui l'a programmé, alors tu sais comment tu l'as conçu et surtout comment tu l'as référencé !
De sorte, tu dois savoir intuitivement l'importance d'un mot dans le titre, par rapport à sa présence dans le texte.

Le problème c'est que je compte en faire un site communautaire avec des articles et tout le taitouin y'aura donc plusieur "admin" du coup je ne peut pas faire comme tu dit.

Je sais pas si sa compte mais j'utilise un index inversé

Chaque mot pointe vers une page ou il a un poids donné

guitare -> id : 112 -> musique.htm

par exemple en simplifiant.

Pour le truc du pagerank heu j'ai trouvé quelque truc sur le net que j'ai repris mais le calcul du poids d'un mot me pose vraiment problème

[Graffito]

Bonjour,

Tu peux utiliser la formule proposée par Trab avec une généralisation consistant à considérer que le nombre d'occurences d'un mot dans une page est un nombre réel (et non un entier). A partir ce là, il suffit d'attribuer (empiriquement) un coefficient multiplicateur d'occurences pour les mots des headers.

Idem en fonction des liens, on attribue un coefficient multiplicateur sur tous les mots de la page en fonction des liens de la page.

[vodevil]

Voici une formule trouvée (essentiellement en bidouillant) par une personne très renommée dans ce domaine, mais dont j'ai oublié le nom :

Soient :
- m le mot cherché.
- x(m) le nombre de documents qui contiennent m
- y(m,d) le nombre d'occurences du mot m dans le document d
- n le nombre de documents indexés
- t(d) la taille d'un document

On note :
- tf(m,d) = log(y(m,d))/log(t(d))
- idf(m) = - log(x(m)/n)

Alors, le scrore d'un document pour une recherche sur le mot m est :
score(m,d) = tf * idf

Il existe d'autres façons de calculer tf et idf, tu devrais en trouver pas mal sur le net. tf signifie Term Frequency et idf Inverted Document Frequency.

Cette méthode n'utilise pas les propriétés des pages web comme les headers et les liens, mais elle devrait déjà donner quelque chose de pas mal.

J'ai une question peut être stupide mais quand tu dit t(d) taille d'un document tu entenf quoi par la ? le nombre total de mot du document ?

[Graffito]

Bonjour,

Oui, il s'agit bien du nombre de mots du documents (sauf mots "vides" non indexés comme article, ponctuation, etc).

Pour compléter ma réponse précédente sur les liens, on peut envisager d'ajouter aux mots de la page, l'ensemble des mots des pages liées avec un coefficient faible par rapport aux mots du document. Si tu le fais, tu seras à ma connaissance un pionnier et je ne vois pas du tout si le résultat en sera amélioré ou parasité.

[vodevil]

Bonjour,

Oui, il s'agit bien du nombre de mots du documents (sauf mots "vides" non indexés comme article, ponctuation, etc).

Pour compléter ma réponse précédente sur les liens, on peut envisager d'ajouter aux mots de la page, l'ensemble des mots des pages liées avec un coefficient faible par rapport aux mots du document. Si tu le fais, tu seras à ma connaissance un pionnier et je ne vois pas du tout si le résultat en sera amélioré ou parasité.

Ah carrément , sinon existe il unes ou des bases de données de mots "vides" j'ai récupéré la liste de windows et sur un ti moteur en php que j'avais pompé il y'a quelque années mais bon c'est peut-être pas suffisant

[Graffito]

Bonjour,

J'ai arrété de travailler sur les interogations en langage naturel bien avant qu'internet n'existe. Je ne sais pas où récupérer des listes de mots vides.

Mais, aucune importance si la liste de mots vides est incomplète : les mots vides auront en principe une pondération faible sur un gros corpus de documents.

[vodevil]

oki donc ché moi sa donne

Code :

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

1
2
3
4
$tf = (log($occurence*$densite))/(log($#tablo+1));
$idf = log(($doc/$docindex));
 
$p = $tf * $idf;

si je met les mots des autres doc sa fait empiriquement:

Code :

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

1
2
tf(m,d) = log(y(m,d))+log(y'(m',d'))...+log(y'(m',d')/log(t(d))
idf(m) = log(x(m)/n)

donc je vais tester tou sa


voici un ti script de simulation en perl :

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
59
#!/usr/bin/perl -w
use strict;
 
my $text = "ma Maison est en chien google google";
 
#===================================================================#
#                                Calcul                             #
#===================================================================#
 
my @tablo = split ' ',$text;
my %occurence = &calcul_occurence(\@tablo);
 
my %res = res($#tablo, %occurence);
 
my $d = \%res;
 
foreach my $ky (sort keys %$d) {
 my $poid = (log($d->{$ky}->[1]*$d->{$ky}->[2]))/((log($#tablo+1))/600)*(log(17));
 print "$d->{$ky}->[0] apparait $d->{$ky}->[1] fois et sa densité est de $d->{$ky}->[2] %\n";
 print "Poid => $poid\n";
}
 
 
#===================================================================#
#                      Affichage des résultats                      #
#===================================================================#
 
sub res {
my %hash;
my $i = shift;
my %occ = @_;
foreach my $word(keys(%occ)){
   my $densite = ($occ{$word}*100)/($i+1);
 # print "$word apparaît $occ{$word} fois et sa densité est $densite%.\n";
 push @{ $hash{"$word"} }, "$word", "$occ{$word}", "$densite";
 }
 return %hash;
}
 
 
#===================================================================#
#                  Calcul du nombre d'occurence(s)                  #
#===================================================================#
 
sub calcul_occurence(){
   my %occur = ();
   my $tablo = $_[0];
 
   foreach my $word (@$tablo){
      if (! $occur{$word}){
         $occur{$word} = 1;
      }
      else {
         $occur{$word}++;
      }
   }
 
   return %occur;
}

les résultats produit sont

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
Maison apparait 1 fois et sa densité est de 14.2857142857143 %
Poid => 2323.10346670766
 
chien apparait 1 fois et sa densité est de 14.2857142857143 %
Poid => 2323.10346670766
 
en apparait 1 fois et sa densité est de 14.2857142857143 %
Poid => 2323.10346670766
 
est apparait 1 fois et sa densité est de 14.2857142857143 %
Poid => 2323.10346670766
 
google apparait 2 fois et sa densité est de 28.5714285714286 %
Poid => 3534.15661362348
 
ma apparait 1 fois et sa densité est de 14.2857142857143 %
Poid => 2323.10346670766

Qu'en pensez vous ?

[vodevil]

J'ai un problème avec

- x(m) le nombre de documents qui contiennent m

je suis entrain de mettre en oeuvre l'algo mais ce paramètre me tracasse car il faut savoir que la taille de la db ne serapas fixe du coup, les fichiers indexé ne serons pas tous a égalité d'autant que si mon ti projet marche les mise a jour de la base de donnée serons assez vois meme très fréquente cela ne risque t'il pas de poser problème ????

[Graffito]

Bonjour,

Je ne comprends pas bien quel est le problème.
Pourrais-tu reformuler la question ?

Lorsque l'on crée l'index (en batch dans une base de donnée ou dynamiquement en mémoire), on connait pour chaque mot différent tous les documents dans lesquels ces mots apparaissent.

Code :

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

1
2
3
Exemple
"BOULE"  : D1, D7, D437       => x(BOULE)=3
"CARRE" :  D1, D2, D90, D789  => x(CARRE)=4

La gestion de l'index doit permettre de mettre la liste des documents associés à chaque mot.

2 solutions :
1) solution Base de donnée classique, on met les toutes les relations,

Code :

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

1
2
3
4
5
6
  exemple :
    BOULE : D1
    BOULE : D2
    BOULE : D437
    CARRE : D1
    ...

2) solution ad-hoc

Code :

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

1
2
    exemple A : Champ binaire de longueur variable avec la liste de tous les doc qui contiennent le mot.
    exemple B : si le nombre de documents est borné, chaine de M bits (M étant le nombre max de documents) avec bit N à 1 ou 0 si le document N contient le mot ou non.

[vodevil]

En fait voila dans la formule que propose Strab x

Code :

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

(m) est le nombre de document qui contienne le mot M

dont je cherche a évaluer le poid , le problème qui mais venue c'est que si j'ai disont :

Code :

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

1
2
Au moment ou j'évalue une page A , M est dans 14 documents,
 et qu'après j'évalue une page B, M est dans 15 documents

Je pense peut-être a tord que sa risque de posé problème


Effectivement j'ai vue le problème avec ma DB je suis entrain de corriger sa

[Graffito]

Bonjour,

Le problème vient du fait que l'indexation doit être faite d'abord :
on construit pour chaque mot la liste de l'ensemble des documents qui le contiennent.

A la fin de cette indexation (et non en cours d'indexation), on a le nombre de doc à utiliser dans la formule.

[vodevil]

Bonjour,

Oui, il s'agit bien du nombre de mots du documents (sauf mots "vides" non indexés comme article, ponctuation, etc).

Pour compléter ma réponse précédente sur les liens, on peut envisager d'ajouter aux mots de la page, l'ensemble des mots des pages liées avec un coefficient faible par rapport aux mots du document. Si tu le fais, tu seras à ma connaissance un pionnier et je ne vois pas du tout si le résultat en sera amélioré ou parasité.

J'ai repris le développement de mon portail, le moteur de recherche fonctionne parfaitement pour l'instant. Je voudrais tester l'idée que tu énonce ci-dessus mais pourrais tu être plus précis sur comment calculé ce fameux coefficient, sa fait bien deux semaines que je me casse la tète dessus et je n'entrevoie pas d'issue a apart ajouter un coefficient statique mais sa risque de pas etre très fiable

[Graffito]

Bonjour,

Il faut vraiment faire des essais à partir d'un coefficient statique (je dirai entre 0,10 et 0,25) et voir le résultat.

On peut aussi imaginer de multiplier ce coefficient par une fonction croissante de t(doc_lié)/t(doc).

Le plus difficile risque d'être l'évaluation de la qualité du moteur pour chaque variante....