Búsqueda booleana explicada

29

Mi madre está tomando un curso en línea para ser una especie de bibliotecaria, en este curso cubren búsquedas booleanas, por lo que pueden buscar bases de datos de manera eficiente, sin embargo, recibió una pregunta que suena así:

La búsqueda "x OR y" dará como resultado 105 000 resultados, mientras que la búsqueda de solo x dará como resultado 80 000 resultados y una búsqueda de solo y obtendrá 35 000 resultados. ¿Por qué la búsqueda "x OR y" da 105 000 resultados, cuando las búsquedas individuales combinadas dan 115 000 resultados?

Para mí esto sonaba extraño, así que lo probé yo mismo, usando las palabras tocino y sandwich .

  • Solo el tocino arrojó 179 000 000 resultados
  • Solo el sándwich arrojó 312 000 000 resultados
  • tocino O sandwich dio 491 000 000 resultados

Pero para mí suma: 179 000 000 (tocino) + 312 000 000 (sándwich) = 491 000 000 (tocino O sándwich)

¿Por qué una consulta OR podría dar como resultado menos visitas que ambas consultas individuales combinadas?

sch
fuente
22
Tienes un perro azul, un gato azul y un gato rojo. NÚMERO DE (AZUL) = 2, NÚMERO DE (GATO) = 2, pero NÚMERO DE (AZUL o GATO) = 3, no 4.
BlueRaja - Danny Pflughoeft
11
Intenté esto, obtuve 184 millones de resultados para tocino. Nunca llegué a buscar sándwiches, ya que inmediatamente me fui a freír tocino.
corsiKa
15
Creo que el verdadero problema aquí es que su base de datos no tiene sándwiches de tocino.
MooseBoys
@MooseBoys, sí, esta debe ser la razón por la cual mis números se suman, ya que no deberían, ¿verdad?
sch
3
@klskl: Si obtienes esos números de Google, ten en cuenta que esos números son estimaciones muy aproximadas. Bien podría ser el caso de que, para obtener la estimación de "tocino o sándwich", simplemente sumen los números. Eso solo funciona porque no se requiere que la estimación tenga ningún tipo de precisión.
BlueRaja - Danny Pflughoeft

Respuestas:

62

Sugerencia: la búsqueda xYy dará como resultado 10 000 visitas.

Yuval Filmus
fuente
sí, pero eso no viene al caso, los maestros afirman que su búsqueda x O y da menos resultados que combinar los resultados de buscar individualmente x luego y
sch
63
No, eso no viene al caso. Por el contrario, es el punto en sí.
Yuval Filmus
Soy nuevo en esto, ¿quieres elaborar? Por lo que entiendo Y dará resultados con ambas palabras en ellas, por lo tanto, menos resultados que cada uno individualmente, pero ¿qué tiene eso que ver con OR?
sch
2
Cuando AND está vacío O funciona como AGREGAR, de lo contrario no lo hace. @klskl la información de xYy es crucial.
Mal
@YuvalFilmus Ya veo, ¡es el punto! (Pensé, hamburguesa Y sándwich no da 10 000 visitas ...) gracias
sch
93

El principio de conteo que se aplica aquí es la inclusión-exclusión .

El |XYEl |=El |XEl |+El |YEl |-El |XYEl |

Para que los números funcionen, debe ser 10000.El |XYEl |

Un diagrama de Venn puede ser más convincente para alguien que pueda sentirse intimidado por la notación.

diagrama de Venn

200_success
fuente
44
Esto es realmente bueno, lo usaré para explicarle a mi madre, muy limpio, ¡gracias!
sch
3
El |XYEl |=El |XEl |+El |YEl |-El |XYEl |El |XYEl |El |XEl |El |YEl |El |XEl |+El |YEl |
Devsman
Las matemáticas funcionan, y tiene sentido, pero no coinciden con el álgebra establecida justo encima.
Kevin Brown
Recuerdo haber hecho Diagramas de Venn cuando tenía 4-5. Realmente están subestimados. Gracias John Venn
Pharap
1
@Pharap De hecho, tales diagramas merecen nuestra venganza.
Mason Wheeler
13

Documento 1: El gato está sobre la mesa
Documento 2: Mi gato es negro
Documento 3: El perro está debajo de la mesa
Documento 4: ¿Cómo se llama su gato?
Documento 5: esta es una foto en blanco y negro

Búsqueda de gato : los documentos devueltos son 1,2,4 (3 documentos devueltos)
Búsqueda de negro : los documentos devueltos son ...
Búsqueda de gato O negro : los documentos devueltos son ...

:-D :-D

Vor
fuente
3

En palabras simples:

Buscar X te da n respuestas.
Buscar Y te da m respuestas.
Buscar X e Y te da p respuestas.

Al buscar X O Y, la búsqueda se interrumpe tan pronto como encuentra X o Y. Entonces, si hay una X antes de una Y, esa Y no se contará en la búsqueda de X O Y. Por lo tanto, su búsqueda de X O Y le dará n + m - p respuestas.

Es importante tener en cuenta que los resultados serán los mismos, ya sea que realice 2 búsquedas o solo una. Es solo que al sumar las dos búsquedas, algunos documentos se cuentan dos veces.

franco
fuente
"la búsqueda se interrumpe tan pronto como encuentra X o Y". ¿No depende esto de la implementación? Una implementación podría obtener todos los resultados para X, obtener todos los resultados para Y y luego combinar los resultados de una manera que elimine los duplicados.
jpmc26
@ArnabDatta Lo que describí definitivamente no es un XOR. "Eliminar duplicados" significa eliminar la segunda copia, no todas las instancias de ese elemento.
jpmc26
Cierto. Entendí mal. Eliminado mi comentario
Arnab Datta
3

Imagina que solo tienes un documento. Este es el Documento # 1 con esto:

X Y

Ahora imagine que tiene una función de búsqueda que puede proporcionarle todos los documentos basados ​​en una palabra clave:

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

Tenga en cuenta que el número de documentos en ambos casos es 1. Ahora, si tiene una función de búsqueda que le proporciona el número de documentos que coinciden con una o más de las palabras clave proporcionadas:

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

Cuando agrega el número de documentos que contienen Xal número de documentos que contienen Y, esto hace que cuente el mismo documento dos veces. En su caso, esto sucedió 10000veces como se señaló anteriormente :)

Arnab Datta
fuente