shannon's Information theory

http://en.wikipedia.org/wiki/Information_theory

일반적인 비손실 압축에서
압축가능한 lower bound는 symbol 1개를 데이터의 entropy (bit)까지 줄일 수 있다.

Entropy H(X)=-Sum(x∈X, p(x) log p(x))

p(x) = symbol x가 symbol set X에서 출현하는 빈도

entropy가 1.75인 셋은 최대한 압축하면 symbol당 평균 1.75 bit가 됨
예를 들어 알파벳에 대해 영어 문장의 entropy가 2.5라면(정확한 값은 모릅니다만)
영어 문장을 압축하면 평균적으로 한 글자당 2.5 bit로까지 압축가능
그럼 30글자짜리 영어문장은 압축하면 평균 75 bit가 됨.

일반적인 압축의 한계는 Kolmogorov Complexity로 알 수 있음.

http://en.wikipedia.org/wiki/Kolmogorov_Complexity