자료구조 & 알고리즘

[박혜웅] 요약 파일 (signature file)

BAGE 2010. 3. 27. 18:08

  • 요약파일의 특징

    • 해시함수를 기반으로 한 단어기반의 색인구조
    • 비트형태의 요약기호(signature) 사용

    • 데이타가 정적인 경우(변하지 않는) 경우 주로 사용된다.

      • 예: 법률, DNS, 도서관, 광디스크

    • 여과(filtering)하는 작용을 한다.

      • 적합하지 않는 문서를 빠르게 걸러 내는데 사용.

    • 저장공간이 작다.

      • 색인어당 수 비트(bit)만 사용하기 때문
      • 색인어크기의 약 10%만 추가적으로 사용

    • 탐색시간이 데이타의 그 크기에 선형비례한다.

      • 데이타의 크기가 소,중형에 알맞다.

    • 중첩기호법

      • 문헌요약은 문헌에 포함된 단어의 요약을 OR 연산하여 생성한다.

    • 대부분의 경우 역파일 보다 성능이 안 좋다.

      • 업데이트는 매우 빠르다.

      • 허위드롭이 발생할 경우 이에 대한 처리 때문에 느리다.

        • 최종 후보 문서마다 패턴탐색을 하므로

 

  • 허위드롭(허위적중, false drop)

    • 문헌요약과 단어요약을 비교했을 때 포함(matching)되는 것으로 판단되지만, 실제로는 포함되지 않는 경우

    • 허위드롭가능성 Fd = 2-m

      • m(단어당 비트 수)가 커질 수록, 허위드롭 가능성은 낮아진다.
      • F=단어당 총 비트수 (요약을 표시하는데 쓰이는 총 비트수)
      • m = 단어당 비트 수 ( F개의 비트중 1이 세팅된 개수, m < F )

      • 허위드롭가능성을 줄이기 위해 문헌을 일정 단어개수 단위의 논리블럭으로 나눈다.

        • 많은 단어의 요약을 AND 하면, 대부분이 1로 세팅되어 허위드롭 가능성이 높아지므로

 

 

 

  • 단어의 부분검색을 하기 위한 방법

    • 모든 부분별로 색인을 생성한다.

      • 예: free -> fr, re ee 이런식으로 나눠서 각각 색인어로 지정

 

 

  • 요약파일의 처리과정

    1. 단어요약 생성

      • B개의 비트중 m개를 무작위로 1로 세팅함
      • 단어마다 다른 bit 배열로 생성

    2. 문헌요약(signature file)  생성

      • 문헌안에 포함된 단어의 요약을 OR 연산.

    3. 질의요약 생성

      • 질의안에 포함된 단어의 요약을 OR 연산.

    4. 문헌요약과 질의요약 비교(matching)

      • W & B = W
      • 질의요약과 문헌요약을 &연산을 하여 비트마스크(bit mask)생성
      • 비트마스크가 질의요약과 같다면, 해당 문헌이 질의어를 포함하고 있다고 추정가능 

    5. 허위드롭 탐지

      • 위와 같은 경우 D3 는 적합하지 않는 문서이므로, 따로 처리
      • 실제로 매칭된 모든 문서를 순차적으로 비교해야 함.

 

 

  • 순차요약파일

 

 

 

  • 순차요약파일의 개선 방안
  • 압축: 요약파일의 저장공간을 줄임

  • 수직분할: 주기억장치의 저장효율 개선

    • 컬럼별로 분할하여 필요한 컬럼에 해당되는 파일만 주기억장치로 저장
  • 수평분할: 탐색 개선
    • 비슷한 요약을 그룹핑

 

  • 요약파일의 분류

    • 분할안함: 순차요약파일 그대로 사용

      • 압축안함

        • 순차요약파일(SSF, Sequential Signature File)

      • 압축

        • 실행길이 부호화
        • 비트블럭 압축(BC, Bit-Block Compress)
        • 가변 비트블럭 압축(VBC, Variable Bit-Block Compress)

    • 수직분할

      • 압축안함

        • 비트분할 요약파일(BSSF)
        • 향상된 비트분할 요약파일(B'SSF)
        • 프레임분할 요약파일(FSSF)
        • 일반화된 프레임분할 요약파일(GFSSF)

      • 압축

        • CBS
        • DCBS
        • NFD

    • 수평분할

      • 데이타독립적 분할

        • Gustafson의 방법
        • 분할요약파일

      • 데이타의존적 분할

        • 2단계 요약팡리
        • S-트리

 

 

  • 순차요약파일의 압축

    • 유한한 허프만 코드

      • 실행길이 부호화
      • 1사이의 연속된 0의 개수 나열

    • 비트-블럭 압축(BC, Bit-Block Compression)

      • 순차요약파일과 같은 크기의 공간을 사용했을 때, 순차요약파일보다 허위드롭 가능성이 더 작다.

      • 비트-블럭의 크기가 고정이다.

        • 비트-블럭: 문헌요약안에
      • 부분 I: 1의 존재여부
      • 부분 II: 1의 개수 에서 마지막 비트만 0으로 표시
      • 부분 III: 1의 위치
      • 그림 4.6에서 압축된 최종결과=  01011 1000 00111000

 

 

  • 가변 비트-블럭 압축(VBC, Variable Bit-Block Compression)

    • 문헌요약에  1의 빈도에 따라 비트-블럭을 다르게 설정

 

  • 수직분할

    • 탐색속도 개선. 주기억장치의 저장효율 개선

    • BSSF, B'SSF

      • 비트단위로 분할
      • 분할과정

      • 검색과정

        • 질의 단어의 요약의 "1"비트 위치를 확인

          • 예: free( 001 000 110 010) 이라면, 확인할 비트는 3,7,8,11번째
        • 위의 모든 비트가 1인 문헌에 대해 검색

      • 삽입과정

        • 요약의 총비트 F 만큼 디스크 랜덤접근하여 기록
        • 각비트별로 분할되어 있기 때문에 지우고 다시쓰는 (rewrite)는 불필요

    • FSSF(프레임-슬라이스)

      • 문헌요약을 프레임단위로 나누고, 프레임단위로 단어요약이 저장되도록 함

        • 프레임단위로 파일을 나눔으로써 디스크 랜덤접근 수를 줄임

      • 분할과정


      • 검색과정

        • 질의 단어당 1프레임만 확인하여 질의요약과 같은지 확인한다.

      • 삽입과정

        • 총 프레임개수 만큼 디스크를 접근한다.

          •  예: 요약이 총 2프레임이면 2번 접근한다.

 

  • 수평분할

    •  탐색시간을 O(N)보다 빠르게 함.

      • 문헌요약에 대한 해싱함수를 만들어, 문헌을 그룹화