電力圖形系統(tǒng)應(yīng)用中SVG文件壓縮算法

盧軍雄+鐘俊

摘要：針對可縮放矢量圖形（SVG）作為矢量圖形格式優(yōu)勢明顯，但存儲時(shí)占用內(nèi)存較大和SVG文件數(shù)據(jù)大量冗余的特點(diǎn)，提出分別使用Huffman算法和LZSS算法對電力系統(tǒng)圖形數(shù)據(jù)載體SVG文件進(jìn)行壓縮，在滿足壓縮時(shí)間的前提下，LZSS算法相對于Huffman算法壓縮率更高。LZSS算法性能能滿足電力系統(tǒng)應(yīng)用SVG文件壓縮要求。

關(guān)鍵詞：電力圖形系統(tǒng)；SVG文件；Huffman；LZSS

中圖分類號：TN919.8 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2017）01-0115-04

隨著電力系統(tǒng)規(guī)模的擴(kuò)大和系統(tǒng)結(jié)構(gòu)越發(fā)復(fù)雜，利用計(jì)算機(jī)技術(shù)開發(fā)出界面友好圖形化軟件對于提高電力系統(tǒng)自動化具有重要的意義。SVG作為W3C推出的一種基于XML文本性矢量描述語言，被IEC61970推薦為圖形文件的基本格式，逐步成為行業(yè)標(biāo)準(zhǔn)[1]。SVG文件的優(yōu)點(diǎn)為。

（1）表達(dá)能力強(qiáng)，刪除和添加方便；

（2）支持圖形無失真縮放；

（3）支持動畫和互動。

SVG文件是純粹的XML，擁有XML的所有特性，SVG作為電力圖形系統(tǒng)數(shù)據(jù)載體已逐步成為一種趨勢[2]。SVG文件以樹的形式管理SVG元素，SVG元素都是基本圖元與其屬性構(gòu)成的文本，基本圖元有直線、圓、橢圓、文本、圓弧等，每一種圖元都有相應(yīng)的屬性，如顏色、線寬、填充等。例如一個(gè)圓的SVG元素定義為，描述圓心為（30，60），半徑為10個(gè)像素點(diǎn)，邊框?yàn)楹谏€寬為2，填充為紅色的圓。在電力圖形系統(tǒng)中復(fù)雜的圖形除去SVG文件固有格式的元素外，剩余的都是由這些基本的圖元構(gòu)成。

信息論之父Claude Shannon認(rèn)為信息都存在冗余，SVG文件存在很多相同的屬性文本，信息冗余量很大，有必要對SVG文件進(jìn)行壓縮。本文分別從統(tǒng)計(jì)編碼Huffman編碼和字典編碼LZSS兩種編碼方案對SVG文件進(jìn)行壓縮，實(shí)驗(yàn)表明LZSS壓縮算法的壓縮比更高。

1 Huffman編碼和LZSS編碼原理

1.1 Huffman編碼

Huffman編碼是一種基于統(tǒng)計(jì)的變長編碼，在編碼前統(tǒng)計(jì)各模式的頻率，根據(jù)不同模式的頻率采用不同長度碼字對其編碼（對于出現(xiàn)頻率高的模式，其編碼的長度最短）。Huffman采用前綴碼的方法表示每一個(gè)字符，前綴碼有時(shí)也稱前綴樹[3]，其特點(diǎn)是任何一個(gè)字符的編碼都不能作為另外一個(gè)字符編碼的前綴，這樣可以大大簡化解碼過程，解碼器只需要識別一個(gè)完整的前綴碼就能解碼當(dāng)前字符，而不需要進(jìn)一步讀取后面的編碼。Huffman編碼的平均長度，在類似的編碼方案中，Huffman編碼獲得的編碼效果最好[4]。

Huffman編碼過程是通過Huffman樹的構(gòu)建過程完成的。首先將字符的統(tǒng)計(jì)結(jié)果按照字符出現(xiàn)頻率的降序排列，記待編碼的數(shù)據(jù)為個(gè)數(shù)為n的字符集，集合；字符出現(xiàn)頻率為，，集合為Huffman編碼的二進(jìn)制輸出，為字符對應(yīng)的二進(jìn)制編碼。編碼帶權(quán)路徑長度，為編碼輸出的二進(jìn)制長度。構(gòu)造一個(gè)Huffman樹的簡單過程如圖1。

