이론 : 일부 파일을 작지만 더 크게 만드는 압축 알고리즘?
https://stackoverflow.com/questions/1513567
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는이 질문을 발견했다.
"무손실 압축 알고리즘은 일부 파일을 더 작고 파일을 더 크게 만들지 않는다고 주장합니다.
이것은;
a) 불가능합니다
b) 가능하지만 불확실한 시간 동안 실행될 수 있습니다.
c) 압축 계수 2 이하,
d) 압축 계수에 대해 가능합니까? "
나는 (a)에 기대고 있지만 그 이유에 대한 확실한 설명을 할 수 없었습니다. (나는 친구의 생각을 나열하고 가능한 대답으로 생각해 냈습니다)
해결책
비둘기 구멍 원리에 따르면, 10 비트의 스트링이 주어지면 1024 개의 가능한 입력이 있고 9 비트 이하의 적은 수로 매핑해야하므로 <1024 출력이 있습니다.
이를 통해 알고리즘에 충돌 (손실 압축)이 있거나 어느 시점에서 수정되지 않은 입력을 출력으로 반환 할 수 있습니다.
후자의 경우, 임의의 비트를 압축하는 방법을 결정할 수 없습니다. (수정되지 않은 입력 또는 더 큰 비트 스트링의 압축 출력 일 수 있음).
-> 불가능합니다.
다른 팁
RJFALCONER의 게시물에 대한 약간의 설명 ...
당신은 단지 가질 필요가 있습니다 약간 파일이 작아 지므로 10 비트의 스트링이 9 비트 이하로 매핑되어야한다는 주장은 옳지 않습니다. 특히 누군가가 그러한 압축 메커니즘을 제안했다면 ~할 수 있었다 모든 문자열은 10 비트 이하의 모든 문자열에서 정확히 동일한 출력 (즉, ID 변환)을 매핑합니다.
그러나 우리는 거기에 있다고 들었습니다 하나 이상의 파일 더 작아집니다. 일반성을 잃지 않으면 서 X 비트로 시작하고 y 비트로 끝나는 것을 고려하십시오. 여기서 y는 엄격하게 x보다 작습니다.
이제 "Y 비트 이하 이하인 파일"의 도메인을 고려하십시오.y+1-1 비트 스트링 (빈 줄 포함). 더 큰 파일을 초래하지 않으려면 각각 동일한 도메인에서 비트 문자열에 매핑되어야합니다.y+1-1 압축 파일. 그러나 우리는 이미 길이 x 비트의 초기 문자열이 해당 값 중 하나로 압축된다는 것을 이미 알고 있습니다.y+1-2 가능한 값.
~에 이것 비둘기 구멍 원리가 들어 오십시오 - 당신은 분명히 2를지도 할 수 없습니다.y+1-1 입력 2y+1압축의 가역성을 위반하는 출력을 반복하지 않고 -2 출력.
a) 불가능합니다
더 압축 할 수없는 파일이있는 경우에도 압축 여부에 관계없이 정보를 추가해야 하므로이 경우 파일이 성장해야합니다.
나는 좀 늦었다는 것을 알고 있지만 Google을 통해 이것을 발견했고 다른 사람이 똑같이 할 수 있으므로 대답을 게시하겠습니다. 명백한 해결책은 다음과 같습니다. a) impossible, 또한 Jon Skeet이 지적했습니다 (BTW는 인터넷 전체에 많은 증거가 있습니다). 나는 처음부터 명확하게 무작위 데이터를 압축 할 수 없다고 의문을 제기하지 않습니다. 나는 그 뒤에 놓인 이론을 이해하고 - 당신이 나에게 물어 보면 수학을 신뢰한다. : d
그러나 우리가 허용된다면 측면으로 생각하십시오, 우리는 질문이 잘 정의되지 않았다는 사실을 분명히 활용할 수 있습니다. 즉, "압축 알고리즘"과 그 속성에 대한 엄격한 정의를 제공하지 않음을 의미합니다 (그러나 감소하기 위해 약간 다른 사람을 확장하지 않고 파일).
또한 파일의 조건을 압축 할 내용을 제시하지 않습니다. 관심있는 유일한 것은 "일부 파일을 더 작고 파일을 더 크게 만들려면".
즉, 우리는 이제 실제로 그러한 알고리즘이 존재한다는 것을 보여주는 두 가지 방법을 가지고 있습니다.
파일 이름을 활용하여 파일의 일부 정보 (또는 파일 시스템에서 허용되는 경우 전체 파일도 0 비트로 줄일 수 있음)를 저장할 수 있습니다. 사소한 경우, 우리는 단순히 모든 파일을 만날 수없는 상태로 결정할 수 있습니다. 나는 이것이 부정 행위로 간주 될 수 있다는 데 동의하지만, 다시, 초기 질문에는 제한이 없으며이 알고리즘은 효과적으로 목적을 달성 할 것입니다 (아무도 파일을 이름 바꾸지 않는 한, 이것이 그 외에도 매우 열악한 디자인 선택이 될 것입니다. 무의미하다).
우리는 압축 할 파일 수를 최소한
X비트 길이. 다시 한 번, 사소한 솔루션은 모든 파일을 그대로 두는 것이지만 하나는 파일보다 작은 파일에 일치하도록 줄일 수 있습니다.X비트. 지금 우리는하다 구두로 인용하여 일부 파일을 더 작고 더 크게 만들지 않는 알고리즘이 있습니다. 그러나 가능한 모든 입력에 대한 제한을 수행합니다 (즉, 모든 파일을 처리 할 수는 없습니다).
이것이 실용적으로 사용되지 않을 것이라고 주장하는 사람들에게 나는 당신과 동의한다고 말합니다 ... 그러나 이것은 이론이며, 이것은 단지 이론적 인 논문이었습니다. ;)
분명히, 내가 테스트를 하고이 질문에 직면한다면, 나는 Bold X를 a), 그리고 그것에 대해 너무 많이 생각하지 않고 계속하십시오.
그럼에도 불구하고 자연어가 본질적으로 모호하고 질문이 공식적으로 표현되지는 않기 때문에 다른 가능한 답변은 반드시 잘못된 것은 아닙니다. 올바른 조건을 배치하고 특정 개념이 의미하는 바를 더 명확하게 지정하는 것은 완벽하게 가능합니다. , 우리는 합법적으로 다른 나열된 옵션의 목표를 충족시켜 일종의 속임수를 수행하고 원하는 행동을 달성하도록 프로그램을 강요 할 수 있습니다.
e) 가능
... 약간의 제한 사항이 있습니다.
나는 최근에왔다 Shoco, 작은 문자열 용 스트링 압축 라이브러리. 이 주장을 읽을 때이 질문을 생각 나게했습니다.
... Shoco의 가장 놀라운 속성은 압축 크기가 일반 ASCII 인 경우 입력 문자열의 크기를 초과하지 않는다는 것입니다.
입력 데이터가 일반 ASCII인지 확신하는 경우 입력 문자열만큼 크기가 커야합니다.
가능한
to make some files smaller and no files larger
상기 압축 알고리즘이 파일을 더 크게 만들면 원본 파일을 반환하십시오.
