路 強， 唐 靚， 馬坤樂，梁 翀

（1. 合肥工業(yè)大學(xué)可視化與協(xié)同計算研究室，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽 合肥 230009）

面向跨語言詞云可視化的拓撲保持布局算法研究

路 強1,2， 唐 靚1,2， 馬坤樂2，梁 翀1,2

（1. 合肥工業(yè)大學(xué)可視化與協(xié)同計算研究室，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽 合肥 230009）

針對大范圍替換詞云中單詞后出現(xiàn)的詞云拓撲結(jié)構(gòu)不穩(wěn)定的現(xiàn)象，提出一種詞云可視化的拓撲保持布局算法。首先，該算法通過對替換后的詞云中單詞進行分散處理，使之前或重疊或遠離的單詞按原拓撲相應(yīng)分離；再利用Delaunay三角剖分算法對分離詞云網(wǎng)格化，形成控制網(wǎng)格；最后在控制網(wǎng)格的基礎(chǔ)上采用緊湊布局的方法將分散詞云緊湊為與替換前原詞云拓撲一致的詞云布局。針對替換的一種具體情況，即跨語言翻譯詞云的情況做詳細介紹。該算法在提高詞云布局穩(wěn)定性，保持原詞云拓撲結(jié)構(gòu)方面是一個新的突破。

圖拓撲保持；單詞替換；翻譯詞云；單詞分散；緊湊布局

詞云也稱為標(biāo)簽云，由Milgram[1]最先提出。其作為一種用于文本分析的可視化工具，顯示了需分析文本中的關(guān)鍵性單詞，用戶只需一掃而過便能掌握文本的主要內(nèi)容，提高了用戶分析文本的效率。出于其高效性考慮，越來越多的研究工作日益展開。目前的詞云工作已由當(dāng)初只想在可視化界面中單純顯示出重要性單詞[2]的初衷，發(fā)展到便于讀者高效分析文本內(nèi)容的前提下同時還能為讀者帶來美學(xué)享受。

目前的詞云研究可以分為兩大方面，分別側(cè)重于詞云的單詞分布和詞云語義一致性研究。我們的工作不同于前兩種，卻是在這二者的基礎(chǔ)上的進一步深化探索。本文將針對于詞云的研究概念，提出一種新的詞云布局方法，即在保持詞云本身的拓撲、顏色、布局不變的情況下，通過替換詞云中的元素即單詞，可能是替換某個，或者是替換全部，可能是將所有英文單詞全替換為翻譯后相應(yīng)的中文詞語、法文單詞等其他語言，亦或是將詞云中的各個單詞分別替換為另一篇文本的其他關(guān)鍵詞，從而形成一種與替換之前拓撲結(jié)構(gòu)完全一致的緊湊詞云分布。其中，本文將針對詞云中單詞跨語言翻譯為其他語種單詞的替換后的詞云拓撲保持算法做一介紹。隨著詞云這一可視化工具在視覺方面和新聞發(fā)布方面越來越普遍的應(yīng)用，這一工作的研究對于美學(xué)工作者及從事新聞領(lǐng)域的工作者有著極大的意義，相比于之前人為翻譯后的手工布局，我們的研究將會因其在詞云生成方面的一致性、高效性、緊湊性、美觀性、便利性，獲得越來越多的青睞。

1 詞云研究現(xiàn)狀

現(xiàn)階段的詞云工作可以分為著重于研究詞云布局從而為用戶帶來美學(xué)影響和以提高詞云可讀性為目的調(diào)整單詞自身特性或單詞間特性這兩方面。基于這兩方面的研究在詞云領(lǐng)域已經(jīng)較為成熟。

（1）詞云的布局方式對于用戶分析文本有著舉足輕重的作用，對于詞云的整體美學(xué)感觀影響更甚。最初的將單詞單一的按一定順序逐行排列的布局方式[3]已不能滿足用戶對于詞云可讀性的需求，文獻[4]提出了用詞云布局美國地圖的方法，每個州分別用各自州名來布局，很好的將詞云同地圖結(jié)合起來，為用戶更方便地了解美國提供了極大便利。同時，利用詞云排列而形成的簡單圖形的詞云布局算法[5]，及一種新型的詞云街道圖[6]都打破了我們關(guān)于詞云布局的原有觀念。但這些算法的研究往往是只偏向于整體布局本身的美觀性，忽略了詞云中單個單詞獨立美觀和各單詞間連貫易讀對于整體詞云效果的影響。