表1展示了8個(gè)字符A∶K出現(xiàn)頻率和經(jīng)過Huffman編碼后對應(yīng)的二進(jìn)制輸出。

編碼輸出的帶權(quán)路徑長度為=2.58，而采用二進(jìn)制編碼需要的帶權(quán)路徑長度為3。根據(jù)表中字符出現(xiàn)的頻率選擇出現(xiàn)頻率最小的兩個(gè)字符A，B構(gòu)造樹，其左孩子為A，出現(xiàn)頻率為0.01，右孩子為B，出現(xiàn)頻率0.05，根節(jié)點(diǎn)為左右孩子出現(xiàn)頻率之和0.06；并將字符A，B從字符集中刪除。同時(shí)將作為新的字符加入字符集中，此時(shí)頻率最小的兩個(gè)節(jié)點(diǎn)是和字符F，同樣按照構(gòu)造樹方式構(gòu)造出整個(gè)Huffman樹如圖1。

1.2 LZSS編碼原理

LZSS編碼原理不同于基于統(tǒng)計(jì)方式的Huffman編碼，它是基于字典壓縮算法LZ77算法的改進(jìn)，不再需要統(tǒng)計(jì)字符出現(xiàn)頻率[5]。LZ77使用已出現(xiàn)的字符串的相關(guān)信息來表示當(dāng)前需要被編碼的字符串，在此過程中使用滑動窗口完成字符流的輸入和字符串的匹配。在編碼過程中，字符緩沖區(qū)的大小設(shè)定為N，已壓縮好字符串的長度為M（M

壓縮開始前，緩沖區(qū)設(shè)為空，字符串以字符流的方式從右至左進(jìn)入超前查看緩沖區(qū)，找出超前查看緩沖區(qū)和正文窗口的匹配的最長字符串，假設(shè)找到最長匹配字符串，其起始位置為s，長度為L（長度可以為0），出現(xiàn)第一個(gè)不匹配的字符位置為e，這樣從當(dāng)前編碼位置開始到第一個(gè)不匹配的字符可以編碼為，且滿足。如果編碼信息占用空間比個(gè)字節(jié)小，便實(shí)現(xiàn)了字符串的壓縮。具體算法流程如圖3。

LZ77壓縮算法存在時(shí)間和空間的性能約束：

在壓縮時(shí)間上存在性能瓶頸：超前查看緩沖區(qū)字符與正文字典匹配采用的是線性的匹配方式，超前查看窗口的大小為，正文窗口大小為M，表2給出了常用字符串匹配算法的平均時(shí)間復(fù)雜度[7]。

表2給出的算法時(shí)間復(fù)雜度最好的情況還是線性的，LZ77算法正文窗口一般設(shè)置為幾千，超前查看緩沖區(qū)設(shè)置位十幾，在進(jìn)行字符串匹配時(shí)嚴(yán)重影響算法的時(shí)間性能[8]。而且都是相關(guān)窗口大小成正比。算法在壓縮空間也存在缺陷：當(dāng)未找到匹配字符串時(shí)，輸出三元組占用的空間比需要進(jìn)行編碼的字符串占用的空間更大，出現(xiàn)負(fù)壓縮的情況。

LZSS算法針對LZ77算法的這兩點(diǎn)缺點(diǎn)作出了改進(jìn)。LZSS采用二叉查找樹技術(shù)替換了滑動窗口的線性查找，超前查看緩沖區(qū)字符串進(jìn)入正文窗口時(shí)需要按照二叉查找樹的特征加入到二叉樹中，采用二叉查找樹技術(shù)字符串的匹配時(shí)間極大優(yōu)化，在壓縮時(shí)間上極大地提高了壓縮性能[5]；LZSS在編碼輸出采用位標(biāo)志方式區(qū)別輸出，輸出時(shí)編碼輸出與設(shè)定最小字符串長度的大小，只有在編碼輸出字節(jié)數(shù)較小采用編碼輸出，反之輸出真正的字符。

2 Huffman編碼與LZSS算法實(shí)現(xiàn)

2.1 Huffman編碼的實(shí)現(xiàn)

SVG文件字符采用單字節(jié)編碼，統(tǒng)計(jì)每個(gè)字符出現(xiàn)次數(shù)使用huffman_node *huffmanArray[0xff]數(shù)組便可以將SVG文本字符統(tǒng)計(jì)完整。Huffman樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為：

