8장 색인과 검색 목차 8.1 소개 8.2 역파일 8.3 다른 색인 기법 8.4 불리안 질의 8.5 순차 탐색 8.6 패턴 정합 8.7 구조적 질의 8.8 압축 8.9 연구 동향 및 쟁점 8.10 참고 문헌 고찰 최신정보검색론 Chapter8

8.1 소개 질의 탐색 - 순차 탐색 또는 온라인 탐색 내용이 자주 변경되는 텍스트나 색인 공간에 대한 여유가 없을 때 사용 - 색인 탐색: 추가적인 데이터 구조(색인)를 만드는 방법 크기가 크고, 정기적으로 변경되는 준정적(semi-static) 텍스트에 대한 탐색시 유리 - 온라인 탐색과 색인 탐색의 혼합 방법 중간 크기의 데이터베이스(200Mb 이내)에 대한 가장 성공적인 기술 최신정보검색론 Chapter8

8.1 소개(계속) 색인 기법 색인 구조 가정 역파일(inverted file), 접미사배열(suffix array), 요약파일(signature file) 색인 구조 정렬된 배열(sorted array),이진 탐색 트리(binary search trees), B-트리(B-trees),해시 테이블(hash table),트라이(tries) 가정 n: 텍스트 데이터베이스의 크기 m: 문자열 탐색시 문자열의 길이 (n보다 훨씬 작은 값) M: 사용 가능한 메모리의 용량 텍스트 데이터베이스에 대한 수정: n(n<n)의 문자열에 대한추가, 삭제, 대체 최신정보검색론 Chapter8

This is a text. A text has many words. Words are made from letters 8.2 역파일 역파일(또는 역색인) 탐색 작업의 속도 향상, 단어기반 메커니즘 구조 : 어휘(vocabulary)와 출현빈도 (occurrences) This is a text. A text has many words. Words are made from letters 1 6 9 11 17 19 24 28 33 40 46 50 55 60 텍스트 어휘 출현빈도 letters made many text words 60… 50… 28… 11, 19… 33, 40… [그림 8.1] 텍스트와 역색인 구성의 예 역색인 [그림 8.1] 텍스트와 역색인 구성의 예 최신정보검색론 Chapter8

8.2 역파일(계속) 공간 - 어휘 상대적으로 작다. - 출현빈도 더욱 많은 공간 필요 Heap의 법칙(6장 참조): 어휘는 O(nβ)로서 증가 β는 0과 1 사이의 상수 값 실험적으로 보통 0.4∼0.6 사이의 값 예) TREC-2의 1Gb 집합에 대한 어휘는 단지 5Mb - 출현빈도 더욱 많은 공간 필요 추가적인 공간: O(n) 불용어(stopword) 제거시 필요 공간은 텍스트 크기의 30∼40% 최신정보검색론 Chapter8

8.2 역파일(계속) 완전 역색인(full inverted index) - 단어의 정확한 출현빈도 (문자 위치) 저장 블록 주소법(block addressing) - 텍스트는 블록 단위로 나누어지고, 출현빈도는 단어의 위치 대신 나타난 블록 - 텍스트 크기의 단지 5% 정도로 색인 구축 - 단점: 인접 질의(proximity query)시 선택된 블록 내에서의 온라인 검색 필요 최신정보검색론 Chapter8

block 1 block 2 block3 block 4 8.2 역파일(계속) This is a text. A text has many words. Words are made from letters block 1 block 2 block3 block 4 텍스트 어휘 출현빈도 letters made many text words 4… 2… 1, 2… 3… 역색인 [그림 8.2] 4개 블록에서의 블록 주소법을 이용한 역색인 [그림 8.2] 4개 블록에서의 블록 주소법을 이용한 역색인 최신정보검색론 Chapter8

8.2 역파일(계속) 비교 - 완전 역색인 : 모든 단어들에 대해 정확한 위치를 4바이트의 포인터로 역색인 - 문헌 주소법 색인(document addressing index) - 10Kb 크기의 문헌 - 포인터: 텍스트 크기에 따라서 1바이트, 2바이트, 또는 3바이트 - 블록 주소법 - 256K 또는 64K 블록 사용 - 포인터는 1 또는 2바이트로 표현 최신정보검색론 Chapter8

