Запросы поисковых систем и операции над множествами
💻 Информатика · 9 класс
Как логические связки в поисковых запросах связаны с операциями над множествами и подсчётом результатов.
Поисковый запрос как условие отбора
Когда мы вводим запрос в поисковую систему, мы фактически задаём условие отбора страниц. Слова в запросе можно соединять логическими связками, и поисковая система возвращает все документы, которые удовлетворяют этому условию. Эта тема тесно связана с понятием множества: каждое слово запроса задаёт множество страниц, на которых оно встречается, а связки между словами соответствуют операциям над этими множествами.
Понимание этой связи помогает решать задачи, в которых по известному числу страниц для одних запросов нужно вычислить число страниц для другого запроса. Такие задачи регулярно встречаются на экзамене.
Основные операции
| Связка | Знак в запросе | Что находит | Операция |
|---|---|---|---|
| И | & | Страницы, где есть оба слова | Пересечение |
| ИЛИ | | | Страницы, где есть хотя бы одно слово | Объединение |
Связка И сужает поиск, и результатов становится меньше, потому что страница должна содержать сразу все указанные слова. Связка ИЛИ расширяет поиск, и результатов становится больше, ведь достаточно хотя бы одного слова. Это в точности соответствует операциям пересечения и объединения множеств.
Разбор задачи
Пусть по запросу барсук найдено 200 страниц, по запросу лиса — 150, а по запросу барсук | лиса — 300. Сколько страниц найдёт запрос барсук & лиса? Воспользуемся формулой, связывающей объединение и пересечение множеств:
Формула включений и исключений:
|A или B| = |A| + |B| - |A и B|
Подставим известные числа:
300 = 200 + 150 - |барсук и лиса|
|барсук и лиса| = 200 + 150 - 300 = 50
Здесь работает формула включений и исключений: количество страниц в объединении равно сумме количеств для каждого слова за вычетом количества в пересечении. Вычитать пересечение нужно потому, что страницы, содержащие оба слова, иначе были бы посчитаны дважды. Из этой формулы мы и нашли искомое число — 50 страниц.
Наглядно это удобно представить с помощью кругов Эйлера. Каждое слово изображают кругом, а их перекрытие — общей частью. Площадь объединения двух кругов равна сумме их площадей минус площадь общей части, посчитанная один раз вместо двух. Тот же приём помогает и в более сложных запросах из трёх слов: рисуют три пересекающихся круга и аккуратно расставляют числа в каждой области, начиная с самой внутренней.
Правило. Чем больше слов соединено связкой И, тем меньше результатов; чем больше связок ИЛИ, тем больше результатов. При этом запрос со связкой И никогда не даёт больше страниц, чем любое из его отдельных слов по отдельности.
Кратко о главном
- Каждое слово запроса задаёт множество страниц, где оно встречается.
- Связка И — это пересечение, связка ИЛИ — объединение множеств.
- Связка И сужает поиск, связка ИЛИ его расширяет.
- Подсчёт ведётся по формуле
|A или B| = |A| + |B| - |A и B|.