정보 론 기초 및 호 프 만 코딩

나 는 논문 마다 다른 세계관 과 서술 방식 을 지긋지긋 하 게 참 았 다.다음 글 의 모든 공식 과 알고리즘 절 차 는 Python 코드 로 제 시 됩 니 다.사람 은 실 수 를 할 수 있 고 언어 는 다른 의미 가 있 으 며 공식 은 숨겨 진 조건 이 있 으 며 논증 은 선 결 가설 이 있 지만 컴퓨터 는 가장 냉정 하고 입력 은 영원히 출력 에 대응 합 니 다.인간 이 정확성 을 쉽게 판단 하지 못 할 수도 있 지만 그 의 미 는 논의 할 여지 가 없다.
호 프 만 인 코딩 은 가장 좋 은 엔트로피 인 코딩 입 니 다. 그것 은 엔트로피 가 무엇 입 니까?
정보 론 에서 엔트로피 (Entropy) 는 요소 가 불확실 성 을 없 애 는 능력 을 묘사 합 니 다.만약 에 동전 을 몇 번 던 지고 떨 어 질 때 정면 을 위로 1 로 기록 하고 반대로 0 으로 기록한다.만약 이 동전 의 정반 면 등 이 무겁다 면, 출력 된 데 이 터 는 대략 1 과 0 등분 이 될 것 이다.정면 이 더 무 거우 면 출력 1 이 0 보다 많 을 것 이다.앞의 데이터 의 엔트로피 는 뒤의 것 보다 높 을 것 이다.예 를 들 어 LPL 이 S 월 드 시리즈 본선 에 진출 하 는 정 보 량 은 LCK 우승 보다 훨씬 많 을 것 이다.LCK 우승 은 이미 흔 한 일이 고, LPL 이 파이 널 에 진출 하 는 것 은 드 문 일이 기 때문이다.사람들 은 누군가가 쓸데없는 말 을 한 마디 했 는데, 바로 말 하 는 엔트로피 가 너무 낮다 고 자주 말한다.
그렇다면 어떻게 수학 적 으로 엔트로피 의 정 의 를 내 립 니까?먼저 한 가지 문 제 를 생각 하 다.

        Root________
       /            \
      0___          1A___
     /    \        /     \
    0      1      0      1B
   / \    / \    / \    /  \
  0   1  0   1  0   1  0   1C

위의 그림 에서 루트 를 출발 하여 시각 장애인 을 목표 C 에 도달 하도록 유도 하려 면 최소한 얼마나 많은 정보 가 필요 합 니까?세 번 의 문맥 과 무관 한 01 등 선택 에서 모두 1 을 선택해 야 한 다 는 것 은 분명 하 다.0 이나 1 을 표현 할 수 있 는 2 진 비트따라서 최소 3 비트 가 걸 려 야 시각 장애인 이 C 에 도착 하도록 유도 할 수 있 으 니 111 로 계산 해도 무방 하 다.이 과정 을 묘사 하 는 모든 정보의 크기 하 계 는 3Bits 이다.주의!엔트로피 는 정보 크기 와 같 지 않다.엔트로피 의 단 위 는 Bits / Symbol 입 니 다.111 은 3 개의 부 호 를 사 용 했 기 때문에 111 의 엔 트로피 는 3Bits / 3 = 1Bts / Symbol 이다.일상생활 에서 뉴스 정 보 량 이 많다 고 하면 정보의 길이 가 길 고 정보 밀도 가 높다 는 것 을 가리 킬 수 있다.엔트로피 는 후 자 를 묘사한다.
위 에서 말 한 것 은 가능 한 상황 을 기다 리 는 것 입 니 다. 그러면 다른 상황 은 요?극단 적 인 상황 을 고려 하 다.

root
  |
 1A
  |
 1B
  |
 1C

큰길 이 종점 으로 직통 한다.그렇다면 이때 시각 장애인 이 루트 에서 C 까지 의 과정 을 묘사 하 는 데 몇 개의 Bits 정보 가 필요 합 니까?0。우리 가 정 보 를 주 든 안 주 든 맹인 은 갈 수 있 는 길이 하나 밖 에 없 기 때문이다.고수 의 각도 에서 이미지 의 잘못된 이 해 는 이때 엔트로피 가 무한대 가 될 것 이다.
이 두 가지 상황 과 다른 요구 에서 향 농 은 자 연 스 럽 게 정보 와 엔트로피 의 공식 을 도 출 했다.

info_per_symbol = lambda p: log2(1/p)
entropy = sum(p * info_per_symbol(p) for p in possibilities)

