一種改進(jìn)的海量信息分類算法

戴立平，譚正華，張進(jìn)修，張又文

(湘潭大學(xué) 信息工程學(xué)院，湖南 湘潭 411105)

0 引 言

信息的分類常常表現(xiàn)為樹狀結(jié)構(gòu)，在實(shí)際應(yīng)用中，一般用Table表表示，而快速生成資訊的所在路徑和實(shí)現(xiàn)某個(gè)分類的增刪，是研究的關(guān)鍵和熱點(diǎn)。

通常情況下，在數(shù)據(jù)庫(kù)中對(duì)每一個(gè)分類新建一個(gè)數(shù)據(jù)表，增加一個(gè)分類就增加一張表。當(dāng)需要將該分類的信息顯示時(shí)，通過查找找到該分類的數(shù)據(jù)表，但操縱數(shù)據(jù)表比操縱數(shù)據(jù)表中的記錄困難得多，因此數(shù)據(jù)表的多少直接關(guān)系到查詢的效率。

Hao Chunmei等[1]提取信息屬性的特征，根據(jù)特征建立優(yōu)化信息分類模型，實(shí)現(xiàn)高效的信息分類，為快速查詢搜索目標(biāo)提供支持；張成剛等[2]提出利用降噪編碼自適應(yīng)神經(jīng)網(wǎng)絡(luò)對(duì)采集的信息進(jìn)行降噪處理并利用分類規(guī)則對(duì)海量信息進(jìn)行智能分類，但該方法計(jì)算過程較為復(fù)雜，且分類耗時(shí)較長(zhǎng)；曾勁松等[3]提出基于沖突博弈算法的海量信息智能分類，通過提取信息特征，確定信息分類策略。

以上方法難以很好地解決信息分類查詢的效率問題，因此文中提出一種海量信息分類算法，包括信息分類編碼和算法API，實(shí)現(xiàn)了分類處理的各種應(yīng)用需求，進(jìn)一步提高了查詢搜索效率。

1 普通的信息分類方法

在信息分類中，樹形結(jié)構(gòu)的每一個(gè)節(jié)點(diǎn)表示一個(gè)分類[4]，定義一個(gè)Catalog表，分類節(jié)點(diǎn)中只保留一個(gè)Name信息。添加一個(gè)CatalogId自增主鍵作為節(jié)點(diǎn)編號(hào)。為了將該樹形結(jié)構(gòu)更為準(zhǔn)確地描述出來(lái)，在節(jié)點(diǎn)中再增加一個(gè)字段，將這個(gè)字段命名為FatherID。如果節(jié)點(diǎn)ID2是ID1的子節(jié)點(diǎn)，那么說(shuō)明這個(gè)分類是該分類的子節(jié)點(diǎn)，即ID1就是ID2的FatherID。約定0為第一層父類編碼，作為一個(gè)在數(shù)據(jù)庫(kù)中無(wú)任何記錄的虛擬分類。

上面定義的Catalog表可以較為輕松地恢復(fù)出一棵分類樹。當(dāng)需要查找該父類的下級(jí)分類時(shí)，只需要使用SQL語(yǔ)句選擇表中FatherID=FID的部分。通過調(diào)用尋找分類下子分類的GetChildren函數(shù)，然后把該子分類的CatalogId主鍵作為下一個(gè)分類的FatherID，通過遞歸調(diào)用得到該分類下的所有子分類[5]。

假設(shè)要搜索某一個(gè)大類下的所有資訊，該大類下有較多的分類層級(jí)，而且資訊靠近根分類[6]。不僅需要搜索出大分類的信息，也要將子分類的信息搜索出來(lái)。一般情況下，將遞歸調(diào)用GetChildren函數(shù)查找得到所有分類及其子分類，通過獲得的分類ID，調(diào)用GetProduct函數(shù)查詢?cè)摲诸悓?duì)應(yīng)的產(chǎn)品。比如一個(gè)分類下其子分類，子子分類有20個(gè)，那么函數(shù)調(diào)用次數(shù)將達(dá)到20次，其查詢效率較為低下。

2 分類編碼的優(yōu)化設(shè)計(jì)

2.1 文檔分類存儲(chǔ)表結(jié)構(gòu)

在設(shè)計(jì)中，主要使用了兩張表(見圖1)。

圖1 數(shù)據(jù)結(jié)構(gòu)表

一張為信息分類基礎(chǔ)DocCatalog表，主要用來(lái)存儲(chǔ)文檔的分類信息，里面主要有4個(gè)關(guān)鍵字段。其中CatalogId為分類節(jié)點(diǎn)ID，F(xiàn)atherId為分類父節(jié)點(diǎn)ID，Name為分類名稱；另一張表為Documents表，主要用來(lái)存儲(chǔ)文檔數(shù)據(jù)，關(guān)鍵字段：DocId為文檔ID，CatalogId為文檔所屬分類ID，這個(gè)字段作為外鍵與DocCatalog表中的主鍵CatalogId具有約束關(guān)系[7]。

2.2 信息分類編碼結(jié)構(gòu)

