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

Question

У меня есть полный инвертированный индекс в виде вложенного словаря Python. Его структура:

{word: {doc_name: [location_list]}}

Например, пусть словарь будет называться index, тогда для слова " spam " запись будет выглядеть так:

{spam: {doc1.txt: [102,300,399], doc5.txt: [200,587]}}

так что документы, содержащие любое слово, могут быть заданы index [word].keys (), а частота в этом документе - len(index[word][document])

Теперь мой вопрос заключается в том, как мне реализовать обычный поиск запросов в этом индексе. т. е. данный запрос, содержащий, скажем, 4 слова, находит документы, содержащие все четыре совпадения (ранжированные по общей частоте появления), затем документы, содержащие 3 совпадения и так далее....

**

Добавил этот код, используя ответ С. Лотта. Это код, который я написал. Он работает точно так, как я хочу (нужно только некоторое форматирование вывода), но я знаю, что это можно улучшить.

**

from collections import defaultdict
from operator import itemgetter

# Take input

query = input(" Enter the query : ")

# Some preprocessing

query = query.lower()
query = query.strip()

# now real work

wordlist = query.split()
search_words = [ x for x in wordlist if x in index ]    # list of words that are present in index.

print "\nsearching for words ... : ", search_words, "\n"

doc_has_word = [ (index[word].keys(),word) for word in search_words ]
doc_words = defaultdict(list)
for d, w in doc_has_word:
    for p in d:
        doc_words[p].append(w)

# create a dictionary identifying matches for each document    

result_set = {}

for i in doc_words.keys():
    count = 0
    matches = len(doc_words[i])     # number of matches
    for w in doc_words[i]:
        count += len(index[w][i])   # count total occurances
    result_set[i] = (matches,count)

# Now print in sorted order

print "   Document \t\t Words matched \t\t Total Frequency "
print '-'*40
for doc, (matches, count)) in sorted(result_set.items(), key = itemgetter(1), reverse = True):
    print doc, "\t",doc_words[doc],"\t",count

Просьба прокомментировать.... Спасибо.

Answer 1

Вот начало:

doc_has_word = [ (index[word].keys(),word) for word in wordlist ]

Это создаст список пар (слово, документ). Вы не можете легко сделать словарь из этого, так как каждый документ встречается много раз.

Но

from collections import defaultdict
doc_words = defaultdict(list)
for d, w in doc_has_word:
    doc_words[tuple(d.items())].append(w)

Может быть полезно.

Answer 2

import itertools

index = {...}

def query(*args):
    result = []

    doc_count = [(doc, len(index[word][doc])) for word in args for doc in index[word]]
    doc_group = itertools.groupby(doc_count, key=lambda doc: doc[0])

    for doc, group in doc_group:
        result.append((doc, sum([elem[1] for elem in group])))

    return sorted(result, key=lambda x:x[1])[::-1]

Answer 3

Вот решение для поиска похожих документов (самая сложная часть):

wordList = ['spam','eggs','toast'] # our list of words to query for
wordMatches = [index.get(word, {}) for word in wordList]
similarDocs = reduce(set.intersection, [set(docMatch.keys()) for docMatch in wordMatches])

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

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

Как только вы найдете документы, которые похожи, вы сможете использовать defaultdict (как показано в ответе С. Лотта), чтобы добавить все списки совпадений для каждого слова и каждого документа.

Ссылки по теме:

• Этот ответ демонстрирует defaultdict (int). defaultdict (список) работает почти так же.
• пример set.intersection