基于深度優(yōu)先搜索的正方化樹圖布局算法①

劉旭

(SAP中國研究院 商務(wù)智能部,上海 201203)

基于深度優(yōu)先搜索的正方化樹圖布局算法①

劉旭

(SAP中國研究院 商務(wù)智能部,上海 201203)

正方化布局算法在樹圖可視化形式中得到廣泛使用,然而經(jīng)典正方化樹圖布局算法無法獲得平均長寬比最優(yōu)的結(jié)果.通過分析經(jīng)典正方化樹圖布局算法的實(shí)現(xiàn)細(xì)節(jié),特別是每一步矩形塊位置的選擇過程,論證了經(jīng)典正方化算法由于使用貪心算法原理導(dǎo)致的缺陷,結(jié)合深度優(yōu)先搜索技術(shù),提出了基于深度優(yōu)先搜索的正方化樹圖布局算法(DSS算法).在詳細(xì)闡述DSS算法實(shí)現(xiàn)過程的基礎(chǔ)上,結(jié)合實(shí)證研究,對(duì)DSS算法在平均長寬比方面的優(yōu)勢(shì),時(shí)間性能的改進(jìn)方向和本質(zhì)特點(diǎn)進(jìn)行了深入探討.

可視化;樹圖;正方化;深度優(yōu)先;搜索

層次數(shù)據(jù)的常見可視化形式是樹形圖,然而樹形圖的連接線段之間存在大量空白無法利用,當(dāng)數(shù)據(jù)量增加時(shí),子結(jié)點(diǎn)會(huì)逐漸密集排列在一起,從而難以區(qū)分.Treemap(樹圖)使用具有一定面積的塊來表示數(shù)據(jù)結(jié)點(diǎn),而利用結(jié)點(diǎn)之間的位置關(guān)系來表示數(shù)據(jù)之間的層次關(guān)系[1].相對(duì)于樹形圖,Treemap的優(yōu)點(diǎn)是充分利用了空間[2],可以通過結(jié)點(diǎn)的大小,顏色表示數(shù)據(jù)的各種屬性[3],同時(shí),Treemap的結(jié)點(diǎn)位置還可以表示數(shù)據(jù)的分布關(guān)系[4].

Treemap的基本形式是用一個(gè)矩形區(qū)域表示根結(jié)點(diǎn),將根結(jié)點(diǎn)劃分為多個(gè)矩形區(qū)域以表示子結(jié)點(diǎn),這樣遞歸地表示整個(gè)層次結(jié)構(gòu)數(shù)據(jù)[5].圖1描述了一個(gè)Treemap的生成步驟[6].基本布局算法是Treemap繪制過程中必須首先解決的問題.由于Treemap是一個(gè)遞歸結(jié)構(gòu),要實(shí)現(xiàn)一個(gè)Treemap的布局算法,最關(guān)鍵的問題就是實(shí)現(xiàn)單層Treemap子結(jié)點(diǎn)的布局,也即在給定結(jié)點(diǎn)權(quán)重和結(jié)點(diǎn)序列的情況下,確定在二維的平面上排布矩形的方案[7].不同的排布方案會(huì)產(chǎn)生不同的可視化效果.

圖1 Treemap的生成步驟[5]

在Treemap的主要布局算法中,以生成平均長寬比較小的矩形為目標(biāo)的經(jīng)典正方化(Squarified)算法有廣泛的應(yīng)用[8],但是此算法所使用的貪心算法原理令其在很多情況下無法獲得最優(yōu)解,有些時(shí)候獲得的結(jié)果與最優(yōu)解差距較大.如果在經(jīng)典正方化算法的基礎(chǔ)上加入搜索技術(shù),可以給出一種改進(jìn)的算法獲得更優(yōu)結(jié)果.

1 經(jīng)典正方化算法的實(shí)現(xiàn)細(xì)節(jié)

如果Treemap布局中劃分出大量細(xì)長的小矩形,則難以進(jìn)行辨認(rèn)和鼠標(biāo)點(diǎn)擊.為了解決這個(gè)問題,需要有一種布局算法降低生成矩形的平均長寬比,經(jīng)典正方化算法就是為了這一目的而提出的.如果要獲得平均長寬比最低的結(jié)果,此問題是一個(gè)NP難問題,但是在實(shí)際情況中,只需要得到一個(gè)平均長寬比相對(duì)較低的結(jié)果[9].