將DocCatalog表中的主鍵CatalogId定義為bigint數(shù)據(jù)類型[8]，大小為8個(gè)字節(jié)，存儲(chǔ)64位二進(jìn)制。如圖2所示，將64長(zhǎng)度從右到左分割成9段，每一段為7位，最左邊剩余的一位廢棄不用，可以獲得ABC至I個(gè)完整的二進(jìn)制段，規(guī)定當(dāng)7位編碼全為0時(shí)不表示任何分類編碼。A段位第一層分類編碼，每一層分類的編碼最小值是從0000001開始表示的。全零的段值不表示分類編碼。當(dāng)創(chuàng)建第一層的第一個(gè)分類時(shí)，就用二進(jìn)制0000001表示，如果該層級(jí)需要?jiǎng)?chuàng)建第二個(gè)分類，分類編碼就為0000010，本層級(jí)的最后一個(gè)分類用編碼1111111表示。

圖2 信息分類編碼

設(shè)計(jì)的分類編碼結(jié)構(gòu)，對(duì)于每一個(gè)層級(jí)，可以有27=128個(gè)編碼，除去全為0的編碼，每層級(jí)可以表示127個(gè)分類。對(duì)于64位編碼，一共有1279個(gè)分類。這對(duì)于企業(yè)信息分類已經(jīng)足夠使用[9]。

當(dāng)A段分類下無(wú)子分類的時(shí)候，那么其他段位值全為0。當(dāng)A段一層分類有子分類時(shí)，則第二層的子分類編碼從0000001開始。從A至I段的編碼總是從0000001開始到1111111結(jié)束。如圖3所示，這是一個(gè)多層分類實(shí)例。

假如給定一個(gè)分類，其十進(jìn)制的編碼值為4210818，將其轉(zhuǎn)換成二進(jìn)制編碼：1000000100000010000010，按從右到左7位為一段，不足7位補(bǔ)0，依次為：0000010 0000001 0000001 0000001，一共分割成了4段，該分類為第四層子分類?？梢缘玫狡渖细腹?jié)點(diǎn)的編碼為0000001 0000001 0000001，十進(jìn)制編碼值為16 513；第二層級(jí)的編碼為0000001 0000001，十進(jìn)制編碼值是129；第一層級(jí)的分類編碼為0000001，十進(jìn)制編碼值是1。對(duì)于分類的分類層級(jí)和其所有的分類路徑，只需要給定該分類的編碼值，就能完整地分析出來(lái)[10]。

圖3 分類編碼二進(jìn)制位

3 算法實(shí)現(xiàn)

基于此分類編碼，設(shè)計(jì)了一套使用簡(jiǎn)單、效率高效的算法。該算法基于微軟LINQ技術(shù)進(jìn)行實(shí)現(xiàn)[11]。在信息分類的程序集中定義一個(gè)CatalogTreeBase信息分類基礎(chǔ)類，另外還定義了幾個(gè)關(guān)鍵基礎(chǔ)信息。

(1)MaxLevels，這是信息分類的總級(jí)數(shù)，由前面分類級(jí)數(shù)可知，其值為9，是一個(gè)常量。

(2)LevelLengh，這是分類編碼的二進(jìn)制長(zhǎng)度，也是一個(gè)常量，其值為7。

(3)分類K碼，這是算法中的關(guān)鍵信息，其值的定義為2LevelLengh。這是一個(gè)永恒不變的常量，由于上述LevelLength值為7，所以K值為128。

(4)LevelGrade分類編碼層，在計(jì)算機(jī)中，移位操作是非常便捷高效的。通過對(duì)編碼值的右移操作，將編碼值進(jìn)行分割，那么LevelGrade值就是其分割后的段數(shù)。

(5)父類截取碼，在程序中用LevelK表示。這是一個(gè)變量，用于將分類編碼與父類截取碼進(jìn)行運(yùn)算后取得上一級(jí)的父類編碼，算法定義為KLevelGrade。按照定義，對(duì)于第一層的LeveK值即為K碼，第二層為K2，依次類推，可以看出當(dāng)父節(jié)點(diǎn)相同時(shí)，其他兄弟分類具有相同的Level值。

在實(shí)際應(yīng)用中，如果給出一個(gè)分類編碼的Id[12]，對(duì)于其父類的編碼值只需要用分類Id的編碼對(duì)上層的LevelK進(jìn)行取模運(yùn)算：FatherId=Id%GetFather-LevelK(Id)。當(dāng)輸入分類編碼值Id，即可求出上一級(jí)的LevelK值。在項(xiàng)目的實(shí)際應(yīng)用中，為了能夠便于隨時(shí)進(jìn)行調(diào)用，定義：public static ulong GetFatherId(ulong Id)。這是一個(gè)計(jì)算父節(jié)點(diǎn)編碼的函數(shù)。而對(duì)于海量信息分類的解決方案，傳統(tǒng)方法是通過對(duì)數(shù)據(jù)庫(kù)進(jìn)行迭代查詢操作，改進(jìn)的分類算法只需要進(jìn)行取模運(yùn)算，即能快速地得到分類的父分類編碼[13]。

