VOOZH about

URL: https://en.wikipedia.org/wiki/Bitwise_trie_with_bitmap

⇱ Bitwise trie with bitmap - Wikipedia

Jump to content
From Wikipedia, the free encyclopedia

A bitwise trie is a special form of trie where each node with its child-branches represents a bit sequence of one or more bits of a key. A bitwise trie with bitmap uses a bitmap to denote valid child branches.

Tries and bitwise tries

[edit]

A trie is a type of search tree where – unlike for example a B-tree – keys are not stored in the nodes but in the path to leaves. The key is distributed across the tree structure. In a "classic" trie, each node with its child-branches represents one symbol of the alphabet of one position (character) of a key.

In bitwise tries, keys are treated as bit-sequence of some binary representation and each node with its child-branches represents the value of a sub-sequence of this bit-sequence to form a binary tree (the sub-sequence contains only one bit) or n-ary tree (the sub-sequence contains multiple bits).

To give an example that explains the difference between "classic" tries and bitwise tries: For numbers as keys, the alphabet for a trie could consist of the symbols '0' .. '9' to represent digits of a number in the decimal system and the nodes would have up to 10 possible children.

👁 Image
A trie with the keys "07" and "42". Note that the node labels like "0" or "07" are just added for readability and are not actually stored in the nodes.

There are multiple straight forward approaches to implement such a trie as physical data structure. To state two:

  • A node can be represented having an array of child pointers for each symbol of the alphabet 👁 {\displaystyle \Sigma }
     – an array of 10 pointers per node in the decimal number example. This gives a 👁 {\displaystyle O(|M|)}
     lookup time with 👁 {\displaystyle |M|}
     being the length of the key. But this isn't space efficient as each node preserves space for all possible child symbols even if there's no key that realizes that path.
  • A node contains a binary tree of (symbol, child pointer) tuples, ordered by symbol. This has a better space efficiency but the lookup time now is 👁 {\displaystyle O(|M|\cdot \log |\Sigma |)}
    . An ideal trie has an access time that is independent of the amount of keys stored.

These approaches get worse for larger alphabets, if, for example, the key is a string of Unicode characters. Treating the key as bit-sequence allows to have a fixed cardinality per node.

Bitwise trie with bitmap

[edit]

Bagwell[1] presented a time and space efficient solution for tries named Array Mapped Tree (AMT). The Hash array mapped trie (HAMT) is based on AMT. The compact trie node representation uses a bitmap to mark every valid branch – a bitwise trie with bitmap. The AMT uses eight 32-bit bitmaps per node to represent a 256-ary trie that is able to represent an 8 bit sequence per node. With 64-Bit-CPUs (64-bit computing) a variation is to have a 64-ary trie with only one 64-bit bitmap per node that is able to represent a 6 bit sequence[2].

👁 Image
Trie node with bitmap that marks valid child branches.

To determine the index of the child pointer of a node for such a given 6-bit value, the amount of preceding child pointers has to be calculated. It turns out that this can be implemented quite efficiently.

Node traversal

[edit]
longbitMap=mem[nodeIdx];
longbitPos=1L<<value;// 6-bit-value
if((bitMap&bitPos)==0)
returnfalse;// not found
longchildNodeIdx=mem[nodeIdx+1+Long.bitCount(bitMap&(bitPos-1))];

The offset to find the index based on the current node index is the amount of least significant bits set in the bitmap before the target position plus one for the bitmap. The amount of least significant bits set can be calculated efficiently with constant time complexity using simple bit operations and a CTPOP (count population) operation that determines the number of set bits, which is available as Long.bitCount() in Java. CTPOP itself can be implemented quite efficiently using a "bit-hack" [3] and many modern CPUs even provide CTPOP as a dedicated instruction treated by compilers as intrinsic function. 

intCTPOP(longx)
{// A "bit-hack" implementation of the population count function.
x-=((x>>>1)&0x5555555555555555L);
x=(x&0x3333333333333333L)+((x>>>2)&0x3333333333333333L);
x=(x+(x>>>4))&0x0f0f0f0f0f0f0f0fL;
x+=(x>>>8);
x+=(x>>>16);
x+=(x>>>32);
returnx&0x7f;
}

Set implementation example

[edit]

Physical data structure

