http://habrahabr.ru/post/263913/

В предыдущей части мы построили индекс, но мы всё ещё не можем выполнять запросы по нему. Про это я и расскажу в этой статье.

Выполнение запросов к индексу

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

Однако, прежде чем мы начнем, я бы рекомендовал обработать запрос так же, как мы обрабатывали документы, когда строили индекс, преобразовывая все слова, делая все буквы строчными и удаляя знаки препинания. Я не буду вдаваться в это, так как это тривиально, но это должно быть сделано перед выполнением запроса.

Примечание: во всех примерах кода ниже, каждая функция будет использовать в переменную с именем ‘invertedIndex’, которая генерируется в предыдущей части статьи. Для полного понимания происходящего ниже вы можете ознакомиться с финальным результатом на GitHub.

Мы собираемся реализовать стандартные запросы в первую очередь. Простой способ реализовать их — разбить запрос на слова (маркеры, как описано выше), получить список за каждое слово, документы в которых они встречаются, а затем объединить все эти списки. Вот как мы выполним запрос для одного слова:

def one_word_query(self, word):
	pattern = re.compile('[\W_]+')
	word = pattern.sub(' ',word)
	if word in self.invertedIndex.keys():
		return [filename for filename in self.invertedIndex[word].keys()]
	else:
		return []

Этот код довольно простой. Все, что мы здесь делаем — это обрабатываем ввод с помощью регулярного выражения и возвращаем список всех ключей в хеш-таблице для этого слова в индексе (который является списком имён файлов, в которых встречается слово).

Теперь стандартный запрос является очень простым расширением. Мы просто агрегируем и объединяем списки как показано здесь:

def free_text_query(self, string):
	pattern = re.compile('[\W_]+')
	string = pattern.sub(' ',string)
	result = []
	for word in string.split():
		result += self.one_word_query(word)
	return list(set(result))

Если вы хотите осуществить запрос, который гарантирует, что каждое слово в запросе встречается в итоговом списке, то вы должны использовать пересечение вместо объединения в агрегации результатов отдельных запросов, содержащих слово. Это довольно тривиально, чтобы сделать, и я оставлю это в качестве упражнения для читателя.

Последним типом запросов является запрос с фразой, который немного сложнее, так как мы должны гарантировать правильный порядок слов в документах. Вот код для данного запроса (я объясню позже):

def phrase_query(self, string):
	pattern = re.compile('[\W_]+')
	string = pattern.sub(' ',string)
	listOfLists, result = [],[]
	for word in string.split():
		listOfLists.append(self.one_word_query(word))
	setted = set(listOfLists[0]).intersection(*listOfLists)
	for filename in setted:
		temp = []
		for word in string.split():
			temp.append(self.invertedIndex[word][filename][:])
		for i in range(len(temp)):
			for ind in range(len(temp[i])):
				temp[i][ind] -= i
		if set(temp[0]).intersection(*temp):
			result.append(filename)
	return self.rankResults(result, string)

И так, мы вновь сначала обрабатываем текст входного запроса. Затем мы запускаем одно слово из запроса для каждого слова на входе, и добавляем каждый из этих списков результатов в наш общий список. Затем мы создаём множество с именем 'setted', который принимает пересечение первого списка со всеми другими списками (по существу, принимая пересечение всех списков), и оставляет нас с промежуточным результатом: множеством всех документов, содержащих все слова запроса.

Теперь мы должны проверить промежуточный результат. Так, для каждого списка в промежуточном результате, мы сначала составьте список списков позиций каждого слова во входном запросе. Затем (внимание!) мы используем два вложенных цикла for для итерации через список списков. Для каждой позиции в каждом списке мы отнимем номер i, который увеличивается на 1, когда мы проходим через список списков. Итак, помните, что списки в Python сохраняют порядок, так что этот список списков содержит списки позиций каждого слова в исходном запросе в порядке слов в исходном запросе. Затем, если эти слова стоят в правильном порядке, и мы вычтем целое число i от каждой позиции в каждом списке позиций, и i увеличивается на 1 каждый раз, как мы проходим через следующий список позиций, то, если эти фразы есть в промежуточном результате, пересечение всех этих модифицированных списков списков должны иметь длину по меньшей мере одного.

Позвольте мне привести пример:

Допустим, фразой в запросе является “торт — это ложь”. Теперь предположим, что для конкретного файла позиции каждого слова такие:

торт: [19, 35, 12]
это: [179, 36, 197]
ложь: [221, 37, 912]

Теперь, наш список списков таков:

[[19, 35, 12], [179, 36, 197], [221, 37, 912]]

Теперь, мы вычитаем i из каждого элемента в каждом списке, где i равно нулю для первого списка, 1 для второго списка, 2 для третьего списка и т.д.

[[19, 35, 12], [178, 35, 196], [219, 35, 910]]

Теперь мы возьмем пересечение всех списков, в которых остались значение с номером элемента 35. После этого можно было бы определить, что фраза “торт — это ложь” есть в файле. И это правд: если мы посмотрим на первоначальный список, мы увидим, что последовательность «35, 36, 37» дает нам нашу фразу.

Есть ещё много параметров запросов, которые вы могли бы реализовать самостоятельно (посмотрите на расширенный поиск у Google для вдохновения). Вы можете попробовать реализовать некоторые из них на своём поисковом движке.

Наш последний шаг состоит в том, чтобы реализовать парсер запросов, что позволит нам сочетать разные типы запросов, чтобы получить один результирующий набор. Например, как можно ввести что-то вроде 'торт “это ложь”' в Google, который сочетает в себе стандартные запросы (на весь запрос), и фраз запросов (“это ложь”). Это также очень просто сделать: просто используйте разделители (например, кавычки), чтобы указать определенный тип запросов, прогнать каждый из меньших запросов отдельно, а затем пересечь все эти результирующие множества, чтобы получить итоговый список документов.

В следующей, заключительной, части я расскажу вам про ранжирование результатов и проведу заключение.