비트맵이 있는 비트 트리
Bitwise trie with bitmapbitwise trie는 child-branch가 있는 각 노드가 하나 이상의 키 비트의 비트 시퀀스를 나타내는 특별한 형태의 trie이다.비트맵이 있는 비트 트리에는 유효한 하위 분기를 나타내기 위해 비트맵을 사용한다.
시도 및 비트 시도
트라이는 검색 트리의 일종으로, 예를 들어 B-트리와는 달리 키가 노드에 저장되지 않고 잎에 저장된다.열쇠는 나무 구조물에 걸쳐 분산되어 있다."classic" trie에서, 자식 브런치가 있는 각 노드는 키의 한 위치(문자) 알파벳의 하나의 기호를 나타낸다.
비트적 시도에서 키는 일부 이진표현의 비트시퀀스로 취급되며, 하위분석이 있는 각 노드는 이진수(하위시퀀스는 1비트만 포함) 또는 n-ary 트리(하위시퀀스는 복수비트를 포함함)를 형성하기 위한 이 비트시퀀스의 하위시퀀스 값을 나타낸다.
"클래식" 시도와 비트적 시도 간의 차이를 설명하는 예를 들면 다음과 같다.숫자들을 키로 사용할 경우, 3개의 알파벳은 기호 '0'으로 구성될 수 있다.'9'는 십진수 시스템에서 숫자의 숫자를 나타내며, 노드는 최대 10개의 가능한 자식을 가질 수 있다.
물리적 데이터 구조와 같은 트라이를 구현하기 위한 여러 가지 직선적 접근방식이 있다.2를 명시하려면:
- 노드는 소수점 예에서 알파벳 })의 각 기호에 대해 하위 포인터의 배열을 가진 것으로 나타낼 수 있다. 하면 키의 길이가 되는 과와) O(M O(M 조회 시간이 주어진다.그러나 각각의 노드가 모든 가능한 어린이 기호들을 위한 공간을 보존하기 때문에, 비록 그 경로를 실현하는 열쇠가 없더라도, 이것은 공간 효율적이지 않다.
- 노드는 (기호, 자식 포인터) 튜플 목록을 포함하며, 이 목록을 통해 이진 검색을 허용하도록 기호별로 정렬되어 있다.이것은 공간 효율성이 더 좋지만 지금 조회 시간은 O ( M 입니다 이상적인 트라이에는 저장된 키의 양과 독립된 액세스 시간이 있다.
예를 들어, 키가 유니코드 문자의 문자열인 경우, 이러한 접근법은 더 큰 알파벳에 대해 악화된다.키를 비트 시퀀스로 처리하면 노드당 고정 카디널리티를 가질 수 있다.
비트맵이 있는 비트 트리
백웰은 AMT(Array Mapped Tree)라는 이름의 시도를 위한 시간과 공간 효율적인 솔루션을 제시했다.HAMT(Hash Array Mapped trie)는 AMT를 기반으로 한다.컴팩트 트라이 노드 표현은 모든 유효한 분기를 표시하기 위해 비트맵을 사용한다. 비트맵으로 비트 트라이를 표시한다.AMT는 노드당 8개의 32비트 비트맵을 사용하여 노드당 8비트 시퀀스를 나타낼 수 있는 256에이리어 트리어를 나타낸다.64비트 CPU(64비트 컴퓨팅)의 경우, 6비트 시퀀스를 나타낼 수 있는 노드당 64비트 비트맵이 하나만 있는 64-ari 트리(트리)가 변동된다.
주어진 6비트 값에 대한 노드의 자식 포인터의 색인을 결정하려면 선행 자식 포인터의 양을 계산해야 한다.이를 상당히 효율적으로 구현할 수 있는 것으로 나타났다.
노드 트래버설
장기의 비트맵 = 밈[nodeIdx]; 장기의 비트포스 = 1L << 가치를 매기다; // 6비트 값 만일 ((비트맵 & 비트포스) == 0) 돌아오다 거짓의; // 찾을 수 없음 장기의 childNodeIdx = 밈[nodeIdx + 1 + 긴.비트카운트(비트맵 & (비트포스 - 1))]; 현재 노드 색인에 기반한 인덱스를 찾기 위한 오프셋은 비트맵에서 목표 위치 앞에 비트맵에 비트맵에 설정된 최소 비트 양과 비트맵에 대한 1을 더한 값이다.최소 중요 비트 세트의 양은 단순 비트 연산 및 자바에서 Long.bitCount()로 사용할 수 있는 세트 비트 수를 결정하는 CTPOP(카운트 모집단) 연산을 사용하여 일정 시간 복잡도로 효율적으로 계산할 수 있다.CTPOP 자체는 "비트랙"을 사용하여 상당히 효율적으로 구현될 수 있으며[2], 현대의 많은 CPU는 컴파일러가 본질적인 기능으로 취급하는 전용 명령으로 CTPOP을 제공하기도 한다.
CTPOP 비트핵 구현
인트로 비트카운트(장기의 x) x -= ((i >>> 1) & 0x55555555555555555555l); x = (x & 0x33333333333333333333333333333333l) + ((x >>> 2) & 0x33333333333333333333333333333333l); x = (x + (x >>> 4)) & 0x0f0f0f0f0f0f0f0f0ff0ffL; x += (x >>> 8); x += (x >>> 16); x += (x >>> 32); 돌아오다 x & 0x7f; 데이터베이스 및 정보 검색 응용 프로그램의 범용 인덱스에 이 원칙을 사용하는 방법은 에 설명되어 있다.[3]32비트-Integer 세트의 구현을 위해 이러한 개념을 증명하는 전문적이고 단순한 솔루션이 아래에 제시되어 있다.
구현 예제 설정
물리적 데이터 구조
이 예제에서 비트맵을 사용한 비트 트리에 대한 구현에서, 노드는 긴 (64비트) 정수의 배열로 배치된다.노드는 해당 배열의 위치(인덱스)로 식별된다.루트 노드의 인덱스는 트라이의 루트를 표시한다.
노드는 해당 어레이의 사용되지 않는 공간에서 할당되며, 필요한 경우 어레이를 확장한다.또한, 교체된 노드들은 무료 리스트에 수집되고 그 공간은 재활용된다.이러한 재활용이 없다면 데이터 구조를 사용하여 기존의 루트 인덱스를 유지하고 기존 노드를 재정의하지 않고 항상 변경된 노드의 복사본을 생성함으로써 지속적인 데이터 구조를 구현할 수 있다.
리프 노드 인라인:leaf 노드에 대한 하위 포인터를 갖는 대신, leaf 노드 자체의 비트맵이 저장된다.
공중의 계급 비비트리셋 { 장기의[] 밈; 장기의[] 자유 목록; 장기의 freeIdx; 장기의 뿌리를 내리다; 장기의 수를 세다; // 최대 노드 크기는 1(비트맵) + 64(하위 포인터 또는 리프 값) + 어레이가 0 기반인 경우 1 최종의 정태의 인트로 FREE_LIST_SIZE = 1+64+1; 최종의 정태의 인트로 알려진_EMENTY_NODE = 0; 최종의 정태의 인트로 알려진_DELETED_NODE = 1; 최종의 정태의 인트로 헤더_사이즈 = 2; // 알려진_EMENTY_NODE, 알려진_DELETED_NODE 공중의 비비트리셋(인트로 사이즈를 맞추다) { 밈 = 새로운 장기의[사이즈를 맞추다]; 자유 목록 = 새로운 장기의[FREE_LIST_SIZE]; freeIdx = 헤더_사이즈; 뿌리를 내리다 = 알려진_EMENTY_NODE; 수를 세다 = 0; } 사유의 장기의 할당하다(인트로 사이즈를 맞추다) { 장기의 무료의 = 자유 목록[사이즈를 맞추다]; 만일 (무료의 != 0) { // 무료 목록, 리링크 및 리턴 헤드에서 사용 가능한 요청 크기 자유 목록[사이즈를 맞추다] = 밈[(인트로) 무료의]; 돌아오다 무료의; } 다른 { // 확장 필요? 만일 (freeIdx + 사이즈를 맞추다 > 밈.길이) { // 25% 증가, 이 정도면 충분하다는 것을 보장 인트로 커러사이즈 = 밈.길이; 인트로 뉴사이즈 = 커러사이즈 + 수학.맥스.(커러사이즈 / 4, 사이즈를 맞추다); 밈 = 배열.카피오프(밈, 뉴사이즈); } 장기의 idx = freeIdx; freeIdx += 사이즈를 맞추다; 돌아오다 idx; } } 사유의 장기의 할당하다삽입하다(장기의 nodeIdx, 인트로 사이즈를 맞추다, 인트로 차일드아이덱스) { 장기의 newNodeRef = 할당하다(사이즈를 맞추다 + 1); 인트로 a = (인트로) newNodeRef; 인트로 b = (인트로) nodeIdx; // 어린이를 위한 공백이 있는 경우 을 위해 (인트로 j = 0; j < 차일드아이덱스; j++) 밈[a++] = 밈[b++]; a++; // 삽입됨 을 위해 (인트로 j = 차일드아이덱스; j < 사이즈를 맞추다; j++) 밈[a++] = 밈[b++]; 할당을 해제하다(nodeIdx, 사이즈를 맞추다); 돌아오다 newNodeRef; } 사유의 장기의 allocate(장기의 nodeIdx, 인트로 사이즈를 맞추다, 인트로 차일드아이덱스) { 장기의 newNodeRef = 할당하다(사이즈를 맞추다 - 1); // 아이가 제거된 상태에서 복사 인트로 a = (인트로) newNodeRef; 인트로 b = (인트로) nodeIdx; 을 위해 (인트로 j = 0; j < 차일드아이덱스; j++) 밈[a++] = 밈[b++]; b++; // 제거됨 을 위해 (인트로 j = 차일드아이덱스 + 1; j < 사이즈를 맞추다; j++) 밈[a++] = 밈[b++]; 할당을 해제하다(nodeIdx, 사이즈를 맞추다); 돌아오다 newNodeRef; } 사유의 공허하게 하다 할당을 해제하다(장기의 idx, 인트로 사이즈를 맞추다) { 만일 (idx == 알려진_EMENTY_NODE) 돌아오다; // 알려진 빈 노드 유지 // 프리리스트에 추가 밈[(인트로) idx] = 자유 목록[사이즈를 맞추다]; 자유 목록[사이즈를 맞추다] = idx; } 사유의 장기의 createLeaf(바이트[] 핵심을, 인트로 떨어져서, 인트로 렌) { 장기의 newNodeRef = 할당하다(2); 인트로 a = (인트로) newNodeRef; 밈[a++] = 1L << 핵심을[렌 - 2]; 밈[a] = 1L << 핵심을[렌 - 1]; // 값 렌 -= 3; 하는 동안에 (렌 >= 떨어져서) { 장기의 newParentNodeRef = 할당하다(2); a = (인트로) newParentNodeRef; 밈[a++] = 1L << 핵심을[렌--]; 밈[a] = newNodeRef; newNodeRef = newParentNodeRef; } 돌아오다 newNodeRef; } 사유의 장기의 삽입 차일드(장기의 nodeRef, 장기의 비트맵, 장기의 비트포스, 인트로 idx, 장기의 가치를 매기다) { 인트로 사이즈를 맞추다 = 긴.비트카운트(비트맵); 장기의 newNodeRef = 할당하다삽입하다(nodeRef, 사이즈를 맞추다 + 1, idx + 1); 밈[(인트로) newNodeRef] = 비트맵 비트포스; 밈[(인트로) newNodeRef+ 1 + idx] = 가치를 매기다; 돌아오다 newNodeRef; } 사유의 장기의 제거차일드(장기의 nodeRef, 장기의 비트맵, 장기의 비트포스, 인트로 idx) { 인트로 사이즈를 맞추다 = 긴.비트카운트(비트맵); 만일 (사이즈를 맞추다 > 1) { // 노드에는 여전히 다른 자식/잎이 있음 장기의 newNodeRef = allocate(nodeRef, 사이즈를 맞추다 + 1, idx + 1); 밈[(인트로) newNodeRef] = 비트맵 & ~비트포스; 돌아오다 newNodeRef; } 다른 { // 노드가 이제 비어 있으므로 제거하십시오. 할당을 해제하다(nodeRef, 사이즈를 맞추다 + 1); 돌아오다 알려진_DELETED_NODE; } } 공중의 장기의 사이즈를 맞추다() { 돌아오다 수를 세다; } } 작업 설정
키 포함
키가 세트의 일부인 경우 get method tests.키는 바이트[]로 전달되며, 여기서 각 바이트는 키의 6비트 비트 시퀀스 하나를 나타내므로 바이트당 8비트 중 6비트만 사용된다.
공중의 부울 얻다(바이트[] 핵심을, 인트로 렌) { 만일 (뿌리를 내리다 == 알려진_EMENTY_NODE) 돌아오다 거짓의; 장기의 nodeRef = 뿌리를 내리다; 인트로 떨어져서 = 0; 을 위해 (;;) { 장기의 비트맵 = 밈[(인트로) nodeRef]; 장기의 비트포스 = 1L << 핵심을[떨어져서++]; // ++에 주의하십시오. 만일 ((비트맵 & 비트포스) == 0) 돌아오다 거짓의; // 찾을 수 없음 장기의 가치를 매기다 = 밈[(인트로) nodeRef + 1 + 긴.비트카운트(비트맵 & (비트포스 - 1))]; 만일 (떨어져서 == 렌 - 1) { // 잎사귀 장기의 비트포즈리프 = 1L << 핵심을[떨어져서]; 돌아오다 ((가치를 매기다 & 비트포즈리프) != 0); } 다른 { // 자식 포인터 nodeRef = 가치를 매기다; } } } 키 설정(추가)
공중의 부울 세트(바이트[] 핵심을, 인트로 렌) { 장기의 nodeRef = 세트(뿌리를 내리다, 핵심을, 0, 렌); 만일 (nodeRef != 알려진_EMENTY_NODE) { //는 변화를 나타낸다. 수를 세다++; 뿌리를 내리다 = nodeRef; 돌아오다 진실의; } 다른 돌아오다 거짓의; } 사유의 장기의 세트(장기의 nodeRef, 바이트[] 핵심을, 인트로 떨어져서, 인트로 렌) { 장기의 비트맵 = 밈[(인트로) nodeRef]; 장기의 비트포스 = 1L << 핵심을[떨어져서++]; // ++에 주의하십시오. 인트로 idx = 긴.비트카운트(비트맵 & (비트포스 - 1)); 만일 ((비트맵 & 비트포스) == 0) { // 아직 아이가 없음 장기의 가치를 매기다; 만일 (떨어져서 == 렌 - 1) 가치를 매기다 = 1L << 핵심을[떨어져서]; 다른 가치를 매기다 = createLeaf(핵심을, 떨어져서, 렌); 돌아오다 삽입 차일드(nodeRef, 비트맵, 비트포스, idx, 가치를 매기다); } 다른 { // 현재 아동 장기의 가치를 매기다 = 밈[(인트로) nodeRef + 1 + idx]; 만일 (떨어져서 == 렌 - 1) { // 잎사귀 장기의 비트포즈리프 = 1L << 핵심을[떨어져서]; 만일 ((가치를 매기다 & 비트포즈리프) == 0) { // 리프 비트맵 업데이트 밈[(인트로) nodeRef + 1 + idx] = 가치를 매기다 비트포즈리프; 돌아오다 nodeRef; } 다른 // 키가 이미 있음 돌아오다 알려진_EMENTY_NODE; } 다른 { // 잎이 아닌, 재귀 장기의 childNodeRef = 가치를 매기다; 장기의 NewChildNodeRef = 세트(childNodeRef, 핵심을, 떨어져서, 렌); 만일 (NewChildNodeRef == 알려진_EMENTY_NODE) 돌아오다 알려진_EMENTY_NODE; 만일 (NewChildNodeRef != childNodeRef) 밈[(인트로) nodeRef + 1 + idx] = NewChildNodeRef; 돌아오다 nodeRef; } } } 키 지우기(제거)
공중의 부울 분명한(바이트[] 핵심을, 인트로 렌) { 장기의 nodeRef = 분명한(뿌리를 내리다, 핵심을, 0, 렌); 만일 (nodeRef != 알려진_EMENTY_NODE) { 수를 세다--; 만일 (nodeRef == 알려진_DELETED_NODE) 뿌리를 내리다 = 알려진_EMENTY_NODE; 다른 뿌리를 내리다 = nodeRef; 돌아오다 진실의; } 다른 돌아오다 거짓의; } 공중의 장기의 분명한(장기의 nodeRef, 바이트[] 핵심을, 인트로 떨어져서, 인트로 렌) { 만일 (뿌리를 내리다 == 알려진_EMENTY_NODE) 돌아오다 알려진_EMENTY_NODE; 장기의 비트맵 = 밈[(인트로) nodeRef]; 장기의 비트포스 = 1L << 핵심을[떨어져서++]; // ++에 주의하십시오. 만일 ((비트맵 & 비트포스) == 0) { // 하위 키가 없음, 키를 찾을 수 없음 돌아오다 알려진_EMENTY_NODE; } 다른 { // 현재 아동 인트로 idx = 긴.비트카운트(비트맵 & (비트포스 - 1)); 장기의 가치를 매기다 = 밈[(인트로) nodeRef + 1 + idx]; 만일 (떨어져서 == 렌 - 1) { // 잎사귀 장기의 비트포즈리프 = 1L << 핵심을[떨어져서]; 만일 ((가치를 매기다 & 비트포즈리프) == 0) // 키가 없음 돌아오다 알려진_EMENTY_NODE; 다른 { // 잎으로 비트를 지우다 가치를 매기다 = 가치를 매기다 & ~비트포즈리프; 만일 (가치를 매기다 != 0) { // leaf에 아직 비트 몇 개가 설정되어 있으므로, leaf는 유지하되 업데이트하십시오. 밈[(인트로) nodeRef + 1 + idx] = 가치를 매기다; 돌아오다 nodeRef; } 다른 돌아오다 제거차일드(nodeRef, 비트맵, 비트포즈리프, idx); } } 다른 { // 잎사귀가 아닌 장기의 childNodeRef = 가치를 매기다; 장기의 NewChildNodeRef = 분명한(childNodeRef, 핵심을, 떨어져서, 렌); 만일 (NewChildNodeRef == 알려진_EMENTY_NODE) 돌아오다 알려진_EMENTY_NODE; 만일 (NewChildNodeRef == 알려진_DELETED_NODE) 돌아오다 제거차일드(nodeRef, 비트맵, 비트포스, idx); 만일 (NewChildNodeRef != childNodeRef) 밈[(인트로) nodeRef + 1 + idx] = NewChildNodeRef; 돌아오다 nodeRef; } } } } 연산자 설정
교차로 (및), 조합 (또는) 및 차이 (마이너스)에 대한 연산자를 아래와 같이 플라이웨이트 패턴을 사용하여 설정할 수 있다.
인터페이스는 운영자의 물리적 노드와 "가상" 결과 노드를 나타낸다.이 인터페이스의 인스턴스는 3회 통과 중에 요청 시 생성된다.둘 이상의 연산자를 포함하는 복합 표현식은 연산자가 다른 연산자의 인수(입력)로 사용될 수 있으므로 이들 연산자를 결합하여 직접 표현할 수 있다.
플라이급 인터페이스
공중의 접점 BBTriieNode { 공중의 장기의 getBitMap(); 공중의 장기의 getBitMapLafe(장기의 비트포스); 공중의 BBTriieNode getChildNode(장기의 비트포스); } 공중의 정태의 계급 BBTrieNodeMem 기구들 BBTriieNode { 장기의 nodeRef; 장기의[] 밈; BBTrieNodeMem 어린아이의; 공중의 BBTrieNodeMem(장기의 nodeRef, 장기의[] 밈) { 이.nodeRef = nodeRef; 이.밈 = 밈; } @오버라이드 공중의 장기의 getBitMap() { 돌아오다 밈[(인트로) nodeRef]; } @오버라이드 공중의 장기의 getBitMapLafe(장기의 비트포스) { 인트로 idx = 긴.비트카운트(getBitMap() & (비트포스 - 1)); 장기의 가치를 매기다 = 밈[(인트로) nodeRef + 1 + idx]; 돌아오다 가치를 매기다; } @오버라이드 공중의 BBTriieNode getChildNode(장기의 비트포스) { 인트로 idx = 긴.비트카운트(getBitMap() & (비트포스 - 1)); 장기의 가치를 매기다 = 밈[(인트로) nodeRef + 1 + idx]; 돌아오다 새로운 BBTrieNodeMem(가치를 매기다, 밈); } } 교차로(AND)
교차로 운영자는 하위 표현에서도 자동으로 가지치기 작업을 하기 때문에 매우 효율적이다.비트맵과 비트 AND 연산을 통해 결과를 미리 확인할 수 있으므로 관련되지 않은 하위 노드에 액세스할 필요가 없다.For example, calculating , the subexpression would not be materialized as intermediate result.
공중의 정태의 계급 BBTrieAnd 기구들 BBTriieNode { BBTriieNode 노드A; BBTriieNode 노드B; 장기의 비트맵A; 장기의 비트맵B; 공중의 BBTrieAnd(BBTriieNode 노드A, BBTriieNode 노드B) { 이.노드A = 노드A; 이.노드B = 노드B; 비트맵A = 노드A.getBitMap(); 비트맵B = 노드B.getBitMap(); } 공중의 장기의 getBitMap() { 돌아오다 비트맵A & 비트맵B; // 이렇게 하면 최적화가 잘 된다(prunning) } 공중의 장기의 getBitMapLafe(장기의 비트포스) { 돌아오다 노드A.getBitMapLafe(비트포스) & 노드B.getBitMapLafe(비트포스); } 공중의 BBTriieNode getChildNode(장기의 비트포스) { BBTriieNode childNodea = 노드A.getChildNode(비트포스); BBTriieNode childNodeB = 노드B.getChildNode(비트포스); 돌아오다 새로운 BBTrieAnd(childNodea, childNodeB); } } 조합(OR)
공중의 정태의 계급 비비티오르 기구들 BBTriieNode { BBTriieNode 노드A; BBTriieNode 노드B; 장기의 비트맵A; 장기의 비트맵B; 공중의 비비티오르(BBTriieNode 노드A, BBTriieNode 노드B) { 이.노드A = 노드A; 이.노드B = 노드B; 비트맵A = 노드A.getBitMap(); 비트맵B = 노드B.getBitMap(); } 공중의 장기의 getBitMap() { 돌아오다 비트맵A 비트맵B; } 공중의 장기의 getBitMapLafe(장기의 비트포스) { 돌아오다 노드A.getBitMapLafe(비트포스) 노드B.getBitMapLafe(비트포스); } 공중의 BBTriieNode getChildNode(장기의 비트포스) { 만일 ((비트맵A & 비트포스) != 0) { BBTriieNode childNodea = 노드A.getChildNode(비트포스); 만일 ((비트맵B & 비트포스) != 0) { BBTriieNode childNodeB = 노드B.getChildNode(비트포스); 돌아오다 새로운 비비티오르(childNodea, childNodeB); } 다른 돌아오다 childNodea; // 최적화, 더 이상 또는 노드가 필요하지 않음 } 다른 { BBTriieNode childNodeB = 노드B.getChildNode(비트포스); 돌아오다 childNodeB; // 최적화, 더 이상 또는 노드가 필요하지 않음 } } } 차이(MINUS)
공중의 정태의 계급 비비트리미너스 기구들 BBTriieNode { BBTriieNode 노드A; BBTriieNode 노드B; 장기의 비트맵A; 장기의 비트맵B; 공중의 비비트리미너스(BBTriieNode 노드A, BBTriieNode 노드B) { 이.노드A = 노드A; 이.노드B = 노드B; 비트맵A = 노드A.getBitMap(); 비트맵B = 노드B.getBitMap(); } 공중의 장기의 getBitMap() { 돌아오다 비트맵A; // 여기서 비트맵B는 유용하지 않음 } 공중의 장기의 getBitMapLafe(장기의 비트포스) { 장기의 ChildbitMapA = 노드A.getBitMapLafe(비트포스); 만일 ((비트맵B & 비트포스) == 0) 돌아오다 ChildbitMapA; 장기의 ChildbitMapB = 노드B.getBitMapLafe(비트포스); 돌아오다 ChildbitMapA & ~ChildbitMapB; } 공중의 BBTriieNode getChildNode(장기의 비트포스) { BBTriieNode childNodea = 노드A.getChildNode(비트포스); 만일 ((비트맵B & 비트포스) == 0) 돌아오다 childNodea; // 최적화, 더 이상 마이너스 노드가 필요하지 않음 BBTriieNode childNodeB = 노드B.getChildNode(비트포스); 돌아오다 새로운 비비트리미너스(childNodea, childNodeB); } } 범위
가상 노드 접근방식을 사용하면 가상 트리(아래 참조)를 생성하는 범위를 다른 운영자와 교차시켜 범위 쿼리를 수행할 수 있다.So to determine which numbers of a set, say , lay in certain range, say [10..50], instead of iterating through the set and checking each entry, this is performed by evaluating
공중의 정태의 계급 BBTriieIntrange 기구들 BBTriieNode { 사유의 장기의 비트맵; 사유의 인트로 a, b; 사유의 인트로 x, y; 사유의 인트로 수평을 이루다; 공중의 BBTriieIntrange(인트로 a, 인트로 b) { 이(a, b, 5); } 사유의 BBTriieIntrange (인트로 a, 인트로 b, 인트로 수평을 이루다) { 이.a = a; 이.b = b; 이.수평을 이루다 = 수평을 이루다; x = (인트로) (a >>> (수평을 이루다 * 6)) & 0x3F; y = (인트로) (b >>> (수평을 이루다 * 6)) & 0x3F; // 비트 hack for: (int i = x; i <= y; i++) 비트설정 = (1 L< i); 비트맵 = 1L << y; 비트맵 = 비트맵 - 1; 비트맵 &= ~((1L << x) - 1); } 공중의 장기의 getBitMap() { 돌아오다 비트맵; } 공중의 장기의 getBitMapLafe(장기의 비트포스) { // 가독성을 위한 간단한 솔루션(자녀가 다시 생성될 때마다 그렇게 효율적이지 않음) 돌아오다 getChildNode(비트포스).getBitMap(); } 공중의 BBTriieIntrange getChildNode(장기의 비트포스) { 인트로 비트Num = 긴.NumberOfTrailingZeros(비트포스); 만일 (x == y) 돌아오다 새로운 BBTriieIntrange(a, b, 수평을 이루다 - 1); 다른 만일 (비트Num == x) 돌아오다 새로운 BBTriieIntrange(a, ~0x0, 수평을 이루다 - 1); 다른 만일 (비트Num == y) 돌아오다 새로운 BBTriieIntrange(0, b, 수평을 이루다 - 1); 다른 돌아오다 새로운 BBTriieIntrange(0, ~0x0, 수평을 이루다 - 1); } } 사용 예제
이 예는 32비트 정수를 키로 사용하는 사용법을 보여준다.
공중의 계급 BBTrieSetSample { 공중의 접점 방문자 { 공중의 공허하게 하다 방문하다(바이트[] 핵심을, 인트로 키렌); } 공중의 정태의 공허하게 하다 방문하다(BBTriieNode 마디를 짓다, 방문자 방문자, 바이트[] 핵심을, 인트로 떨어져서, 인트로 렌) { 장기의 비트맵 = 마디를 짓다.getBitMap(); 만일 (비트맵 == 0) 돌아오다; 장기의 조각들 = 비트맵; 하는 동안에 (조각들 != 0) { 장기의 비트포스 = 조각들 & -조각들; 조각들 ^= 비트포스; // 가장 오른쪽 비트를 얻고 지우다 인트로 비트Num = 긴.NumberOfTrailingZeros(비트포스); 핵심을[떨어져서] = (바이트) 비트Num; 만일 (떨어져서 == 렌 - 2) { 장기의 가치를 매기다 = 마디를 짓다.getBitMapLafe(비트포스); 장기의 비트2 = 가치를 매기다; 하는 동안에 (비트2 != 0) { 장기의 비트포스2 = 비트2 & -비트2; 비트2 ^= 비트포스2; 인트로 비트Num2 = 긴.NumberOfTrailingZeros(비트포스2); 핵심을[떨어져서+1] = (바이트) 비트Num2; 방문자.방문하다(핵심을, 떨어져서 + 2); } } 다른 { BBTriieNode childNode = 마디를 짓다.getChildNode(비트포스); 방문하다(childNode, 방문자, 핵심을, 떨어져서 + 1, 렌); } } } 공중의 정태의 인트로 set6Int(바이트[] b, 인트로 가치를 매기다) { 인트로 양치류 = 0; b[양치류 ] = (바이트) ((가치를 매기다 >>> 30) & 0x3F); b[양치류 + 1] = (바이트) ((가치를 매기다 >>> 24) & 0x3F); b[양치류 + 2] = (바이트) ((가치를 매기다 >>> 18) & 0x3F); b[양치류 + 3] = (바이트) ((가치를 매기다 >>> 12) & 0x3F); b[양치류 + 4] = (바이트) ((가치를 매기다 >>> 6) & 0x3F); b[양치류 + 5] = (바이트) (가치를 매기다 & 0x3F); 돌아오다 6; } 공중의 정태의 인트로 6인트를 얻다(바이트[] b) { 인트로 양치류 = 0; 돌아오다 ((b[양치류 ] & 0x3F) << 30) ((b[양치류 + 1] & 0x3F) << 24) ((b[양치류 + 2] & 0x3F) << 18) ((b[양치류 + 3] & 0x3F) << 12) ((b[양치류 + 4] & 0x3F) << 6) (b[양치류 + 5] & 0x3F); } 공중의 정태의 공허하게 하다 본래의(끈[] 아그) { 비비트리셋 삼위일체 = 새로운 비비트리셋(100); 비비트리셋 삼위일체 = 새로운 비비트리셋(100); 바이트[] 핵심을 = 새로운 바이트[64]; 인트로 렌; 최종의 인트로 KEY_LEN_INT = set6Int(핵심을, 1); // 6 인트로[] 시험하다 = 새로운 인트로[] { 10, 20, 30, 40, 50, 30, 60, 61, 62, 63 }; 을 위해 (인트로 i = 0; i < 시험하다.길이; i++) { 렌 = set6Int(핵심을, 시험하다[i]); 부울 갈아타다 = 삼위일체.세트(핵심을, 렌); 시스템.밖으로.인쇄하다("set: " + 시험하다[i] + ", " + 갈아타다); } 시스템.밖으로.인쇄하다("트리원 크기: " + 삼위일체.사이즈를 맞추다()); BBTrieSetOps.방문하다(새로운 BBTrieNodeMem(삼위일체.뿌리를 내리다, 삼위일체.밈), 새로운 BBTrieSetOps.방문자() { @오버라이드 공중의 공허하게 하다 방문하다(바이트[] 핵심을, 인트로 키렌) { 시스템.밖으로.인쇄하다("방문자: "+ 6인트를 얻다(핵심을) + ", " + 키렌); } }, 핵심을, 0, KEY_LEN_INT); 시험하다 = 새로운 인트로[] { 10, 25, 30, 40, 45, 50, 55, 60 }; 을 위해 (인트로 i = 0; i < 시험하다.길이; i++) { 렌 = set6Int(핵심을, 시험하다[i]); 부울 포함했다 = 삼위일체.얻다(핵심을, 렌); 시스템.밖으로.인쇄하다("포함: " + 시험하다[i] + ", " + 포함했다); } 시험하다 = 새로운 인트로[] { 10, 20, 30, 40, 45, 50, 55, 60, 61, 62, 63 }; 을 위해 (인트로 i = 0; i < 시험하다.길이; i++) { 렌 = set6Int(핵심을, 시험하다[i]); 부울 갈아타다 = 삼위일체.분명한(핵심을, 렌); 시스템.밖으로.인쇄하다("cleared: " + 시험하다[i] + ", " + 갈아타다); BBTrieSetOps.방문하다(새로운 BBTrieNodeMem(삼위일체.뿌리를 내리다, 삼위일체.밈), 새로운 BBTrieSetOps.방문자() { @오버라이드 공중의 공허하게 하다 방문하다(바이트[] 핵심을, 인트로 키렌) { 시스템.밖으로.인쇄하다(6인트를 얻다(핵심을) + " "); } }, 핵심을, 0, KEY_LEN_INT); 시스템.밖으로.인쇄하다(); } 시스템.밖으로.인쇄하다("트리원 크기: " + 삼위일체.사이즈를 맞추다()); 을 위해 (인트로 i = 0; i <= 50; i++) { 렌 = set6Int(핵심을, i); 삼위일체.세트(핵심을, 렌); 시스템.밖으로.인쇄하다("set: " + i); } 시스템.밖으로.인쇄하다("트리원 크기: " + 삼위일체.사이즈를 맞추다()); 을 위해 (인트로 i = 25; i <= 75; i++) { 렌 = set6Int(핵심을, i); 삼위일체.세트(핵심을, 렌); 시스템.밖으로.인쇄하다("set: " + i); } 시스템.밖으로.인쇄하다("트리2 크기: " + 삼위일체.사이즈를 맞추다()); // AND 예제 BBTriieNode 결과 = 새로운 BBTrieAnd( 새로운 BBTrieNodeMem(삼위일체.뿌리를 내리다, 삼위일체.밈), 새로운 BBTrieNodeMem(삼위일체.뿌리를 내리다, 삼위일체.밈)); BBTrieSetOps.방문하다(결과, 새로운 BBTrieSetOps.방문자() { @오버라이드 공중의 공허하게 하다 방문하다(바이트[] 핵심을, 인트로 키렌) { 시스템.밖으로.인쇄하다("방문자 AND 결과: " + 6인트를 얻다(핵심을)); } }, 핵심을, 0, KEY_LEN_INT); } } 참조
- ^ Phil Bagwell (2000). Fast And Space Efficient Trie Searches (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
- ^ Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
- ^ EP 특허 3376407, Walter Bauer, "2018-09-19, 2020-09-16, Crintshare AG"를 발행한 "데이터 구조의 효율적인 데이터베이스 사용"