[정보검색] 3. Dictionaries and tolerant retrieval

 

2. Dictionaries

dictionary는 term vocabulary를 저장하는 자료 구조

(term voca. = data, dictionary = data structure)

 

대표적인 자료구조 클래스-hash와 tree(정보검색도 둘다 사용.)

 

Hashes

• 각 vocabulary term은 배열의 행번호인 정수로 해싱됨.
• 쿼리 시간: 고정길이 array에 위치
• 장점: 빠르다.(상수 시간)
• 단점: 마이너한 용어 찾기 어려움/prefix 찾을 수 없음/voca.가 커지면 모든걸 rehash

 

Trees

• prefix 문제 해결
• 가장 간단한 트리는 이진 트리
• O(log M)이라 느리긴 함(M이 voca.의 크기)
• 그러나 최적상태는 B-tree(Balanced tree)로만 가능.
• Rebalancing 문제도 완화 가능.
• 정의는 알아서 찾아.

 

3. Wildcard queries.

Q. 이게 뭔데요?

A. *.zip으로 zip파일 전부 찾거나 하는거 있잖어. '*' 이런거.

 

Q1. mon*이라는 쿼리에 대해

A1. 트리에서 mon<=t<moo를 만족하는 t를 찾으면 됨.

 

근데 반대로라면?

Q2. *mon을 찾으려면?

A2. 반대로 찾자(nom*를 찾기)-단, 그 거꾸로 된 애들도 다 dictionary에 넣어줘야 함.(=크기 2배)

 

그렇다면 중간은 어떨까?

Q3. m*nchen을 찾으려면?

A3. m*와 *nchen을 각각 해서 intersect한다.

당연히 오래 걸림.(찾고+찾고+합치고)

 

그래서 <Permuterm index>를 이용

(핵심 아이디어) 쿼리를 돌려서 *가 마지막에 나오게 한다.

단어는 저장할 때에 마지막에 $기호를 넣는다.=>글자수+1만큼의 단어가 저장됨.

(보통 4~5배가 저장된다고.)

 

여튼 hello라는 단어는

hello$, ello$h, llo$he, lo$hel, o$hell, $hello

위와 같이 저장된다.

 

쿼리 예시

X: X$를 검색

X*: $X*를 검색

*X: X$*를 검색

*X*: X*를 검색

X*Y: Y$X*를 검색

 

+permuterm index를 permuterm tree라고도 부름.

 

k-gram index

• permuterm index보다 좀더 공간효율적
• 용어에서 발생하는 모든 문자 k-gram들을 열거.
• 2-gram은 bigram이라 부름.
• $는 경계를 나타내는 심볼.
• inverted index의 두가지 다른 유형.
• k-gram은 k-gram들로 이루어진 쿼리에 기반하여 term을 찾는다.

bigram에서 wildcard를 하려면?

Q. mon*

• $m AND mo AND on을 검색하면 된다.
• 그러나 false positive 발생(moon은?)
• 이런건 postfilter가 필요.

k-gram과 permuterm index를 비교하면

k-gram은 공간, permuterm은 시간 면에서 장점을 가진다.

 

 

4. Edit distance

tolerant한 검색을 위해

글자간 차이(distance)를 계산하는 것.

주요 연산은 Insert/Delete/Replace. (여기에 Damerau-Levenshtein방법은 swap-transpostion까지 들어가기도)

즉 '몇번 바꿔서 해당 단어가 되는지'

 

이런 표를 채우는데, 칸 4개가

왼쪽 위(대각선)에서 copy/replace를 하는 경우 (0 또는 1)	위쪽에서 delete(+1)
왼쪽에서 insert(+1)	다른 3개 칸의 값들 중 최소 값

다음과 같은 규칙으로 채워진다.

 

그리고 마지막까지 완성하고, 수가 늘어난 규칙이 무엇인지 찾아내면 끝.

 

 

6. Soundex

음성적인(phonetic) 대안을 찾는 것에 기반

알고리즘

• 4-character reduced form으로 모든 token을 인덱싱
• query terms와 동일
• reduced form에서 build&인덱스 탐색

Not very..useful (in I.R.), "high recall" task에서는 Ok.