[edit]

In this example implementation for a bitwise trie with bitmap, nodes are placed in an array of long (64-bit) integers. A node is identified by the position (index) in that array. The index of the root node marks the root of the trie.

Nodes are allocated from unused space in that array, extending the array if necessary. In addition, nodes, that are replaced, are collected in free lists and their space is recycled. Without this recycling, the data structure can be used to implement a persistent data structure by just keeping the previous root index and never overriding existing nodes but always creating a copy of a changed node.

Leaf nodes are inlined: Instead of having a child-pointer to a leaf node, the bitmap of the leaf node itself is stored. 

publicclass BBTrieSet{

long[]mem;
long[]freeLists;
longfreeIdx;

longroot;
longcount;

// maximum node size is 1 (bitMap) + 64 (child pointers or leaf values) + 1 as arrays are zero based
finalstaticintFREE_LIST_SIZE=1+64+1;

finalstaticintKNOWN_EMPTY_NODE=0;
finalstaticintKNOWN_DELETED_NODE=1;
finalstaticintHEADER_SIZE=2;// KNOWN_EMPTY_NODE, KNOWN_DELETED_NODE

publicBBTrieSet(intsize){
mem=newlong[size];
freeLists=newlong[FREE_LIST_SIZE];
freeIdx=HEADER_SIZE;
root=KNOWN_EMPTY_NODE;
count=0;
}

privatelongallocate(intsize){
longfree=freeLists[size];
if(free!=0){
// requested size available in free list, re-link and return head
freeLists[size]=mem[(int)free];
returnfree;
}
else{
// expansion required?
if(freeIdx+size>mem.length){
// increase by 25% and assure this is enough
intcurrSize=mem.length;
intnewSize=currSize+Math.max(currSize/4,size);
mem=Arrays.copyOf(mem,newSize);
}

longidx=freeIdx;
freeIdx+=size;
returnidx;
}
}

privatelongallocateInsert(longnodeIdx,intsize,intchildIdx){
longnewNodeRef=allocate(size+1);

inta=(int)newNodeRef;
intb=(int)nodeIdx;

// copy with gap for child
for(intj=0;j<childIdx;j++)
mem[a++]=mem[b++];
a++;// inserted
for(intj=childIdx;j<size;j++)
mem[a++]=mem[b++];

deallocate(nodeIdx,size);

returnnewNodeRef;
}

privatelongallocateDelete(longnodeIdx,intsize,intchildIdx){
longnewNodeRef=allocate(size-1);

// copy with child removed
inta=(int)newNodeRef;
intb=(int)nodeIdx;
for(intj=0;j<childIdx;j++)
mem[a++]=mem[b++];
b++;// removed
for(intj=childIdx+1;j<size;j++)
mem[a++]=mem[b++];

deallocate(nodeIdx,size);

returnnewNodeRef;
}

privatevoiddeallocate(longidx,intsize){
if(idx==KNOWN_EMPTY_NODE)
return;// keep our known empty node

// add to head of free-list
mem[(int)idx]=freeLists[size];
freeLists[size]=idx;
}

privatelongcreateLeaf(byte[]key,intoff,intlen){
longnewNodeRef=allocate(2);
inta=(int)newNodeRef;
mem[a++]=1L<<key[len-2];
mem[a]=1L<<key[len-1];// value
len-=3;
while(len>=off){
longnewParentNodeRef=allocate(2);
a=(int)newParentNodeRef;
mem[a++]=1L<<key[len--];
mem[a]=newNodeRef;
newNodeRef=newParentNodeRef;
}
returnnewNodeRef;
}

privatelonginsertChild(longnodeRef,longbitMap,longbitPos,intidx,longvalue){
intsize=Long.bitCount(bitMap);
longnewNodeRef=allocateInsert(nodeRef,size+1,idx+1);
mem[(int)newNodeRef]=bitMap|bitPos;
mem[(int)newNodeRef+1+idx]=value;
returnnewNodeRef;
}

privatelongremoveChild(longnodeRef,longbitMap,longbitPos,intidx){
intsize=Long.bitCount(bitMap);
if(size>1){
// node still has other children / leaves
longnewNodeRef=allocateDelete(nodeRef,size+1,idx+1);
mem[(int)newNodeRef]=bitMap&~bitPos;
returnnewNodeRef;
}
else{
// node is now empty, remove it
deallocate(nodeRef,size+1);
returnKNOWN_DELETED_NODE;
}
}

publiclongsize(){
returncount;
}

}

