본문 바로가기

자료구조 & 알고리즘/트라이(Trie)

[박혜웅] 패트리샤 트리 (patricia tree)

  • patricia tree의 특징

    • "Practical algorithm to retrieve information coded in alphanumerical" 논문에서 유래

      • 자,영어로 기록된 정보를 검색하기 위한 실용적인 알고리즘"
    • 압축된 접미트리(compressed suffix tree) 라고도 한다(????)
    • 단일자손 노드를 제거한 binary trie

      • binary trie에서 skip-counter(스킵계수기)또는 위치번호(bitNumber)를 이용하여 높이를 줄인 구조

        • = binary trie를 compact, compressed 한 구조
    •  patricia tree는 내부노드와 외부노드로 구성됨.

      • n= 키값의 수 = 접미부분의 시작위치
      • 내부노드(분기노드): 다음 검사할 노드의 위치 및 skip 정보

        • 내부노드는 n-1개로 구성
      • 외부노드(데이터노드): 텍스트에서의 위치를 나타냄

        • n개의 키값으로 구성

 

  • 패트리샤트리의 구조

    • binary trie와 patricia tree의 비교

      • binary trie

          

      • patricia tree