用於以相對順序存儲數據的高效數據結構

我必須將句子連同句子的可能的句子一起存儲到有效的數據結構中。目前，我使用字典，然後使用詞典的每個鍵的列表來存儲分段。我可以使用更好的數據結構來有效地存儲它們嗎？我已經詳細介紹了下面的全部要求。用於以相對順序存儲數據的高效數據結構

這裏，句子開頭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）），而不是從一個到另一個。
數據結構的建立是一個單一的時間的操作，並且因此整個插入過程可以是時間服用，但訪問所述箱並消除衝突節點需要被重複地進行，因此需要加快那裏。

任何可以部分解決我的問題的幫助表示讚賞。

來源

2016-07-22 Amrith Krishna

也是盒子3和11也是衝突？ – inspectorG4dget

@ inspectorG4dget - 是的，他們也有衝突。我提到的範圍是包容性的。感謝您指出。 –

那麼基本上，沒有兩個盒子可以聲稱相同的索引？ – inspectorG4dget

好像你可以逃脫以正確的方式構建樹回溯深度優先搜索：一旦這樣做了

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)

來源

2016-07-22 04:33:16 inspectorG4dget

用於以相對順序存儲數據的高效數據結構

回答

相關問題