平时工作中会遇到一些有意思的算法或者数据结构，因为理解起来需要花费一些精力与时间，为了二次查阅时的时间节省，这里将之罗列到一起，并进行简单原理介绍。
1. Hierarchical Bit Vectors（简称HBV）
参考文献[1]中给出了一种叫做Hierarchical Bit Vectors的数据结构，通过多层数据来实现对有限大小的整数数据的表达，举个例子，假设我们有一个数据集合，中间包含了三个整数{2, 3, 6}，我们可以选择使用一个bit vector来表示这个集合：00110010。这个vector长度为8（考虑到扩展，比如我们已知的集合最大数值为7，那么这里最后还是需要加上0凑成8位，否则7位就足够了）。而使用HBV则需要在这个基础上增加多层数据，比如我们使用2-ary HBV（每一层的每个bit在下一层对应2个bit，如果k-ary HBV则是每层每个bit对应下层的k个bits）往上一层的bit vector为0101（这一层的每个bit是否为1取决于其下层的两个bit是否被置为1，如果都是0，那么这一层的bit就是0，否则就是1），再往上一层就是11，最后最上面一层就是1，用图形表示就是如下图所示：
使用其他分叉数值的HBV如下图所示（4-ary HBV）
这里的一个问题就是，对于这些数据，我们直接使用一个bit vector（即最下层的那个vector，这种方式可以看成是标准的bit vector）就能够表示了，那么为什么要搞这么复杂来增加上面几层呢？
从[1]中的分析总结来看，这是因为HBV相对于标准的bit vector而言在succ操作（给定一个数n，找出集合中大于n的最小数值的操作）的效率要高很多，而HBV相对于传统的BST（Binary Search Tree）在contains（判断是否包含某个数值）操作上的效率要高一些，也就是说虽然从一些普通应用场景来看，HBV不具有优越性，但是在一些特殊的应用场景，这个数据结构还是有一定的应用市场的。
网友评论