Поиск обычного запроса в инвертированном индексе

Question

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

{слово: {DOC_NAME: [location_list]}}

Для примера рассмотрим словарь можно назвать индекс, то для слова "спам", запись будет выглядеть следующим образом:

{спам: {Doc1.txt: [102300399], doc5.txt: [200587]}}

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

Теперь, мой вопрос: как реализовать обычный поиск запроса в этом индексе. то есть данный запрос, содержащий позволяет сказать 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 

Pls комментарий .... Thanx.

Answer 1

Вот начало:

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

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

Но

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, представляя эти списки имен документов в качестве наборов, а затем пересекая их для поиска общих имен документов.

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

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

• This answer demonstrates defaultdict(int). defaultdict (list) работает практически так же.
• set.intersection example