8.2 역파일(계속) 표 8.1 색인 소형컬렉션 (1 Mb) 중형컬렉션 (200 Mb) 대형컬렉션 (2 Gb) 단어 주소법 전체 텍스트 컬렉션에 대한 백분율로 표시된 역파일의 크기. 4개 단위의 주소법과 3가지 컬렉션 고려 왼쪽 열은 불용어를 색인하지 않은 경우이고, 오른쪽 열은 모든 단어를 색인한 경우 색인 소형컬렉션 (1 Mb) 중형컬렉션 (200 Mb) 대형컬렉션 (2 Gb) 단어 주소법 45% 73% 36% 64% 35% 63% 문헌 주소법 19% 26% 18% 32% 47% 64K블록 주소법 27% 41% 5% 9% 256K블록 25% 1.7% 2.4% 0.5% 0.7% 전체 텍스트 컬렉션에 대한 백분율로 표시된 역파일의 크기. 최신정보검색론 Chapter8

8.2.1 탐색 역색인의 탐색 알고리즘: 3단계 블록 주소법 - 어휘 탐색: 질의에 나타난 단어와 패턴은 분리되어 어휘 8.2.1 탐색 역색인의 탐색 알고리즘: 3단계 - 어휘 탐색: 질의에 나타난 단어와 패턴은 분리되어 어휘 내에서 탐색 - 출현빈도의 탐색: 발견된 모든 단어의 출현빈도 목록 탐색 - 출현빈도의 처리: 구와 근접 또는 불리안 연산을 해결하기 위해 출현빈도 처리 블록 주소법 - 블록 순회 필요, 질의 처리비용은 텍스트 크기에 대해 선형 비례 예) 250Mb 텍스트 완전 역색인 탐색 시간 - 단순한 하나의 단어 탐색: 0.08초 - 2개에서 5개의 단어를 가진 구 탐색: 0.25∼0.35초 최신정보검색론 Chapter8

8.2.1 탐색(계속) - 어휘를 분리된 파일로 관리: 주기억장치에 저장 8.2.1 탐색(계속) - 어휘를 분리된 파일로 관리: 주기억장치에 저장 - 단일어 질의(single-word query) : 탐색 속도 증진 해싱, 트라이, B-트리 사용 해싱과 트라이: 텍스트 크기에 관계없이 O(m)의 탐색 비용 사전 편집 순으로 단어 저장: 더 작은 공간, 이진 탐색 이용 O(log n)비용 - 접두사(prefix)와 범위 질의(range query) 해싱을 제외한 이진 탐색, 트라이, B-트리로 해결 - 문맥 질의(context query) 구 질의, 근사 질의 모든 요소에 대한 목록들은 동기화 되어서 순회 최신정보검색론 Chapter8

8.2.2 구축 색인 (두 파일로 분리) 1. 포스팅 파일(posting file): 출현빈도 목록을 연속적으로 저장 8.2.2 구축 색인 (두 파일로 분리) 1. 포스팅 파일(posting file): 출현빈도 목록을 연속적으로 저장 2. 어휘는 사전 편집 순으로 저장되고, 위 파일의 각 단어에 대한 목록 포인터 포함 어휘 트라이 [그림 8.3] 예제 텍스트를 위한 역색인 만들기 [그림 8.3] 예제 텍스트를 위한 역색인 만들기 최신정보검색론 Chapter8

8.2.2 구축(계속) 구축 소요 시간 트라이: 각 텍스트 글자마다 O(1)의 연산 수행, 최악의 경우 O(n) 최신정보검색론 8.2.2 구축(계속) 구축 소요 시간 트라이: 각 텍스트 글자마다 O(1)의 연산 수행, 최악의 경우 O(n) [그림 8.4] 부분 색인들의 이진 형태 병합. 사각형은 부분 색인, 둥근 사각형은 병합 연산 [그림 8.4] 부분 색인들의 이진 형태 병합. 사각형은 부분 색인, 둥근 사각형은 병합 연산 알고리즘의 총 비용: O(n log(n/M)) 최신정보검색론 Chapter8

[그림 8.5] 관심 부분을 색인 포인트로 표시한 예제 텍스트 8.3 다른 색인 기법 8.3.1 접미사 트리와 접미사 배열 [그림 8.5] 관심 부분을 색인 포인트로 표시한 예제 텍스트 [그림 8.5] 관심 부분을 색인 포인트로 표시한 예제 텍스트 최신정보검색론 Chapter8