Set operations

[edit]

Contains key

[edit]

The get method tests, if a key is part of the set. The key is delivered as byte[] where each byte represents one 6-bit bit sequence of the key – so only 6 of the 8 bits per byte are used. 

publicbooleanget(byte[]key,intlen){
if(root==KNOWN_EMPTY_NODE)
returnfalse;

longnodeRef=root;
intoff=0;

for(;;){
longbitMap=mem[(int)nodeRef];
longbitPos=1L<<key[off++];// mind the ++ 
if((bitMap&bitPos)==0)
returnfalse;// not found

longvalue=mem[(int)nodeRef+1+Long.bitCount(bitMap&(bitPos-1))];

if(off==len-1){
// at leaf
longbitPosLeaf=1L<<key[off];
return((value&bitPosLeaf)!=0);
}
else{
// child pointer
nodeRef=value;
}
}
}

Set (add) key

[edit]
publicbooleanset(byte[]key,intlen){
longnodeRef=set(root,key,0,len);
if(nodeRef!=KNOWN_EMPTY_NODE){
// denotes change
count++;
root=nodeRef;
returntrue;
}
else
returnfalse;
}

privatelongset(longnodeRef,byte[]key,intoff,intlen){
longbitMap=mem[(int)nodeRef];
longbitPos=1L<<key[off++];// mind the ++
intidx=Long.bitCount(bitMap&(bitPos-1));

if((bitMap&bitPos)==0){
// child not present yet
longvalue;
if(off==len-1)
value=1L<<key[off];
else
value=createLeaf(key,off,len);
returninsertChild(nodeRef,bitMap,bitPos,idx,value);
}
else{
// child present
longvalue=mem[(int)nodeRef+1+idx];
if(off==len-1){
// at leaf
longbitPosLeaf=1L<<key[off];
if((value&bitPosLeaf)==0){
// update leaf bitMap
mem[(int)nodeRef+1+idx]=value|bitPosLeaf;
returnnodeRef;
}
else
// key already present
returnKNOWN_EMPTY_NODE;
}
else{
// not at leaf, recursion
longchildNodeRef=value;
longnewChildNodeRef=set(childNodeRef,key,off,len);
if(newChildNodeRef==KNOWN_EMPTY_NODE)
returnKNOWN_EMPTY_NODE;
if(newChildNodeRef!=childNodeRef)
mem[(int)nodeRef+1+idx]=newChildNodeRef;
returnnodeRef;
}
}
}

Clear (remove) key

[edit]
publicbooleanclear(byte[]key,intlen){
longnodeRef=clear(root,key,0,len);
if(nodeRef!=KNOWN_EMPTY_NODE){
count--;
if(nodeRef==KNOWN_DELETED_NODE)
root=KNOWN_EMPTY_NODE;
else
root=nodeRef;
returntrue;
}
else
returnfalse;
}

publiclongclear(longnodeRef,byte[]key,intoff,intlen){
if(root==KNOWN_EMPTY_NODE)
returnKNOWN_EMPTY_NODE;

longbitMap=mem[(int)nodeRef];
longbitPos=1L<<key[off++];// mind the ++
if((bitMap&bitPos)==0){
// child not present, key not found
returnKNOWN_EMPTY_NODE;
}
else{
// child present
intidx=Long.bitCount(bitMap&(bitPos-1));
longvalue=mem[(int)nodeRef+1+idx];
if(off==len-1){
// at leaf
longbitPosLeaf=1L<<key[off];
if((value&bitPosLeaf)==0)
// key not present
returnKNOWN_EMPTY_NODE;
else{
// clear bit in leaf
value=value&~bitPosLeaf;
if(value!=0){
// leaf still has some bits set, keep leaf but update
mem[(int)nodeRef+1+idx]=value;
returnnodeRef;
}
else
returnremoveChild(nodeRef,bitMap,bitPosLeaf,idx);
}
}
else{
// not at leaf
longchildNodeRef=value;
longnewChildNodeRef=clear(childNodeRef,key,off,len);
if(newChildNodeRef==KNOWN_EMPTY_NODE)
returnKNOWN_EMPTY_NODE;
if(newChildNodeRef==KNOWN_DELETED_NODE)
returnremoveChild(nodeRef,bitMap,bitPos,idx);
if(newChildNodeRef!=childNodeRef)
mem[(int)nodeRef+1+idx]=newChildNodeRef;
returnnodeRef;
}
}
}

}