엔 트로피 는 모든 압축 알고리즘 의 극한 이다.선택 등 가능 한 상황 에서 우 리 는 어떠한 압축 도 할 수 없고 n 번 선택 은 n Bits 가 필요 합 니 다.선택 하지 않 은 상황 에서 우 리 는 거의 '무한 압축' 할 수 있 고 어떠한 데이터 도 기록 할 필요 가 없다.
다시 말 해 0 을 선택 하면 66%, 1 을 선택 하면 33% 의 가능성 이 있다 면 어떻게 될 까?

           root_____________________
          /                         \
        0 66%_______               1 33%______
       /            \             /           \
     0 44%         1 22%        0 22%        1 11%
    /     \       /     \      /     \      /     \
  0 29%  1 15%  0 14%  1 7%  0 15%  1 7%  0 7%   1 4%

아무것도 변 하지 않 았 다 고 말 할 수 있 겠 지?나 는 111 로 이 사건 을 묘사 할 수 있다.확실히 111 은 여전히 목 표를 잘 달성 할 수 있 지만 더 이상 전 체 를 반영 할 수 없다.선택 할 수 있 는 111 은 다른 종점 과 같 기 때문에 111 을 가지 고 토론 하 는 것 이 일반성 을 잃 지 않 는 다.현재 111 은 특례 다.
공식 적 으로 경로 1 을 계산 하 는 정 보 량 은 log 2 (1 / 0.33) = 1.6Bits 이 고 경로 0 은 log 2 (1 / 0.66) = 0.6Bits 이다.어떻게 이해 하지?우 리 는 무한 원숭이 의 정 리 를 알 고 있다. 정보 란 모든 가능 한 수치 공간 에서 특정한 점 이나 구역 을 걸 러 내 는 것 이다.방금 계산 한 결과 33% 확률 의 경로 1 의 정 보 를 표현 하 는 능력 은 50% 확률 의 경로 1 의 1.6 배 에 달 했다.다음 그림 을 잘 보 세 요.

        Root_____________________________________________________
       /                           \                             \
      0________________             0________________             1________________
     /       \         \           /       \         \           /       \         \
    0___      0___      1___      0___      0___      1___      0___      0___      1___
   / \  \    / \  \    / \  \    / \  \    / \  \    / \  \    / \  \    / \  \    / \  \
  0   0  1  0   0  1  0   0  1  0   0  1  0   0  1  0   0  1  0   0  1  0   0  1  0   0  1

나 는 확률 이 다른 2 선 1 문 제 를 등 확률 의 3 선 1 문제 로 바 꾸 었 다.만약 에 우리 에 게 3 진 시스템 이 있다 고 가정 하면 {A, B, C} 으로 A 3 진 Bits / Symbol 을 표시 합 니 다.이제 문 제 는 하나 남 았 다.어떻게 3 진법 을 2 진법 으로 바 꿉 니까?log2(3)=1.6。이해 하기 어 려 우 면 각 도 를 바 꿔 보 자. 수학 적 으로 예상 되 는 33% 확률 의 선택 은 하나의 경로 1, p = 1 / 27 을 얻 을 수 있다.50% 확률 이면 몇 번 이 걸 려 야 같은 결 과 를 얻 을 수 있 을까요?log 2 (27) = 4.8, 한 번 의 비율 은 1: 1.6 이다.
여기 서 우 리 는 정보의 압축 이 한계 가 있다 는 것 을 알 고 엔트로피 로 정확하게 묘사 할 수 있다.일부 이론 은 처음에 구체 적 인 현상 을 설명 하지 못 하고 추상 적 인 개념 에 착안 하 는 경우 가 많다.예 를 들 어 내 가 처음에 도입 한 맹인 걷 기 문 제 는 실천 적 의미 가 없 잖 아 ~ 향 농 은 전보 코드 부터 전체 정보 론 을 유도 하 는 기초 야.과학 의 가장 중요 한 것 은 기억력 이나 문 제 를 푸 는 기교 가 아니 라 상상력 이다.
호 프 만 인 코딩 은 어떻게 데 이 터 를 압축 합 니까?
주파수 가 다른 Symbol 에 포 함 된 정 보 는 다 릅 니 다. 다시 말 하면 가장 최 적 화 된 인 코딩 은 길 어 져 야 합 니 다.그러나 대부분의 컴퓨터 분야 에서 사용 하 는 인 코딩 은 길다.예 를 들 어 ASCII 인 코딩 은 모든 문자 가 8Bits 의 공간 을 차지 하고 더 통용 되 는 UTF - 8 인 코딩 은 길이 가 8 의 정수 배 여야 한다.호 프 만 인 코딩 은 고주파 차 (저 엔트로피) 의 인 코딩 을 비교적 짧 은 인 코딩 으로 표시 하고 저주파 차 는 비교적 긴 인 코딩 으로 표시 하 는 것 이다.이 알고리즘 은 비교적 간단 해서 나 도 피곤 하 게 썼 으 니 군말 하지 않 겠 다.