【数据结构（邓俊辉）学习笔记】向量06——位图

0.概述

位图（Bitmap）是一种特殊的序列结构，可用以动态地表示由一组（无符号）整数构成的集合。

1. test() 判断k 是否存在集合S中。
2. set() 将k 加入到集合S中。
3. clear() 将k从集合S中移除。

若是32位，则长度U为$2^{32}$，且其中每个元素的取值均为布尔型（初始值均为 false）。

1.结构

注意：bit的最小操作单位是8位，n+ 7是在做ceiling。

算法思想：

• test算法：
  第一步：找bit所在基本单位区间，即以8个bit为单位的，k >> 3 即（k/8），即为入口。
  第二步：根据第一步找到的入口，计算offset值，k & 0x07 即（k%8），再生成掩码去操作single bit。
• set算法 / clear算法：
  与test算法基本相同，将 & 改成 |= 或 &=~。
  
  综上：
• 就可在O（1）时间完成test set clear操作。
• 位图向量所占的空间线性正比于集合的取值范。

2.实现

上述接口实现

class Bitmap { //位图Bitmap类
private:
   unsigned char* M;
   Rank N, _sz; //位图空间M[]，N*sizeof(char)*8个比特中含_sz个有效位
protected:
   void init( Rank n )
      { M = new unsigned char[N = ( n + 7 ) / 8]; memset( M, 0, N ); _sz = 0; }
public:
   Bitmap( Rank n = 8 ) { init( n ); } //按指定容量创建位图（为测试暂时选用较小的默认值）
   Bitmap( char* file, Rank n = 8 ) { //按指定或默认规模，从指定文件中读取位图
      init( n );
      FILE* fp = fopen( file, "r" ); fread( M, sizeof( char ), N, fp ); fclose( fp );
      for ( Rank k = 0, _sz = 0; k < n; k++ ) _sz += test(k);
   }
   ~Bitmap() { delete[] M; M = NULL; _sz = 0; } //析构时释放位图空间

   Rank size() { return _sz; }
   void set   ( Rank k ) { expand( k ); _sz++; M[k >> 3] |=   ( 0x80 >> ( k & 0x07 ) ); }
   void clear ( Rank k ) { expand( k ); _sz--; M[k >> 3] &= ~ ( 0x80 >> ( k & 0x07 ) ); }
   bool test  ( Rank k ) { expand( k ); return M[k >> 3] &    ( 0x80 >> ( k & 0x07 ) ); }

   void dump( char* file ) //将位图整体导出至指定的文件，以便对此后的新位图批量初始化
   { FILE* fp = fopen( file, "w" ); fwrite( M, sizeof ( char ), N, fp ); fclose( fp ); }
   char* bits2string( Rank n ) { //将前n位转换为字符串——
      expand( n - 1 ); //此时可能被访问的最高位为bitmap[n - 1]
      char* s = new char[n + 1]; s[n] = '\0'; //字符串所占空间，由上层调用者负责释放
      for ( Rank i = 0; i < n; i++ ) s[i] = test( i ) ? '1' : '0';
      return s; //返回字符串位置
   }
   void expand( Rank k ) { //若被访问的Bitmap[k]已出界，则需扩容
      if ( k < 8 * N ) return; //仍在界内，无需扩容
      Rank oldN = N; unsigned char* oldM = M;
      init( 2 * k ); //与向量类似，加倍策略
      memcpy_s( M, N, oldM, oldN );
      delete[] oldM; //原数据转移至新空间
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

• 提供了一个dump()接口，可以将位图整体导出至指定的文件，以便对此后的新位图批量初始化。
• 与可扩充向量一样，一旦即将发生溢出，这里将调用expand()接口扩容。可见，这里采用的也是“加倍”的扩容策略。

3. 应用

3.1 去重

• 利用 Bitmap 类设计算法，在 O(n)时间内剔除 n 个 ASCII 字符中的重复字符，各字符仅保留一份

 1. 将非重复的ASCII字符视作一个集合，并将其组织为一个Bitmap结构——ASCII编码为k的字符，对应于其中第k个比特位。
 2. 初始时，该集合为空，Bitmap结构中的所有比特位均处于0状态。以下，只需在O(n)时间内遍历所有的输入字符，并对
ASCII编码为k的字符，通过set(k)接口将其加入集合。
 3. 请注意，这里使用的Bitmap结构只需128个比特位。因此，最后只需再花费O(128) = O(1)时间遍历一趟所有的比特位，
 并输出所有通过test()测试的比特位，即可完成字符集的去重。
1
2
3
4
5
6

3.2 筛法

• 求素数
  算法思想：0和1自然不是，若2是，则认为2的倍数4，6，8均是，依次类推。最后留下来的则是素数。
  
  实现思想：Bitmap B（n），记录待处理的数，0和1自然不是set掉，查看数i是否被set，若没有则以i为步长，set掉取余数。
  
• 利用 Bitmap 类设计算法，快速地计算不大二 10^8 的所有素数。

#include "../Bitmap/Bitmap.h" //引入Bitmap结极
/******************************************************************************************
* 筛法求素数
* 计算出不大于n的所有素数
* 不计内循环，外循环自身每次仅一次加法、两次判断，累计O(n)
* 内循环每趟迭代O(n/i)步，由素数定理至多n/ln(n)趟，累计耗时不过
* n/2 + n/3 + n/5 + n/7 + n/11 + ...
* < n/2 + n/3 + n/4 + n/6 + n/7 + ... + n/(n/ln(n))
* = O(n(ln(n/ln(n)) - 1))
* = O(nln(n) - nln(ln(n)) - 1)
* = O(nlog(n))
* 如下实现做了进一步优化，内循环从i * i而非i + i开始，迭代步数由O(n / i)降至O(max(1, n / i - i))
******************************************************************************************/
void Eratosthenes ( int n, char* file ) {
	Bitmap B ( n ); B.set ( 0 ); B.set ( 1 ); //0和1都不是素数
	for ( int i = 2; i < n; i++ ) //反复地，从下一
		if ( !B.test ( i ) ) //可认定的素数i起
			for ( int j = 2*i; j < n; j += i ) //以i为间隔
				B.set ( j ); //将下一个数标记为合数
	B.dump ( file ); //将所有整数的筛选标记统一存入指定文件，以便日后直接寻入
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

该算法可在O(nlogn)时间内计算出不超过n的所有素数。