오래 전에 저는 어떤 종류의 교수가 미래에 우리는 단지 2 비트 (또는 이와 유사한 것)로 데이터를 압축 할 수 있다고 신문 기사를 읽었습니다.
이것은 물론 정확하지 않습니다 (그리고 그가 정확히 말한 것에 대한 나의 기억이 올바르지 않을 수도 있습니다). (기술적으로 가능하더라도) 0과 1의 문자열을 단지 2 비트로 압축 하는 것은 실용적이지 않습니다. 왜냐하면 너무 많은 다른 종류의 문자열은 같은 두 비트로 압축 될 것입니다. ‘및’10 ‘중에서 선택).
어쨌든, 이것은 어떤 계획에 따라 0과 1의 임의의 길이 문자열을 압축하는 가능성에 대해 생각하게했습니다. 이러한 종류의 문자열의 경우 문자열 길이 (0과 1 사이의 비율은 중요하지 않음)와 최대 압축 사이에 알려진 관계가 있습니까?
다시 말해, 0과 1의 문자열을 압축 할 수있는 최소 (가장 작은) 길이를 결정하는 방법이 있습니까?
(여기서 저는 현재 기술적으로 가능한 것이 아니라 수학적 최대 압축에 관심이 있습니다.)
답변
Kolmogorov의 복잡성 은 이것을 수학적으로 공식화하는 한 가지 방법입니다. 불행히도 문자열의 Kolmogorov 복잡성을 계산하는 것은 계산할 수없는 문제입니다. Kolmogorov 복잡성 근사화 참조 .
문자열 자체 보다는 문자열 소스 를 분석하면 더 나은 결과를 얻을 수 있습니다 . 다시 말해, 소스는 어떤 분포에 따라 문자열을 무작위로 선택하는 확률 적 프로세스로 모델링 될 수 있습니다. 이 분포의 엔트로피는 수학적으로 가능한 압축률을 알려줍니다 (최대 약간의 추가 상수).
완벽한 압축이 불가능하면 다음 사항에도 관심이있을 수 있습니다.
답변
또한 많은 경우에 정확한 재구성에 신경 쓰지 않습니다 . 이것을 손실 압축 이라고하며 음악과 비디오가 압축되는 방식입니다. 이 경우 위에서 언급 한 하한은 유지되지 않지만 다른 하한을 생각해 낼 수 있습니다.
답변
다음은 임의의 비트 문자열을 무손실로 압축 할 수있는 간단한 체계입니다. 가장 작은 결과는 단지 1 비트입니다.
문자열이 컴퓨터의 하드 드라이브에 저장된 AAC 형식으로 베토벤의 9 번째 교향곡, 4 번째 움직임을 녹음하는 것과 일치하면 출력은 단일 비트 ‘0’입니다.
문자열이 다른 것이라면, 출력은 단일 비트 ‘1’에 이어 원본 문자열과 동일한 사본이옵니다.
이 방식은 하나의 가능한 입력을 정확히 1 비트로 줄이고 다른 모든 입력의 길이를 늘립니다. 압축 알고리즘이 입력 문자열을 압축 문자열에 매핑 할 수 있고 압축 문자열을 원래 문자열에 다시 매핑하는 압축 해제 알고리즘이 있고 압축 알고리즘이 입력을 더 짧은 문자열에 매핑 하는 경우 그런 다음 일부 입력 문자열을 더 긴 문자열로 매핑해야합니다 .
답변
모든 압축 구성표에 대해 압축 할 수없는 데이터를 생성 할 수 있습니다. 따라서 압축 방식이 일부 유형의 데이터에서 매우 효율적이더라도 일정한 비율로 일관되게 압축되지는 않습니다.
특정 압축 알고리즘에 대해 압축 할 수없는 데이터의 예를 생성하는 방법은 간단합니다. 더 이상 크기가 줄어들지 않을 때까지 모든 종류의 데이터를 가져 와서 압축 알고리즘을 반복적으로 실행하십시오.
따라서 비트 열의 압축성은 실제로 문자열 길이의 함수가 아니라 압축 알고리즘과 관련하여 복잡합니다.
답변
엔터프라이즈 백업 시스템에서 사용하는 흥미롭고 완전히 다른 알고리즘이 있습니다. 아이디어는 10,000 대의 컴퓨터를 보유한 회사가있는 경우 이러한 많은 컴퓨터에는 동일한 파일이 많이 포함된다는 것입니다. 예를 들어 회사의 모든 사람에게 전송 된 전자 메일은 모든 단일 하드 드라이브에서 동일한 파일로 끝날 수 있습니다.
따라서 파일을 백업하려는 백업 시스템은 공간을 절약하기 위해 파일을 압축하려고 시도하지만, 백업 시스템은 먼저 완전히 동일한 파일이 이미 저장되어 있는지 확인합니다! 그래서 그 대신 백업의 아무것도 , 백업 시스템이하는 모든 것을 당신이 당신의 하드 드라이브에 백업 시스템에서 파일 번호 1487578을 가지고 예를 들어, 기억하기위한 것입니다.
예를 들어 10,000 명의 사용자가 모두 동일한 운영 체제와 응용 프로그램을 설치 한 경우에 특히 효과적입니다. 단일 사용자에게는 전혀 유용하지 않습니다.