정보 검색 중간고사

유의사항

• 시험 전에 강의자료 훑으면서 편하게 작성한 거라 보기 좋은 정리는 아님. 복습을 위한 자료지 예습이나 학습을 위한 자료는 전혀 아님.
• 6주차 수업에 결석해서 강의자료 번역했음. 6주차 내용은 내 필기 아님.

2주

이번 학기 공부 대상 : 텍스트 검색

유닉스 명령어 grep : 원하는 것을 찾을 수 있긴 한데 정보 검색용으로 있는 명령어는 아님

• 특정 단어가 존재하거나, 존재하지 않는 파일 검색 가능
• 대규모 파일 처리 느림
• 없는 단어 찾기 어려움 : 전수조사 필요
• “~와 가까운 ~” 같은 상세조건 불가
• 적절한 결과순 랭킹 불가
• * : 모든 파일 중에서 찾기
• | : 이 기호 앞에 있는 명령을 먼저 수행하고, 그 결과에 대해 다음 명령을 수행
• -v : NOT

term-doc matrix : term과 doc의 관계를 나타낸 행렬

• 행에는 모든 term 나열, 열에는 모든 doc 나열, 각 term과 doc에 대해 해당 doc에 term 등장 여부 표시
• 문서가 많을수록 행렬이 커짐
• 비트 단위 연산으로 간단히 결과 도출 가능

정보 검색의 기본적인 전제 : 문서의 집합은 고정되어 있다(비현실적이지만 설명 편의상 전제함)

정밀도와 재현율 : 통합본 13페이지, 2주차 13페이지
정밀도 : 검색 결과 중 제대로 검색한 것
재현율 : 원래 원했던 결과 중 찾아낸 것
F-measure : 가중치(α)를 준 정밀도(P)와 재현율(R)의 조화평균. 식은 1/(α * 1/P + (1 - α) * 1/R), 보통 가중치는 0.5로 주고 이를 정리하면 2PR/(P+R)이 됨.

inverted index : 각 단어마다 그것이 등장하는 문서만 표시한 인덱스. 단어를 헤드노드로 하는 연결 리스트로 만든다. 정렬된 게 쓰기 좋다.

• 토큰화 과정 : 모든 문서를 검사해 (단어, 등장 문서) 투플을 만들고, 단어를 기준으로 정렬하고, 중복된 단어에 대해 투플을 통합한다. 문서당 빈도를 표시할 수도 있다.
  결과는 사전과 포스팅 리스트로 나누어진다.

사전은 상대적으로 크기가 작으므로 보통 메인 메모리에 저장하고 포스팅은 디스크에 저장한다. 포스팅 리스트는 연결 리스트로 만든다.
비교해야 할 두 단어의 포스팅 리스트 길이가 각각 x, y라고 할 때, AND 연산의 시간 복잡도는 O(x + y)이다. 이때 리스트는 정렬되어 있어야 한다.
여러 단어에 대해 논리 연산을 해야 할 경우 연산 순서를 바꾸면 연산 시간을 줄일 수도 있다. 포스팅 리스트(doc-freq) 길이가 짧은 것부터 먼저 연산하면 된다. OR 연산의 결과의 길이는 최대 두 포스팅 리스트의 합과 으므로 AND 연산과 섞여있다면 최댓값으로 가정하고 순서를 정한다.

위의 inverted index가 불가능한 기능 : 구 검색, “가까운” 단어 검색, 검색할 정보의 zone 지정하기

“가까운” 단어 검색 : 포스팅 리스트에 있는 각 문서별로 등장 페이지 리스트를 따로 붙이면 계산 가능
검색 결과 정렬에는 term-freq를 활용할 수 있으나 신뢰도는 보장할 수 없음 → boolean 모델에서 원칙적으로 결과 랭킹은 불가하지만 가능은 함

텍스트 검색은 범위(부등호) 검색 불가능

군집과 분류 : 통합본 46페이지, 2주차 46페이지
군집 : 선묶음 후기준, 총 묶음 개수를 미리 알 수 없음
분류 : 선기준 후묶음, 묶음 개수가 한정됨

3주

문서 토큰화 이전에 할 일 : 문서 종류 파악, 언어 파악(코드 변환이 필요할 수 있음) → 기계가 하거나, 사람이 하거나
한 문서가 여러 언어로 쓰인 경우, 한 문서가 여러 파일/언어로 구성된 경우 있을 수 있음

