'inverted index'에 해당되는 글 1건

  정보검색(IR. Information Retrieval)의 의미는 매우 광의적일 수 있다. 어쩌면 지갑에서 신용카드를 꺼내서 카드번호를 적는 그 자체도 정보검색의 일종이지만, 학계에서의 정보검색은 다음과 같이 정의가 된다.

  정보검색은 정형화되지 않은 세계에서 자료(일반적으로 문서들)을 찾는다. 보통 컴퓨터에 저장되어진 굉장히 큰 컬렉션 내의 정보욕구를 해결해준다..

  이런 의미로 정의됨으로, 정보검색은 소수(사서, 변호사 보조원, 전문적인 정보검색사)들에 의해 이용되어지는 것으로 여겨졌다. 현재 세상은 변하고 있다. 정보검색에 관여하는 수백만의 사람들이 매일 웹 검색엔진을 이용하고 자신의 이메일을 검색한다. 정보검색은 정보 접근의 지배적인 형태로 급속히 변화하고 있고 전통적인 데이터베이스 검색을 대체하고 있다.(  "미안하다, 당신의 주문 ID를 나에게 줘야만 당신의 주문서를 찾을 수 있다"라고 점원이 당신에게 말할 때와 같은 부류)

   또한, 정보검색은 위에서 언급한 핵심적 정의를 넘어서 다른 종류의 데이터나 정보 문제로까지 확장될 수 있다. "비정형화 데이터(unstructured data)"는 깔끔하지도, 의미적으로 명백하지도, 컴퓨터가 이해하기 쉬운 구조체이지도 않은 데이터를 말한다. "정형화된 데이터(structured data)"의 반대 의미이며, 중요한 산출물과 개인적인 레코드들을 사용하기 위해  회사의 관계된 데이터베이스가 전형적인 예이다. 사실, 어떠한 데이터도 비정형화된 데이터가 아니다. 만약, 여러분들이 인간 언어의 잠재적인 말을 생각한다면, 이것은 모든 텍스트 데이터에 대해 의미적으로 맞다는 것을 확인할 수 있다. 그러나, 의도된 개념 구조조차 명백한 구조라고 인정하고 있다. 대부분의 텍스트는 일반적으로 명백한 마크업에 의해 문서를 표현하는 머리말, 문단, 주석을 가진 구조이다. 정보검색은 또한 Java라는 단어가 있는 제목과 threading이 있는 본문을 가진 문서를 찾는 것처럼 "준정형화(semistructrued)" 검색을 용이하게 사용한다.

  정보검색의 분야는 브라우징 혹은 문서 컬렉션을 필터링 또는 검색된 문서 집합을 활용, 분석할려는 사용자들을 지원한다. 문서 집합이 주어졌을 때, 클러스터링(clustering)은 컨텐츠(검색된 문서 집합)를 기반으로 문서들을 적당한 그룹으로 분류하는 것이다. 서가에서 주제별로 책들을 정돈하는 것과 유사하다. 토픽 집합이 주어졌을 때, 분류화(classification)는 각각의 문서 집합이 어떤 클래스에 속하는지 정의하는 것이다. 이것은 처음에 수동으로 몇몇 문서들을 분류화함으로써 접근을 하고, 그 후론 자동적으로 새로운 문서들을 분류할 수 있도록 한다.

  정보검색 시스템은 연산을 하는 범위에 의해 구분되어질 수 있으며, 그것은 3개의 명백한 범위를 구분하는데 유용하다.

  웹 검색에서, 시스템은 수백만 대의 컴퓨터에 저장되어진 십억 개 이상의 문서들에 대해 검색을 제공한다. 주요 이슈는 색인을 위해서 문서들을 수집하는 것이 필요하다. 이러한 거대한 범위에서 효과적인 작업을 할 수 있는 시스템을 만들고, 웹의 특별한 면(하이퍼텍스트를 활용하는 것처럼)을 핸들링할 수 있으며, 검색엔진 랭킹을 올리기 위해 사이트 제공자가 페이지 컨텐츠를 조절할 만큼 어리석지 않아야 한다. 웹의 상업적 중요성을 시사하며 이것은 chapter 12-21에서 논의한다.

  다른 명백한 범위 중 하나는 개인정보검색이다. 최근 몇 년간 consumer operating systems들은 정보 검색을 통합하고 있다. (Apple's max OS X Spotlight나 Windows Vista's Instant Search). 이메일 프로그램은 일반적으로 검색 뿐만 아니라 텍스트 분류화 작업(classification)을 제공한다. 그것들은 적어도 스팸(junk mail) 필터를 제공하고, 일반적으로 특정한 폴더에 바로 이동시키는 분류화를 위해 수동적으로나 자동적인 방법을 제공한다. 주요 이슈는 전형적인 개인 컴퓨터에서 굉장히 많은 문서의 종류를 핸들링해야 하면, 검색 시스템의 유지, 보수는 무료여야 하고, 구동, 처리를 위해 충분히 가벼워야 하면, 소유자를 성가시게 하지 않고 하나의 기계에서 돌아가기 위한 디스크 공간을 사용해야 한다.

  이것들의 중간적인 의미로서, enterprise, instituional, domain-specific 검색이 있다. 회사의 내부 문서, 특허 데이터베이스, 생화학의 연구 논문과 같은 컬렉션을 검색한다. 이 같은 경우, 문서들은 전형적으로 중앙 집중하는 파일시스템에 저장되어진다. 이 책은 이러한 전체적인 범위 이상의 기술을 포함하지만 웹 검색에서의 몇몇 병렬/분산 검색과 같은 주제에 대해서는 상대적으로 조금만 다룰 것이다. 그러나, 소수의 웹 검색 회사 이외의 소프트웨어 개발자들은 대개 개인 검색과 enterprise 시나리오에 부닥칠 것이다.

  이번 chapter에서는 매우 간단한 정보검색의 문제로 시작한다. 그리고, term-document 배열의 아이디어(Section 1.1)와 역배열 구조체(Section 1.2)를 소개한다. Boolean retrieval model과 Boolean query는 어떻게 처리되는지(Section 1.3, 1.4)를 설명한다.

