基于哈夫曼的k-匿名模型隐私保护数据压缩方案.pdf

2023 年 8 月 Chinese Journal of Network and Information Security August 2023 第 9 卷第 4 期 网络与信息安全学报 Vol.9 No.4 基于哈夫曼的 k-匿名模型隐私保护数据压缩方案 于玥1,2，林宪正3，李卫海1,2，俞能海1,2（1.中国科学技术大学网络空间安全学院，安徽 合肥 230001；2.中国科学院电磁空间信息重点实验室，安徽 合肥 230001；3.华为技术有限公司 2012 实验室，香港 999077）摘 要：k-匿名模型作为常用的数据匿名技术，广泛应用于数据发布阶段的隐私保护。随着大数据时代的快速发展，海量数据的产生给数据存储带来了新的挑战。然而，存储器的成本较高且存储空间有限，通过硬件升级来无限制地扩充存储空间并不可行。为此，使用数据压缩技术可以减少存储成本和通信开销。为减少数据发布阶段使用匿名技术产生的数据的存储空间，提出了 k-匿名模型隐私保护数据压缩方案。对于 k-匿名模型的原始数据，按照设定的规则及原始数据同匿名数据之间的预设泛化层次关系计算两者的差值，并根据差值数据具有的频率特性对差值进行哈夫曼编码压缩。通过存储差值可以间接获得原始数据，从而减少原始数据的存储空间。对于 k-匿名模型的匿名数据，根据模型的泛化规则或预设泛化层次关系，匿名数据通常具有较高的重复性，且设定的 k 值越大，匿名数据的泛化程度越高、重复性越强。对匿名数据设计实现哈夫曼编码压缩，减少匿名数据的存储空间。实验结果表明，所提方案能够显著降低 k-匿名模型的原始数据及匿名数据的压缩率。在使用的 5 个 k-匿名模型及不同 k 值的设定情况下，与 Windows 11 的 zip 工具相比，所提方案的原始数据压缩率和匿名数据压缩率平均降低了 72.2%、64.2%。关键词：k-匿名模型；隐私保护；数据压缩存储；哈夫曼编码 中图分类号：TP393 文献标志码：A DOI:10.11959/j.issn.2096109x.2023054 Privacy-preserving data compression scheme for k-anonymity model based on Huffman coding YU Yue1,2,LIN Xianzheng3,LI Weihai1,2,YU Nenghai1,2 1.School of Cyber Technology and Science,University of Science and Technology of China,Hefei 230001,China 2.Key Laboratory of Electro-magnetic Space Information,Chinese Academy of Sciences,Hefei 230001,China 3.2012 Labs,Huawei Technology Co.Ltd,Hong Kong 999077,China Abstract:The k-anonymity model is widely used as a data anonymization technique for privacy protection during the data release phase.However,with the advent of the big data era,the generation of vast amounts of data poses 收稿日期：20221215；修回日期：20230324 通信作者：于玥， 基金项目：国家自然科学基金（62071446）Foundation Item:The National Natural Science Foundation of China(62071446)引用格式：于玥,林宪正,李卫海,等.基于哈夫曼的 k-匿名隐私保护数据压缩方案J.网络与信息安全学报,2023,9(4):64-73.Citation Format:YU Y,LIN X Z,LI W H,et al.Privacy-preserving data compression scheme for k-anonymity model based onHuffman coding J.Chinese Journal of Network and Information Security,2023,9(4):64-73.第 4 期 于玥等：基于哈夫曼的 k-匿名模型隐私保护数据压缩方案 65 challenges to data storage.However,it is not feasible to expand the storage space infinitely by hardware upgrade,since the cost of memory is high and the storage space is limited.For this reason,data compression techniques can reduce storage costs and communication overhead.In order to reduce the storage space of the data generated by using anonymization techniques in the data publishing phase,a compression scheme was proposed for the original data and anonymized data of the k-anonymity model.For the original data of the k-anonymity model,the difference between the original data and the anonymized data was calculated according to the set rules and the pre-defined generalization level.Huffman coding compression was applied to the difference data according to frequency characteristics.By storing the difference data,the original data can be obtained indirectly,thus reducing the storage space of the original data.For anonymized data of the k-anonymity model,the anonymized data usually have high repeatability according to the generalization rules of the model or the pre-defined generalization hierarchy relations.The larger the value of k,the more generalized and repeatable the anonymized data becomes.The design of Huffman coding compression was implemented for anonymous data to reduce storage space.The experimental results show that the proposed scheme can significantly reduce the original data and the anonymous data compression rate of the k-anonymity model.Across five models and various k-value settings,the proposed scheme reduces the compression rate of raw and anonymized data by 72.2%and 64.2%on average compared to the Windows 11 zip tool.Keywords:k-anonymity model,privacy preservation,data compression storage,Huffman coding 0 引言 随着大数据时代的到来以及计算机计算性能的不断提升，互联网、教育、医疗等行业存储了海量数据，数据的共享范围逐渐扩大。在数据发布的过程中，如果数据拥有方对数据处理不当，可能会泄露用户的个人隐私信息1。数据匿名技术是重要的隐私保护技术之一，其通过匿名化技术弱化敏感信息与个体之间的关联性，并对原始数据中的敏感信息进行保护处理，从而有效地降低数据发布过程中个人隐私信息披露的风险。k-匿名模型是最常用的匿名保护数据发布技术，其基本思想是通过泛化和隐匿原始数据集中的部分属性值形成满足 k-匿名要求的匿名数据集并用于数据发布，保护隐私的同时在一定程度上保持数据的可用性2-3。基于 k-匿名的模型广泛应用于公共数据库或微数据发布阶段的隐私保护、位置隐私保护等领域。Wu 等4提出了一个基于反馈的 k-匿名方案，用于众包数据库的隐私保护。在该方案中，合成样本被公布给人类工作者，其结果被用来指导对匿名策略的选择。Kabir 等5提出了一个基于微聚集方法的 k-匿名模型，用于保护云计算中的微数据。该模型以特定的方式对数据集中的所有记录进行排序，并提出一个微聚集方法来创建 k-匿名聚类。Wang 等6提出了一个基于客户端的个性化k-匿名方案，实现在网络系统中对自主车辆查询服务的隐私保护。Fei 等7提出了一种基于 k-匿名原则的隐私保护的两级模式方案，其降低了位置服务隐私保护的成本并提高了用户位置隐私的安全性。Xing 等8提出了一种基于双 k-匿名的位置隐私保护方法，该方法可以隐藏用户位置和请求信息，并应用于社会化车联网。为保证用户隐私数据的安全性，使用匿名化技术对发布数据进行处理是必要的，同时海量数据的产生给数据存储带来了压力。然而，存储器的存储空间有限且成本较高，无法通过硬件升级来无限扩充空间。在这种情况下，可以使用数据压缩技术减少存储成本和通信开销9。目前已有对结构化数据进行压缩的相关研究10-11，但没有针对匿名数据及其原始数据进行压缩的研究。k-匿名模型通常根据预设的泛化层级或一定的泛化规则将原始数据转化为匿名数据，可以将两者间的关系具体表示为差值，并根据差值的特性对其进行压缩存储。原始数据可由差值及匿名数据间接获得，从而减少原始数据存储占用的空间。匿名数据相较于原始数据更具重复性，因此可以利用匿名数据的重复性对其进行压缩。哈夫曼编码是一种经典的熵编码算法12，它被广泛应用于数据压缩13、图像处理14、数据安全15-16、音频压66 网络与信息安全学报 第 9 卷 缩17等领域。哈夫曼编码主要依据字符的频率进行压缩，适用于 k-匿名模型的数据压缩。本文的主要工作总结如下。1)针对 k-匿名模型的原始数据，提出一种压缩方案，将原始数据与匿名数据之间的关联性具体化为差值。使用哈夫曼编码对差值进行压缩，减少原始数据的存储空间。2)针对 k-匿名模型的匿名数据，提出一种压缩方案，由于泛化后的数据具有一定的重复性，且泛化层次越高重复性越强，使用哈夫曼进行压缩，减少匿名数据的存储空间。3)实验结果表明，提出的 k-匿名模型原始数据压缩方案和匿名数据压缩方案的压缩率相较于 Windows 11 的 zip 工具，平均降低了 72.2%、64.2%。1 预备知识 1.1 k-匿名模型 k-匿名模型要求数据集中的每个记录至少与k1 条记录无法区分，以抵御链接攻击。k-匿名模型相关定义如下。定义 1 原始数据表T。原始数据表T 由显式标识符EI、准标识符QI、敏感属性SA及非敏感属性NSA组成，可以将 T 形式化地表示为(EI,QI,SA,NSA)T=。1)显式标识符EI 每条记录的显式标识符都可以唯一标识原始数据集T 中的个体身份。在数据发布前必须被删除或隐匿。2)准标识符QI 假定一个原始数据表12(,)nT A AA?，其中1A至nA代表组成数据表的属性，T的准标识符QI ,ijAA=?由一组属性组成，其中,ijAA?12,nA AA?，则准标识符为能够以较高概率识别出目标个体的最小属性集合。3)敏感属性SA 需要保护的敏感信息，一般无法预先获知，也无法通过敏感属性唯一确定一个用户记录。4)非敏感属性NSA 非敏感属性即非敏感信息，单一的属性可作为非敏感属性，多个非敏感属性组合有可能成为准标识符。定义 2 匿名数据表T。原始数据通过匿名化技术处理之后得到的数据表为匿名数据表T。定义 3 k-匿名。假定12(,)nT A AA?是一个表，QI是表T相关的准标识符，当且仅当在QIT中出现的每一个记录至少出现k次，则称表T满足k-匿名。k-匿名模型的实现主要通过匿名化和模型算法。匿名化主要包括泛化和隐匿方法。泛化的思想是通过降低准标识符属性的精度，使得在准标识符属性上值相同的元组个数增加。准标识符属性分为数值型和分类型两种类型，对于数值型属性通常将数值泛化成对应的区间，对于分类型属性则泛化为相对应原属性值更一般的值来取代。泛化操作需要根据属性的泛化层次结构实现，泛化层次结构主要包括域泛化层次（DGH，domain generalization hierarchy）和值泛化层次（VGH，value generalization hierarchy）。图1为数值型属性Age32,33,36,37,38=的域泛化层次和值泛化层 次。图2为 分 类 型 属 性Country=China,India,Italy,Poland,Cuba,Canada的域泛化层次和值泛化层次。隐匿的思想是去除单元值或一个元组的所有值。图 1 属性 Age 的域泛化层次和值泛化层次 Figure 1 The generalization process of domain and value of age attribute 图 2 Country 属性的域泛化层次和值泛化层次 Figure 2 The generalization process of domain and value of country attribute 第 4 期 于玥等：基于哈夫曼的 k-匿名模型隐私保护数据压缩方案 67 k-匿名模型的泛化算法从泛化约束的角度可以分为全域泛化算法和局域泛化算法。经典的全域泛化算法包括Datafly算法18、Incognito算法19等，主要的局域泛化算法包括Top-down算法20、Mondrian21、Basic Mondrian22等。1.2 哈夫曼编码 哈夫曼编码是一种可变长编码，通常用于无损数据压缩，其主要目的是为出现频率较高的字符分配长度较短的码字，从而最大程度地减少存储空间。哈夫曼的编码过程由两部分组成。首先，统计原始数据中各字符出现的频率，根据字符频率生成对应的哈夫曼树以及编码表。其次，扫描原始数据的每个字符并查询编码表，使用对应的码字替换字符。在解码的过程中，解码器读取压缩文件以确定编码表中对应的字符并进行替换。下面使用一个示例来解释编码过程。初始字符及其字符频率如图3所示。图 3 初始字符及其字符频率 Figure 3 Initial string and its character frequency 按照字符出现的频率进行升序排列，并生成对应的哈夫曼树，如图4所示。生成哈夫曼树的算法如下，假设共有n个字符。1)创建n个节点并为每个字符分配一个节点，节点的权值字符的频率，将其作为有n棵树的森林；2)在森林中选择两个根节点的权值最小的树进行合并，作为一棵新树的左、右子树，且新树的根节点权值为其左、右子树根节点权值之和。3)从森林中删除选取的两棵树，并将新树加入森林。4)重复步骤2)、步骤3)，直到森林中只剩一棵树，该树即所求的哈夫曼树。根据哈夫曼树可以获得对应的编码表。在图4中，左子树的前缀为0，右子树的前缀为1，由此可以获得每个叶节点字符的编码值。编码表由每个字符及其对应的码字组成，除此之外还需存储每个码字的长度。表1是根据图4中的Huffman树获得的编码表。图 4 根据字符频率生成的哈夫曼树 Figure 4 Huffman tree generated based on symbol frequency 表 1 哈夫曼编码表 Table 1 Huffman codling table 字符 码字 码字长度 A 11 2 B 100 3 C 0 1 D 101 3 2 方案设计 本文针对k-匿名模型原始数据与匿名数据之间存在的关联性，提出了k-匿名模型的原始数据压缩方案。该方案计算原始数据同匿名数据之间的差值，由于差值不同的数据的频率相差较大，数据具有一定重复性，故使用哈夫曼编码对其进行压缩存储。通过存储差值可以间接获得原始数据，并减少原始数据的存储空间。对于匿名数据，随着模型的k值变大，其泛化层级也会变高，使得匿名化后的数据具有一定的重复性。针对这一特点，本文提出了k-匿名模型的匿名数据压缩方案，通过哈夫曼进行压缩以减少其存储空间。由于k-匿名模型的泛化操作对象为准标识符属性，故本文只讨论对于准标识符属性的压缩。2.1 k-匿名模型的原始数据压缩 通过设定规则将原始数据与匿名数据之间的关系进行具体化表示，即计算其差值。根据差值的统计特性对其进行压缩存储。给定一个原始数据表T，T的准标识符为11QI,nmDD CC=?，iD和jC分别为数值型属性和分类型属性，其中1in，1jm，68 网络与信息安全学报 第 9 卷 n 和 m 分别为QI包含的数值型属性和分类型属性的个数。经过匿名化处理后得到的匿名数据表为T。对于准标识符中的数值型属性iD，假定其原始数据的值为x，在经过泛化处理后x存在3种情况。1)x被泛化到对应泛化层次的区间,a b，其中axb。2)x被泛化到最高泛化层次，最高泛化层次为字符*。3)x的泛化层次为第一个层次，即泛化前后x的值不变。针对数值型属性iD 计算其差值，若x被泛化到区间,a b，则xa=。若x被泛化为*，统计原始数据中iD 的不同数值出现的频率，按频率对数值进行降序排序，并建立关于*的字典(*)iDZ。假定iD 共有d 个不同的数值，将排序后的数值设定为字典的键，字典的值依次分配为0至d。在这种情况下，为字典(*)iDZ中键 x对应的值。若泛化前后 x的值不变，则0=。对于准标识符中的分类型属性jC，假定其原始数据的值为 y，在经过泛化处理后 y 存在两种情况。1)y 被泛化到对应泛化层级的值y；2)y 的泛化层次为第一个层次，即泛化前后y 的值不变。针对分类型属性jC 计算其差值，若 y 被泛化到对应泛化层级的值 y，y 通常对应于原始数据表T 中多个不同值。假定 y 对应于T 中c 个不同的值ky，其中0kc。根据原始数据表T 与匿名数据表T 之间的泛化层级的信息，建立 y 的字典()jCyZ。统计ky的频率，按频率对其进行降序排序。将排序后的值设定为字典的键，字典的值依次分配为0至c。为字典()jCyZ中键ky对应的值。若泛化前后y的值不变，则0=。通过匿名数据表T、差值、字典(*)iDZ和()jCyZ可以计算得出原始数据表T，存储差值及字典可以减少存储原始数据表所占用的存储空间。由于在对进行设置的过程中，对泛化为*的数值型以及泛化为y的分类型的原始数据按频率进行排序，故为0等较小的值出现的频率较高，其数据具有一定的重复性。统计不同值的个数和频率，并使用哈夫曼编码进行压缩可以有效减少其存储空间。对原始数据的压缩过程如算法1所示。算法 1 原始数据压缩 输入 原始数据表T，匿名数据表T，准标识符11QI,nmDD CC=?输出 Huffman压缩结果及编码表oR，字典Z 1)0oR 2)for QIiD do 3)for ixD do 4)if x被泛化为,a b then 5)xa=6)end if 7)if x被泛化为*then 8)(*).get()iDZx=9)end if 10)if x泛化前后不变 then 11)0=12)end if 13)end for 14)Huffman()ooRR+15)(*)iDZZZ+16)end for 17)for QIjC do 18)for jyC do 19)if y被泛化为y then 20)().get()jCyZy=21)end if 22)if y泛化前后不变 then 23)0=24)end if 25)end for 26)Huffman()ooRR+27)()jCyZZZ+28)end for 29)return,oR Z 2.2 k-匿名模型的匿名数据压缩 在匿名化操作的过程中，匿名数据表T由原始数据表T经过泛化算法运算获得，通常根据泛第 4 期 于玥等：基于哈夫曼的 k-匿名模型隐私保护数据压缩方案 69 化程度的需要对k值进行设定。由于泛化算法会根据预设的泛化层级将不同的数据泛化为同一数据，泛化后T中的数据会具有一定的重复性，且k值设定的数值越大，T的泛化程度越高，数据的重复性越大，利用这一特点对匿名数据进行压缩。给定一个匿名数据表T，T的准标识符为12QI,nA AA=?，其中n为QI包含的属性的个数。对于T中的QI属性数据，其具有重复性，适用于哈夫曼编码进行压缩。分别统计QI中每个属性的不同值的个数和频率，使用哈夫曼进行压缩。特别地，当泛化程度非常高时，泛化后的数据只具有一个值（最高泛化层级*），则直接记录该值及其对应的数量。对匿名数据的压缩过程如算法2所示。算法 2 匿名数据压缩 输入 匿名数据表T，准标识符1QI=,A 2,nAA?输出 Huffman压缩结果及编码表aR 1)0aR 2)for QIiA do 3)if iA只包含一个值 then 4)将该值及其对应的数量存储为u 5)aaRRu+6)end if 7)if iA包含多个值 then 8)Huffman()aaiRRA+9)end if 10)end for 11)return aR 3 实验结果与分析 3.1 数据集及实验环境 本文实验使用的数据集来源于UC Irvine Machine Repository的Adult数据集23，该数据集是研究k-匿名最常采用的数据源之一。通过对数据集进行完整性和适用性检测，最终选用Adult数据集中的adult.data文件作为实验的数据样本，其大小为3.79 MB，包含15个属性和32 561条数据。删除含有空值和非法值的元组后，共有30 162条数据。选择数据集中的9个属性作为准标识符的属性集，表2中描述了准标识符属性的数据结构。表 2 数据结构示意 Table 2 Schematic of data structure 编号 属性 类别 不同值个数 可泛化层级1 Age 数值型 72 5 2 Education 分类型 16 4 3 Marital-status分类型 7 3 4 Native-country分类型 41 3 5 Occupation 分类型 14 3 6 Race 分类型 5 2 7 Gender 分类型 2 2 8 Salary-class分类型 2 2 9 Workclass 分类型 7 3 各属性的泛化层次定义如下。Age，泛化层次为5层。第1个层次：原始数据；第2个层次：5年间隔；第3个层次：10年间隔；第4个层次：20年间隔；第5个层次：*。Education，泛化层次为4层。第1个层次：原始数据；第2个层次：Undergraduate、Graduate、High School、Primary School、Professional Edu-cation；第3个层次：Higher Education、Primary Education、Secondary Education；第4个层次：*。Marital-status，泛化层次为3层。第1个层次：原始数据；第2个层次：spouse present、spouse not present；第3个层次：*。Native-country，泛化层次为3层。第1个层次：原始数据；第2个层次：North America、Asia、Europe、Africa、South America；第3个层次：*。Occupation，泛化层次为3层。第1个层次：原始数据；第2个层次：Technical、Non-technical、Other；第3个层次：*。Race、Gender、Salary-class，泛化层次均为2层。第1个层次：原始数据；第2个层次：*。Workclass，泛化层次为3层。第1个层次：原始数据；第2个层次：Government、Non-Government、Unemployed；第3个层次：*。对于模拟实验，使用的操作系统为Windows 11；硬件环境为11th Gen Intel Core i5-1135G7，4核2.4 GHz主频，内存为16 GB；编译环境Python 3.8.6。3.2 原始数据压缩实验 为验证所提出的k-匿名模型的原始数据压缩70 网络与信息安全学报 第 9 卷 方案的有效性，本文采用5个经典的k-匿名模型进行对比实验，包括两个全域泛化算法模型Incognito19、Datafly18，以及3个局域泛化算法模型Top-down20、Mondrian21、Basic Mondri-an22。实验设置模型的k值分别为5、10、50、100，对比本文方法以及Windows 11的zip工具的压缩效果。全域泛化模型原始数据的压缩率对比如图5所示，图中Huf代表本文方案。对于Incognito模型，当k值分别为5、10、50、100时，本文方案的压缩率相较于Windows 11的zip压缩率分别降低了76.7%、74.7%、70.3%、68.6%；对于Datafly模型，其压缩率分别降低了70.9%、68.7%、68.7%、68.7%。从图中可以看出，当k值增大时压缩率存在小幅上涨，这是由于泛化层次变高，导致匿名数据的信息损失度增大，在计算匿名数据同原始数据的差值时字典变大。相较于低k值，高k值的数据频率有所降低。特别地，对于Datafly模型，由于其模型本身对数据的泛化程度较高、信息损失度较大。当k值为10时，Datafly模型中部分准标识符属性已达到最大泛化层级，故继续增大k值其压缩率保持不变。图 5 全域泛化模型原始数据的压缩率对比 Figure 5 Comparison of raw data compression rates of full-domain generalization models 局域泛化模型原始数据的压缩率对比如图6所示，图中Huf代表本文方案。对于Top-down模型，当k值分别为5、10、50、100时，本文方案的压缩率相较于Windows 11的zip压缩率分别降低了75.3%、72.4%、67.1%、65.4%；对于Mondrian模型，其压缩率分别降低了78.7%、77.4%、71.9%、71.5%；对于Basic Mondrian模型，其压缩率分别降低了76.4%、74.2%、72.7%、72.3%。图 6 局域泛化模型原始数据压缩率对比 Figure 6 Comparison of raw data compression rates for local generalization models 对于不同k值的全域泛化模型Incognito、Datafly，本文方案的压缩率平均降低了72.6%、69.3%。对于局域泛化模型Top-down、Mondrian、Basic Mondrian，本文方案的压缩率平均降低了70.1%、74.9%、73.9%，证明本文提出的针对k-匿名模型的原始数据压缩方案优于Windows 11的zip压缩工具。表3罗列了5个模型及其最大泛化程度对应的k值，即当表2中的9个准标识符属性均达到最大泛化层次时，5个模型对应的k值。其中对于Datafly模型，k=10时除Gender属性和Education属性外其余准标识符属性均达到最大泛化层次，继续增大k值会使用隐匿方法去除不满足k-匿名条件的记录，导致数据表失真严重从而使数据表失去可用性，故Datafly模型的k值取10。表 3 模型及其最大泛化程度对应的 k 值 Table 3 The model and its maximum generalization degree corresponding to the value of k 模型 k 值 Incognito 1 800 Datafly 10 Top-down 2 700 Mondrian 14 100 Basic Mondrian 15 000 Windows 11的zip压缩工具对原始数据的压缩率为7.87%，当全部9个准标识符属性均达到最大泛化层次时，本文提出的原始数据压缩方案第 4 期 于玥等：基于哈夫曼的 k-匿名模型隐私保护数据压缩方案 71 的压缩率为3.46%，即无论k值如何增大，压缩率最大为3.46%，相较于Windows 11的zip压缩工具，本文方案仍有更优的压缩率。需要注意的是，表3列出的k值是为了说明达到最大泛化程度时模型的k值大小，而实际应用中通常不会将k值设置过大，这是因为k值过大会导致数据失去可用性。表4列出了k值为5、10、50和100时，本文提出的原始数据压缩方案和Windows 11的zip压缩工具的压缩时间对比，从表中可以看出，本文所提的压缩方案需要花费的时间更少、开销更小。表 4 原始数据压缩时间对比 Table 4 Original data compression time comparison 模型 压缩时间/ms k=5 k=10 k=50 k=100 Incognito 33.4 33.6 34.9 35.4 Datafly 34.5 35.2 35.2 35.2 Top-down 33.6 34.4 35.7 36.4 Mondrian 32.9 33.2 34.5 34.7 Basic_Mondrian 33.5 34.1 34.3 34.4 zip 43.5 43.5 43.5 43.5 3.3 匿名数据压缩实验 匿名数据压缩实验的模型设置同3.2节原始数据压缩实验。表5列出了全域泛化模型匿名数据压缩率对比（即相较于zip，本文方案的压缩率降低的百分比）。从表中可知，对于不同k值的Incognito及Datafly模型，本文方案的压缩率相较于zip平均降低了60.6%、72%。表 5 全域泛化模型匿名数据压缩率对比 Table 5 Comparison of anonymized data compression rates for the full domain generalization models 模型及 k 值设置 zip 压缩率 本文方案压缩率 压缩率对比 Incognito(k=5)7.77%2.87%63.1%Incognito(k=10)7.54%2.82%62.6%Incognito(k=50)6.75%2.74%59.4%Incognito(k=100)6.08%2.59%57.4%Datafly(k=5)3.42%1.06%69%Datafly(k=10)3.18%0.86%73%Datafly(k=50)3.18%0.86%73%Datafly(k=100)3.18%0.86%73%表6列出了局域泛化模型匿名数据的压缩率对比（即相较于zip，本文方案的压缩率降低的百分比）。从表中可知，对于不同k值的Top-down、Mondrian、Basic Mondrian模型，本文所提方案的压缩率相较于zip平均降低了61.5%、68.6%、58.2%，证明本文提出的针对k-匿名模型的匿名数据压缩方案优于Windows 11的zip压缩工具。表 6 局域泛化模型匿名数据压缩率对比 Table 6 Comparison of anonymized data compression rates for the local generalization models 模型及 k 值设置 zip 压缩率 本文方案压缩率 压缩率对比Top-down(k=5)7.70%2.91%62.2%Top-down(k=10)7.51%2.84%62.2%Top-down(k=50)6.94%2.67%61.5%Top-down(k=100)6.66%2.65%60.2%Mondrian(k=5)7.26%2.58%64.5%Mondrian(k=10)6.46%2.19%66.1%Mondrian(k=50)4.34%1.28%70.5%Mondrian(k=100)3.36%0.90%73.2%Basic Mondrian(k=5)7.87%2.96%62.4%Basic Mondrian(k=10)7.57%2.92%61.4%Basic Mondrian(k=50)6.10%2.81%53.9%Basic Mondrian(k=100)4.95%2.22%55.2%表7和表8分别列出了全域泛化模型、局域泛化模型的匿名数据压缩时间对比。从表中可以看出，对于不同算法及不同k值设置，本文提出的匿名数据压缩方案的压缩时间均少于Windows 11的zip压缩工具，需要的计算开销更小。表 7 全域泛化模型的匿名数据压缩时间对比 Table 7 Comparison of anonymized data compression time for the full domain generalization models 模型及 k 值设置 压缩时间/ms zip 本文方案 Incognito(k=5)43.6 28.7 Incognito(k=10)42.9 27.5 Incognito(k=50)42.1 26.9 Incognito(k=100)41.5 26.2 Datafly(k=5)32.5 18.2 Datafly(k=10)31.4 16.6 Datafly(k=50)31.4 16.6 Datafly(k=100)31.4 16.6 72 网络与信息安全学报 第 9 卷 表 8 局域泛化模型的匿名数据压缩时间对比 Table 8 Comparison of anonymized data compression time for the local generalization models 模型及 k 值设置 压缩时间/ms zip 本文方案 Top-down(k=5)41.5 27.4 Top-down(k=10)40.8 26.8 Top-down(k=50)39.4 25.7 Top-down(k=100)38.9 25.5 Mondrian(k=5)40.8 24.7 Mondrian(k=10)38.4 19.3 Mondrian(k=50)34.5 17.8 Mondrian(k=100)32.3 17.5 Basic Mondrian(k=5)42.5 28.1 Basic Mondrian(k=10)41.1 27.6 Basic Mondrian(k=50)37.9 26.3 Basic Mondrian(k=100)35.8 22.7 4 讨论 现阶段还没有针对k-匿名脱敏前后数据压缩方案的设计，基于数据发布阶段k-