토큰화
토큰화 : 문서를 단어 단위로 나누는 것, 정규화 이후 진행함, 불용어 사용. 기본적으로는 공백 단위로 나누고 문장부호 삭제하는데, 고유명사에 문장부호가 들어가는 등의 경우는 어떤 방식을 쓰든 문서와 질의어를 똑같이 전처리하면 된다.

어려운 점 : 하이픈의 용도가 다양해서 처리 방법을 하나로 정할 수 없음, 하이픈이 들어간 구는 더 어려움
문제점 : 날짜, IP주소, 이메일 등 기호/공백이 있지만 분리하면 안되는 토큰 → 무시하기엔 너무 유용하고 토큰 넣기엔 너무 많은데 → 사전을 늘리기로 결정

토큰화 언어 식별 : 숫자로 된 코드만 보고 한글인지 영어인지 맞혀야 함. 영어에 없는 조합이면 한국어고, 한국어에 없는 조합이면 영어라고 판단하는 방식으로 식별함.

불용어
불용어 : 빈번하게 나오지만 별로 중요하지 않은 말, 기능어(반대 : 내용어).
전체 텍스트의 약 30% 차지, 사전 크기는 별로 줄지 않지만 포스팅 리스트는 많이 줄일 수 있다.
문장이 너무 짧은 경우 불용어가 문장의 대부분을 차지해 문장의 내용이 상당히 소실되는 문제가 있어 불용어가 줄어들고 있으나, 요즘은 압축 기술이 좋아 포스팅 리스트 저장 비용이 감소했고, 질의어를 잘 최적화하면 된다(기능어에 가중치 적게 주기).

정규화
정규화 : 다르게 표기하지만 실상은 다 같은 단어를 하나의 단어로 통합하는 것. 기호를 없애는 것도 방법.
Thesaurus : 유의어/반의어 사전. 동의어나 동음이의어를 다룰 수 있으며 이 사전이 없으면 수작업을 해야 함.
정규화를 할 경우 질의어도 똑같이 정규화해서 검색해야 한다.

• 단어를 하나의 클래스로 통합해 인덱스를 합치는 방법이 있고
• 하나의 클래스에 속하는 단어마다 모두 통합된 똑같은 인덱스를 주는 방법이 있고 → 메모리를 손해보지만 질의어를 정규화할 필요가 없어 검색이 빨라짐
• 각 단어별 인덱스는 따로 만들고 질의어를 확장하는 방법 → 오래걸림

Stemming
재현율(recall) 높이기 위해 단어에서 접사 떼고 어근만 남기기
정확할 필요 없고 적당히 자르면 됨. sess → ss 등 규칙 있음.
질의어도 똑같이 처리해야 함

Lemmatization
형태소 분석. 엄격하게 실제 단어만 남기고 어근/조사/접사 다 떼기

• 스테밍과 레마티제이션 비교 : 후자가 더 좋아보이지만 실상 별 차이 없다고 함

스킵 포인터
인덱싱할 때 만듦. 검색하기 위한 비교 횟수 감소 기능.
스킵 포인트가 많으면 스킵 기회도 많지만 스킵 거리가 짧고 메모리 더 필요
스킵 포인트가 적으면 스킵 기회는 적지만 스킵 거리가 긺.

구 검색

1. biword index : 모든 조합의 두 단어 구(인접한 것만) 인덱스 만들기
   사전이 매우 커지지만 두 단어 구 즉시 검색 가능
   긴 구 질의 - 여러 개의 두 단어 구로 나눠 검색, 검색이 되긴 되지만 꼭 모든 단어가 질의처럼 붙어서 나온다는 보장이 없어 위양성(false positive) 존재
   표준적인 해결책이 아님
2. positional index 등장 위치 인덱스 : 단어에 달린 포스팅 리스트의 각 포스트마다 해당 단어가 어디서 등장하는지 인덱스 기록. 사전은 그대로이고 인덱스 사이즈 커짐.
   두 단어 구 검색 - 두 단어 동시 등장 문서 찾기, 동시 등장 문서 중 인접한 위치 찾기
   구가 얼마나 길든 검색 가능, 단어 간 거리 지정 검색 가능 ← biword는 불가능
3. 혼합 방식 : 자주 검색되는 특정 구에 대해 biword 인덱스 만들기
   사람들이 검색한 기록인 로그 데이터(자산이 되기 때문에 함부로 버리면 안됨)를 이용해 자주 검색되는 구를 알아내 biword 인덱스 생성

