11.텍스트를 위한 화일

▶ 텍스트를 위한 화일 텍스트 필드로만 구성된 레코드를 접근할 수 있는 화일 텍스트 : 긴 문자열로 구성된 데이타 (예) 학생의 자기 소개, 신문 기사, 사전의 용어, 인터넷 사이트에 대한 설명 정보 텍스트 필드는 하나의 필드 안에 여러 개의 탐색 값(단어, keyword)이 포함 (예) 학번이 123456인 학생 레코드의 자기 소개 필드에 “데이타베이스 시스템과 질의어에 대한 지식을 보유하고 있다.” 라고 기술되어 있다고 가정하자. Keyword : “데이타베이스”, “시스템”, “질의어” 라는 단어(탐색 값)을 어떠한 방법으로 탐색할 것인가? 응용 분야 Yahoo, AltaVista, Naver 의 인터넷 검색 엔진의 핵심기술

 역 리스트 화일(Inverted list file) 역 리스트 화일 구조 역 리스트 화일 = 인덱스 화일 + 포스팅 화일 + 데이타 화일 인덱스 화일(사전 : dictionary) : 키워드 + 관련 레코드 수(hit 수) + 포스팅에 대한 포인터 포스팅 화일(posting file) : - 키워드를 포함한 데이타 레코드에 대한 포인터의 리스트, (- 그 레코드의 텍스트 필드에서 해당 키워드의 발생 빈도, - 그 텍스트에서 해당 키워드의 상대적인 중요도(weight), - 그 텍스트에서 해당 키워드의 발생 위치(offset)를 추가 ) 데이타 화일 : 문서 화일(document file) 장점 구현 용이, 속도가 빠름, 동의어 지원 용이 단점 많은 기억 공간 요구 : 데이타 화일의 300%까지 인덱스 갱신, 재구성 시 : 비용이 크게 증가 응용분야 : 상용검색엔진(DIALOG, BRS, ORBIT, STAIRS)

▶ 역 리스트 화일 구조의 예 - 키워드는 가나다 순으로 정렬 … 2 질의어 시스템 3 데이타베이스 7 1 6 5 레코드2 : 시스템 운영과 관리 경험이 있다. 레코드1 : 데이타 베이스 시스템과 질의어에 대한 지식을 보유하고 있다. 키워드 히트링크 인덱스 화일 레코드번호 링크 포스팅 화일 데이타 화일

▶ 역 리스트 화일의 탐색 방법 질의(Query) : Boolean query, Ranking query 불리언 질의 탐색 키워드들간의 논리 연산자( ‘&’,’ |’, ‘!’ )를 이용 표현 (예) ‘데이타베이스 & 질의어’ 질의는 두 키워드가 모두 포함하는 데이타 화일을 검색 --- <1, 5, 6> & <1, 7> 을 AND하면 < 1 > 이므로, 두 키워드를 포함한 것은 1 레코드 (예) ‘데이타베이스 | 질의어’ 의 결과는 <1, 5, 6, 7 > 됨 랭킹 질의 탐색 질의어와 데이타 레코드간의 근접도(closeness)를 평가하기 위해 유사도(similarity) 휴리스틱을 사용하여 일정한 개수 (예, K개)의 근접 데이타 레코드들을 결과로 가져옴. 초기 검색 엔진에 많이 사용, 최근에는 병행 지원.

 시그니처 화일(Signature File) 개략적 필터(inexact filter) 방식에 기반 전체 화일의 내용을 순차적으로 검색하지 않고, 화일의 내용을 부호화하여 소량의 공간에서 질의 검색하는 방법 중첩 코딩(superimposed coding) : 시그니처 화일 생성방법 개략적 필터라고 하는 이유 첫째, 서로 다른 키워드에 대한 해싱 결과가 동일한 시그니처를 생성할 가능성. 둘째, 블록 시그니처를 만들 때 여러 개의 시그니처를 “OR” 연산으로 취합하면서 다른 키워드와 일치할 가능성 질의 연산 종류 exact match : 질의문에 블록 시그니처의 모든 키워드가 주어질 때 partial match : 질의문에 블록 시그니처의 키워드 일부만 주어질 때

▶ 시그니처 코딩 방법 중첩 코딩 방법 (F=16, m=3으로 가정) 단어(키워드) 시그니처 (F=16 비트) 데이타베이스 각 문서를 동일한 수의 상이한 키워드를 포함하는 “논리 블록” 나눔 각 키워드를 F개의 비트로 구성된 “단어 시그니처”를 작성 (단어 시그 니처는 m개 비트만 “1”로 세트, 나머지는 “0”으로 세트, 각 단어에 대해 “1”로 세트되는 m 개의 위치는 hash 함수로 결정) 단어 시그니처들을 OR 연산으로 하나의 “블록 시그니처”를 작성 단어(키워드) 시그니처 (F=16 비트) 데이타베이스 0010 0100 0000 0001 시스템 0000 1000 1000 0010 질의어 0100 1000 0100 0000 블록 시그니처 0110 1100 1100 0011

▶ 시그니처 화일을 이용한 검색 질의문 : “시스템”이 포함된 텍스트를 검색하라 1) 질의 시그니처 생성 0000 1000 1000 0010 2) 질의 시그니처 0000 1000 1000 0010 AND) 블록 시그니처 0110 1100 1100 0011 0000 1000 1000 0010 (≡ 질의 시그니처) 3) 2와 같은 조건을 만족하는 텍스트에 대해 “시스템”이 실제로 포함되었는지 검사

시그니처 화일이 적합한 경우 시그니처 화일의 장단점 탈락 착오(false drop) PC에서 사용되는 중 규모의 DB 검색 질의 빈도가 낮은 DB(B-트리 인덱스보다 비용 저렴) 병렬 처리되는 DB 시그니처 화일의 장단점 전문(full text) 검색보다 2배 정도 빠름. 10 ~ 15%의 추가 공간이 필요 (역 화일기법의 인덱스가 50 ~ 300%의 추가 공간 필요) 추가적인 삽입만을 허용하므로 삽입 연산이 간단 대규모 DB에서는 속도가 저하 탈락 착오(false drop) 시그니처 구성에 사용되지 않은 키워드가 매치되는 것

▶ 시그니처 화일 구조와 탐색 방법 (1) 순차 시그니처 화일 : F * N 이진 행렬 - 행 우선으로 순차 저장

▶ 시그니처 화일의 탐색 방법 (2) 압축(compression) (3) 수직 분할(vertical partitioning) ① 질문에 포함된 키워드로 하나의 질의 시그니처를 생성 ② 질의 시그니처를 N개의 논리 블록 시그니처의 각 각과 AND 연산한 결과가 원래의 질의 시그니처와 일치하면 매치한 것 ③ 매치된 블록에 해당하는 포인터 화일의 포인터를 따라 문서 화일을 검색하여 질의문의 키워드들이 포함된 지를 검사 ④ ③에서 실제로 매치된 논리 블록이 검색할 문서의 결과임 (2) 압축(compression) 시그니처의 행렬이 희소할 경우, 압축을 통해 저장 공간 감소시킴 시그니처 화일의 검색 시간 단축 (3) 수직 분할(vertical partitioning) 시그니처 화일을 열 단위(bit slice)로 나누어 저장 1로 세트된 비트 슬라이스만을 검색, 검색시간 단축 삽입 시간은 증가 (4) 수평 분할(horizontal partitioning) 시그니처 화일에 대한 인덱스를 만들어 검색 전체 시그니처 화일 검색 불필요