python - 以相对顺序存储数据的高效数据结构

Question

我必须将一个句子连同该句子的可能片段一起存储到一个高效的数据结构中。目前，我使用字典，然后是字典的每个键的列表来存储段。我可以使用更好的数据结构来有效地存储相同的数据吗？我在下面详细说明了整个要求。

这里，句子以 pravaramuku.........yugalah 开头，没有任何背景色。编号为 1 到 24 的每个彩色框都是句子的片段。

现在我将以下内容存储如下

class sentence:
      sentence = "pravaramuku....."
      segments = dict()

键是框相对于句子的起始位置，值是存储每个框详细信息的对象。

    segments = {0: [pravara_box1, pravara_box10], 
7:[mukuta_box2], 
13:[manim_box3,maninm_box11,mani_box19,mani_box_25],...........}

如果其中一个盒子的 key 在 key 和 key+len(word in box) 之间，则两个盒子被认为是冲突的其他框的 (范围包括在内)。例如，方框 7 和方框 15 是冲突的，方框 3 和 11 也是如此。

在程序中，将选择其中一个盒子作为获胜者，这是通过魔术方法决定的。一旦选择了获胜者，其冲突框将被删除。再次选择另一个框，然后迭代继续，直到没有框剩余。

现在，如您所见，目前我的数据结构是一个字典，每个键都有一个列表作为其值。

什么是更好的数据结构来处理这个问题，因为目前消除冲突节点部分需要花费大量时间。

我的需求可以总结如下:

• 什么可以是一种有效的数据结构来存储以下数据以便进行更快的处理。

• 需要存储每个框的相对位置。有没有更好的方法来显式标记冲突节点(可能是 C 中的指针之类的东西)

• 这是一棵树，但没有顺序遍历，因为需要随机访问框，即需要调用任何框(使用 O(1))而不是从一个框到另一个框的遍历。

• 数据结构的创建是一次操作，因此整个插入过程可能很耗时，但是访问框和消除冲突节点需要重复进行，因此需要加快速度。

感谢任何可以部分解决我的问题的帮助。

Answer 1

看起来您可以在正确构造的树上进行回溯深度优先搜索:

sentence = "pravaramuku.........yugalah"
words = sentenceToWords(sentence)  # it seems like you already have this

tree = collections.defauldict(list)
for word in words:
    for i in (i for i in range(len(sentence)) if sentence[i:i+len(word)] == word):
        tree[i].append(word)

完成后，您只需要对树进行深度优先遍历:

def makeSentences(tree, pos=None, sofar=None):
    if pos is None: pos = 0
    if sofar is None: sofar = []
    if pos not in tree: print(' '.join(sofar))
    for word in tree[pos]:
        makeSentences(tree, pos+len(word), sofar+[word])

然后:

makeSentences(tree)