（2）詞云中的單個單詞本身特性，包括單詞的字體、顏色、大小等方面及詞云中各單詞間的關(guān)聯(lián)性我們稱為單詞間的語義連貫性[7]對用戶理解文本起到關(guān)鍵性作用。Shaw[8]為了將單詞的關(guān)聯(lián)性在可視化空間有所表示，提出將每個單詞看做單個的點，將相互關(guān)聯(lián)的單詞用點與點之間連線的形式顯式表達，從而得到一種語義相關(guān)的詞云分布。2010年，文獻[9]中提出了一種新型語義相關(guān)方式，這種方式將語義相關(guān)的單詞聚簇到一起，且用不同的顏色分類，這一方法使得針對詞云可讀性的研究向前邁進了一大步。

誠然，上述兩方面對于最終詞云達到的效果都有著舉足輕重的作用，能體現(xiàn)文本內(nèi)容的分布方式，可以提高詞云的美觀性，而相鄰單詞具有語義連貫性的分布方式，有助于提高整體詞云的可讀性。我們的工作不同于這兩方面，但卻是在這兩方面的進一步深化探索，針對已具備各單詞語義連貫的美觀詞云，在保持其原有拓撲不變的情況下，將詞云各單詞全部替換或直接翻譯為其他語言詞云，就目前來說，是一種全新形式。與此同時，該算法的實現(xiàn)將會給從事新聞行業(yè)和視覺設(shè)計行業(yè)的工作者帶來極大便利，相比于人為翻譯后的手工布局，該方法更加高效便利。

2 跨語言詞云可視化的拓撲保持布局算法

本算法相比于前人的工作，從保持詞云的拓撲結(jié)構(gòu)著手，介紹一種新的詞云布局概念深化詞云的布局形式，即在替換詞云中各單詞顯示形式的情況下，著重介紹詞云的跨語言替換，即翻譯詞云的這種情況下，通過對翻譯過程中各個單詞的調(diào)整，保證翻譯后相對應(yīng)各單詞分布緊湊，使拓撲結(jié)構(gòu)保持不變。

2.1 相關(guān)定義

與文本主體內(nèi)容越貼近的單詞在文本中出現(xiàn)的頻率越高，當(dāng)然，一些起連接作用和代詞作用的詞除外。以單詞出現(xiàn)的頻率為標(biāo)準(zhǔn)，定義了單詞的重要性值，出現(xiàn)頻率越高，該單詞對于整個詞云的重要性影響越大。將重要性值越大的單詞通過顯示不同的字體和顏色進行標(biāo)注，突顯在詞云中，已成為詞云工作者在布局詞云時參考的一種基本原則。依照此原則布局的詞云是有意義的，而用我們的算法對此詞云保持原拓撲替換或翻譯為其他語言的詞云也是有意義的。

圖1所示的詞云是由百度百科中對于Wordnet[10]的文本描述為文本來源生成的，也較好體現(xiàn)了以上述原則分布詞云對于詞云主要內(nèi)容表達的正確性，由圖1可以得知Wordnet是用來描述詞語的語義信息關(guān)系的大體概念。表1對文本中提取的前100個詞語出現(xiàn)的頻率劃分頻率區(qū)間，并對相應(yīng)詞語劃分的不同優(yōu)先級進行說明，其中高頻率單詞具有高優(yōu)先級。我們定義詞云中顯示面積較大的單詞具有較高優(yōu)先級，顯示同種大小的單詞具有相同優(yōu)先級，以此為依據(jù)對翻譯詞云中各單詞重要性進行判斷。為了對算法作用后的拓撲保持程度形象化說明，在此基礎(chǔ)上，我們定義單詞語義相關(guān)的概念，其具體表現(xiàn)為單詞間的相對位置和相對距離的關(guān)系，其中相鄰單詞必定語義相關(guān)。

圖1 描述Wordnet的詞云

表1 根據(jù)頻率區(qū)間定義單詞優(yōu)先級

2.2 基本框架