4주

사전을 저장하는 자료구조 - 주로 두 가지 방법 : 해시테이블과 트리

해시 테이블
해시 함수에 문자열을 입력으로 주면 함수 계산을 해서 나오는 값을 인덱스로 삼아 데이터를 저장, 해시 함수를 잘 만들어야 효율적으로 저장할 수 있다.
탐색 속도가 아주 빠르지만 해시 함수에 따라 저장 공간이 중복되는 단어(충돌)가 생길 수 있다 → 충돌한 자리에 연결 리스트 생성
장점 : 서치가 O(1)
단점 : 비슷한 단어 찾기 어려움(해시 값이 전혀 다름), 와일드카드 불가, 사전이 점점 커지면서 해시테이블의 크기를 바꾸면 해시함수도 바뀌고 사전 전체를 다시 해싱해야 한다

트리 - 이진 트리
장점 : 비슷한 단어 찾을 수 있음, 와일드카드 가능
단점 : 서치 느림 O(logn), 효율적이려면 균형 트리 만들어야 함(루트를 잘 골라야 하고 정렬된 데이터 넣으면 skewed), 트리를 수정하다 보면 균형 깨질 수 있음(→ 재정렬 필요) → 재정렬 피하기 위해 B트리 사용

트리 - B트리
자식 노드의 수가 a~b개 사이를 유지하는 트리

와일드카드 쿼리
lexicon : 사전
B트리를 쓰면 와일드카드 질의를 다루기 쉽다
결과는 검색된 단어들을 전부 검색(문서 검색이 목적이니까)

• 와일드카드가 앞에 나오면? *mon
  거꾸로 된 B트리(단어를 거꾸로 쓴 것)가 하나 더 필요하다
  역B트리로 nom* 검색
• 중간에 와일드카드가 들어간 경우 pro*cent
  반으로 나눠서 따로 검색하고 결과 합치기, 그 결과로 나온 단어로 다시 문서 검색
  문제 : 검색 결과 합치는 연산이 너무 오래 걸림 → permuterm index로 시간이 덜 걸리는 대신 메모리를 더 씀

permuterm index
단어에 $를 붙이고 회전시킴, 이 회전을 permute라고 함.
변형된 단어를 모두 사전에 저장하고 원본 단어를 가리키는 포인터를 둠.
기본 와일드카드 검색은 질의어 끝에 $를 붙이고 단어를 회전시켜 *이 마지막에 나오게 만듦.
와일드카드가 여러 개 있으면 $를 붙인 상태에서 우선 그 와일드카드 중 하나가 단어 맨 뒤로 가게 만들어 앞에서부터 와일드카드 단위로 잘라서 검색
단점 : 사전이 많이 커진다. 영어로 실험 결과 사전이 10배 정도 커지지만 AND 연산보다는 감수할만 하다고 함.

k-gram
보통 n그램이라고 많이 씀. k개의 연속된 시퀀스(글자, 단어 등)를 말함. $로 단어의 시작과 끝을 표시.
1-gram : unigram, 2-gram : bigram, 3-gram : trigram, n-gram : ngram. 주로 2그램, 3그램 씀.

k-gram index
모든 k그램을 사전에 저장
각 k그램은 해당 k그램을 포함하는 단어를 전부 가리킴, 사전순 정렬
3그램이 2그램보다 단어 종류가 많지만(메모리 손해) 효율도 더 좋음
permuterm 인덱스보다 메모리는 효율적(중복이 많아서 사전이 덜 큼), 속도는 비교하기 어려움
문제 : 와일드카드 검색어에 따라 올바르지 않은 결과가 섞일 수 있다 → 검색 후 필터링하면 됨

철자 고쳐주기

• 단어 고쳐주기
  1. 단어만 고려하기(문맥 X)
  2. 문맥 고려해서 고쳐주기(시간이 좀 더 오래 걸림)
• 문서 고쳐주기
  이미지 → 텍스트 변환한 문서의 오타 고치기. 문자 인식 오타와 타자 오타는 양상이 다름.

멋대로 고쳐서 검색하지 말고 사용자에게 제안하기

사용자의 검색어와 비슷한 단어 찾기 : 만약 고친 단어 후보 중 동점이 나와서 결정이 안 되면 단어 사용 횟수/검색 빈도 고려. 어떻게 가장 비슷한 단어를 정하나? → 편집 거리, k그램 오버랩

