2.2 역색인

(1)

2013. 09. 08

가천대학교 IT대학 컴퓨터미디어융합학과

Information Retrieval

제2장 색인

(2)

2.1 개요

2.2 역색인

2.3 Trie index

2.4 Tree index

2.5 Signature file

(3)

3

Why Index?

찾아보기 수단은?

Index is power of Search.

^탐색이란^색인이다^.

색인이 있어야 신속하고 정확한 탐색이 가능.

(4)

2.1 개요

질의 검색

온라인 검색: 다수를 검색하는 비중이 높을 때.

ex. 학기말에 성적을 처리할 때

색인 검색: 극소수만 검색하는 비중이 높을 때.

ex. 학번으로 재학증명서를 요구할 때

질의 검색

온라인 검색/

순차 탐색

색인 검색

직접 자료 파일 탐색 (파일이 작을 때)

보조 파일 탐색 (파일이 클 때)

(5)

5

2.1 개요

질의 검색 온라인 검색

- 텍스트에서 직접 원하는 패턴을 검색 - 언제 사용하는가?

-텍스트가 작을 때

-텍스트가 자주 수정되고 소멸될 때 -색인 공간의 여유가 없을 때

색인 검색

검색 속도를 높이기 위한 자료구조 언제 사용?

- 문서 집합이 크고 자주 변하지 않을 때

색인 기술: 역파일, 접미사 배열, 요약 파일

(6)

2.1 개요

색인/찾아보기 index 정보검색에서 색인의 역할

순서 색인의 역할

1 질의와 문서 집합의 연결 수단

2 (질의와 문서의) 주제를 표현하는 키워드 3 탐색 속도를 향상하는 보조 파일

4 특정 문자의 위치를 표시하는 자료 목록

(7)

7

2.1 개요

색인/찾아보기 index Index Def.

- data structure constructed from the text to speed up the search.

- 문서나 질의의 주제를 표현하는 단어.

- 사용자와 Database 사이에서 정보를 효율적으로 찾아주는 단어.

- 검색하려는 단어를 문서에서 추출하여 작성한 파일

- 문서에서 중요한 단어들을 추출하여 그 단어의 본문 위치 를 기록한 파일

색인이 없으면

모든 문서(파일)를 직접 탐색.

모든 데이터베이스를 직접 탐색.

(8)

2.1 개요

색인/찾아보기 index 색인의 주요 주제: database의 연구 주제

순서 내 역 비 고 1 색인 구조

2 색인 생성 수동, 자동

3 색인 저장 저장 구조, 압축 기법 4 색인 처리 검색 기법, 시간

5 색인 갱신

(9)

9

2.1 개요

색인의 종류

1) 기본키 색인………. 자료 검색용 색인

개체를 고유하게 식별할 수 있는 자료………….키기반 검색

e.g. 학번, 군번, 주민번호

2) 보조키(키워드 ) 색인………..문서 검색용 색인

문서 안에 있는 단어를 색인으로 활용…………..내용기반 검 색

색인어 index term:

주제를 표현하는 단어.

키워드, 핵심어, 주제어

색인화 indexing:

색인어와 색인어가 포함된 문서를 연결하는 것.

(10)

2.1 개요

색인의 기본 구조 Keyed File:

고유한 키 값으로 구성된 색인.

군번이 ‘73-02476’인 사람을 찾아라

(11)

11

2.1 개요

색인의 기본 구조

Inverted File:

내용으로 구성된 색인: ‘홍길동’을 찾아라.

(12)

2.1 개요

색인의 기본 구조 Inverted File:

중복을 허용하는 색인: 전산부 직원을 찾아라.

(13)

13

2.1 개요

색인의 기본 구조

Inverted File:

색인을 주기적으로 갱신해야 하는 부담.

작은 내용으로 큰 내용 찾기

정보검색의 보조키

(14)

2.1 개요

색인의 유형 1 색인의 분류

분류

기준 색인 종류 내 역

키

기본 키 색인 기본 키를 색인으로 구성: 한 파일에 한 개만 가능 보조 키 색인 보조 키를 색인으로 구성: 한 파일에 복수 개 가능

주제

키워드 색인 문서의 자체의 개념(주제)을 기준으로 색인 구성 속성 색인 문서를 만든 정보를 기준으로 색인 구성

실례: 제목, 출판사, 출판년도, 저자,, 추출

방식

