[박혜웅] 패트리샤 트리 (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