• compressed trie

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

      • 단일자식노드: 자식노드가 1개 분인 노드
    • trie, compact trie 보다 저장공간, 탐색시간 절약
    • 압축으로 인해 삭제되는 간선(edge)의 정보를 보존해야 함

      • B,I를 나타내는 간선이 압축될 경우, 압축된 간선은 BI 의 정보를 가지고 있어야 함.
    • 탐색후, 질의어와 일치하는지 확인하는 과정 필요

 

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

    • compact trie

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

      •  
    • compressed trie

      •  


Posted by 바게 BAGE

댓글을 달아 주세요

  1. BlogIcon mimimimamimimo

    관리자의 승인을 기다리고 있는 댓글입니다

    2019.10.07 11:19 [ ADDR : EDIT/ DEL : REPLY ]