[박혜웅] 역파일 (inverted file)

• 역파일의 특징

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

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

  • 업데이트가 어렵다.

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

 

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

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

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

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

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

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

 

• 역파일 구성 예

 

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

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

 

• 렉시콘 파일용 구조체

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

  • 트라이

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

 

 

• 포스팅 파일용 구조체

  • 연결리스트

    • 임시포스팅파일에 사용

  • 배열

    • 정적포스팅파일에 사용

 

• 역파일 생성 방법