Wyjaśnienie wyszukiwania logicznego

29

Moja matka bierze udział w kursie internetowym, aby zostać bibliotekarką, w tym kursie obejmują wyszukiwania boolowskie, dzięki czemu mogą skutecznie przeszukiwać bazy danych, jednak pojawiło się pytanie brzmiące mniej więcej tak:

Wyszukiwanie „x OR y” spowoduje 105 000 trafień, podczas gdy wyszukiwanie tylko x da 80 000 trafień, a wyszukiwanie tylko y da 35 000 trafień. Dlaczego wyszukiwanie „x OR y” daje 105 000 trafień, gdy połączone pojedyncze wyszukiwania dają 115 000 trafień?

Dla mnie to brzmiało dziwnie, więc sam to przetestowałem, używając słów bekon i kanapka .

  • Tylko boczek przyniósł 179 000 000 wyników
  • Tylko kanapki przyniosły 312 000 000 wyników
  • kanapka z boczkiem LUB dała 491 000 000 wyników

Ale dla mnie sumuje się: 179 000 000 (boczek) + 312 000 000 (kanapka) = 491 000 000 (boczek LUB kanapka)

Dlaczego zapytanie OR może skutkować mniejszą liczbą trafień niż oba pojedyncze zapytania łącznie?

sets counting sch
źródło
22
Masz niebieskiego psa, niebieskiego kota i czerwonego kota. LICZBA (NIEBIESKA) = 2, LICZBA (KOT) = 2, ale LICZBA (NIEBIESKA lub KOT) = 3, a nie 4.
BlueRaja - Danny Pflughoeft
11
Próbowałem tego, uzyskałem 184 miliony wyników dla boczku. Nigdy nie udawało mi się szukać kanapek, ponieważ natychmiast wyszedłem usmażyć sobie bekon.
corsiKa
15
Myślę, że prawdziwym problemem jest to, że w twojej bazie danych nie ma kanapek z boczkiem.
MooseBoys
@MooseBoys tak, to musi być powód, dla którego moje liczby się sumują, ponieważ nie powinny, prawda?
sch
3
@klskl: Jeśli otrzymujesz te liczby z Google, pamiętaj, że te liczby są bardzo, bardzo przybliżone. Równie dobrze może być tak, że aby uzyskać oszacowanie dla „boczku LUB kanapki”, po prostu sumują liczby. Działa to tylko dlatego, że oszacowanie nie wymaga żadnej dokładności.
BlueRaja - Danny Pflughoeft

Odpowiedzi:

62

Wskazówka: Wyszukiwanie x AND y da 10 000 trafień.

Yuval Filmus
źródło
Tak, ale to mija się z celem, nauczyciele twierdzą ich X lub Y wyszukiwarka daje mniej trafień niż łączenie ciosy indywidualnie poszukujących x to y
sch
63
Nie, nie o to chodzi. Wręcz przeciwnie, jest to sedno sprawy.
Yuval Filmus
Jestem w tym nowy, chcesz to rozwinąć? Z tego, co rozumiem, ORAZ da wyniki z obydwoma słowami, stąd mniej wyników niż z każdym z osobna, ale co to ma wspólnego z OR?
sch
2
Gdy AND jest pusty LUB działa jak DODAJ, w przeciwnym razie nie. @klskl informacja x AND y jest kluczowa.
Zły
@YuvalFilmus Widzę teraz, o to chodzi! (Byłem jak, hamburger ORAZ kanapka nie daje 10 000 hitów ...) dziękuję
sch
93

Obowiązująca tutaj zasada liczenia to wykluczenie włączenia .

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

|X∩Y|

Diagram Venna może być bardziej przekonujący dla kogoś, kto może być zastraszony przez notację.

Schemat Venna

200_sukces
źródło
4
To jest naprawdę dobre, wykorzystam to, aby wyjaśnić mojej matce, naprawdę czyste, dzięki!
sch
3
|X∪Y|=|X|+|Y|−|X∩Y||X∩Y||X||Y||X|+|Y|
Devsman
Matematyka się sprawdza i ma sens, ale nie pasuje do ustawionej powyżej algebry.
Kevin Brown
Pamiętam, jak robiłem diagramy Venna, kiedy miałem 4-5 lat. Są naprawdę niedoceniani. Dziękuję John Venn.
Pharap,
1
@Pharap Rzeczywiście, takie diagramy zasługują na naszą Venn-eration.
Mason Wheeler,
13

Dokument 1: Kot jest na stole
Dokument 2: Mój kot jest czarny
Dokument 3: Pies jest pod stołem
Dokument 4: Jak nazywa się twój kot?
Dokument 5: To jest czarno-białe zdjęcie

Wyszukaj kota : zwrócone dokumenty to 1,2,4 (3 zwrócone dokumenty)
Wyszukaj czarne : zwrócone dokumenty są ...
Wyszukaj kota LUB czarne : zwrócone dokumenty są ...

:-D :-D

Vor
źródło
3

W prostych słowach:

Szukaj X daje n odpowiedzi.
Szukaj Y daje m odpowiedzi.
Szukaj X AND Y daje p odpowiedzi.

Szukając X LUB Y, wyszukiwanie przerywa się, gdy tylko znajdzie X lub Y. Więc jeśli X znajduje się przed Y, to Y nie będzie liczone podczas wyszukiwania X LUB Y. Dlatego twoje wyszukiwanie X LUB Y da ci n + m - p odpowiedzi.

Ważne jest, aby pamiętać, że wyniki będą takie same, niezależnie od tego, czy wykonasz 2 wyszukiwania, czy tylko jedno. Po prostu podsumowując dwa wyszukiwania, niektóre dokumenty są liczone dwukrotnie.

szczery
źródło
„wyszukiwanie przerywa się, gdy tylko znajdzie X lub Y”. Czy to nie zależy od implementacji? Implementacja może uzyskać wszystkie wyniki dla X, uzyskać wszystkie wyniki dla Y, a następnie połączyć wyniki w sposób, który eliminuje duplikaty.
jpmc26
@ArnabDatta To, co opisałem, zdecydowanie nie jest XOR. „Eliminowanie duplikatów” oznacza eliminowanie drugiej kopii, a nie wszystkich instancji tego elementu.
jpmc26
Prawdziwe. Źle zrozumiałem. Usunąłem mój komentarz.
Arnab Datta
3

Wyobraź sobie, że masz tylko jeden dokument. To jest Dokument nr 1 z tym:

X Y

Teraz wyobraź sobie, że masz funkcję wyszukiwania, która może dostarczyć wszystkie dokumenty na podstawie jednego słowa kluczowego:

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

Zauważ, że liczba dokumentów w obu przypadkach wynosi 1. Teraz, jeśli masz funkcję wyszukiwania, która podaje liczbę dokumentów, które pasują do jednego lub więcej podanych słów kluczowych:

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

Gdy dodasz liczbę dokumentów zawierających Xdo liczby dokumentów zawierających Y, spowoduje to policzenie tego samego dokumentu dwukrotnie. W twoim przypadku tak się stało, 10000jak wskazano powyżej :)

Arnab Datta
źródło