對于給定的輸入詞云即待翻譯詞云V，用跨語言詞云可視化的拓撲保持布局算法，將其翻譯為具有相同拓撲結(jié)構(gòu)的相應(yīng)語種詞云，具體實現(xiàn)主要分以下3個部分，首先我們需將其翻譯為指定語言，翻譯后的詞云與原詞云相比肯定存在差異，之前無重疊的單詞相互覆蓋，又或者是原本緊湊的詞云分布翻譯后存在大量空白，依照本文的算法第二步的工作是將詞云中的單詞依照其優(yōu)先級的相反順序移動單詞，保證單詞相互分散的同時各語義相關(guān)單詞間依舊保持相關(guān)關(guān)系。在對分散后的單詞進行 Delaunay三角剖分[11]形成控制網(wǎng)格后，最后緊湊布局網(wǎng)格化詞云得到最終詞云分布。該算法的核心部分以偽代碼形式描述如下：

1 start

2 translate(V) //翻譯所有單詞節(jié)點的標(biāo)簽

其中，N表示V中的單詞個數(shù)，ks為翻譯后詞云覆蓋部分面積占總面積的比例，d1, d2為本算法自定義的閾值，distance_n為單詞n為消除重疊所需移動距離，ln為單詞分散時單詞n需移動的位移，F(xiàn)n為單詞n所受合力，dn為在緊湊詞云這一步驟時單詞n需移動的向量。

2.3 詞云翻譯

將中文詞云中的單詞翻譯為相應(yīng)英文為例，翻譯后的英文單詞與之前相比普遍更為扁平，在確定了翻譯后英文單詞的字體和大小后，根據(jù)單詞所占像素確定字體所在矩形框的大小，將詞云中的單詞放置在與之大小匹配的矩形框中，通過調(diào)整矩形框的位置實現(xiàn)對相應(yīng)單詞實際位置的調(diào)整，進而通過調(diào)整各個矩形框之間的距離實現(xiàn)實際單詞間無重疊的初步放置。

2.4 單詞分散

不同語種的同一單詞有著不同的顯示結(jié)果。我們?nèi)匀灰灾形膯卧~翻譯為對應(yīng)的英文單詞為例說明。翻譯后的單詞在長度和高度上明顯存在差異，其長度一般較為拉長，高度在原有基礎(chǔ)上更為壓縮，這必然使得翻譯后的詞云存在大面積的單詞重疊，為了達到消除單詞重疊的目的，我們提出一種單詞分散算法，實現(xiàn)可能存在大面積空白的無重疊詞云放置。

圖2 翻譯后的單詞重疊

對于給定詞云V，根據(jù)單詞在詞云中的顯示大小確定各單詞的優(yōu)先級，我們規(guī)定從優(yōu)先級最低的單詞開始，同種優(yōu)先級的單詞按單詞序號進行，依次對詞云中各單詞進行遍歷。如圖2所示，以詞云中的兩個中文單詞a, b為例，單詞a的優(yōu)先級高于單詞b,原本相對緊湊的布局由于翻譯為相應(yīng)的英文單詞（圖2(b)所示）其原有長度被拉長，高度被壓縮，使得單詞間必定存在重疊。對于Word b，為了消除與Word a之間的單詞重疊，其需要在圖中所示的x方向移動距離Δx ，y方向移動距離Δy ，分別表示為dx和dy。為了保證詞云中各單詞的語義相關(guān)性得到保持，在此基礎(chǔ)上，我們采用循環(huán)迭代的方法將Word b每次按系數(shù)α, β移動，假定有n個單詞與Word b重疊，則Word b第j次需移動的位移lbJ定義如下：

其中α, β可由相應(yīng)兩種字體的長寬自行確定，對于中英文跨語言的詞云，經(jīng)過大量實驗得出α, β分別取值為1/16，1/8時可取得較好效果。當(dāng)位移lbJ在某次迭代后的值小于規(guī)定閾值e時，迭代終止，即lbJ＜e。由此得到翻譯后的英文單詞分散分布的詞云。

2.5 緊湊布局

通過上述算法得到的詞云存在大量空白（如圖3(a)所示），為了在保持詞云原有拓撲結(jié)構(gòu)的基礎(chǔ)上得到緊湊的詞云分布，我們將各單詞用其矩形框的中心點表示，對其三角剖分得到網(wǎng)格化的最初圖G（如圖3(b)所示）。假定Delaunay邊連接Word a和Word b，在此基礎(chǔ)上我們定義兩種力：引力和斥力，保證Word a，Word b在不重疊的情況下最大限度的靠近，緊湊布局（如圖3(c)所示）。引力的使用有助于消除單詞間的大量空白，使得詞云中的單詞分布緊密（如圖3(d)所示），對于Word a和Word b，如圖4所示，它們之間的引力定義如下：

