Boolean Retrieval

정보검색 : 많은 문서 집합에서 원하는 정보를 얻기 위해 비구조화된 문서들에서 필요한 자료를 찾는 것

1996년) TEXT와 같이 비구조화된 문서의 규모가 구조화된 문서보다 컸음. 근데 시장에서는 비구조화된 문서를 다루는 건 돈이 되지 않았음

2006년) 여전히 비구조화된 문서의 규모가 크지만 TEXT 검색 서비스 시장이 커지면서 비구조화 문서를 다루는 시장이 성장함

정보검색시스템이 없다면, 유닉스의 grep명령어, | 로 찾을 수 있음. 하지만, 문서의 양이 크다면 속도가 느리기 때문에 정보 검색 목적으로는 적절하지 않다. 특정 내용이 들어가 있는 건 들어가 있으면 더 탐색할 필요가 없으니 쉬운 편이지만, 특정 내용이 들어가 있지 않은 건 파일을 끝까지 다 탐색해 봐야 하기 때문에 어렵다. 단어가 인접해 있는지 여부는 grep 명령으로 찾을 순 없다.

Boolean 모델은 단어 포함 여부만 알 수 있기 때문에 검색 결과로 추출된 문서들의 순위를 매기긴 힘들다. grep 또한, Boolean 모델에 따르기 때문에 순위를 매기긴 힘들다.

Boolean 모델도 점수를 매겨서 Sort할 수 있긴 하지만, 기본적으론 순위 매길 수 없다.

$ grep -v <질의어> * : 모든 문서 파일(*)에서 질의어가 포함되지 않은(-v) 문서를 탐색한다.

Term-document (incidence) matrix

Term과 Document의 관계를 나타내는 행렬

검색 대상이 되는 모든 문서에 대해, Term이 Document에 나오면 1, 나오지 않으면 0

질의어와 일치하는 Term의 행들을 찾아서 주어진 질의어에 따라 행끼리 AND, OR, NOT 연산 수행

이때, NOT은 1과 0을 맞바꿈.

bitwise : 같은 위치의 bit끼리 연산

예) 질의어 : Brutus AND Caesar but NOT Calpurnia

Brutus = 110100, Caesar = 110111, Calpurnia = 010000

연산 : 110100 AND 110111 AND 101111 = 100100

→ 1, 4번째 문서가 검색 결과에 포함되고 나머지는 포함되지 않음.

Term-document (incidence) matrix가 주어져 있다면, 질의어 키워드에 해당하는 Term의 행을 찾아서 연산을 통해 검색 결과를 도출해낼 수 있음. (Boolean 검사 기본 방법론)

Boolean Model 기본 가정 : 문서의 집합은 고정되어 있음.

말뭉치 : Corpus, 문서의 집합

Refine : 사람이나 검색 시스템이 질의어를 더 정교하게 수정해서 재검색을 하는 행위

검색도 시스템 평가 기준

Precision 정밀도 : 결과가 질의어와 얼마나 부합하는지

모델이 True라고 분류한 것 중에서 실제 True인 것의 비율(=정답률)

실제로 사용자가 찾고자 하는 내용이 담긴 문서 / 모델 검색 결과

정답 / 내가

Recall 재현율 : 질의어에 부합하는 문서를 얼마나 찾아내는지

실제 True인 것 중에서 모델이 True라고 예측한 것의 비율(=제공률)

정답 / 실제

정확도(Accuracy)는 정보 검색 평가에 쓰이지 않음

정밀도가 높으면 재현율이 낮고, 정밀도가 낮으면 재현율이 높음.

정밀도가 100인 경우 : 찾고자 하는 내용이 담긴 문서 100개에서 1개 찾음. → 재현율은 0.01

재현율이 100인 경우 : 찾은 문서 100개 중 찾고자 하는 내용이 담긴 모든 문서가 1개임 → 정밀도는 0.01

F-measure : 정밀도와 재현율에 가중치를 주고 구한 평균

→ 흔히 알파(가중치)를 0.5로 주어 아래와 같이 만듦

F-measure로 검색 시스템 성능 평가에 사용함.

예시)

Q1. 검색 대상 문서 100만 개, 각 문서는 평균적으로 1000개의 단어가 있음. 한 단어는 평균적으로 띄어쓰기, 부호 포함 6bytes(6글자). 문서 전체 크기는?

A1. 문서 전체 크기 = 100만 * (1000 * 6bytes) = 6,000,000,000 = 60억bytes = 6GB

Q2. 10억(100만 * 1000 = 1,000,000,000)개 의 단어 중, 500,000개의 다른 단어가 있다. Term-Document Matrix의 크기는?

A2.

Term 개수 = 50만

Document 개수 = 100만

Term-Document Matrix 크기 = 50만 * 100만 = 5천 억

→ Boolean 검색을 위해 Term-Document Matrix를 미리 만들어야 하는데, 크기가 너무 큼.

5천 억개의 0과 1중 0의 비중이 보통 99.8%를 차지하여 1은 0.2%를 차지하여 1000개로 많지 않음.

따라서, 1인 것만 따로 표시하도록 함. ⇒ Inverted Index (Inverted file)

0이 차지하는 비율

term(행) = 50만개, document(열) = 100만개

하나의 문서의 term 정보 = 한 열(50만개의 term), 하나의 문서는 1000개의 단어로 구성됨 ⇒ 하나의 문서에 term 중 평균적으로 1000개의 단어만 나오므로 50만 개의 한 열에서 1은 평균적으로 1000개임. 49만9천개는 0임. ⇒ 50만 개에서 1000개가 1이었으니 100만개에서는 2000개가 1임. ⇒ 2천/100만 = 0.002. 0.2%가 1이고, 99.8%가 0임.

Inverted index (inverted file)

Term-Document Matrix의 공간 상의 문제 해결을 위해 1인 문서만 목록화함.

검색 대상(문서, 웹, PC경로)에 따라 검색 결과가 다르기 때문에 Posting list에는 논리적으로 문서의 번호 식별자를 부여함.

Posting : 문서 번호 식별자 하나하나

Posting list : Posting이 나열된 하나의 배열(리스트)

Posting lists : Posting list의 집합

질의어를 찾을 때 더 빨리 찾을 수 있도록 문서를 정렬해야 하기 때문에, Posting list는 배열보다 연결 리스트를 선호한다. 하지만 포인터 공간을 더 차지한다.

Dictionary == Vocabulary (Term의 집합)

Inverted Index 만드는 과정

[단계]

1. Tokenization (토큰화)
   1. → 만약, 문서가 TXT가 아닌 아래한글, html이라면? → 경우에 따라 토큰화 어려울 수 있음.
   2. Linguistic Modules를 통해 언어에 따라 처리함. (영어 : 모두 소문자로, 원형으로 만듦)
   3. Indexer : 토큰을 인덱스로 만듦
      • 어느 토큰이 어느 문서에서 나왔는지 Postings list(해당 토큰의 문서 위치를 나타냄) 구축
      • Inverted Index를 만듦.
        1. (Term, DocID) 쌍으로 만듦
        2. Term을 기준으로 정렬함.
        3. 필요 시, TF 정보 추가
           • 한 문서의 중복 Term은 하나로 통일
           • Term Frequency(TF) : 한 문서를 기준으로 Term이 나온 개수 추가
        4. 필요 시, DF 정보 추가
           
           • Document Frequency(DF) : Term이 나온 문서의 개수 추가
           • 이때 Term Frequency끼리 합을 구함
           • DF로 합쳐진 중복 Term은 각각 연결 리스트 식으로 자신의 (DocID, TF)를 가리킴 → 나중에 연결 리스트 형식의 Inverted Index의 기틀이 됨.  

사람이 쓰는 단어는 한계가 있으므로 Dictionary size는 Postings list에 비해 변화가 적음.

따라서, Dictionary는 검색 서비스를 위해 Main Memory로 load 됨.

Postings는 크기가 점점 커지고 변화도 잦아 Disk에 저장됨.

 

Postings list 저장 방법

1. 연결 리스트
2. 가변 배열
3. hybrid scheme : 연결리스트 + 가변 배열 (배열을 연결리스트로 연결함.)

질의어

1. Conjunctive : AND시간복잡도 : 비교하는 Posting List 길이의 합if not sorting 시간복잡도 : 비교하는 Posting List 길이의 곱
2. 조건 : Posting list가 정렬되어 있어야 함.
3. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 다르면 작은 쪽의 Posting이 오른쪽으로 이동하고 다시 비교
4. Disjunctive : OR시간복잡도 : 비교하는 Posting List 길이의 합
5. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 달라도 문서 번호가 더 작은 쪽을 먼저 검색 결과에 포함하고 작은 쪽이 오른쪽으로 이동한다.
6. NOT → 시간 오래 걸림NOT이 붙은 Posting list는 오른쪽으로 넘어가기 전에, 자신에게 없는 Posting의 문서 번호와 다른 Posting list와 연산함.NOT이 붙은 Posting의 문서 번호가 NOT이 붙지 않은 Posting의 문서 번호와 다르면, 추가하지 않고 작은 쪽이 오른쪽으로 이동한다. 같으면 추가하지 않고 두 Posting 모두 오른쪽으로 이동한다.
7. <AND>
8. NOT이 붙은 단어가 검색 결과에 포함되면 안 됨.

WestLaw 시스템

질의어를 만들 때, AND, OR, NOT + /숫자, ! 가능함.

띄어쓰기 : OR

/<숫자> : <숫자> 단어 이내에 두 단어가 나올 때, AND

! : Wild-card 문자 *

/s : 한 문장 안에 두 단어가 둘 다 나와야 함. AND

/p : 한 문단 안에 두 단어가 둘 다 나와야 함. AND

Proximity operators : 인접성을 표시할 수 있는 연산 기호

