Pesquisa booleana explicada

29

Minha mãe está fazendo um curso on-line para ser uma espécie de bibliotecária; neste curso, eles abrangem pesquisas booleanas, para que possam pesquisar bancos de dados de maneira eficiente; no entanto, ela tem uma pergunta que soa algo como isto:

A pesquisa "x OR y" resultará em 105 000 ocorrências, enquanto uma pesquisa por apenas x resultará em 80 000 ocorrências, e uma pesquisa apenas em y obterá 35 000 ocorrências. Por que a pesquisa "x OR y" fornece 105.000 hits, quando as pesquisas individuais combinadas fornecem 115.000 hits?

Para mim, isso soou estranho, então eu testei isso sozinho, usando as palavras bacon e sanduíche .

  • Apenas o bacon produziu 179 000 000 resultados
  • Apenas sanduíche produziu 312 000 000 resultados
  • bacon OU sanduíche deu 491 000 000 resultados

Mas, para mim, soma: 179 000 000 (bacon) + 312 000 000 (sanduíche) = 491 000 000 (bacon OU sanduíche)

Por que uma consulta OR poderia resultar em menos ocorrências do que as duas consultas individuais combinadas?

sets counting sch
fonte
22
Você tem um cachorro azul, um gato azul e um gato vermelho. NÚMERO DE (AZUL) = 2, NÚMERO DE (CAT) = 2, mas NÚMERO DE (AZUL ou CAT) = 3, não 4. #
BlueRaja - Danny Pflughoeft
11
Eu tentei isso, obtive 184 milhões de resultados para o bacon. Nunca cheguei a procurar sanduíches, pois saí imediatamente para fritar um pouco de bacon.
corsiKa 4/16
15
Acho que o verdadeiro problema aqui é que seu banco de dados não possui sanduíches de bacon.
MooseBoys
@MooseBoys sim, deve ser por isso que meus números aumentam, já que não deveriam, certo?
SCH
3
@klskl: Se você está obtendo esses números do google, lembre-se de que esses números são estimativas muito aproximadas. Poderia muito bem acontecer que, para obter a estimativa de "bacon OU sanduíche", eles somassem os números. Isso só funciona porque não é necessário que a estimativa tenha qualquer tipo de precisão.
BlueRaja - Danny Pflughoeft

Respostas:

62

Dica: A pesquisa x AND y resultará em 10 000 ocorrências.

Yuval Filmus
fonte
sim, mas isso não vem ao caso, os professores reivindicam sua X ou Y pesquisa dá menos golpes de combinar os hits de procurar individualmente x então y
sch
63
Não, isso não vem ao caso. Pelo contrário, é o ponto em si.
Yuval Filmus
Eu sou novo nisso, gostaria de elaborar? Pelo que entendi, E darei resultados com ambas as palavras, portanto, menos resultados do que cada um individualmente, mas o que isso tem a ver com OU?
SCH
2
Quando AND está vazio OU funciona como ADD, caso contrário, não funciona. @klskl as informações de x e y são cruciais.
mal
@YuvalFilmus eu vejo agora, é o ponto! (Eu era como, hambúrguer e sanduíche não dá 10 000 acessos ...) obrigado
sch
93

O princípio da contagem que se aplica aqui é a inclusão-exclusão .

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

Para fazer os números funcionarem,deve ser 10000.|X∩Y|

Um diagrama de Venn pode ser mais convincente para alguém que pode ser intimidado pela notação.

Diagrama de Venn

200_success
fonte
4
Isso é muito bom, vai usar isso para explicar para minha mãe, muito limpo, obrigado!
SCH
3
Vou expandir um pouco o seu diagrama e apontar que o motivoé porquefaz parte de ambosejá, então quando você adiciona, você contou duas vezes. Você então subtrai para que seja contado apenas uma vez. | X ∩ Y | | X | | Y | | X | + | Y ||X∪Y|=|X|+|Y|−|X∩Y||X∩Y||X||Y||X|+|Y|
Devsman 04/04
A matemática funciona e faz sentido, mas não corresponde à álgebra definida logo acima.
Kevin Brown
Lembro-me de fazer os diagramas de Venn quando tinha 4-5 anos. Eles são realmente subestimados. Obrigado John Venn.
Pharap
1
@Pharap De fato, esses diagramas merecem nossa Venn-eration.
Mason Wheeler
13

Documento 1: O gato está em cima da mesa
Documento 2: Meu gato é preto
Documento 3: O cachorro está embaixo da mesa
Documento 4: Qual é o nome do seu gato?
Documento 5: esta é uma foto em preto e branco

Pesquisa por gato : documentos retornados são 1,2,4 (3 documentos retornados)
Pesquisa por preto : documentos retornados são ...
Pesquisa por gato OU preto : documentos retornados são ...

:-D :-D

Vor
fonte
3

Em palavras simples:

A pesquisa por X fornece n respostas.
A busca por Y fornece m respostas.
A pesquisa por X e Y fornece p respostas.

Ao procurar X OU Y, a pesquisa é interrompida assim que encontra X ou Y. Portanto, se houver um X antes de um Y, esse Y não será contado na pesquisa de X OU Y. Portanto, sua pesquisa por X OU Y fornecerá respostas n + m - p.

É importante observar que os resultados serão os mesmos, se você fizer duas pesquisas ou apenas uma. Só que, ao somar as duas pesquisas, alguns documentos são contados duas vezes.

sincero
fonte
"a pesquisa é interrompida assim que encontra X ou Y." Isso não depende da implementação? Uma implementação pode obter todos os resultados para X, obter todos os resultados para Y e depois combinar os resultados de uma maneira que elimine duplicatas.
Jpmc26
@ArnabDatta O que eu descrevi definitivamente não é um XOR. "Eliminar duplicatas" significa eliminar a segunda cópia, nem todas as instâncias desse elemento.
Jpmc26
Verdade. Eu entendi errado. Removido meu comentário.
Arnab Datta
3

Imagine que você tem apenas um documento. Este é o Documento # 1 com isso:

X Y

Agora imagine que você tem uma função de pesquisa que pode fornecer todos os documentos com base em uma palavra-chave:

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

Observe que o número de documentos nos dois casos é 1. Agora, se você possui uma função de pesquisa que fornece o número de documentos que correspondem a uma ou mais das palavras-chave fornecidas:

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

Quando você adiciona o número de documentos que contêm Xo número de documentos que contêm Y, isso faz com que você conte o mesmo documento duas vezes. No seu caso, isso aconteceu 10000vezes como indicado acima :)

Arnab Datta
fonte