[정보 검색] 5. Index Compression

 

2. Compression

Why?

• 적은 디스크 용량=>비용 절약
• 메모리 절약=>속도 향상
• 디스크->메모리간 데이터 전송 속도 향상
• 단, 압축해제 알고리즘도 꽤 속도가 있어야함.(이게 느리면 의미가 없다)

 

왜 정보 검색에서?

• dictionary 고려- 메인메모리 사용을 줄일 수 있음
• posting-디스크 필요 공간 줄이고, 디스크를 읽는 시간도 줄임.

 

Lossy와 lossless

- Lossy는 손실이 있지만 많이 압축됨

- lossless는 손실이 없음.

 

 

3. Term statistics

term vocabulary의 크기는 얼마?

(모든 웹페이지를 인덱싱하려 할 때에 collection의 크기는?)

length 20에 최소 70^20(약 10의 37승)개의 다른 words가 존재.

Heap's law: M = kT^b

• M: vocabulary의 size
• T: token의 수
• k: 30~100 정도의 상수
• b: 약 0.5

이 수식을 약간 변형하면(log 스케일)

logM = logk + blogT로 변형되고, 이것을 y=logM, x=logT로 치환하면

y=bx+c의 1차방정식으로 볼 수 있다.

 

Zipf's law

어휘가 증가하는 것에 대한 특성.(빈도 높은 term-빈도 낮은 term)

cfi는 1/i에 비례.

• i는 몇번쨰로 많이 나오는지(순서)
• cfi는 i번째 많이 나오는 것의 빈도.
• 이것을 cfi = ci^k(k=-1)로 바꿀 수 있고, 
• 다시 log cfi = log c + k log i로 바꿀 수 있다.(c: cf1)

 

4. Dictionary compression

dictionary는 posting에 비해 용량이 작음=>메모리 적재 가능

 

fixed-width entry는

term에 20+빈도에 4+posting에 4

총 28byte * 400,000(term 갯수) = 11.2MB를 사용한다.

 

but. term은 평균 8글자(=8byte)이므로 term당 평균 12바이트가 낭비됨.

 

Dictionary as a string은 

term 대신 term string으로 포인팅하는 포인터를 추가.

포인터 3byte, term string에 8byte 할당

4+4+3+8로 19byte * 400,000 = 7.6MB를 사용하게 된다.

 

Dictionary as a string with blocking은

위 방법에서 포인터쪽에서 모든 글자를 가져오지 않고,

term string의 각 term 앞에 글자 개수가 삽입된다.

term string은 늘어나지만, 포인터는 줄어든다.

예시)

block size k = 4라고 가정하면

blocking 없이는 4*3 byte가 포인터로 사용되는데

blocking을 사용하면 포인터당 3byte로 줄고 대신 각 term당 4byte가 늘어난다.(글자 한개를 삽입하므로)

그리하여 block당 5바이트(이전 12, 현 3+4)를 절약할 수 있다.

7.6MB에서 7.1MB로 감소된다.

tree 형태로 비교하면 더 쉽다.

 

 

Front coding

단어끼리 중복되는 부분이 꽤 있다.

ex. -tive/tivly/-tion/-tional/-te 형태로 뒤에만 달라지는.

공통되는 그 앞부분을 묶고, 뒤에 마름모 기호를 통해 불러온다.

숫자는 이전이랑 동일하지만, 뒷부분은 기호를 제외한 글자 만큼 샌다.(effect가 *로 저장되면 뒤는 3ㅁive 인식--마름모 기호)

약 1.2MB 절약(in RCV1)

 

5. Posting Compression

posting file은 dictionary에 비해 크다. (적어도 10배)

->이 posting을 축약적으로 저장하는것.

포스팅은 docID를 이용

RCV1 task에서 이전까진 32bit docID를 사용(4byte 정수형)

그러나 log2(800000)이 20보다 작으므로 모든 파일은 20bit 내에 표현이 가능하다.(800,000= 1000*800 ~= 2^10 *2^20 )

 

주요아이디어: gap 사용하기.

말 그대로 첫 id를 제외하고 그 다음 docID까지의 차이만을 표시하는 방법.

비슷한 곳에서 빈도가 높으면 유리.

그러나 gab 크기도 유동이 큼.=>variable length 필요

 

Variable length encoding

: 말 그대로 다양한 크기로 인코딩

Variable byte(VB) code

• 전체 바이트의 맨 앞비트를 continuation bit 'c'로 설정하고, 마지막 바이트에서만 1로 설정.

그 외에도 VW(words=32bit), VDB(double byte=16bit), VN(nibble = 4bit)

 

bit level에서의 Gamma code

일단 Unary코드는 숫자 n을 n개의 1에 마지막에 0을 붙여 나타낸다.

감마 코드는 length와 offset의 조합으로 gap G를 나타낸다.

숫자 n을 2진법으로 고치고, 맨 앞의 1을 제거한다. (이게 offset)

그리고 offset의 길이가 length. length는 Unary code로 나타낸다.

length-offset을 순서대로 조합하여 코드가 된다.

 

offset의 크기는 lower(log2 G) bit, length의 크기는 lower(log2 G) + 1 bit

=>전체 코드는 2lower(log2 G)+1 bit이다.(즉 무조건 홀수이다.)

다른 prefix가 혼동되지 않는다.(prefix-free)