Тема сегодняшнего занятия — построение обратного индекса. Мы узнаем с вами о том, как именно построить обратный индекс, а также о том, почему хороший индекс — это быстрый индекс. О том, что такое обратный индекс, мы уже с вами говорили, но, давайте, вспомним. Это структура, которая состоит из двух основных логических частей: первая из них это словарь, это список термов, которые входят в документы в нашем корпусе. Далее, каждому терму ставится в соответствие инвертированный список. Это список документов, в которые входит конкретный терм. В общем виде построение обратного индекса выглядит следующим образом: мы берем документы нашего корпуса, парсим их, извлекаем из них лексемы, дальше мы нормализуем каждую лексему уже известными нам методами и получаем набор термов и уже для полученных термов мы строим инвертированный список. Таким образом, каждый документ дает нам какое-то множество термов. Преобразуем это множество в набор пар, где каждому терму поставим в соответствие тот документ, из которого этот терм был извлечен. Теперь мы можем объединить эту информацию по тому, какой терм из какого документа был извлечен, то есть основываясь на термах, мы объединяем информацию и получаем, для каждого терма список тех документов, из которых этот терм мы извлекли. Прежде, чем переходить непосредственно к построению обратного индекса, давайте проведем несколько улучшений. Во-первых, обращаться к документу в инвертированном списке мы должны основываясь на чем-то, на какой-то идентификаторе, которой однозначно говорит нам, что это был за документ. В случае с веб-поиском мы можем, например, использовать URL. Однако, URL — это строка и он занимает очень много места в памяти, поэтому в общем случае лучше использовать в качестве идентификатора какое-то число. Мы можем, во-первых, контролировать уникальность этого идентификатора, во-вторых, он занимает немного места. Аналогичные изменения мы можем провести и с термами, так как термы могут иметь абсолютно разную длину, могут занимать много места и, в конце концов, это строки, мы можем вместо них использовать какие-то идентификаторы числовые, к которым адресоваться, обращаться. Однако нам потребуется хранить в словаре исходный терм для того, чтобы вернуться к нему обратно после того, как мы обработаем нужную нам информацию. Давайте, забежим немного вперед, как вы помните, у нас в результате поиска может получаться очень большое множество документов, настолько большое, что пользователь физически будет не в состоянии просмотреть их все. Поэтому мы иногда решаем, что мы показываем ему только лучшие документы, отбирая определенное множество, которое мы ему и отдаем. Для того, чтобы это сделать, мы должны решить, какие документы лучше. Этими вопросами занимается ранжирование. Есть такое понятие как черновое ранжирование, которое позволяет нам не прибегая к достаточно сложным алгоритмам достаточно грубо оценить, насколько хорош тот или иной документ для данного запроса, насколько он ему релевантен. Именно для чернового ранжирования мы можем, например, использовать частоту термов. Эту информацию мы можем хранить в самом словаре вместе с термом. Так же, например, если нам требуется черновой вариант отбора лучших нескольких документов, мы можем для того, чтобы ускорить этот процесс, хранить в инвертированных списках такое понятие, как популярность документа. Таким образом, в инвертированном списке у нас будут документы отсортированы так, что в самом начале будет лежать максимально популярные документы и мы сможем рассматривать не весь инвертированный список, а только определенную часть в его начале и уже из этой части строить тот топ документов, который нам в конечном счете и понадобится. Давайте, поговорим с вами также о том, как мы будем представлять наш обратный индекс, как мы будем его хранить. Первый вариант, как мы можем хранить, мы можем использовать для этого структуру фиксированной величины, однако это очень невыгодно. Во-первых, у нас что термы, что инвестирование списки имеют разнообразную длину для различных частей из словаря, для различных документов. Таким образом, мы получаем избыточность, то есть в случае со структурами фиксированной величины у нас во многих случаях будет заниматься место, которое фактически будет представлять собой пустоту. То есть в случае, если терм слишком маленький, а мы выделили слишком много места под него, то полезная нагрузка очень низкая. Кроме того, мы не знаем максимальную величину, что терма, что инвертированного списка, узнаем мы об этом только после того, как построим непосредственно словарь и все инвертированные списке. Поэтому логичным решением будет использовать структуры динамические, например, это может быть массив переменной величины. В таких случаях мы решаем проблему с использованием места, в случаях, если у нас термы переменной длины. Однако такие структуры очень сложно наполнять, это требует дополнительных расходов. Есть альтернативный подход. Это использование, например, односвязных списков. Такие структуры удобно дополнять, однако мы получаем небольшой overhead при хранении, так как при хранении нам кроме самой структуры потребуется хранить еще и ссылки. Собственно, можно использовать любую из этих структур.
