본문 바로가기

검색 엔진

[박혜웅] 역파일(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): 정렬된 (단어번호+문헌번호) 배열