정보검색론 공부 - Boolean 검색

• 정보검색
• 대규모 정보군(일반적으로 컴퓨터에 탑재되어 있는 형태)으로부터 정보 요구를 충족시키는 비구조적인 속성(일반적으로 텍스트)을 지닌 자료(일반적으로 문헌)를 찾아내는 것
• 비구조화된 자료(Unstructured data)
• 의미적으로도 불명확하여 컴퓨터가 이해하기 어려운 형태의 자료를 의미하며, 구조화된 자료(Structured data)의 반대 의미임
• 현실적으로 자료 자체가 비구조화된 구조는 거의 없으며, 명시적 마크업(Explicit markup)인 반구조화된 자료(Semi-structured data)로 구성됨
• 규모별 정보검색 시스템 구분
• 웹 검색(Web search)
• 색인 대상 문헌을 수집, 엄청난 규모에서도 효율적으로 작동, 웹의 고유한 측면을 다루는 것 등의 다양한 이슈들을 포함하는 정보검색 시스템으로 수백만 대의 컴퓨터에 저장된 수십억 건 이상의 문헌들을 검색할 수 있게 해야 함
• 개인 정보 검색(Personal information retrieval)
• 개인 수준에서 수행하는 정보검색 시스템으로 메일 필터링, 컴퓨터의 문헌 관리 등의 이슈들을 포함
• 기업, 기관 등의 특정 영역
• 규모적으로 웹과 개인정보의 중간에 있는 정보검색 시스템 구분으로 회사의 내부 문헌, 연구 논문 등과 같은 문헌 집단을 대상으로 하여, 일반적으로 문헌들은 중앙 집중형 파일 시스템에 저장되고, 하나 또는 소수의 전용 시스템이 컬렉션에 대한 검색을 지원함

1.1 정보 검색 문제

• 정보 검색에서 추가적인 기법이 필요한 경우
• 대용량 문헌 컬렉션의 신속한 처리
• 보다 융통성 있는 매칭 연산
• 순위가 부여된 검색 결과 제공
• 색인(Index)
• 순차적 스캔을 방지하기 위한 방법
• 용어(Term)
• 일반적으로는 단어를 단위로 가짐
• 발생 행렬(Incidence matrix)
• 단어에 대해 해당 문헌이 각 단어를 포함하고 있는지 아닌지를 기록하기 위한 하나의 방법
• Boolean 검색 모델(Boolean retrieval model)
• Boolean 논리식 형태로 모든 질의를 작성할 수 있는 정보 검색 모델로, 질의식을 구성하는 용어들은 AND, OR, NOT 연산자로 결합됨
• 문헌(Document)
• 어떤 단위가 되었든지 간에 하나의 검색 시스템을 구축하기로 결정한 기반 단위
• 컬렉션(Collection) = 말뭉치(Corpus)
• 검색 대상이 되는 문헌의 집단
• 단순 검색(Ad hoc retrieval)
• 가장 전형적인 정보 검색 작업으로 임의의 사용자가 던진 질의를 한 번에 하나씩 시스템에 전달하여, 사용자의 정보 요구에 적합한 문헌을 컬렉션에서 찾아 제공하는 것
• 정보 요구(Information need)
• 사용자가 더 알아보고자 하는 주제이며, 질의와는 다름
• 질의(Query)
• 사용자의 정보 요구를 컴퓨터에 전달하기 위해 사용자가 표현하는 것
• 적합 문헌(Relevant document)
• 사용자의 정보 요구와 관련하여 가치 있는 정보를 수록하고 있다고 사용자가 판단한 문헌
• 유효성(Effectiveness)
• 정보 검색 시스템에서 결과의 적합성에 대한 평가로 다음의 두 가지 핵심적인 통계량으로 나타낼 수 있음
• 정확률(Precision): 반환된 결과 중 정보 요구에 적합한 비율은 얼마인가? (Positive로 추측된 결과 중 True인 것)
• 재현율(Recall): 컬렉션에 포함된 적합 문헌 중 시스템에 의해 반환된 적합 문헌이 차지하는 비율은 얼마인가? (실제 Positive 중 True인 것)
• 역색인(Inverted index)
• 0과 1로 구성된 발생행렬 전체를 저장하기에는 한계가 있으며, 99.8%는 0이기 때문에 1만 저장하는 것이 효율적 임
• 포스팅(Posting)
• 역색인의 각 항목들을 포스팅이라 하며, 모든 포스팅 목록들을 일컬어 포스팅이라고 칭할 수 있음

1.2 역색인 구축의 첫 단계