圖3 緊湊布局過程示意圖

圖4 有引力作用情況示意圖

只有當(dāng)Word a和Word b重疊時，它們之間的斥力才會產(chǎn)生作用，以圖2(b)為例，此時的斥力可以被定義為：

其中，kr是一個給定的值，Δx 和Δy分別為Word a和Word b重疊部分的x，y方向的長度。

單詞間無重疊無覆蓋是緊湊布局的前提，因此我們定義斥力的優(yōu)先級高于引力，量化的表示為

與單詞分散的遍歷一致，依照單詞的優(yōu)先級順序從最低優(yōu)先級的單詞進行遍歷，同等優(yōu)先級的單詞按序號從大到小進行，依次計算每個單詞受到的合力，以圖3(b)中的word b為例，它在第q次遍歷時所受到的合力可以被定義為：

其中，num為以單詞出現(xiàn)頻率為依據(jù)的單詞編號，單詞出現(xiàn)頻率越高其值越小，N為所分析詞云包含單詞的總個數(shù)，t為給定值的單位時間。

3 實驗結(jié)果分析

以百度百科中定義Wordnet的文本描述為文本來源生成的兩種布局形式的詞云圖，分別為螺旋狀排布單詞的緊湊布局（如圖5(a)）和完全依照單詞重要性程度按層次依次從大到小發(fā)散性布局（如圖5(b)），為輸入詞云。

由于中文和韓文相比于英文來說都屬于方塊型字體，相應(yīng)的中文翻譯成韓文后遮擋的面積較小，如圖5(c)所示，可以直接使用緊湊布局算法對其進行調(diào)整；而中文翻譯成英文詞云出現(xiàn)的遮擋面積過大，如圖5(d)，所以先將詞云用單詞分散算法進行分散處理，分散后的詞云分布如圖6所示，再進行緊湊布局，形成最終詞云分布。圖5(e)和圖5(f)為兩種詞云布局形式分別翻譯為韓文和英文后的最終詞云分布圖。

詞云的拓撲變化主要由單詞間相對位置變化和單詞本身大小變化引起的。為了對我們的算法在替換原詞云單詞后的拓撲保持程度量化說明，受文獻[12]啟發(fā)，我們提出一種方法評估翻譯后詞云拓撲保持程度。

圖5 兩種中文分布的不同翻譯結(jié)果

圖6 分散算法處理后的英文詞云分布

其中，由于翻譯后的單詞間相對位置變化，因此各單詞相對于最高優(yōu)先級單詞的相對位置也會發(fā)生變化，我們定義參數(shù)距離和，即Δ p，則：

與此同時，單詞本身大小的改變也會對單詞間的語義相關(guān)性和詞云的拓撲保持產(chǎn)生影響。由此，我們定義參數(shù)s表示詞云中所有單詞的矩形框的面積和。

表2 翻譯前后詞云拓撲保持程度的量化衡量

從實驗結(jié)果可知，相比于翻譯為韓文后詞云的拓撲結(jié)構(gòu)得到了程度較大保持來講，翻譯后的英文詞云單詞間的語義相關(guān)性較小，拓撲保持效果相對較差，與圖5所示的實驗結(jié)果相符。這主要是由于在緊湊布局算法中使用了按優(yōu)先級由低到高依次進行力導(dǎo)向布局的緣故，此方法在拓撲調(diào)節(jié)時極力地保持了優(yōu)先級較高單詞的相對位置不變，并且使空白的區(qū)域盡量的減少，因此優(yōu)先級較低的詞便有可能產(chǎn)生相對位置較大的變化。如圖5(b)中“計算機”一詞與圖5(f)中相應(yīng)翻譯后單詞“computer”位置差距較大，產(chǎn)生此現(xiàn)象的原因主要是：①單詞“Computer”的優(yōu)先級相對較低，移動的距離相對較大；②使用緊湊布局調(diào)節(jié)時，由于單詞“Computer”緊湊時需要的空白區(qū)域較大，無法將其塞入原相對位置，而字體比“Computer”小的詞（如單詞“Overall”）大小合適，為了不出現(xiàn)詞云大面積空白的現(xiàn)象，由其代替入空白區(qū)域。正由于此，致使詞“Computer”因為程序的多次循環(huán)而逐漸的偏離。針對于翻譯為英文后優(yōu)先級較低單詞相對位置不變但存在偏離的情況有待進一步改善，我們的深入工作將進一步在其上開展。

