Pencarian Boolean menjelaskan

29

Ibu saya mengambil kursus online untuk menjadi semacam pustakawan, dalam kursus ini mereka mencakup pencarian boolean, sehingga mereka dapat mencari database secara efisien, namun, dia mendapat pertanyaan yang terdengar seperti ini:

Pencarian "x ATAU" akan menghasilkan 105.000 klik, sedangkan pencarian hanya x akan menghasilkan 80.000 klik, dan pencarian hanya y akan mendapatkan 35.000 klik. Mengapa pencarian "x ATAU" memberikan 105.000 klik, ketika pencarian individu gabungan memberikan 115.000 klik?

Bagi saya ini terdengar aneh, jadi saya mengujinya sendiri, menggunakan kata bacon dan sandwich .

  • Hanya bacon yang menghasilkan 179.000 hasil
  • Hanya sandwich yang menghasilkan 312.000 hasil
  • bacon OR sandwich memberi 491.000 hasil

Tetapi bagi saya itu menambahkan: 179 000 000 (bacon) + 312 000 000 (sandwich) = 491 000 000 (bacon ATAU sandwich)

Mengapa kueri ATAU dapat menghasilkan lebih sedikit klik daripada gabungan kueri individual?

sets counting sch
sumber
22
Anda memiliki anjing biru, kucing biru, dan kucing merah. NUMBER OF (BLUE) = 2, NUMBER OF (CAT) = 2, tetapi NUMBER OF (BLUE atau CAT) = 3, bukan 4.
BlueRaja - Danny Pflughoeft
11
Saya mencoba ini, mendapat 184 juta hasil untuk daging. Tidak pernah berhasil mencari sandwich, karena saya segera pergi untuk menggoreng bacon.
corsiKa
15
Saya pikir masalah sebenarnya di sini adalah bahwa database Anda tidak memiliki sandwich daging di dalamnya.
MooseBoys
@ MooseBoys ya, ini pasti mengapa jumlah saya bertambah, karena seharusnya tidak, kan?
sch
3
@klskl: Jika Anda mendapatkan angka-angka itu dari google, ingatlah bahwa angka-angka itu adalah perkiraan yang sangat kasar. Bisa jadi itu adalah kasus bahwa, untuk mendapatkan perkiraan "bacon ATAU sandwich", mereka hanya menjumlahkan angkanya. Itu hanya bekerja karena estimasi tidak diperlukan untuk memiliki akurasi apa pun.
BlueRaja - Danny Pflughoeft

Jawaban:

62

Petunjuk: Pencarian x DAN y akan menghasilkan 10.000 klik.

Yuval Filmus
sumber
ya, tapi itu intinya, para guru mengklaim pencarian x ATAU y memberikan lebih sedikit hit daripada menggabungkan hit pencarian individual x kemudian y
sch
63
Tidak, bukan itu intinya. Sebaliknya, itu intinya sendiri.
Yuval Filmus
Saya baru dalam hal ini, peduli untuk menjelaskan? Dari apa yang saya mengerti DAN akan memberikan hasil dengan kedua kata di dalamnya, maka hasilnya lebih sedikit daripada masing-masing secara individu, tetapi apa hubungannya dengan OR?
sch
2
Ketika DAN kosong ATAU berfungsi seperti TAMBAH, jika tidak maka TIDAK. @klskl informasi x AND y sangat penting.
Evil
@YuvalFilmus saya mengerti sekarang, itu intinya! (Saya seperti, hamburger DAN sandwich tidak memberikan 10.000 hit ...) terima kasih
sch
93

Prinsip penghitungan yang berlaku di sini adalah inklusi-pengecualian .

|X∪Y|=|X|+|Y|-|X∩Y|

Untuk membuat angka-angka bekerja, harus 10.000.|X∩Y|

Diagram Venn mungkin lebih meyakinkan bagi seseorang yang mungkin terintimidasi oleh notasi.

diagram Venn

200_sukses
sumber
4
Ini sangat bagus, akan menggunakan ini untuk menjelaskan kepada ibuku, sangat bersih, terima kasih!
sch
3
|X∪Y|=|X|+|Y|-|X∩Y||X∩Y||X||Y||X|+|Y|
Devsman
Matematika berhasil, dan itu masuk akal, tetapi tidak cocok dengan aljabar yang ditetapkan tepat di atasnya.
Kevin Brown
Saya ingat melakukan Venn Diagram ketika saya berusia 4-5. Mereka benar-benar diremehkan. John Venn terima kasih.
Pharap
1
@Pharap Memang, diagram semacam itu pantas untuk Venn erasi kita.
Mason Wheeler
13

Dokumen 1: Kucing ada di meja
Dokumen 2: Kucing saya hitam
Dokumen 3: Anjing ada di bawah meja
Dokumen 4: Apa nama kucing Anda?
Dokumen 5: Ini adalah foto hitam putih

Mencari kucing : dokumen yang dikembalikan adalah 1,2,4 (3 dokumen yang dikembalikan)
Mencari hitam : dokumen yang dikembalikan adalah ...
Mencari kucing ATAU hitam : dokumen yang dikembalikan adalah ...

:-DD

Vor
sumber
3

Dengan kata sederhana:

Pencarian untuk X memberi Anda n jawaban.
Mencari Y memberi Anda jawaban.
Mencari X AND Y memberi Anda jawaban p.

Dalam mencari X OR Y, pencarian terputus begitu menemukan X atau Y. Jadi, jika ada X sebelum Y, maka Y tidak akan dihitung dalam mencari X OR Y. Oleh karena itu pencarian Anda untuk X OR Y akan memberi Anda n + m - p jawaban.

Penting untuk dicatat bahwa hasilnya akan sama, apakah Anda melakukan 2 pencarian, atau hanya satu. Hanya saja dalam menjumlahkan dua pencarian, beberapa dokumen dihitung dua kali.

jujur
sumber
"pencarian terputus begitu menemukan X atau Y." Apakah ini tidak tergantung pada implementasi? Suatu implementasi dapat memperoleh semua hasil untuk X, memperoleh semua hasil untuk Y, dan kemudian menggabungkan hasilnya dengan cara yang menghilangkan duplikat.
jpmc26
@ArnabDatta Apa yang saya jelaskan jelas bukan XOR. "Menghilangkan duplikat" berarti menghilangkan salinan kedua, tidak semua contoh elemen itu.
jpmc26
Benar. Saya salah paham. Menghapus komentar saya.
Arnab Datta
3

Bayangkan Anda hanya memiliki satu dokumen. Ini adalah Dokumen # 1 dengan ini:

X Y

Sekarang bayangkan Anda memiliki fungsi pencarian yang dapat memberi Anda semua dokumen berdasarkan satu kata kunci:

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

Perhatikan bahwa jumlah dokumen dalam kedua kasus adalah 1. Sekarang jika Anda memiliki fungsi pencarian yang memberi Anda jumlah dokumen yang cocok dengan satu atau lebih kata kunci yang disediakan:

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

Ketika Anda menambahkan jumlah dokumen yang mengandung Xjumlah dokumen yang mengandung Y, ini menyebabkan Anda menghitung dokumen yang sama dua kali. Dalam kasus Anda, ini terjadi 10000kali seperti yang ditunjukkan di atas :)

Arnab Datta
sumber