Why Compression?

• disk space, memory를 절약.
• compressed data + decompress 과정이 uncompressed data를 읽는 과정보다 빨라야 한다.
• decompression 알고리즘이 빨라야 한다.

Compression for inverted index

• Dictionary가 main memory에 넣을 수 있을 정도로 작았으면 좋겠다.

term vocabulary가 몇 개 있을까? : 70여개 ^ 20개 character = 10^37

길이 20짜리 string은 10^37개의 가짓수가 나옴

Vocabulary vs Collection size

$$ M=kT^b $$

T : Collection의 token 수, M : Dictionary size

아 그러니까 가로축이 $log_{10}T$, 세로축이 $log_{10}M$인 그래프에서 $y=ax+b$를 한거임. $log_{10}M=a(log_{10}T)+b=alog_{10}T^b$ 느낌으로 됨. 그냥 linear regression하는 거인듯.

중요