[Information Retrieval] Term voc and posting - Skip Pointers, Phrase queries, Proximity search

1. Documents

기본적으로 정보검색은 document의 단어를 대상으로 한다.

document의 포맷은 pdf, word, excel 등이 될 수 있고 그 안의 character set 또한 다양하다. utf 등등..

한글 이메일에 일본 문서가 실리는 경우 이메일 본문, 첨부된 문서를 각각 document로 볼건지, 전체를 document로 볼건지 또한 고민해야 한다. 정보검색의 설계에 달려있는 문제이다.

정보검색은 다양한 문서에서 어떻게 문서를 파싱 해서 text를 정확하게 찾아내서 검색을 하느냐에 대한 얘기이다.

---

2. Terms - General + Non-English

Word

• text 내에 나타나는 delimiter(빈 칸, 탭 등)로 분리된 하나의 연속된 단위의 character

Term

• normalized word, word는 대소문자, 복수형 등이 존재하여 구분되는데 term은 대소문자, 복수형 등이 구분되지 않음.

Token

• instance of term, Document 내에서 실제 나타나는 term
• 한 document에 boy가 두 번 나오면 두 개의 boy는 같은 term, 다른 token이다.

Type

• Term과 같은 의미로 사용된다.

Normalization

• Word→ Term 과정에서 사용된다.
• 복수형을 떼거나 대소문자를 통일시키는 등 같은 form으로 통일시키는 것이다.
  • ex) word → Word, word, Words, words
  • ex) U.S.A → USA 이 경우에는 .을 제거하게 되는데. 이 소수점의 점인지 약어의 점인지 문장의 끝을 나타내는 점인지 구분할 필요가 생긴다.
• 조금 다른 방식의 Alternatively 정규화도 있다.
  • windows → Windows, windows Windows (no expansion) 창문들이라는 의미의 windows와 제품 Windows의 폼이 같다. 따라서 Windows가 쿼리로 들어오면 normalization 없이 Windows만 검색해야 한다.
  • 위와 같은 방식은 좀 더 정확하게 검색할 수 있지만 효과적이진 않다.
  • 고민은 Windows와 windows를 같은 클래스에 넣어도 되느냐이다.
• 다른 언어의 경우에도 문제가 생긴다. PETER WILL NICHT MIT.라는 독일어에서의 MIT는 소문자 mit로 바꿔도 된다. 하지만 He got his PhD form MIT. 에서의 MIT는 특별한 약어이므로 소문자 mit로 바꿔서는 안 된다. 따라서 같은 알파벳을 사용하더라도 언어를 구분해야 한다.

Tokenization

• Normalization된 단어를 토큰화하는 과정이다.
• IN June, the dog likes to chase the cat in the barn. token은 12개, word type은 9개가 된다.
• 토큰화 과정에서 굉장히 문제가 될 수 있는 사항들이 많다. 하나씩 살펴보자.
  • Mr.O'Neill thinks that the boy'stories about Chile's capital aren't amusing. 이 예시는 모든. 을 잘라야 하는지, ‘를 잘라야 하는지 문제가 생긴다.
    • 이런 문제가 몇 개 더 생기는데, Hewlett-Packard는 자르게 되면 원래 기업이라는 의미를 잃는다. State-of-the-art는 현재 최고 기술을 의미하는데 대시 단위로 자르면 그 의미가 다 사라진다.
  • data base, San Francisco 또한 띄어쓰기로 자르면 전혀 다른 의미가 된다.
  • 3/20/91 은 91년3월20일의 의미인데 어떤 나라에서는 20/3/91 이렇게도 쓴다. Mar 20, 1991 이렇게도 쓰고 91.3.20. 이렇게도 쓴다. 이게 다 똑같은 날짜인지 판단하기는 쉽지 않다.
  • 100.2.86.144, (800) 234-3333 같은 IP 주소나 전화번호도 잘라버리면 전혀 다른 토큰이 된다.
  • 중국어는 whitespace가 존재하지도 않는다. 단어를 자르는 것을 segmentation이라 하는데, 이 segmentation을 잘못하면 전혀 다른 단어가 된다. 중국어만 그런 것도 아니고, 독일어 등에서도 no whitespace인 굉장히 긴 복합어도 많다.
  • 일본어는 히라가나, 가타가나, 영어 등 여러 종류의 문자가 사용된다는 문제도 있다.
  • 아랍어는 한 글자가 여러 토큰으로 분리되는 경우도 있고 읽는 방향이 아라비아 숫자는 왼쪽에서 시작, 글자는 오른쪽에서 시작하는 경우도 있다.
  • 요지는 형태소, whiltespace, dash 등의 문제 때문에 단어를 뽑아내는데 많은 문제가 있다는 것이다.

