11.텍스트를 위한 화일.

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

1 11.텍스트를 위한 화일

2 ▶ 텍스트를 위한 화일 텍스트 데이타로 구성된 문서(documents)나 텍스트 필드(text field)를
포함하고 있는 레코드 검색에 이용할 수 있는 화일 텍스트(text): 긴 문자열로 구성된 데이타 (예) 학생의 자기 소개, 신문 기사, 사전의 용어, 인터넷 사이트에 대한 설명 정보 키 워드(keyword): 텍스트 데이타에 대한 탐색 키 값 하나의 레코드를 식별하기 위하여 텍스트 필드는 여러 개의 키워드가 사용될 수 있음. (예) 학번이 인 학생 레코드의 자기 소개 필드에 “데이타베이스 시스템과 질의어에 대한 지식을 보유하고 있다.” 라고 기술되어 있다고 가정하면. “데이타베이스”, “시스템”, “질의어” 라는 키워드로 학번이 인 학생 레코드를 검색할 수 있음 응용 분야 digital office filing, digital library, image database , 기사(article) 검색 인터넷 검색 엔진의 핵심기술

3  역 리스트 화일(inverted list file)
텍스트 필드를 지원하는 대표적 화일 구조 역 화일(inverted file)에서는 인덱스 엔트리가 여러 개의 포인터를 포함할 수 있지만 화일 내에서 이 포인터들은 모두 상이하다. 역 리스트 화일에서는 인덱스 엔트리가 여러 개의 포인터를 포함할 수 있을 뿐 아니라 하나의 레코드에 대한 포인터가 상이한 인덱스 엔트리에 중복해서 여러 번 포함 될 수 있다.

4 ▶ 역 리스트 화일 구조 레코드가 문서(document)라고 가정할 때 역 리스트 화일은 인덱스
화일(index file), 포스팅 화일(posting file), 데이타 화일(data file)로 구성된다. 1. 인덱스 화일(index file) 또는 사전(dictionary) 키워드: 알파벳 순으로 정렬 관련된 문서 수(hit 수) 포스팅 화일에 대한 포인터 2. 포스팅 화일(posting file) : 키워드를 포함하고 있는 문서들에 대한 포인터 리스트 (<문서번호, 포인터>)를 저장 그 외에 그 문서에서 해당 키워드의 출현 빈도(frequency) 그 문서에서 해당 키워드의 상대적인 가중치(weight) 그 문서에서 해당 키워드의 오프셋(offset) 즉 키워드의 위치 등 3. 데이타 화일 (data file) 또는 문서 화일(document file) 텍스트 즉 문서를 저장한 화일

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

6 ▶ 역 리스트 화일의 검색 질의(query): 특정 키워드를 포함하고 있는 문서를 검색하는 과정
1. 불리언 질의(boolean query) 탐색 키워드들간의 논리적 관계를 AND, OR, NOT ( &, |, ! )를 이용하여 표현 (예) ‘데이타베이스 & 질의어’ 질의는 두 키워드가 모두 포함하는 데이타 화일을 검색 --- {1, 5, 6} & {1, 7} 을 AND하면 {1}이 되므로, 두 키워드를 포함한 문서는 1 번 문서 2. 랭킹 질의(ranking query) 원하는 문서를 단순히 키워드 리스트로 명세 명세된 키워드와 목표 문서 간의 근접도(closeness), 즉 유사성(similarity)을 평가하여 근접도가 높은 순서로 일정한 수(k)의 문서를 질의 결과로 생성. 근접도 계산에는 키워드의 가중치가 사용

7  시그니처 화일(Signature File)
기본 아이디어는 개략적 필터(inexact filter) 방식에 기반 부적격 데이타를 우선적으로 제외 전체 화일의 내용을 순차적으로 검색하지 않고, 화일의 내용을 코드화해서 작은 공간을 차지하는 후보 데이타를 걸러낸 뒤에 이들을 검사해서 목표 데이타를 검색하는 방법 접근 방법 1. 문서(document)들을 텍스트 화일(text file)에 순차적으로 저장. 2. 이 문서들에 대한 문서 시그니처(document signature), 즉 해시 코드된 비트 패턴(hash-coded bit pattern)들을 시그니처 화일 (signature file)에 저장. 3. 질의문 처리시 이 시그니처 화일을 먼저 검사해서 부적격 문서를 걸러냄. 4. 나머지 문서들을 검사해서 결과를 생성. 시그니처는 일반적으로 중첩 코딩(superimposed coding) 방법을 이용하여 생성

