有限拓?fù)涞木幋a算法*

陳建兵， 梁立， 葉志霞

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

1 引 言

對有限集合Xn={x1,x2,…,xn}的集族T，若滿足下面兩個條件：

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

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

則稱集族T為Xn上的一個有限拓?fù)?

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

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

2 拓?fù)渚幋a

用算法構(gòu)建拓?fù)湫枰獙ν負(fù)溥M(jìn)行編碼，拓?fù)湫畔⒌拇鎯σ残枰幋a.拓?fù)涞木幋a直接影響算法的時間復(fù)雜度和空間復(fù)雜度.因為有限集合的子集數(shù)是2n，所以容易想到用二進(jìn)制數(shù)對其進(jìn)行編碼.拓?fù)渚幋a的基礎(chǔ)是集合的編碼和集族的編碼.

2.1 集合的編碼

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

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

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

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

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

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

2.2 集族的編碼

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

例如，對3元集合{a,b,c}的一個集族{ {a},,{a,b},{a,c} }可表示為：

40012010201121012

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

41235

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

6012357

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

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

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

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

2.3 拓?fù)涞木幋a

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

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

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

3 拓?fù)渚幋a算法

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

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

3.1 拓?fù)渚幋a算法

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

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

對k從2到T[0]-1，做

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

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

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

TB[i] = (1<

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

例如n=5時，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ù)組的長度

輸出數(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中并不包含空集和全集，因為每一個拓?fù)涠及占腿?輸出數(shù)組TB不需要記數(shù)組的長度，因為它們的長度都一樣(2n-3).

可以看出，數(shù)組表示需要9個字節(jié)，二進(jìn)制表示需要4個字節(jié)，二進(jìn)制表示1的個數(shù)就是拓?fù)涞拈L度(不含空集與全集).從上例還看到拓?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個元素的字節(jié)數(shù)組(當(dāng)n≤3時bytes=1)

初值j=2;

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

x = TB[i];

k = 8 * i;

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

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

x >>=1;

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

T[1]=0; //空集

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

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

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

例如n=5時，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 }

需要說明的是，二進(jìn)制數(shù)組TB原本是一個長數(shù)據(jù)，應(yīng)該從低字節(jié)到高字節(jié)從右向左排列，但程序設(shè)計時用到數(shù)組元素下標(biāo)從0開始由左向右；另外，TB習(xí)慣上看見的是十進(jìn)制數(shù)，比如上面的TB={1,5,1,5}，視為4字節(jié)的長數(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越來越大時(如n≥7)，沒有任何一種編程語言能表示2n-2位這樣大的整數(shù)類型，即使64位的編程語言也只能取到n=6，所以就用字節(jié)數(shù)組來組裝這個拓?fù)涠M(jìn)制數(shù).

4 算法實驗

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

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

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

5 結(jié)束語

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