정보검색 #3 색인(Indexing)

정보검색 시스템의 대략적인 그림

 

색인(Indexing) 이란?

효율적인 검색을 위해 [문서 집합]을 미리 가공해두는 과정을 의미합니다.

 

 

색인의 과정

1. 텍스트 추출 - 다양한 형식을 가진 문서에서 순수한 텍스트를 추출해냅니다.

2. 토큰 추출 - text를 검색하기 좋게 토큰화 시킵니다.

3. 불용어(Stop-word) 제거 - 의미를 가지지않아 필요없는 관용어, 불용어를 제거합니다.

- 불용어란 관사(a, the)처럼 의미를 가지지않는 용어를 말합니다.

 

4. 정규화 - 의미를 가진 용어를 기본형으로 바꾸고, 어간을 생성합니다.

영어에서는 Stemming(스태밍)이라고 해서 단어에서 항상 고정되는 어간을 추출합니다.

Stemming(스태밍), Stemmer

 

5. 역파일색인(Inverted Index)

문서에서 단어를 찾는 것이 아니라 색인을 통해 단어에서 특정 문서를 찾아내는 방법을 말합니다.

어려운 용어가 아니라, 우리가 평소에 책읽을때도 사용하는 방법입니다.

(대량의 문서 집합에서 '특정 키워드'가 포함된 문서를 색인하는 방법)

 

문서의 표현(Representation)

우리는 앞의 예제에서 D1 { 사과, 바나나, 바나나 } 와 같이 이미 전처리가 완료된 문서만 봤습니다.

그렇다면 실제 정보검색에서 문서는 어떤 식으로 저장, 색인해야 할까요?

 

1. a bag of word (단어 보자기)

그냥 텍스트에서 단어만 추출한 방법입니다. 중복을 고려하지 않습니다.

2. a set of word (단어의 집합)

단어를 set에 넣은 형태입니다. 중복을 고려해서 같은 단어는 1개만 저장합니다.

 

위 그림처럼, 단순히 생각해도 방법에는 여러가지가 있고 문서의 형태에 따라 구체적인 방법은 달라집니다.

만약 영어라면 스태밍을 거쳐 단어의 원형(어간)을 추출하는 방법을 사용했다면

한국어의 경우 명사형태를 추출하여 형태소분석, 품사종류 태깅, 복합명사 분해등의 과정이 필요할 것입니다.

 

색인 단위

의미를 색인 단위로 사용한 경우

어절을 색인 단위로 사용한 경우, 음절-gram은 말 그대로 소리나는 글자 수를 기준으로 쪼개 추출하는 방법입니다.

여담으로, 한국어는 의외로 명사추출이 아닌 음절-2gram을 많이 이용합니다. 명사추출을 사용할려면 신조어를 계속해서 추가하며 최신화 되어있는 대형 사전데이터(형태소 분석기, 품사 태깅) 필요하고, 음절-gram이 생각보다 성능이 좋습니다.

 

요약

1. 색인(Indexing) 모듈

2. 역파일색인(Invert Indexing) 모듈

3. 문서 검색(Retrieval) 모듈

위 과정은 아래 그림의 파란부분에 해당됩니다.

 

정보검색 시스템의 대략적인 그림

 

퀴즈

1. 다음 어절로부터 추출될 수 있는 모든 음절 2-gram을 적으시오.
한국에서는

한국, 국에, 에서, 서는

---

2. 다음 어절로부터 추출될 수 있는 모든 음절 3-gram을 적으시오.
코로나로부터

코로나, 로나로, 나로부, 로부터

---

다음은 질의 Q와 문서 D를 보인 것이다.
음절 2-gram 색인단위를 사용한다고 가정하고, 아래 물음에 답하시오.
- 유사도 sim(Q,D)는 "질의용어 q의 문서 D에서의 가중치 w(q,D)”(들)의 합으로 계산하시오.
- 예를 들어, Q=[q1,q2]인 경우 sim(Q,D)=w(q1,D)+w(q2,D)로 계산됨.
Q="부산관광"
D="부산시는 외국인 관광객을 위해 부산 홍보에 나섰다"

3- A. 질의 용어의 문서 내 가중치 계산 시 TF만 사용한다고 가정하고, 질의문서유사도 sim(Q,D)의 수식을 적으시오.

Q의 2-gram색인 = ( 부산, 산관, 관광 )
sim(Q,D) = w(부산,D) + w(산관,D) + w(관광,D)
여기에서 가중치(Weight) 계산 시 tf만 사용하라고 조건을 주었으므로
sim(Q,D) = tf(부산,D) + w(산관,D) + w(관광,D) = 2 + 0 + 1 = 3

---

3- B. 질의 용어의 문서 내 가중치 계산 시 TF와 문서길이만 사용한다고 가정하고, 질의문서유사도 sim(Q,D)의 수식을 적으시오. 문서길이는 문서 내 색인용어(들)의 총 개수로 계산하시오.

3-A 와 동일한데, 가중치 계산 시 TF + 문서길이를 사용하라고 했으므로

---

4. 음절 3-gram 색인단위를 사용한다고 가정하고 앞 3번 문제를 해결하시오.
A.
B.

A.
sim(Q,D) = w(부산관,D)+w(산관광,D)
sim(Q,D) = tf(부산관,D)+tf(산관광,D)
= 0+0=0


B.
sim(Q,D) = 0/len(D) + 0/len(D)
sim(Q,D) = 0/9 + 0/9
= 0

그렇다, 이 예제에서도 알 수 있듯이 한글에서 3-gram 색인은 매우 성능이 좋지않다.

---

 

5. 다음은 질의 Q와 전체문서집합 C={D0,D1,D2,D3}을 보인 것이며 각 문서는 색인용어들의 나열이 라고 가정할 때 아래 물음에 답하시오.
Q=[부산,송정,서핑,예약]
D0=[부산],   D1=[부산,송정,서핑],   D2=[부산,서핑,서핑],   D3=[대구]

5-A. 위 전체문서집합의 색인이 완료되었다고 가정할 때, 각 용어의 문서 포스팅을 표시하시오.

이 문제의 정답을 구하는 과정 == 역파일색인을 구하는 과정
부산: [D0, D1, D2]
송정: [D1]
서핑: [D1, D2]
대구: [D3]

---

5-B. 질의문서유사도 sim(Q,D)는 "질의용어 q의 문서 D에서의 가중치 w(q,D)"(들)의 합으로 계산되며 w(q,D) 계산 시 TF만 사용한다 질의 Q와 각 문서의 유사도 수식을 적으시오.
- 예를 들어, Q=[q1,q2]인 경우 sim(Q,D)=w(q1,D)+w(q2,D)로 계산됨.

각 문서의 가중치 점수(유사도)를 매겨보자.
단, 가중치 점수는 TF만 사용한다고 조건이 있다.
w(부산,D0) => TF(부산,D0) => 'D0'에서 '부산'이라는 Term이 나온 횟수

sim(Q, D0)= w(부산,D0)+w(송정,D0)+w(서핑,D0)+w(예약,D0)
sim(Q, D0)= 1+0+0+0 = 1
이런식으로 Q에 대한 각각 문서의 가중치 점수를 다 구하면 된다.
sim(Q, D1)=1+1+1+0 = 3
sim(Q, D2)=1+0+2+0 = 3
sim(Q, D3)=0+0+0+0 = 0

즉, 여기서는 Q[부산,송정,서핑,예약]을 검색하면 D1과 D2가 제일 적합한 문서라고 판단된다.

---