나는 이진 파일에 연속적으로 저장된 정렬 된 32 비트 정수의 몇 가지 세트 인 색인을 작성하고 있습니다. 문제는이 파일이 상당히 커진다는 것입니다. 일부 압축 스키마를 추가하려고 생각했지만 그게 내 전문 지식에서 약간 벗어났습니다. 그래서 나는 압축 알고리즘이이 경우에 가장 잘 작동하는지 궁금해합니다. 또한이 인덱스는 룩업을 만드는 데 사용되므로 압축 해제 속도가 빨라야합니다.정렬 된 정수를 압축
임의의 32 비트 정수 (982346 ..., 3487623412 .. 등)가 아닌 서로 가깝게있는 정수 (예 : 1, 3, 4, 5, 9, 10 등 ...)를 저장하는 경우) 당신은 한 가지 수행 할 수 있습니다
이 예에서 등 2,1,1,4,1 ... 같은 것 인접한 숫자 사이의 차이를 (찾기)를 다음 허프만이 인코딩 번호.
원래 숫자 목록에 직접 적용하면 허프만 인코딩이 작동하지 않을 것이라고 생각합니다.
그러나 가까운 번호의 정렬 된 목록이있는 경우 확률은 호프만 인코딩을 통해 매우 좋은 압축률을 얻고 숫자 차이를 인코딩하여 LZW 알고리즘을 사용하는 것보다 더 좋은 비율 일 수 있습니다. 우편 라이브러리.
어쨌든이 흥미로운 질문을 게시 주셔서 감사합니다.
나는 Huffman coding이 비슷한 목적으로 (그리고 비교적 빠른 속도로 유사한 압축 비율을 가진 다른 알고리즘과 비교할 때) 매우 적절할 것이라고 생각한다.
편집 : 내 대답은 일반적인 포인터 일뿐입니다. Niyaz가 제안한 연속 숫자 간의 차이를 인코딩하는 것이 좋습니다. (그러나 목록이 이 아니거나이 아니거나 숫자의 간격이 매우 불규칙하면 일반 허프만 인코딩을 사용하는 것이 효과적 일 수는 없다고 생각합니다. 사실 LZW 또는 이와 유사한 것이이 경우 가장 좋을 것입니다. 매우 좋습니다.)
정수가 고밀도 또는 희소 방식으로 그룹화되어 있습니까? 정수는 당신이 압축 할 수있는 조밀 한 방법으로 그룹화하는 경우
[1, 4, 7, 9, 19, 42, 53, 55, 78, 80]
: 스파 스에 의해
[1, 2, 3, 4, 42, 43, 78, 79, 80, 81]
내가 말하는 겁니다 : 고밀도으로
내가 말하는 겁니다 3 개의 범위를 보관 유지하는 최초의 벡터 :
[(1, 4), (42, 43), (78, 81)]
40 % 압축입니다. 물론 데이터가 원래 데이터보다 100 % 더 많은 공간을 차지하므로이 알고리즘은 희소 데이터에서 제대로 작동하지 않습니다.
나 자신의 계획에 투자하기 전에 선반 밖에서 뭔가 늪지대를 사용하고 싶습니다.
Java에서는 예를 들어 GZIPOutputStream을 gzip 압축을 적용 할 수 있습니다.
정수 목록의 조건은 약간 다르지만 질문 Compression for a unique stream of data은 도움이 될 수있는 몇 가지 방법을 제안합니다.
데이터를 start 및 일련 번호 offset으로 사전 필터링하는 것이 좋습니다. 오프셋이 안정적으로 작다는 것을 안다면 4 바이트가 아닌 1 또는 2 바이트로 인코딩 할 수도 있습니다. 모르는 경우 각 오프셋은 여전히 4 바이트가 될 수 있지만 작은 차이가 발생하므로 원본 정수를 저장할 때보 다 더 많은 반복이 발생합니다.
미리 필터링 한 후 gzip 또는 zlib와 같은 바이트 수준에서 작동하는 원하는 압축 스키마를 통해 출력을 실행하십시오. 실제로는 좋은 작업을 수행 할 수 있습니다.
아마도 차이점 인을 연속 된 32 비트 정수 사이에 16 비트 정수로 저장할 수 있습니다.
당신이 발견 한 것처럼 N 32 비트 정수의 정렬 된 시퀀스에는 32 * N 비트의 데이터가 없습니다. 이것은 놀라운 일이 아닙니다. 중복이 없다고 가정 할 때 모든 정렬 된 시퀀스에는 N! 동일한 정수를 포함하는 정렬되지 않은 시퀀스.
이제 정렬 된 순서에서 제한된 정보를 어떻게 활용합니까? 많은 압축 알고리즘은 일반적인 입력 값에 대해 더 짧은 비트 스트링을 사용하여 압축합니다 (허프만은이 트릭 만 사용함). 몇몇 포스터는 이미 수의 차이를 계산하고 그 차이를 압축 할 것을 제안했습니다. 그들은 그것이 일련의 작은 숫자 일 것이라고 가정하며, 그 중 다수는 동일한 것입니다. 이 경우 차이 시퀀스는 대부분의 알고리즘에 의해 잘 압축됩니다.
그러나 피보나치 시퀀스를 사용하십시오. 그건 분명히 정렬 된 정수입니다. F (n)과 F (n + 1)의 차이는 F (n-1)입니다. 따라서 차이점의 순서를 압축하는 것은 시퀀스 자체를 압축하는 것과 같습니다. 전혀 도움이되지 않습니다!
그래서 우리가 정말로 필요로하는 것은 입력 데이터의 통계 모델입니다. 주어진 시퀀스 N [0] ... N [x], N [x + 1]의 확률 분포는 얼마인가? 시퀀스가 정렬 될 때 P (N [x + 1] < N [x]) = 0임을 알 수 있습니다. 차분/허프만 기반 솔루션은 P (N [x + 1] - N [x] = d)가 작은 양수 d와 x와는 별개로 매우 높다고 가정하기 때문에 작동합니다. 작은 차이. 다른 모델을 제공 할 수 있다면 최적화 할 수 있습니다.
빠른 임의 액세스 조회가 필요한 경우 Niyaz가 제안한 차이의 허프만 인코딩은 이야기의 절반에 불과합니다. n 번째 숫자를 쉽게 추출 할 수 있도록 일종의 페이징/색인 체계가 필요할 수도 있습니다.
이 작업을 수행하지 않으면 n 번째 숫자를 추출하는 것은 O (n) 작업이므로 이후에 번호를 찾기 전에 파일의 절반을 해프먼 해독해야합니다. 페이지 오프셋을 저장하는 오버 헤드와 조회 속도를 조화 시키려면 페이지 크기를 신중하게 선택해야합니다.
MSalters의 답변은 흥미롭지 만 제대로 분석하지 않으면 혼란 스러울 수 있습니다. 32 비트에 맞는 피보나치 숫자는 47 개뿐입니다.
하지만 그는 압축 할 패턴을 찾기 위해 일련의 증분을 분석하여 문제를 올바르게 해결하는 방법에 대해 집중하고 있습니다.
중요 사항 : a) 반복되는 값이 있습니까? 그렇다면 얼마나 자주? (중요하다면 그것을 압축의 일부로 만들어라. 그렇지 않으면 예외가된다.) b) 준 무작위 적으로 보입니까?또한 적절한 평균 증가분을 발견 할 수 있기 때문에 좋은 결과를 얻을 수 있습니다.
숫자의 특정 임계 값에 도달 한 후에는 반복되는 패턴이되어 언제 알 수 있습니다. 따라서 나는 Niyaz가 제안한 알고리즘을 사용하는 것이 좋을 것이라고 생각합니다. 실제로 –
예. 그러나 Simonn은 순진한 구현은 O (n)쪽으로 임의 액세스를 가져올 수 있다고 언급했습니다. 또한 도움이되지 않는 배포판이있을 수 있다고 생각합니다. 적응 형 허프만이 처리 할 수 있습니다. 그리고 마지막으로, 매우 자주 RLE (증가분에 따라)가 극소수의 코드 행에서 작업을 수행합니다. – alecco
정렬 된 정수? 숫자 대신 범위 [0-1000]을 저장할 수 있습니까? 전체 32 비트 범위를 사용합니까? 여러 개의 숫자를 하나의 정수로 묶을 수 있습니까? – JeffFoster