intro-inf-retrieval

Репозиторий по курсу "Основы информационного поиска".

Инструкция для объединения вашего и шаблонного репозиториев.

---

Домашние задания

Задание 1.

Написать веб-краулер, который парсит выбранный Вами тематический сайт.

Первый этап: выделение ссылок на статьи/посты.

Второй этап: выделение заголовка статьи, текста и указанные ключевые слова/теги/данные из мета-тега keywords. Если ключевые слова ни в каком виде не указаны, выберите другой сайт.

Текст на сайте должен быть преимущественно русский. Количество спарсенных страниц не менее 30.

Выделенные блоки не должны содержать тегов, скриптов, ссылок итп - только текст. Проблем с кодировкой тоже не должно быть.

Результат записать в виде xml-файла со следующей структурой и кодировкой UTF-8:

<?xml version="1.0" encoding="UTF-8"?>
<documents>
	<document id = "1">
		<url/>
		<title/>
		<text/>
		<keywords/>
	</document>
	<document id = "2">
		<url/>
		<title/>
		<text/>
		<keywords/>
	</document>
</documents>

Язык программирования выбираете сами, можете использовать библиотеки. При выделении элементов html-документа можете использовать XPath, XQuery, а также другие инструменты рассматривающие html-документы в виде объекта.

Задание 2.

Из сохраненных документов, полученных в задании 1, для блоков title и text:

• выделить отдельные слова (очистить от символов);
• привести к нижнему регистру;
• удалить стопслова;
• лемматизировать с использованием стеммера Портера, либо MyStem.

Результат записать в текстовый файл.

Задание 3.

1. Построить инвертированный индекс и записать в виде следующего xml-файла:

<?xml version="1.0"?>
<terms>
	<term value="word1">
		<doc id="1" count="7"/>
		<doc id="2" count="3"/>
	</term>
	<term value="word2">
		<doc id="1" count="7"/>
		<doc id="3" count="3"/>
	</term>
</terms>

Термы должны быть отсортированы в лексиграфическом порядке, документы по порядку включения.

2. Реализовать булев поиск для операций пересечения и дополнения (пробел соответствует операции AND, дефис операции NOT).

• К запросу применяются методы из задания 2.
• Если в запросе есть дополнение, то сперва находите их.
• Порядок поиска пересечений необходимо посчитать по количеству документов, в которых встречается слова из запроса. Т.е. по возрастанию словопозиций. Например, если слово1, слово2, слово3 встречается 6, 30, 1 раз соответственно, то сперва нужно искать пересечение слово3 и слово1, а затем его результат со словом 2. Дополнение же вычисляется в приоритете по сравнению с операцией пересечения.
• Результат выполнения программы записать в текстовый файл, который должен содержать запрос и список документов в которых он встречается (заголовок и url). Минимум 5 запросов от 3 до 5 слов, и один без результата.

Задание 4.

1. Вычислить по формуле tf-idf(t, d, D) = tf(t,d)*idf(t,D),

где .

f_t,d - количество вхождений терма t в документе d, знаменатель в tf - количество слов в документе. N = |D| - размер коллекции, n_t - количество докуметов, в которых есть этот терм. Полученные значения записать в инвертированный индекс в аттрибут tf-idf:

<?xml version="1.0"?>
<terms>
    <term value="word1">
        <doc id="1" count="7" tf-idf="0.0234"/>
    </term>
</terms>

2. В задание 3.2 добавить ранжированный поиск, используя tf-idf значения из инвертированного поиска. Для этого у каждого документа полученного методом булевого поиска по пересечению (факультативно объединению) вычислить score(q, d) = \sum tf-idf. Результаты отсортировать в порядке убывания score. Вывести аналогично заданию 3.2, используя те же запросы.

Задание 5.

Реализовать поиск на основе векторного модели по построенному индексу.

Этапы:

1. Для каждого слова из запроса, которое есть в коллекции, извлечь из инвертированного индекса список словопозиций.
2. На основе полученных данных формируется матрица соответствия документ-терм. Каждая строка которой представляет собой вектор документа, элементы которой являются tf-idf значения. Длина вектора равна количеству слов в запросе, которые есть в словаре.
3. Далее, для каждой пары векторов документа и запроса вычисляем косинусную меру между ними.
4. Вывести результаты в порядке убывания значния косинуса (вывести первые 10, url и значение косинусной меры), значение лежит в отрезке от 0 до 1, чем ближе к 1 тем более релевантно.

Задание 6.

Реализовать поиск на основе латентно-семантического анализа.

Ликбез

Аналогично 5 заданию, за исключением того что во втором шаге к матрице, используя любую библиотеку, применяете сингулярное разложение.

На шаге 3 используется формула Equation 11 из ликбеза. Число k подберите от 3 до 5. Для документов используете tf-idf, для запроса булеву функцию.

Значения можете не сохранять в файл.

Также как и в прошлом задании выдать результаты 5 запросов, в текстовом файле.

Вопросы можно задавать здесь