데이터 압축 방식, 수학

Question

나는 [0, 255] 범위의 모든 24 개의 난수 목록 42,000 개의 목록을 가지고 있습니다. 예를 들어 첫 번째 목록은 [32, 15, 26, 27, ... 11] 일 수 있습니다. 두 번째 목록은 [44, 44, 18, 19, .. 113] 일 수 있습니다. 각 목록에서 번호를 선택하여이 새로운 목록이 ZIP을 사용하여 가장 압축 될 수 있도록 (그래서 약 42,000 개의 숫자로 된 새 목록을 만들게 될 것입니다)?

-이 질문이 나에게 NP-완료 냄새 수학, 데이터 압축

Answer 1

과 관련이있다,하지만 난 그것을 증명하는데도 수 근처입니다 없습니다. 외부에서는 테스트 할 수있는 약 7.45e + 57968 (!)의 구성이 가능합니다. 비 압축 초기 섹션이 나중에 압축 될 수 있으므로 특정 구성을 조기에 거부 할 수는 없습니다.

"좋은"압축에 대한 최선의 추측은 전체 요소 집합 전체에서 각 숫자의 발생 횟수를 계산하고 각 목록에서 가장 많이 나오는 숫자를 선택하는 것입니다. 예를 들어, 모든 목록에 42이 있으면 그 중 하나만 선택하면 같은 값의 42,000 개의 인스턴스가 압축 될 수있는 배열이됩니다.

Answer 2

ZIP 파일 형식은 압축 알고리즘에 DEFLATE을 사용합니다. 따라서 알고리즘이 작동하는 방식을 고려하고 알고리즘이 압축하기 쉬운 데이터를 선택해야합니다. 위키피디아 기사에 따르면 압축의 두 단계가 있습니다. 첫 번째는 LZ77을 사용하여 반복되는 데이터 섹션을 찾아서 짧은 참조로 대체합니다. 두 번째는 Huffman coding을 사용하여 나머지 데이터를 가져 와서 전체 블록에서 중복을 제거합니다. 엔트로피 코딩이라고합니다 - 정보가 매우 랜덤하지 않은 경우 (낮은 엔트로피가있는 경우) 코드는 일반 기호를 짧은 기호로 대체하여 엔트로피를 늘립니다.

일반적으로, 많은 반복 실행 목록 (즉, [111,2,44,93,111,2,44,9,9 ...])은 첫 번째 패스에서 잘 압축됩니다. 다른 임의의 물건 (예 : [111,34,43,50111341111112342260,111,98,2], 34 및 111이 자주 나타나는) 내에서 반복되는 숫자가 많은 목록은 두 번째 패스.

적절한 숫자를 찾으려면, 가장 쉬운 방법은 각 목록을 정렬 한 다음 병합하여 병합을 유지하면서 42000 출력 숫자가 될 때까지 정렬하는 것입니다. 그들이 일어날 때 도망 갈 것입니다. 이것은 최적이 아니므로 각 입력 목록에 숫자 255가있을 수 있으며이 기술을 사용하여 놓칠 수는 있지만 쉽습니다.

다른 접근법은 숫자를 256 개의 빈으로 히스토그램 화하는 것입니다. 눈에 띄는 빈은 그룹화해야하는 숫자를 나타냅니다. 그 후에, 나는 당신이 서열을 검색해야만한다고 생각합니다. 다시 말하지만, 입력을 정렬하면이 작업이 더 쉬워 질 것입니다.

각 목록에서 하나의 번호를 선택해야한다는 제약이 있습니다. 그래서 두 경우 모두 각 목록을 정렬 한 다음 중복을 제거 할 수 있습니다.

또한 나무를 사용하여 호프만 코드를 생성 할 수 있으므로 자동으로 올바른 답을 줄 수있는 마법 트리 구조가 있는지 궁금합니다.