我有一个 python 嵌套字典(基本上是一个 trie 结构),以句子为分支 - 每个节点都是一个单词。像这样的东西:
检索从根到提示(句子)的所有分支的最有效方法是什么?也就是说,我想要拥有所有可能的句子(我有一只狗,我有一把猎枪,我不喜欢猫王)。分支(句子)长度不是固定值。
最佳答案
您应该进行深度优先搜索并递归地生成句子的标记。 例如,使用生成器:
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"]
关于python - 从嵌套字典中检索分支,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17080894/