經(jīng)典正方化算法是貪心算法的應(yīng)用,其思路是首先將子結(jié)點(diǎn)按從大到小排序,然后從第一個(gè)結(jié)點(diǎn)開始,按照從短邊開始的策略填充.從第二個(gè)矩形開始,當(dāng)填充第i個(gè)矩形時(shí),在當(dāng)前的Row(即當(dāng)前行列)中插入或者新建Row這兩種策略中選擇,而選擇的依據(jù)是第1至第i-1個(gè)已經(jīng)填充矩形的最高長寬比或平均長寬比,最高長寬比或平均長寬比較低的填充策略則為第i個(gè)結(jié)點(diǎn)的填充方式[10].如果用偽代碼描述,經(jīng)典正方化算法為:

圖2是經(jīng)典正方化算法的一個(gè)示例[8],使用的排序后的序列為6,6,4,3,2,2,1.可以看出此算法可以得到平均長寬比較低的布局.

圖2 經(jīng)典正方化算法示例[8]

對(duì)于經(jīng)典正方化算法,首先要進(jìn)行排序,使用歸并排序的最壞時(shí)間花銷為O(nlogn),然后,要進(jìn)行n個(gè)步驟,每一步需要計(jì)算當(dāng)前的行或列的平均長寬比.在最壞情況下,所有的矩形都放置于初始的行或列中,則算法在選擇策略上的時(shí)間花銷為0+1+2+…+(n -1)=n(n-1)/2,故在最壞情況下,經(jīng)典正方化算法的時(shí)間性能為O(n2),可以看出此時(shí)間性能是可以接受的[11].

2 對(duì)經(jīng)典正方化算法缺陷的分析

在對(duì)經(jīng)典正方化算法進(jìn)行大量的測試之后,易知該算法在大多數(shù)情況下獲得的結(jié)果令人滿意,但是在有些情況下獲得的結(jié)果明顯較差.圖3顯示的是一個(gè)無法獲得最優(yōu)解的典型情況,給定的矩形是一個(gè)長寬各為100的正方形,需要放入的三個(gè)矩形塊序列為[4800,4800,400].圖3(a)顯示的是一個(gè)較優(yōu)解,此布局下的各矩形平均長寬比為3.5395,然而使用經(jīng)典正方化算法只能獲得圖3(d)所示的結(jié)果,此布局下的各矩形平均長寬比為9.6133,從圖中可以明顯看出最后一個(gè)矩形長寬比很大,視覺效果不佳.

圖3 經(jīng)典正方化算法對(duì)于[4800,4800,400]不能獲得最優(yōu)解的情況

出現(xiàn)這種情況的直接原因在于,經(jīng)典正方化算法在對(duì)第二個(gè)矩形塊布局時(shí)選擇了插入已有的Row,而不是新建Row.如圖3(b)所示,在放入第二個(gè)矩形塊時(shí),當(dāng)前的Row中有第一個(gè)矩形,容易算出,此時(shí)插入當(dāng)前Row的兩個(gè)矩形平均長寬比為1.92,而新建Row之后兩個(gè)矩形的平均長寬比為2.0833,故按照貪心算法的原理應(yīng)該選擇如圖3(c)所示的那樣插入當(dāng)前Row,但是,在對(duì)第三塊矩形布局時(shí),不管是插入現(xiàn)有的Row還是新建Row,都會(huì)成為一個(gè)狹長的矩形,導(dǎo)致最終所有矩形塊的平均長寬比反而不如在第二塊矩形新建Row,并在第三塊插入第二塊新建的Row所獲得的圖3(a)所示的效果.