전제 : 정확한 단어의 사전이 있다 → 사전에서 질의어와 비슷하게 생긴 단어를 찾음

편집 거리
단어를 고치려면 몇 번이나 편집해야 하는지
기본적으로 삽입과 삭제만을 고려하고, ‘대체’도 포함할지는 상황에 따라 다름.
가로로는 올바른 단어를 쓰고, 세로로는 잘못 쓴 단어를 써서 각 글자를 연결해 격자를 만든다. 격자의 왼쪽 위에서부터 오른쪽 아래로 가는 최단경로가 편집 거리. 아래로 가는 방향은 글자 삭제를 의미하고 오른쪽으로 가는 방향은 글자 삽입을 의미함. 서로 겹치는 글자가 만나는 격자에는 대각선을 그어 카운트하지 않고 넘어가게 한다.

편집 거리가 특정 값보다 작은 것만 대체 단어로 제안하도록 하면 제안할 대상을 줄일 수 있다.

k그램 오버랩
질의어를 이용해 k그램 검색을 하여 질의어가 갖는 k그램을 마찬가지로 갖는 단어들을 찾되, 질의어는 틀린 단어이기 때문에 그대로 검색하면 안된다. threshold를 정해서 이 값을 넘기는 것을 후보로 포함한다.
k그램 오버랩으로 골라낸 단어만 가지고 편집 거리 계산
문제 : 단어가 너무 길어서 k그램이 많이 겹쳤을 뿐인 사례. 정규화는 어떻게 할 수 있는지.

k그램 오버랩 : 두 집합이 얼마나 겹치는지 계산. 교집합 크기 / 합집합 크기. 각 집합의 요소는 해당 단어의 k그램.

문맥 고려 단어 고치기
모든 단어가 틀렸다고 전제하고 교정 후보 찾아 조합하기 → 그 조합 중 가장 많이 나온 것으로 제안(말뭉치에 단어 3그램 미리 준비)
이 방법은 정말 오래걸리니까 수상할 정도로 검색 결과가 적을 때만 사용

5주

인덱스 만들기

하드웨어 기초
메인 메모리 접근 시간 < 하드 접근 시간
디스크 탐색 시간 : 헤드가 원하는 트랙과 섹터로 이동하는 시간
IO는 블록 단위로. 컴퓨터마다 다르지만 보통 한 블록은 8~64kb

압축하지 않은 데이터 읽는 시간 > 압축한 데이터 읽고 압축 푸는 시간 → 요즘은 이게 더 빠름

Fault tolerance : 기계적인 결함이 발생해도 시스템을 계속 사용할 수 있는 시스템(예: CPU가 여러 개 있어서 하나가 죽어도 계속 작동함)
비싼 컴퓨터 하나 쓰는 것보다 싼 컴퓨터 여러 대 묶어서 쓰는 게 저렴하고 낫다.

로이터 RCV1
로이터의 1년치 뉴스기사로 만든 말뭉치, 다양한 토픽 존재함.
스케일에 상관 없이 먹히는 인덱스 구축 알고리즘을 적용하는 예시로 사용.

토큰 당 평균 바이트 수는 4.5, term당 평균 바이트 수는 7.5인데 이 차이는 불용어 유무 때문에 생김. 보통 불용어는 짧고 많기 때문에 이것이 빠진 term의 평균 길이가 길어짐.

인덱스 만들기
정렬 기반 인덱스는 scalable한가? → 그닥
scalable 인덱스 세 가지 : BSBI, SPIMI, distributed 인덱싱

정렬 기반 인덱스
문서로부터 단어와 등장 문서의 쌍 생성
모든 쌍을 정렬하고 포스팅 리스트 구축 ← 단어를 ID로 바꿔서 정렬하면 문자열 비교보다 쉽지만 각 단어의 ID를 저장한 테이블이 따로 필요하다. 단어와 문서의 ID는 int라고 가정.
이 방법은 스케일이 커지면 메인메모리 용량 문제로 사용 불가
메인메모리를 사용하지 않는다면 시간이 너무 오래 걸려서 사용 불가

BSBI
블록 단위 정렬 후 인덱스 통합

1. 블록 단위 인덱스 정렬
2. 같은 단어끼리 등장 문서 합치기
3. 토너먼트식으로 다른 블록과 인덱스 합치기

