비트 배열의 일반적인 용도는 무엇입니까?

Question

초보자 설명서의 비트 배열을 사용한 예제를 작성했습니다. 나는 그들이 무엇을 사용할 수 있는지, 그리고 어떤 공통적 인 데이터 구조가 무엇인지 알고 싶다. ("배열"은 꽤 느슨한 용어라고 가정한다.)

고마워.

Answer 1

는 Bit array 위키 백과 문서의 Applications 절에 나와있는 몇 가지가 있습니다

때문에 소형화

공간이나 효율 프리미엄이고, 비트 배열이 분야에서 다수의 애플리케이션이있다. 가장 일반적으로는 간단한 부울 플래그 그룹 또는 순서가 지정된 부울 값 시퀀스를 나타내는 데 사용됩니다.

위에서 언급 한 것처럼 비트 배열은 우선 순위 큐에 사용되며, 여기서 인덱스 k의 비트는 k가 큐에있는 경우에만 설정됩니다. 이 데이터 구조는 예를 들어 Linux 커널에서 사용되며 하드웨어에서 찾기 0에서부터 큰 이점을 얻습니다.

비트 어레이는 메모리 페이지, inode, 디스크 섹터 등의 할당에 사용될 수 있습니다. 이러한 경우 비트 맵이라는 용어가 사용될 수 있습니다. 그러나이 용어는 픽셀 당 여러 비트를 사용할 수있는 래스터 이미지를 나타내는 데 자주 사용됩니다.

비트 배열의 또 다른 응용 프로그램은 Bloom 필터입니다. Bloom 필터는 작은 공간에 큰 세트를 저장할 수있는 확률 적 세트 데이터 구조로, 작은 오류 확률을 교환합니다. 가양 성 또는 거짓 네거티브를 허용하는 비트 배열을 기반으로 확률 적 해시 테이블을 작성할 수도 있습니다.

비트 배열과 그 연산은 가능한 최소 공간에 가깝게 사용되는 간결한 데이터 구조를 구성하는 데 중요합니다. 이와 관련하여 n 번째 1 비트를 찾거나 특정 위치까지 1 비트 수를 계산하는 것과 같은 연산이 중요합니다.

비트 배열은 압축 된 데이터 스트림을 검사 할 때 유용한 추상화로, 바이트의 일부를 차지하거나 바이트 정렬되지 않은 요소가 포함되어있는 경우가 많습니다. 예를 들어, 단일 8 비트 문자의 압축 된 허프만 코딩 표현은 1에서 255 비트 길이가 될 수 있습니다.

정보 검색에서 비트 배열은 자주 사용되는 용어의 게시 목록을 나타내는 데 적합합니다. 엄격하게 증가하는 정수리스트에서 인접한 값 사이의 갭을 계산하고 단항 코딩을 사용하여 엔코 드하면 결과는 n이 목록에있는 경우에만 n 번째 위치에 1 비트가있는 비트 배열입니다. n의 갭의 내포 된 확률은 1/2n이다. 이것은 Golomb 코딩의 특수한 경우이며 매개 변수 M은 1입니다. 이 매개 변수는 일반적으로 -log (2-p)/log (1-p) ≤ 1 일 때만 선택되거나 대개이 용어는 문서의 38 % 이상에서 발생합니다.