연산 순서 최적화

1. 앞부터 처리
2. 순서 바꿔서 처리 → 시간 절약 가능OR 시간 복잡도 : Posting list size의 합
   1. Doc Freq가 작은 것부터 처리함.
   2. Posting list size == Doc Freq
   3. 연산 시 시간 복잡도를 최대로 계산해서 시간 복잡도가 작은 순서대로 처리함.
3. AND 시간 복잡도 : Posting list size의 합

인접조건

질의어의 단어가 띄어쓰기 단위로 끊어지면 안 되고 붙어있어야 할 때

Proximity 인접조건 명령어 : NEAR

구조화된 TEXT까지 생각해서 검색해보는 방법도 생각해보기(저자와 내용 구조가 맞는 검색)

Inverted Index + Position Information

Position Information : Posting이 해당 문서가 그 문서 내에서 어디에 나왔는지 위치 정보가 담긴 list를 가리킴

Position Information Size = Term Frequency

두 단어가 인접해 있는지 찾는 법 : AND 연산으로 각 문서에 해당 Term 나왔는지 검사 → 두 위치 정보를 비교함 → 인접 조건에 맞을 경우 결과에 포함

인접 차이 : 1이면 두 단어가 붙어있음을 의미하고, 2면 두 단어 사이에 한 단어가 포함되어 있음을 의미함.

Term Freq 활용

Term Freq가 큰 순으로 결과 제공하기

어떤 Term이 하나의 문서에서 Document에서 몇 번 나왔는지 고려

어떤 Posting의 Term Freq == 그 Posting의 Positional Information 리스트의 길이

검색 결과로, 각 문서의 Term Freq의 합이 큰 문서부터 제공함.

Ranking Search

Boolean 모델은 해당 질의어가 문서에 포함 됐는지 안 됐는지만 판단하기 때문에 Ranking을 매기는 건 원칙적으로는 불가능하다.

하지만, 기준을 적용해서 조금 더 유용할 만한 검색 결과를 제공할 수도 있다. Proximity 인접성을 이용해서 인접할 수록 사용자가 더 원하는 정보에 더 가까울 수 있으므로 가까운 순으로 제공하거나, 문서의 Term Freq를 이용해서 큰 순으로 제공하거나, 문서가 만들어진 시간을 인덱스에 부여해서 최근 문서부터 제공할 수 있긴 하다.

정보 검색 VS DB 검색

정보 검색

비구조화 됨

범위 검색 불가능

단, TEXT이더라고 약간의 구조가 있을 수 있음. Semi-Structured Data 예) PPT, XML

글자의 크기, 글자의 굵기와 같은 정보를 이용해 약간의 구조를 추가할 수 있음.

DB 검색

구조화됨.

범위 검색 가능

관련 있는 Concept 검색 : 아직 불가능

용어

Clustering : 군집(모으기)

Classfication : 분류

웹 검색

다양한 문서, 다양한 사람, 질의어, 정보 존재함.

링크된 정보 활용하거나 클릭한 정보 활용 가능함.

Cross-language information retrieval : 교차 언어, 번역해서 검색 결과 제공

Question answering : 질의 응답 시스템 질문&답변

Summarization : 검색결과 요약해서 제공

TEXT mining : TEXT에서 필요한 정보 뽑아서 알려줌

1996년) TEXT와 같이 비구조화된 문서의 규모가 구조화된 문서보다 컸음. 근데 시장에서는 비구조화된 문서를 다루는 건 돈이 되지 않았음

2006년) 여전히 비구조화된 문서의 규모가 크지만 TEXT 검색 서비스 시장이 커지면서 비구조화 문서를 다루는 시장이 성장함

정보검색시스템이 없다면, 유닉스의 grep명령어, | 로 찾을 수 있음. 하지만, 문서의 양이 크다면 속도가 느리기 때문에 정보 검색 목적으로는 적절하지 않다. 특정 내용이 들어가 있는 건 들어가 있으면 더 탐색할 필요가 없으니 쉬운 편이지만, 특정 내용이 들어가 있지 않은 건 파일을 끝까지 다 탐색해 봐야 하기 때문에 어렵다. 단어가 인접해 있는지 여부는 grep 명령으로 찾을 순 없다.

Boolean 모델은 단어 포함 여부만 알 수 있기 때문에 검색 결과로 추출된 문서들의 순위를 매기긴 힘들다. grep 또한, Boolean 모델에 따르기 때문에 순위를 매기긴 힘들다.

Boolean 모델도 점수를 매겨서 Sort할 수 있긴 하지만, 기본적으론 순위 매길 수 없다.

$ grep -v <질의어> * : 모든 문서 파일(*)에서 질의어가 포함되지 않은(-v) 문서를 탐색한다.

Term-document (incidence) matrix Term과 Document의 관계를 나타내는 행렬

검색 대상이 되는 모든 문서에 대해, Term이 Document에 나오면 1, 나오지 않으면 0

질의어와 일치하는 Term의 행들을 찾아서 주어진 질의어에 따라 행끼리 AND, OR, NOT 연산 수행

이때, NOT은 1과 0을 맞바꿈.

bitwise : 같은 위치의 bit끼리 연산

예) 질의어 : Brutus AND Caesar but NOT Calpurnia

Brutus = 110100, Caesar = 110111, Calpurnia = 010000

연산 : 110100 AND 110111 AND 101111 = 100100

→ 1, 4번째 문서가 검색 결과에 포함되고 나머지는 포함되지 않음.

Term-document (incidence) matrix가 주어져 있다면, 질의어 키워드에 해당하는 Term의 행을 찾아서 연산을 통해 검색 결과를 도출해낼 수 있음. (Boolean 검사 기본 방법론)

Boolean Model 기본 가정 : 문서의 집합은 고정되어 있음.

말뭉치 : Corpus, 문서의 집합

Refine : 사람이나 검색 시스템이 질의어를 더 정교하게 수정해서 재검색을 하는 행위

검색도 시스템 평가 기준

Precision 정밀도 : 결과가 질의어와 얼마나 부합하는지

모델이 True라고 분류한 것 중에서 실제 True인 것의 비율(=정답률)

실제로 사용자가 찾고자 하는 내용이 담긴 문서 / 모델 검색 결과

정답 / 내가

Recall 재현율 : 질의어에 부합하는 문서를 얼마나 찾아내는지

실제 True인 것 중에서 모델이 True라고 예측한 것의 비율(=제공률)

정답 / 실제

정확도(Accuracy)는 정보 검색 평가에 쓰이지 않음

정밀도가 높으면 재현율이 낮고, 정밀도가 낮으면 재현율이 높음.

정밀도가 100인 경우 : 찾고자 하는 내용이 담긴 문서 100개에서 1개 찾음. → 재현율은 0.01

재현율이 100인 경우 : 찾은 문서 100개 중 찾고자 하는 내용이 담긴 모든 문서가 1개임 → 정밀도는 0.01

**F-measure : 정밀도와 재현율에 가중치를 주고 구한 평균**

→ 흔히 알파(가중치)를 0.5로 주어 아래와 같이 만듦

F-measure로 검색 시스템 성능 평가에 사용함.

예시)

Q1. 검색 대상 문서 100만 개, 각 문서는 평균적으로 1000개의 단어가 있음. 한 단어는 평균적으로 띄어쓰기, 부호 포함 6bytes(6글자). 문서 전체 크기는?

A1. 문서 전체 크기 = 100만 * (1000 * 6bytes) = 6,000,000,000 = 60억bytes = 6GB

Q2. 10억(100만 * 1000 = 1,000,000,000)개 의 단어 중, 500,000개의 다른 단어가 있다. Term-Document Matrix의 크기는?

A2.

Term 개수 = 50만

Document 개수 = 100만

Term-Document Matrix 크기 = 50만 * 100만 = 5천 억

→ Boolean 검색을 위해 Term-Document Matrix를 미리 만들어야 하는데, 크기가 너무 큼.

5천 억개의 0과 1중 0의 비중이 보통 99.8%를 차지하여 1은 0.2%를 차지하여 1000개로 많지 않음.

따라서, 1인 것만 따로 표시하도록 함. ⇒ Inverted Index (Inverted file)

0이 차지하는 비율

term(행) = 50만개, document(열) = 100만개

하나의 문서의 term 정보 = 한 열(50만개의 term), 하나의 문서는 1000개의 단어로 구성됨 ⇒ 하나의 문서에 term 중 평균적으로 1000개의 단어만 나오므로 50만 개의 한 열에서 1은 평균적으로 1000개임. 49만9천개는 0임. ⇒ 50만 개에서 1000개가 1이었으니 100만개에서는 2000개가 1임. ⇒ 2천/100만 = 0.002. 0.2%가 1이고, 99.8%가 0임.

Inverted index (inverted file)

Term-Document Matrix의 공간 상의 문제 해결을 위해 1인 문서만 목록화함.

검색 대상(문서, 웹, PC경로)에 따라 검색 결과가 다르기 때문에 Posting list에는 논리적으로 문서의 번호 식별자를 부여함.

Posting : 문서 번호 식별자 하나하나

Posting list : Posting이 나열된 하나의 배열(리스트)

Posting lists : Posting list의 집합

질의어를 찾을 때 더 빨리 찾을 수 있도록 문서를 정렬해야 하기 때문에, Posting list는 배열보다 연결 리스트를 선호한다. 하지만 포인터 공간을 더 차지한다.

Dictionary == Vocabulary (Term의 집합)

Inverted Index 만드는 과정

[단계]