---

3. Terms - English

토큰화를 할 때 영어에만 집중해보면 대문자를 소문자로 바꾸는 편이 유리하다. 대문자가 특별한 의미를 갖는 MIT 같은 예시가 있긴 하지만 그 비율이 적기 때문이다.

검색에 쓸모가 없는 Stop words(불용어)도 존재한다. a, an, and, are 등이다. 정보검색에 사용되지 않는 단어를 빼버리면 문서의 matrix size가 확 줄어든다.

그렇다고 해서Stop words를 다 빼면 성능이 떨어지기도 하는데 King of Denmark와 같은 예시가 그렇다.

Soundex

• 사람이름 같은 발음이 같은 단어도 문제가 생긴다. Muller, Mueller이 같은 사람을 지칭한다는 것을 알아야 한다.

Thesauri

• 의미적으로 동일한 car, automobile이 다른 Term으로 인식된다.

Lemmatization

• 형태소 분석과 유사하다. 고왔다의 원형인 곱다를 검색하는 것이다.
• 변형/활용된 형태의 단어를 기본형으로 바꿔서 사전형으로 검색하는 것이다.
• am, are → be / car, cars, car’s → car

Stemming

• lemma를 하려다 보니까 규칙이 없어서 까다롭다는 문제가 있다. am, are, is → be는 하나하나 매칭해야 하고 cutting는 ting를 떼야한다. 정보검색은 빠른 시스템이어야 하는데 lemma 처리에 시간이 너무 오래 걸린다는 문제가 있다. 백만, 천만 문서의 토큰을 처리하는데 시간이 오래 걸리는 것은 심각한 문제이다.
• 이 문제를 해결하기 위해 나온게 Stemming이다.
• Stemming은 Crude heuristic process이다. 거칠게 휴리스틱 한 처리인데, 언어적 처리 없이 기본형태에 가깝게 단어의 끝을 잘라내는 것이다.
• Stemming은 언어에 따라 달라질 수 있다.
• automate, automatic, automation을 언어적 처리를 하면 automate가 되지만 stamming 해보면 automat이 된다.

Porter algorithm

• stemming english에 사용되는 알고리즘이다.
• 포터알고리즘은 몇 가지 룰이 있다. SSES → SS, IES → I, SS → SS, S → Φ

Stemming은 Term의 수가 줄어들고 스태밍 시간이 적게 걸린다는 장점이 있다.

Stemming을 하게되면하게 되면 어떤 질의에 대해서는 검색 효과가 잘 올라가는데 어떤 검색은 떨어지는 경우도 있다. 예를 들어 sweater, sweaters 같은 단어는 잘 처리하지만 operational AND research는 하나의 고유명사로 특수한 의미를 뜻한다. 하지만 Stemming을 하게 되면 의미가 깨져서 검색 효과가 떨어지게 된다.

---

4. Skip Pointers

intersection을 생각해보면 Linear 시간에 끝난다. postings list의 길이만큼 스캔하면 끝나는 것인데, 이게 만만치 않다. O(1)에 가깝게 하려면 Skip Pointers를 사용할 수 있다.

 

기본적인 아이디어는 intersection에서 한 칸씩 증가시키는 게 아니라 몇 칸씩 건너뛰는 것이다.

BRUTUS에서 2를 시작으로 skip pointer를 거치면 34가 나오고 또 거치면 128이 나오고 그렇다. 일정하게 몇 칸씩 뛰는 것이다.

둘 다 하나씩 skip 해서 34, 8인 경우를 생각해보자. 일반적으로는 작은 쪽을 증가시켜야 하는데, skip pointer에서는 8의 skip pointer인 31을 본다. 31이 34보다 여전히 작으므로 skip pointer를 타고 31까지 건너뛴다.

그럼 34, 31이 된다.

직접 해보자. 알고리즘도 직접 짜봐야 한다.

스킵 포인터 간격이 짧으면 스킵을 많이 이용할 수 있어서 좋긴 하지만 스킵 포인터를 유지하는 메모리가 많이 든다. 간격이 길다면 스킵을 많이 못쓰겠지만 필요한 메모리는 그만큼 적다.

