论文部分内容阅读
信息的负表示(Negative Representation)是受人工免疫系统启发而来的,与一般的信息表示的区别在于负表示通过不在传统数据集中的内容来表示原信息。负数据库(Negative Databases, NDB)作为负表示的一种形式,在信息安全和隐私保护上有着重要的研究意义和良好的应用前景。负数据库与正数据库的区别在于负数据库存储的内容是正数据库补集的一种压缩形式。已有的工作表明,负数据与SAT公式是等价的。负数据库已经被用于信息隐藏,隐私数据收集和密码负认证。一些与负数据库相关的典型的应用是基于难以逆转的负数据库,因此,生成难以逆转的负数据库具有重要的研究意义。此外,负数据库也适用于正数据库上的一些操作(如：选择、插入、删除、更新、交集、并集等),因此,正数据库上的一些应用也可以适用于负数据库。本论文旨在研究负数据库生成算法及应用。本论文的主要研究内容和创新之处有如下几个方面。(1)提出基于前缀算法和q-hidden算法的混合算法,用于生成完备并且难以逆转(对诸如WalkSAT之类的采用局部搜索策略的SAT求解器)的单串负数据库。该混合算法先生成一个小规模的完备的负数据库,然后使得这个完备的负数据库难以逆转,进而同时具有完备性和难解性。(2)提出p-hidden算法,该算法能生成难以逆转(对诸如WalkSAT之类的采用局部搜索策略的SAT求解器,以及诸如zChaff之类的采用DPLL策略的SAT求解器)的单串负数据库。该算法通过两个可变的参数来控制负数据库中不同类型的记录的比例。与只用一个可变参数的q-hidden算法相比较,p-hidden算法可以对局部搜索的求解器造成更强的误导,进而生成更加难以逆转(对诸如WalkSAT之类的采用局部搜索策略的SAT求解器)的单串负数据库。(3)提出难以逆转(对诸如WalkSAT之类的采用局部搜索策略的SAT求解器,以及诸如zChaff之类的采用DPLL策略的SAT求解器)的多串负数据库生成算法。首先,依据单串负数据库的难解区域,该算法以数据库中两个串的中心串为基础来生成负数据库,通过控制负数据库中不同类型的记录的比例,使得局部搜索策略的求解器被误导到向数据库中两个串的反方向搜索,即这两个串都位于各自对应的难解区域内,进而生成难以逆转的两串负数据库。其次,本文将难以逆转的两串负数据库生成算法推广到多个串的情况,生成难以逆转的多串负数据库。(4)提出在典型的单串负数据库上进行k近邻分类和k均值聚类的算法。这两个算法的核心都是一个估计负数据库和二进制串之间海明距离的方法,然后以此方法为基础,在负数据库上进行k近邻分类和k均值聚类。本论文对负数据库生成算法及其应用进行了深入的研究。首先,研究了单串负数据库生成算法,并提出了两个新算法生成单串负数据库。接着,提出了难以逆转的多串负数据库生成算法。最后,提出了在典型的单串负数据库上进行k近邻分类和k均值聚类的算法。本文工作对负数据库的有关理论和方法研究具有参考价值。