1. Tokenization (토큰화)→ 만약, 문서가 TXT가 아닌 아래한글, html이라면? → 경우에 따라 토큰화 어려울 수 있음.1-2. Linguistic Modules를 통해 언어에 따라 처리함. (영어 : 모두 소문자로, 원형으로 만듦)어느 토큰이 어느 문서에서 나왔는지 Postings list(해당 토큰의 문서 위치를 나타냄) 구축1-3-1. (Term, DocID) 쌍으로 만듦.1-3-3. 필요 시, TF 정보 추가Term Frequency(TF) : 한 문서를 기준으로 Term이 나온 개수 추가

       Document Frequency(DF) : Term이 나온 문서의 개수 추가
   
       이때 Term Frequency끼리 합을 구함.
   

   DF로 합쳐진 중복 Term은 각각 연결 리스트 식으로 자신의 (DocID, TF)를 가리킴
2. → 나중에 연결 리스트 형식의 Inverted Index의 기틀이 됨.
3. 1-3-5. 필요 시, DF 정보 추가
4. 한 문서의 중복 Term은 하나로 통일.
5. 1-3-2. Term을 기준으로 정렬함.
6. Inverted Index를 만듦.
7. 1-3. Indexer : 토큰을 인덱스로 만듦.
8. Tokenizer 모듈을 통해 토큰화 함.
9. 1-1. 토큰화 : 문서들의 문장을 공백을 기준으로 자름

사람이 쓰는 단어는 한계가 있으므로 Dictionary size는 Postings list에 비해 변화가 적음.

따라서, Dictionary는 검색 서비스를 위해 Main Memory로 load 됨.

Postings는 크기가 점점 커지고 변화도 잦아 Disk에 저장됨.

Postings list 저장 방법

1. 연결 리스트
2. 가변 배열
3. hybrid scheme : 연결리스트 + 가변 배열 (배열을 연결리스트로 연결함.)

질의어

1. Conjunctive : AND시간복잡도 : 비교하는 Posting List 길이의 합if not sorting 시간복잡도 : 비교하는 Posting List 길이의 곱
2. 조건 : Posting list가 정렬되어 있어야 함.
3. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 다르면 작은 쪽의 Posting이 오른쪽으로 이동하고 다시 비교
4. Disjunctive : OR시간복잡도 : 비교하는 Posting List 길이의 합
5. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 달라도 문서 번호가 더 작은 쪽을 먼저 검색 결과에 포함하고 작은 쪽이 오른쪽으로 이동한다.
6. NOT → 시간 오래 걸림NOT이 붙은 Posting list는 오른쪽으로 넘어가기 전에, 자신에게 없는 Posting의 문서 번호와 다른 Posting list와 연산함.NOT이 붙은 Posting의 문서 번호가 NOT이 붙지 않은 Posting의 문서 번호와 다르면, 추가하지 않고 작은 쪽이 오른쪽으로 이동한다. 같으면 추가하지 않고 두 Posting 모두 오른쪽으로 이동한다.
7. <AND>
8. NOT이 붙은 단어가 검색 결과에 포함되면 안 됨.

WestLaw 시스템

질의어를 만들 때, AND, OR, NOT + /숫자, ! 가능함.

띄어쓰기 : OR

/<숫자> : <숫자> 단어 이내에 두 단어가 나올 때, AND

! : Wild-card 문자 *

/s : 한 문장 안에 두 단어가 둘 다 나와야 함. AND

/p : 한 문단 안에 두 단어가 둘 다 나와야 함. AND

Proximity operators : 인접성을 표시할 수 있는 연산 기호

연산 순서 최적화

1. 앞부터 처리
2. 순서 바꿔서 처리 → 시간 절약 가능OR 시간 복잡도 : Posting list size의 합
   1. Doc Freq가 작은 것부터 처리함.
   2. Posting list size == Doc Freq
   3. 연산 시 시간 복잡도를 최대로 계산해서 시간 복잡도가 작은 순서대로 처리함.
3. AND 시간 복잡도 : Posting list size의 합

인접조건

질의어의 단어가 띄어쓰기 단위로 끊어지면 안 되고 붙어있어야 할 때

Proximity 인접조건 명령어 : NEAR

구조화된 TEXT까지 생각해서 검색해보는 방법도 생각해보기(저자와 내용 구조가 맞는 검색)

Inverted Index + Position Information

Position Information : Posting이 해당 문서가 그 문서 내에서 어디에 나왔는지 위치 정보가 담긴 list를 가리킴

Position Information Size = Term Frequency

두 단어가 인접해 있는지 찾는 법 : AND 연산으로 각 문서에 해당 Term 나왔는지 검사 → 두 위치 정보를 비교함 → 인접 조건에 맞을 경우 결과에 포함

인접 차이 : 1이면 두 단어가 붙어있음을 의미하고, 2면 두 단어 사이에 한 단어가 포함되어 있음을 의미함.

Term Freq 활용

Term Freq가 큰 순으로 결과 제공하기

어떤 Term이 하나의 문서에서 Document에서 몇 번 나왔는지 고려

어떤 Posting의 Term Freq == 그 Posting의 Positional Information 리스트의 길이

검색 결과로, 각 문서의 Term Freq의 합이 큰 문서부터 제공함.

Ranking Search

Boolean 모델은 해당 질의어가 문서에 포함 됐는지 안 됐는지만 판단하기 때문에 Ranking을 매기는 건 원칙적으로는 불가능하다.

하지만, 기준을 적용해서 조금 더 유용할 만한 검색 결과를 제공할 수도 있다. Proximity 인접성을 이용해서 인접할 수록 사용자가 더 원하는 정보에 더 가까울 수 있으므로 가까운 순으로 제공하거나, 문서의 Term Freq를 이용해서 큰 순으로 제공하거나, 문서가 만들어진 시간을 인덱스에 부여해서 최근 문서부터 제공할 수 있긴 하다.

정보 검색 VS DB 검색

정보 검색

비구조화 됨

범위 검색 불가능

단, TEXT이더라고 약간의 구조가 있을 수 있음. Semi-Structured Data 예) PPT, XML

글자의 크기, 글자의 굵기와 같은 정보를 이용해 약간의 구조를 추가할 수 있음.

DB 검색

구조화됨.

범위 검색 가능

관련 있는 Concept 검색 : 아직 불가능

용어

Clustering : 군집(모으기)

Classfication : 분류

웹 검색

다양한 문서, 다양한 사람, 질의어, 정보 존재함.

링크된 정보 활용하거나 클릭한 정보 활용 가능함.

Cross-language information retrieval : 교차 언어, 번역해서 검색 결과 제공

Question answering : 질의 응답 시스템 질문&답변

Summarization : 검색결과 요약해서 제공

TEXT mining : TEXT에서 필요한 정보 뽑아서 알려줌

1996년) TEXT와 같이 비구조화된 문서의 규모가 구조화된 문서보다 컸음. 근데 시장에서는 비구조화된 문서를 다루는 건 돈이 되지 않았음

2006년) 여전히 비구조화된 문서의 규모가 크지만 TEXT 검색 서비스 시장이 커지면서 비구조화 문서를 다루는 시장이 성장함

정보검색시스템이 없다면, 유닉스의 grep명령어, | 로 찾을 수 있음. 하지만, 문서의 양이 크다면 속도가 느리기 때문에 정보 검색 목적으로는 적절하지 않다. 특정 내용이 들어가 있는 건 들어가 있으면 더 탐색할 필요가 없으니 쉬운 편이지만, 특정 내용이 들어가 있지 않은 건 파일을 끝까지 다 탐색해 봐야 하기 때문에 어렵다. 단어가 인접해 있는지 여부는 grep 명령으로 찾을 순 없다.

Boolean 모델은 단어 포함 여부만 알 수 있기 때문에 검색 결과로 추출된 문서들의 순위를 매기긴 힘들다. grep 또한, Boolean 모델에 따르기 때문에 순위를 매기긴 힘들다.

Boolean 모델도 점수를 매겨서 Sort할 수 있긴 하지만, 기본적으론 순위 매길 수 없다.

$ grep -v <질의어> * : 모든 문서 파일(*)에서 질의어가 포함되지 않은(-v) 문서를 탐색한다.

Term-document (incidence) matrix Term과 Document의 관계를 나타내는 행렬

검색 대상이 되는 모든 문서에 대해, Term이 Document에 나오면 1, 나오지 않으면 0

질의어와 일치하는 Term의 행들을 찾아서 주어진 질의어에 따라 행끼리 AND, OR, NOT 연산 수행

이때, NOT은 1과 0을 맞바꿈.

bitwise : 같은 위치의 bit끼리 연산

예) 질의어 : Brutus AND Caesar but NOT Calpurnia

Brutus = 110100, Caesar = 110111, Calpurnia = 010000

연산 : 110100 AND 110111 AND 101111 = 100100

→ 1, 4번째 문서가 검색 결과에 포함되고 나머지는 포함되지 않음.

Term-document (incidence) matrix가 주어져 있다면, 질의어 키워드에 해당하는 Term의 행을 찾아서 연산을 통해 검색 결과를 도출해낼 수 있음. (Boolean 검사 기본 방법론)

Boolean Model 기본 가정 : 문서의 집합은 고정되어 있음.

말뭉치 : Corpus, 문서의 집합

Refine : 사람이나 검색 시스템이 질의어를 더 정교하게 수정해서 재검색을 하는 행위

검색도 시스템 평가 기준

Precision 정밀도 : 결과가 질의어와 얼마나 부합하는지

모델이 True라고 분류한 것 중에서 실제 True인 것의 비율(=정답률)

실제로 사용자가 찾고자 하는 내용이 담긴 문서 / 모델 검색 결과

정답 / 내가

Recall 재현율 : 질의어에 부합하는 문서를 얼마나 찾아내는지

실제 True인 것 중에서 모델이 True라고 예측한 것의 비율(=제공률)

정답 / 실제

정확도(Accuracy)는 정보 검색 평가에 쓰이지 않음

정밀도가 높으면 재현율이 낮고, 정밀도가 낮으면 재현율이 높음.

