从嵌套字典中检索分支

Question

我有一个python嵌套字典（基本上是一个trie结构），带有句子作为分支 - 每个节点都是一个字。事情是这样的：

什么是检索根各分公司的提示（句子）的最有效方法是什么？也就是说，我想要所有可能的句子（我有一只狗，我有一支猎枪，我不喜欢猫王）。分支（句子）长度不是固定值。

Answer 1

你应该做一个深度优先搜索和递归产生句子的标记。 例如，使用一台发电机：

def yield_sentences(node): 
    if node.is_leaf(): 
     yield node.word 
    else: 
     for child in node.children: 
      for sentence in yield_sentences(child): 
       yield '{} {}'.format(node.word, sentence) 

用法：

>>> class Node(object): 
...  def __init__(self, word, *children): 
...    self.word = word 
...    self.children = children 
...  def is_leaf(self): 
...    return not self.children 
... 
>>> tree = Node('I', Node('have', Node('a', Node('dog'), Node('shotgun'))), Node("don't", Node('like', Node('Elvis')))) 
>>> #tree is now your example tree 
>>> list(yield_sentences(tree)) 
['I have a dog', 'I have a shotgun', "I don't like Elvis"] 

Answer 2

可能最好的方法是使用memoization优化已解析分支的深度优先搜索。

为此，最简单的方法是在每个节点中存储预先格式化的所有父节点。例如节点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)