使用python在文件中写入b-tree

Question

有一些文档需要索引，这意味着我需要读取文档，提取单词，并通过存储它们出现在哪个文档和哪个位置来对它们进行索引。

对于每个单词，我最初都创建了一个单独的文件。考虑两个文档：

文档1

The Problem of Programming Communication with

文档2

Programming of Arithmetic Operations

所以会有10个单词，8个唯一的。所以我创建了8个文件。

使用算术运算对通信编程的问题

在每个文件中，我将存储它们出现在哪个文档和位置。我正在实现的实际结构有更多的信息，但这个基本结构将服务于目的。

文件名文件内容

1 1

问题1 2

共1 3 2 2

编程1 4 2 1

通信1 5

有1个6

算术2 3

操作2 4

意思是。单词位于第一个文档-第三个位置和第二个文档-第二个位置。

在初始索引完成后，我将把所有文件连接到一个索引文件中，并在另一个文件中存储将找到特定单词的偏移量。

索引文件：

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树作为索引文件的结构，这样我就可以动态地更改文件内容并以某种方式更新偏移量？如果是这样，有人可以指导我一些教程或库是如何工作的，或者解释一下我如何实现它？

非常感谢您花时间阅读了这么长的一篇文章。

编辑:我不知道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

一种选择是使用字典来组织数据，并使用cPickle将其转储到文件中。