Page 262 - 《软件学报》2020年第11期

侯瑞涛 等:分级可逆的关系数据水印方案 3577

3. table basic _i[k]=bit s ;
4. else if (table basic _i[k] euqals bit s )
5. continue(⋅);
6. else if (table basic _i[k] !euqals bit s )
7. put(hash em ,table overflow _i);
辅助数据存储时,采用哈希表为主的存储结构,且以数据分区为单位进行存储,各数据分区 i 均具有相应的
辅助数据存储结构 D s _i.D s _i 由两张表构成:一张基本表 table basic _i,一张溢出表 table overflow _i.其中,table basic _i 为
哈希表,用于存储大部分辅助数据;table overflow _i 为普通的关系数据表,用于存储发生哈希冲突且取值相反的辅
助数据对应的嵌入哈希值 hash em .根据函数 1,bit s 的具体存储过程:首先计算 bit s 在 table basic _i 中的存储位置 k,
其中,m 表示 table basic _i 的规模.如果 table basic_ i[k]为空,将 bit s 存入 table basic _i[k]即可;否则判断 table basic _i[k]与 bit s
是否相同.如果相同,不做处理,函数 1 运行完毕;如果不同,将 bit s 对应的 hash em 存入 table overflow _i,函数 1 运行完
毕.要注意的是,待所有的辅助数据存储完毕后,需为 table overflow _i 建立数据库索引,以提高 table overflow 的查询效
率.另外,table overflow _i 存储的是 hash em .相比于存储主键值本身的方式,其占用空间更少,而且对于具有非数值型
主键的数据,以及具有多字段组合主键的数据来说,可以采用统一的处理方式,其效率更高,更具实用性.
为降低辅助数据存储时的冲突率,进一步提高辅助数据的存取效率,本方案对辅助数据存储结构中基本表
的规模进行了实验分析.具体的实验细节见第 4.1 节.
2.4 数据质量等级检测
数据质量等级的检测是实现分级可逆水印的一个重要环节,其本质是检测嵌有水印的数据分区.水印检测
和数据质量等级提升都需要提前获知当前的数据质量等级,确定水印所在的数据分区.具体流程见算法 2.
算法 2. 等级检测算法.
Input: D s ,D w ,k,sk,S.

Output: Flag.
1. for i=0 to γ−1 do
2. totalcount_i=matchcount_i=0;
3. for each tuple r∈D w do
4. hash part =H(r.key,k);
5. i=hash part mod γ;
6. hash em =H(r.key,sk_i);
7. if (hash em mod η equals 0) {
8. A_index x=hash em mod ε;
9. if (A_x is NULL)
10. continue(⋅);
11. bit_index y=hash em mod ξ;
12. WS_index z=hash em mod ω;
13. bit s =bit_y xor S_z;
14. bit_temp=Get(r.key,D s _i);
15. if (bit s equals bit_temp)
16. matchcount_i++;
17. totalcount_i++;}
18. else
19. next tuple;
20. τ_i=threshold(totalcount_i,α);