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

leehipo의 이미지

게임을 만들고 있습니다.

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

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

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

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

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

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

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

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

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

puresupe의 이미지

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

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

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

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

mithrandir의 이미지

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

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

snowall의 이미지

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

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

snowall의 이미지

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

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

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

terzeron의 이미지

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

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

cleansugar의 이미지

원본 정보량: 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의 이미지

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

cleansugar의 이미지

제가 틀린 것 같네요.

제가 모르는 게 있는데요.

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

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

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

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

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

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

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

kaeri17의 이미지

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

kaeri17의 이미지

두번써져서...

nthroot의 이미지

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

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

kaeri17의 이미지

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

kaeri17의 이미지

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.