从嵌套字典中检索分支

Question

我有一个python嵌套字典（基本上是trie结构），其中的句子作为分支-每个节点都是一个单词。像这样的东西： 从根到技巧（句子）检索所有分支的最有效方法是什么？也就是说，我想拥有所有可能的句子（我有一只狗，我有a弹枪，我不喜欢猫王）。分支（句子）长度不是固定值。

Answer 1

做到这一点的最佳方法可能是使用记忆来优化已解析分支的深度优先搜索。

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