압축은 어려워 ... ㅠㅜ :: 2008/11/19 14:45


아직도 1바이트에 목숨을 걸어야 한다는 이야기를 듣는다면 숨이 콱 막힙니다. 특히나 자신이 그런 일에 내몰릴때는 정말 토할것 같은 심정이죠. 요즘 회사에서 하고 있는 일 중에도 이런 것과 관련된 것들이 있답니다. 물론 1바이트에 목숨걸 정도는 아니지만 평소 무시하고 살던 용량에 제법 민감한 작업이랍니다. 하여튼 이런 연유로 오늘은 파일을 압축하는 기능을 추가하고 있었습니다. 그러다 압축에 관한 재미난 사실을 알게 되었지요. 머 대단한 건 아니지만 말입니다. ㅋㅋㅋ~

제가 작업했던 내용은 실행 파일에 변형, 암호화, 압축과 같은 수정을 가해서 크기를 줄이는 작업이었습니다. 그다지 어려운 작업은 아니었지만 늘 그렇듯이 무엇을 저장하고 무엇을 계산할지 결정하는 일, 오프셋 계산을 하는 일들이 귀찮은 그런 작업이었죠.

#0. 압축을 먼저할까? 암호화를 먼저할까?
먼저 처리해야 하는 굵직한 작업 두 가지는 압축과 암호화 였습니다. 완전히 별개의 두 가지 작업이기 때문에 어떤 것을 먼저하든 순서는 큰 상관이 없습니다. 단지 암호화 작업은 입력 버퍼에서 그대로 작업이 가능하고(in place), 압축은 그게 불가능하다는 것이 특징이었죠. 그래서 저는 로딩하는 부분을 간단히 하기 위해서 암호화를 먼저했습니다. 그러면 로딩할때는 압축을 해제할 버퍼 하나만 생성하면 되거든요. 반대로 한다면 버퍼를 두 번 생성을 해야 한답니다.

그런데 재미난 사실은 이 두 가지 작업의 순서에 따라서 압축 효율이 극도로 달라진다는 사실입니다. 제가 처음 작업했던 암호화, 압축의 순서대로 프로그램을 작성하면 60k 정도 파일이 40k 정도로 생성이 되었습니다. 그런데 놀랍게도 압축을 먼저하고 암호화를 하면 60k 정도 파일이 20k로 압축이 되더군요.

왜 그럴까요?
답은 간단합니다. 복잡도에 따른 압축 효율의 차이죠. 암호화 작업을 하게 되면 원본 파일의 바이트 구성이 극도로 불규칙해집니다. 무질서해 졌다고 할 수 있겠죠. 따라서 원본 보다는 압축 효율이 낮을 수 밖에 없었던 겁니다. "0001111"을 압축하는 것과 "z0234ccf"를 압축하는 것은 크기가 같더라도 차이가 나겠죠.

#1. 패딩 바이트 제거. 독일까? 약일까?

크기에 대한 욕심이 들면서 저는 추가적으로 압축을 하기 전에 실행 파일 사이에 들어있는 패딩 바이트들을 제거하는 작업을 하기로 했습니다. 쓸모도 없이 0으로 가득찬 그 공간이 꽤나 못마땅하게 느껴졌거든요. 패딩 바이트를 제거하기 위해서 또 귀찮은 오프셋 계산을 하고 몇 번의 디버깅을 했습니다. 흠. 그리곤 새로운 함수 하나가 추가되었죠. 이 함수를 통해서 압축을 하기 전에 패딩 바이트들을 제거할 수 있게 되었습니다. 이제 프로그램은 아래와 같은 순서를 따라서 결과를 만들게 되었습니다.

원본 => 패딩제거 => 압축 => 암호화 => 결과

물론 패딩 바이트들이 그렇게 크진 않지만 4k 정도의 정렬 기준을 사용하는 경우에는 수십 킬로 바이트를 패딩 공간이 낭비하는 경우도 더러 있습니다. 제가 사용했던 입력 파일은 60k정도에 패딩으로 6k 정도가 사용되는 그런 파일이었습니다. 즉 패딩 제거를 함으로써 압축의 입력으로 들어가는 크기가 6k가 줄었다는 것이죠. 꽤나 큰 차이 아닌가요? ㅎㅎ

