비트 배열의 대안은 무엇입니까?

https://stackoverflow.com/questions/36106

09-06-2019
|

문제

나는 천만 비트 정도의 비트 배열을 생성하는 정보 검색 응용 프로그램을 가지고 있습니다.배열의 "설정" 비트 수는 모두 지우기부터 모두 설정까지 매우 다양합니다.현재 저는 간단한 비트 배열(java.util.BitSet), 따라서 각 비트 배열은 몇 메가바이트를 차지합니다.

내 계획은 첫 번째 카디널리티를 살펴보는 것입니다. N 그런 다음 나머지 부분에 사용할 데이터 구조를 결정합니다.분명히 일부 데이터 구조는 매우 희박한 비트 배열에 더 좋고, 다른 데이터 구조는 비트의 대략 절반이 설정된 경우에 더 좋습니다(대부분의 비트가 설정된 경우 부정을 사용하여 희소한 0 집합으로 처리할 수 있습니다).

각 극단에서는 어떤 구조가 좋을 수 있습니까?
중간에 있나요?

다음은 몇 가지 제약 조건이나 힌트입니다.

비트는 인덱스 순서대로 한 번만 설정됩니다.
100% 정확도가 필요하므로 Bloom 필터와 같은 것만으로는 충분하지 않습니다.
세트가 구축된 후에는 "세트" 비트를 효율적으로 반복할 수 있어야 합니다.
비트는 무작위로 분산되므로 실행 길이 인코딩 알고리즘은 단순한 비트 인덱스 목록보다 훨씬 나을 가능성이 없습니다.
메모리 활용도를 최적화하려고 하는데 속도가 여전히 느려집니다. 일부 무게.

오픈 소스 Java 구현이 있으면 도움이 되지만 꼭 필요한 것은 아닙니다.저는 기본에 더 관심이 있어요.

해결책

데이터가 실제로 무작위가 아닌 이상 그리고 대칭적인 1/0 분포를 가지면 이는 단순히 무손실 데이터 압축 문제가 되며 흑백에 사용되는 CCITT 그룹 3 압축과 매우 유사합니다(예:바이너리) 팩스 이미지.CCITT 그룹 3은 허프만 코딩 체계를 사용합니다.FAX의 경우 고정된 허프만 코드 세트를 사용하지만 주어진 데이터 세트에 대해 각 데이터 세트에 대해 특정 코드 세트를 생성하여 달성된 압축률을 향상시킬 수 있습니다.암시한 대로 비트에 순차적으로 액세스하기만 하면 되는 한 이는 매우 효율적인 접근 방식이 될 것입니다.무작위 액세스는 몇 가지 추가 문제를 야기하지만 배열의 다양한 오프셋 지점에 대한 이진 검색 트리 인덱스를 생성하여 원하는 위치에 가까이 다가간 다음 거기에서 들어갈 수 있습니다.

메모:허프만 방식은 1/0 분포가 완벽하게 균일하지 않은 한 데이터가 무작위인 경우에도 여전히 잘 작동합니다.즉, 분포가 고르지 않을수록 압축률이 좋아집니다.

마지막으로, 비트가 정말로 균일하게 분포된 무작위라면 다음과 같습니다. 씨.클로드 섀넌, 어떤 구성표를 사용해도 상당한 양을 압축할 수 없습니다.

다른 팁

허프만 코딩 대신 범위 인코딩을 사용하는 것이 좋습니다.일반적으로 범위 인코딩은 허프만 코딩보다 비대칭성을 더 효과적으로 활용할 수 있지만 이는 특히 알파벳 크기가 너무 작을 때 더욱 그렇습니다.실제로 "기본 알파벳"이 단순히 0과 1인 경우 Huffman이 압축을 얻을 수 있는 유일한 방법은 해당 기호를 결합하는 것입니다. 이것이 바로 범위 인코딩이 수행하는 작업이며 더 효과적으로 수행됩니다.