8 ▶ 중첩 코딩 생성 방법 각 문서를 일정 수(D)의 상이한 키워드를 포함하는 논리 블록 (logical block)으로 분할
2. 각 키워드에 대해 F개의 비트로 구성된 키워드 시그니처(keyword signature)를 작성. 키워드 시그니처는 m개의 비트만 1로 설정되고, 나머지는 0으로 설정 F와 m의 값은 시그니처 화일 설계 시에 결정 각 키워드 시그니처에 1로 설정되는 m 개의 위치는 hash 함수로 결정 3. 한 논리 블록에 속한 D개의 키워드 시그니처들에 OR 연산을 수행하여 하나의 블록 시그니처(block signature)를 작성 4. 문서에 속한 블록 시그니처들을 모두 접합(concatenation)하여 문서 시그니처(document signature)를 작성. 5. 질의문에 명세된 키워드를 검색하기 위해서는 이 키워드의 시그니처를 만들어 여기에 포함된 1들이 각 블록 시그니처의 1들과 일치하는지 비교해서 매치 여부를 결정

9 ▶ 중첩 코딩 예 D=3, F=16, m=3인 경우의 중첩 코딩 예 키워드 시그니처 (F=16 비트) 데이타베이스
시스템 질의어 블록 시그니처

10 ▶ 시그니처 화일을 이용한 검색 블록이 질의문의 키워드를 포함하고 있는지는 다음 식의 만족 여부로 결정:
(질의문 시그니처) AND (블록 시그니처) = 질의문 시그니처? 질의문 예 : “시스템”이 포함된 문서를 검색하라 질의 시그니처 생성 2. 블록 시그니처 3. 질의 시그니처 AND 블록 시그니처 AND (≡ 질의 시그니처) 4. 위의 조건을 만족하는 문서에 대해 “시스템”이 포함되었는지 실제로 검사

11 ▶ 시그니처 화일의 장단점 시그니처 화일의 장점 시그니처 화일의 단점 전문(full text) 검색보다 2배 정도 빠름.
10 ~ 15%의 추가 공간만 필요 역 화일(inverted file)의 인덱스는 50 ~ 300%의 추가 공간을 필요 추가적인 삽입만을 허용하므로 삽입 연산이 간단 시그니처 화일의 단점 대규모 DB에서는 속도 저하 허위 통과(false drop) 또는 허위 적중(false hit) 시그니처 구성에 포함되지 않은 키워드가 매치되는 것

12 ▶ 시그니처 화일의 구조 시그니처 화일은 N 개의 블록 시그니처를 나타내는 N x F 이진 행렬(binary matrix)
순차 시그니처 화일(SSF; sequential signature file) N 개의 블록 시그니처를 행 단위로 순차 저장 포인터 화일은 논리 블록의 시작점을 지시

13 ▶ 시그니처 화일의 검색 방법 검색 과정 ① 질문에 포함된 키워드로 하나의 질의문 시그니처(query signature)를 생성 ② 질의문 시그니처를 N개의 논리 블록 시그니처의 각 각과 AND 연산한 결과로 질의 시그니처와 매치 여부를 결정 ③ 매치된 블록에 해당하는 포인터 화일의 포인터를 따라 텍스트 화일을 검색하여 질의문의 키워드들이 포함되어 있는 지를 검사 ④ ③에서 실제로 매치된 논리 블록들을 검색 결과로 출력

14 ▶ 시그니처 화일의 성능 향상 방안(1) (1) 압축(compression)
시그니처의 행렬이 희소할 경우(1의 수가 매우 적음) 압축을 통해 저장 공간을 축소 시그니처 화일의 검색 시간 단축 (2) 수직 분할(vertical partitioning) 시그니처 화일을 열 단위, 즉 비트 슬라이스(bitslice)로 나누어 저장 비트 슬라이스 구조는 전치 비트 행렬(transposed bit matrix)이 됨 각 비트 위치마다 하나의 비트 화일(bit-file)로 전부 F 개의 화일을 사용하여 저장함 검색 시 질의문 시그니처에 1로 세트된 m 개의 파일에서 m 비트 벡터만 검색하여 AND를 하면 원하는 논리 블록을 식벽 할 수 있음 전체 검색시간 단축 시그니처 삽입 시에는 F 개의 화일을 전부 접근해야 됨 삽입 시간은 증가

15 ▶ 시그니처 화일의 성능 향상 방안(2) (3) 수평 분할(horizontal partitioning)
유사 시그니처를 그룹화하고 이 시그니처 그룹에 대한 인덱스를 만들어 검색 전체 시그니처 화일의 순차 검색이 불필요