Set operators

[edit]

Set operators for intersection (and), union (or) and difference (minus) are feasible using a flyweight pattern as shown below.

An interface represents physical nodes and "virtual" result nodes of an operator. Instances of this interface are created on demand during a trie traversal. Compound expressions, involving more than one operator, can be expressed directly by combining these operators as an operator can be used as argument (input) for another operator.

Flyweight interface

[edit]
publicinterface BBTrieNode{
publiclonggetBitMap();
publiclonggetBitMapLeaf(longbitPos);
publicBBTrieNodegetChildNode(longbitPos);
}

publicstaticclass BBTrieNodeMemimplementsBBTrieNode{

longnodeRef;
long[]mem;

BBTrieNodeMemchild;

publicBBTrieNodeMem(longnodeRef,long[]mem){
this.nodeRef=nodeRef;
this.mem=mem;
}

@Override
publiclonggetBitMap(){
returnmem[(int)nodeRef];
}

@Override
publiclonggetBitMapLeaf(longbitPos){
intidx=Long.bitCount(getBitMap()&(bitPos-1));
longvalue=mem[(int)nodeRef+1+idx];
returnvalue;
}

@Override
publicBBTrieNodegetChildNode(longbitPos){
intidx=Long.bitCount(getBitMap()&(bitPos-1));
longvalue=mem[(int)nodeRef+1+idx];
returnnewBBTrieNodeMem(value,mem);
}

}

Intersection (AND)

[edit]

The intersection operator is very efficient as it automatically performs pruning even over subexpressions. Nonrelevant child nodes don't have to be accessed because the bitmap and a bitwise AND operation allows to determine the result upfront. For example, calculating 👁 {\displaystyle \{1,2,3\}\cap (\{2,3,4\}\cup \{5,6,7\})=\{2,3\}}
, the subexpression 👁 {\displaystyle \{2,3,4\}\cup \{5,6,7\}=\{2,3,4,5,6,7\}}
 would not be materialized as intermediate result. 

publicstaticclass BBTrieAndimplementsBBTrieNode{

BBTrieNodenodeA;
BBTrieNodenodeB;
longbitMapA;
longbitMapB;

publicBBTrieAnd(BBTrieNodenodeA,BBTrieNodenodeB){
this.nodeA=nodeA;
this.nodeB=nodeB;
bitMapA=nodeA.getBitMap();
bitMapB=nodeB.getBitMap();
}

publiclonggetBitMap(){
returnbitMapA&bitMapB;// this gives a nice optimization (pruning)
}

publiclonggetBitMapLeaf(longbitPos){
returnnodeA.getBitMapLeaf(bitPos)&nodeB.getBitMapLeaf(bitPos);
}

publicBBTrieNodegetChildNode(longbitPos){
BBTrieNodechildNodeA=nodeA.getChildNode(bitPos);
BBTrieNodechildNodeB=nodeB.getChildNode(bitPos);
returnnewBBTrieAnd(childNodeA,childNodeB);
}

}

Union (OR)

[edit]
publicstaticclass BBTrieOrimplementsBBTrieNode{

BBTrieNodenodeA;
BBTrieNodenodeB;
longbitMapA;
longbitMapB;

publicBBTrieOr(BBTrieNodenodeA,BBTrieNodenodeB){
this.nodeA=nodeA;
this.nodeB=nodeB;
bitMapA=nodeA.getBitMap();
bitMapB=nodeB.getBitMap();
}

publiclonggetBitMap(){
returnbitMapA|bitMapB;
}

publiclonggetBitMapLeaf(longbitPos){
returnnodeA.getBitMapLeaf(bitPos)|nodeB.getBitMapLeaf(bitPos);
}

publicBBTrieNodegetChildNode(longbitPos){
if((bitMapA&bitPos)!=0){
BBTrieNodechildNodeA=nodeA.getChildNode(bitPos);
if((bitMapB&bitPos)!=0){
BBTrieNodechildNodeB=nodeB.getChildNode(bitPos);
returnnewBBTrieOr(childNodeA,childNodeB);
}
else
returnchildNodeA;// optimization, no more or-node required
}
else{
BBTrieNodechildNodeB=nodeB.getChildNode(bitPos);
returnchildNodeB;// optimization, no more or-node required
}
}

}