스킵 포인터 길이는 보통 postings list 길이 P에 대해 $\sqrt p$를 많이 쓴다.

---

5. Phrase queries

[stanford university]를 하나의 phrase로 검색하려면 어떻게 해야 할까? stanford에 대해 검색을 하고, university에 대해 검색을 해서 intersection을 하면 된다.

그러나 결과가 그렇게 만족스럽진 않다. The inventor Stanford Ovshinsky never went to university 이러한 문장 또한 검색 결과에 포함될 수 있기 때문이다.

위와 같은 경우를 잘못된 정답, false positive라 한다.

Phrase queries 문제를 해결하기 위한 방법을 하나씩 알아보자.

먼저 가장 간단한 방법으로 phrase 자체를 term으로 설정하는 방법도 있다. 하지만 phrase를 만들 수 있는 경우의 수가 너무 많아서 term의 list가 너무 많아지게 된다. 따라서 inverted index를 확장한 두 가지 방법을 주로 사용한다.

• biword index : 연속해서 나온 두 단어를 한 단어로 취급한다.
• positional index : 단어의 위치를 같이 기록해서 위치가 바로 옆에 나온 것인지 판단하여 phrase인지 아닌지 판단한다.

Biword indexes

phrase를 하나의 term으로 하는 bioword를 생성하여 vocabulary term에 달아 두는 방법이다.

• 예를 들어 Friends, Romans, Countrymen이라는 문장에 대해 두 가지 bioword를 생성할 수 있다. friends romans, romans countrymen이 되고 이 두 bioword를 term으로 사용한다.

이 방식의 문제는 phrase가 두 단어가 아닌, 긴 phrase인 경우에 문제가 생길 수 있다.

• stanford university palo alto라는 phrase에 대해서 biword 방식으로 해결하려면 stanford university, university palo, palo alto 이렇게 두 biword를 만들어서 intersection으로 해결할 수 있지만 이전과 똑같이 false positive 문제가 생길 수 있다.

term vocabulary가 굉장히 길어지고 긴 phrase에 대해 잘못된 결과가 많이 나온다는 문제가 있다.

Positional indexes

biword 보단 좀 더 efficient 하다. 기존의 posting list를 생각해보면, position이 없는 nonpositional index였다. 단어의 위치를 포함하지 않는다는 뜻이다.

positional index는 문서 내에서의 단어의 위치를 포함하는 posting list이다. 한 문서 내에 같은 단어가 여러 번 나올 수 있으므로 list 형태로 position이 달리게 된다.

• 예를 들어 to be or not to be phrase 를 검색해 보자.

1. 쿼리의 각 토큰에 번호를 매긴다.

 

2. 각 term이 몇 개의 문서에서 등장하는지 적어준다.

 

3. 각 문서에서 term이 등장하는 위치를 적어준다.

1 : <7, 18, 33, …>; 에서 1은 문서 번호, 뒤의 list는 position index이다.

 

4. 전체 결과를 보고 phrase가 맞는지 판단한다.

phrase를 판단하는 과정을 잘 보자!

4번 document에서 to가 16, be가 17 index에 존재하고, 쿼리를 보면 첫 번째 to와 4칸 떨어진 곳에 또 to be가 존재한다. 그런데 16 index에서 등장한 to 다음 to는 너무 멀어서 match 되지 않고 429 번째 index에서 등장한 to가 match 될 가능성이 높다.

Proximity search

• positional index을 사용해서 근사치 검색에 사용할 수 있다.
• 예를 들어 employment /4 place 가 쿼리라면, employment와 place 사이에 최대 3개의 단어가 존재하도록 검색하는 것이다.
• 자주 나오는 단어, 특히 stop words(불용어)가 포함되는 우 position 정보를 사용하게 되면 굉장히 비효율적이다.

코드를 보고 잘 짜보자!

k가 거리가 된다. p1, p2는 docID, pp1, pp2는 document 내부에서 word index가 된다.

Combination scheme

Biword와 Positional을 조합하여 검색 성능을 향상할 수 있다. 자주 나타나는 biword를 index에 추가하고 자주 나타나지 않는 phrase는 positional을 사용하는 방법이다. 이 방법은 더 많은 공간을 차지하지만 속도는 positional만 사용하는 것보다 빠르다.