데이터는 표현하고자 하는 "값"을 약속된 미디어 매체를 통해 디지털 신호로 보존/전달한다. 데이터 미디어 매체를 “용기/그릇”이라 한다면 컴퓨터에서 사용하는 이진(binary) 데이터는 보통 8비트, 16비트, 32비트, 64비트 단위의 용기(unit or register)의 “값”에 대한 그릇으로 사용한다.

저장/전송되는 데이터 값의 유형을 막론하고 “데이터 값”은 그 값을 의도했거나 매우 희귀한 경우를 제외한 일상적인 데이터에서는 저장하는 용기보다 항상 작은 경우가 발생할 수밖에 없다. 그릇의 크기 보다 더 큰 물을 담을 수 없다. 현재 컴퓨터와 네트워크를 통해 저장/전송하려는 “값”은 사용 목적과 환경에 맞도록 적당한 형태의 알고리즘을 사용한 데이터 처리 프로세싱 을 통해 멀티 미디어 파일, 웹 페이지, 네트워크 트래픽 등의 “그릇”을 통해 저장 또는 전송 되고 있다.

압축을 해도 잉여는 여전히 발생한다. 압축한 후에 잉여가 가장 적게 발생하는 것이 압축률이 좋은 알고리즘이고, 사용된 알고리즘의 계산 복잡도가 낮을 수록 빠른 알고리즘이다. 훌륭한 압축 알고리즘은 알고리즘이 사용될 목표 시스템에 따라 다르다. 웹 페이지를 웹 브라우저에게 압축해서 전송하는 것의 1차 목적은 전송 데이터의 크기를 줄였을 때 얻을 수 있는 “빠른 응답 속도”이지, 압축으로 얻을 수 있는 트래픽 저하가 아니며 압축과 해제에 소요되는 CPU 자원에 대한 고려를 통해 deflate, zip 방식과 같은 가장 보편적이고 빠른 압축 방식을 사용하게 된다.

심볼의 희박에 대한 예를 들자면 순수 영문 ASCII 값으로만 된 텍스트 파일의 경우 가용한 8bit 0~255 값의 범위 안에서 출력 가능한 32~127의 값으로 텍스트를 작성하며, 탭, 리턴 등 키보드로 입력할 수 있는 문자만을 포함하게 된다. 그런 순수 ASCII 파일의 경우도 64비트 컴퓨터에서는 1글자의 값에 64비트 레지스터의 그릇을 사용하게 되는데, 실제로는 저장할 ASCII 값을 표현하기 위해서는 7비트만으로도 충분하다. 저장 공간을 줄이기 위하여 데이터를 변형 저장하는 쪽(Encode)과 읽어 해석하는 쪽(Decode)이 서로 정해진 약속(Protocol)을 통해 ASCII 파일을 간단한 알고리즘을 고안하여  데이터를 압축한다면 손쉽게 64비트 그릇 하나에 8개 이상의 7비트 ASCII 문자를 넣을 수 있어 in-memory 상태에서 저장 공간을 80% 이상 줄일 수 있게 된다.

위의 그림과 같이 "값"에 사용할 수 있는 가용한 모든 심볼 중에 소수의 심볼 만을 사용하는 경우와  "AAAAAAAA"와 같이 심볼의 "반복"에 의한 잉여가 발생하는 경우 또, “When she head to hell.” 의 문자에서의 ‘he’ 의 “중복”, 그리고 영어에서 "S"와 "A"가 "Z"과 "Q" 보다 더 많이 사용된다는 사용 “빈도”에 의한 예측 및 데이터 처리 과정에서의 데이터 진행 유형의 “유사성”에 적응하는 과정에서 압축 가능한 잉여(redundancy)를 발견하고 적합한 압축 코드를 만들어 낼 수 있다.

데이터가 이진 바이너리 형태로 발전하던 80~90년 대에는 512K ~ 1.2M bytes 용량의 플로피 디스크가 이동식 저장 매체로 많이 활용 되었다. 웬만한 대형 게임(?)의 크기가 1M 바이트를 넘지 않았었다. 플로피에 데이터를 옮기기 위해 포맷하고 복사하고 검사하는 데에 30분이 걸렸다는 호랑이 담배 피던 시절이었다. 그에 따라 플로피 던 20M 짜리 하드 디스크이던 파일 압축에 소요되는 시간 보다는 결과물의 압축률에 치중한 이진 데이터 압축 방식이 많이 사용되었다. 반대의 경우로 느려터진 모뎀을 사용하여 통신을 하던 시절에 그림 파일을 온라인에서 전송하기 위해서는 느려터진 네트워크 속도 보다는 처리 속도가 빠른 매우 단순한 이미지 압축 전송 방식(PanitBrush PCX, GIF, BMP etc)들을 사용해야 했었고 매우 훌륭한 방식이었다. JPEG가 처음 등장했을 때에 120K짜리 JPEG 이미지 파일을 해제하고 다시 압축하는 데에 최신 386 컴퓨터로 10분 이상이 걸렸다는 아주 옛날이 있었고, 그립기도 하다.