[그림 8.6] 예제 텍스트에 대한 접미사 트라이와 접미사 트리 8.3.1 접미사 트리와 접미사 배열(계속) [그림 8.6] 예제 텍스트에 대한 접미사 트라이와 접미사 트리 [그림 8.6] 예제 텍스트에 대한 접미사 트라이와 접미사 트리 최신정보검색론 Chapter8

This is a text. A text has many words. Words are made from letters 8.3.1 접미사 트리와 접미사 배열(계속) 구조 This is a text. A text has many words. Words are made from letters 1 6 9 11 17 19 24 28 33 40 46 50 55 60 텍스트 60 50 28 19 11 40 33 접미사 배열 [그림 8.7] 예제 텍스트에 대한 접미사 배열 [그림 8.7] 예제 텍스트에 대한 접미사 배열 최신정보검색론 Chapter8

This is a text. A text has many words. Words are made from letters 8.3.1 접미사 트리와 접미사 배열(계속) 구조(계속) This is a text. A text has many words. Words are made from letters 1 6 9 11 17 19 24 28 33 40 46 50 55 60 텍스트 lett text word 상위 색인 [그림 8.8[ 접미사 배열에 대한 상위 색인(supra-index) 60 50 28 19 11 40 33 접미사 배열 [그림 8.8] 접미사 배열에 대한 상위 색인(supra-index) 최신정보검색론 Chapter8

This is a text. A text has many words. Words are made from letters 8.3.1 접미사 트리와 접미사 배열(계속) 구조(계속) This is a text. A text has many words. Words are made from letters 1 6 9 11 17 19 24 28 33 40 46 50 55 60 텍스트 Letters made many text word 어휘 상위 색인 [그림 8.9] 색인 리스트와 어휘 상위 색인을 가지는 접미사 배열과의 관계 60 50 28 19 11 40 33 접미사 배열 60 50 28 11 19 33 40 역 리스트 [그림 8.9] 색인 리스트와 어휘 상위 색인을 가지는 접미사 배열과의 관계 최신정보검색론 Chapter8

8.3.1 접미사 트리와 접미사 배열(계속) 탐색 250Mb 텍스트에 대한 탐색 시간 - 하나의 단어나 구에 대해 약 1초 정도가 소요 - 해당 텍스트의 액세스와 관련된 부분은 총 0.6초 이상이 소요되며, - 상위 색인의 사용은 총 소요 시간을 0.3초로 낮출 수 있다. 최신정보검색론 Chapter8

8.3.1 접미사 트리와 접미사 배열(계속) 대용량 텍스트에 대한 접미사 배열의 구축 1) 첫번째 블록에 대한 접미사 배열을 만든다. 2) 두번째 블록에 대한 접미사 배열을 만든다. 3) 두 개의 접미사 배열을 병합한다. 4) 세번째 블록에 대한 접미사 배열을 만든다. 5) 앞에서 병합한 것과 새로운 접미사 배열을 병합한다. 6) 네번째 블록에 대한 접미사 배열을 만든다. 7) 앞에서 병합한 것과 새로운 접미사 배열을 병합한다. 8) 모든 블록들이 병합될 때까지 반복한다. 최신정보검색론 Chapter8

8.3.1 접미사 트리와 접미사 배열(계속) 최신정보검색론 Chapter8 [그림 8.10] 대용량 텍스트를 위한 접미사 배열 구축 과정 [그림 8.10] 대용량 텍스트를 위한 접미사 배열 구축 과정 (a) 지역 접미사 배열이 만들어진다. (b) 카운터가 계산된다. (c) 접미사 배열들이 병합된다. 최신정보검색론 Chapter8

8.3.2 요약 파일 요약 파일(signature file) - 해시 함수를 기반으로 한 단어 기반(word-oriented) 8.3.2 요약 파일 요약 파일(signature file) - 해시 함수를 기반으로 한 단어 기반(word-oriented) 색인구조 - 구조: 단어를 비트로 매핑하여 B개의 비트로 만드는 해시 함수(요약)를 이용 텍스트를 b개의 단어를 가지는 블록으로 분할 최신정보검색론 Chapter8

block 1 block 2 block3 block 4 8.3.2 요약 파일(계속) 구조 This is a text. A text has many words. Words are made from letters block 1 block 2 block3 block 4 텍스트 000101 110101 100100 101101 텍스트 요약 h(text) = 000101 h(many) = 110000 h(words) = 100100 h(made) = 001100 h(letters) = 100001 [그림 8.11] 블록으로 나누어진 예제 텍스트에 대한 요약 파일 요약 함수 [그림 8.11] 블록으로 나누어진 예제 텍스트에 대한 요약 파일 최신정보검색론 Chapter8

