2.2 기본 개념 (문자열, 정규식(불리언 표현식), 유한 오토마타) 문자열

Presentation on theme: "2.2 기본 개념 (문자열, 정규식(불리언 표현식), 유한 오토마타) 문자열"— Presentation transcript:

1 2.2 기본 개념 (문자열, 정규식(불리언 표현식), 유한 오토마타) 2.2.1 문자열
제 2 장 정보검색에 관한 자료구조와 알고리즘 2.2 기본 개념 (문자열, 정규식(불리언 표현식), 유한 오토마타) 2.2.1 문자열 알파벳 , 문자열: 로부터의 유한한 길이의 기호들 xy: x와 y의 연결 w=xyz에 대하여, x는 w의 접두(prefix), y는 w의 접미(suffix) 2.2.2 문자열 사이의 유사성 거리함수 d(s1,s1)=0, d(s1,s2)>=0, d(s1,s3) <= d(s1,s2)+d(s2,s3) 해밍거리: 동일 위치에 서로 다른 기호 수 예) d(text,that)=2 편집거리: s1을 s2로 변화하기 위해 입력, 삭제, 치환되는 기호의 수 예) d(text, tax)=2

2 2.2.3 정규식(regular expresstion)
연결(concatenation), 결합(union: +), 반복(star/closure: *) 의 언어: C로부터의 문자열 집합 연결: L1L2 = {xy | x  L1 and y  L2} 반복: L* = , 양의(positive) 반복: L+ = LL* L0 = {}, Li = LLi-1, 언어 L내에서 만들어질 수 있는 모든 언어의 문자열 조합 에대한 정규식의 정의 (L(r): 정규식 r로 표현되는 언어 L내의 문자열 집합을 표기) : 공집합, : 집합 {}, 내의 각 기호 a에 대해, a: {a} p+q: L(p) U L(q), pq: L(p)L(q), p*: L(p)* : 로부터의 한 기호, r?: +r (r이 0번 혹은 1번 발생) [a1..am]: 로부터의 기호 범위, rk:

3 2.2.4 유한 오토마타 예) 1. <A> Scot 80 <W> (Kenilw+Discov)
2. <bl> [a..z]* </bl> 3. <EQ> (<LQ>)?<Q> <D> 161(0+1) </D> <A> Shak 4. <A> ((Sirb)?W)?bScottb? </A> 2.2.4 유한 오토마타 수학적 모델, 오토마톤: 테이프로부터 입력 (그림 2.1) 정의 (Q, , , q0, F) Q: 상태, : 입력알파벳, q0  Q: 초기상태, FQ: 최종상태 : Q(+{})에서 Q로의 함수 q0에서 시작, a 읽으면 (q,a)로 상태 전이 & 읽기 헤드 우이동 (q,a)가 유일한 값이면 DFA, 아니면 NFA 한 언어를 받아들이는 FA가 존재하면 “정규 언어” (그림 2.2) IR에서는 DFA를 탐색기계로 사용

4 2.3 자료구조 2.3.1 탐색트리 이진 트리: 주기억 장치에 적합
B-트리(균형 탐색 트리): 보조기억장치에 적합(내부 노드 많음) 차수가 2m인 경우 루트는 2~2m, 내부노드는 m~2m개 키 내부노드를 항상 반 이상 채운다 ki에 대하여, i-1번째 자노드의 모든 키는 ki보다 작고, i번째 자노드의 모든 키는 ki보다 크다 모든 잎(leaf)노드는 동일한 깊이를 갖는다 B+-트리: B-트리의 잎 노드에 모든 자료 저장 (그림 2.3) B-트리는 내부노드의 자료는 잎에 나타나지 않음 삽입: 상향식 삽입위치탐색->노드 분할(필요하면, 상위 노드 분할)

5 2.3.2 해싱 . 오버플로우 해결 기법 B*-트리: 이웃 노드의 여유가 있으면 이웃으로 옮김(분할x)
부분확장(partial expansion): 서로 다른 크기(2:3) 버켓 버켓 확장/분할 적응분할(adaptive split): 1/2크기의 두종류 버켓 분할 시 균형을 고려하지 않음 2.3.2 해싱 자료 순서를 임의화, 탐색 속도 빠름, 순차 처리는 불가 h(x): 키 x를 주어진 범위의 정수로 사상 (요약, signature) 주어진 범위에서의 균등 분포 값을 구함 “충돌”의 해결이 문제 개방 주소법: 충돌시 재해싱(새 색인값), 2개의 해싱함수 문제: 테이블 재구성 (그림 2.4) .

6 2.3.3 디지털 트리 오버플로우 주소법: 충돌시 오버플로우 영역에 저장 동일 해싱값의 키들은 서로 연결
문제: 해싱 본래의 취지 희석 (선형 탐색 필요) 문헌 DB에서는 주로 요약화일(signature file)사용 혼합기법 B-트리의 탐색시간 향상, 해싱기법의 범위탐색 허용 예) B+-트리의 버켓들을 해싱 테이블로 구성 2.3.3 디지털 트리 접두사 탐색: 디지털 트리, 이진 트라이 트라이(tries): 문자열의 디지털 분해를 사용하는 순환트리구조 매번 전체 키를 비교하지 않고 한번에 한비트씩 비교 한정된 후보 set내의 각각을 bit로 구분하는 과정 (그림 2.5) 패트리샤 트리: 단일 자손 노드가 제거된 트라이 (그림 2.6)

7 2.4 알고리즘 2.4.1 검색 알고리즘 여분 기억장소의 양에 따라 2가지로 구분 텍스트의 순차적 탐색: 여분이 거의 없을 때
색인 텍스트: 역화일, 요약화일 일반적으로 ‘검색 문제’ 문자열 t(텍스트), 정규식 q(질의)에 대하여, tmq*인 최초 위치 m>0를 찾거나 q가 나타난 모든 위치 혹은 횟수를 알아낸다

8 2.4.2 여과(filtering) 알고리즘 2.4.3 색인 알고리즘 텍스트의 크기를 줄이거나 탐색을 단순화
불용어목록(stoplist): 일반적인 단어만 남김 대소문자 변환, 특수기호/연속공백 제거, 숫자/날짜 표준화 스테밍: 접두(미)사 제거 자동 키워드 추출 2.4.3 색인 알고리즘 빠른 탐색에 적합한 자료구조를 만드는 것이 목표 역화일, 요약화일, 트리: 트리구조나 해싱에 근거 그 밖에 클러스터링(clustering, 군집) 등이 있음 텍스트에 대한 전체적인 처리 과정 : 그림 2.7 일부를 탐색(질의 수행)시간으로 이전 가능