전체 정렬과 다른 점 : 각 블록들을 합칠수록 블록의 크기는 커지지만 어차피 합칠 때는 블록 전체가 메모리에 있을 필요가 없으니 scalable한 방법이 맞다.
모든 블록을 한 번에 조금씩 잘라서 합치는 방법도 있다 : 토너먼트식 병합보다 빠르지만 각 블록이 모두 파일이기 때문에 한번에 다수의 파일을 열어두어야 하는데, 한번에 열어둘 수 있는 파일의 수가 제한적이기 때문에 한계 있음.
문제 : 단어에 ID를 부여하면 메인메모리에 사전과 테이블이 동시에 올라가야 하는데 이건 용량이 너무 커지고, ID를 부여하지 않으면 인덱싱이 오래걸림

SPIMI
정렬하지 말고 해싱하자. 블록 단위로 만들고 합치자.
합칠 때는 사전만 정렬함 → 위에서부터 투포인터 탐색하면서 겹치는 것 찾아 합쳐야 하기 때문

distributed 인덱싱
웹 스케일의 인덱싱은 컴퓨터 한 대로는 부족하다.
각각의 컴퓨터는 문제가 발생할 가능성이 있다.
고로 몇 대의 컴퓨터에 인덱스를 나눠 저장한다.
예 : 구글 데이터 센터

MapReduce : 분산 컴퓨팅의 일반적인 아키텍처
분산되는 각 작업들(스플릿)은 한번에 빠르게 처리할 수 있는 크기로.
파서와 인버터
파서 : 스플릿들(분류되지 않은 단어와 등장 문서 쌍)을 읽고 세그먼트 파일(알파벳 순으로 여러 개의 파티션으로 나눈 세그먼트)에 분류한다. 각 파서마다 세그먼트 파일이 한묶음씩 나온다. 파서의 수는 스플릿의 수와 같고, 물리적 컴퓨터의 수와는 다를 수 있다.
인버터 : 파서마다 나온 세그먼트 파일들 중 특정 세그먼트만을 모두 읽고 합펴 인버티드 인덱스를 만든다. 인버터의 수는 세그먼트의 수와 같다.
마스터가 위의 작업을 모두 감독하고 배치한다.

한 대의 컴퓨터에서 파서와 인버터가 동시에 돌아갈 수 있다. 파서와 인버터는 프로그램이다.

term 파티션 인덱싱 : 단어를 기준으로 파티션을 나누었기 때문에 사람들이 특정 단어를 많이 검색하면 특정 파티션을 맡은 컴퓨터에 부담이 몰린다.
doc 파티션 인덱싱 : 모든 컴퓨터가 단어는 전부 갖고 있지만 포스팅 리스트를 나눠 가진다. 어떤 단어를 검색하면 모든 컴퓨터가 해당 단어를 검색하고 합쳐야 하지만 각자 가진 인덱스가 적기 때문에 빠르다.

다이나믹 인덱싱
가장 간단한 접근 : 하나의 큰 메인 인덱스와 새 문서에 대한 정보를 저장하는 작은 임시 인덱스를 가지며 주기적으로 통합한다. 없어진 문서에 대한 정보는 따로 갖고 있다가 검색 결과에서 제외한다.
문제 : 메인 인덱스가 너무 커서 메인 인덱스와 서브 인덱스를 통합하는 동안 서치 엔진 사용이 불편해지는데, 통합을 자주 한다.

로가리즘 병합

1. 보조 인덱스가 생긴다. 일정 이상 커지면 메모리에 쓴다.
2. 또 보조 인덱스가 디스크에 입력된다.
3. 같은 크기의 보조 인덱스를 합친다.
4. 반복한다.

요약 : 인덱스 2048
특징 : 병합을 단계적으로 하기 때문에 효율적이다. 질의어를 처리할 때 모든 인덱스 파티션을 확인해야 하므로 질의 처리 속도는 좀 떨어진다.
로가리즘을 계속 하면 인덱스 파티션이 점점 많아져서 쿼리 처리가 느려지니까 주기적으로 통합해야 한다.

6주

인덱스 압축

무손실 압축 : 모든 정보가 보존됨
손실 압축 : 일부 정보가 버려짐. 버려진 정보는 별로 중요하지 않음. 대신 압축률이 좋음.
몇 가지 전처리 단계는 손실 압축으로 보일 수 있다

단어 수 추정하기
종종 언어는 특정 크기의 사전을 갖는다고 본다.
대규모 컬렉션의 어휘는 훨씬 크다 : 인명, 지명, 학술용어 포함. 이들은 인버티드 인덱스에 들어가야 한다.