• 검색할 때 색인 효과를 높이기 위해 색인을 미리 수행하는 방법
1. 색인 대상 문헌을 수집
2. 문헌을 토큰 처리하여 각 문헌을 토큰 목록으로 변환
3. 자연어 전처리를 수행한 다음, 색인어가 될 정규화 토큰의 목록을 생성
4. 어휘집과 포스팅으로 구성되는 역색인을 생성하여, 각 용어가 출현하는 문헌을 색인
• 토큰(Token), 정규화 토큰(Normalized token)
1. 단어와 거의 유사한 것으로 간주
2. 토큰: Friends | Romans | countrymen | So
3. 정규화 토큰: friend | roman | countrymen | so
• 정렬(Sort)
1. 동일 문헌에서 같은 용어가 여러 번 출현하면 하나로 합쳐 그룹화되고, 어휘집과 포스팅으로 분리하는 등 저장 공간을 절약하고 몇 가지 통계량(문헌 빈도(Document frequency) 등)을 기록하여, 질의 시 검색 엔진의 효율을 향상시켜 줌
• 색인 결과의 저장
1. 일반적으로 포스팅 목록이 더 커서, 사전은 메모리에 있는데 비해 포스팅 목록들은 디스크에 저장됨
2. 포스팅 목록의 경우 어떤 단어들은 많은 문헌에 출현하지만, 다른 단어들은 아주 적은 문헌에 출현하기 때문에 고정 길이 배열을 쓰는 것은 낭비임
• 단일 연결 목록(Singly linked lists): 포스팅 목록에 문헌을 쉽게 삽입할 수 있으며(갱신된 문서에 대해 웹을 재수집할 때처럼 갱신 내역을 추적함), 따라서 스킵 리스트(추가적인 포인터가 필요) 등보다 진보된 색인 전략으로 확장할 수 있음
• 가변 길이 배열(Variable length arrays): 공간적인 면에서는 포인터가 필요한 공간을 절약할 수 있고, 시간적인 면에서는 연속적인 공간을 사용하므로 처리 속도를 개선할 수 있음
• 갱신 빈도가 상대적으로 빈번하지 않을 경우 가변 길이 배열이 보다 간단하고 빠른 검색 방법임

1.3 Boolean 질의 처리

• 단순 결합 질의(Simple conjunctive query)
• | Brutus AND Calpurnia | 와 같이 교집합을 구하는 질의
• 교집합(Intersection)
• 매우 중요한 연산으로 두 용어를 모두 포함하는 문헌들을 빨리 찾을 수 있도록 하기 위해 포스팅 목록으로 부터 교집합 연산을 효과적으로 수행해야하며, 병합 알고리즘(Merging algorithm)이라고도 나타냄
• 질의 최적화(Query optimization)
• 시스템이 수행해야 할 총 작업량을 최소화시킬 목적으로 질의에 대한 응답을 조직하는 방법을 선택하는 과정으로 가장 일반적인 예로는 문헌 빈도가 낮은 용어부터 처리하는 방법이 있음
• 모든 중간 결과는 제일 작은 포스팅 목록보다 결코 크지 않을 것이므로, 총 작업량을 최소화시킬 수 있음

1.4 확장 Boolean 모델과 순위 검색

• 자연어 질의(Free text query)
• 질의를 표현하려면 연산자와 같은 정교한 언어를 사용하지 않고 자연어 문장처럼 단어를 나열하는 질의 표현 방법
• 순위 검색 모형(Ranked retrieval model)
• 사용자는 대부분 자연어 질의를 이용하는 것이 더 효과적인 방법이며, 시스템도 질의에 가장 적합한 순으로 문헌을 정렬하는 편이 더 효과적임
• 하지만 많은 사용자, 특히 전문가들은 Boolean 질의 모델을 더 선호함
• Boolean 질의는 정확함
• 하나의 문헌은 특정 질의에 일치하거나 그렇지 않음
• 사용자는 무엇이 검색될지를 더욱더 잘 통제할 수 있고 투명하게 확인할 수 있도록 제안함
• 확장 Boolean 검색 모델
• 근접 연산자와 같은 추가적인 연산자를 제공하는 Boolean 검색 모델
• 근접 연산자(Proximity operator)
• 질의에 있는 두 용어가 한 문헌에서 서로 가까이 출현하는 조건을 지정하기 위한 연산자로 단어 사이의 거리일 수도 있고, 문장이나 문단과 같은 구조적인 단위로 제한하는 것을 의미하기도 함

참고: Introduction to Information Retrieval