Эффективная структура данных для хранения данных с относительным упорядочением

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)