11.텍스트를 위한 화일.

Presentation on theme: "11.텍스트를 위한 화일."— Presentation transcript:

1 11.텍스트를 위한 화일

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

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

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

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

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

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

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

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

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

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