typedef struct huffman_node

{

unsigned char value；

unsigned int count；

bool isDealt；

struct huffman_node *left， *right， *parent；

} huffman_node；

Huffman_node中value表示該節(jié)點(diǎn)代表的字符，isDealt表示該字符是否已被處理，在查找字符出現(xiàn)頻率最小的兩個(gè)中經(jīng)常使用此標(biāo)記。根據(jù)huffmanArray統(tǒng)計(jì)結(jié)果查找出現(xiàn)頻率最小的兩個(gè)字符，分別作為新建二叉樹的左右孩子，二叉樹父節(jié)點(diǎn)統(tǒng)計(jì)頻率為左右孩子出現(xiàn)頻率之和，并將已加入二叉樹的字符標(biāo)記為已處理。二叉樹仍然可以按照單個(gè)字符處理，直到所有的字符都被加入Huffman樹中。在給編碼數(shù)組編碼時(shí)首先訪問Huffman樹最左邊的葉子節(jié)點(diǎn)，設(shè)定其編碼為‘0，然后通過parent指針訪問右節(jié)點(diǎn)設(shè)定編碼為‘1，再次通過parent回到父節(jié)點(diǎn)，避免使用遞歸方式遍歷樹結(jié)構(gòu)帶來的時(shí)間開銷。通過已經(jīng)編碼過的編碼數(shù)組為SVG文件每一個(gè)字符編碼，直到文件結(jié)束。Huffman編碼模塊劃分如圖4。

由于SVG文件所使用的字符都是8位編碼字符，編碼數(shù)組的長度為0xff。編碼數(shù)組的數(shù)據(jù)結(jié)構(gòu)為

typedef struct code_list

{

byte_t codeLen；

unsigned int *code；

} code_list；

2.2 LZSS編碼的實(shí)現(xiàn)

根據(jù)前述的LZ77算法，改進(jìn)后的LZSS算法在編碼輸出和字符串匹配上實(shí)現(xiàn)了優(yōu)化。其算法的如流程圖5。

實(shí)現(xiàn)算法的相關(guān)數(shù)據(jù)結(jié)構(gòu)：

超前查看緩沖區(qū)和正文緩沖區(qū)，根據(jù)文件內(nèi)容上下文依賴關(guān)系正文緩沖區(qū)大小不盡相同，定義宏WINDOW_SIZE大小為4K，用12bits來表示，所以需要4bits來表示字符串的長度。超前查看緩沖區(qū)一般設(shè)置為18bits。定義最長不可編碼長度為MAX_UNCODED，當(dāng)匹配字符串與MAX_UNCODED比較時(shí)，可以使用ENCODE與UNCODE來標(biāo)識輸出。最大可編碼長度為超前查看緩沖區(qū)大小設(shè)置為MAX_CODE，由匹配字符串長度和最長不可編碼長度決定。

字符串編碼使用封裝長度和位置的數(shù)據(jù)結(jié)構(gòu)：

typedef struct encoded_string

{

unsigned int offset；

unsigned int length；

} encoded_string；

offset和length可以分別得到字符串編碼信息：位置和長度。

二分查找樹是二叉樹的一種變形，二分查找樹根節(jié)點(diǎn)存儲的關(guān)鍵字總是大于其左子樹的關(guān)鍵字，小于右子樹的關(guān)鍵字。在建立二分查找樹時(shí)要按照二叉樹關(guān)鍵字的性質(zhì)建立，對于N個(gè)節(jié)點(diǎn)的二分查找樹查找關(guān)鍵字時(shí)，最好的情況下時(shí)間復(fù)雜度為，大大加速了查找時(shí)間。該算法使用的二叉樹結(jié)構(gòu)為：

typedef struct tree_node

{

unsigned int left；

unsigned int right；

unsigned int parent；

} tree_node；

該結(jié)構(gòu)體中的left，right，parent都是指向正文緩沖區(qū)字符的索引；使用tree_node tree[WINDOW_SIZE]對應(yīng)每一個(gè)正文緩沖區(qū)的字符。

