Задачи про три слова
Задача от Drungа. А как выполнять например такой?
мезозой 500
кроманьонец 600
неандерталец 700
мезозой | кроманьонец 800
мезозой | неандерталец 1000
неандерталец & (мезозой | кроманьонец) 200
Сколько страниц будет найдено по запросу
кроманьонец & (мезозой | неандерталец)
Отвечаем.
Эта задача значительно труднее, чем та, которая приведена в демоверсии. Точнее, не труднее, а сложнее в вычислениях. Тем не менее, давайте разбираться.
1. Важные наблюдения.
На рисунке схематично изображены документы, в которых встречаются слова «неандерталец» (красный круг), «кроманьонец» (синий круг) и «мезозой» (черный круг). К слову, мезозой (или мезозойская эра) закончился примерно за 40 миллионов лет до появления на Земле неандертальцев и кроманьонцев.
Наблюдение 1. Документы, в которых встречается хотя бы одно из этих слов можно разделить на 6 групп:
Н1 – встречается только «неандерталец», других слов нет.
К1 – встречается только «кроманьонец», других слов нет.
М1 – встречается только «мезозой», других слов нет.
НК-М – встречаются «неандерталец» и «кроманьонец»; «мезозой» не встречается
НМ-К - встречаются «неандерталец» и «мезозой»; «кроманьонец» не встречается
КМ-Н - встречаются «кроманьонец» и «мезозой»; «неандерталец» не встречается
НКМ – встречаются все три слова
Наблюдение 2. Эти группы НЕ пересекаются !!!
Наблюдение 3. Множество документов, которые отбираются по любому запросу со словами «неандерталец», «кроманьонец» и «мезозой», составлено из этих групп. Например, по запросу «мезозой» будут отобраны документы из групп М1, НМ-К, КМ-Н и НКМ.
!!! Предполагается, что других слов, кроме слов «неандерталец», «кроманьонец» и «мезозой», в запросе нет.
Обозначение. Обозначим количество документов в группе Н1 через N(Н1), количество документов в группе НМ-К через N(НМ-К) и т.д.
Наблюдение 4. Так как наши группы не пересекаются, то количество документов, отобранных по любому запросу со словами «неандерталец», «кроманьонец» и «мезозой» (см. Наблюдение 2), можно представить как сумму чисел N(Н1), N(К1), N(М1), N(НК-М) ), N(НМ-К) ), N(КМ-Н) ), N(НКМ).
Примеры.
- Количество документов, найденных по запросу «мезозой | кроманьонец» равно
N(М1) + N(НМ-К) + N(КМ-Н) + N(НКМ)
2. Количество документов, найденных по запросу «мезозой» равно
N(М1) + N(К1) + N(НМ-К) + N(КМ-Н) + N(НК-М) + N(НКМ)
(участвуют все группы, кроме Н1);
3. Количество документов, найденных по запросу «неандерталец & (мезозой | кроманьонец)» равно
N(НМ-К) + N(НК-М) + N(НКМ)
2. Решение на все случаи
Эти наблюдения позволяют решить любую задачу такого типа, в которой есть 6 условий: каждое условие дает нам уравнение, а полученную систему из 6 линейных уравнений с 6 неизвестными несложно решить.
В нашем случае, например, для запроса «мезозой» (см. пример 1) получаем уравнение:
N(М1) + N(НМ-К) + N(КМ-Н) + N(НКМ) = 500 (1)
Для запроса «кроманьонец»:
N(К1) + N(НК-М) + N(КМ-Н) + N(НКМ) = 600 (2)
Для запроса «неандерталец»:
N(Н1) + N(НК-М) + N(НМ-К) + N(НКМ) = 700 (3)
Для запроса «мезозой | кроманьонец»
N(М1) + N(К1) + N(НМ-К) + N(КМ-Н) + N(НК-М) + N(НКМ) = 800 (4)
(слева – все группы, кроме Н1)
Для запроса «мезозой | неандерталец»:
N(М1) + N(Н1) + N(НМ-К) + N(КМ-Н) + N(НК-М) + N(НКМ) = 1000 (5)
Для запроса «неандерталец & (мезозой | кроманьонец)»:
N(НМ-К) + N(НК-М) + N(НКМ) = 200 (6)
Получили 6 уравнений с 6 неизвестными. Такую систему можно решить обычным способом (например, исключая переменные по одному). После этого можно найти количество документов, которые будут отобраны по запросу «кроманьонец & (мезозой | неандерталец)». Это количество равно
N(КМ-Н) + N(НК-М) + N(НКМ)
Идея приведенного решения простая, но вычислений много и ошибиться легко.
К счастью, в некоторых задачах такого типа бывают и более простые решения. Как правило, это бывает, когда задачу можно свести к задаче, в которой используются только два слова или какая-то группа документов – пустая. См. такие примеры в демо-версии.
Остались вопросы? Пишите! Ответим.
0 Comments
Оставьте коммент первым.