힙의 법칙
모음 크기의 함수로 어휘 크기를 추정한다.
M은 어휘 사이즈, T는 컬렉션에 있는 토큰 수로 정해지는 컬렉션 사이즈, 보통 30 ≤ k ≤ 100, b는 0.5쯤. k는 컬렉션 자체와 그것의 전처리 과정에 영향을 받는다. 케이스 폴딩(모든 문자를 소문자로 바꾸는 정규화)과 스테밍은 k를 줄이고 숫자와 오타를 사전에 포함하는 것은 k를 증가시킨다.
공식은 M = kT^b
로그를 취하면 M과 T는 선형 관계이다.
log M = b log T + log k

가정 : 사전은 충분히 크고, 계속 커진다(최대 단어 수 제한 없음).
고로 효율적인 정보 검색 시스템을 위해 사전 압축은 반드시 필요하다.

zipf의 법칙
보통 자연어에는 아주 흔한 소수의 단어가 있고, 아주 다양한 희소 단어가 있다.
단어의 등장 빈도를 컬렉션의 랭크 함수로 나타낼 수 있다.
f_i = c/i, log f_i = log c - log i
f_i는 i번째로 흔한 단어의 빈도이고 c는 정규화 상수다.

인덱스 압축

1. 사전의 크기를 고려한다. 메인메모리에 둘 수 있을 만큼 작게 만들어야 한다.
2. 포스팅을 위한 공간. 디스크 공간을 줄일수록 디스크에서 읽어들이는 시간이 줄어든다. 큰 서치 엔진은 포스팅의 중요한 부분을 메인 메모리에 둔다.
3. 각 포스팅은 docID라고 가정한다. 빈도와 등장 위치는 고려하지 않는다.

• 사전 압축
• 포스팅 압축
• 허프만 코드

사전을 압축하는 이유

• 빠른 질의 처리를 위해 사전을 메모리에 보관(또는 사전의 상당 부분 이상)
• 빠른 시작 시간을 위해
• 다른 응용 프로그램과 메모리를 공유하려면(특히 엔터프라이즈 검색 엔진)

사전을 위한 자료구조
너비가 고정된 배열
단어 당 20바이트, 문서 빈도와 포스팅 리스트에 각각 4바이트. RCV1 기준 40만 단어 * term 당 28바이트 = 11.2MB
term에 20바이트를 할당했는데, 실제 term 당 평균 바이트는 7.5이므로 용량 낭비가 있고, 일부 너무 긴 단어는 잘릴 수 있음.

스트링 압축
사전을 하나의 긴 문자열로 저장
다음 단어로의 포인터는 현재 단어의 끝을 나타낸다.
주소 공간 : 40만 단어 * term 당 8바이트 = 3.2MB
포인터는 log₂ 3.2M = 22bits = 3바이트

사전을 문자열로 저장했을 때 공간
문서 등장 빈도에 4바이트, 포스팅 리스트 포인터에 4바이트,
term 포인터에 3바이트, term에 8바이트 → term 당 평균 11바이트가 됨. 아까는 20바이트였음.
40만 단어 * 단어 당 19바이트 = 7.6MB
너비가 고정된 배열이 11.2MB였던 것에 비해 32% 절약

블록 저장
단어들을 사이즈가 k인 블록에 문자열로 저장
단어 포인터는 블록 당 첫 단어에만 할당
단어의 길이를 저장해야 하기 때문에 각 단어의 시작부분에 추가 바이트 필요
k 단어 블록 당 2k-3 바이트 절약
k가 4일 때, 4 단어 블록 당 5바이트 절약
k가 4일 때 40만 단어 / 4 * 5 = 0.5MB, 사전 사이즈는 7.1MB로 감소. 고정 너비 배열에 비해 37% 절약

k가 클수록 사전은 더 압축되지만 서치가 느려짐. 각 블록의 첫 단어에서부터 선형 탐색을 해야 하기 때문.

front coding
정렬된 단어들은 보통 동일한 prefix를 갖는다. 그러니 이들의 차이나는 부분만 저장한다.
예)
8 automata 8 automate 9 automatic 10 automation
8 automat* a 1◊e 2◊ic 3◊ion
*은 한 어근의 끝, * 뒤에 나오는 숫자는 어근 뒤에 붙는 추가 글자의 수

블록 저장과 프론트 코딩을 병행하면 5.9MB 됨.