在算法進(jìn)入主循環(huán)前需要對正文緩沖區(qū)，超前查看緩沖區(qū)和二分查找樹初始化，InitializeSearchTree（）完成樹的初始化工作，二分查找樹根節(jié)點(diǎn)ROOT_INDEX為依照正文緩沖區(qū)建立字符串的最后一個(gè)窗口為WINDOW_SIZE - MAX_CODED-1，為方便查找和插入操作空節(jié)點(diǎn)NULL_INDEX為ROOT_INDEX+1。初始化樹根節(jié)點(diǎn)的父節(jié)點(diǎn)為ROOT_INDEX；剩余所有節(jié)點(diǎn)左右孩子和父節(jié)點(diǎn)全部清空。

只有超前查看緩沖區(qū)不為空，壓縮算法將持續(xù)進(jìn)行，主要是對位于超前查看緩沖區(qū)的字符串進(jìn)行編碼，二分查找樹的字符串刪除和添加；MatchString（）算法利用二分查找樹返回匹配字符串位置和長度，從根節(jié)點(diǎn)開始查找匹配字符，如匹配即利用左右節(jié)點(diǎn)關(guān)鍵字關(guān)系進(jìn)行下一個(gè)字符匹配，直到搜索到葉子節(jié)點(diǎn)。將以編碼過的字符串加入二叉查找樹由AddString（）完成，在向二分查找樹添加字符串的同時(shí)需要將樹中舊的字符串刪除DeleteString（）。

3 壓縮算法性能與實(shí)驗(yàn)

衡量壓縮算法的性能主要有壓縮率和壓縮耗時(shí)，但是這兩個(gè)指標(biāo)之間存在矛盾，只能在合適的應(yīng)用場景折中選擇。定義壓縮率=壓縮文件大小/源文件大小*100%，壓縮率越小表明壓縮效果越好；壓縮耗時(shí)是指壓縮完文件所需時(shí)間。

實(shí)驗(yàn)設(shè)備采用采用Ubuntu 15.10操作系統(tǒng)，CPU型號為Intel（R） Core（TM） i5@2.53GHz，內(nèi)存大小為4G，Huffman算法和LZSS算法運(yùn)行環(huán)境相同。壓縮數(shù)據(jù)源為電力系統(tǒng)圖形界面SVG文件。實(shí)驗(yàn)結(jié)果如表3。

從表3可以看出對Huffman壓縮算法在壓縮時(shí)間上比LZSS算法好，但LZSS壓縮算法在壓縮比性能上比Huffman壓縮效果好，在存儲空間較小的應(yīng)用場合有一定的應(yīng)用場景。對于特定的壓縮算法，文件在較大時(shí)其壓縮效果比小文件更好，在電力圖形化系統(tǒng)中SVG文件越大，其信息冗余越多，可以壓縮的空間越大，壓縮率也相對高一些。

參考文獻(xiàn)

[1]紀(jì)陵，蔣衍君，施廣德.基于SVG的電力系統(tǒng)圖形互操作研究[J].電力自動化設(shè)備，2011，31（7）：105-114.

[2]李為，潘秀霞，等.基于SVG標(biāo)準(zhǔn)的電力系統(tǒng)圖形編輯器的設(shè)計(jì)與實(shí)現(xiàn)[J].中國電力教育，2008年研究綜述與技術(shù)論壇專刊.

[3]Utpal Nandi， Jyotsna Kumar Mandal. Windowed Huffman coding with limited distinct symbols[J]. Procedia Technology， 2012， 4：589-594.

[4]Yi Zhang， Zhili Pei， Jinhui Yang， Yanchun Liang. Canonical Huffman code based full-text index[J]. Progress in Natural Science， 2008， 18（3）：325-330.

[5]王平著.LZSS文本壓縮算法實(shí)現(xiàn)與研究[J].計(jì)算機(jī)工程.2001年8月.第27卷（第 8期）.

[6]閭松林.基于字典編解碼算法的應(yīng)用與研究[D].湖南長沙，中南大學(xué)，2011：9-11.

[7]王堅(jiān).基于后綴數(shù)組的滑動窗口匹配壓縮改進(jìn)算法研究[D].湖北武漢，華中科技大學(xué)，2012：7-10.

[8]蔡成攀.無損數(shù)據(jù)壓縮技術(shù)在嵌入式系統(tǒng)中的應(yīng)用[D].陜西西安，西安電子科技大學(xué)，2007，14-18.