Explication de la recherche booléenne

29

Ma mère suit un cours en ligne afin d'être une sorte de bibliothécaire, dans ce cours, ils couvrent les recherches booléennes, afin qu'ils puissent rechercher des bases de données efficacement, cependant, elle a reçu une question ressemblant à ceci:

La recherche «x OU y» donnera 105 000 résultats, tandis que la recherche de x seulement donnera 80 000 résultats, et une recherche pour seulement y obtiendra 35 000 résultats. Pourquoi la recherche "x OU y" donne-t-elle 105 000 visites, alors que les recherches individuelles combinées donnent 115 000 visites?

Pour moi, cela semblait étrange, alors je l'ai testé moi-même, en utilisant les mots bacon et sandwich .

  • Seul le bacon a donné 179 000 000 résultats
  • Seul le sandwich a donné 312 000 000 résultats
  • bacon OU sandwich a donné 491 000 000 résultats

Mais pour moi ça s'additionne: 179 000 000 (bacon) + 312 000 000 (sandwich) = 491 000 000 (bacon OU sandwich)

Pourquoi une requête OR pourrait-elle entraîner moins de hits que les deux requêtes individuelles combinées?

sets counting sch
la source
23
Vous avez un chien bleu, un chat bleu et un chat rouge. NOMBRE DE (BLEU) = 2, NOMBRE DE (CAT) = 2, mais NOMBRE DE (BLEU ou CAT) = 3, pas 4.
BlueRaja - Danny Pflughoeft
11
J'ai essayé, j'ai obtenu 184 millions de résultats pour le bacon. Je n'ai jamais réussi à chercher des sandwichs, car je suis immédiatement parti pour me faire frire du bacon.
corsiKa
15
Je pense que le vrai problème ici est que votre base de données ne contient aucun sandwich au bacon.
MooseBoys
@ MooseBoys ouais, ça doit être la raison pour laquelle mes chiffres s'additionnent, car ils ne devraient pas, non?
sch
3
@klskl: Si vous obtenez ces chiffres de google, gardez à l'esprit que ces chiffres sont des estimations très très approximatives. Il se pourrait très bien que, pour obtenir l'estimation pour "bacon OU sandwich", ils additionnent simplement les chiffres. Cela ne fonctionne que parce que l'estimation n'a pas besoin d'avoir une quelconque précision.
BlueRaja - Danny Pflughoeft

Réponses:

62

Astuce: La recherche x ET y donnera 10 000 résultats.

Yuval Filmus
la source
oui, mais ce n'est pas la question, les enseignants affirment que leur recherche x OU y donne moins de résultats que de combiner les résultats de la recherche individuelle x puis y
sch
63
Non, ce n'est pas hors de propos. Au contraire, c'est le point lui-même.
Yuval Filmus
Je suis nouveau dans ce domaine, vous voulez élaborer? D'après ce que je comprends ET donnera des résultats avec les deux mots en eux, donc moins de résultats que chacun individuellement, mais qu'est-ce que cela a à voir avec OU?
sch
2
Lorsque AND est vide OU fonctionne comme ADD, sinon ce n'est pas le cas. @klskl les informations de x ET y sont cruciales.
Evil
@YuvalFilmus Je vois maintenant, c'est le point! (J'étais genre, un hamburger ET un sandwich ne donne pas 10 000 hits ...) merci
sch
93

Le principe de comptage qui s'applique ici est l' inclusion-exclusion .

|X∪Y|=|X|+|Y|−|X∩Y|

|X∩Y|

Un diagramme de Venn peut être plus convaincant pour quelqu'un qui peut être intimidé par la notation.

Diagramme de Venn

200_success
la source
4
C'est vraiment bien, je vais l'utiliser pour expliquer à ma mère, vraiment propre, merci!
sch
3
|X∪Y|=|X|+|Y|−|X∩Y||X∩Y||X||Y||X|+|Y|
Devsman
Les mathématiques fonctionnent, et cela a du sens, mais cela ne correspond pas à l'algèbre définie juste au-dessus.
Kevin Brown
Je me souviens avoir fait des diagrammes de Venn quand j'avais 4-5 ans. Ils sont vraiment sous-estimés. Merci John Venn.
Pharap
1
@Pharap En effet, de tels diagrammes méritent notre Venn-ération.
Mason Wheeler
13

Document 1: Le chat est sur la table
Document 2: Mon chat est noir
Document 3: Le chien est sous la table
Document 4: Quel est le nom de votre chat?
Document 5: Ceci est une photo en noir et blanc

Recherche de chat : les documents retournés sont 1,2,4 (3 documents retournés)
Recherche de noir : les documents retournés sont ...
Recherche de chat OU noir : les documents retournés sont ...

:-D :-D

Vor
la source
3

En termes simples:

Rechercher X vous donne n réponses.
La recherche de Y vous donne m réponses.
Rechercher X ET Y vous donne p réponses.

En recherchant X OR Y, la recherche s'interrompt dès qu'elle trouve X ou Y. Donc s'il y a un X avant un Y, ce Y ne sera pas compté dans la recherche de X OU Y. Par conséquent, votre recherche de X OU Y vous donnera n + m - p réponses.

Il est important de noter que les résultats seront les mêmes, que vous fassiez 2 recherches ou une seule. C'est juste qu'en sommant les deux recherches, certains documents sont comptés deux fois.

franc
la source
"la recherche s'interrompt dès qu'elle trouve X ou Y." Cela ne dépend-il pas de la mise en œuvre? Une implémentation peut obtenir tous les résultats pour X, obtenir tous les résultats pour Y, puis combiner les résultats de manière à éliminer les doublons.
jpmc26
@ArnabDatta Ce que j'ai décrit n'est certainement pas un XOR. «Éliminer les doublons» signifie éliminer la deuxième copie, pas toutes les instances de cet élément.
jpmc26
Vrai. J'ai mal compris. Suppression de mon commentaire.
Arnab Datta
3

Imaginez que vous n'ayez qu'un seul document. Voici le document n ° 1 avec ceci:

X Y

Imaginez maintenant que vous ayez une fonction de recherche qui peut vous donner tous les documents basés sur un mot-clé:

search("X") => 1
search("Y") => 1

Notez que le nombre de documents dans les deux cas est 1. Maintenant, si vous avez une fonction de recherche qui vous donne le nombre de documents correspondant à un ou plusieurs des mots-clés fournis:

search("X", "Y") => 1

Lorsque vous ajoutez le nombre de documents contenant Xau nombre de documents contenant Y, cela vous oblige à compter le même document deux fois. Dans votre cas, cela s'est produit des 10000fois comme indiqué ci-dessus :)

Arnab Datta
la source