непонимание алгоритма спими

Я пытаюсь реализовать индексатор в памяти за один проход в C ++

Но в алгоритме я думаю, что что-то не так или (скорее всего) у меня неправильное понимание

SPIMI-INVERT(token_stream)
output_file = NEWFILE()
dictionary = NEWHASH()

while (free memory available)
token ← next(token_stream)
if term(token) ∈ dictionary
then postings_list = ADDTODICTIONARY(dictionary, term(token))
else postings_list=GETPOSTINGSLIST(dictionary,term(token))
if full(postings_list)
then postings_list = DOUBLEPOSTINGSLIST(dictionary, term(token))

ADDTOPOSTINGSLIST(postings_list, docID(token))
sorted_terms ← SORTTERMS(dictionary)
WRITEBLOCKTODISK(sorted_terms,dictionary,output_file)
return output_file

Давайте предположим, что я сделал все разборы и превратил все документы в поток жетоны где жетоны являются term,doc_id пары

http://nlp.stanford.edu/IR-book/html/htmledition/single-pass-in-memory-indexing-1.html говорит, что функция SPIMI-INVERT вызывается для каждого блока.

Хорошо, тогда начнем,

  • мы читаем поток блок за блоком, так что теперь у меня есть один блок и
    отправил его через функцию SPIMI-INVERT в качестве аргумента
  • функция выполняет некоторую обработку с токеном для словаря

как-то (может быть, потому что словарь слишком большой) у нас нет свободного
память больше, когда мы находимся в цикле while.

  • Алгоритм прерывает цикл и записывает текущий словарь в
    диск.

Но из внешнего мира (как вызывающая функция) я понятия не имею, если
блок, который я отправляю как аргумент, обрабатывается полностью или нет. Не так ли
думаете, что здесь что-то не так?

1

Решение

Поскольку пока нет ответа, и после разговора с моим профессором я отвечаю на мой вопрос.

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

поток токенов — это файл, который включает токены (термин, пара идентификатора документа)

while (there is token in token stream)
dict = new dictionary()
while(there is free memory available)
token = next_token()
dict.add_to_postingList(token)
write_dict_to_file(dict)
delete dict

//Assuming posting list is dynamically sized and dictionary knows if a term exist.

Вот Я реализовал это в C ++, может быть полезным

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]