陳建兵， 梁立， 葉志霞

(1.云南師范大學(xué) 信息管理處,云南 昆明650500；2.云南師范大學(xué) 信息學(xué)院,云南 昆明650500)

1 引 言

對(duì)有限集合Xn={x1,x2,…,xn}的集族T，若滿(mǎn)足下面兩個(gè)條件：

(1)空集Ф和全集Xn都在T中(可行性)；

(2)對(duì)任意A,B∈T，都有A∩B∈T且A∪B∈T(封閉性);

則稱(chēng)集族T為Xn上的一個(gè)有限拓?fù)?

只由空集和全集組成的拓?fù)浞Q(chēng)為平庸拓?fù)?，由全部子集組成的拓?fù)浞Q(chēng)為離散拓?fù)?如果拓?fù)銽滿(mǎn)足∪A∈T{Ф,Xn}A≠Xn,稱(chēng)T為Xn上的α拓?fù)?例如X={a,b,c}的離散拓?fù)涫莧Ф,{a},,{c},{a,b},{a,c},{b,c},X}；{Ф,{a},,{a,b},X}是X上的一個(gè)α拓?fù)?

有限拓?fù)涞膽?yīng)用十分廣泛，特別是在數(shù)據(jù)壓縮和信息安全方面的應(yīng)用[1].有限拓?fù)涞臄?shù)量相當(dāng)龐大，給計(jì)算和存儲(chǔ)帶來(lái)壓力[2]，因此有限拓?fù)涞木幋a和壓縮非常重要.

2 拓?fù)渚幋a

用算法構(gòu)建拓?fù)湫枰獙?duì)拓?fù)溥M(jìn)行編碼，拓?fù)湫畔⒌拇鎯?chǔ)也需要編碼.拓?fù)涞木幋a直接影響算法的時(shí)間復(fù)雜度和空間復(fù)雜度.因?yàn)橛邢藜系淖蛹瘮?shù)是2n，所以容易想到用二進(jìn)制數(shù)對(duì)其進(jìn)行編碼.拓?fù)渚幋a的基礎(chǔ)是集合的編碼和集族的編碼.

2.1 集合的編碼

n元集合的表示方法有很多，最直接的方法是用長(zhǎng)度為n的字符串或者字符數(shù)組表示，但字符串表示集合存在以下問(wèn)題：一是占用的空間比較多，n元集合至少占用n個(gè)字節(jié)的空間；二是集合運(yùn)算比較復(fù)雜，拓?fù)渲兄饕羌系摹敖弧迸c“并”運(yùn)算，集合的交運(yùn)算需要求解類(lèi)似“最長(zhǎng)公共子序列”問(wèn)題，集合的并運(yùn)算除了字符串連接還需要字符串去重以保證集合中的元素唯一；三是集族的表示需要字符串?dāng)?shù)組(或二維字符數(shù)組).

雖然有些計(jì)算機(jī)語(yǔ)言(如Pascal和Python)有集合數(shù)據(jù)類(lèi)型，但運(yùn)算其實(shí)也是字符串的運(yùn)算，仍然沒(méi)有解決空間和時(shí)間的問(wèn)題，而拓?fù)鋽?shù)據(jù)量的龐大必然需要追求存儲(chǔ)空間少和計(jì)算速度快.

實(shí)際上，在拓?fù)溥\(yùn)算中最關(guān)心的是n元集合的子集之間的運(yùn)算，因?yàn)樽蛹g的“交”和“并”的運(yùn)算比較頻繁.

如果用一個(gè)n位二進(jìn)制數(shù)xn-1xn-2…x1x0表示n元集合Xn的子集S:

則集合的運(yùn)算就是二進(jìn)制按位運(yùn)算，運(yùn)算簡(jiǎn)單且速度快，即

交集：A∩B=A&B

并集：A∪B=A|B

包含：A?S?A&S==A

例如，3元集合{a,b,c}的子集{a,b}=0112=3，{a,c}=1012=5，且

{a,b}∩{a,c}=011&101=001={a}

{a,b}∪{a,c}=011|101=111={a,b,c}{a,b}=111&(～011)=111&100=100={c}

這里～011可能得到的結(jié)果是11111100而不是100，所以必須跟Xn求“與”運(yùn)算.

n元集合只需要n位二進(jìn)制數(shù)，比n個(gè)字節(jié)的字符串所需存儲(chǔ)空間至少少7倍(至少的意思是字符串還需要結(jié)束標(biāo)志或者字符串的長(zhǎng)度)，二進(jìn)制數(shù)按位運(yùn)算的速度快，而且自然“去重”保證了集合中的元素唯一.

集合的大小就是集合的編碼數(shù)值.例如{a,b} < {a,c}.

2.2 集族的編碼

n元集合的全部子集(包括空集和全集)有2n個(gè)，也就是離散拓?fù)涞拈L(zhǎng)度是2n.很容易想到用一個(gè)數(shù)組表示一個(gè)集族，但每一個(gè)集族的長(zhǎng)度(基數(shù))不一樣，所以必須標(biāo)記集族的長(zhǎng)度或者集族之間的分隔符.用數(shù)組的第一個(gè)元素表示集族的長(zhǎng)度比較方便.

