電力圖形系統(tǒng)應用中SVG文件壓縮算法
2017-04-25 23:44:52盧軍雄鐘俊
數(shù)字技術(shù)與應用 2017年1期
盧軍雄+鐘俊
摘要：針對可縮放矢量圖形（SVG）作為矢量圖形格式優(yōu)勢明顯，但存儲時占用內(nèi)存較大和SVG文件數(shù)據(jù)大量冗余的特點，提出分別使用Huffman算法和LZSS算法對電力系統(tǒng)圖形數(shù)據(jù)載體SVG文件進行壓縮，在滿足壓縮時間的前提下，LZSS算法相對于Huffman算法壓縮率更高。LZSS算法性能能滿足電力系統(tǒng)應用SVG文件壓縮要求。
關鍵詞：電力圖形系統(tǒng)；SVG文件；Huffman；LZSS
中圖分類號：TN919.8 文獻標識碼：A 文章編號：1007-9416（2017）01-0115-04
隨著電力系統(tǒng)規(guī)模的擴大和系統(tǒng)結(jié)構(gòu)越發(fā)復雜，利用計算機技術(shù)開發(fā)出界面友好圖形化軟件對于提高電力系統(tǒng)自動化具有重要的意義。SVG作為W3C推出的一種基于XML文本性矢量描述語言，被IEC61970推薦為圖形文件的基本格式，逐步成為行業(yè)標準[1]。SVG文件的優(yōu)點為。
（1）表達能力強，刪除和添加方便；
（2）支持圖形無失真縮放；
（3）支持動畫和互動。
SVG文件是純粹的XML，擁有XML的所有特性，SVG作為電力圖形系統(tǒng)數(shù)據(jù)載體已逐步成為一種趨勢[2]。SVG文件以樹的形式管理SVG元素，SVG元素都是基本圖元與其屬性構(gòu)成的文本，基本圖元有直線、圓、橢圓、文本、圓弧等，每一種圖元都有相應的屬性，如顏色、線寬、填充等。例如一個圓的SVG元素定義為
信息論之父Claude Shannon認為信息都存在冗余，SVG文件存在很多相同的屬性文本，信息冗余量很大，有必要對SVG文件進行壓縮。本文分別從統(tǒng)計編碼Huffman編碼和字典編碼LZSS兩種編碼方案對SVG文件進行壓縮，實驗表明LZSS壓縮算法的壓縮比更高。
1 Huffman編碼和LZSS編碼原理
1.1 Huffman編碼
Huffman編碼是一種基于統(tǒng)計的變長編碼，在編碼前統(tǒng)計各模式的頻率，根據(jù)不同模式的頻率采用不同長度碼字對其編碼（對于出現(xiàn)頻率高的模式，其編碼的長度最短）。Huffman采用前綴碼的方法表示每一個字符，前綴碼有時也稱前綴樹[3]，其特點是任何一個字符的編碼都不能作為另外一個字符編碼的前綴，這樣可以大大簡化解碼過程，解碼器只需要識別一個完整的前綴碼就能解碼當前字符，而不需要進一步讀取后面的編碼。Huffman編碼的平均長度，在類似的編碼方案中，Huffman編碼獲得的編碼效果最好[4]。
Huffman編碼過程是通過Huffman樹的構(gòu)建過程完成的。首先將字符的統(tǒng)計結(jié)果按照字符出現(xiàn)頻率的降序排列，記待編碼的數(shù)據(jù)為個數(shù)為n的字符集，集合；字符出現(xiàn)頻率為，，集合為Huffman編碼的二進制輸出，為字符對應的二進制編碼。編碼帶權(quán)路徑長度，為編碼輸出的二進制長度。構(gòu)造一個Huffman樹的簡單過程如圖1。
表1展示了8個字符A∶K出現(xiàn)頻率和經(jīng)過Huffman編碼后對應的二進制輸出。
編碼輸出的帶權(quán)路徑長度為=2.58，而采用二進制編碼需要的帶權(quán)路徑長度為3。根據(jù)表中字符出現(xiàn)的頻率選擇出現(xiàn)頻率最小的兩個字符A，B構(gòu)造樹，其左孩子為A，出現(xiàn)頻率為0.01，右孩子為B，出現(xiàn)頻率0.05，根節(jié)點為左右孩子出現(xiàn)頻率之和0.06；并將字符A，B從字符集中刪除。同時將作為新的字符加入字符集中，此時頻率最小的兩個節(jié)點是和字符F，同樣按照構(gòu)造樹方式構(gòu)造出整個Huffman樹如圖1。
1.2 LZSS編碼原理
LZSS編碼原理不同于基于統(tǒng)計方式的Huffman編碼，它是基于字典壓縮算法LZ77算法的改進，不再需要統(tǒng)計字符出現(xiàn)頻率[5]。LZ77使用已出現(xiàn)的字符串的相關信息來表示當前需要被編碼的字符串，在此過程中使用滑動窗口完成字符流的輸入和字符串的匹配。在編碼過程中，字符緩沖區(qū)的大小設定為N，已壓縮好字符串的長度為M（M 壓縮開始前，緩沖區(qū)設為空，字符串以字符流的方式從右至左進入超前查看緩沖區(qū)，找出超前查看緩沖區(qū)和正文窗口的匹配的最長字符串，假設找到最長匹配字符串，其起始位置為s，長度為L（長度可以為0），出現(xiàn)第一個不匹配的字符位置為e，這樣從當前編碼位置開始到第一個不匹配的字符可以編碼為，且滿足。如果編碼信息占用空間比個字節(jié)小，便實現(xiàn)了字符串的壓縮。具體算法流程如圖3。 LZ77壓縮算法存在時間和空間的性能約束： 在壓縮時間上存在性能瓶頸：超前查看緩沖區(qū)字符與正文字典匹配采用的是線性的匹配方式，超前查看窗口的大小為，正文窗口大小為M，表2給出了常用字符串匹配算法的平均時間復雜度[7]。 表2給出的算法時間復雜度最好的情況還是線性的，LZ77算法正文窗口一般設置為幾千，超前查看緩沖區(qū)設置位十幾，在進行字符串匹配時嚴重影響算法的時間性能[8]。而且都是相關窗口大小成正比。算法在壓縮空間也存在缺陷：當未找到匹配字符串時，輸出三元組占用的空間比需要進行編碼的字符串占用的空間更大，出現(xiàn)負壓縮的情況。 LZSS算法針對LZ77算法的這兩點缺點作出了改進。LZSS采用二叉查找樹技術(shù)替換了滑動窗口的線性查找，超前查看緩沖區(qū)字符串進入正文窗口時需要按照二叉查找樹的特征加入到二叉樹中，采用二叉查找樹技術(shù)字符串的匹配時間極大優(yōu)化，在壓縮時間上極大地提高了壓縮性能[5]；LZSS在編碼輸出采用位標志方式區(qū)別輸出，輸出時編碼輸出與設定最小字符串長度的大小，只有在編碼輸出字節(jié)數(shù)較小采用編碼輸出，反之輸出真正的字符。
2 Huffman編碼與LZSS算法實現(xiàn)
2.1 Huffman編碼的實現(xiàn)
SVG文件字符采用單字節(jié)編碼，統(tǒng)計每個字符出現(xiàn)次數(shù)使用huffman_node *huffmanArray[0xff]數(shù)組便可以將SVG文本字符統(tǒng)計完整。Huffman樹節(jié)點的數(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é)點代表的字符，isDealt表示該字符是否已被處理，在查找字符出現(xiàn)頻率最小的兩個中經(jīng)常使用此標記。根據(jù)huffmanArray統(tǒng)計結(jié)果查找出現(xiàn)頻率最小的兩個字符，分別作為新建二叉樹的左右孩子，二叉樹父節(jié)點統(tǒng)計頻率為左右孩子出現(xiàn)頻率之和，并將已加入二叉樹的字符標記為已處理。二叉樹仍然可以按照單個字符處理，直到所有的字符都被加入Huffman樹中。在給編碼數(shù)組編碼時首先訪問Huffman樹最左邊的葉子節(jié)點，設定其編碼為‘0，然后通過parent指針訪問右節(jié)點設定編碼為‘1，再次通過parent回到父節(jié)點，避免使用遞歸方式遍歷樹結(jié)構(gòu)帶來的時間開銷。通過已經(jīng)編碼過的編碼數(shù)組為SVG文件每一個字符編碼，直到文件結(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編碼的實現(xiàn)
根據(jù)前述的LZ77算法，改進后的LZSS算法在編碼輸出和字符串匹配上實現(xiàn)了優(yōu)化。其算法的如流程圖5。
實現(xiàn)算法的相關數(shù)據(jù)結(jié)構(gòu)：
超前查看緩沖區(qū)和正文緩沖區(qū)，根據(jù)文件內(nèi)容上下文依賴關系正文緩沖區(qū)大小不盡相同，定義宏WINDOW_SIZE大小為4K，用12bits來表示，所以需要4bits來表示字符串的長度。超前查看緩沖區(qū)一般設置為18bits。定義最長不可編碼長度為MAX_UNCODED，當匹配字符串與MAX_UNCODED比較時，可以使用ENCODE與UNCODE來標識輸出。最大可編碼長度為超前查看緩沖區(qū)大小設置為MAX_CODE，由匹配字符串長度和最長不可編碼長度決定。
字符串編碼使用封裝長度和位置的數(shù)據(jù)結(jié)構(gòu)：
typedef struct encoded_string
{
unsigned int offset；
unsigned int length；
} encoded_string；
offset和length可以分別得到字符串編碼信息：位置和長度。
二分查找樹是二叉樹的一種變形，二分查找樹根節(jié)點存儲的關鍵字總是大于其左子樹的關鍵字，小于右子樹的關鍵字。在建立二分查找樹時要按照二叉樹關鍵字的性質(zhì)建立，對于N個節(jié)點的二分查找樹查找關鍵字時，最好的情況下時間復雜度為，大大加速了查找時間。該算法使用的二叉樹結(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]對應每一個正文緩沖區(qū)的字符。
在算法進入主循環(huán)前需要對正文緩沖區(qū)，超前查看緩沖區(qū)和二分查找樹初始化，InitializeSearchTree（）完成樹的初始化工作，二分查找樹根節(jié)點ROOT_INDEX為依照正文緩沖區(qū)建立字符串的最后一個窗口為WINDOW_SIZE - MAX_CODED-1，為方便查找和插入操作空節(jié)點NULL_INDEX為ROOT_INDEX+1。初始化樹根節(jié)點的父節(jié)點為ROOT_INDEX；剩余所有節(jié)點左右孩子和父節(jié)點全部清空。
只有超前查看緩沖區(qū)不為空，壓縮算法將持續(xù)進行，主要是對位于超前查看緩沖區(qū)的字符串進行編碼，二分查找樹的字符串刪除和添加；MatchString（）算法利用二分查找樹返回匹配字符串位置和長度，從根節(jié)點開始查找匹配字符，如匹配即利用左右節(jié)點關鍵字關系進行下一個字符匹配，直到搜索到葉子節(jié)點。將以編碼過的字符串加入二叉查找樹由AddString（）完成，在向二分查找樹添加字符串的同時需要將樹中舊的字符串刪除DeleteString（）。
3 壓縮算法性能與實驗
衡量壓縮算法的性能主要有壓縮率和壓縮耗時，但是這兩個指標之間存在矛盾，只能在合適的應用場景折中選擇。定義壓縮率=壓縮文件大小/源文件大小*100%，壓縮率越小表明壓縮效果越好；壓縮耗時是指壓縮完文件所需時間。
實驗設備采用采用Ubuntu 15.10操作系統(tǒng)，CPU型號為Intel（R） Core（TM） i5@2.53GHz，內(nèi)存大小為4G，Huffman算法和LZSS算法運行環(huán)境相同。壓縮數(shù)據(jù)源為電力系統(tǒng)圖形界面SVG文件。實驗結(jié)果如表3。
從表3可以看出對Huffman壓縮算法在壓縮時間上比LZSS算法好，但LZSS壓縮算法在壓縮比性能上比Huffman壓縮效果好，在存儲空間較小的應用場合有一定的應用場景。對于特定的壓縮算法，文件在較大時其壓縮效果比小文件更好，在電力圖形化系統(tǒng)中SVG文件越大，其信息冗余越多，可以壓縮的空間越大，壓縮率也相對高一些。
參考文獻
[1]紀陵，蔣衍君，施廣德.基于SVG的電力系統(tǒng)圖形互操作研究[J].電力自動化設備，2011，31（7）：105-114.
[2]李為，潘秀霞，等.基于SVG標準的電力系統(tǒng)圖形編輯器的設計與實現(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文本壓縮算法實現(xiàn)與研究[J].計算機工程.2001年8月.第27卷（第 8期）.
[6]閭松林.基于字典編解碼算法的應用與研究[D].湖南長沙，中南大學，2011：9-11.
[7]王堅.基于后綴數(shù)組的滑動窗口匹配壓縮改進算法研究[D].湖北武漢，華中科技大學，2012：7-10.
[8]蔡成攀.無損數(shù)據(jù)壓縮技術(shù)在嵌入式系統(tǒng)中的應用[D].陜西西安，西安電子科技大學，2007，14-18.