Difference (MINUS)

[edit]
publicstaticclass BBTrieMinusimplementsBBTrieNode{

BBTrieNodenodeA;
BBTrieNodenodeB;
longbitMapA;
longbitMapB;

publicBBTrieMinus(BBTrieNodenodeA,BBTrieNodenodeB){
this.nodeA=nodeA;
this.nodeB=nodeB;
bitMapA=nodeA.getBitMap();
bitMapB=nodeB.getBitMap();
}

publiclonggetBitMap(){
returnbitMapA;// bitMapB not useful here
}

publiclonggetBitMapLeaf(longbitPos){
longchildBitMapA=nodeA.getBitMapLeaf(bitPos);
if((bitMapB&bitPos)==0)
returnchildBitMapA;

longchildBitMapB=nodeB.getBitMapLeaf(bitPos);
returnchildBitMapA&~childBitMapB;
}

publicBBTrieNodegetChildNode(longbitPos){
BBTrieNodechildNodeA=nodeA.getChildNode(bitPos);
if((bitMapB&bitPos)==0)
returnchildNodeA;// optimization, no more minus-node required

BBTrieNodechildNodeB=nodeB.getChildNode(bitPos);
returnnewBBTrieMinus(childNodeA,childNodeB);
}

}

Ranges

[edit]

Using the virtual node approach, range queries can be accomplished by intersecting a range generating virtual trie (see below) with another operator. So to determine which numbers of a set, say 👁 {\displaystyle \{10,20,30,40,50,60,61,62,63\}}
, lay in certain range, say [10..50], instead of iterating through the set and checking each entry, this is performed by evaluating 👁 {\displaystyle \{10,20,30,40,50,60,61,62,63\}\cap \{10,..,50\}}
. 

publicstaticclass BBTrieIntRangeimplementsBBTrieNode{

privatelongbitMap;
privateinta,b;
privateintx,y;
privateintlevel;

publicBBTrieIntRange(inta,intb){
this(a,b,5);
}

privateBBTrieIntRange(inta,intb,intlevel){
this.a=a;
this.b=b;
this.level=level;
x=(int)(a>>>(level*6))&0x3F;
y=(int)(b>>>(level*6))&0x3F;

// bit hack for: for (int i = x; i <= y; i++) bitSet |= (1L << i);
bitMap=1L<<y;
bitMap|=bitMap-1;
bitMap&=~((1L<<x)-1);
}

publiclonggetBitMap(){
returnbitMap;
}

publiclonggetBitMapLeaf(longbitPos){
// simple solution for readability (not that efficient as for each call a child is created again)
returngetChildNode(bitPos).getBitMap();
}

publicBBTrieIntRangegetChildNode(longbitPos){
intbitNum=Long.numberOfTrailingZeros(bitPos);
if(x==y)
returnnewBBTrieIntRange(a,b,level-1);
elseif(bitNum==x)
returnnewBBTrieIntRange(a,~0x0,level-1);
elseif(bitNum==y)
returnnewBBTrieIntRange(0,b,level-1);
else
returnnewBBTrieIntRange(0,~0x0,level-1);
}

}

Usage example

[edit]

The example shows the usage with 32-bit integers as keys. 

