劉旭

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

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

劉旭

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

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

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

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

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

圖1 Treemap的生成步驟[5]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 完整搜索的DSS算法

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

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

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

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

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

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

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

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

4 對完整搜索的DSS算法的改進

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

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

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

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

5 實驗和進一步分析

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

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

表1 DSS算法在不同參數(shù)下運行的實驗結果

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

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

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

圖9 運行時間隨S值和N值改變的折線圖

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

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

圖10 運行時間隨L值和N值改變的折線圖

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

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

6 結論

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

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)化研究.計算機輔助設計與圖形學學報,2013,25(11):1623–1634.

7張昕,袁曉如.樹圖可視化.計算機輔助設計與圖形學學報, 2012,24(9):1113–1124.

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

9谷建濤,周哲,曹建亮.基于正方化算法的樹圖生成方法研究.計算機應用與軟件,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周哲.雙向正方化樹圖生成算法[碩士學位論文].長沙:湖南大學,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ù)組實現(xiàn)分析與性能優(yōu)化.計算機與現(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;收到修改稿時間:2016-09-27

10.15888/j.cnki.csa.005734