1.1 An example information retrieval problem

  많은 사람들이 소유한 장서 중 하나는 셰익스피어의 전집(Shakespeare's collected Works)이다. 당신이 이 책에서 Brutus와 Caeser라는 단어가 포함되고 Calpurnia라는 단어는 포함되지 않은 (Brutus AND Caeser AND NOT Calpurnia) 셰익스피어의 작품들을 확인하기를 원한다고 가정하자. 이것을 수행하기 위한 한 가지 방법은 처음부터 모든 텍스트를 읽는 것이다. Brutus와 Caeser가 포함되었는지 확인을 하되 Calpurnia가 포함되었다면 고려 대상으로부터 제외한다. 문서 검색의 가장 간단한 형태는 컴퓨터가 문서를 선형 스캔하는 것과 같은 방법을 행하는 것이다. 이러한 처리는 일반적으로 텍스트를 스캔하는 유닉스 명령어인 "grep"을 이용하여 grepping하는 것과 같은 방법을 추천한다. 텍스트를 grepping하는 것은 매우 효과적인 처리일 수 있다. 특히 주어진 현대 컴퓨터의 속도가 주어졌다면 말이다. 그리고 종종 정규 표현식을 통한 와일드 카드 패턴 매칭을 가능케 한다. 적당한 크기의 컬렉션의 간단한 쿼리를 위해 현대 컴퓨터가 있다면, 당신은 더 이상의 어떤 것도 필요치 않다. (셰익스피어의 전집의 크기는 전체적으로 100만 단어 이하이다.)
그러나, 더 많은 목적을 위해 여러분들은 더 많은 것이 필요로 한다.

1. 대용량 문서 컬렉션을 빨리 처리하기
   많은 온라인 데이터는 최소한 컴퓨터의 속도만큼이나 빨리 성장하고, 우리는 수 십억에서
   수 조의 단어가 있는 전체 컬렉션에서 검색할 수 있기를 원한다.
2. 좀 더 유연한 매칭 연산을 수행하기
   예를 들어, 쿼리 "Romans NEAR countrymen"은 grep을 이용해서 수행하기는
   비현실적다. (NEAR는 같은 문자 혹은 5단어 이내의 연산을 의미한다.)
3. 랭크된 검색을 수행하기
   많은 경우에 있어 당신은 특정 단어를 포함한 많은 문서들에서 최선의 답을 획득하기를
   원한다.

110100 AND 110111 AND 101111 = 100100

  이 쿼리에 대한 답은 "Antony and Cleopatra"와 "Hamle"이 된다. (그림 1.2)

  Boolean retrieval model은 정보검색의 한 모델이며 우리는 term들의 Boolean 표현의 형태로 어떤 쿼리를 취할 수 있다. 즉, term들은 연산 AND, OR, NOT을 이용하여 결합되어진다.
이 모델은 단어의 집합으로 각 문서들을 바라본다.
좀 더 현실적인 시나리오를 고려함과 동시에 몇몇 용어와 표기법에 대한 기회를 갖자. 우리는 N = 1 million 문서를 가지고 있다고 가정하자. 검색 시스템을 문서 단위로 구축하기로 결정했다. 문서들은 개인적인 메모들일 수도 있고, 책의 chapter일 수도 있다. (Section 2.1.2 - page 20에서 향후 다룬다.) 컬렉션으로서 검색을 수행하기 위해 문서의 그룹들을 참조한다. 때론 텍스트의 본문인 코퍼스(corpus)를 참조한다. 각 문서가 2-3페이지에 걸쳐 약 1,000개의 단어가 있다고 가정하자. 스페이스와 구두문자를 포함하여 단어당 평균 6byte라고 가정하면, 이것은 약 6GB의 문서 컬렉션이다. 전형적으로 이러한 문서에서 약 M = 500,000개의 서로 다른 term들이 있을 수 있다. 우리가 선택한 숫자에 대한 특별한 것은 아무 것도 없고, 그 숫자들은 크기나 그 이상의 것의 순서에 따라 변할 수 있지만, 그것은 우리가 다루어야 할 필요가 있는 갖가지 문제의 차원에 대한 몇몇 아이디어를 제공한다. 우리는 논의할 것이고 Section 5.1 (page 79)에서 이러한 크기를 가정하는 것을 모델링할 것이다.

  우리의 목표는 Ad-hoc 검색 임무를 가진 시스템을 개발하는 것이며, 이것은 가장 표준 IR의 임무이다. 시스템은 임의의 사용자 정보와 연관성이 있고 1회성의, 사용자 초기 쿼리의 의미로 시스템과 소통하는 컬렉션 내의 문서들을 제공해주는 것을 목표로 한다.

  필요한 정보는 사용자가 좀 더 알고자 하는 것에 대한 주제이며, 사용자가 필요한 정보를 획득하기 위한 시도로써 컴퓨터에 전달하는 쿼리로부터 차별되어진 것이다. 만일, 사용자가 개인적으로 필요한 정보에 부합한 정보의 가치를 포함한다고 여긴다면 문서는 연관성이 있다.
우리의 위의 예제는 필요한 정보가 특정 단어들로 정의되었다는 것은 다소 인위적이다. 반면, 일반적으로 사용자는 "파이프 누수"와 같은 주제에 관심이 있고 그들이 정확한 단어들(파이프 누수)를 사요하던지 "파이프 파열"과 같은 다른 단어를 씀으로써 개념을 표현하던지 상관없이 관련된 문서를 찾길 원한다. IR 시스템의 유효성(검색 결과의 질)에 접근하기 위해 일반적으로 사용자는 쿼리에 대한 시스템이 내주는 결과에 대한 2가지 주요 통계를 알고자 한다.

Precision (정확도) : 얼마만큼의 검색 결과가 필요하고자 하는 정보와 연관성이 있는가?
Recall (재현율) : 컬렉션에서 얼마만큼의 연관된 문서가 시스템에 의해 검색되었는가?

  Precision과 Recall을 포함한 연관성과 평가에 대한 기술된 논의는 chapter 8에서 다룬다.

  우리는 지금 원시적인 방법으로 term-document 행렬을 만들 수 없다. 500K X 1M 행렬은 너무 커서 컴퓨터 메모리에 적재하기 힘든 5천억 개의 0's와 1's를 가진다. 그러나 중요한 관점은 행렬이 너무 희박하다(Sparse Matrix). 즉 0이 아닌 엔트리가 극히 적다는 의미이다.  왜냐하면, 각 문서는 1,000개의 단어들로 구성이 되고, 그 행렬은 10억 개 이상의 1's를 가지지 않아서 구성원의 최소 99.8%가 0이다. 더 나은 표현법은 1의 위치만 기록하는 것이다.
 
 이 아이디어는 정보 검색에서 첫 번째 중요한 개념인 역색인(inverted idnex)의 핵심이다. 이름은 실제로 중복적이다. 색인은 항상 term에서 term이 발생한 문서의 일부분으로 거꾸로 매핑을 한다. 그럼에도 불구하고 역색인, 때론 역파일은 IR에서는 표준 용어로 사용되어지고 있다.


  역색인의 기본적인 생각은 그림 1.3에서 보여준다. 우리는 term들의 dictionary(때로 종종 vacabulary 나 lexicon처럼 언급한다. 이 책에서는 데이터 구조를 위해 dictionary를, term들의 집합을 vocabulary로 사용)를 유지할 것이고, 각 term은 term들이 발생한 문서의 레코드들을 리스트로 가진다. 리스트에서 각 아이템 - 문서에서 출현한 term의 레코드 (그리고, 향후에 종종 문서의 위치) -는 전통적으로 "posting"이라고 불리운다. 리스트는 "posting list (또는 inverted list)"라 불리우고, posting list들은 posting들을 참조한다. 그림 1.3에서 dictionary는 알파벳 순으로 정렬이 되어졌고, 각 posting list는 documen ID로 정렬되어진다. 우리는 이것이 Section 1.3에서 유용하다는 것을 알게 될 것이고 나중에 우리는 또한 이것의 사용 유무를 고려하게 된다. (Section 7.1.5)

** 다음 글 **
1.2 A first take at building an inverted index
1.3 Processing Boolean queries
1.4 The extended Boolean model versus ranked retrieval
1.5 References and further reading