정밀도가 100인 경우 : 찾고자 하는 내용이 담긴 문서 100개에서 1개 찾음. → 재현율은 0.01

재현율이 100인 경우 : 찾은 문서 100개 중 찾고자 하는 내용이 담긴 모든 문서가 1개임 → 정밀도는 0.01

**F-measure : 정밀도와 재현율에 가중치를 주고 구한 평균**

→ 흔히 알파(가중치)를 0.5로 주어 아래와 같이 만듦

F-measure로 검색 시스템 성능 평가에 사용함.

예시)

Q1. 검색 대상 문서 100만 개, 각 문서는 평균적으로 1000개의 단어가 있음. 한 단어는 평균적으로 띄어쓰기, 부호 포함 6bytes(6글자). 문서 전체 크기는?

A1. 문서 전체 크기 = 100만 * (1000 * 6bytes) = 6,000,000,000 = 60억bytes = 6GB

Q2. 10억(100만 * 1000 = 1,000,000,000)개 의 단어 중, 500,000개의 다른 단어가 있다. Term-Document Matrix의 크기는?

A2.

Term 개수 = 50만

Document 개수 = 100만

Term-Document Matrix 크기 = 50만 * 100만 = 5천 억

→ Boolean 검색을 위해 Term-Document Matrix를 미리 만들어야 하는데, 크기가 너무 큼.

5천 억개의 0과 1중 0의 비중이 보통 99.8%를 차지하여 1은 0.2%를 차지하여 1000개로 많지 않음.

따라서, 1인 것만 따로 표시하도록 함. ⇒ Inverted Index (Inverted file)

0이 차지하는 비율

term(행) = 50만개, document(열) = 100만개

하나의 문서의 term 정보 = 한 열(50만개의 term), 하나의 문서는 1000개의 단어로 구성됨 ⇒ 하나의 문서에 term 중 평균적으로 1000개의 단어만 나오므로 50만 개의 한 열에서 1은 평균적으로 1000개임. 49만9천개는 0임. ⇒ 50만 개에서 1000개가 1이었으니 100만개에서는 2000개가 1임. ⇒ 2천/100만 = 0.002. 0.2%가 1이고, 99.8%가 0임.

Inverted index (inverted file)

Term-Document Matrix의 공간 상의 문제 해결을 위해 1인 문서만 목록화함.

검색 대상(문서, 웹, PC경로)에 따라 검색 결과가 다르기 때문에 Posting list에는 논리적으로 문서의 번호 식별자를 부여함.

Posting : 문서 번호 식별자 하나하나

Posting list : Posting이 나열된 하나의 배열(리스트)

Posting lists : Posting list의 집합

질의어를 찾을 때 더 빨리 찾을 수 있도록 문서를 정렬해야 하기 때문에, Posting list는 배열보다 연결 리스트를 선호한다. 하지만 포인터 공간을 더 차지한다.

Dictionary == Vocabulary (Term의 집합)

Inverted Index 만드는 과정

[단계]

1. Tokenization (토큰화)→ 만약, 문서가 TXT가 아닌 아래한글, html이라면? → 경우에 따라 토큰화 어려울 수 있음.1-2. Linguistic Modules를 통해 언어에 따라 처리함. (영어 : 모두 소문자로, 원형으로 만듦)어느 토큰이 어느 문서에서 나왔는지 Postings list(해당 토큰의 문서 위치를 나타냄) 구축1-3-1. (Term, DocID) 쌍으로 만듦.1-3-3. 필요 시, TF 정보 추가Term Frequency(TF) : 한 문서를 기준으로 Term이 나온 개수 추가

       Document Frequency(DF) : Term이 나온 문서의 개수 추가
   
       이때 Term Frequency끼리 합을 구함.
   

   DF로 합쳐진 중복 Term은 각각 연결 리스트 식으로 자신의 (DocID, TF)를 가리킴
2. → 나중에 연결 리스트 형식의 Inverted Index의 기틀이 됨.
3. 1-3-5. 필요 시, DF 정보 추가
4. 한 문서의 중복 Term은 하나로 통일.
5. 1-3-2. Term을 기준으로 정렬함.
6. Inverted Index를 만듦.
7. 1-3. Indexer : 토큰을 인덱스로 만듦.
8. Tokenizer 모듈을 통해 토큰화 함.
9. 1-1. 토큰화 : 문서들의 문장을 공백을 기준으로 자름

사람이 쓰는 단어는 한계가 있으므로 Dictionary size는 Postings list에 비해 변화가 적음.

따라서, Dictionary는 검색 서비스를 위해 Main Memory로 load 됨.

Postings는 크기가 점점 커지고 변화도 잦아 Disk에 저장됨.

Postings list 저장 방법

1. 연결 리스트
2. 가변 배열
3. hybrid scheme : 연결리스트 + 가변 배열 (배열을 연결리스트로 연결함.)

질의어

1. Conjunctive : AND시간복잡도 : 비교하는 Posting List 길이의 합if not sorting 시간복잡도 : 비교하는 Posting List 길이의 곱
2. 조건 : Posting list가 정렬되어 있어야 함.
3. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 다르면 작은 쪽의 Posting이 오른쪽으로 이동하고 다시 비교
4. Disjunctive : OR시간복잡도 : 비교하는 Posting List 길이의 합
5. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 달라도 문서 번호가 더 작은 쪽을 먼저 검색 결과에 포함하고 작은 쪽이 오른쪽으로 이동한다.
6. NOT → 시간 오래 걸림NOT이 붙은 Posting list는 오른쪽으로 넘어가기 전에, 자신에게 없는 Posting의 문서 번호와 다른 Posting list와 연산함.NOT이 붙은 Posting의 문서 번호가 NOT이 붙지 않은 Posting의 문서 번호와 다르면, 추가하지 않고 작은 쪽이 오른쪽으로 이동한다. 같으면 추가하지 않고 두 Posting 모두 오른쪽으로 이동한다.
7. <AND>
8. NOT이 붙은 단어가 검색 결과에 포함되면 안 됨.

WestLaw 시스템

질의어를 만들 때, AND, OR, NOT + /숫자, ! 가능함.

띄어쓰기 : OR

/<숫자> : <숫자> 단어 이내에 두 단어가 나올 때, AND

! : Wild-card 문자 *

/s : 한 문장 안에 두 단어가 둘 다 나와야 함. AND

/p : 한 문단 안에 두 단어가 둘 다 나와야 함. AND

Proximity operators : 인접성을 표시할 수 있는 연산 기호

연산 순서 최적화

1. 앞부터 처리
2. 순서 바꿔서 처리 → 시간 절약 가능OR 시간 복잡도 : Posting list size의 합
   1. Doc Freq가 작은 것부터 처리함.
   2. Posting list size == Doc Freq
   3. 연산 시 시간 복잡도를 최대로 계산해서 시간 복잡도가 작은 순서대로 처리함.
3. AND 시간 복잡도 : Posting list size의 합

인접조건

질의어의 단어가 띄어쓰기 단위로 끊어지면 안 되고 붙어있어야 할 때

Proximity 인접조건 명령어 : NEAR

구조화된 TEXT까지 생각해서 검색해보는 방법도 생각해보기(저자와 내용 구조가 맞는 검색)

Inverted Index + Position Information

Position Information : Posting이 해당 문서가 그 문서 내에서 어디에 나왔는지 위치 정보가 담긴 list를 가리킴

Position Information Size = Term Frequency

두 단어가 인접해 있는지 찾는 법 : AND 연산으로 각 문서에 해당 Term 나왔는지 검사 → 두 위치 정보를 비교함 → 인접 조건에 맞을 경우 결과에 포함

인접 차이 : 1이면 두 단어가 붙어있음을 의미하고, 2면 두 단어 사이에 한 단어가 포함되어 있음을 의미함.

Term Freq 활용

Term Freq가 큰 순으로 결과 제공하기

어떤 Term이 하나의 문서에서 Document에서 몇 번 나왔는지 고려

어떤 Posting의 Term Freq == 그 Posting의 Positional Information 리스트의 길이

검색 결과로, 각 문서의 Term Freq의 합이 큰 문서부터 제공함.

Ranking Search

Boolean 모델은 해당 질의어가 문서에 포함 됐는지 안 됐는지만 판단하기 때문에 Ranking을 매기는 건 원칙적으로는 불가능하다.

하지만, 기준을 적용해서 조금 더 유용할 만한 검색 결과를 제공할 수도 있다. Proximity 인접성을 이용해서 인접할 수록 사용자가 더 원하는 정보에 더 가까울 수 있으므로 가까운 순으로 제공하거나, 문서의 Term Freq를 이용해서 큰 순으로 제공하거나, 문서가 만들어진 시간을 인덱스에 부여해서 최근 문서부터 제공할 수 있긴 하다.

정보 검색 VS DB 검색

정보 검색

비구조화 됨

범위 검색 불가능

단, TEXT이더라고 약간의 구조가 있을 수 있음. Semi-Structured Data 예) PPT, XML

글자의 크기, 글자의 굵기와 같은 정보를 이용해 약간의 구조를 추가할 수 있음.

DB 검색

구조화됨.

범위 검색 가능

관련 있는 Concept 검색 : 아직 불가능

용어

Clustering : 군집(모으기)

Classfication : 분류

웹 검색

다양한 문서, 다양한 사람, 질의어, 정보 존재함.

링크된 정보 활용하거나 클릭한 정보 활용 가능함.

Cross-language information retrieval : 교차 언어, 번역해서 검색 결과 제공

Question answering : 질의 응답 시스템 질문&답변

Summarization : 검색결과 요약해서 제공

TEXT mining : TEXT에서 필요한 정보 뽑아서 알려줌

