2024. 11. 26. 08:00ㆍCS/Information Retrieval
1. Compression
정보검색에서의 압축은 다음과 같은 의미를 가진다.
- dictionary의 크기를 줄이는 것은 메인 메모리에 많이 올릴 수 있다는 것이다.
- posting file을 줄이는 것은 disk space를 줄이고, disk를 읽는 시간을 줄이는 것이다.
Lossy
- 손실이 있는 압축이다.
- 소문자로 바꾸거나 stemming, stop word 제거하는것 등이다.
Lossless
- 손실이 없는 압축이다.
- zip 등이다.
딕셔너리를 디스크에 올려놓는게 굉장히 빠르고 좋은데 너무 크다. 따라서 압축을 해야 한다. 압축을 하는 경우 압축을 푸는 시간이 들긴 하지만 디스크에 접근하는 것 보다 훨씬 빠르다.
2. Term statistics
통계를 다시 보자.
number를 제외하거나 case folding, stopword 제한, stemming 방법을 사용하면 lossy하지만 많이 줄일 수 있다.
stop word를 30개 사용하나 150개 사용하나 dictionary에서는 차이가 없지만 non-positional index에서는 많이 차이난다.
dictionary에는 똑같은 단어를 허용하지 않는 term으로 구성되어 있다. 따라서 stop word가 적게 나타나고, index에는 많이 나타나는 것이다.
다르게 말하면 단어가 늘어난다고 해서 term은 그 비율대로 증가하지 않는다.
Heaps’ law
언어의 어휘가 얼마나 많을까? 문서의 개수가 증가되면 vocabulary의 크기가 어떻게 늘어날까?
- vocabulary가 계속 늘어나거나 점점 늘어나는게 아니라 어느정도 수렴한다.
- Heaps’ law : M=kT^b
- M : vocabulary의 size, T : 토큰의 수
- b는 0.5에 근사하고 k는 30 ≤ k ≤ 100을 만족한다.
- Heap’s law를 사용하면 단어 길이의 평균 byte를 추정해서 토큰 수를 구할 수 있다.
Heaps’ law를 log space에서 그려보자.
log M = log k + b log T
→ Y = C + bX 즉, 일차함수 형태로 나타난다.
실제 그래프와 비교해보면 굉장히 유사하다.
Heap’s law를 사용하면 토큰 수가 주어졌을 때 몇 개의 term이 존재할지 추정할 수 있다.
- 예를 들어 1,000,020개의 토큰을 넣었다고 생각해보자. 그럼 44 X 1,000,020^0.49 = 38,323 = dicationary size → term의 개수가 된다.
- 첫 10,000 토큰에서 3,000개의 term을 찾았고 1,000,000 토큰에서 30,000개의 term을 찾았다. 검색엔진은 총 2 x 10^10 개의 페이지를 색인화 하였고 평균적으로 200개의 토큰을 포함한다.
- 이때 vocabulary size를 Heaps law를 사용해서 추측해보자.
- log M = log k + b * log T log 3000 = log k + b * log 10000 log 30000 = log k + b* log 1000000 → k, b의 값을 구할 수 있고 그렇다면 Heaps law를 완성할 수 있다. Heaps law에 T = 2 * 10^10 * 200을 대입하면 M을 구할 수 있다.
Zipf’s law
- 자연어 처리에서 자주 나오는 단어의 종류는 적고 자주 나오지 않는 단어의 종류는 많다.
- Zipf’s law는 i번째로 자주 나오는 단어가 cf_i의 빈도를 가진다고 했을 때 1/i에 비례한다는 법칙이다.
- cf_i \propto \frac 1 i
- 예를 들어 가장 많이 등장하는 단어 the를 cf_1 , 두 번째로 많이 등장하는 단어 of를 cf_2$라 하자.
- $cf_2 = \frac 1 2 cf_1$ 이 된다.
- $cf_4 = \frac 1 4 cf_1 = \frac 1 2 cf_2$ 가 된다.
- 수식을 잘 알아두면 연결관계를 잘 정할 수 있다.
- $cf_i = \frac 1 i cf_1 = i^{-1} c = ci^k$ 로그를 취하면 $\log cf_i = \log c + k\log i \ (for \ k = -1)$ 이 된다. 즉, 이 또한 일차함수가 된다.
Few fre-quent term 즉, 자주 나오는 단어는 개수가 적고 many rare term 즉, 자주 나오지 않는 단어 개수는 많다.
3. Dictionary compression
dictionary는 posting file에 비해 매우 작고 보통 메모리에 올려놓는 것이 좋다.
따라서 dictionary는 compressing이 중요하다.
fixed length dictionary는 내부 단편화가 일어나지만 구현은 매우 간단하다.
또, 20 byte를 할당했는데 단어가 1글자거나 20 byte 보다 큰 단어가 들어오면 안된다.
Dictionary as a string
단어를 테이블에 직접 넣는게 아니라 테이블에 포인터를 두고 포인터가 가리키는 것이다.
- term의 출현 빈도를 저장하는데 4 byte를 사용한다.
- 각 용어의 posting list를 가리키는데 4 byte를 사용한다.
- 평균적으로 term의 길이는 8 byte를 사용해야 하지만 해당 방식은 각 용어의 위치를 가리키는 포인터에 3 byte를 사용한다.
- 왜 3 byte를 사용할까? 평균적으로 8 byte 길이의 term이 40만개 존재한다. 따라서 최대 term의 위치는 대략 3,200,000이 되고 log(3200000) = 22가 된다. 따라서 22 bit, 3 byte면 충분히 다 표현할 수 있다.
- 결론적으로 4(freq) + 4(posting ptr) + 3(term ptr) + 8(term in string) byte면 저장할 수 있다.
Dictionary as a string with blocking
- 연속된 block size 만큼의 term을 하나의 block으로 그룹화한다.
- block size가 4일때를 생각해보면 원래 4개의 term을 나타내기 위해 3 * 4 byte를 사용하였다면, blocking 한다면 block pointer 3 byte + term 길이 4 byte = 7 byte만 사용해도 된다.
- block size가 4일때 각 block당 12 - (3 + 4) = 5 byte만큼 절약되었다.
- 전체로 따지면, 총 400,000개의 term에 대해 100000개의 block으로 만들 수 있고 block당 5 byte를 아꼈으므로 총 500000 byte = 0.5 MB 만큼 절약하였다.
blocking을 사용하지 않는다면 term을 아래와 같이 차례대로 찾게 된다.
blocking이 있을 때는
이렇게 search의 과정이 4개씩 보는것으로 바뀌었다.
block size 만큼 sequence 서치를 해야하고 sequence 서치만큼의 시간이 좀 더 걸린다.
Front coding
사전은 sorting 되어 있다. 그래서 비슷한 단어들이 연결되어 있는 경우가 많다.
예를 들어 automata, automate, automatic, automation과 같은 단어는 다 모여있다.
여기서 automat가 모두 중복되는데, 이 부분에서 Front coding을 사용할 수 있다.
- block 별로 압축을 진행한다.
- 첫 단어는 그대로 저장한다. 그 형태는 8automt*a와 같다. 묶을 부분의 끝을 *로 표시하는 것이다.
- 다음 단어부터 첫 단어와 길이 차이 ◇ 다른 문자 를 적어준다. 1◇e 2◇ic 3◇ion 와 같다.
이런 방법을 front coding이라 한다. 공통되는 부분을 묶고 ◇로 대체시키는 방법이다.
front coding에서 prefix의 길이가 길다면 더 많은 공간을 절약할 수 있지만 디코딩 시간이 길다.
4. Postings compression
posting file은 dictionary에 비해 굉장히 크다.
800,000개의 documents를 위해서는 docID를 위해서 4-byte 정수인 32bit는 과하다. log 800000은 대략 20이므로 20 bit만 있어도 된다. 그래서 32 bit를 20bit로 줄이겠다는게 처음 아이디어이다.
gap
- docID 대신 문서 사이의 gap을 이용하는 방법이다.
- 예를 들어 COMPUTER: 283154, 283159, 283202의 posting에서 제일 처음 숫자를 가지고 gap을 나타내보면 283159 → 5, 283202 → 43이 되고 최종적으로는 COMPUTER: 283154, 5, 43, … 이렇게 표현할 수 있다.
실제 단어에 대해서 보자. 단점이 드러날 것이다.
THE은 gap이 1로 매우 작고 일정하다. COMPUTER도 그렇지만 ARACHNO~~는 gap이 굉장히 다양하고 fixed로는 충분하지 않다.
복잡한 단어들은 gap을 20bit로 표현하는 경우도 있을텐데, 그렇다면 gap으로 표현하는 의미가 없다.
Variable byte code
8bit의 가장 앞을 continuation bit로 빼둔다.
gap이 만약 7bit에 딱 맞으면 continuation bit를 1로 설정한다. 127보다 작은 숫자는 1 byte로 표현이 가능한것이다.
127보다 큰 숫자가 나오면 continuation bit를 0으로 설정하고 그 다음 byte에 마저 쓰게 된다.
byte를 채울때는 숫자를 bit로 나열하고 앞의 남는 bit는 0으로 채운다.
Other variable codes
1 byte를 단위로 하지 않고 32 bits (words), 16 bits, 4 bits (nibbles) 등등의 단위로 할 수 있다.
기본은 1 byte이다.
Gamma code
unary code를 먼저 알아야 한다.
unary code는 n을 나타내려면 1을 n개 나타내고 마지막에 0을 붙이는 방식이다. 3은 1110이 된다.
- gamma code는 gap을 length와 offset으로 표현한다.
- offset은 binary로 표현하고 맨 앞에있는 bit(leading bit)는 자른다.
- 예를 들어 13 → 1101(binary code) → 101(leading bit 제거)이 101이 offset이 된다.
- length는 offset의 길이가 된다.
- 예를 들어 offset 101인 13의 length는 3이다.
- length는 unary code로 인코딩하여 1110과 같이 표현한다.
- length+offset = unary + binary, 13 = 1110101과 같이 나타내는 방식이 gamma code이다.
예제를 잘 알아두자. 콤마는 예제를 위해 붙인 것이고 원래는 콤마를 적어서는 안된다.
감마 코드에서 원래 gap을 찾아보자.
0100 → 첫 0은 당연히 1이다. 다음 1은 legnth가 1, offset이 10 = 2, 그 다음 0도 1이다. 따라서 1/2/1이다.
gap : 100101 → 100/101 → 10/11 → 2/3
gap : 110000 → 11000/0 → 100/1 → 4/1
length가 0이면 실제 offset은 1이라는 점만 잘 알고 넘어가자.
gamma code의 길이는 어떻게될까?
- gap의 길이를 G라 하자.
- offset의 길이는 $\lfloor log_2G \rfloor$ bits 이다.
- 그 이유는 G를 2진수로 표현하려면 $\lfloor log_2 G \rfloor + 1$ bit 만큼 필요한데 leading bit를 제거하기 때문이다.
- length의 길이는 $\lfloor log_2G \rfloor$ + 1 bits가 된다.
- 따라서 전체 코드 길이는 $2\times \lfloor log_2G \rfloor + 1$ bits이다.
- 감마코드는 항상 홀수 길이이다.
- 감마코드는 최적의 인코딩 길이인 log G의 2배 이내가 된다.
gamma code의 특징
- prefix-free이다. 즉, 다른 것과 혼동 없이 확실하게 prefix를 구분할 수 있다.
- gap의 분포에 상관 없이 사용할 수 있다.
- 이전에는 분포에 따라 byte code를 쓸지, word code를 쓸지 정해졌다면 감마코드는 아니다.
- 파라미터가 필요없다.
- machine은 bit 단위로 움직이지 않고 byte 단위로 움직이기에 byte를 읽고 bit 단위로 잘라야해서 조금 문제가 있긴 하다.
- 그러나 space도 적게들고 효율이 좋다.
지금까지 배운 내용들을 총정리해보면 아래와 같다.