유도 색인 문서에 있는 단어로 색인을 구성

할당 색인 필요한 용어들을 기반으로 인위적으로 색인을 구성

(15)

15

2.1 개요

색인의 유형 1

주제에 의한 분류 1) 주제 색인

내용과 주제를 분석하고 대표적인 중요 개념을 추출하여 선 택.

- 이용자 관점의 색인

2) 비주제 색인

문서의 속성을 이용하여 색인어를 생성.

- 컴퓨터 중심의 색인

ex. 저자, 표제, 기관명, 출판년도, ISBN,,,

(16)

2.1 개요

색인의 유형 2 색인어 추출 방식에 의한 분류

본문에 있는 단어와 의도적으로 만드는 단어로 분류

1) 자연언어 색인/유도 색인

문서의 본문에서 발췌하여 만든 색인어.

- 키워드 색인

저자가 사용한 용어가 해석 없이 그대로 색인어로 사용됨 단점

유사어 동의어 등이 검색에서 누락될 위험 재현율과 정확율 저하

(17)

17

2.1 개요

색인의 유형 3

2) 통제언어색인/할당 색인

동일한 개념이나 의미상 관련 있는 용어들을 모으고 어형을 통일

통제 어휘로부터 할당된 색인어 index term.

- 통제 어휘가 시소러스가 아니면 기술자 descriptor라고 함.

- 통제 어휘에서 만들 수 없으면 식별자 identifier를 생성.

통제어휘집

분류표, 주제명표목표, 시소러스 등 단점

개념 분석 후에 한 단계 추가  추가 비용 주제명표목표 subject heading list : 자연어로 된 용어들의 통제어휘. 융통성이 분류 표보다 낫고 시소러스만 못하다. 단행본 이외의 정보 표현과 검색에 사용

(18)

2.1 개요

색인 작업 지적인 작업: 인간이 수행

기계적 작업: 색인 엔트리의 자모순 배열과 형태 자동 색인 (기계 색인)

지적인 작업과 기계적 작업을 모두 컴퓨터가 수행한 색인.

키워드 인접성, 위치, 확률, 언어학에 기반.

(19)

19

2.1.2 내용기반 색인

전문 검색 full text search Def.

- 전체 문서의 내용을 색인으로 제공하여 원하는 문서 찾기.

- 주어진 질의 내용으로 문서 전체를 검색하여 찾기.

내용기반 색인 content-based retrieval Def.

- 특정한 내용이 포함되어 있는 파일을 찾는 작업.

- 질의 내용이 포함된 파일을 찾는 일.

- 작은 내용을 기반으로 많은 내용이 포함된 파일을 찾는 일.

ex. 문서 검색:

특정한 단어가 주어지면 그 단어들이 포함된 문서들을 검색.

(20)

2.1.2 내용기반 색인 C

ontent-Based Retrieval : CBR 특징

여러 개의 키워드로 문서를 검색하면 복수의 결과가 검색.

우선 순위 필요

유사도 검색, not exact match

내용기반 색인의 목적

순서 내 역

1 특정 주제를 포함하는 문서를 쉽게 검색

2 주제 영역을 정의함으로써 문서 간의 연계 기능 제공

(21)

21

2.1 개요

내용기반 검색의 문제점

Information Seeker Authors

Concepts Concepts

Query Terms Document Terms

Do these represent the same concepts?

(22)

2.1 개요 내용기반 검색

내용기반 색인 :

 문서 분석을 통하여 선정된 문서 대표 주제

 문서 내에서의 선정된 용어 + 용어의 위치

 빈도 수치, 관련 수학법칙, 저자 인용사항 등 다양

(23)

23

2.1 개요 내용기반 색인

색인어를 결정하는 관점

 고 출현빈도 용어: 부적합

 일상적인 용어는 문헌의 주제와 특별한 관련이 없 다

 예) 그러나, 그리고, and , or , the

 저 출현빈도 용어: 부적합

 문헌의 한 두 번 나오는 용어는 부적합

 예) 서문, 요약, 결론 등

 일반적으로 위의 두 경우 사이에 나오는 용어를 색인 용어로 고려

(24)

2.2 역색인

2.2.1 역 색인 inverted index Def.

-문서 파일에서 용어 탐색 속도를 향상하기 위하여 용어와 용어의 주소 로 만든 색인.

-특정한 키워드가 어떤 문서에서 나타났는지를 알려주는 자료구조.

