[Information Retrieval] 정보 검색 2. The term vocabulary and postings lists

1. Term 

* Tokenization

“Friends, Romans and Countrymen” 라는 input이 들어오면

토큰화된 결과인 토큰들이 아웃풋으로 나온다

friends, romans, countrymen 

 

normalization 정규화 

= 각 토큰은 index entry의 후보가 되고 데이터 검색할 때 중요한 term으로 저장되는 것들을 의미함

소문자로 변환하거나 특정 문자를 제거하는 등 표준화

 

토큰화 과정에서 의미 없는 단어를 제거하기 위해

불용어 리스트를 사용함

 

* Tokenization - 문서 단위

- 인덱싱에 사용되는 단위 문서를 정의함

- indexing granularity = 인덱싱의 세분화 

- 책 전체를 하나의 문서로 간주할지, 각 챕터를 개별 문서로 간주할지 결정

문서가 커질수록 재현율 recall의 증가 (포함은 높지만 정확도는 떨어지는 트레이드 오프)

vs 문서가 작아질수록 precision 정밀도 증가

 

= recall 재현율 = 검색 결과가 얼마나 많은 관련 문서를 포함하고 있는가 

= precision 정밀도 = 검색 결과가 얼마나 정확한가

 

* Tokenization - 식별할 요소

- 문서의 형식

- 문서의 언어

- 문자 집합

> 머신러닝을 통해서 분류할 수도 있지만 휴리스틱한 방법으로 해결하는 것이 보통

(경험에 기반한 직관적이고 간단한 규칙)

 

 

* Tokenization - 언어 식별

- 짧은 문자 서열을 사용해서 언어 식별 가능

나는 학생이다 sksms gkrtoddlek 둘 중에 의미 있는 것으로

- 문자 집합 식별도 비슷한 방식, 사용하는 인코딩에 따라 다르게 취급

 

* Tokenization - 문서 형식 식별

파일 형식을 판단할 수 있는 고유한 매직 넘버가 있음

 

* Tokenization - 토큰화의 복잡도 문제

- 토큰화할 때 공백으로 나누고 문장부호를 버리면 해결될 것 같지만 그 때문에 발생하는 문제도 있었음

예시 Mr. O'Neill의 O'Neill

 

 

* Tokenization - 토큰화의 하이픈 취급 문제

Hewlett-Packard 처럼 하이픈이 있을 때 하나의 토큰으로 취급할지, 두 개로 분리해야 할지

 

 

* Tokenization - 토큰화의 특정 토큰 처리 문제

특정 패턴을 갖는 토큰을 어떻게 처리할지에 대한 문제는 잘못 처리하면 유용한 정보를 잃을 수 있음

03/02/02 같은 날짜나 전화번호, 이메일 등

 

* Tokenization - 토큰화의 언어별 특수 토큰 처리 문제

띄어쓰기 없는 중국어나 일본어는 문맥에 따라 달라질 수 있고

로마자 히라가나 가타카나 한자를 다 사용하는 일본어는 어떤 것으로 검색해도 나와야 함

 

* Tokenization - 불용어 

- stop words 불용어

의미가 적은 단어인 a, the, and 같은 것은 검색에서 제외

포스팅 수를 줄여서 검색 속도를 개선

 

- 불용어의 변화

최근 불용어 리스트 줄어들고 있음 ... 검색 엔진이 불용어 처리 방식을 더 정교하게 변화시킴

 

 

* Normalization 

동일성을 맞추기 위해 필요한 정규화 

- index에 저장된 용어와 사용자가 입력하는 검색어 모두 형식을 동일하도록 정규화

- USA, U.S.A 등의 다양한 표기방식이 하나의 의미일 때 매칭시켜서 정보 검색의 정확도를 높임

 

* Normalization - howto

- mapping rules : 점과 하이픈을 제거하는 것처럼 다양한 규칙을 적용해서 통일된 형태로 변환

- thesaurus : 동의어, 상위어, 하위어 관계를 처리하기 위해 동의어 사전을 이용. car라면 automobile, transportation 처럼 !!

- 동의어 사전은 사람이 직접 생성하기도, 자동으로 생성하기도

* Normalization - usage

- 정규화 없이 인덱싱하면 모든 유사 용어가 전부 개별 인덱스화

- 동의어 유의어 상/하위어에 대한 인덱스를 모두 확인해야하니 효율성이 떨어짐

 

 

- 정규화 적용을 통해 equivalence class를 생성하면 관련어를 하나의 인덱스로 검색될 수 있게 함

- 각기 다른 표현으로 검색해도 통합된 결과를 얻을 수 있다는 장점

 