通過進(jìn)一步分析布局過程,可知按照經(jīng)典正方化算法對(duì)序列元素逐個(gè)布局的方式,為了取得較小的平均長寬比,對(duì)每一個(gè)新加入的矩形塊實(shí)際上有三種可能的布局方式:(1)插入當(dāng)前的Row(插入的方向由當(dāng)前Row的方向確定);(2)在空白區(qū)域靠短邊新建Row; (3)在空白區(qū)域靠長邊新建Row[12].由于經(jīng)典正方化算法只保證已經(jīng)加入的矩形塊具有最小的平均長寬比,不考慮未加入的矩形塊,這意味著經(jīng)典正方化算法會(huì)錯(cuò)過那些對(duì)于已經(jīng)加入的矩形塊不利,但是對(duì)未來新加入的矩形塊有利的布局.例如在圖3所示的情況下,第二個(gè)矩形塊應(yīng)該是新建Row比插入當(dāng)前Row更加有利.特別地,經(jīng)典正方化算法不會(huì)在空白區(qū)域靠長邊新建Row,因?yàn)閷?duì)于當(dāng)前Row中的矩形塊而言肯定是靠短邊較優(yōu),但是在有些情況下靠長邊新建Row反而對(duì)未來的矩形塊有利.

圖4顯示了一種靠長邊新建Row更好的典型情況,矩形空間長為400,寬為300,需要放入的矩形塊序列為[400,400,100,100,100,100],圖4(a)顯示的是最佳布局方案,此時(shí)所有的矩形塊都是正方形,平均長寬比為1,但是使用經(jīng)典正方化算法只能得到圖4(b)所示的結(jié)果,易知此時(shí)所有矩形塊的平均長寬比為1.7778.圖5詳細(xì)分析了導(dǎo)致這種結(jié)果的原因.為了得到最佳布局方案,第一塊矩形新建Row時(shí)應(yīng)該選擇靠長邊,這樣第二塊矩形加入Row之后即可獲得兩個(gè)正方形的矩形塊.但是經(jīng)典正方化算法的特點(diǎn)是在加入第一個(gè)矩形塊時(shí)不考慮第二塊,故對(duì)第一塊矩形新建Row時(shí)選擇的是靠短邊,這樣開始的兩個(gè)矩形塊就錯(cuò)過了選擇最佳方案的機(jī)會(huì),之后的矩形塊無論是插入Row還是新建Row,第一塊矩形的長寬比都不可能達(dá)到1.

圖4 經(jīng)典正方化算法對(duì)于[400,400,100,100,100, 100]不能獲得最優(yōu)解的情況

圖5 靠長邊新建Row獲得更優(yōu)布局的步驟分析

3 完整搜索的DSS算法

從以上的分析可以看出,為了獲得更優(yōu)結(jié)果,在每一步選擇布局方案時(shí)不僅需要考慮當(dāng)前矩形塊的平均長寬比,還要探測后繼矩形塊的布局情況,探測的矩形塊越多,越可能選擇出更優(yōu)結(jié)果.理想情況下,檢查了所有矩形塊布局方案之后就可以獲得在逐步靠邊新建Row的這一算法框架下的最優(yōu)解.

為了探測所有可能的布局情況,算法中需要引入搜索技術(shù),以當(dāng)前的布局方案為基點(diǎn)擴(kuò)展搜索樹．搜索樹的擴(kuò)展方式有多種,但最基本的是廣度優(yōu)先和深度優(yōu)先兩種方式．在搜索方式的問題解決過程中,一般在搜索樹的某些分支深度可能無限,或是搜索結(jié)果可能在淺層結(jié)點(diǎn)出現(xiàn)時(shí)會(huì)優(yōu)先考慮廣度優(yōu)先搜索.然而就當(dāng)前問題而言,搜索樹的深度是有限的,搜索層數(shù)一定要達(dá)到最深才能獲得搜索結(jié)果,這意味著深度優(yōu)先搜索具有和廣度優(yōu)先搜索一樣的完備性,而且使用廣度優(yōu)先搜索也不可能在較淺的搜索層次上提前獲得搜索結(jié)果.使用廣度優(yōu)先搜索的缺點(diǎn)在于需要維護(hù)一個(gè)先進(jìn)先出的隊(duì)列保存搜索樹狀態(tài),算法會(huì)有較高的空間復(fù)雜度[13].

