1.2 A first take at building an inverted index

아직 시작 단계인데, 벌써 겁이 나기 시작합니다.
너무나 미약한 영어 실력에 막히는 곳이 한 두 군데가 아니고,
우리말로 표현하자니 의미 전달이 잘 안 되는 단어들도 존재하구...
직역을 고집하여 작성을 하고 있으나, 의역이 필요한 곳도 있고...
새삼 번역 일이라는게 쉽지 않은 일이구나 라는 걸 느낍니다.

1.2 A first take at building an inverted index

검색시 색인 속도에 대한 이점을 획득하기 위해 우리는 향상된 색인을 구축해야 한다. 이것은 중요한 단계들은
   1. 색인되어질 문서들을 수집 
     

   2. 텍스트들을 토큰화, 각 문서들을 토큰들의 리스트로 변환
     

   3. 언어학적으로 전처리, 색인화될 term들의 일반화된 토큰들의 리스트로 처리
     

   4. dictionary와 posting들로 구성된 역색인을 구축하는 것으로 각 term이 발생하는
      문서를 색인

우리는 앞선 처리 단계(1-3 단계)에 대해서 Section 2.2에서 정의하고 논의한다. 그때까지 여러분들은 토큰들(tokens)과 일반화된 토큰들(normalized tokens)을 단어들(words)과 대충 유사하다고 생각할 수 있다. 여기서, 우리는 첫 3개의 단계가 벌써 이루어졌다고 가정을 하고 정렬화된 색인에 의해 기본적인 역색인을 구축하는 것을 시험한다.

 문서 컬렉션 내에서 우리는 각 문서가 document identifier(docID)라고 알려진 유일한 순차적인 숫자를 가진다고 가정한다. 색인 구축 동안 우리는 간단하게 연속적인 정수를 처음으로 만나게 되는 각 문서에 할당할 수 있다. 색인 생성시 입력 값은 그림 1.4와 같이 term과 각 문서의 쌍의 리스트로서 생각할 수 있는 각 문서에 대해 일반화된 토큰들의 리스트들이다. 핵심 색인 단계는 그림 1.4의 중간 세로 줄에서 표현된 것처럼 term들이 알파벳 순이 되도록 이런 리스트들을 정렬하는 것이다. 똑같은 문서에서 동일한 term이 중복 발생이 되는 것은 합병되어질 수 있다. 그림 1.4의 오른쪽 세로줄에서 보여주듯이, 동일한 term이 그룹화되어지는 대신 그 결과는 dictionary와 posting으로 나뉘어진다. 일반적으로 term은 수 많은 문서에서 발생하기 때문에 이러한 데이터 구조화는 색인이 요구하는 저장공간을 감소시킨다. 또한 dictionary는 각 term을 포함하는 문서의 개수(각 posting list의 길이인 document frequency)와 같은 몇몇 통계를 기록한다. 이러한 정보는 기본적인 Boolean 검색 엔진에서는 그리 중요하지 않지만, 질의시 검색엔진의 성능을 향상시키며, 많은 랭킹 검색 모델(Ranked Retrieval Model)에서 향후 사용되어지는 통계이다.

Posting은 2차적으로 docID에 의해 정렬되어진다. 이것은 효과적인 질의 처리를 위해 기본이다. 이러한 역색인 구조는 본질적으로 Ad-hoc 텍스트 검색을 지원하는 가장 효과적인 구조체로서 경쟁 대상이 없다.
 색인 결과를 저장하기 위해서 2개의 dictionary와 posting list를 위한 저장 공간이 필요하다. 후자는 더 크지만, dictionary는 일반적으로 메모리상에서 관리를 하고, posting list들은 디스크상에서 관리를 한다. 그래서 각각의 크기는 중요하다. Chapter 5에서, 우리는 저장공간을 어떻게 잘 활용할 것이며 효과적으로 어떻게 접근할 것인지에 대해 시험한다. 어떤 데이터 구조체를 posting list를 위해 사용할 것인가? 고정된 길이의 배열은 낭비다. 몇몇 단어들은 많은 문서에서 발생하고, 어떤 단어들은 매우 적게 출현한다. 메모리상의 posting list를 위해서 singly linekd lists와 가변 길이 배열(variable length array)가 2가지 좋은 선택이다. singly linked list는 posting list에 문서 삽입 비용을 효과적으로 한다. (웹 문서를 재수집시 업데이트된 문서를 업데이트) 자연스럽게 추가적인 포인터를 요구하는 리스트를 건너 띔으로써 좀 더 향상된 색인 전략으로 확대할 수 있다.

 가변 길이 배열은 포인터와 요청에 대한 오버헤드를 피할 수 있어 공간 요구에 대해 효과적이다. 왜냐하면, 그들의 인접한 메모리를 사용하는 것은 메모리 캐쉬로 인해 최근 프로세서는 속도를 향상시킬 수 있다. 여분의 포인터는 실제로 옵셋처럼 리스트들로 인코딩되어질 수 있다. 만일, 업데이트가 상대적으로 드물다면 가변 길이 배열은 찾기에 더 간결하고 빨라진다. 또한 우리는 각 term에 대해 고정 길이 배열의 리스트를 연결하는 혼합 체계를 사용할 수 있다. Posting list들이 디스크상에 저장되었을 때 그것들은 그림 1.3과 같이 포인터없이 인접하게끔 (아마 압축 형태로) 저장되어진다. 그렇게 함으로써, posting list의 사이즈를 줄일 수 있고 메모리 상에서 posting list들을 읽기 위해 찾을 수 있다.

Exercise 1.1 다음 문서 컬렉션을 위해 구축되어질 역색인을 그려라. (예제로 그림 1.3을 보라)
          Doc 1   new home sales top forecats
          Doc 2   home sales rise in july
          Doc 3   increase in home sales in july
          Doc 4   july new home sales rise

Exercise 1.2 이러한 문서들을 가정하자.
          Doc 1   breakthrough drug for schizophrenia
          Doc 2   new schizophrenia drug
          Doc 3   new approach for treatment of schizophrenia
          Doc 4   new hopes for schizophrenia patients

                a. 문서 컬렉션을 위해 term-document 접속행렬(incidence matrix)를 그려라.
                b. 6 페이지의 그림 1.3과 같이 이 컬렉션을 위해 역색인 표현을 하라.

Exercise 1.3  Exercise 1.2에서 보여준 문서 컬렉션에서 다음과 같은 질의어에 대한 결과는 무엇인가?
          a. schizophrenia AND drug
          b. for AND NOT (drug OR approach)

** 이전 글 **
Introduction
1.1 An example information retrieval problem

** 다음 글 **
1.3 Processing Boolean queries
1.4 The extended Boolean model versus ranked retrieval
1.5 References and further reading