1996년) TEXT와 같이 비구조화된 문서의 규모가 구조화된 문서보다 컸음. 근데 시장에서는 비구조화된 문서를 다루는 건 돈이 되지 않았음

2006년) 여전히 비구조화된 문서의 규모가 크지만 TEXT 검색 서비스 시장이 커지면서 비구조화 문서를 다루는 시장이 성장함

정보검색시스템이 없다면, 유닉스의 grep명령어, | 로 찾을 수 있음. 하지만, 문서의 양이 크다면 속도가 느리기 때문에 정보 검색 목적으로는 적절하지 않다. 특정 내용이 들어가 있는 건 들어가 있으면 더 탐색할 필요가 없으니 쉬운 편이지만, 특정 내용이 들어가 있지 않은 건 파일을 끝까지 다 탐색해 봐야 하기 때문에 어렵다. 단어가 인접해 있는지 여부는 grep 명령으로 찾을 순 없다.

Boolean 모델은 단어 포함 여부만 알 수 있기 때문에 검색 결과로 추출된 문서들의 순위를 매기긴 힘들다. grep 또한, Boolean 모델에 따르기 때문에 순위를 매기긴 힘들다.

Boolean 모델도 점수를 매겨서 Sort할 수 있긴 하지만, 기본적으론 순위 매길 수 없다.

$ grep -v <질의어> * : 모든 문서 파일(*)에서 질의어가 포함되지 않은(-v) 문서를 탐색한다.

Term-document (incidence) matrix Term과 Document의 관계를 나타내는 행렬

검색 대상이 되는 모든 문서에 대해, Term이 Document에 나오면 1, 나오지 않으면 0

질의어와 일치하는 Term의 행들을 찾아서 주어진 질의어에 따라 행끼리 AND, OR, NOT 연산 수행

이때, NOT은 1과 0을 맞바꿈.

bitwise : 같은 위치의 bit끼리 연산

예) 질의어 : Brutus AND Caesar but NOT Calpurnia

Brutus = 110100, Caesar = 110111, Calpurnia = 010000

연산 : 110100 AND 110111 AND 101111 = 100100

→ 1, 4번째 문서가 검색 결과에 포함되고 나머지는 포함되지 않음.

Term-document (incidence) matrix가 주어져 있다면, 질의어 키워드에 해당하는 Term의 행을 찾아서 연산을 통해 검색 결과를 도출해낼 수 있음. (Boolean 검사 기본 방법론)

Boolean Model 기본 가정 : 문서의 집합은 고정되어 있음.

말뭉치 : Corpus, 문서의 집합

Refine : 사람이나 검색 시스템이 질의어를 더 정교하게 수정해서 재검색을 하는 행위

검색도 시스템 평가 기준

Precision 정밀도 : 결과가 질의어와 얼마나 부합하는지

모델이 True라고 분류한 것 중에서 실제 True인 것의 비율(=정답률)

실제로 사용자가 찾고자 하는 내용이 담긴 문서 / 모델 검색 결과

정답 / 내가

Recall 재현율 : 질의어에 부합하는 문서를 얼마나 찾아내는지

실제 True인 것 중에서 모델이 True라고 예측한 것의 비율(=제공률)

정답 / 실제

정확도(Accuracy)는 정보 검색 평가에 쓰이지 않음

정밀도가 높으면 재현율이 낮고, 정밀도가 낮으면 재현율이 높음.

정밀도가 100인 경우 : 찾고자 하는 내용이 담긴 문서 100개에서 1개 찾음. → 재현율은 0.01

재현율이 100인 경우 : 찾은 문서 100개 중 찾고자 하는 내용이 담긴 모든 문서가 1개임 → 정밀도는 0.01

**F-measure : 정밀도와 재현율에 가중치를 주고 구한 평균**

→ 흔히 알파(가중치)를 0.5로 주어 아래와 같이 만듦

F-measure로 검색 시스템 성능 평가에 사용함.

예시)

Q1. 검색 대상 문서 100만 개, 각 문서는 평균적으로 1000개의 단어가 있음. 한 단어는 평균적으로 띄어쓰기, 부호 포함 6bytes(6글자). 문서 전체 크기는?

A1. 문서 전체 크기 = 100만 * (1000 * 6bytes) = 6,000,000,000 = 60억bytes = 6GB

Q2. 10억(100만 * 1000 = 1,000,000,000)개 의 단어 중, 500,000개의 다른 단어가 있다. Term-Document Matrix의 크기는?

A2.

Term 개수 = 50만

Document 개수 = 100만

Term-Document Matrix 크기 = 50만 * 100만 = 5천 억

→ Boolean 검색을 위해 Term-Document Matrix를 미리 만들어야 하는데, 크기가 너무 큼.

5천 억개의 0과 1중 0의 비중이 보통 99.8%를 차지하여 1은 0.2%를 차지하여 1000개로 많지 않음.

따라서, 1인 것만 따로 표시하도록 함. ⇒ Inverted Index (Inverted file)

0이 차지하는 비율

term(행) = 50만개, document(열) = 100만개

하나의 문서의 term 정보 = 한 열(50만개의 term), 하나의 문서는 1000개의 단어로 구성됨 ⇒ 하나의 문서에 term 중 평균적으로 1000개의 단어만 나오므로 50만 개의 한 열에서 1은 평균적으로 1000개임. 49만9천개는 0임. ⇒ 50만 개에서 1000개가 1이었으니 100만개에서는 2000개가 1임. ⇒ 2천/100만 = 0.002. 0.2%가 1이고, 99.8%가 0임.

Inverted index (inverted file)

Term-Document Matrix의 공간 상의 문제 해결을 위해 1인 문서만 목록화함.

검색 대상(문서, 웹, PC경로)에 따라 검색 결과가 다르기 때문에 Posting list에는 논리적으로 문서의 번호 식별자를 부여함.

Posting : 문서 번호 식별자 하나하나

Posting list : Posting이 나열된 하나의 배열(리스트)

Posting lists : Posting list의 집합

질의어를 찾을 때 더 빨리 찾을 수 있도록 문서를 정렬해야 하기 때문에, Posting list는 배열보다 연결 리스트를 선호한다. 하지만 포인터 공간을 더 차지한다.

Dictionary == Vocabulary (Term의 집합)

Inverted Index 만드는 과정

[단계]

1. Tokenization (토큰화)→ 만약, 문서가 TXT가 아닌 아래한글, html이라면? → 경우에 따라 토큰화 어려울 수 있음.1-2. Linguistic Modules를 통해 언어에 따라 처리함. (영어 : 모두 소문자로, 원형으로 만듦)어느 토큰이 어느 문서에서 나왔는지 Postings list(해당 토큰의 문서 위치를 나타냄) 구축1-3-1. (Term, DocID) 쌍으로 만듦.1-3-3. 필요 시, TF 정보 추가Term Frequency(TF) : 한 문서를 기준으로 Term이 나온 개수 추가

       Document Frequency(DF) : Term이 나온 문서의 개수 추가
   
       이때 Term Frequency끼리 합을 구함.
   

   DF로 합쳐진 중복 Term은 각각 연결 리스트 식으로 자신의 (DocID, TF)를 가리킴
2. → 나중에 연결 리스트 형식의 Inverted Index의 기틀이 됨.
3. 1-3-5. 필요 시, DF 정보 추가
4. 한 문서의 중복 Term은 하나로 통일.
5. 1-3-2. Term을 기준으로 정렬함.
6. Inverted Index를 만듦.
7. 1-3. Indexer : 토큰을 인덱스로 만듦.
8. Tokenizer 모듈을 통해 토큰화 함.
9. 1-1. 토큰화 : 문서들의 문장을 공백을 기준으로 자름

사람이 쓰는 단어는 한계가 있으므로 Dictionary size는 Postings list에 비해 변화가 적음.

따라서, Dictionary는 검색 서비스를 위해 Main Memory로 load 됨.

Postings는 크기가 점점 커지고 변화도 잦아 Disk에 저장됨.

Postings list 저장 방법

1. 연결 리스트
2. 가변 배열
3. hybrid scheme : 연결리스트 + 가변 배열 (배열을 연결리스트로 연결함.)

질의어

1. Conjunctive : AND시간복잡도 : 비교하는 Posting List 길이의 합if not sorting 시간복잡도 : 비교하는 Posting List 길이의 곱
2. 조건 : Posting list가 정렬되어 있어야 함.
3. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 다르면 작은 쪽의 Posting이 오른쪽으로 이동하고 다시 비교
4. Disjunctive : OR시간복잡도 : 비교하는 Posting List 길이의 합
5. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 달라도 문서 번호가 더 작은 쪽을 먼저 검색 결과에 포함하고 작은 쪽이 오른쪽으로 이동한다.
6. NOT → 시간 오래 걸림NOT이 붙은 Posting list는 오른쪽으로 넘어가기 전에, 자신에게 없는 Posting의 문서 번호와 다른 Posting list와 연산함.NOT이 붙은 Posting의 문서 번호가 NOT이 붙지 않은 Posting의 문서 번호와 다르면, 추가하지 않고 작은 쪽이 오른쪽으로 이동한다. 같으면 추가하지 않고 두 Posting 모두 오른쪽으로 이동한다.
7. <AND>
8. NOT이 붙은 단어가 검색 결과에 포함되면 안 됨.

WestLaw 시스템

질의어를 만들 때, AND, OR, NOT + /숫자, ! 가능함.

띄어쓰기 : OR

/<숫자> : <숫자> 단어 이내에 두 단어가 나올 때, AND

! : Wild-card 문자 *

/s : 한 문장 안에 두 단어가 둘 다 나와야 함. AND

/p : 한 문단 안에 두 단어가 둘 다 나와야 함. AND

Proximity operators : 인접성을 표시할 수 있는 연산 기호

연산 순서 최적화