如果使用深度優(yōu)先搜索,由于已經(jīng)搜索過結(jié)點(diǎn)的所有后代結(jié)點(diǎn)都可以不再保存,需要保存的搜索樹狀態(tài)大大減少.搜索樹的狀態(tài)需要記錄在棧中,如果使用JavaScript等高級(jí)語言,間接遞歸的程序設(shè)計(jì)方式即可很簡明的實(shí)現(xiàn)搜索棧,同時(shí),深度優(yōu)先搜索在這個(gè)問題上的另一個(gè)優(yōu)勢(shì)是如果有一條搜索路徑搜索到所有矩形塊均為正方形的方案,例如出現(xiàn)圖4(a)所示的情況,即可直接結(jié)束搜索,廣度優(yōu)先搜索在獲得這一結(jié)果之前必須探測所有的較淺層結(jié)點(diǎn),需要檢查的結(jié)點(diǎn)數(shù)量比深度優(yōu)先搜索多.如果在經(jīng)典正方化算法的基礎(chǔ)上加入深度優(yōu)先搜索技術(shù),可以得到基于深度優(yōu)先搜索的正方化算法(Depth-first Search Squarified算法,簡稱DSS算法),此算法可以有效地改進(jìn)最終布局結(jié)果.

如果使用JavaScript偽代碼,一個(gè)完整搜索所有布局方案的DSS算法可以用以下函數(shù)表示:

DSS算法的執(zhí)行需要調(diào)用 DSSquarify函數(shù), rectObjs是當(dāng)前用于布局的數(shù)組,itemIndex是指當(dāng)前用于布局的數(shù)組元素索引,在初始狀態(tài)下為 0, currentRowRect表示當(dāng)前的Row,初始狀態(tài)下長寬都是0,currentLiveRect表示當(dāng)前未被填充的矩形空間. evaluateAspectRatio函數(shù)用于計(jì)算當(dāng)前布局方案的所有矩形平均長寬比,計(jì)算之后獲得的newCtx_inRow, newCtx_newRowShort,newCtx_newRowLong包含有完整的布局方案.DSSquarify函數(shù)實(shí)際上就是比較三種方案的平均長寬比,用min函數(shù)選擇平均長寬比最低的值,然后返回最低值對(duì)應(yīng)的布局方案. evaluateAspectRatio函數(shù)為了計(jì)算出所有矩形塊的平均長寬比,需要完成整個(gè)布局過程. evaluateAspectRatio函數(shù)的偽代碼如下:

可以看出,evaluateAspectRatio函數(shù)的執(zhí)行過程實(shí)際 上 是 先 調(diào) 用 insertAndLayoutRow 或 者makeNewRowAndLayout函數(shù)按照不同的方案擺放當(dāng)前的矩形塊,然后遞歸地調(diào)用縮小了問題規(guī)模的DSSquarify函數(shù)完成剩下矩形塊的擺放,最后進(jìn)行對(duì)于當(dāng)前方案的估值.其中的insertAndLayoutRow是當(dāng)前矩形塊插入當(dāng)前 Row 的布局過程,而makeNewRowAndLayout是當(dāng)前矩形塊新建Row的布局過程,參數(shù)isLongFirst指定了Row是靠長邊還是靠短邊.在調(diào)用DSSquarify完成了剩下的矩形塊布局之后,evaluateAspectRatio函數(shù)調(diào)用evaluateAllRects完成對(duì)于當(dāng)前布局方案的估值,估值的過程就是計(jì)算所有矩形塊的平均長寬比.

圖 6 完全搜索的DSS算法執(zhí)行示意圖

圖6 用樹形圖直觀顯示了完全搜索的DSS算法的一個(gè)執(zhí)行過程,其中矩形空間長為150,寬為100,需要放入的矩形塊序列為 [48,48,4].可以看出,DSS算法一共進(jìn)行了三層搜索,搜索的過程就是以深度優(yōu)先的方式遍歷整個(gè)樹形結(jié)構(gòu),并在葉子結(jié)點(diǎn)進(jìn)行估值計(jì)算,而每一個(gè)父結(jié)點(diǎn)的估值都是由最小的葉子結(jié)點(diǎn)估值決定的.一般而言,在每一層搜索都有三種可選的方案,只有第一層和最末層是例外(以葉子結(jié)點(diǎn)為搜索的最末層),由于在最末層只剩下一個(gè)矩形塊,只有插入Row和填充全部空白新建Row這兩種擺放方式,而在第一層,由于Row還沒有建立,不存在插入Row的擺放方式,僅能以兩種不同方式新建Row.從圖中可以看出,紅線加粗的兩種方案的最終估值均為3.4315,為各種方案中最小值,而這兩種方案的第一步都是靠長邊新建Row,這是使用經(jīng)典正方化算法無法獲得的結(jié)果.