너무 늦었을 수도 있지만 희소 비트 배열(무손실) 및 시도 기반의 기타 데이터 유형을 위한 매우 빠르고 메모리 효율적인 라이브러리가 있습니다.보다 주디 배열

답변해주셔서 감사합니다.이것이 올바른 방법을 동적으로 선택하기 위해 시도할 것입니다.

처음엔 다 모아볼게 N 일반적인 비트 배열에 도달하고 이 샘플의 대칭성을 기반으로 세 가지 방법 중 하나를 선택합니다.

샘플이 비대칭 인 경우 목록에 인덱스를 세트 비트 (또는 다음 비트까지의 거리)에 간단히 저장하겠습니다.
샘플이 매우 대칭이라면 기존 비트 어레이를 계속 사용하겠습니다.
샘플이 중간 정도 대칭이라면 Huffman Coding과 같은 무손실 압축 방법을 사용하겠습니다. Inscitekjeff가 제안합니다.

비대칭, 중간 및 대칭 영역 사이의 경계는 필요한 공간과 균형을 이루는 다양한 알고리즘에 필요한 시간에 따라 달라지며, 여기서 시간 대 공간의 상대적 값은 조정 가능한 매개변수입니다.허프만 코딩에 필요한 공간은 대칭의 함수이며 테스트를 통해 이를 프로파일링하겠습니다.또한 구현에 필요한 시간을 결정하기 위해 세 가지 방법을 모두 테스트하겠습니다.

중간 압축 방법이 항상 목록이나 비트 배열 또는 둘 다보다 나을 가능성이 있습니다(실제로 저는 희망합니다).어쩌면 나는 더 높거나 더 낮은 대칭성에 적합한 허프만 코드 세트를 선택함으로써 이를 장려할 수 있습니다.그러면 시스템을 단순화하고 두 가지 방법만 사용할 수 있습니다.

압축에 대한 또 하나의 생각:

비트 배열이 너무 길지 않으면 다음을 적용해 볼 수 있습니다. 버로우즈-휠러 변환 Huffman과 같은 반복 인코딩을 사용하기 전에.순진한 구현에서는 압축을 풀 때 O(n^2) 메모리가 필요하고 압축을 푸는 데 O(n^2 log n) 시간이 소요됩니다. 지름길도 거의 확실히 있습니다.그러나 데이터에 순차적 구조가 있다면 이는 허프만 인코딩에 큰 도움이 될 것입니다.

또한 해당 아이디어를 한 번에 하나의 블록에 적용하여 시간/메모리 사용량을 보다 실용적으로 유지할 수도 있습니다.한 번에 하나의 블록을 사용하면 순차적으로 읽고 쓰는 경우 대부분의 데이터 구조를 항상 압축된 상태로 유지할 수 있습니다.

간단한 무손실 압축이 좋은 방법입니다.검색 가능하게 만들려면 상대적으로 작은 블록을 압축하고 블록 배열에 대한 인덱스를 만들어야 합니다.이 인덱스에는 각 블록의 시작 비트에 대한 비트 오프셋이 포함될 수 있습니다.

실제로 많은 공간을 절약할 수 없다는 빠른 조합 증명:

총 n 비트 중 1로 설정된 n/2 비트의 임의 하위 집합이 있다고 가정합니다.(n 선택 n/2) 가능성이 있습니다.사용 스털링의 공식, 이는 대략 2^n / sqrt(n) * sqrt(2/pi)입니다.모든 가능성의 가능성이 동일하다면 가능성이 높은 선택을 더 짧게 표현하는 방법은 없습니다.따라서 log_2(n은 n/2 선택) 비트가 필요하며 이는 약 n - (1/2)log(n) 비트입니다.

이는 메모리 절약 효과가 좋지 않습니다.예를 들어 n=2^20(1meg)으로 작업하는 경우 약 10비트만 저장할 수 있습니다.그만한 가치가 없습니다.

그럼에도 불구하고 실제로 유용한 데이터가 실제로 무작위일 가능성은 거의 없어 보입니다.데이터에 더 많은 구조가 있는 경우 더 낙관적인 대답이 있을 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow