[박혜웅] PAT tree

• PAT tree 의 정의

  • 텍스트의 모든 시스트링(sistring)으로 구성되는 patricia tree
  • 색인점을 단어나 구로 정할 경우 색인점(시스트링의 시작위치)의 개수는 20%로 감소한다.

  

• prefix searching (전위탐색)

  • 주어진 접두사(prefix)와 일치하는 모든 sistring을 검색

  • 검색과정

    1. 접두사를 모두 쓰거나, 외부노드(잎)에 도달할 때까지 탐색

    2. 최종적으로 skip된 비트를 비교해야 함

       • 아래의 그림에서 질의가 100, 101 일 때 결과는 같은 서브트리를 가리킨다.
       • 하지만 skip된 비트를 검사하면 101일 경우에는 결과가 없다는 것을 알 수 있다.
• • 
    
    

 

 

•  proximity searching (근사탐색)

  • 두개의 문자열사이에 일정범위의 다른 문자열이 포함된 모든 sistring 검색

  • 검색과정

    1. 두 문자열에 대한 subtree 탐색
    2. 작은 크기의 subtree를 정렬
    3. 각 위치 순서를 고려하며, 작은 subtree의 각 원소와 큰 subtree 원소를 검사
  • 
    
    

 

•  range searching(범위 탐색)

  •  두 문자열 사이에 포함되는 문자열을 사전편찬식으로 모두 검색

  • 범위탐색의 예

    • abc .. acc => acacia, abnormal  (abacus, acrimonious"는 포함도지 않음

  • 검색과정

    1. 두 문자열에 해당하는 양 끝원소를 탐색하고
    2. 양 끝원소를 포함하여 그 사이의 subree를 수집
  • 
    
    

 

 

• longest repetition searching(최장 반복 탐색)

  • 다른위치에서 가장 많은 문자가 반복되는 문자열을 탐색

  • 검색과정

    • skip bit를 고려하여 깊이가 가장 깊은 내부노드를 탐색하는 것과 같음
  • 내부노드에 가장 깊이가 큰 내부노드에 대한 정보를 1개의 비트로 보유하면 트리를 만드는 동안 미리 최장반복을 결정할 수 있다.
  • 
    
    

 

 

• most frequent searching (최빈탐색)

  • 주어진 길이 h 에 대해 가장 자주 반복되는 문자열 탐색

  • 검색과정

    • 루트로부터 h 깊이의 가장 큰 하위트리를 찾는것과 같음
  • 
    
    

 

 

• regular expression searching

  • 정규식으로된 질의에 해당하는 모든 원소를 검색

  • 검색과정

    1. convert the regular expression into a minimized DFA
    2. eliminate outgoing transitions from final states
    3. convert character DFA into binary DFA
    4. simulate the binary DFA on the binary digital trie
    5. for every node of the index associated with a final state, accept the whole subtree
  •  
    

• PAT tree의 구축

  • 문제점: 색인트리의 크기가 텍스트의 크기에 선형비례 O(n)

  • 해결방법

    • 외부노드를 bucket 에 저장

      • subtree의 모든 외부노드를 bucket으로 모아 한 곳에 저장
      • bucket내에서의 탐색과정이 추가적으로 필요
      • 
        
        

    • supernode를 이용하여 tree를 디스크 페이지 단위로 mapping

      • 내부노드 공간절약

      • 디스크 접근 회수 감소시킴

        • 한 개의 디스크페이지에 최대한 큰 트리를 집어 넣어 디스크 접근 회수를 감소시킴
      • 
        
        

 

 

• 배열로서 PAT tree

  • 방법

    • 모든 외부노드를 1개의 배열로  표현
    • 트리에서의 순서와 동일한 순서로 유지
    • 이진탐색으로 탐색 시간 최소화
    • 
      
      

  • 장점

    • 트리의 탐색방법을 대부분 보존
    • 예: 하위트리의 크기 검사시 시작과 끝위치를 찾고 그 차이를 계산

  • 단점

    • longest repetition searching(최장 반복 탐색) 불가

 

• PAT tree의 색인시간

  • n: 색인점수, t: 디스크 임의엑세스 시간
  • 색인시간 = n * logn * t

  • 사례

    • 옥스포드 영어사전의 색인

      • 1억 2천만 색인점, 초당 30회 디스크 접근
      • 구축시간=약 3.4년

 

• 배열로서 PAT tree 구축 해결방법

• • 주기억장치(메모리)내에서 색인구축

    • thrashing을 줄이기 위한 방법

      • thrashing: 운영체제의 페이징시스템에 의해, 페이지교체에 따른 주기억장치와 보조기억장치(디스크)간의 데이타 교체시간이 많이 걸리는 현상
• quick sort 이용: 정렬된 파일에 대하여 순차적 엑세스를 하므로 구축에 적합한 알고리즘

• 대규모 Pat array를 소규모로 합병

  1. 텍스트를 작은 조각으로 분리
  2. 첫번째 조각(주메모리의 1/2크기)을 주메모리에서 색인

  3. n-1번째 조각(큰조각)과 n번째 조각(작은조각)을 합병

     • 계수기 이용: 큰 조각에서 작은 조각의 일부를 넣을 위치 목록
•