4 對(duì)完整搜索的DSS算法的改進(jìn)

完整搜索的DSS算法似乎已經(jīng)在通過新建Row來逐步完成布局的框架下給出了一個(gè)最優(yōu)的解決方案,然而,完整搜索的DSS算法是缺乏實(shí)用價(jià)值的,其最大的問題在于時(shí)間性能.根據(jù)上文的分析,在一般情況下,每一層搜索都有三種可能的布局方式,即使假定每一層的布局時(shí)間開銷為常數(shù),完成n個(gè)矩形塊的布局搜索需要的時(shí)間也高達(dá)O(3n),這是指數(shù)時(shí)間的算法,實(shí)際上每一層布局的時(shí)間還與n有關(guān),在運(yùn)行中,時(shí)間開銷會(huì)隨著n的增大迅速增加,因此該算法一般不能用于實(shí)際應(yīng)用程序.JavaScript語言兼具面向?qū)ο蠛秃瘮?shù)式編程風(fēng)格,已經(jīng)在可視化軟件開發(fā)中得到廣泛應(yīng)用[14].如果應(yīng)用程序使用JavaScript編制并運(yùn)行于Chrome中,當(dāng)n=20時(shí),完整搜索的DSS算法在一臺(tái)CPU為Intel Core 2 Duo 2.20GHz的個(gè)人電腦上的運(yùn)行時(shí)間已經(jīng)超過6秒,這樣的性能是令人無法接受的.

圖7 經(jīng)典正方化算法和完整搜索的DSS算法布局比較

由于時(shí)間的開銷是由于搜索層數(shù)的增加,為了改進(jìn)完整搜索的DSS算法,一個(gè)最直觀的策略就是減少搜索層數(shù),即指定一個(gè)搜索層數(shù)S,每次搜索時(shí)僅搜索當(dāng)前位置開始的S層,在還沒有對(duì)所有矩形塊完成布局的情況下,使用已經(jīng)完成布局的S層矩形塊進(jìn)行估值.如果以N表示矩形塊個(gè)數(shù),可見完整搜索的DSS算法中S=N,而經(jīng)典正方化算法即為S=1的DSS算法.減少搜索層數(shù)實(shí)際上是一種質(zhì)量和效率的折衷,其優(yōu)點(diǎn)是可以顯著加快算法運(yùn)行速度,但也使得估值結(jié)果不夠準(zhǔn)確,從而可能無法獲得完整搜索的DSS算法可以獲得的最優(yōu)方案.另一個(gè)提高時(shí)間性能的策略是在開始進(jìn)行較少層次的搜索,僅在最后L層進(jìn)行完全搜索.圖7顯示的是在矩形空間長為100,寬為30的情況下,分別使用經(jīng)典正方化算法和完整搜索的DSS算法對(duì)序列[3366,1857, 5437,2668,3867,1920,2695,9192,2605,583]進(jìn)行布局獲得的結(jié)果,其中的2.039785和1.447654是兩種布局方案的平局長寬比.可以看出,完整搜索的DSS算法獲得的結(jié)果較優(yōu),但是兩種算法對(duì)于開始的6個(gè)矩形塊的布局方案是完全一樣的,區(qū)別僅在于最后4個(gè)矩形塊布局的不同,尤其是最后一個(gè)矩形塊.這一現(xiàn)象的出現(xiàn)不是偶然的,而是經(jīng)典正方化算法的貪心原則導(dǎo)致的.在布局的開始階段,由于剩下的矩形塊個(gè)數(shù)較多,長寬比例較大的矩形塊還可能在后續(xù)的布局中得到調(diào)整,但是對(duì)于后續(xù)的矩形塊,調(diào)整的機(jī)會(huì)越來越少,從而最后的幾個(gè)矩形塊布局方案往往較差,影響了所有矩形塊的平均長寬比.通過對(duì)經(jīng)典正方化算法生成的大量布局方案進(jìn)行統(tǒng)計(jì),可知在超過85%的情況下,長寬比最高的那個(gè)矩形塊出現(xiàn)在最后10%的矩形塊中.

