Le modèle booléen |
 |
Le modèle booléen
Le modèle booléen traite une requête comme une expression logique. Si D est un document et t un terme, on définit l’expression R(D,t) comme étant vraie si le terme se trouve dans le document et comme fausse, s’il en est autrement. Souvent, en informatique, la valeur « fausse » est représentée par l’entier 0 et la valeur « vraie », par l’entier 1.
On définit trois opérateurs ET, OU et SAUF (AND, OR et NOT en anglais) qui influent sur les valeurs booléennes :
1) x ET y : est vrai si et seulement si x et y sont vrais.
2) x OU y : est vrai si et seulement si x ou y, ou les deux, sont vrais.
3) x SAUF y : est vrai si et seulement si x est vrai et y est faux.
Ainsi, l’expression R(D,Daniel ET Lemire) sera vraie si et seulement si le document contient à la fois le mot « Daniel » et le mot « Lemire ». L’expression R(D,Daniel OU Lemire) sera vraie si le document contient le mot « Daniel », le mot « Lemire » ou les deux. L’expression R(D,Daniel SAUF Lemire) sera vraie si et seulement si le document contient le mot « Daniel », mais pas le mot « Lemire ».
Implémentation efficace d’un moteur booléen
Si le modèle booléen peut sembler simple, une implémentation vraiment efficace n’est pas si facile à produire. Supposons qu’on puisse trouver facilement et rapidement tous les documents contenant un mot donné [1]. Prenons le cas des requêtes portant sur deux mots seulement. Le calcul de « x OU y » est l’union de tous les documents contenant le mot x et de tous les documents contenant le mot y. Le calcul de « x ET y » est similaire, mais il constitue plutôt une intersection. En pratique, ces calculs sont assez rapides si l’un des deux mots est rare. Par exemple, si vous avez 12 documents qui contiennent le mot constitution et 110 qui contiennent le mot chat, pour calculer « chat ET constitution », il suffit de survoler les 12 documents contenant le mot constitution et de voir lesquels contiennent le mot chat. Par contre, si les deux mots sont très fréquents, le temps de calcul peut être plus important, surtout si on a beaucoup de documents. En général, dans des requêtes combinant plusieurs mots avec l’opérateur « SAUF », le problème est plus complexe et justifie l’utilisation d’un moteur booléen spécialisé.
[1] Dans deux semaines, nous verrons que cela est possible avec un index inversé.