8.5 불리안 질의 최적화 구현의 예 AND AND 4 6 1 4 6 OR 1 4 6 2 3 4 6 7 2 4 6 2 3 7 (b) AND AND AND AND AND 4 AND 6 그림 8.12 질의 구문 트리의 내부 노드들의 처리. 1 1 OR 2 4 OR 2 4 OR 3 4 OR 4 6 OR 6 OR 7 4 3 4 3 4 7 6 7 7 [그림 8.12] 질의 구문 트리의 내부 노드들의 처리. (a) 전체 평가 (b) 지연 평가 최신정보검색론 Chapter8

8.5 순차 탐색 8.5.1 Brute Force(BF) 탐색: 최악의경우는O(mn)평균 O(n) a b r c d a b r [그림 8.13] 패턴 'abracadabra'에 대한 Brute-force 탐색 알고리즘 a a b r c d [그림 8.13] 패턴 'abracadabra'에 대한 Brute-force 탐색 알고리즘 최신정보검색론 Chapter8

8.5.2 Knuth-Morris-Pratt(KMP) [그림 8.15] 집합 'hello', 'elbow', 'eleven'에 대한 모든 실패 전이 중에서 [그림 8.14] 'abracadabra'를 탐색하는 KMP 알고리즘 왼쪽은 next 함수의 예 , 'abracada'에 정합된 이후, 다음 문자가 'b'가 아니므로 마지막 'a'까지 정합시키려고 시도하지 않음 오른쪽은 탐색의 예: 암영 부분은 재사용된 접두사 정보 최신정보검색론 Chapter8

8.5.2 Knuth-Morris-Pratt(KMP)(계속) [그림 8.15] 집합 'hello', 'elbow', 'eleven'에 대한 모든 실패 전이 중에서 단지 하나를 보여주는Aho-Corasick 트라이의 예 [그림 8.15] 집합 'hello', 'elbow', 'eleven'에 대한 모든 실패 전이 중에서 단지 하나를 보여주는Aho-Corasick 트라이의 예 최신정보검색론 Chapter8

8.5.3 Boyer-Moore Family(BM) 윈도우 내부의 검사가 역 방향(backward)으로 처리 알고리즘의 공간과 전처리 시간: O(m+sigma) 탐색 시간: 평균 O(n log (m)/m), 최악의 경우 O(mn) a b r c d r a a b r c d a [그림 8.16] 'abracadabra'를 탐색하는 BM 알고리즘. r a [그림 8.16] 'abracadabra'를 탐색하는 BM 알고리즘.사각형 부분은 수행된 비교, 암영 부분은 이미 비교된 부분. 점선 사각형은 선택되지 않은 정합 휴리스틱 최신정보검색론 Chapter8

8.5.4 Shift-Or 비트 병렬성(bit-parallelism) 기반 최악의 경우 O(mn/w)시간 (최적의 속도 향상). [그림 8.17] 'abracadabra'를 탐색하는 비결정적 오토마타와 연관된 B 테이블. [그림 8.17] 'abracadabra'를 탐색하는 비결정적 오토마타와 연관된 B 테이블. 최초 루프는 어느 문자와도 일치되며, 각 테이블 열은 오토마타의 에지에 대응. 최신정보검색론 Chapter8

8.5.5 접미사 오토마타 Backward DAWG Matching(BDM) 알고리즘 8.5.5 접미사 오토마타 Backward DAWG Matching(BDM) 알고리즘 - 접미사 오토마타 기반: 패턴 P상의 접미사 오토마타는 P의 모든 접미사들을 인식 - 최악의 경우: O(mn), 평균 O(n log (m)/m)시간 [그림 8.18] 비결정적 접미사 오토마타. [그림 8.18] 비결정적 접미사 오토마타. 점선은 ε전이(입력 없이 발생되는 전이), I는 오토마타의 초기 상태. 최신정보검색론 Chapter8

8.5.5 접미사 오토마타(계속) MultiBDM : BDM 알고리즘의 다중패턴 버전. a b r c d X X X X 8.5.5 접미사 오토마타(계속) MultiBDM : BDM 알고리즘의 다중패턴 버전. a b r c d X X X X [그림 8.19] 'abracadabra' 패턴을 위한 BDM 알고리즘. [그림 8.19] 'abracadabra' 패턴을 위한 BDM 알고리즘. 사각형은 텍스트 윈도우와 비교되는 요소 X는 패턴 접두사가 인식되는 위치. 최신정보검색론 Chapter8