例如，對(duì)3元集合{a,b,c}的一個(gè)集族{ {a},,{a,b},{a,c} }可表示為：

40012010201121012

用十進(jìn)制數(shù)表示這個(gè)數(shù)組：

41235

下面這個(gè)數(shù)組表示了集合{a,b,c}的一個(gè)拓?fù)鋥Φ,{a},,{a,b},{a,c},{a,b,c} }：

6012357

因而集族{Φ,{a},,{a,b},{a,c},{a,b,c} }={0,1,2,3,5,7}.

這種方法對(duì)驗(yàn)證集族或拓?fù)涞姆忾]性比較方便[3]，但是需要的存儲(chǔ)空間比較大(每個(gè)元素的最大取值是2n-1).因?yàn)榧謇锏淖蛹≈凳?～2n-1間的連續(xù)整數(shù)，所以用2n位二進(jìn)制數(shù)表示一個(gè)集族也是可以的.二進(jìn)制的位置編號(hào)(從低位到高位編號(hào)0～2n-1)對(duì)應(yīng)子集的十進(jìn)制數(shù)，這就是占位編碼.

例如上面例子中的集族{Ф,{a},,{a,b},{a,c},{a,b,c} }可以表示為23=8位二進(jìn)制數(shù)：10101111(如表1)，也就是位置編號(hào)為0,1,2,3,5,7的二進(jìn)制數(shù)為1，其余為0.

表1 二進(jìn)制的位置編號(hào)

2.3 拓?fù)涞木幋a

拓?fù)涫翘厥獾募?根據(jù)拓?fù)涞目尚行?拓?fù)渲斜仨毎占腿?，每個(gè)拓?fù)涠加锌占腿酝負(fù)涞木幋a可以去掉空集和全集，只對(duì)其余2n-2個(gè)子集編碼，因此可用2n-2位二進(jìn)制數(shù)表示一個(gè)拓?fù)?

例如上面例子中的拓?fù)鋥Ф,{a},,{a,b},{a,c},{a,b,c} }可以表示為23-2=6位二進(jìn)制數(shù)010111.雖然010111={1,2,3,5}不是一個(gè)拓?fù)?，但在將它視為拓?fù)鋾r(shí)，只需添加空集和全集就變成{0,1,2,3,5,7}.

因?yàn)槎M(jìn)制數(shù)的位置編號(hào)與拓?fù)渲械淖蛹灰粚?duì)應(yīng)，所以對(duì)二進(jìn)制編碼的拓?fù)浣獯a也很容易.

3 拓?fù)渚幋a算法

拓?fù)溆袃煞N表示，第一種是數(shù)組形式，主要用于計(jì)算；第二種是二進(jìn)制形式，用于存儲(chǔ)以節(jié)省空間;因此，把計(jì)算結(jié)果用于存儲(chǔ)時(shí)需要把第一種形式變成第二種形式，這個(gè)過(guò)程是拓?fù)涞木幋a；需要計(jì)算時(shí)取出第二種形式的二進(jìn)制數(shù)據(jù)變成第一種形式的數(shù)組，這是解碼.

因?yàn)榻^大多數(shù)拓?fù)渲械淖蛹潜容^稀疏的，也就是拓?fù)涞亩M(jìn)制數(shù)中0比較多，因此，為了節(jié)約存儲(chǔ)空間，可把二進(jìn)制數(shù)進(jìn)行壓縮.

3.1 拓?fù)渚幋a算法

拓?fù)渚幋a算法：把數(shù)組表示的拓?fù)銽編碼為二進(jìn)制表示的拓?fù)銽B.

輸入：數(shù)組T.//T[0]表示拓?fù)涞拈L(zhǎng)度，T[1]表示空集，T[T[0]]表示全集

對(duì)k從2到T[0]-1，做

x=T[k]; // 取一個(gè)子集在二進(jìn)制里的占位編號(hào)

i=(x-1) / 8; // 在第幾個(gè)字節(jié)

j=(x-1)x%8; // 在字節(jié)內(nèi)的占位編號(hào)

TB[i] = (1<

輸出：數(shù)組TB.//數(shù)組TB的類(lèi)型是字節(jié)，長(zhǎng)度是2n-3.

例如n=5時(shí)，Xn={a,b,c,d,e}

拓?fù)洌簕 Φ,{a},{a,d},{a,b,d},{a,e},{a,d,e},{a,b,d,e},{a,b,c,d,e} }

輸入數(shù)組T：{ 8,0,1,9,11,17,25,27,31 }//8是數(shù)組的長(zhǎng)度

輸出數(shù)組TB： 00000001 00000101 00000001 00000101

第0字節(jié)：00000001(表示子集1={a})

第1字節(jié)：00000101(表示子集9={a,d},11={a,b,d})

第2字節(jié)：00000001(表示子集17={a,e})

第3字節(jié)：00000101(表示子集25={a,d,e}，27={a,b,d,e})

