异或运算下(2,n)分存规模的极小值

被引：6

作者：

杨克 ^{[1
]}

林行良 ^{[1
]}

潘平 ^{[1
]}

戴一奇 ^{[1
]}

机构：

[1] 清华大学计算机科学与技术系

来源：

清华大学学报(自然科学版) | 1998年 / S1期

关键词：

（2.n）分存; 三值立方体; 数据规模;

D O I：

10.16511/j.cnki.qhdxxb.1998.s1.011

中图分类号：

TP311, [];

学科分类号：

081202 ; 0835 ;

摘要：

信息分存引起的数据规模膨胀在实际应用中成为一个十分值得重视的问题。但问题本身的复杂性使得在一般情况下计算（ｋ，ｎ）分存的极小规模变得十分困难，即使是在实际应用中比较常用的异或运算下的（２，ｎ）分存，其最小规模问题至今也尚未解决。因此提出了一个“三值立方体”模型及相应的“顶点”，“象限”，“覆盖”和“覆盖集”等概念，讨论了它们的性质和特点，并利用该模型求出异或运算下（２，ｎ）分存的极小值为ｎｌｏｇ２ｎ＋ｎ－２ｌｏｇ２ｎ，同时也给出了具体的实现方案。

引用

页码：51 / 54

页数：4