바게의 정보검색

요약파일의 특징

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

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

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

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

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

• 저장공간이 작다.

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

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

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

• 중첩기호법

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

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

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

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

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

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

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

• 허위드롭가능성 F_d = 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)보다 빠르게 함.

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

     

접두 B+트리의 특징

• 갱신비용이 작고, 탐색시간이 빠름
• 저장공간 많이 소모
• 구현이 어려움
• 텍스트 색인에 사용

접두 B+트리의 구조

• 키: 다음 레벨의 키와 구분되는 최소의 문자들(단어의 일부, 접두어)

• 잎노드: 단어 저장

  • 단어(알파벳)
  • 빈도
  • 포스팅위치

역파일의 특징

• 단어번호, 문헌번호에 대해서 순서대로 정렬한다.

  1. 단어번호에 대한 정렬은 질의어(검색어)와 연관된 문서집합을 찾는데 사용
  2. 문헌번호에 대한 정렬은 검색어가 여러 단어일 경우, 각각의 단어에 대한 문서집합 간의 연산(merging)을 위해 필요함
• 구현은 쉽다.

• 업데이트가 어렵다.

  • 정렬된 상태를 유지해야하므로

역파일의 구성 = 렉시콘 + 포스팅렉시콘 파일 (lexicon, 색인어 목록, 사전)

• • 색인어
  • 문서빈도(총 빈도, 포스팅 개수)
  • 포스팅위치

• 포스팅 파일 (문헌정보 파일)

  • 문헌식별자(문서ID, 문헌번호) 목록

  • 문헌내의 단어 위치(선택사항)

    • 근접연산시에만 사용
    • 블럭, 단어, 글자단위 위치
  • 문헌내의 단어 빈도(선택사항)

렉시콘에 포함되지 않는 글자 또는 단어

• 불용어 목록: 관사,전치사등
• 색인될 필요가 없는 문자열: 숫자등
• 단어 구분의 규칙이 되는 문자: 공백, 마침표등

렉시콘 파일용 구조체

• 정렬된 배열
• 접두 B+트리
• 접두 B트리

• 트라이

  • 패트리샤트리
• 해시
• 여러 구조체의 조합

포스팅 파일용 구조체

• 연결리스트

  • 임시포스팅파일에 사용

• 배열

  • 정적포스팅파일에 사용