Запись b-дерева в файл с использованием python

Question

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

Для каждого слова изначально создаю отдельный файл. Рассмотрим 2 документа:

документ 1

The Problem of Programming Communication with 

документ 2

Programming of Arithmetic Operations 

Так что будет 10 слов, 8 уникальных. Поэтому я создаю 8 файлов.

проблема из программирования Communications с арифметических операций

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

содержимое файла имя файла

проблема 1 2

программирование 1 4 2 1

связи 1 5

с 1 6

арифметическая 2 3

операции 2 4

Значение. слово расположено на 1-й позиции-3-й позиции и 2-м документе-2-й позиции.

После того, как начальный индекс будет выполнен, я объединю все файлы в один индексный файл, а в другом файле храню смещение, в котором будет найдено определенное слово.

индексный файл:

1 1 1 2 1 3 2 2 1 4 2 1 1 5 1 6 2 3 2 4 

смещение файла:

the 1 problem 3 of 5 programming 9 communications 13 with 15 arithmetic 17 operations 19 

Так что, если мне нужно указательным данные о связи я Гото 13 положение файла и читать ДО (исключая) 15-е место, в другими словами, смещение следующего слова.

Все это нормально для статического индексирования. Но если я сменил один индекс, весь файл нужно будет переписать. Могу ли я использовать b-дерево в качестве структуры индексного файла, чтобы я мог динамически изменять содержимое файла и как-то обновлять смещение? Если да, то кто-нибудь может привести меня в какой-то учебник или библиотеку, как это работает, или объяснить немного о том, как я могу это реализовать?

Большое спасибо за то, что нашли время, чтобы прочитать такой длинный пост.

EDIT: Я не знал о различии между B-деревом и двоичным деревом. Поэтому я сначала задал вопрос, используя бинарное дерево. Теперь это исправлено.

Answer 1

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

Вот пример кода, который делает это:

import shelve 

DOC1 = "The problem of Programming Communication with" 
DOC2 = "Programming of Arithmetic Operations" 

DOC1 = DOC1.lower() 
DOC2 = DOC2.lower() 

all_words = DOC1.split() 
all_words.extend(DOC2.split()) 
all_words = set(all_words) 

inverted_index = {} 

def location(doc, word): 
    return doc[:doc.find(word)].count(' ') + 1 


for word in all_words: 
    if word in DOC1: 
     if word in inverted_index: 
      inverted_index[word].append(('DOC1', location(DOC1, word))) 
     else: 
      inverted_index[word] = [('DOC1', location(DOC1, word))] 
    if word in DOC2: 
     if word in inverted_index: 
      inverted_index[word].append(('DOC2', location(DOC2, word))) 
     else: 
      inverted_index[word] = [('DOC2', location(DOC2, word))] 

# Saving to persistent object 
inverted_index_file = shelve.open('temp.db') 
inverted_index_file['1'] = inverted_index 
inverted_index_file.close() 

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

>>> import shelve 
>>> t = shelve.open('temp.db')['1'] 
>>> print t 
{'operations': [('DOC2', 4)], 'of': [('DOC1', 3), ('DOC2', 2)], 'programming': [('DOC1', 4), ('DOC2', 1)], 'communication': [('DOC1', 5)], 'the': [('DOC1', 1)], 'with': [('DOC1', 6)], 'problem': [('DOC1', 2)], 'arithmetic': [('DOC2', 3)]} 

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

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

Answer 2

Одним из вариантов было бы использовать dicts для структурирования ваших данных и использования cPickle, чтобы выгрузить его в файл.