비트 배열의 대안은 무엇입니까?
-
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비트만 저장할 수 있습니다.그만한 가치가 없습니다.
그럼에도 불구하고 실제로 유용한 데이터가 실제로 무작위일 가능성은 거의 없어 보입니다.데이터에 더 많은 구조가 있는 경우 더 낙관적인 대답이 있을 수 있습니다.