publicclass BBTrieSetSample{

publicinterface Visitor{
publicvoidvisit(byte[]key,intkeyLen);
}

publicstaticvoidvisit(BBTrieNodenode,Visitorvisitor,byte[]key,intoff,intlen){
longbitMap=node.getBitMap();
if(bitMap==0)
return;
longbits=bitMap;
while(bits!=0){
longbitPos=bits&-bits;bits^=bitPos;// get rightmost bit and clear it
intbitNum=Long.numberOfTrailingZeros(bitPos);
key[off]=(byte)bitNum;
if(off==len-2){
longvalue=node.getBitMapLeaf(bitPos);
longbits2=value;
while(bits2!=0){
longbitPos2=bits2&-bits2;bits2^=bitPos2;
intbitNum2=Long.numberOfTrailingZeros(bitPos2);
key[off+1]=(byte)bitNum2;
visitor.visit(key,off+2);
}
}
else{
BBTrieNodechildNode=node.getChildNode(bitPos);
visit(childNode,visitor,key,off+1,len);
}
}
}

publicstaticintset6Int(byte[]b,intvalue){
intpos=0;
b[pos]=(byte)((value>>>30)&0x3F);
b[pos+1]=(byte)((value>>>24)&0x3F);
b[pos+2]=(byte)((value>>>18)&0x3F);
b[pos+3]=(byte)((value>>>12)&0x3F);
b[pos+4]=(byte)((value>>>6)&0x3F);
b[pos+5]=(byte)(value&0x3F);
return6;
}

publicstaticintget6Int(byte[]b){
intpos=0;
return
((b[pos]&0x3F)<<30)|
((b[pos+1]&0x3F)<<24)|
((b[pos+2]&0x3F)<<18)|
((b[pos+3]&0x3F)<<12)|
((b[pos+4]&0x3F)<<6)|
(b[pos+5]&0x3F);
}

publicstaticvoidmain(String[]args){
BBTrieSettrie1=newBBTrieSet(100);
BBTrieSettrie2=newBBTrieSet(100);

byte[]key=newbyte[64];
intlen;
finalintKEY_LEN_INT=set6Int(key,1);// 6

int[]test=newint[]{10,20,30,40,50,30,60,61,62,63};
for(inti=0;i<test.length;i++){
len=set6Int(key,test[i]);
booleanchange=trie1.set(key,len);
System.out.println("set: "+test[i]+", "+change);
}
System.out.println("trie1 size: "+trie1.size());

BBTrieSetOps.visit(newBBTrieNodeMem(trie1.root,trie1.mem),newBBTrieSetOps.Visitor(){
@Override
publicvoidvisit(byte[]key,intkeyLen){
System.out.println("Visitor: "+get6Int(key)+", "+keyLen);
}
},key,0,KEY_LEN_INT);

test=newint[]{10,25,30,40,45,50,55,60};
for(inti=0;i<test.length;i++){
len=set6Int(key,test[i]);
booleancontained=trie1.get(key,len);
System.out.println("contained: "+test[i]+", "+contained);
}

test=newint[]{10,20,30,40,45,50,55,60,61,62,63};
for(inti=0;i<test.length;i++){
len=set6Int(key,test[i]);
booleanchange=trie1.clear(key,len);
System.out.println("cleared: "+test[i]+", "+change);
BBTrieSetOps.visit(newBBTrieNodeMem(trie1.root,trie1.mem),newBBTrieSetOps.Visitor(){
@Override
publicvoidvisit(byte[]key,intkeyLen){
System.out.print(get6Int(key)+" ");
}
},key,0,KEY_LEN_INT);
System.out.println();

}
System.out.println("trie1 size: "+trie1.size());

for(inti=0;i<=50;i++){
len=set6Int(key,i);
trie1.set(key,len);
System.out.println("set: "+i);
}
System.out.println("trie1 size: "+trie1.size());

for(inti=25;i<=75;i++){
len=set6Int(key,i);
trie2.set(key,len);
System.out.println("set: "+i);
}
System.out.println("trie2 size: "+trie2.size());

// AND example
BBTrieNoderesult=newBBTrieAnd(
newBBTrieNodeMem(trie1.root,trie1.mem),
newBBTrieNodeMem(trie2.root,trie2.mem));

BBTrieSetOps.visit(result,newBBTrieSetOps.Visitor(){
@Override
publicvoidvisit(byte[]key,intkeyLen){
System.out.println("Visitor AND result: "+get6Int(key));
}
},key,0,KEY_LEN_INT);

}
}

References

[edit]
  1. ^ Phil Bagwell (2000). Fast And Space Efficient Trie Searches (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
  2. ^ EP patent 3376407, Walter Bauer, "Efficient use of trie data structure in databases", published 2018-09-19, issued 2020-09-16, assigned to censhare AG
  3. ^ Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
Category:
Hidden category: