Python에서 자동 완성을 지원하는 Trie 구현

Question

웹 사이트에서 자동 완성을 지원하는 데이터 구조를 구현하려고합니다. Trie의 반복 버전을 구현할 수있었습니다. Trie에서 추가 및 검색하는 두 가지 기본 방법을 지원합니다. 그러나 이제 다음 접두사로 시작하는 모든 단어를 반환하는 메서드를 추가해야합니다. 누군가가 이것으로 나를 도울 수 있습니까?

class Trie: 
    def __init__(self): 
     self.root = TrieNode() 

    def insert(self, word): 
     curr = self.root 
     for letter in word: 
      node = curr.children.get(letter) 
      if not node: 
       node = TrieNode() 
       curr.children[letter] = node 
      curr = node 
     curr.end = True 

    def search(self, word): 
     curr = self.root 
     for letter in word: 
      node = curr.children.get(letter) 
      if not node: 
       return False 
      curr = node 
     return curr.end 

    def all_words_beginning_with_prefix(self, prefix): 
     #I'm not sure how to go about this one. 

Answer 1

다른 방법과 동일한 방식으로 접두사에 따라 Trie를 반복하는 발전기를 구현할 수 있습니다.

class TrieNode: 
    def __init__(self): 
     self.end = False 
     self.children = {} 

    def all_words(self, prefix): 
     if self.end: 
      yield prefix 

     for letter, child in self.children.items(): 
      yield from child.all_words(prefix + letter) 

class Trie: 
    # existing methods here 
    def all_words_beginning_with_prefix(self, prefix): 
     cur = self.root 
     for c in prefix: 
      cur = cur.children.get(c) 
      if cur is None: 
       return # No words with given prefix 

     yield from cur.all_words(prefix) 

trie = Trie() 
trie.insert('foobar') 
trie.insert('foo') 
trie.insert('bar') 
trie.insert('foob') 
trie.insert('foof') 

print(list(trie.all_words_beginning_with_prefix('foo'))) 

출력 : 접두사의 끝에서 노드를 발견하면 터미널 노드가 발견 될 때 접두사를 추적하고 항복하면서 서브 트라이 반복하는 yield from와 재귀 생성기를 사용할 수 있습니다 :

['foo', 'foob', 'foobar', 'foof']