어휘: 문자열에 있는 모든 상이한 단어나 용어의 집합 발생: 단어의 위치를 포함하는 모든 문서 목록

가 정:

문서 = set of words, set of keywords 역색인: ordered list of keywords

단어-문서 색인은 해시 테이블, 정렬 배열, 트리 등으로 구현.

역 파일은 IRS와 탐색 엔진에서 가장 널리 사용되는 색인.

(25)

25

2.2 역색인

2.2.1 역 색인 inverted index 자료 검색

키로 문서의 내용을 검색

y = f(x)

x: 키

y: 검색하려는 내용

정보 검색: 자료 검색의 역함수 내용으로 내용을 검색

x = f

^-1

(y)

y: 검색하려는 내용 x: 원하는 문서의 키값

(26)

2.2 역색인 2.2.1 역 색인 inverted index

역파일 구조

색인 파일, 포스팅 파일, 자료 파일 1) 색인 파일:

어휘를 사전 순으로 저장, dictionary 라고도 함 키워드, 관련 레코드 수, 포스팅에 대한 포인터 2) 포스팅 파일:

키워드를 포함한 자료 레코드에 대한 포인터의 리스트.

발생 빈도, 가중치, 단어 위치 3) Document 파일

실제 텍스트를 포함하는 문서 파일

색인과 포스팅 파일 분리 이유: 검색 시 메모리에서 검색 가능

(27)

27

2.2 역색인 2.2.1 역 색인 inverted index

역파일 장점

- 구현 용이 - 속도 빠름

- 동의어 쉽게 지원: 색인에 threaded list로 표현 가능 - 대다수 검색 엔진에서 사용: Dialog, BRS, Orbit, Stairs 단점

- 공간 소요: 자료 파일의 300%까지 - 키워드에 많은 정보 유지 경우

- 색인의 갱신, 재구성 비용 크게 증가

(28)

2.2 역색인 2.2.1 역 색인 inverted index

역파일

임시 파일:

{색인어, 문서번호, 색인어 빈도수, 문서 위치}

포스팅 파일

{색인어, 문서번호, 색인어 빈도수, 문서 위치}

색인 파일

{(색인어, 문서의 수, 포스팅 레코드 위치)}

(29)

29

2.2 역색인

역 색인 파일의 구조

0 2 2

posting file

4 3

1 3 2

2 2

..

1 2 ..

5 1 ..

5 2 ..

Doc 2: This is a text file. Index is a short text file … text is a good ..

색인어: text, file, index, text, file, text

색인어 df

text 4

file 3

index 2

문자열 처리

역색인

df: document frequency tf: term frequency

ptr: pointer to posting & document file

Index file

Doc 0 text

ptr

..

Doc# tf ptr

Doc 1 text text Doc 2 text File … index, text, file..

text

document file Doc 3 file file

Doc 4 text text

..

Doc 5 index index file posting file

색인어 순 1

2

3 임시 파일

file 2 2 ..

색인 Doc# tf ptr

index 2 1 ..

text 2 3 ..

색인어 추출

2 1 ..

(30)

2.2 역색인

2.2.1 역 색인 구조 역색인 구축 및 검색 과정

(31)

31

2.2 역색인 2.2.1 역 색인 inverted index

역색인 구축과 검색과정

순 서

작업 과

정 내 역 비 고

1

색인 구축

임시 파일 생성 문서 집합에서 색인어를 추출

2 포스팅 파일 구축 임시 파일에서 포스팅 파일을 구축 3 색인 파일 구축 포스팅 파일에서 색인 파일 구축 4

질의 (검색)

질의: 색인 파일

탐색 사용자가 질의하면 색인 파일 탐색

5 포스팅 파일 탐색 색인 파일에서 얻은 정보로 포스팅 파 일 탐색

6 문서 파일 탐색 포스팅 파일에서 얻은 정보로 문서 검 색

(32)

2.2.2 역색인의 실례와 장단점

<용어, 주소>: <단어, 단어의 위치>

용어의 알파벳 순서로 정렬된 파일.

전문 역색인full inverted index 과 블록 block 역색인 으로 구 분

전문 역색인

There is a book. A book has many figures. Figures are made from lines.

1 12 20 29 34 43 53 63

12, 20...

34, 43...

63...

53...

28...

단어 주소

Inverted index book

figures lines made many

document

(33)

33

2.2 역색인 블록 역색인

블록 역색인