포스팅 리스트 압축
포스팅 파일이 사전보다 훨씬 크다.
이 예제의 포스팅은 빈도와 위치 정보를 제외하고 단순히 docID이다.

포스팅 파일의 공간 요구 사항은 250MB이다.
우리의 목표는 각 포스팅을 docID 당 20비트 미만으로 압축하여 저장하는 것이다.

키 아이디어

• 절대적인 docID 대신, 우리는 포스팅 파일에서 두 개의 인접한 docID의 차이를 사용합니다.
• 자주 나오는 포스팅들이 서로 가까이 붙어 있다는 게 우리의 관측이다.
• 따라서 차이 또는 간격은 더 적은 공간으로 나타낼 수 있습니다.

포스팅 리스트에 각 문서의 ID를 그대로 적는 대신 앞 문서와의 ID 차를 적는다.
희망 사항 : 대부분의 차이는 20비트보다 훨씬 적은 것으로 표현될 수 있으면 좋겠다.

the와 같은 단어는 거의 모든 문서마다 나온다. → 포스팅 당 20비트는 너무 낭비다. 1비트만 있어도 된다.
어떤 단어는 백만 문서에 한 번 나온다. 이건 20비트로 나타내야 한다.
결론 : 가변 바이트 인코딩 필요

가변 바이트 인코딩
목표

• 모든 갭을 필요한 만큼 적은 비트로 인코딩합니다.
• 가변 바이트 인코딩은 작은 숫자에 짧은 바이트 코드를 사용함으로써 이 목표를 달성한다.

1. 간격 G를 저장하기 위해 1바이트로 시작하고 연속 비트 c로 사용할 수 있도록 1비트를 할당한다.
2. G ≤ 127일 경우, 7개의 사용 가능한 비트로 인코딩하고 c = 1로 설정한다.
3. 그렇지 않으면 G의 하위 7비트를 인코딩한 다음 추가 바이트를 사용하여 동일한 알고리즘을 사용하여 상위 비트를 인코딩한다.
4. 마지막 바이트의 연속 비트를 1(c = 1)로 설정합니다. 다른 바이트의 연속 비트가 0(c = 0)으로 설정됩니다.

다른 가변 길이 코드
바이트 대신 다른 정렬 단위를 사용할 수도 있습니다. : 32비트(word), 16비트, 4비트(nibbles)
가변 바이트 코드는 작은 공백이 많은 경우 공간을 낭비한다.

• 그런 경우에는 nibbles(4비트)가 더 낫다.

인덱스 압축 요점
이제 매우 공간 효율적인 부울 검색을 위한 인덱스를 만들 수 있습니다.

• 컬렉션의 전체 텍스트 크기 중 13%만
  • RCV1 컬렉션의 경우 960MB, VB 인코딩 포스팅의 경우 116MB
• 하지만, 우리는 위치 정보를 무시했습니다.
  • 따라서 실제로 사용되는 인덱스의 경우 공간 절약이 더 적습니다.
  • 하지만 기술은 실질적으로 동일합니다.

허프만 코드

• 1950년대에 David Huffman에 의해 개발되었다.
• 문자 또는 단어의 빈도 분포 사용
• 가변길이코드
  • 더 빈번한 기호에는 더 짧은 코드가 할당됩니다.
• prefix 속성을 가지고 있습니다.
  • 어떤 코드도 다른 코드의 접두사가 아니다.
  • 임의의 비트 스트림은 주어진 허프만 코드로 고유하게 디코딩할 수 있다.
  • 전송 오류는 거의 항상 자동으로 걸러집니다.

허프만 코드 인코딩

• 말뭉치에서 문자(또는 단어) 빈도를 수집합니다.
• 빈도 분포에 따라 이진 트리인 허프만 트리를 만듭니다.
• 트리에서 허프만 코드 테이블을 얻을 수 있습니다. ← 왼쪽 서브트리로 가면 0, 오른쪽 서브트리로 가면 1을 부여하고 루트에서 각 글자인 리프까지 가는 경로를 각 글자의 코드로 정함.
• 표를 사용하여 각 문자(또는 단어)를 허프만 코드로 인코딩합니다.

허프만 코드 디코딩

• 인코딩에 사용된 것과 동일한 Huffman 트리를 사용합니다.
• 허프만 트리의 루트에서 리프에 닿을 때까지 아래로 가로지른다.
• 각 문자(또는 단어)는 리프에서 해독된다.
• 전송 오류는 코드를 따라 해독했을 때 매치되는 글자가 없기 때문에 거의 항상 자동으로 걸러집니다.