既然經(jīng)典正方化算法的弱點(diǎn)主要集中在最后的幾個(gè)矩形塊,僅在最后L層進(jìn)行完全搜索即可在時(shí)間代價(jià)較小的情況下獲得較優(yōu)的布局,例如,僅需搜索最后兩層即可避免圖3示意的對(duì)于[4800,4800,400]不能獲得最優(yōu)解的情況.在引入S作為搜索層數(shù)和L作為最終完全搜索層數(shù)這兩個(gè)參數(shù)之后,可以獲得一般形式的,更加具有實(shí)用價(jià)值的DSS算法,可根據(jù)實(shí)際的硬件水平和應(yīng)用場景選擇合適的S和L.一般情況下,在DSS算法的運(yùn)行中取S=1,L=6即可獲得時(shí)間性能較好,同時(shí)明顯優(yōu)于經(jīng)典正方化算法的結(jié)果.在這里也不難看出,完全搜索的DSS算法和經(jīng)典正方化算法實(shí)際上都是DSS算法的兩個(gè)特例,在完全搜索的DSS算法中S=N,L=N,而在經(jīng)典正方化算法中S=1,L=1.

5 實(shí)驗(yàn)和進(jìn)一步分析

在具有實(shí)際意義的信息可視化過程中,過大的N值往往會(huì)導(dǎo)致多數(shù)顯示的矩形塊面積過小而難以看清,故一般會(huì)采用適當(dāng)?shù)臄?shù)據(jù)聚合方式以使N的值不會(huì)很大,N在100之內(nèi)的情況比較常見.普通用戶對(duì)于圖形渲染可接受的等待時(shí)間一般在3秒之內(nèi),考慮到硬件的發(fā)展,在實(shí)驗(yàn)中認(rèn)為6秒是DSS算法最大可接受運(yùn)行時(shí)間.

表1列出了DSS算法在不同的S值和L值下運(yùn)行的實(shí)驗(yàn)結(jié)果,實(shí)驗(yàn)的硬件條件是一臺(tái)CPU為Intel Core i7 2.93 GHz,內(nèi)存16GB的個(gè)人電腦,軟件環(huán)境是Windows 7企業(yè)版,DSS算法使用JavaScript實(shí)現(xiàn),運(yùn)行于Chrome瀏覽器.表格中的實(shí)驗(yàn)結(jié)果都是取隨機(jī)數(shù)運(yùn)行100次之后的平均值,其中N代表矩形塊的個(gè)數(shù),時(shí)間的單位是毫秒,S=1,L=1即為經(jīng)典正方化算法,S=N,L=N為完整搜索的DSS算法,標(biāo)記為N/A的單元格表示因?yàn)樾枰倪\(yùn)行時(shí)間超過6秒(6000毫秒)而不予統(tǒng)計(jì)結(jié)果.

表1 DSS算法在不同參數(shù)下運(yùn)行的實(shí)驗(yàn)結(jié)果

通過實(shí)驗(yàn)數(shù)據(jù)不難看出,S值和L值越大,平均長寬比越低,但是需要的時(shí)間也越長.為了進(jìn)一步分析表格中的數(shù)據(jù),可以使用可視化的方式對(duì)平均長寬比和時(shí)間的變化分別生成折線圖.圖8顯示了平均長寬比變化的折線圖,從圖形可知平均長寬比隨著N的增加而降低,而S和L對(duì)于平均長寬比的影響在N較小時(shí)更加顯著.這說明在使用DSS算法時(shí),可以在問題規(guī)模較小(N較小)時(shí)使用較大的S和L值以獲得更優(yōu)結(jié)果,由于問題規(guī)模小,付出的時(shí)間代價(jià)有限,而在問題規(guī)模較大時(shí),由于平均長寬比會(huì)降低,可以適當(dāng)減小S和L值以獲得更優(yōu)的時(shí)間性能.

圖8 平均長寬比變化折線圖

