오래 전에 저는 어떤 종류의 교수가 미래에 우리는 단지 2 비트 (또는 이와 유사한 것)로 데이터를 압축 할 수 있다고 신문 기사를 읽었습니다.

이것은 물론 정확하지 않습니다 (그리고 그가 정확히 말한 것에 대한 나의 기억이 올바르지 않을 수도 있습니다). (기술적으로 가능하더라도) 0과 1의 문자열을 단지 2 비트로 압축 하는 것은 실용적이지 않습니다. 왜냐하면 너무 많은 다른 종류의 문자열은 같은 두 비트로 압축 될 것입니다. ‘및’10 ‘중에서 선택).

어쨌든, 이것은 어떤 계획에 따라 0과 1의 임의의 길이 문자열을 압축하는 가능성에 대해 생각하게했습니다. 이러한 종류의 문자열의 경우 문자열 길이 (0과 1 사이의 비율은 중요하지 않음)와 최대 압축 사이에 알려진 관계가 있습니까?

다시 말해, 0과 1의 문자열을 압축 할 수있는 최소 (가장 작은) 길이를 결정하는 방법이 있습니까?

(여기서 저는 현재 기술적으로 가능한 것이 아니라 수학적 최대 압축에 관심이 있습니다.)

답변