1. 앞부터 처리
2. 순서 바꿔서 처리 → 시간 절약 가능OR 시간 복잡도 : Posting list size의 합
   1. Doc Freq가 작은 것부터 처리함.
   2. Posting list size == Doc Freq
   3. 연산 시 시간 복잡도를 최대로 계산해서 시간 복잡도가 작은 순서대로 처리함.
3. AND 시간 복잡도 : Posting list size의 합

인접조건

질의어의 단어가 띄어쓰기 단위로 끊어지면 안 되고 붙어있어야 할 때

Proximity 인접조건 명령어 : NEAR

구조화된 TEXT까지 생각해서 검색해보는 방법도 생각해보기(저자와 내용 구조가 맞는 검색)

Inverted Index + Position Information

Position Information : Posting이 해당 문서가 그 문서 내에서 어디에 나왔는지 위치 정보가 담긴 list를 가리킴

Position Information Size = Term Frequency

두 단어가 인접해 있는지 찾는 법 : AND 연산으로 각 문서에 해당 Term 나왔는지 검사 → 두 위치 정보를 비교함 → 인접 조건에 맞을 경우 결과에 포함

인접 차이 : 1이면 두 단어가 붙어있음을 의미하고, 2면 두 단어 사이에 한 단어가 포함되어 있음을 의미함.

Term Freq 활용

Term Freq가 큰 순으로 결과 제공하기

어떤 Term이 하나의 문서에서 Document에서 몇 번 나왔는지 고려

어떤 Posting의 Term Freq == 그 Posting의 Positional Information 리스트의 길이

검색 결과로, 각 문서의 Term Freq의 합이 큰 문서부터 제공함.

Ranking Search

Boolean 모델은 해당 질의어가 문서에 포함 됐는지 안 됐는지만 판단하기 때문에 Ranking을 매기는 건 원칙적으로는 불가능하다.

하지만, 기준을 적용해서 조금 더 유용할 만한 검색 결과를 제공할 수도 있다. Proximity 인접성을 이용해서 인접할 수록 사용자가 더 원하는 정보에 더 가까울 수 있으므로 가까운 순으로 제공하거나, 문서의 Term Freq를 이용해서 큰 순으로 제공하거나, 문서가 만들어진 시간을 인덱스에 부여해서 최근 문서부터 제공할 수 있긴 하다.

정보 검색 VS DB 검색

정보 검색

비구조화 됨

범위 검색 불가능

단, TEXT이더라고 약간의 구조가 있을 수 있음. Semi-Structured Data 예) PPT, XML

글자의 크기, 글자의 굵기와 같은 정보를 이용해 약간의 구조를 추가할 수 있음.

DB 검색

구조화됨.

범위 검색 가능

관련 있는 Concept 검색 : 아직 불가능

용어

Clustering : 군집(모으기)

Classfication : 분류

웹 검색

다양한 문서, 다양한 사람, 질의어, 정보 존재함.

링크된 정보 활용하거나 클릭한 정보 활용 가능함.

Cross-language information retrieval : 교차 언어, 번역해서 검색 결과 제공

Question answering : 질의 응답 시스템 질문&답변

Summarization : 검색결과 요약해서 제공

TEXT mining : TEXT에서 필요한 정보 뽑아서 알려줌

1996년) TEXT와 같이 비구조화된 문서의 규모가 구조화된 문서보다 컸음. 근데 시장에서는 비구조화된 문서를 다루는 건 돈이 되지 않았음

2006년) 여전히 비구조화된 문서의 규모가 크지만 TEXT 검색 서비스 시장이 커지면서 비구조화 문서를 다루는 시장이 성장함

정보검색시스템이 없다면, 유닉스의 grep명령어, | 로 찾을 수 있음. 하지만, 문서의 양이 크다면 속도가 느리기 때문에 정보 검색 목적으로는 적절하지 않다. 특정 내용이 들어가 있는 건 들어가 있으면 더 탐색할 필요가 없으니 쉬운 편이지만, 특정 내용이 들어가 있지 않은 건 파일을 끝까지 다 탐색해 봐야 하기 때문에 어렵다. 단어가 인접해 있는지 여부는 grep 명령으로 찾을 순 없다.

Boolean 모델은 단어 포함 여부만 알 수 있기 때문에 검색 결과로 추출된 문서들의 순위를 매기긴 힘들다. grep 또한, Boolean 모델에 따르기 때문에 순위를 매기긴 힘들다.

Boolean 모델도 점수를 매겨서 Sort할 수 있긴 하지만, 기본적으론 순위 매길 수 없다.

$ grep -v <질의어> * : 모든 문서 파일(*)에서 질의어가 포함되지 않은(-v) 문서를 탐색한다.

Term-document (incidence) matrix Term과 Document의 관계를 나타내는 행렬

검색 대상이 되는 모든 문서에 대해, Term이 Document에 나오면 1, 나오지 않으면 0

질의어와 일치하는 Term의 행들을 찾아서 주어진 질의어에 따라 행끼리 AND, OR, NOT 연산 수행

이때, NOT은 1과 0을 맞바꿈.

bitwise : 같은 위치의 bit끼리 연산

예) 질의어 : Brutus AND Caesar but NOT Calpurnia

Brutus = 110100, Caesar = 110111, Calpurnia = 010000

연산 : 110100 AND 110111 AND 101111 = 100100

→ 1, 4번째 문서가 검색 결과에 포함되고 나머지는 포함되지 않음.

Term-document (incidence) matrix가 주어져 있다면, 질의어 키워드에 해당하는 Term의 행을 찾아서 연산을 통해 검색 결과를 도출해낼 수 있음. (Boolean 검사 기본 방법론)

Boolean Model 기본 가정 : 문서의 집합은 고정되어 있음.

말뭉치 : Corpus, 문서의 집합

Refine : 사람이나 검색 시스템이 질의어를 더 정교하게 수정해서 재검색을 하는 행위

검색도 시스템 평가 기준

Precision 정밀도 : 결과가 질의어와 얼마나 부합하는지

모델이 True라고 분류한 것 중에서 실제 True인 것의 비율(=정답률)

실제로 사용자가 찾고자 하는 내용이 담긴 문서 / 모델 검색 결과

정답 / 내가

Recall 재현율 : 질의어에 부합하는 문서를 얼마나 찾아내는지

실제 True인 것 중에서 모델이 True라고 예측한 것의 비율(=제공률)

정답 / 실제

정확도(Accuracy)는 정보 검색 평가에 쓰이지 않음

정밀도가 높으면 재현율이 낮고, 정밀도가 낮으면 재현율이 높음.

정밀도가 100인 경우 : 찾고자 하는 내용이 담긴 문서 100개에서 1개 찾음. → 재현율은 0.01

재현율이 100인 경우 : 찾은 문서 100개 중 찾고자 하는 내용이 담긴 모든 문서가 1개임 → 정밀도는 0.01

**F-measure : 정밀도와 재현율에 가중치를 주고 구한 평균**

→ 흔히 알파(가중치)를 0.5로 주어 아래와 같이 만듦

F-measure로 검색 시스템 성능 평가에 사용함.

예시)

Q1. 검색 대상 문서 100만 개, 각 문서는 평균적으로 1000개의 단어가 있음. 한 단어는 평균적으로 띄어쓰기, 부호 포함 6bytes(6글자). 문서 전체 크기는?

A1. 문서 전체 크기 = 100만 * (1000 * 6bytes) = 6,000,000,000 = 60억bytes = 6GB

Q2. 10억(100만 * 1000 = 1,000,000,000)개 의 단어 중, 500,000개의 다른 단어가 있다. Term-Document Matrix의 크기는?

A2.

Term 개수 = 50만

Document 개수 = 100만

Term-Document Matrix 크기 = 50만 * 100만 = 5천 억

→ Boolean 검색을 위해 Term-Document Matrix를 미리 만들어야 하는데, 크기가 너무 큼.

5천 억개의 0과 1중 0의 비중이 보통 99.8%를 차지하여 1은 0.2%를 차지하여 1000개로 많지 않음.

따라서, 1인 것만 따로 표시하도록 함. ⇒ Inverted Index (Inverted file)

0이 차지하는 비율

term(행) = 50만개, document(열) = 100만개

하나의 문서의 term 정보 = 한 열(50만개의 term), 하나의 문서는 1000개의 단어로 구성됨 ⇒ 하나의 문서에 term 중 평균적으로 1000개의 단어만 나오므로 50만 개의 한 열에서 1은 평균적으로 1000개임. 49만9천개는 0임. ⇒ 50만 개에서 1000개가 1이었으니 100만개에서는 2000개가 1임. ⇒ 2천/100만 = 0.002. 0.2%가 1이고, 99.8%가 0임.

Inverted index (inverted file)

Term-Document Matrix의 공간 상의 문제 해결을 위해 1인 문서만 목록화함.

검색 대상(문서, 웹, PC경로)에 따라 검색 결과가 다르기 때문에 Posting list에는 논리적으로 문서의 번호 식별자를 부여함.

Posting : 문서 번호 식별자 하나하나

Posting list : Posting이 나열된 하나의 배열(리스트)

Posting lists : Posting list의 집합

질의어를 찾을 때 더 빨리 찾을 수 있도록 문서를 정렬해야 하기 때문에, Posting list는 배열보다 연결 리스트를 선호한다. 하지만 포인터 공간을 더 차지한다.

Dictionary == Vocabulary (Term의 집합)

Inverted Index 만드는 과정

[단계]