圖9 顯示的是運(yùn)行時(shí)間隨S值和N值變化的折線圖.從圖中可以看出時(shí)間的消耗對(duì)S值的變化高度敏感,S較大時(shí),運(yùn)行時(shí)間隨N值增長很快,近似于指數(shù)曲線,這是由搜索算法的特點(diǎn)決定的.在L=1,N=40的情況下,S=3時(shí)算法需要的執(zhí)行時(shí)間是S=2時(shí)的將近200倍,接近4秒.在實(shí)際的應(yīng)用中,一般不宜取較大的S值.

圖9 運(yùn)行時(shí)間隨S值和N值改變的折線圖

圖10顯示的是運(yùn)行時(shí)間隨L值和N值變化的折線圖.不難看出,當(dāng)L值變大時(shí),運(yùn)行時(shí)間隨N的增長率也變大,但是增長的趨勢(shì)比較平緩,近似于線性.在實(shí)際的應(yīng)用中,可以考慮取L=6或L=7.

為了提升DSS算法的時(shí)間性能,除了選擇適當(dāng)?shù)腟和L值之外,還可以考慮更多策略,例如在搜索過程中引入啟發(fā)式規(guī)則,以及使用空間換時(shí)間的策略緩存和重復(fù)利用中間估值結(jié)果.啟發(fā)式規(guī)則在許多深度優(yōu)先搜索算法中常用,一般是一些經(jīng)驗(yàn)規(guī)則,例如在搜索到一個(gè)父結(jié)點(diǎn)時(shí),在已經(jīng)完成布局的矩形塊中如果出現(xiàn)長寬比大于10的情況,則停止搜索該結(jié)點(diǎn)的所有子結(jié)點(diǎn),并為該結(jié)點(diǎn)估值為無窮大.啟發(fā)式規(guī)則可以有效降低搜索時(shí)間的消耗,但也有可能錯(cuò)過一些開始布局較差但后續(xù)布局較好的方案.在對(duì)布局方案的搜素過程中,有可能出現(xiàn)重復(fù)的布局情況,例如在圖6中的第三層即出現(xiàn)了好幾對(duì)重復(fù)布局.如果之前的布局估值已經(jīng)被緩存,則在出現(xiàn)重復(fù)布局時(shí),如果重復(fù)的布局不是最末層結(jié)點(diǎn),就可以避免對(duì)子結(jié)點(diǎn)的重復(fù)搜索,僅需返回已緩存的估值即可.重復(fù)利用中間估值結(jié)果的方案關(guān)鍵需要是實(shí)現(xiàn)快速的布局比較和合適的緩存結(jié)構(gòu)[15].

圖10 運(yùn)行時(shí)間隨L值和N值改變的折線圖

圖11 使用完整搜索DSS算法不能獲得數(shù)學(xué)上最優(yōu)解的情況

此外,必須提到的一點(diǎn)是,在矩形空間中對(duì)若干矩形塊布局是一個(gè)NP難問題,要獲得數(shù)學(xué)意義上的最優(yōu)解非常困難.DSS算法的實(shí)現(xiàn)仍然沿用了經(jīng)典正方化算法的基本思路,即逐塊矩形不斷靠邊新建Row或插入已有的Row,將空白區(qū)域保留在靠矩形空間角落的地方,這一思路是無法涵蓋所有可能的布局的.即使是完整搜索的DSS算法,在某些情況下獲得的依然不是數(shù)學(xué)意義上的最優(yōu)解.例如圖11顯示的情況,矩形空間長寬均為9,矩形塊序列為[20,20,20,20,1],圖11(a)顯示的是完整搜索的DSS算法獲得的布局,平均長寬比為3.0386,但是圖11(b)是一個(gè)顯然的更佳布局,平均長寬比僅為1.2,然而,圖11(b)的這一布局是不可能通過DSS算法搜索到的,因?yàn)樽詈蟮男【匦螇K不被保留在矩形空間的任何一個(gè)角落上.

6 結(jié)論