輸出數(shù)組TB中并不包含空集和全集，因?yàn)槊恳粋€(gè)拓?fù)涠及占腿?輸出數(shù)組TB不需要記數(shù)組的長(zhǎng)度，因?yàn)樗鼈兊拈L(zhǎng)度都一樣(2n-3).

可以看出，數(shù)組表示需要9個(gè)字節(jié)，二進(jìn)制表示需要4個(gè)字節(jié)，二進(jìn)制表示1的個(gè)數(shù)就是拓?fù)涞拈L(zhǎng)度(不含空集與全集).從上例還看到拓?fù)渲?的數(shù)量很少，因此，拓?fù)涞亩M(jìn)制形式很稀疏(0很多)，有利于數(shù)據(jù)壓縮.

3.2 拓?fù)浣獯a算法

拓?fù)浣獯a算法：把二進(jìn)制表示的拓?fù)銽B解碼為數(shù)組表示的拓?fù)銽.

輸入：數(shù)組TB.//共有bytes=2n-3個(gè)元素的字節(jié)數(shù)組(當(dāng)n≤3時(shí)bytes=1)

初值j=2;

對(duì) i 從0到bytes-1，做：//對(duì)第i個(gè)字節(jié)處理

x = TB[i];

k = 8 * i;

對(duì)y從1到8，做: //y是在字節(jié)內(nèi)的占位編號(hào)

如果x&1 ≠0，則T[j++]= k+y; //1的位置k+y是子集的編號(hào)

x >>=1;

T[0]=j; //拓?fù)溟L(zhǎng)度

T[1]=0; //空集

T[j]=2n-1; //全集

輸出：數(shù)組T.//T中元素的最大取值2n-1.

輸入數(shù)組TB不包含空集和全集，所以輸出數(shù)組T需要添加空集和全集并計(jì)入數(shù)組長(zhǎng)度.

例如n=5時(shí)，Xn={a,b,c,d,e}.

輸入數(shù)組TB：00000001 00000101 00000001 00000101

第0字節(jié)：00000001(表示子集1={a})

第1字節(jié)：00000101(表示子集9={a,d},11={a,b,d})

第2字節(jié)：00000001(表示子集17={a,e})

第3字節(jié)：00000101(表示子集25={a,d,e}，27={a,b,d,e})

輸出數(shù)組T：{ 8,0,1,9,11,17,25,27,31 }

需要說(shuō)明的是，二進(jìn)制數(shù)組TB原本是一個(gè)長(zhǎng)數(shù)據(jù)，應(yīng)該從低字節(jié)到高字節(jié)從右向左排列，但程序設(shè)計(jì)時(shí)用到數(shù)組元素下標(biāo)從0開(kāi)始由左向右；另外，TB習(xí)慣上看見(jiàn)的是十進(jìn)制數(shù)，比如上面的TB={1,5,1,5}，視為4字節(jié)的長(zhǎng)數(shù)據(jù)的二進(jìn)制數(shù)是00000101 00000001 00000101 00000001(十六進(jìn)制數(shù)是05010501)，它的十進(jìn)制數(shù)是83952897.所以，相當(dāng)于用十進(jìn)制數(shù)83952897表示了拓?fù)鋥 Φ,{a},{a,d},{a,b,d},{a,e},{a,d,e},{a,b,d,e},{a,b,c,d,e} }.但是，當(dāng)n越來(lái)越大時(shí)(如n≥7)，沒(méi)有任何一種編程語(yǔ)言能表示2n-2位這樣大的整數(shù)類(lèi)型，即使64位的編程語(yǔ)言也只能取到n=6，所以就用字節(jié)數(shù)組來(lái)組裝這個(gè)拓?fù)涠M(jìn)制數(shù).

4 算法實(shí)驗(yàn)

在拓?fù)涞臉?gòu)造過(guò)程中生成一棵拓?fù)錁?shù)，只有α拓?fù)鋄2]是非葉子節(jié)點(diǎn)，所以只需存儲(chǔ)α拓?fù)鋽?shù)據(jù).把α拓?fù)浯嫒霐?shù)據(jù)文件，其數(shù)據(jù)量如表2所示.

從表2可以看出，拓?fù)涞亩M(jìn)制形式比數(shù)組形式所需要的存儲(chǔ)空間小很多，而且二進(jìn)制形式的數(shù)據(jù)壓縮比很高.

表2 α拓?fù)涞臄?shù)據(jù)量

5 結(jié)束語(yǔ)

有限拓?fù)涞臄?shù)據(jù)量很大，拓?fù)溆?jì)算對(duì)空間復(fù)雜度和時(shí)間復(fù)雜度要求都很高，因此數(shù)據(jù)的編碼很重要.拓?fù)涞木幋a首先是子集的編碼，用二進(jìn)制對(duì)子集編碼，運(yùn)算方便且速度快；再用二進(jìn)制數(shù)對(duì)拓?fù)溥M(jìn)行編碼，編碼算法簡(jiǎn)單，數(shù)據(jù)的壓縮率非常高.實(shí)驗(yàn)表明，當(dāng)n=8時(shí)壓縮率達(dá)到7.54%.如果對(duì)拓?fù)涞挠?jì)算不需要解碼就更好了.