. 텍스트를위한 화일 텍스트를위한화일 텍스트데이타로구성된문서 (docments) 나텍스트필드 (text field) 를포함하고있는레코드검색에이용할수있는화일 텍스트 (text): 긴문자열로구성된데이타 ( 예 ) 학생의자기소개, 신문기사, 사전의용어, 인터넷사이트에대한설명정보 키워드 (keyword): 텍스트데이타에대한탐색키값 하나의레코드를식별하기위하여텍스트필드는여러개의키워드가사용될수있음. ( 예 ) 학번이 23456인학생레코드의자기소개필드에 데이타베이스시스템과질의어에대한지식을보유하고있다. 라고기술되어있다고가정하면. 데이타베이스, 시스템, 질의어 라는키워드로학번이 23456인학생레코드를검색할수있음 응용분야 digital office filing, digital library, image database, 기사 (article) 검색 인터넷검색엔진의핵심기술 2
v 역리스트화일 (inverted list file) 텍스트필드를지원하는대표적화일구조 역화일 (inverted file) 에서는인덱스엔트리가여러개의포인터를포함할수있지만화일내에서이포인터들은모두상이하다. 역리스트화일에서는인덱스엔트리가여러개의포인터를포함할수있을뿐아니라하나의레코드에대한포인터가상이한인덱스엔트리에중복해서여러번포함될수있다. 3 역리스트화일구조 레코드가문서 (docment) 라고가정할때역리스트화일은인덱스화일 (index file), 포스팅화일 (posting file), 데이타화일 (data file) 로구성된다.. 인덱스화일 (index file) 또는사전 (dictionary) 키워드 : 알파벳순으로정렬 관련된문서수 (hit 수 ) 포스팅화일에대한포인터 2. 포스팅화일 (posting file) : 키워드를포함하고있는문서들에대한포인터리스트 (< 문서번호, 포인터 >) 를저장그외에 그문서에서해당키워드의출현빈도 (freqency) 그문서에서해당키워드의상대적인가중치 (weight) 그문서에서해당키워드의오프셋 (offset) 즉키워드의위치등 3. 데이타화일 (data file) 또는문서화일 (docment file) 텍스트즉문서를저장한화일 4
역리스트화일구조의예 인덱스화일키워드히트링크 데이타베이스 시스템 질의어 3 2 2 포스팅화일문서번호링크 5 6 2 7 데이타화일 문서 : 데이타베이스시스템과질의어에대한지식을보유하고있다. 문서 2 : 시스템운영과관리경험이있다. 5 역리스트화일의검색 질의 (qery): 특정키워드를포함하고있는문서를검색하는과정. 불리언질의 (boolean qery) 탐색키워드들간의논리적관계를 AND, OR, NOT ( &,,! ) 를이용하여표현 ( 예 ) 데이타베이스 & 질의어 질의는두키워드가모두포함하는데이타화일을검색 --- {, 5, 6} & {, 7} 을 AND 하면 {} 이되므로, 두키워드를포함한문서는 번문서 2. 랭킹질의 (ranking qery) 원하는문서를단순히키워드리스트로명세 명세된키워드와목표문서간의근접도 (closeness), 즉유사성 (similarity) 을평가하여근접도가높은순서로일정한수 (k) 의문서를질의결과로생성. 근접도계산에는키워드의가중치가사용 6
v 시그니처화일 (Signatre File) 시그니처화일 기본아이디어는개략적필터 (inexact filter) 방식에기반 부적격데이타를우선적으로제외 전체화일의내용을순차적으로검색하지않고, 화일의내용을코드화해서작은공간을차지하는후보데이타를걸러낸뒤에이들을검사해서목표데이타를검색하는방법 접근방법. 문서 (docment) 들을텍스트화일 (text file) 에순차적으로저장. 2. 이문서들에대한문서시그니처 (docment signatre), 즉해시코드된비트패턴 (hash-coded bit pattern) 들을시그니처화일 (signatre file) 에저장. 3. 질의문처리시이시그니처화일을먼저검사해서부적격문서를걸러냄. 4. 나머지문서들을검사해서결과를생성. 시그니처는일반적으로중첩코딩 (sperimposed coding) 방법을이용하여생성 7 중첩코딩생성방법. 각문서를일정수 (D) 의상이한키워드를포함하는논리블록 (logical block) 으로분할 2. 각키워드에대해 F 개의비트로구성된키워드시그니처 (keyword signatre) 를작성. 키워드시그니처는 m 개의비트만 로설정되고, 나머지는 0 으로설정 F 와 m 의값은시그니처화일설계시에결정 각키워드시그니처에 로설정되는 m 개의위치는 hash 함수로결정 3. 한논리블록에속한 D 개의키워드시그니처들에 OR 연산을수행하여하나의블록시그니처 (block signatre) 를작성 4. 문서에속한블록시그니처들을모두접합 (concatenation) 하여문서시그니처 (docment signatre) 를작성. 5. 질의문에명세된키워드를검색하기위해서는이키워드의시그니처를만들어여기에포함된 들이각블록시그니처의 들과일치하는지비교해서매치여부를결정 8
중첩코딩예 D=3, F=6, m=3 인경우의중첩코딩예 키워드데이타베이스시스템질의어블록시그니처 시그니처 (F=6 비트 ) 000 000 0000 000 0000 000 000 000 000 000 000 0000 00 00 00 00 9 시그니처화일을이용한검색 블록이질의문의키워드를포함하고있는지는다음식의만족여부로결정 : ( 질의문시그니처 ) AND ( 블록시그니처 ) = 질의문시그니처? 질의문예 : 시스템 이포함된문서를검색하라. 질의시그니처생성 0000 000 000 000 2. 블록시그니처 00 00 00 00 3. 질의시그니처 AND 블록시그니처 0000 000 000 000 AND 00 00 00 00 ------------------------------------------ 0000 000 000 000 ( 질의시그니처 ) 4. 위의조건을만족하는문서에대해 시스템 이포함되었는지실제로검사 0
시그니처화일의장단점 시그니처화일의장점 전문 (fll text) 검색보다 2배정도빠름. 0 ~ 5% 의추가공간만필요 역화일 (inverted file) 의인덱스는 50 ~ 300% 의추가공간을필요 추가적인삽입만을허용하므로삽입연산이간단 시그니처화일의단점 대규모 DB에서는속도저하 허위통과 (false drop) 또는허위적중 (false hit) 시그니처구성에포함되지않은키워드가매치되는것 시그니처화일의구조 시그니처화일은 N 개의블록시그니처를나타내는 N x F 이진행렬 (binary matrix) 순차시그니처화일 (SSF; seqential signatre file) N 개의블록시그니처를행단위로순차저장 포인터화일은논리블록의시작점을지시 블록시그니처화일 F 비트 0... 0 포인터화일 텍스트화일논리블록 N 논리블록시그니처... 0 2
시그니처화일의검색방법 검색과정 질문에포함된키워드로하나의질의문시그니처 (qery signatre) 를생성 2 질의문시그니처를 N개의논리블록시그니처의각각과 AND 연산한결과로질의시그니처와매치여부를결정 3 매치된블록에해당하는포인터화일의포인터를따라텍스트화일을검색하여질의문의키워드들이포함되어있는지를검사 4 3에서실제로매치된논리블록들을검색결과로출력 3 시그니처화일의성능향상방안 () () 압축 (compression) 시그니처의행렬이희소할경우 (의수가매우적음 ) 압축을통해저장공간을축소 시그니처화일의검색시간단축 (2) 수직분할 (vertical partitioning) 시그니처화일을열단위, 즉비트슬라이스 (bitslice) 로나누어저장 비트슬라이스구조는전치비트행렬 (transposed bit matrix) 이됨 각비트위치마다하나의비트화일 (bit-file) 로전부 F 개의화일을사용하여저장함 검색시질의문시그니처에 로세트된 m 개의파일에서 m 비트벡터만검색하여 AND를하면원하는논리블록을식벽할수있음 전체검색시간단축 시그니처삽입시에는 F 개의화일을전부접근해야됨 삽입시간은증가 4
시그니처화일의성능향상방안 (2) (3) 수평분할 (horizontal partitioning) 유사시그니처를그룹화하고이시그니처그룹에대한인덱스를만들어검색 전체시그니처화일의순차검색이불필요 5