8.5.6 실제적인 비교 최신정보검색론 Chapter8 [그림 8.20] 알고리즘들 사이의 실제적인 비교. 8.5.6 실제적인 비교 [그림 8.20] 알고리즘들 사이의 실제적인 비교. [그림 8.20] 알고리즘들 사이의 실제적인 비교 위 왼쪽 : 영어 텍스트 상에서의 짧은 패턴 탐색, 위 오른쪽 : DNA상에서의 긴 패턴의 경우 아래 : 64문자로 구성된 임의 텍스트 상에서의 짧은 패턴 탐색 경우 시간은 1Mb당 10분의 1초. 최신정보검색론 Chapter8

8.6 패턴 정합 8.6.1 오류 허용 문자열 정합 동적 프로그래밍 행렬 C[0..m, 0..n]은 열 단위로 채워진다. 8.6 패턴 정합 8.6.1 오류 허용 문자열 정합 동적 프로그래밍 행렬 C[0..m, 0..n]은 열 단위로 채워진다. C[i, j]는 의 접미사와 를 정합시키는데 필요한 최소 에러 수 최신정보검색론 Chapter8

8.6.1 오류 허용 문자열 정합(계속) s u r g e y 1 2 3 v 4 5 6 8.6.1 오류 허용 문자열 정합(계속) 알고리즘은 O(mn)시간, O(m) 공간, 전처리 시간 O(m) s u r g e y 1 2 3 v 4 5 6 [그림 8.21] 'surgery' 텍스트에서 'survey'를 탐색하는 두 개의 오류를 허용하는 [그림 8.21] 'surgery' 텍스트에서 'survey'를 탐색하는 두 개의 오류를 허용하는 동적 프로그래밍 알고리즘. 굵은 글씨로 표시된 엔트리들은 일치된 위치. 최신정보검색론 Chapter8

8.6.1 오류 허용 문자열 정합(계속) 오토마타 최신정보검색론 Chapter8 8.6.1 오류 허용 문자열 정합(계속) 오토마타 [그림 8.22] 두 개의 오류를 가진 패턴 'survey'의 근사 문자열 정합을 위한 NFA. [그림 8.22] 두 개의 오류를 가진 패턴 'survey'의 근사 문자열 정합을 위한 NFA. 빗금친 상태는 텍스트 'surgery'를 읽고 난 후에 활성화된 것 아무런 표식이 없는 전이는 모든 문자와 정합. 최신정보검색론 Chapter8

8.6.2 정규식과 확장 패턴 최신정보검색론 Chapter8 [그림 8.23] 정규식 b b*(b | b*a)에 대한 8.6.2 정규식과 확장 패턴 [그림 8.23] 정규식 b b*(b | b*a)에 대한 [그림 8.23] 정규식 b b*(b | b*a)에 대한 비결정적 오토마타(a)와 결정적 오토마타(b) 최신정보검색론 Chapter8

8.8 압축 8.8.1 순차 탐색 최신정보검색론 Chapter8 8.8 압축 8.8.1 순차 탐색 [그림 8.24] 왼쪽은 하나의 오류를 허용하는 간단한 패턴 'rose'에 대한 탐색. [그림 8.24] 왼쪽은 하나의 오류를 허용하는 간단한 패턴 'rose'에 대한 탐색. 오른쪽은 구 'ro* rose is'에 대한 탐색, 여기서 'ro*'는 접두사 탐색. 최신정보검색론 Chapter8

8.9 연구 동향 및 쟁점 문헌 데이터베이스에 대한 색인과 탐색의 주요 동향 - 탐색은 더욱 복잡해진다. - 텍스트 컬렉션은 더욱 대규모화 된다. - 탐색은 더욱 복잡해진다. - 압축은 실제 업무에서 인기가 있다. 최신정보검색론 Chapter8

8.9 연구 동향 및 쟁점(계속) 최신정보검색론 Chapter8 [그림 8.25] 색인 공간과 단어 탐색 시간 사이의 트레이드 오프 [그림 8.25] 색인 공간과 단어 탐색 시간 사이의 트레이드 오프 최신정보검색론 Chapter8