equivalence class를 사용한다는 점은 동일하지만 세 가지는 활용하는 방법이 조금씩 다르다

 

1) equivalence class name 을 통한 인덱싱

- 유의어를 하나의 클래스로 묶고 대표 이름을 부여함

automobile, suv, car >> car

- 통합된 인덱스에서 관리하여 대표 이름으로만 검색해도 나머지가 포함된 문서를 검색할 수 있음

- 대표 이름이 아닌 나머지로는 검색이 어려울 수 있음

 

2) multiple indexing with equivalences

- 유의어 개별적으로 독립 인덱스를 가짐 + 동일한 문서 그룹에 연결 

- automobile, suv, car 각각 5, 23, 48과 연결되어 있어서 어떤 단어로 검색해도 동일한 결과

- 원하는 결과를 얻을 가능성이 높아지고 단어별로 인덱싱되었으니 모든 단어로 검색 가능

- 인덱스 크기가 커지고 중복된 인덱싱 발생 가능성

 

3) query expansion with equivalence

 

- 특정 검색어를 입력했을 때 대응하는 equivalence class의 모든 단어로 자동 확장해서 검색

- automobile >> automobile, car, suv

- 단일 검색어만으로 검색 범위 확장되니 포괄성 높아짐

- 검색 과정에서 쿼리 확장을 위해 필요한 추가 처리가 성능에 영향

 

 

* Normalization - language specific > 언어별 특수 문제

- 언어별 문제 : 독일어에서 Tuebingen과 Tübingen, résumé와 resume는 각각 동일한 의미

- 정규화 필요성 : 검색어 입력시 사용자가 악센트 넣지 않을 가능성 有

 

* Normalization - language specific > case folding

- case folding 모든 문자를 소문자로 변환해서 동일하게 처리

- 정규화가 의도하지 않은 문제는 C.A.T를 cat와 같게 처리하는 문제가 발생할 수도 있음

... 첫 글자를 제외하고 소문자로 변환하는 것을 해결책으로

 

* Normalization - language specific >  idiosyncratic formats

- 나라마다 다른 날짜 형식 ... 통일해서 처리

- 일본어의 표기방식 다양성 

 

* Stemming

- 어미 자르기 = 단어의 어간(의미를 가지는 기본형태)만 남기기

automates, automatic, automation > automat

- equivalence class 로 처리 : 정확한 형태가 아니더라도 같은 의미를 갖는 단어를 동일한 그룹에

 

* Stemming - porter's algorithm

- 영어에서 stemming을 수행하기 위해 porter's algorithm 을 가장 많이 사용

= 정해진 규칙에 의거해 단어의 어간을 찾는 것

- 조건을 포함한 규칙 적용

= 특정 길이 조건이 충족될 때 어미를 제거하거나 맥락에 따라 다르게 변환

 

* Lemmatization 

- 단어 변형 형태를 사전적인 기본형(lemma)으로 변환하는 것 

am are is > be 

- 형태소 분석기로 문법적으로 정확하게 변환

* Stemming과 Lemmatization 비교

- stemming 어미 자르는 간단한 방법. 정확도 낮지만 재현율 높음. 여러 단어 포괄해서 결과 더 많아짐.

operational AND system > operate AND system

- lemmatization 정확하게 변환하지만 장점이 크지 않음. 유사한 편.

operational AND system > operate AND system , operating AND system ...

 

* Multilingual documents Dictionary entries

  문서 내부의 언어를 감지하고 normalization, stemming, lemmatization을 수행하며 언어별 태그 표시를 추가 인덱싱함

 

2. Faster postings merges : Skip pointers/Skip lists

* 포스팅 리스트 기본 병합

- 두 개의 포스팅 리스트를 동시에 순회하며 병합하는 방식

- 처음부터 끝까지 비교하며 조건에 만족하는 것을 결과 리스트에 추가하는 것

- 두 리스트를 모두 순회해야하니 O(m+n)의 리스트 길이에 비례하는 선형적 시간복잡도를 가짐

* 포스팅 리스트 병합 - 스킵 포인터

1) Augment postings with skip pointers (at indexing time)

- 리스트 내 특정 위치를 건너 뛰고 다음에 있는 중요한 항목으로 바로 이동할 수 있게 함

- 불필요한 항목을 생략하니 검색 효율이 증가함

.. 특히 and 에서는 공통항목을 찾는 것이므로 불필요한 것은 건너뛰고 다음 항목을 확인하기 좋음

- OR 쿼리에서는 모든 항목을 확인해야해서 스킵 포인터의 효과가 제한적임

 

8까지 처리를 완료하고 이제 11과 41을 비교하려고할 때 

