엔트로피 코딩

수학 지식을 높이기 위해 엔트로피에 관한 지식을 배워야 하나!!
엔트로피는 원래 뭐였지?
정보량과 엔트로피는 정보 이론의 개념으로 어떤 일이 발생할 때 얼마나 어렵게 발생하는지를 나타내는 척도이다.
어떤 데이터를 표현하는데 필요한 최소한의 정보량은 무엇일까.A와 B 두 가지 모드만 있다면 A=0, B=1이 할당된 것을 알았다면 ABAB는 0101(bit)이며 0x5(hex)로 표현할 수 있다.
사람은 엔트로피를 토대로 더 적은 데이터로 정보를 표현하기 위해 끊임없이 모색하고 있다.
가농포 코드
한마디로 누적된 출현 확률이 그대로 드러난다.
예를 들어 다음과 같은 테스트 데이터로 고려한다(공간은 쉽게 이해할 수 있는 구분자를 위한 것이다).
- SRC = AABB ABAB ABAB CAAA
A=00, B = 01, C=10 (bin)면 2비트× 16 = 32bit
- SRC = 00000101 00010001 00010001 10000000 (bin)

P(A) = 9/16 = 0.5625(dec)

P(B) = 6/16 = 0.375(dec)

P(C) = 1/16 = 0.0625(dec)

li(A) = ceil ( ln( 0.5625) ) = ceil(0.830075) = 1

li(B) = ceil ( ln( 0.375) ) = ceil(1.415037) = 2

li(C) = ceil ( ln( 0.0625) ) = ceil(4) = 4

누적 P(A) = 0.0(dec) = 0.0(hex)

누적P(B)=누적P(A)+P(A)=0.0+0.55625=0.55625=0.11(hex)

누적 P(C) = 누적 P(N)+P(B) = 0.55625+0.375 = 0.9375=0.11(hex)

a(A) = 0

a(B) = 10

a(C) = 1110

SRC = 00000101 00010001 00010001 10000000 (32bit)

DST = 001010 010010 010010 1110000　(25 bit)

하프만 코드
빈도가 높은 것이 나오면 짧은 비트를 나눠보자는 생각이다.

P(A) = 9/16 = 0.5625(dec)

P(B) = 6/16 = 0.375(dec)

P(C) = 1/16 = 0.0625(dec)

P(B) 및 P(C)가 낮습니다.그래서 여기서 노드(B+C)를 만든다.

P(A) = 0.5625

P(B+C) = 0.4275

여기서 새로운 노드(A+B+C)를 만듭니다.이 시간에 모든 요소를 처리했기 때문에 결국 이 A+B+C는 루트가 되었다.
그리고 인코딩을 시도해 보세요.

root(A+B+C) ⇒ A : a(A) = "0"

root(A+B+C) ⇒ node(B+C) ⇒ B : a(B) ⇒ "1"+"0"= "10"

root(A+B+C) ⇒ node(B+C) ⇒ C : a(C) ⇒ "1"+"1"= "11"

이걸로 23비트까지 작아지다니!

SRC = 00000101 00010001 00010001 10000000 (32bit)

DST = 001010 010010 010010 11000 (23bit)

여기까지의 수단의 약점은?
예를 들어 재주파수를 나타내는 A만 1비트를 사용했다!그러니까 정보량이 더 이상 줄어들면 안 된다는 거예요.
그래서'복수 비트의 기호로 더 많은 정보를 표현하자'고 생각했다.
극단적으로 말하면, "3.14"는 바로 "159265..."이다.이어'1.732'하면'0508...'이렇게 계속됩니다.
이야기는'어떤 수열을 표현하고 더욱 치밀한 표현 수단'을 향해 발전한다.
산술 부호
데이터의 출현 빈도에 따라 0~1 사이의 구간을 구분하다.
다음 데이터가 반복되면 그 동네도 다시 쪼개지고...
한 소수로 여러 개의 데이터 열을 표시할 수 있는 방법.

범위 인코딩
소수 연산을 위한 인코딩.산술 인코딩에서 0~1 구간 내에 있으면dynamic보다 몇 배나 많은 것을 동시에 처리합니다.아르바이트 단위로 출력을 입력할 수 있다고 쓰여 있는데, 음...어쨌든 보류하겠습니다.
Asymmetric numberal 시스템으로 이야기 계속
<다음 예고>https://arxiv.org/pdf/1311.2540.pdf를 천천히 읽고 좀 더 자세히 읽어주세요!