7주

1주-6주까지 배운 불린 모델의 문제점 : 검색 결과가 너무 많은 경우가 있고, 검색 결과의 랭킹이 없음

검색 결과에 점수 매기기의 기본
보통 0-1 사이 실수로 점수를 매김

쿼리-문서 매칭 스코어
문서에 질의어가 자주 나올수록 높은 점수 부여

불린 모델에서 점수를 매기는 방법
자카드 계수
교집합 / 합집합
0과 1 사이의 값을 가짐. 완전히 포개질 때만 1.
문제 : 문서 내에서의 단어 등장 빈도(해당 문서 내에서 아주 중요한 단어)와 문서들에 등장하는 빈도(어디에나 나와서 별로 안 중요한 단어)를 반영하지 못함

파라미터와 존 인덱스
문서 본문 이외 추가 정보 반영. 저자, 제목, 출판 일자 등.
parametric index : 특정 범위로 제한된 값만 들어가는 인덱스. 예를 들어 출판 연도라면 2022 이하의 숫자만 가능.

기본적인 존 인덱스는 한 단어에 대해 abstract 인덱스 따로, 제목 인덱스 따로, 작가 인덱스 따로 만들지만 인코디드 존 인덱스는 저걸 모두 합침. 단어 → 2.저자.제목 → 3.저자 → 4.제목 이런 식으로. 이렇게 하면 사이즈가 줄어드는 대신 검색 시간이 늘어남.

가중치 존 스코어링
g_i는 가중치, S_i는 점수
한 질의어에 대한 한 문서의 점수는 가중치와 점수의 곱의 합
모든 가중치의 합은 보통 1이 되게 맞춤
가중치는 제목, 저자, 본문 등 존에 부여함.

좀 더 객관적인 가중치를 만들기 위해 기계학습을 사용할 수 있음
한 질의어와 한 문서가 관계가 있는지 없는지 사람이 먼저 판별해 표시하고 이 표시에 맞추어 학습시킴. 오차는 정답과 예측값의 차의 제곱을 사용. 오차의 총합을 줄이는 방향으로 학습.

벡터 공간 모델
term-doc 매트릭스의 각 줄을 벡터라고 보면 됨. 등장 여부 대신 등장 빈도 표시.

bag of words 모델
벡터는 단어의 등장 순서를 반영할 수 없다.
불린 모델에 비하면 일 보 후퇴한 부분이지만 rank를 사용하기 위해 감수한다.

단어 등장 빈도 tf
tf_t,d는 문서 d에서 단어 t가 등장한 횟수를 의미한다. 그러나 그냥 사용하지는 않고 log tf를 사용한다.

문서 등장 빈도 df
불용어나 흔히 쓰이는 단어보다 드물게 등장하는 단어가 가치가 높다.
그러니 너무 흔한 단어는 양수 가중치를 주되 다른 가치있는 단어보다는 낮게 주고 싶다.
df는 항상 모든 문서의 수보다 같거나 작고, 단어의 정보량을 파악하는 척도이다.

역 문서 등장 빈도 idf
t는 단어이고 N은 모든 문서의 수
idf_t = log N/df_t

로그 tf 가중치
만약 tf가 0보다 크다면 1 + log tf, 그렇지 않다면 0으로 한다.

tf-idf 가중치
tf와 idf가 모두 0보다 클 때 가중치 w는 로그 tf 가중치와 idf의 곱이다.

한 문서에 대해 모든 단어의 tf-idf 가중치를 나열한 것이 벡터가 된다.

벡터 거리
벡터 거리가 가까울수록 관계 있는 문서라고 판단
벡터 거리는 각도로 정한다. 코사인이 0도부터 90도 사이에서 단조감소하기때문에 코사인 값을 사용한다. 1에 가까울수록 각도가 작고, 두 벡터가 유사하다.

두 벡터의 각도 차에 대한 코사인 값은 두 벡터의 내적과 두 벡터의 크기의 곱을 나눈 값과 같다.
벡터 내적은 같은 자리의 성분을 서로 곱하고 모든 값을 더하면 된다.

코사인 유사도
코사인 유사도는 문서와 문서 사이의 유사도 검사 가능. 1에 가까울수록 두 문서가 유사하다고 볼 수 있다.
문제 : 단어의 순서를 고려하지 못함 → 같은 단어 구성 다른 의미 고려 불가