1. Tokenization (토큰화)→ 만약, 문서가 TXT가 아닌 아래한글, html이라면? → 경우에 따라 토큰화 어려울 수 있음.1-2. Linguistic Modules를 통해 언어에 따라 처리함. (영어 : 모두 소문자로, 원형으로 만듦)어느 토큰이 어느 문서에서 나왔는지 Postings list(해당 토큰의 문서 위치를 나타냄) 구축1-3-1. (Term, DocID) 쌍으로 만듦.1-3-3. 필요 시, TF 정보 추가Term Frequency(TF) : 한 문서를 기준으로 Term이 나온 개수 추가

       Document Frequency(DF) : Term이 나온 문서의 개수 추가
   
       이때 Term Frequency끼리 합을 구함.
   

   DF로 합쳐진 중복 Term은 각각 연결 리스트 식으로 자신의 (DocID, TF)를 가리킴
2. → 나중에 연결 리스트 형식의 Inverted Index의 기틀이 됨.
3. 1-3-5. 필요 시, DF 정보 추가
4. 한 문서의 중복 Term은 하나로 통일.
5. 1-3-2. Term을 기준으로 정렬함.
6. Inverted Index를 만듦.
7. 1-3. Indexer : 토큰을 인덱스로 만듦.
8. Tokenizer 모듈을 통해 토큰화 함.
9. 1-1. 토큰화 : 문서들의 문장을 공백을 기준으로 자름

사람이 쓰는 단어는 한계가 있으므로 Dictionary size는 Postings list에 비해 변화가 적음.

따라서, Dictionary는 검색 서비스를 위해 Main Memory로 load 됨.

Postings는 크기가 점점 커지고 변화도 잦아 Disk에 저장됨.

Postings list 저장 방법

1. 연결 리스트
2. 가변 배열
3. hybrid scheme : 연결리스트 + 가변 배열 (배열을 연결리스트로 연결함.)

질의어

1. Conjunctive : AND시간복잡도 : 비교하는 Posting List 길이의 합if not sorting 시간복잡도 : 비교하는 Posting List 길이의 곱
2. 조건 : Posting list가 정렬되어 있어야 함.
3. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 다르면 작은 쪽의 Posting이 오른쪽으로 이동하고 다시 비교
4. Disjunctive : OR시간복잡도 : 비교하는 Posting List 길이의 합
5. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 달라도 문서 번호가 더 작은 쪽을 먼저 검색 결과에 포함하고 작은 쪽이 오른쪽으로 이동한다.
6. NOT → 시간 오래 걸림NOT이 붙은 Posting list는 오른쪽으로 넘어가기 전에, 자신에게 없는 Posting의 문서 번호와 다른 Posting list와 연산함.NOT이 붙은 Posting의 문서 번호가 NOT이 붙지 않은 Posting의 문서 번호와 다르면, 추가하지 않고 작은 쪽이 오른쪽으로 이동한다. 같으면 추가하지 않고 두 Posting 모두 오른쪽으로 이동한다.
7. <AND>
8. NOT이 붙은 단어가 검색 결과에 포함되면 안 됨.

WestLaw 시스템

질의어를 만들 때, AND, OR, NOT + /숫자, ! 가능함.

띄어쓰기 : OR

/<숫자> : <숫자> 단어 이내에 두 단어가 나올 때, AND

! : Wild-card 문자 *

/s : 한 문장 안에 두 단어가 둘 다 나와야 함. AND

/p : 한 문단 안에 두 단어가 둘 다 나와야 함. AND

Proximity operators : 인접성을 표시할 수 있는 연산 기호

연산 순서 최적화

1. 앞부터 처리
2. 순서 바꿔서 처리 → 시간 절약 가능OR 시간 복잡도 : Posting list size의 합
   1. Doc Freq가 작은 것부터 처리함.
   2. Posting list size == Doc Freq
   3. 연산 시 시간 복잡도를 최대로 계산해서 시간 복잡도가 작은 순서대로 처리함.
3. AND 시간 복잡도 : Posting list size의 합

인접조건

질의어의 단어가 띄어쓰기 단위로 끊어지면 안 되고 붙어있어야 할 때

Proximity 인접조건 명령어 : NEAR

구조화된 TEXT까지 생각해서 검색해보는 방법도 생각해보기(저자와 내용 구조가 맞는 검색)

Inverted Index + Position Information

Position Information : Posting이 해당 문서가 그 문서 내에서 어디에 나왔는지 위치 정보가 담긴 list를 가리킴

Position Information Size = Term Frequency

두 단어가 인접해 있는지 찾는 법 : AND 연산으로 각 문서에 해당 Term 나왔는지 검사 → 두 위치 정보를 비교함 → 인접 조건에 맞을 경우 결과에 포함

인접 차이 : 1이면 두 단어가 붙어있음을 의미하고, 2면 두 단어 사이에 한 단어가 포함되어 있음을 의미함.

Term Freq 활용

Term Freq가 큰 순으로 결과 제공하기

어떤 Term이 하나의 문서에서 Document에서 몇 번 나왔는지 고려

어떤 Posting의 Term Freq == 그 Posting의 Positional Information 리스트의 길이

검색 결과로, 각 문서의 Term Freq의 합이 큰 문서부터 제공함.

Ranking Search

Boolean 모델은 해당 질의어가 문서에 포함 됐는지 안 됐는지만 판단하기 때문에 Ranking을 매기는 건 원칙적으로는 불가능하다.

하지만, 기준을 적용해서 조금 더 유용할 만한 검색 결과를 제공할 수도 있다. Proximity 인접성을 이용해서 인접할 수록 사용자가 더 원하는 정보에 더 가까울 수 있으므로 가까운 순으로 제공하거나, 문서의 Term Freq를 이용해서 큰 순으로 제공하거나, 문서가 만들어진 시간을 인덱스에 부여해서 최근 문서부터 제공할 수 있긴 하다.

정보 검색 VS DB 검색

정보 검색

비구조화 됨

범위 검색 불가능

단, TEXT이더라고 약간의 구조가 있을 수 있음. Semi-Structured Data 예) PPT, XML

글자의 크기, 글자의 굵기와 같은 정보를 이용해 약간의 구조를 추가할 수 있음.

DB 검색

구조화됨.

범위 검색 가능

관련 있는 Concept 검색 : 아직 불가능

용어

Clustering : 군집(모으기)

Classfication : 분류

웹 검색

다양한 문서, 다양한 사람, 질의어, 정보 존재함.

링크된 정보 활용하거나 클릭한 정보 활용 가능함.

Cross-language information retrieval : 교차 언어, 번역해서 검색 결과 제공

Question answering : 질의 응답 시스템 질문&답변

Summarization : 검색결과 요약해서 제공

TEXT mining : TEXT에서 필요한 정보 뽑아서 알려줌

1996년) TEXT와 같이 비구조화된 문서의 규모가 구조화된 문서보다 컸음. 근데 시장에서는 비구조화된 문서를 다루는 건 돈이 되지 않았음

2006년) 여전히 비구조화된 문서의 규모가 크지만 TEXT 검색 서비스 시장이 커지면서 비구조화 문서를 다루는 시장이 성장함

정보검색시스템이 없다면, 유닉스의 grep명령어, | 로 찾을 수 있음. 하지만, 문서의 양이 크다면 속도가 느리기 때문에 정보 검색 목적으로는 적절하지 않다. 특정 내용이 들어가 있는 건 들어가 있으면 더 탐색할 필요가 없으니 쉬운 편이지만, 특정 내용이 들어가 있지 않은 건 파일을 끝까지 다 탐색해 봐야 하기 때문에 어렵다. 단어가 인접해 있는지 여부는 grep 명령으로 찾을 순 없다.

Boolean 모델은 단어 포함 여부만 알 수 있기 때문에 검색 결과로 추출된 문서들의 순위를 매기긴 힘들다. grep 또한, Boolean 모델에 따르기 때문에 순위를 매기긴 힘들다.

Boolean 모델도 점수를 매겨서 Sort할 수 있긴 하지만, 기본적으론 순위 매길 수 없다.

$ grep -v <질의어> * : 모든 문서 파일(*)에서 질의어가 포함되지 않은(-v) 문서를 탐색한다.

Term-document (incidence) matrix Term과 Document의 관계를 나타내는 행렬

검색 대상이 되는 모든 문서에 대해, Term이 Document에 나오면 1, 나오지 않으면 0

질의어와 일치하는 Term의 행들을 찾아서 주어진 질의어에 따라 행끼리 AND, OR, NOT 연산 수행

이때, NOT은 1과 0을 맞바꿈.

bitwise : 같은 위치의 bit끼리 연산

예) 질의어 : Brutus AND Caesar but NOT Calpurnia

Brutus = 110100, Caesar = 110111, Calpurnia = 010000

연산 : 110100 AND 110111 AND 101111 = 100100

→ 1, 4번째 문서가 검색 결과에 포함되고 나머지는 포함되지 않음.

Term-document (incidence) matrix가 주어져 있다면, 질의어 키워드에 해당하는 Term의 행을 찾아서 연산을 통해 검색 결과를 도출해낼 수 있음. (Boolean 검사 기본 방법론)

Boolean Model 기본 가정 : 문서의 집합은 고정되어 있음.

말뭉치 : Corpus, 문서의 집합

Refine : 사람이나 검색 시스템이 질의어를 더 정교하게 수정해서 재검색을 하는 행위

검색도 시스템 평가 기준

Precision 정밀도 : 결과가 질의어와 얼마나 부합하는지

모델이 True라고 분류한 것 중에서 실제 True인 것의 비율(=정답률)

실제로 사용자가 찾고자 하는 내용이 담긴 문서 / 모델 검색 결과

정답 / 내가

Recall 재현율 : 질의어에 부합하는 문서를 얼마나 찾아내는지

실제 True인 것 중에서 모델이 True라고 예측한 것의 비율(=제공률)

정답 / 실제

정확도(Accuracy)는 정보 검색 평가에 쓰이지 않음

정밀도가 높으면 재현율이 낮고, 정밀도가 낮으면 재현율이 높음.

