현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

허프만 인코딩에 대한 질문입니다.

leehipo의 이미지
글쓴이: leehipo / 작성시간: 토, 2010/12/04 - 8:07오후

게임을 만들고 있습니다.

30x30보드에 0~9까지의 숫자가 적혀있습니다.

이 보드에 대한 정보를 길이 100의 문자열로 표현해 서버로 전송해야 하는데요.

30x30 = 900칸인데.. 문자열 길이도 900이 되잖아요.

이를 압축하기 위한 방법을 찾던중 허프만인코딩을 알게되었는데요.

허프만인코딩을 사용하면 문자열이 더 길어지지 않나요?

예를 들어
997796이면 001010011인데 6->9로 길이가 늘어나잖아요?

물론 byte, bit 용량으로 따지만 줄어들지만.

둘다 문자열(String)로 표현할 경우 길이는 늘어나는게아닌가요?

음.. 압축을 어떻게할지 고민이 많습니다.

Forums: 
프로그래밍 QnA
puresupe의 이미지

글쓴이: puresupe / 작성시간: 토, 2010/12/04 - 10:06오후

문자열로 전송하는 경우는 해당되지 않을것같습니다.

말그대로 허프만코딩 자체가 정보량에 대한것인데.

스트링으로 보내는것은 무의미하다고 생각합니다.

비트로 인코딩해서 보내서. 서버에서 디코딩하실순 없나요??

mithrandir의 이미지

글쓴이: mithrandir / 작성시간: 토, 2010/12/04 - 10:36오후

10을 표현하려면 4bit. 요걸 900개 하면 3600bit = 450byte 군요. 여전히 100byte에 비하면 많이 넘치긴 하네요. 그런데 huffman으로 압축한다고 해도 정말 최소일 때 개당 1bit, 900 = 900bit ~ 112byte. 그럼 100은 넘어갑니다.
100byte한정의 이유가 있나요?

언제나 삽질 - http://tisphie.net/typo/
프로그래밍 언어 개발 - http://langdev.net

snowall의 이미지

글쓴이: snowall / 작성시간: 월, 2010/12/06 - 6:08오후

100바이트 한정은 아마 트위터 기반 게임이기 때문에 그런 것 아닐까요? 물론 근거없는 추측입니다....

피할 수 있을때 즐겨라! http://melotopia.net/b

snowall의 이미지

글쓴이: snowall / 작성시간: 일, 2010/12/05 - 10:01오전

30x30픽셀의 그림이라고 생각하고 보면, 최초 1회에 전체 정보를 보내고 그 이후부터는 변화한 부분만 보냅니다.
그럼 900개중 k번째(3자리수 < 1024 = 10비트)+변화한 값(1자리수 < 16 = 4비트)니까 1개당 14비트로 보낼 수 있고, 그럼 100바이트(=800비트) 범위 내에서 57개까지 보낼 수 있습니다. 한두개 남는 비트는 패리티로 쓸 수도 있겠네요.

한번에 변화하는 양이 57개 이상이거나, 최초 1회부터 100바이트 제한이 걸린다면 이 방법은 사용할 수 없겠지만요.

피할 수 있을때 즐겨라! http://melotopia.net/b

terzeron의 이미지

글쓴이: terzeron / 작성시간: 일, 2010/12/05 - 4:41오후

동일한 정보가 연속해서 반복적으로 나타나는 경우에는 길이가 줄어들지만
그렇지 않으면 길이가 원본보다 늘어날 가능성도 좀 있습니다.
상식적으로 생각해보면 900칸에 대해 0~9까지의 10가지 값이 존재한다면
연속해서 동일한 정보가 나타날 확률이 높기 때문에 원본길이보다는 줄어들 가능성이 훨씬 높겠네요.

900칸이면 3칸씩 모아서 10비트로 표현하면 총 3000비트가 필요한데
100바이트 밖에 사용할 수 없다면 800비트이므로
대략 1/4 압축률을 확보해야겠네요.
(요건 실험을 통해 확인해 볼 필요가 있습니다.)

cleansugar의 이미지

글쓴이: cleansugar / 작성시간: 월, 2010/12/06 - 8:02오전

원본 정보량: 900log2(10)=900log(10)/log(2)=900*1/0.3010=2990비트입니다.

원본 글자수: 2990/(2^8)=11.68int=11.68char입니다.

100char 정보량: 100*(2^8)=25600비트입니다.

허프만 코딩 압축률 응용값은 다음처럼 36.3~94%입니다.
http://www.data-compression.com/lossless.shtml

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

terzeron의 이미지

글쓴이: terzeron / 작성시간: 월, 2010/12/06 - 5:02오후

100char 정보량이 25600비트라는 게 잘 이해가 안 됩니다.
100바이트=800비트 아닌가요?
정보량으로 따지자면 2^800 가지가 될 거구요.
설명 좀 부탁드려도 될까요?

cleansugar의 이미지

글쓴이: cleansugar / 작성시간: 화, 2010/12/07 - 3:09오전

제가 틀린 것 같네요.

제가 모르는 게 있는데요.

정보량을 가짓수라는 단위로 표현하는데, 정보량의 주요 단위는 bit입니다.

'가지'와 'bit'랑 어떻게 다른 건지 궁금하네요.

저는 두개가 같은 걸로 생각하고 그냥 가지를 bit로 바꿔서 틀린 것 같습니다.

이런 거 어느 과에서 배울 수 있는 건지도 궁금합니다.

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

kaeri17의 이미지

글쓴이: kaeri17 / 작성시간: 화, 2010/12/07 - 3:20오전

정보이론에서 나오는 것이고요 수학이나 컴퓨터 또는 물리에서 나옵니다...

kaeri17의 이미지

글쓴이: kaeri17 / 작성시간: 화, 2010/12/07 - 3:21오전

두번써져서...

nthroot의 이미지

글쓴이: nthroot / 작성시간: 월, 2010/12/06 - 9:52오전

허프만을 쓰시고 base64 같은걸로 한번더 하면 될거 같은데요. 압축율이 45% 이상은 나와야 가능한 것 같네요.

------식은이 처------
길이 끝나는 저기엔 아무 것도 없어요. 희망이고 나발이고 아무 것도 없어.

kaeri17의 이미지

글쓴이: kaeri17 / 작성시간: 월, 2010/12/06 - 7:35오후

log_2 10^900 = 900*log_2 10 = 2990 정도 되네요. 2990bit니까 373byte로군요. 어떻게 해도 100byte로는 힘들것 같습니다...

kaeri17의 이미지

글쓴이: kaeri17 / 작성시간: 화, 2010/12/07 - 3:28오전

2^800의 정보량입니다. 일단 900개를 4개로 나눠 225개씩 보낸다고 하면 100바이트쪼가리 4개면 되겠네요. 그냥 225자리 10진수를 2진수로 변환한걸 비트로 만들면 됩니다. 뭐 이렇게 큰수를 변환하려면 좀 알고리즘이 복잡해 지긴 하겠네요... C환경이면 GMP로 가능하긴 할듯.

255자리를 16진수로 BCD를 하면 113바이트가 필요하네요. 이러면 2진수 변환은 불필요하지만 그만큼 불필요한 비트가 더 쓰이게 됩니다.

아 그리고 허프만 인코딩하고 상관 없이 100바이트로 줄이는건 불가능합니다. 100바이트는 아무리 많이 다른 정보를 가져도 2^800밖에 안되니까요. 2^800개의 서로 다른 상태까지 밖에 표현을 못합니다. 혹시 30 by 30의 큰 크기가 다 필요하지 않고 무슨 제약이 있다면 꼭 10^900이 정보량이 될 필요가 없기 때문에 가능할 수도 있을지 모르겠습니다.

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.