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

• 기본적인 방법

  • 특징

    • 배열을 이용하여, 단어를 나열하고 정렬한 후, 합병한다.
    • 시간,색인공간의 비용이 크다.
    • 소형 데이타에 유리

  • 과정

    1. 파싱

       • 텍스트를 단어목록으로 분할한다.
       • 문서별 단어목록, 문서에 대한 단어별 가중치 계산

    2. 정렬

       • (단어+문헌번호)목록을 알파벳순 정렬

    3. 합병(중복제거) 및 가중치(총빈도수) 부여

       • (단어+문헌번호+빈도수)목록으로 합병
       • 같은 문헌을 가리키는 같은 단어의 빈도수를 합침
    4. 재배열 또는 압축

  • 결과

    • 렉시콘: 정렬된 배열(단어+총빈도수+포스팅위치)
    • 포스팅: 배열(문헌번호+빈도수)

 

 

 

 

• 비정렬 역파일 생성 방법

  • 특징

    • 이진트리를 사용하여, 단어를 추가하면서 정렬이 되므로 추가적인 정렬이 불필요
    • 시간, 색인공간의 비용이 작다.
    • 중대형 데이타에 유리

  • 과정

    1. 파싱

    2. 임시용 생성(정렬하지 않음)

       • 단어목록: 우측으로 쏠린 이진트리,

         • 노드= 단어+포스팅개수+포스팅위치(머리/꼬리)
       • 임시포스팅: 연결리스트
    3. 단어목록(이진트리)를 순회하며 가중치(총빈도수) 계산

  • 결과

    • 렉시콘: 정렬된 배열(단어+총빈도수+포스팅위치)
    • 포스팅: 배열(문헌번호+빈도수)

 

• 고속 역알고리즘(FAST-INV)

• • 특징

    • 주기억장치를 이용하여, 주기억장치내에서 처리할 수 있는 양만큼 작업을 분리하고 이 결과를 합병 
    • 문헌벡터파일이 이미 정렬되어 있기 때문에 작업을 분리할 수 있음._(바게주)
    • 주기억장치가 어느정도 크다고 가정. 주기억장치가 클수록 유리.

  • 자료구조

    • 문헌벡터 파일(document vector files)

      • 문헌번호+단어번호(개념번호)으로 정렬된 파일

    • 로드테이블(작업목록, load table)

      • 각 작업에서사용할 문헌벡터파일의 튜플(문헌번호,단어번호) 범위

      • 로드(작업): 주기억장치에서 한번 처리할 작업. 각 작업량의 범위를 정의

         

    • 개념(단어)포스팅/포인터(concept postings/ptrs)

      • 각 작업에서 단어별로 참조하는 문헌벡터파일의 튜플(문헌번호,단어번호) 범위

    • 문헌벡터 로드파일(document vector loads files)

      • 로드별로 분할된 문헌벡터파일
  • 과정

  • 1. 준비

       • 주기억장치보다 작은 메모리를 사용하도록 작업의 수를 나눠 로드테이블에 저장.
       • 문헌벡터 파일로부터 로드테이블과 개념포스팅/포인터(CONPTR) 파일을 생성

    2. 분할

       • 문헌벡터파일과 로드테이블로부터 문헌벡터로드파일 생성

    3. 도치

       • 각 작업별로 반복하여 문헌벡터 로드파일로부터 작업별 역파일을 생성한다.

  • 결과

    • 역파일(inverted file): 정렬된 (단어번호+문헌번호) 배열