Block 1 Block 2 Block 3 Block 4

book figures lines made many

1, 2...

3...

4...

2...

단어 블록 주소

Inverted index document

(34)

2.2 역색인 블록 역색인

문서를 블록 단위로 나누고, 단어의 위치는 블록 주소로 저장.

블록 검색 + 블록 내 단어 검색

장점: 공간 절약. 블록의 수 < 단어의 수

단점: 블록 안에서 재 검색. 원거리 검색 곤란 역색인의 종류

색인 이름 특 징

접미사 Trie 색인 키의 길이에 따라서 가변적으로 키를 구성하는 트리 구조

접미사 Tree 색인 키를 구성하는 문자를 생략하여 트리의 높이를 낮춘 트리 구조

(35)

35

2.3 Trie

역색인 구축

접미사 트라이trie, 접미사 트리, 접미사 배열, 요약 파일 2.3.2 Trie

Def. tree of degree m>= 2 in which the branching at any level is determined not by the entire key value but by only a portion of it.

전체 키 값이 아니라 키의 일부분으로 분기가 결정되는 트리.

- 키가 스트링인 연관적인 배열을 저장하기 위하여 사용되는 순서화된 트리 .

키 값이 가변 크기일 때 유용.

구성: 2 types of node.

branch node, information node:

key value: one of the 26 letters of alphabet.

blank: terminate a key value.

(36)

2.3 Trie

Trie example

key values: blue, buy, goose, hello, hen, hotel

...

A B G H

goose

...

L

blue buy

U

...

E O

...

L N

hello hen

hotel Z

goose

blue buy

hello hen

hotel

‘b’ ‘g’ ‘h’

‘l’ ‘u’ ‘e’ ‘o’

‘l’ ‘n’

(37)

37

2.3 Trie

2.4.2 접미사 트라이

알파벳 순서의 최단거리 색인 구축. 잎 노드 에 주소 저장.

line 63

made 53 figure

34,43 book

12,20

many 29

‘l’ ‘m’

‘d’

‘n’

‘b’ ‘f’

단어 트라이

(a) fox가 추가 되기 전

1 12 20 29 34 43 53 63

‘a’

(b) fox가 추가 된 후 line

63

figure 34,43 book

12,20

‘l’ ‘m’

‘a’

‘b’ ‘f’

단어 트라이

made 53 many

29

‘d’

fox 73

‘i’ ‘o’

(38)

2.3 Trie

2.3.2 Suffix Trie 장 점

- 효율적 공간 구현

- 복잡한 질의를 효율적으로 처리

- 유전 DB같이 광범위한 응용범위에 적합 단 점:

- 구축 비용 과다

- 질의 시점에 텍스트 필요,

- 결과가 위치순서대로 되지 않음

- 복잡하지 않은 질의는 역파일이 우수

(39)

39

2.4 Tree 색인

2.4 접미사 트리 suffix tree 역색인 구축

‘f’

‘ m

’

‘a’

‘d’

‘b’ ‘l’

1

3

‘l’ ‘m’

‘d’ ‘n’

‘b’ ‘f’

5 6

‘’ ‘.’

‘I’

‘g’

‘u’

‘o’

‘k’

‘’ ‘.’

(a) 접미사 트라이 (b) 접미사 트리

53 29

20 12

43 34

63 63

1 12 20 29 34 43 53 63

‘r’

‘e’

‘s’

‘’

(40)

2.4 Tree 색인 2.4 접미사 배열 Suffix Array

접미사 트리의 잎 노드들을 위에서 아래로 순회할 때와 동일 순서.

또는 접미사 트리의 왼쪽 잎 노드부터 오른쪽 잎 노드로 순회 2진탐색 가능. O(logN)

오버 헤드: 색인된 접미사마다 포인터 필요  40% 공간 증가 부담

20 12 43 34 63 53 29 접미사 배열

1 12 20 29 34 43 53 63

(41)

41

2.4 Tree 색인

2.4 접미사 배열 Suffix Array

상위(다단계) 색인의 접미사 배열

트리의 규모가 커지면 색인을 추가.  다단계 색인.

book figure line 상위 색인

접미사 배열

1 12 20 29 34 43 53 63

20 12 43 34 63 53 29

(42)

2.4 Tree 색인

2.4 접미사 배열 Suffix Array

역색인 리스트와 접미사 배열의 관계.

상위 색인

접미사 배열

