비둘기집의 원리와 압축

비둘기집의 원리란 다음과 같은 것이다.

비둘기가 n마리 있고, 비둘기집이 m개 있는데, n>m이면, 반드시 비둘기가 2마리 이상 들어가는 집이 하나 이상 있다.

예를 들어 비둘기 5마리가 비둘기 집 3개에 들어가려면 어떤 집에는 비둘기가 2마리 이상이 들어간다는 것이다. 비둘기집의 원리는 너무 당연한 사실이지만, 이산수학에서 꽤 중요한 위치를 차지하고 있는 놈이다.
위키백과에서 관련된 내용을 살펴볼수 있다: 위키백과-비둘기집의 원리

컴퓨터 압축기술에 비둘기집의 원리를 적용해보자. 데이터 압축이란 어떤 데이터를 인코딩의 과정을 거쳐 원래 크기보다 작은 데이터로 변형하고, 다시 디코딩 과정을 거쳐 원래 데이터를 복원해 내는 일 모두를 일컫는다. 데이터가 압축될때 원래 데이터의 크기보다 크기가 줄어드는데, 여기에 비둘기집의 원리를 적용해보면, 모든 파일을 압축할수있는 방법은 없다는 결론이 나온다. 적어도 어떤 파일은 압축시 크기가 늘어날수 밖에 없다.

압축하기 전 데이터를 비둘기로 보고, 압축후 데이터를 비둘기집으로 보면, 압축하기 전 데이터의 길이가 압축한 후 데이터의 길이보다 길기 때문에, 압축 전의 데이터의 가짓수가 압축 후의 데이터 가짓수보다 많다. 즉 비둘기의수 가 비둘기집의 수보다 많다. 따라서 어떤 비둘기집에 적어도 2마리 이상의 비둘기가 들어가게 되고, 이는 압축된 데이터를 디코딩할때 원래 데이터를 복원해 낼수 없다는 의미가 된다. 따라서 모든 데이터를 성공적으로 디코딩할수 있으려면 압축시 크기가 늘어나는 경우도 있어야 한다.

비둘기집 원리에 따르면 압축은 불가능해 보이는데 어떻게 '압축'이 가능한 것일까?

첫번째 해결책은 압축시 데이터를 손실시키는 방법이다. 그림, 음악, 동영상 파일들의 압축(jpg,mp3,mpeg 등등)방법이 대표적인 예이다. 원본파일의 데이터를 손실시킴으로써, 비둘기의 숫자를 줄이는 것이다. 비둘기의 숫자를 많이 줄일수록(데이터를 많이 손실시킬수록) 비둘기와 1대1로 대응시켜야하는 비둘기집 숫자도 줄어들기 때문에 압축률은 높아진다.

두번째 해결책은 그냥 압축시 크기가 늘어나는 경우도 있을수 있음을 받아들이는 것이다.(-_-) 이 경우 무손실압축도 가능하다.(반복길이 부호화, 허프만 부호화 등등). 여기서 중요한 것은 파일의 특성을 백분 활용하는 것이다.
예전에 자주 쓰이던 pcx라는 그림 포맷이 있다. 반복길이 부호화 방법을 사용하는데, 주로 pcx파일이 인공적인 그림을 저장하는데 쓰였기 때문에 압축은 매우 효과적이었다. 실제 사진과 같은 데이터는 연속적으로 반복되는 색채값이 거의 나타나지 않는다. 그러나 윈도우 창과 같은 것을 찍은 그림은 같은 색이 계속 이어진다. (윈도우 창의 제목줄, 바탕색만 봐도 똑같은 색이 계속 반복되는 걸 알수 있다.) pcx포맷은 이런 그림을 저장하는데 쓰기 때문에 높은 압축률을 보일수 있는 것이다.

즉 압축은 사람에게 잘 띄지 않는 데이터를 손실시키거나, 파일의 특성을 최대한 활용하여 나타날 가능성의 거의 없는 경우를 배제함으로써 가능한 것이다. 사실 우리가 쓰는 데이터는 모두 특성이 있으며, 나타날수 있는 모든 데이터의 경우 중 대부분은 아무 의미없는 데이터(노이즈)이다. 사람은 모든 경우의 데이터를 사용하지 않는다. 의미있는 데이터만 사용하고 압축한다.