Boolesche Suche erklärt

29

Meine Mutter besucht einen Online-Kurs, um eine Art Bibliothekarin zu werden. In diesem Kurs werden Boolesche Suchen behandelt, damit sie Datenbanken effizient durchsuchen können. Sie hat jedoch eine Frage, die in etwa so aussieht:

Die Suche "x ODER y" ergibt 105 000 Treffer, während eine Suche nach nur x 80 000 Treffer ergibt und eine Suche nach nur y 35 000 Treffer ergibt. Warum ergibt die Suche "x ODER y" 105 000 Treffer, wenn die kombinierte Einzelsuche 115 000 Treffer ergibt?

Für mich klang das seltsam, also habe ich das selbst getestet, mit den Worten Speck und Sandwich .

  • Nur Speck lieferte 179 000 000 Ergebnisse
  • Nur Sandwich ergab 312 000 000 Ergebnisse
  • Speck oder Sandwich gab 491 000 000 Ergebnisse

Aber für mich summiert sich: 179 000 000 (Speck) + 312 000 000 (Sandwich) = 491 000 000 (Speck ODER Sandwich)

Warum kann eine ODER-Abfrage zu weniger Treffern führen als beide Einzelabfragen zusammen?

sets counting sch
quelle
22
Sie haben einen blauen Hund, eine blaue Katze und eine rote Katze. NUMBER OF (BLUE) = 2, NUMBER OF (CAT) = 2, aber NUMBER OF (BLUE oder CAT) = 3, nicht 4.
BlueRaja - Danny Pflughoeft
11
Ich habe es versucht und 184 Millionen Ergebnisse für Speck erzielt. Ich habe es nie geschafft, nach Sandwiches zu suchen, da ich sofort gegangen bin, um mir etwas Speck zu braten.
corsiKa
15
Ich denke, das eigentliche Problem hier ist, dass Ihre Datenbank keine Specksandwiches enthält.
MooseBoys
@MooseBoys ja, das muss der Grund sein, warum sich meine Zahlen addieren, denn sie sollten es nicht, oder?
sch
3
@klskl: Wenn Sie diese Zahlen von Google erhalten, denken Sie daran, dass diese Zahlen sehr, sehr grobe Schätzungen sind. Es kann durchaus vorkommen, dass sie, um die Schätzung für "Speck ODER Sandwich" zu erhalten, nur die Zahlen summieren. Das funktioniert nur, weil die Schätzung keinerlei Genauigkeit haben muss.
BlueRaja - Danny Pflughoeft

Antworten:

62

Hinweis: Die Suche x UND y ergibt 10 000 Treffer.

Yuval Filmus
quelle
ja, aber das ist nebensächlich, die Lehrer behaupten, dass ihre Suche nach x ODER y weniger Treffer liefert als die Kombination der Treffer einer individuellen Suche nach x dann y
sch
63
Nein, darum geht es nicht. Im Gegenteil, es ist der eigentliche Punkt.
Yuval Filmus
Ich bin neu in diesem Bereich. Möchtest du etwas näher ausführen? Nach dem, was ich verstehe UND ergebe ich Ergebnisse mit beiden Wörtern, daher weniger Ergebnisse als jedes einzelne, aber was hat das mit ODER zu tun?
sch
2
Wenn AND leer ist, funktioniert OR wie ADD, andernfalls nicht. @klskl Die Information von x UND y ist entscheidend.
Evil
@YuvalFilmus Ich sehe jetzt, es ist der Punkt! (Ich war wie, Hamburger und Sandwich gibt nicht 10 000 Treffer ...) Danke
sch
93

Hier gilt das Zählprinzip Einschluss-Ausschluss .

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

Damit die Zahlen klappen, |X∩Y|

Ein Venn-Diagramm kann für jemanden überzeugender sein, der sich von der Notation einschüchtern lässt.

Venn-Diagramm

200_erfolg
quelle
4
Das ist wirklich gut, ich werde es meiner Mutter erklären, wirklich sauber, danke!
sch
3
|X∪Y.|=|X|+|Y.|-|X∩Y.||X∩Y.||X||Y.||X|+|Y.|, du hast es zweimal gezählt. Sie subtrahieren es dann, so dass es nur einmal gezählt wird.
Devsman
Die Mathematik funktioniert, und es macht Sinn, aber es stimmt nicht mit der Mengenalgebra überein, die direkt darüber liegt.
Kevin Brown
Ich erinnere mich, Venn-Diagramme gemacht zu haben, als ich 4-5 Jahre alt war. Sie sind wirklich unterschätzt. Vielen Dank, John Venn.
Pharap
1
@Pharap In der Tat verdienen solche Diagramme unsere Venneration.
Mason Wheeler
13

Dokument 1: Die Katze ist auf dem Tisch
Dokument 2: Meine Katze ist schwarz
Dokument 3: Der Hund ist unter dem Tisch
Dokument 4: Wie heißt Ihre Katze?
Dokument 5: Dies ist ein Schwarzweißfoto

Search for cat: returned documents are 1,2,4 (3 documents returned)
Search for black: returned documents are ...
Search for cat OR black: returned documents are ...

:-D :-D

Vor
quelle
3

In simple words:

Search for X gives you n answers.
Search for Y gives you m answers.
Search for X AND Y gives you p answers.

In searching for X OR Y, the search breaks off as soon as it finds either X or Y. So if there's an X before a Y, that Y will not be counted in searching for X OR Y. Therefore your search for X OR Y will give you n + m - p answers.

It's important to note that the results will be the same, whether you do 2 searches, or just one. It's just that in summing the two searches, some documents are counted twice.

frank
quelle
"the search breaks off as soon as it finds either X or Y." Doesn't this depend on implementation? An implementation could obtain all results for X, obtain all results for Y, and then combine the results in a way that eliminates duplicates.
jpmc26
@ArnabDatta What I described is most definitely not an XOR. "Eliminating duplicates" means eliminating the second copy, not all instances of that element.
jpmc26
True. I misunderstood. Removed my comment.
Arnab Datta
3

Imagine you have only one document. This is Document#1 with this:

X Y

Now imagine you have a search function that can give you all the documents based on one keyword:

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

Notice that the number of documents in both cases is 1. Now if you have a search function that gives you the number of documents that matched one or more of the keywords supplied:

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

When you add the number of documents containing X to the number of documents containing Y, this causes you to count the same document twice. In your case, this happened 10000 times as pointed out above :)

Arnab Datta
quelle