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

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

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

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

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

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

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

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

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

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

1 詞云研究現狀

現階段的詞云工作可以分為著重于研究詞云布局從而為用戶帶來美學影響和以提高詞云可讀性為目的調整單詞自身特性或單詞間特性這兩方面?；谶@兩方面的研究在詞云領域已經較為成熟。

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

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

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

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

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

2.1 相關定義

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

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

圖1 描述Wordnet的詞云

表1 根據頻率區間定義單詞優先級

2.2 基本框架

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

1 start

2 translate(V) //翻譯所有單詞節點的標簽

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

2.3 詞云翻譯

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

2.4 單詞分散

不同語種的同一單詞有著不同的顯示結果。我們仍然以中文單詞翻譯為對應的英文單詞為例說明。翻譯后的單詞在長度和高度上明顯存在差異，其長度一般較為拉長，高度在原有基礎上更為壓縮，這必然使得翻譯后的詞云存在大面積的單詞重疊，為了達到消除單詞重疊的目的，我們提出一種單詞分散算法，實現可能存在大面積空白的無重疊詞云放置。

圖2 翻譯后的單詞重疊

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

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

2.5 緊湊布局

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

圖3 緊湊布局過程示意圖

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

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

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

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

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

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

3 實驗結果分析

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

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

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

圖5 兩種中文分布的不同翻譯結果

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

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

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

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

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

4 總 結

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

[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]. 語言文字應用, 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] 劉文印, 唐 龍, 唐澤圣. 一種在矢量基礎上進行圖形識別的通用方法[J]. 軟件學報, 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

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

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