4 總 結(jié)

本文分析了一種適用于不同布局的詞云可視化拓撲保持布局算法，面向翻譯中文詞云為英文詞云和韓文詞云的具體情況做了詳細描述。針對翻譯后存在大面積重疊的詞云分布，在進行單詞分散的基礎(chǔ)上，對分散后的詞云進行三角剖分，用控制網(wǎng)格確保緊湊布局的過程中保持詞云的原有拓撲。結(jié)果表明，該算法對于替換單詞后的詞云拓撲具有較好的保持效果，也為詞云研究工作開辟了一種全新模式。

[1] Proshansky H M. Environmental psychology: People and their physical settings[M]. Holt, 1976: 632-633.

[2] Evans T. Money makes the world go round [J]. Capital & Class, 1985, 8(3): 99-123.

[3] Kaser O, Lemire D. Tag-cloud drawing: algorithms for cloud visualization [C]//www workshop on Tagging and Metadata for Social Information Organization, 2007: 1087-1088.

[4] Paulovich F V, Toledo F, Telles G P, Minghim R, Nonato L G. Semantic Wordification of Document Collections[C]//Computer Graphics Forum. Blackwell Publishing Ltd, 2012: 1145-1153.

[5] Park M, Joshi D, Loui A. Tag Cloud++-scalable tag clouds for arbitrary layouts[C]//IEEE International Symposium on Multimedia(ISM), 2012: 318-325.

[6] Afzal S, Maciejewski R, Jang Y, Elmqvist N, Ebert D S. Spatial text visualization using automatic typographic maps [J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(12): 2556-2564.

[7] Wang C, Yu H, Ma K L. Importance-driven timevarying data visualization [J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(6): 1547-1554.

[8] Shaw B. Utilizing folksonomy: similarity metadata from the del. icio. us system [EB/OL]. http://www.metablake. com/webfolk/web-project.pdf, 2008.

[9] Cui Weiwei, Wu Yingcai, Liu Shixia, Wei Furu, Zhou M X, Qu Huamin. Context preserving dynamic word cloud visualization[C]// IEEE Pacific Visualization Symposium (PacificVis), 2010: 121-128.

[10] 姚天順, 張 俐, 高 竹. WordNet綜述[J]. 語言文字應(yīng)用, 2001, 1: 27-32.

[11] Berg M D, Cheong O, Kreveld M V, Overmars M. Computational geometry: algorithms and applications [M]. Springer, 2000: 1-17.

[12] 劉文印, 唐 龍, 唐澤圣. 一種在矢量基礎(chǔ)上進行圖形識別的通用方法[J]. 軟件學(xué)報, 1997, 8(5): 376-383.

Topology Preserving Word Cloud Visualization Algorithm for Cross-Language Replacing

Lu Qiang1,2, Tang Liang1,2, Ma Kunle2, Liang Chong1,2
(1.Visualization & Cooperative Computing, Hefei University of Technology, Hefei Anhui 230009, China; 2. School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China)

The word cloud may be unstable when replacing some words or even all words from it. This paper presents a visualization algorithm to solve the problem and ensure that the final topology of the cloud will be totally consistent with the original one. The algorithm can be concluded as follows. Firstly, all the words are scattered in the cloud to avoid overlapping. Secondly, the Delaunay Triangulation may be used on the words to obtain the mesh which can make sure the topology not be destructed after the last step being executed. Finally, the words are compacted on the basis of the control mesh to reduce the empty space. Then the final layouts of the word cloud may be formed. This paper may take the situation that all the words may be translated in other language for example to introduce the method in detail. The algorithm is a new breakthrough in keeping the stability and topology of the word clouds.

topology preserve; words replace; cross-language; scatter words; words compaction

TP 391.72

A

2095-302X (2014)02-0307-06

2013-06-08；定稿日期：2013-07-21

國家自然科學(xué)基金資助項目（61070124）；高等學(xué)校博士學(xué)科點專項科研基金資助項目（20120111110003）

路 強（1978-），男，安徽合肥人，副教授，博士。主要研究方向為信息可視化與可視分析學(xué)習(xí)環(huán)境。E-mail：luqiang@hfut.edu.cn