11의 스킵포인터를 사용하면 바로 다음 31로 이동가능하다

어차피 41보다 11이 작아서 31까지의 항목은 건너뛰어도 된다 오히려 좋아

 

대규모 구조에서 불필요한 항목을 건너뛸 수 있어서 성능이 좋다는 장점 有

2) Then, where do we plce skips?

짧은 간격의 많은 포인터, 스킵 가능성 높으니 속도 빠를 수 있지만, 건너뛸 기회가 많을수록 각 포인터마다 비교연산 추가

 

긴 간격의 적은 포인터. 스킵 가능성 낮으니 비교연산은 적지만 속도 느리고, 건너뛸 기회가 많지 않으니까 사용 적음

 

3. Phrase queries and positional indexes

- 여러 단어를 하나의 구문으로 인식해서 정확히 일치하는 단어만 반환해야하는 경우가 있음

스탠포드에 있는 대학과 스탠포드 대학교는 다르기 때문

- 기존의 (term:docs) 로만 인덱스를 저장하던 것은 정보가 불충분. 위치정보가 필요함

 

* solution 1. biword indexes

- 연속된 두 단어씩 묶어서 인덱스 생성

- 두 단어로 구성된 구문 검색에서 biword 인덱스로 빠르게 찾을 수 있음

 

extended biwords

- biword보다 더 긴 구문을 처리하고 싶을 때 품사 태깅 후 특정 패턴을 가지는 구문을 biword로 확장

 

예시로 확인해보자면

renegotiation of the constitution 라는 문장에서 

renegotiation of 혹은 of the 처럼 두 단어로만 묶으면 정확하게 검색할 수 없음

그래서 renegotiation of the constitution 의 품사를 확인해보았을 때 

N 명사 X 불용어 X 불용어 N 명사 순서이므로

불용어는 임의의 단어로 처리하고 첫 번째와 두 번째 명사를 하나로 묶는다 

( renegotiation ... constitution ) 형태로 구문을 만들고 이 구문이 포함된 문서를 검색함

 

품사 태거를 실행하면

이렇게 고유명사는 NNP 과거형 동사는 VBD 등으로 출력됨

 

longer phrase queries

- 긴 구문을 boolean 쿼리로 바꿔서 AND로 연결해서 검색

- 대신 false positive의 가능성이 있음 = 실제 구문이 포함되지 않은 문서도 검색될 가능성 有

 

issues for biword indexes

- biword index는 인덱스가 커지면 모든 단어를 두 개씩 조합하니까 저장공간 급증 = index blow up 발생

- false positive 발생할 가능성도 있음 = 두 단어 조합만 인식해서 실제로 구문이 없는데 결과가 잘못 나올 수 있음

- 더 긴 구문 처리를 위해 phrase index를 사용하면 되지만 인덱스 크기 문제가 심각해짐 = 전체 구문을 인덱스에 저장해야하는데 그런 구문이 많아지면.....

- phrase index의 대안으로 positional index를 사용하는 것이 일반적  = 단어의 위치 정보만 저장해서 공간을 절약하고 긴 구문을 찾기 더 쉽도록 함

 

* solution 2. positional indexes

각 단어의 위치정보를 포함하는 형태의 인덱스

2번 문서의 1, 5, 12, 15 .... 에 위치하고 이는 brutus

 

processing a query

Stanford University를 검색하면 Stanford와 University가 한 문서 안에서 인접해있는지 확인

 

processing phrase queries

To be or not to be 가 문서에 있는지 확인하려면 위치 정보로 순서대로 연결된 위치가 있는지 확인해야함

 

processing proximity queries

LIMIT! /3 STATUTE /3 FEDERAL /2 TORT 처럼 찾는 단어가 특정 거리 내에 있는지 확인

positional index는 위치 정보를 가지고 있으니 proximity queries가 가능하지만 biword index는 할 수 없음

 

positional index > size issue

문서 내에서 각 단어의 위치를 모두 저장해야하니 역시 인덱스 크기가 커짐

단어 수가 많은 문서면 더 커지고 성능에 악영향

 

positional index > size issue > rules of thumb

위치 기반 인덱스의 가이드라인이 있음

위치 정보를 지원하지 않는 인덱스보다 2~4배 크기가 큼 (단어마다 여러 개의 위치 정보를 포함해야해서)

추가 공간이 필요하더라도 검색 효율을 높이기 때문에 사용

 

positional index > size issue > combination schemes

자주 검색되는 구문은 positional index 만으로 처리하기 비효율적임

자주 검색되는 구문은 biword index나 phrase index로 효율적 처리 필요