12주 실습강의 2009. 1학기, 소프트웨어 설계 및 실험(Ⅰ)

정보 검색(Information Retrieval) 데이터 검색 구조가 있는 데이터(structured data)의 집합에 대하여 정확한 질의어(query)를 사용하여 조건에 맞는 결과 집합을 얻는 것 데이터베이스 검색 문서 검색 구조가 없는 데이터(unstructured data)에 대하여 자유로운 형식의 모호성있는 질의어를 사용하여 관련된 결과 집합을 얻는 것 구글, 네이버 등의 검색엔진 앞으로 3주 동안의 실습은 문서 검색을 대상으로 함 대량의 문서 확보가 힘들기 때문에 실습 3주차에 만들었던 게시판을 검색 대상으로 함

용어(슬라이드 노트 참고) INDEX TERM DOCUMENTS INVERTED INDEX/FILE DICTIONARY docID DOCUMENT FREQUENCY TERM FREQUENCY POSTING Index - 색인. 검색을 효율적으로 하기 위한 용어의 리스트와 같이, key(검색에서는 각각의 Term이 된다.) - 본체의 어드레스 위치(물리적, 상대적 위치)를 쌍으로 갖고 데이터의 본체를 검색하기 위한 항목을 의미한다. Term - 검색에서는 인덱스를 구성하는 하나의 unit(=key)을 의미한다. 일반적으로 단어(words)가 이에 해당하지만, 'Hong Kong'과 같이 Word가 항상 Term이 되지는 않는다. Documents - 검색의 대상이 되는 기본 단위를 의미한다. 이것은 파일 하나, 책 전체가 될 수도 있고, 문서 안의 한 단락, 한 문장이 될 수도 있다. Inverted Index / File (역파일) - Incidence Matrix의 경우 Term - Documents의 관계를 표현하기 위해 전체 Term 수 x Dictionary 수 크기의 공간을 확보해야 한다. 이 데이터는 매우 Sparse 하기 때문에, 공간적 비용의 낭비가 심하다고 할 수 있다. 이를 대신하기 위해, Documents - Term의 목록이 아니라 그 반대, 즉 Term에 대해 Documents 들을 참조하게 한 인덱스다. Dictionary - Data Structure의 입장에서 Term(=key)-값으로 이루어진 목록을 자료 구조 측면에서 말하는 것. docID - 문서 ID, Document ID로, 검색에서 연산 및 결과 반환에 사용되는 하나의 고유값이라고 볼 수 있다. docID는 검색의 범위를 어떻게 정의하느냐에 따라(= 검색을 위한 대상의 granularity를 결정해야 한다.) 파일, 책, 문단, 문장에 각각의 docID가 부여될 수 있다. Document Frequency - Term이 나타나는 문서의 빈도. Collection Frequency와 달리, 해당 문서에서 Term이 여러 번 나오더라도, 전체 Collection(말뭉치)에서 하나의 문서에만 나올 때, 그것의 Document Frequency는 1이 된다. Term Frequency - 한 문서에서 Term이 나타나는 빈도. Posting - Inverted Index의 구성요소로, 특정 Document에서 Term이 발견될 경우, 이를 이후에 참조할 수 있도록 기록한 것.

간략한 과정 문서 수집 문서 전처리 문서 분석 문서 색인 역파일 생성 역파일 저장 문서 검색 수작업, robot 색인어 사전 구축, 색인어와 문서 id 부여 역파일 생성 색인어 기준으로 각 문서 내용 정렬 문서를 색인어별로 merge 역파일 저장 문서 검색 질의어 색인 질의

Inverted index For each term T, we must store a list of all documents that contain T. 2 4 8 16 32 64 128 3 5 13 21 34 1 Posting Dictionary Brutus Calpurnia Caesar Postings lists

