본문 바로가기

자료구조 & 알고리즘

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

  • 역파일의 특징

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

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

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

 

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

      • 색인어
      • 문서빈도(총 빈도, 포스팅 개수)
      • 포스팅위치
    • 포스팅 파일 (문헌정보 파일)

      • 문헌식별자(문서ID, 문헌번호) 목록
      • 문헌내의 단어 위치(선택사항)

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

 

  • 역파일 구성 예


 

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

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

 

  • 렉시콘 파일용 구조체

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

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

 

  • 포스팅 파일용 구조체

    • 연결리스트

      • 임시포스팅파일에 사용
    • 배열

      • 정적포스팅파일에 사용

 

  • 역파일 생성 방법