[박혜웅] compact trie

• compact trie 의 특징

  • 잎 노드위의 단일자식노드를 제거한 trie

    • 단일자식노드: 자식노드가 1개 분인 노드
  • trie보다 저장공간, 탐색시간 절약

  • 탐색후, 질의어와 일치하는지 확인하는 과정 필요

    • 예: 질의어 black 일 경우 아래 그림에서 탐색은 성공하지만, 실제 색인어는 bluebird 이므로 결과에 표시하면 안됨

 

• compact trie 의 구조

  • 데이타: bluebird, bunting, cardinal, chicadee, godwit, goshawk, thrasher, thrush, wren
    

 

• trie를 compact trie로 변환

  • trie

    •  

      
      
      

  • 잎 노드위의 단일자식노드를 제거

    • 
       

  • compact trie

    •