[박혜웅] 압축 트라이 (compressed trie)

• compressed trie

• • compact trie 에서 내부노드중 단일자식노드를 1개의 노드로 압축

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

  • 압축으로 인해 삭제되는 간선(edge)의 정보를 보존해야 함

    • B,I를 나타내는 간선이 압축될 경우, 압축된 간선은 BI 의 정보를 가지고 있어야 함.

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

 

• compact trie를 compressed trie로 압축하는 과정

  • compact trie

    • 
       

  • 내부노드중 단일자식노드를 1개의 노드로 압축

    • 
       

  • compressed trie

    •