한국어
메뉴

정보 이론과 부호의 기초

무손실 압축과 정보원의 엔트로피의 관계에 대한 설명으로 올바른 것은?

  1. A뛰어난 무손실 압축 알고리즘을 사용하면, 어떤 내용의 파일이라도 반드시 원래보다 작게 할 수 있다
  2. B기호를 독립적으로 내는 정보원이라도, 잘 고안한 가역 부호라면 평균 부호 길이를 엔트로피보다 작게 할 수 있다
  3. C가역 부호의 평균 부호 길이는 엔트로피보다 작게 할 수 없지만, 기호를 묶어서 부호화하면 가깝게 할 수 있다
정답과 해설 보기

정답: C. 가역 부호의 평균 부호 길이는 엔트로피보다 작게 할 수 없지만, 기호를 묶어서 부호화하면 가깝게 할 수 있다

기호를 독립적으로 내는 정보원에서는 가역 부호의 1기호당 평균 부호 길이가 엔트로피 이상이 되며, 기호를 묶어서 부호화하면 엔트로피에 얼마든지 가깝게 할 수 있습니다(정보원 부호화 정리). 또한 n비트 파일은 2ⁿ가지가 있는데 그보다 짧은 비트열은 모두 합해도 2ⁿ − 1가지밖에 없으므로, 모든 파일을 짧게 할 수 있는 무손실 압축은 없습니다. 무손실 압축은 치우침이나 반복이 있는 데이터를 짧게 하는 대신, 그렇지 않은 데이터를 조금 길게 합니다.

이 분야 연습하기 분야로 돌아가기

정보 이론과 부호의 기초의 다른 문제

  1. 40문자의 문자열 AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD(A가 12개, B가 4개, C가 20개, D가 4개)를, 같은 문자의 연속을 '문자(1바이트)와 개수(1바이트)'의 쌍으로 나타내는 런 렝스 부호화로 압축한다. 원래 문자열은 1문자 1바이트로 하고, 압축률을 '압축 후의 크기 ÷ 압축 전의 크기'로 할 때 압축률은?
  2. 런 렝스 부호화로 압축했을 때 크기를 가장 작게 하기 쉬운 데이터는?
  3. ZIP이나 gzip 등에서 사용되는 LZ77 방식의 개념으로 올바른 것은?
  4. LZ77 방식으로 압축한 데이터를 복원한다. 데이터는 '문자 A', '문자 B', '(거리 2, 길이 5)'의 순서로 늘어서 있다. (거리 d, 길이 L)은 '복원한 문자열의 끝에서 d문자 앞의 문자를 끝에 복사하는' 것을 1문자씩 L번 반복함을 나타낸다. 복원한 문자열은?
  5. 데이터를 압축할 때, 손실 압축이 아니라 무손실 압축을 사용해야 하는 것은?