정밀도가 100인 경우 : 찾고자 하는 내용이 담긴 문서 100개에서 1개 찾음. → 재현율은 0.01

재현율이 100인 경우 : 찾은 문서 100개 중 찾고자 하는 내용이 담긴 모든 문서가 1개임 → 정밀도는 0.01

**F-measure : 정밀도와 재현율에 가중치를 주고 구한 평균**

→ 흔히 알파(가중치)를 0.5로 주어 아래와 같이 만듦

F-measure로 검색 시스템 성능 평가에 사용함.

예시)

Q1. 검색 대상 문서 100만 개, 각 문서는 평균적으로 1000개의 단어가 있음. 한 단어는 평균적으로 띄어쓰기, 부호 포함 6bytes(6글자). 문서 전체 크기는?

A1. 문서 전체 크기 = 100만 * (1000 * 6bytes) = 6,000,000,000 = 60억bytes = 6GB

Q2. 10억(100만 * 1000 = 1,000,000,000)개 의 단어 중, 500,000개의 다른 단어가 있다. Term-Document Matrix의 크기는?

A2.

Term 개수 = 50만

Document 개수 = 100만

Term-Document Matrix 크기 = 50만 * 100만 = 5천 억

→ Boolean 검색을 위해 Term-Document Matrix를 미리 만들어야 하는데, 크기가 너무 큼.

5천 억개의 0과 1중 0의 비중이 보통 99.8%를 차지하여 1은 0.2%를 차지하여 1000개로 많지 않음.

따라서, 1인 것만 따로 표시하도록 함. ⇒ Inverted Index (Inverted file)

0이 차지하는 비율

term(행) = 50만개, document(열) = 100만개

하나의 문서의 term 정보 = 한 열(50만개의 term), 하나의 문서는 1000개의 단어로 구성됨 ⇒ 하나의 문서에 term 중 평균적으로 1000개의 단어만 나오므로 50만 개의 한 열에서 1은 평균적으로 1000개임. 49만9천개는 0임. ⇒ 50만 개에서 1000개가 1이었으니 100만개에서는 2000개가 1임. ⇒ 2천/100만 = 0.002. 0.2%가 1이고, 99.8%가 0임.

Inverted index (inverted file)

Term-Document Matrix의 공간 상의 문제 해결을 위해 1인 문서만 목록화함.

검색 대상(문서, 웹, PC경로)에 따라 검색 결과가 다르기 때문에 Posting list에는 논리적으로 문서의 번호 식별자를 부여함.

Posting : 문서 번호 식별자 하나하나

Posting list : Posting이 나열된 하나의 배열(리스트)

Posting lists : Posting list의 집합

질의어를 찾을 때 더 빨리 찾을 수 있도록 문서를 정렬해야 하기 때문에, Posting list는 배열보다 연결 리스트를 선호한다. 하지만 포인터 공간을 더 차지한다.

Dictionary == Vocabulary (Term의 집합)

Inverted Index 만드는 과정

[단계]

1. Tokenization (토큰화)→ 만약, 문서가 TXT가 아닌 아래한글, html이라면? → 경우에 따라 토큰화 어려울 수 있음.1-2. Linguistic Modules를 통해 언어에 따라 처리함. (영어 : 모두 소문자로, 원형으로 만듦)어느 토큰이 어느 문서에서 나왔는지 Postings list(해당 토큰의 문서 위치를 나타냄) 구축1-3-1. (Term, DocID) 쌍으로 만듦.1-3-3. 필요 시, TF 정보 추가Term Frequency(TF) : 한 문서를 기준으로 Term이 나온 개수 추가

       Document Frequency(DF) : Term이 나온 문서의 개수 추가
   
       이때 Term Frequency끼리 합을 구함.
   

   DF로 합쳐진 중복 Term은 각각 연결 리스트 식으로 자신의 (DocID, TF)를 가리킴
2. → 나중에 연결 리스트 형식의 Inverted Index의 기틀이 됨.
3. 1-3-5. 필요 시, DF 정보 추가
4. 한 문서의 중복 Term은 하나로 통일.
5. 1-3-2. Term을 기준으로 정렬함.
6. Inverted Index를 만듦.
7. 1-3. Indexer : 토큰을 인덱스로 만듦.
8. Tokenizer 모듈을 통해 토큰화 함.
9. 1-1. 토큰화 : 문서들의 문장을 공백을 기준으로 자름

사람이 쓰는 단어는 한계가 있으므로 Dictionary size는 Postings list에 비해 변화가 적음.

따라서, Dictionary는 검색 서비스를 위해 Main Memory로 load 됨.

Postings는 크기가 점점 커지고 변화도 잦아 Disk에 저장됨.

Postings list 저장 방법

1. 연결 리스트
2. 가변 배열
3. hybrid scheme : 연결리스트 + 가변 배열 (배열을 연결리스트로 연결함.)

질의어

1. Conjunctive : AND시간복잡도 : 비교하는 Posting List 길이의 합if not sorting 시간복잡도 : 비교하는 Posting List 길이의 곱
2. 조건 : Posting list가 정렬되어 있어야 함.
3. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 다르면 작은 쪽의 Posting이 오른쪽으로 이동하고 다시 비교
4. Disjunctive : OR시간복잡도 : 비교하는 Posting List 길이의 합
5. Posting list끼리 첫 번째 인덱스부터 비교해서 문서 번호가 같으면 검색 결과에 포함하고, 달라도 문서 번호가 더 작은 쪽을 먼저 검색 결과에 포함하고 작은 쪽이 오른쪽으로 이동한다.
6. NOT → 시간 오래 걸림NOT이 붙은 Posting list는 오른쪽으로 넘어가기 전에, 자신에게 없는 Posting의 문서 번호와 다른 Posting list와 연산함.NOT이 붙은 Posting의 문서 번호가 NOT이 붙지 않은 Posting의 문서 번호와 다르면, 추가하지 않고 작은 쪽이 오른쪽으로 이동한다. 같으면 추가하지 않고 두 Posting 모두 오른쪽으로 이동한다.
7. <AND>
8. NOT이 붙은 단어가 검색 결과에 포함되면 안 됨.

WestLaw 시스템

질의어를 만들 때, AND, OR, NOT + /숫자, ! 가능함.

띄어쓰기 : OR

/<숫자> : <숫자> 단어 이내에 두 단어가 나올 때, AND

! : Wild-card 문자 *

/s : 한 문장 안에 두 단어가 둘 다 나와야 함. AND

/p : 한 문단 안에 두 단어가 둘 다 나와야 함. AND

Proximity operators : 인접성을 표시할 수 있는 연산 기호

연산 순서 최적화

1. 앞부터 처리
2. 순서 바꿔서 처리 → 시간 절약 가능OR 시간 복잡도 : Posting list size의 합
   1. Doc Freq가 작은 것부터 처리함.
   2. Posting list size == Doc Freq
   3. 연산 시 시간 복잡도를 최대로 계산해서 시간 복잡도가 작은 순서대로 처리함.
3. AND 시간 복잡도 : Posting list size의 합

인접조건

질의어의 단어가 띄어쓰기 단위로 끊어지면 안 되고 붙어있어야 할 때

Proximity 인접조건 명령어 : NEAR

구조화된 TEXT까지 생각해서 검색해보는 방법도 생각해보기(저자와 내용 구조가 맞는 검색)

Inverted Index + Position Information

Position Information : Posting이 해당 문서가 그 문서 내에서 어디에 나왔는지 위치 정보가 담긴 list를 가리킴

Position Information Size = Term Frequency

두 단어가 인접해 있는지 찾는 법 : AND 연산으로 각 문서에 해당 Term 나왔는지 검사 → 두 위치 정보를 비교함 → 인접 조건에 맞을 경우 결과에 포함

인접 차이 : 1이면 두 단어가 붙어있음을 의미하고, 2면 두 단어 사이에 한 단어가 포함되어 있음을 의미함.

Term Freq 활용

Term Freq가 큰 순으로 결과 제공하기

어떤 Term이 하나의 문서에서 Document에서 몇 번 나왔는지 고려

어떤 Posting의 Term Freq == 그 Posting의 Positional Information 리스트의 길이

검색 결과로, 각 문서의 Term Freq의 합이 큰 문서부터 제공함.

Ranking Search

Boolean 모델은 해당 질의어가 문서에 포함 됐는지 안 됐는지만 판단하기 때문에 Ranking을 매기는 건 원칙적으로는 불가능하다.

하지만, 기준을 적용해서 조금 더 유용할 만한 검색 결과를 제공할 수도 있다. Proximity 인접성을 이용해서 인접할 수록 사용자가 더 원하는 정보에 더 가까울 수 있으므로 가까운 순으로 제공하거나, 문서의 Term Freq를 이용해서 큰 순으로 제공하거나, 문서가 만들어진 시간을 인덱스에 부여해서 최근 문서부터 제공할 수 있긴 하다.

정보 검색 VS DB 검색

정보 검색

비구조화 됨

범위 검색 불가능

단, TEXT이더라고 약간의 구조가 있을 수 있음. Semi-Structured Data 예) PPT, XML

글자의 크기, 글자의 굵기와 같은 정보를 이용해 약간의 구조를 추가할 수 있음.

DB 검색

구조화됨.

범위 검색 가능

관련 있는 Concept 검색 : 아직 불가능

용어

Clustering : 군집(모으기)

Classfication : 분류

웹 검색

다양한 문서, 다양한 사람, 질의어, 정보 존재함.

링크된 정보 활용하거나 클릭한 정보 활용 가능함.

Cross-language information retrieval : 교차 언어, 번역해서 검색 결과 제공

Question answering : 질의 응답 시스템 질문&답변

Summarization : 검색결과 요약해서 제공

TEXT mining : TEXT에서 필요한 정보 뽑아서 알려줌