중첩 된 사전에서 분기 검색

Question

나는 각 노드가 하나의 단어 인 문장이있는 파이썬 중첩 사전 (기본적으로 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

아마도 가장 좋은 방법은 이미 구문 분석 된 분기를 최적화하기 위해 메모를 사용하는 깊이 우선 검색입니다.

이렇게하려면 가장 간단한 방법은 각 노드에 미리 서식이 지정된 모든 부모 노드를 저장하는 것입니다. 노드 a이 I have있을 것입니다 예를 들어, 노드 dog 등

, I have a이 방법은있을 것입니다, 당신은 여기서 n은 노드가 계산이다 더불어, O(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)