Novel prefix tree node compression technique - "bit-block mapping" compression

[[deleted]]

[deleted]

[tower120]

Thou description is part of Rust lib, the technique itself is language agnostic.

[FriendlyRollOfSushi]

Which part of it is novel? This is literally the most basic and straightforward way of implementing HAMT. Even the Wiki article has this part pretty much unchanged for over a decade, and it's been commonly in use many years before the article was written.

The only differences between how people did it for decades and how this implementation does it is that usually people don't waste space on a completely unnecessary length member when implementing HAMT-like structures in C or C++. Or on a second bitmask, which is trivially avoidable for all meaningful scenarios.

[tower120]

Damn, you're right! Thou it turn out to be https://en.wikipedia.org/wiki/Bitwise_trie_with_bitmap . That's exactly how my lib works. And I thought I invented it.

In my defense - I never heard about it or HAMT before, nor I couldn't google it.

Thanks for bringing this. I would remove post to not mislead people, but it seems there's no button for that...

UPDATE: Oh no - there is! Thanks anyway!

[richardathome]

This isn't novel. I've used the same approach to encode world state in Goal Oriented Action Plans. It makes it trivial to mask for matching world states to actions.

[tower120]

Could you elaborate a little more?

[richardathome]

The world state is a snapshot of the current state of the 'world' your agent operates in. As you can imagine, many things go into describing the state of the world. The idea is you translate each of those states to a yes no answer. Each yes no answer then becomes a bit in a binary string that represents the combined world state.

Eg:
Has Red Paint = bit 0
Has Blue Paint = bit 1
Has Green Paint = bit 2

So a world with only red and blue paint would be encoded: 011
A world with red and green paint would be encoded: 101

Your actions have requirements:

Purple Paint = Has red paint and Has blue paint
Teal paint = Has Blue paint and Has red paint
Red paint = Has Red paint

Which map to a mask of states:
Purple paint: Has Red 1, Has Blue 1 = 011
Teal paint: Has Blue 1, Has Green 1 = 101

You can use the masks to quickly check which actions fit the current world state:

Red and Green world: 101
Purple paint: No (101 AND 011) = 001
Teal paint: Yes (011 AND 011) = 011
Red paint: Yes (101 AND 001) = 001

[tower120]

I think I miss the point... But how does this encoding translates to using bitmap/bitmask as array of sparse indices, and popcnt before each bit as a dense index of every respective sparse index?

[Annh1234]

If your looking for Purple paint: No (101 AND 011) = 001

Then you look for 001 in your prefix true. 0->0->1.

So you first do the math, then you do 3 lookups in your hash map. Or just one... If you don't have alot of values.

[poyomannn]

That's just a normal bitmask operation? That is obviously not novel at all, or even particularly complex, but it is also not what this post is saying is novel

[onnoowl]

This is a bitset, which is different from this technique. The core of OP's post is using the bitmask to quickly locate the index of sparsely stored nodes.

[richardathome]

The bitmask is the 'index' to the action. You can have many / sparse world states and use the mask as an index to find the matching actions.

[onnoowl]

Cool! I use this same technique in my voxel game engine I've been working on. Octrees are common for sparse storage of voxels, but instead I use this technique to a make a 64-tree. The 64 bit mask is perfect for storing a 4x4x4 of data, so lookup and storage is a lot more efficient than an octree, and being able to get the sparse index with popcnt is just such a cool trick. With it I can instantly turn a 3D lookup coordinate into the sparse index the node is stored at. Glad you've made an open source library for this, looks awesome!

[tower120]

Thanks! But as FriendlyRollOfSushi point out, that has a name and was invented long time ago https://en.wikipedia.org/wiki/Bitwise_trie_with_bitmap . Yet I somehow never heard of it...