我有一個python嵌套字典（基本上是trie結構），其中的句子作為分支-每個節點都是一個單詞。像這樣的東西： 從根到技巧（句子）檢索所有分支的最有效方法是什么？也就是說，我想擁有所有可能的句子（我有一只狗，我有a彈槍，我不喜歡貓王）。分支（句子）長度不是固定值。
3 回答
墨色風雨
TA貢獻1853條經驗 獲得超6個贊
做到這一點的最佳方法可能是使用記憶來優化已解析分支的深度優先搜索。
為此，最簡單的方法是在每個節點中存儲所有已格式化的父節點。例如，該節點a將具有I have，該節點dog將具有I have a等等。
這樣，您將能夠提取O(n)復雜的所有分支，其中n是節點數。但是，這需要對結構進行一些修改。
例如
class Node(dict):
def __init__(self,parent,value,parent_str):
self.parent = parent
self.value = value
self.children = {}
parent.children[value] = self
self.parent_str = parent_str+' '+value
def __repr__(self):
return self.parent_str+' '+value
def addChild(self,value):
Node(self,value,self.parent_str)
添加回答
舉報
0/150
提交
取消