對(duì)于獲取某一分類下的直接下一級(jí)子分類，或者根據(jù)指定的分類編碼獲取下級(jí)的所有分類，在信息方案中，普通方法是采用迭代循環(huán)的方式，調(diào)用查找子類的方法，來(lái)找到所有的子分類。對(duì)于優(yōu)化的分類編碼，所有子分類編碼中就包括了父節(jié)點(diǎn)的編碼。在運(yùn)算的時(shí)候，如果子分類的編碼中能夠解析出父類編碼，那么該子類就能夠被視為找到。LINQ的子類查詢語(yǔ)句如下：

Public IQueryable GetSubCatalog(long id)

{

longlevelK=GetLevelK(id);

var query=from u dbContext.Catalog where u.CatalogId % levelK==id select u;

return query.AsQueryable();

}

在上述語(yǔ)句中，對(duì)于父分類編碼的獲得，在查詢時(shí)只需要分類編碼對(duì)父分類levelK進(jìn)行取模操作，u.catalogId%levelK==id。在圖3中，對(duì)于3層級(jí)分類1.2.1，其分類編碼值為16 641，父類的levelK為K2=16 384，對(duì)其取模得到16 641%16 384=257，而二層級(jí)分類1.2的編碼值就是257，可以判定為該分類是分類1.2的子分類，同理可判定1.2.2也是分類1.2的子分類。如果需要查找一個(gè)指定分類的下層級(jí)子分類，使用LINQ查詢時(shí)，增加一個(gè)判定條件，下層級(jí)的比父分類層級(jí)大1，其代碼如下[14]：

Public IQueryable GetChildrenCata

{

int levelGrade=GetLevelGrade(id)+long levelK=GetLeveelK(id);

var query=from u dbContext.Catalog where u.CatalogId % levelK select u;

return query.AsQueryable();

}

由于LINQ語(yǔ)句不能直接去調(diào)用外部函數(shù)GetLevelGrade()，這里使用的是偽代碼，用來(lái)判定父分類比子分類的層級(jí)高1級(jí)。

在實(shí)際項(xiàng)目中，經(jīng)常需要恢復(fù)出目錄樹。采用遞歸的方式，調(diào)用前面定義的GetChildrenCatalog()函數(shù)，就能較為簡(jiǎn)便輕松地實(shí)現(xiàn)完整的信息分類樹。

4 算法測(cè)試

為了測(cè)試改進(jìn)的海量信息分類查詢方法和普通迭代信息分類方法的效率差異，將在不同測(cè)試條件下進(jìn)行算法的性能測(cè)試，其測(cè)試環(huán)境相同。測(cè)試主要采用的實(shí)例為生成分類樹。

測(cè)試一：查找的分類指定，其Id為1，分類層級(jí)為3，每層級(jí)有8個(gè)子分類。

測(cè)試二：查找的分類指定，其Id為1，分類層級(jí)為4，每層級(jí)有8個(gè)子分類。

測(cè)試三：查找的分類指定，Id也為1，分類層級(jí)為4，每層級(jí)有20個(gè)子分類。

圖4和圖5為測(cè)試用時(shí)結(jié)果比對(duì)，可以得出以下幾點(diǎn)結(jié)論：

圖4 運(yùn)行耗時(shí)結(jié)果比對(duì)

測(cè)試條件測(cè)試條件一測(cè)試條件二測(cè)試條件三普通迭代算法用時(shí)(s)0.150.684.09優(yōu)化的分類算法(s)0.080.090.22

圖5 測(cè)試用時(shí)

(1)當(dāng)分類的層級(jí)較少且分類數(shù)目不多時(shí)，改進(jìn)的海量信息分類算法和普通的迭代算法在耗時(shí)時(shí)間上差異較小，但改進(jìn)的分類算法性能上較優(yōu)。

(2)在分類層級(jí)增加，而且分類總數(shù)也增加的情況下，改進(jìn)的分類算法要比普通的迭代算法少一個(gè)數(shù)量級(jí)的時(shí)間。

(3)當(dāng)分類層級(jí)和分類的總數(shù)大量增加時(shí)，改進(jìn)的分類算法在耗時(shí)上差異較小，在增長(zhǎng)速率上更加優(yōu)于普通的迭代算法。

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

提出了一種查詢、檢索海量信息的分類算法，其特點(diǎn)如下：優(yōu)化編碼設(shè)計(jì)，編碼值包含了信息分類的層次結(jié)構(gòu)，能提供最大9層級(jí)約8.59×1018個(gè)分類，保證了信息分類結(jié)構(gòu)的完整。通過基于微軟的LINQ技術(shù)設(shè)計(jì)了一套簡(jiǎn)單、高效的算法，借助計(jì)算機(jī)的高速運(yùn)算能力，能快速解析出信息分類的結(jié)構(gòu)層次與分類編碼。優(yōu)化的算法為海量信息分類提供了參考，有利于提高信息數(shù)據(jù)檢索的效率。