실행을 하기 전까지 저는 당연히 약이 될거라 생각했습니다. 6k나 줄였는데 1바이트는 줄겠지 하는 생각을 했었죠. 새로운 기능이 추가된 것으로 작업을 했습니다. 하앍... 왠걸. 원래 만든 프로그램보다 출력 결과물이 어림잡아 1~200 바이트나 크게 나오는 겁니다. 입력을 무려 무려 60k에서 6k나 줄였는데 거진 10%가 줄인 입력을 넣었는데 결과가 더 크게 나오는 것이죠. 다른 몇몇 파일로도 실험을 해보았는데 비슷한 결과가 나오더군요. 결국 패딩을 제거하는 것은 압축에는 독이된 셈이었습니다. 물론 이 또한 무질서 정도에 따른 압축 효율 저하때문이겠죠. 0으로 착하게 채워진 공간들이 압축 알고리즘에는 제법 도움을 줬나 봅니다.

#2. 역으로...
이런 일련의 두 사건을 겪다보니 실상 압축에 있어서 파일 크기가 그렇게 큰 팩터가 되지 않는다는 사실을 느끼게 되었습니다. 특히나 저처럼 작은 파일을 더 작게 만드는 일에 있어서는 말이죠. 그래서 생각난 것이 그러면 역으로 압축시 노이즈를 삽입해서 엔트로피를 낮출수 있다면 더 작은 파일을 만드는 것이 가능하지도 않을까하는 생각이 들었습니다. 물론 손실 압축을 이야기하는 것은 아닙니다. 노이즈는 일정 규칙대로 삽입이 되어야 하고, 압축이 해제된다음 원본으로 복원할 수 있어야겠죠.

해보진 않았지만 이런 작업으로 압축 효율을 높일 수 있다면 대단한 일이 될 것 같네요. 찾아봐도 딱히 마땅한 자료는 안걸리는 군요. ㅠㅜ~



스폰서
글타래

  • 2주간 인기 글
  • 2주간 인기글이 없습니다.
Trackback Address :: http://jiniya.net/tt/trackback/738
  • 오랜만에..

    Tracked from zoops 이야기 | 2008/11/19 18:46 | DEL

    정말 오랜만에 포스팅을 해본다. 곧 돌아올 예정이긴 하지만... 어떤 형태로 돌아올지는 아직 미지수.... 하여간... 포스팅한이유는... 영진씨 포스팅을 읽고.... 재미있는것 같아서.... ^^ 영진씨..

  • Gravatar Image.
    Z | 2008/11/19 16:46 | PERMALINK | EDIT/DEL | REPLY

    노이즈 삽입에까지 생각이 미친다는 것 자체가 나이스하네...
    But ... 러프하게 생각해서리... 시간낭비일 것이다에 한표....(비코우즈... 뭔가를 더해야 한다는 귀차니즘 발동)

  • Gravatar Image.
    drvoss | 2008/11/20 09:05 | PERMALINK | EDIT/DEL | REPLY

    노이즈를 삽입하면 음.. 재밌겠는데요 ^^

    저는 파일 타입에 따라서 바이너리 특징이 있으니, 파일 타입에 따른 바이너리 재배열을 선행하고 압축하면 압축률이 좋아지지 않을까 생각해 본적이 있습니다. 0001111 으로 정렬된게 아무래도 이로울 테니까요.

    파일 크기가 얼마나 작은지 모르겠지만, 아주 작지 않다면 Dictionary 크기가 크면 짱입니다. 4기가짜리 쓰면 7zip 정도 압축률이 나오니, 한 32기가 쓰면 백과사전정도는 디스켓 한장에 담을 수 있지 않을까요?

    좋은 생각 감사합니다. ^^ 아침부터 완전 상큼하네요 >_<

    • Gravatar Image.
      codewiz | 2008/11/20 18:06 | PERMALINK | EDIT/DEL

      제가 사전 크기를 16M부터 4G까지 해봤는데 파일이 작아서 그런지 별로 달라지지 않더라고요. 32G 사전은 정말 쩔겠네요... ㅋㅋㅋ~

  • Gravatar Image.
    Glo | 2010/08/19 23:58 | PERMALINK | EDIT/DEL | REPLY

    압축을 먼저하면 버퍼를 두번 생성해야 하는군요^^
    좋은 정보 보고 가요~

Name
Password
Homepage
Secret
< PREV | 1| ... 44|45|46|47|48|49|50|51|52| ... 604| NEXT >