Friends, Romans, countrymen. Inverted index 생성 Tokenizer Token stream. Friends Romans Countrymen Linguistic modules Modified tokens. friend roman countryman Indexer Inverted index. 2 4 13 16 1 More on these later. Documents to be indexed. Friends, Romans, countrymen.

Indexer steps 1 Sequence of (Modified token, Document ID) pairs. Doc 1 I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me. So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious

Indexer steps 2 Sort by terms. Core indexing step.

For document’s ranking Indexer steps 3 Multiple term entries in a single document are merged. Frequency information is added. Why frequency? For document’s ranking Term Frequency(tf)가 높으면 해당 문서에 단어가 여러 번 나타났다는 것이므로 문서의 중요도는 올라가게 된다. Document Frequency(df)가 높으면 많은 문서에 자주 나타나는 단어이므로 중요도는 낮아진다.

Indexer steps 4 For searching Inverted index – in hard disk Dictionary – in main memory

게시판 검색 일반적인 게시판 검색 실습용 게시판 검색 데이터 검색 데이터베이스에서 SQL의 like 등의 문법으로 검색 문서 검색 Inverted index를 이용한 검색 그러나 일반적인 문서 검색과는 차이가 있음

실습 - 검색 문서 수집 문서 전처리, 분석 문서 색인 역파일 생성, 저장 문서 검색 검색범위는 게시판 제목으로 제한 간단하게 공백(white space) 단위로 tokenize 문서 색인 다음 주 실습에서... 역파일 생성, 저장 DB에 저장, Term Frequency는 사용하지 않음 문서 검색 질의어 색인 : 다음 주 실습에서... 질의 : 공백(white space)을 AND연산하여 검색, ‘|’(bar)를 OR연산하여 검색

실습 - DB 스키마 InvertedIndex ( term#, postingslists, df ) Name Type Data(예) term nvarchar(50) – string 실버라이트 posting_list nvarchar(max) – string 1 5 17 (숫자 사이는 white space) df int 3 ExpBoard ( index#, writer, password, title, contents, read, date ) - 실습 3주차와 동일 - ‘#’은 key를 의미함 Term을 key로 두어 검색을 빠르게 한다.(MS SQL 내부적으로 binary search를 할 수도 있고, hash를 쓸 수도 있고,…)

실습 - Code 문서 수집 ~ 역파일 저장 공백 단위로 tokenize Dictionary에 term이 있을 경우 공백으로 docID 구분 Dictionary에 term이 없을 경우

실습 - Code 문서 검색 Term(검색어)에 대한 Postings list(게시판 index번호 목록)를 반환 찾기 못할 경우 -1을 반환

실습 - Code 문서 검색 공백 단위로 tokenize 각각의 index로 data(document)를 가져옴

실습 - 해결해야 할 문제 2개 이상의 term들로 이루어진 질의 Document의 수정, 삭제 시 AND연산, OR연산 등 Document의 수정, 삭제 시 DB에서 삭제(?) Document 우선 순위 적용 Term Frequency의 사용(DB 스키마 수정 필요) Document, 질의어의 색인 다음 주 실습에서 ... 검색된 부분의 하이라이팅 검색 속도 글쓴이, 본문 등의 검색 그 외 여러가지

실습 – AND 연산 오늘의 실습 내용 위의 예에서 질의어가 ‘Brutus Calpurnia’이면 Brutus와 Calpurnia의 AND연산을 통해 docID가 2와 8인 것을 찾아낸다. 2 4 8 16 32 64 128 3 5 13 21 34 1 Posting Dictionary Brutus Calpurnia Caesar Postings lists

실습 – 추가구현(OR 연산) 2 4 8 16 32 64 128 3 5 13 21 34 1 Posting 위의 예에서 질의어가 ‘Brutus|Calpurnia’이면 Brutus와 Calpurnia의 OR연산을 통해 docID가 1,2,3,4,5,8,13,16,21,32,34,64,128인 것을 찾아낸다. Dictionary Brutus Calpurnia Caesar Postings lists