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

Question

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

最初我为每个单词创建了一个单独的文件。考虑 2 个文档:

文档 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

意义。该词位于 ar 1st document-3rd position 和 2nd document-2nd position.

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

索引文件:

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 因为它是轻量级的。