역색인 리스트 book figure line made many

1 12 20 29 34 43 53 63

20 12 43 34 63 53 29

12 20 34 43 63 53 29

(43)

43

2.5 요약 파일

2.5 Signature file

문서와 질의를 signature로 기호화하고 비교하여 탐색.

구조: 해시 함수 Inexact

다른 키워드의 해싱 결과가 동일한 시그니처를 생성 가능.

블록 색인 생성 절차

1. 텍스트를 블록으로 나눈다.

2. 블록 안에 있는 키워드를 해싱한다.

3. 블록에 대한 비트 마스크를 구한다.

4. 블록 안에 있는 모든 단어의 요약 파일을 비트 단위로 OR 연산을 수 행

(44)

2.5 시그니처 파일

(45)

h(book) = 000101 h(many) = 110000 h(figure) = 100100 h(made) = 001100 h(lines) = 100001

질의와동일 검색 성공 ORing

111101 100001

질의 lines

ANDing

h(lines)

100001

블록 요약 질의 요약

요약 집합

색인어

해시

1 12 20 29 34 43 53 63

45

2.5 시그니처 파일

(46)

2.5 시그니처 파일

텍스트 문서에 대한 요약 색인

101010 110001 011010 000111 101100

단어 해시 값(요약 값) 주소 book

figures lines made many

document

12, 20 34 43 63 53 29

1 12 20 29 34 43 53 63

(47)

47

2.5 시그니처 파일

검색 방법

질의를 해싱한 값과, 블록 코드와 ANDing한 결과를 비교.

h(many)  110000 AND Block2 시그니처  결과 비교

This is a text. A text has many words. Words are made from letters.

Block 1 Block 2 Block 3 Block 4

h(book) = 000101 h(many) = 110000 h(figure) = 100100 h(made) = 001100 h(lines) = 100001

Signiture hash function

000101 110101 100100 101101

(48)

2.5 시그니처 파일 2.5 Signature file 시그니처 파일이 적합한 경우

- PC에서 사용되는 중 규모 DB

- 검색 질의 빈도가 낮은 DB. B-tree 색인보다 저렴.

- 추가 삽입만 필요한 WORM 형식의 광디스트 - 병렬 처리되는 DB

장점

- full text 검색보다 2배 정도 빠름.

- 텍스트 파일의 10 ~ 15%의 추가 공간

역 파일기법의 인덱스: 50 ~ 300%의 추가 공간 - 추가적인 삽입만을 허용하므로 삽입 연산이 간단 - 순차탐색 비용이 텍스트 크기의 10-20%.

(49)

49

2.5 시그니처 파일

2.3.5 Signature file

단점

대규모 DB에서 속도가 저하. ………대책: 압축 레코드 수에 비례하여 속도 저하.

Hashing: 다른 단어가 동일한 시그니처 생성

ORing: 블록 시그니처 생성 시 우연히 동일한 결과 생성 false drop

시그니처 구성에 사용되지 않은 키워드가 검색되는 것

(50)

50

2.6 요점 정리

색인

파일이 클 때 자료를 빨리 찾기 위한 수단 보조 파일. 색인 검색  온라인 검색 색인의 역할

질의와 문서의 연결  주제 표현  속도 향상 색인의 종류

키: 기본키 색인, 보조키 색인(유일, 중복) 주제: 키워드 색인, 속성 색인

추출: 유도색인, 할당색인 내용기반 색인

전문 검색, 내용기반 검색

(51)

51

2.6 요점 정리

역색인 inverted index: 내용으로 내용 찾기

y = f(x)  x = f^-1(y) 역파일의 구조

색인 파일, 포스팅 파일, 문서 파일 역파일 생성 절차

문서  임시 파일  포스팅 파일  색인 파일 역파일 검색 절차:

색인 파일  포스팅 파일  문서 역색인의 구조

전문 역색인 블록 역색인

(52)

2.6 요점 정리

Trie 색인

키값의 길이에 따라 색인을 만드는 트리 구조의 색인 Tree 색인

키값에 따라서 분기를 결정하는 색인 구조

접미사 트라이: 뿌리에서 잎까지 모든 문자 포함 접미사 트리: 뿌리에서 잎까지 필요한 문자만 포함

접미사 배열: 접미사 트리를 왼쪽에서 오른쪽으로 순회

요약 색인 signature index

키 값을 짧은 크기의 코드로 축소하여 검색 효율 향상