인터넷은 이제 보다 더 크고 복잡한 멀티미디어 데이터가 많이 활용되고, 동영상이 인터넷 트래픽의 가장 큰 부분을 차지하는 현재의 환경에 있어, 압축 분야 중에 가장 많이 사용되고 연구되는 데이터 압축 방식은 멀티미디어 데이터 압축이다. 보다 많은 메모리를 사용하고 광범위한 데이터 비교 검색에 의한 데이터 간의 동일성 또는 차이점을 인코딩 하는 방식으로 발전해 왔고, 대표적인 것들이 음악 및 영상에 사용되는 AC3, MP4, H.264 등의 우리에게 친근한 멀티미디어 압축 포맷이 있고 지속적으로 새로운 압축 형태가 연구 개발되고 있다. Google이 얼마 전 발표한 WebP 이미지 방식이나, On2 테크놀로지 흡수 합병 후 개발하고 있는 VP8 오픈 소스 프로젝트 및 WebM 등이 시사하는 바는 컴퓨팅 환경은 생물같이 지속적으로 변화하고 있고, 변화하는 인터넷 환경 및 데이터 유형에 따라 새로운 압축 알고리즘이 요구되고 있다는 것이다.

다 외우기도 힘든 이미지 파일 확장자들의 수만큼 전세계 인터넷에 사용되는 Universal하고 친숙한  압축 형태 보다 알려지지 않은 수 십만 배의 데이터 솔루션 업체들의 고유하고 독특한 압축 방식이 존재한다.

데이터 압축 방식은 용도에 따라 매우 다양하다. 목적에 따라 수많은 압축 알고리즘/데이터 핸들링 알고리즘을 조합하여 가장 효율적인 방식을 고안해 내는 것은 프로그래밍에 있어서 최고 수준의 "뇌력"과 "노력"이 필요한 특수한 분야이기도 하다.

현재까지 많이 사용되는 대표적인 압축 알고리즘은 크게 다음과 같다.

• Bit Squeezing – Byte Pair Encoding
• Run Length Encoding
• Lempel-Ziv
• Arithmetic Encoding
• Huffman Encoding
• Dynamic Markov Chain
• Burrow-Wheeler's Transformation
• Context Tree Weighting
• Prediction by partial matching
• Shannon-Fano

이 글에서 데이터에 존재하는 심볼의 희박성, 데이터 구성의 중복/반복성, 데이터 구성 코드의 사용 빈도에서 잉여가 발생한다고 했다. 이와 같이 데이터에는 크게 3가지 부분에서 잉여가 발생하는 데에 효율적 데이터 압축의 불확실성 및 복잡성이 존재한다. 하나의 알고리즘이나 프로세싱에서 모든 데이터 불확실한 잉여를 효율적으로 처리하기는 어렵다. 대부분 압축 프로세싱은 압축/복원 속도를 위해 어느 정도의 데이터 “압축률 VS 처리 과정의 복잡성”의 타협을 하게 된다.

보통 데이터 압축 프로세싱은 다음의 단계를 거치게 된다.

1. 심볼의 분석 후 가상 심볼 생성
2. 데이터 중복 제거 후 압축 코드 생성 ( 2 pass 이상으로 구성되기도 한다 )
3. 압축 코드 entropy의 statistical 분석 및 코딩 ( 속도 vs 압축률 )

데이터 압축은 일반적으로 위의 3단계의 데이터 프로세싱을 거치며, 1번 단계는 처리할 데이터의 유형에 따라 매우 중요할 수도, 불필요할 수도 있으며, 3단계는 계산의 복잡성이 높아 CPU/FPU 차원에서의 비용 대비 효율에서 가장 큰 타협이 이루어지는 단계이며 CPU 계산 능력에 따라 선택되며 아예 생략되기도 한다.

다음은 압축 알고리즘 중에 가장 간단하다고 알려진 RLE에 대해 알아보기로 하겠다.

다음 : Run Length Encoding( PCX )