DSS算法是在對(duì)于Treemap的經(jīng)典正方化布局算法進(jìn)行深入分析的基礎(chǔ)上提出的,從本質(zhì)上來說,它是對(duì)經(jīng)典正方化布局算法的一種擴(kuò)展,以更多的時(shí)間和空間換更優(yōu)解,即通過對(duì)于搜索狀態(tài)樹上更多結(jié)點(diǎn)的探測獲得更佳的布局結(jié)果.DSS算法中的參數(shù),本質(zhì)上是算法性能和更優(yōu)結(jié)果之間的一種折衷,而經(jīng)典正方化布局算法實(shí)際上就是DSS算法的一個(gè)時(shí)間與空間代價(jià)最小,然而布局效果最差的特例.在實(shí)際應(yīng)用中,需要結(jié)合實(shí)際情況使用最適合當(dāng)前應(yīng)用場景的參數(shù)設(shè)置,也可考慮使用啟發(fā)式規(guī)則和緩存技術(shù)進(jìn)一步改進(jìn)DSS算法.從工程的角度來說,DSS算法已經(jīng)明顯改善了經(jīng)典正方化算法的布局結(jié)果,但是如果要獲得數(shù)學(xué)意義上的最優(yōu)結(jié)果,仍然需要更多探索.

1 Bederson BB,Shneiderman B,Wattenberg M.Ordered and quantum treemaps:Making effective use of 2D space to display hierarchies.ACM Trans.on Graphics(TOG),2002, 21(4):833–854.

2 Chintalapani G,Plaisant C,Shneiderman B.Extending the utility of treemaps with flexible hierarchy.Proc.Eighth International Conference on Information Visualisation, 2004(IV 2004).IEEE.2004.335–344.

3 Vliegen R,Van Wijk JJ.Visualizing business data with generalized treemaps.IEEE Trans.on Visualization and Computer Graphics,2006,12(5):789–796.

4 Balzer M,Deussen O,Lewerentz C.Voronoi treemaps for the visualization of software metrics.Proc.of the 2005 ACM Symposium on SoftwareVisualization.ACMF.2005.165–172.

5 Tu Y,Shen HW.Visualizing changes of hierarchical data using treemaps.IEEE Trans.on Visualization and Computer Graphics,2007,13(6):1286–1293.

6陳誼,胡海云,李志龍.樹圖布局算法的比較與優(yōu)化研究.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2013,25(11):1623–1634.

7張昕,袁曉如.樹圖可視化.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2012,24(9):1113–1124.

8 Bruls M,Huizing K,Van Wijk JJ.Squarified treemaps. Springer.2000.

9谷建濤,周哲,曹建亮.基于正方化算法的樹圖生成方法研究.計(jì)算機(jī)應(yīng)用與軟件,2008,25(7):74–76.

10 Shneiderman B,Wattenberg M.Ordered treemap layouts. IEEE Symposium on Proc.of the Information Visualization. IEEE Computer Society.2001.73.

11 Engdahl B.Ordered and unordered treemap algorithms and their applications on handheld devices[Master’s Thesis]. Department of Numerical Analysis and Computer Science, Stockholm Royal Institute of Technology,2005.

12周哲.雙向正方化樹圖生成算法[碩士學(xué)位論文].長沙:湖南大學(xué),2005.

13 Russell SJ,Norvig P,Canny JF,et al.Artificial intelligence: A modern approach.Prentice hall Upper Saddle River, 2003.

14劉旭.ChromeV8引擎中的JavaScript數(shù)組實(shí)現(xiàn)分析與性能優(yōu)化.計(jì)算機(jī)與現(xiàn)代化,2014,(10):66–70.

15 Tamassia R.Handbook of graph drawing and visualization. CRC press,2013.

Squarified Treemap Layout Algorithm Based on Depth-First Search

LIU Xu

(Department of Business,Intelligence of SAP Labs China,Shanghai 201203,China)

Squarified layout algorithm is widely used in the Treemap Visualization,but classic Squarified algorithm cannot achieve the best average aspect ratio.By analyzing implementation details of Squarified Treemap layout algorithm,especially each step of the rectangular block position selection process,the paper demonstrates the drawback of classic Squarified algorithm caused by using greedy algorithm.Combining with depth-first search technique,it also proposes Squarified Treemap layout algorithm based on depth-first search(DSS algorithm).Based on elaborating implementation process of DSS algorithm,combining empirical research,the advantage of the DSS algorithm in the aspect ratio,the improvement direction and the essential characteristics of the time performance are discussed.

visualization;treemap;squarified;depth-first;search

2016-08-02;收到修改稿時(shí)間:2016-09-27

10.15888/j.cnki.csa.005734