摘 要：用Context加權(quán)來估計較為合理的條件概率分布并對當前信源符號進行編碼，能減小其編碼碼長。本文對Context的加權(quán)系數(shù)進行了研究，提出最優(yōu)化的權(quán)值是：多Context加權(quán)后，能夠使當前信源符號的前m個信源符號的碼長之和最短的那組權(quán)值。本文使用了多元優(yōu)化算法（MOA）對最短碼長進行尋優(yōu)從而得到最優(yōu)化的權(quán)值。并通過實驗驗證了該方法對于減小碼長的有效性，得到已知信源長度為10時，編碼的碼長較短且計算復雜度低。

關(guān)鍵詞：Context加權(quán)；權(quán)值；多元優(yōu)化算法；最短碼長

中圖分類號：TP18

根據(jù)編碼理論可知，若對信源序列x1…xn進行編碼，當前符號的編碼長度為：

但是p（xi/xi-1…x1）是不知道的，可用當前符號xn之前的已知信源符號序列x1…xn來估計些個條件概率分布，這種估計條件概率的機制稱為Context模型[1]。在p（xi/xi-1…x1）中如果已知的符號越多，而且所對應(yīng)的條件概率分布都有合理的估計，那么編碼的平均碼長應(yīng)逐漸減小直至接近信源極限熵。假設(shè)用已知信源序列x1…xn對當前信源符號xn進行估計，M表示信源符號可能的取值個數(shù)，那么條件概率分布就有Mn-1個。當 值較大時，在有限的已知信源符號中進行統(tǒng)計，每種情況的條件概率分布將得不到充分的統(tǒng)計，造成“Context稀釋”，Rissanen將其稱為“模型代價”[2]。為降低“模型代價”可以選取當前符號之前的某k（k<

其中ωg為第g組模型所對應(yīng)的權(quán)值。用加權(quán)的方法合并多個Context模型既降低了“模型代價”又充分利用了多個已知符號的條件概率分布的信息，從而有可能降低對當前信源符號xn編碼的碼長。

如何對多個條件概率分布加權(quán)，在前人的研究中Willems等人提出了一種針對二進制序列的CWT算法[3]，他們認為在特定Context條件下所對應(yīng)的信源子序列可能是無記憶的也可能是有記憶的，該算法對這兩種模型下的概率分布進行加權(quán)平均來獲得當前符號的概率分布。Mahone等人采用的編碼同樣針對二進制信源符號，其權(quán)值的調(diào)整是沿著編碼代價梯度方向進行的[4]。Cao M D等人認為權(quán)值ωg等于已知過去信源序列情況下模型g出現(xiàn)概率的大小。根據(jù)貝葉斯理論得出：模型g的權(quán)值ωg的負對數(shù)正比于利用該模型對過去信源序列進行編碼所得的平均碼長[5]。Pinho方法與Cao相近，但是其平均碼長的計算是隨著編碼的進行以遞歸濾波的辦法對權(quán)值進行調(diào)整[6]。

上述的研究中均沒有涉及到權(quán)值的最優(yōu)化問題，在本文中我們探索了權(quán)值的優(yōu)化問題，主要思路是：希望加權(quán)后的條件概率分布對過去的一段已知信源序列進行編碼的碼長最短?？紤]到用優(yōu)化算法來尋找上述權(quán)值最優(yōu)解的結(jié)果可能不唯一，本文采用多元優(yōu)化算法（MOA），該算法允許在整個解空間內(nèi)找到多組最優(yōu)解且不容易陷入局部最優(yōu)。本文以下部分分別討論了碼長的計算及其在Context加權(quán)中的應(yīng)用、多元優(yōu)化算法（MOA）、實驗設(shè)計及分析，最后給出結(jié)論。

1 碼長的計算

用多個Context模型進行加權(quán)合并得到當前符號的條件概率分布首先應(yīng)估計每個Context模型的條件概率分布。在模型g中對當前信源符號xn而言若選取已知信源符號xn-n1（g）…xn-nk（g）作為條件，則所有可能的組合有I=Mk種，于是該模型中所有Context組合可用集合D（g）={Ci（g） |i=1…I}表示。假設(shè)p（xn=j/Ci（g））表示在該模型中出現(xiàn)第i號Context組合時當前符號取值為j的條件概率，則該概率可用下式估計：

在對當前信源符號xn進行編碼時，根據(jù)公式1可知當前符號的編碼長度與當前符號的條件概率有關(guān)，而當前符號的條件概率是由多個Context模型中當前條件概率分布加權(quán)合并而成的（公式2）。若當前信源符號取值為j時，加權(quán)后的條件概率P（xn=j/Cω）實際上是下式計算的：

于是最優(yōu)化的權(quán)值為：G組Context加權(quán)后，能夠使當前信源符號的前m個信源符號的碼長之和最短的那組權(quán)值?？紤]到信源的相關(guān)性，下一段信源序列編碼時，使用該組權(quán)值對多組Context加權(quán)后進行編碼也應(yīng)得到較短的碼長。由于統(tǒng)計特性會隨時間變化，條件概率也是逐漸改變的，在一段信源編碼后應(yīng)對權(quán)值進行更新。

2 多元優(yōu)化MOA算法

本文采用多元優(yōu)化MOA算法[7]對權(quán)值進行求解，該算法用全局搜索元（GSA）和局部搜索元（LSA）交替合作地進行全局和局部的搜索。算法首先生成GSA，以優(yōu)勝劣汰決定其進入或者退出隊列，實現(xiàn)全局搜索；然后根據(jù)隊列中的GSA的排列位置和它對應(yīng)搜索空間中的位置，生成不同規(guī)模的LSA組實現(xiàn)對不同的局部進行不同粒度的局部搜索，以優(yōu)勝劣汰決定LSA進入或者退出GSA所對應(yīng)的棧。其結(jié)構(gòu)體（如圖1）是由1個位于頂部的隊列和n個掛接在隊列節(jié)點上的棧所組成。隊列中的每個節(jié)點下都掛載著一個棧。在隊列節(jié)點中，pPrior指向前一個隊列節(jié)點，pNext指向后一個隊列節(jié)點，pStack指向其下掛接的棧，pAtom指向一個全局搜索結(jié)構(gòu)元。同時每個隊列中包含一個Head和Last指針和一個最大長度屬性。在棧節(jié)點中，pUpper指向上一個棧節(jié)點，pUnder指向下一個棧節(jié)點，pAtom指向一個局部搜索結(jié)構(gòu)元。同時每個棧包含了pTop棧頂指針、pBottom棧底指針，和一個最大深度的屬性。

結(jié)構(gòu)體中隊列的節(jié)點根據(jù)結(jié)構(gòu)元的適應(yīng)度值ffit按從右到左依次遞減，棧中節(jié)點根據(jù)結(jié)構(gòu)元的適應(yīng)度值ffit從上到下依次遞增。隊列中GSA在隊列中的位置越靠前，在其鄰域內(nèi)生成的LSA個數(shù)就越多，這樣就能大大增加找到更優(yōu)解的概率，在本文中定義適應(yīng)值函數(shù)f（x）為加權(quán)后的一段信源序列的碼長Lm。算法具體流程如下：

Step1.初始化結(jié)構(gòu)體：按照結(jié)構(gòu)體的設(shè)定產(chǎn)生初始化GSA和LSA，并加入到結(jié)構(gòu)體。

Step2.產(chǎn)生GSA（全局搜索結(jié)構(gòu)元），更新隊列。

Step3.產(chǎn)生LSA（局部搜索結(jié)構(gòu)元），更新堆棧。

Step4.判斷群體性能是否滿足某一指標，或者已完成預定迭代次數(shù)，不滿足則回到步驟Step2。

本文設(shè)置結(jié)構(gòu)體中隊列的長度和各個棧的深度都為1000，搜索半徑為0～1之間，終止條件為迭代次數(shù)一千次。算法運行結(jié)束后左上方的結(jié)構(gòu)體中即存放了最優(yōu)自適應(yīng)值及其權(quán)值。

3 實驗方法及分析

本文選取原始灰度圖像進行實驗，為了更準確構(gòu)建條件概率分布，先將圖像進行了8級量化。若當前像素稱為x（i，j），當前像素空間位置的上方的像素點稱為x（i，j-1），左方的像素點稱為x（i-1，j），用這兩個已知像素點建立兩組context模型。為了進一步簡化計算，將這兩個像素點量化成0或者1.即x（i，j-1） [0，3]，則x（i，j-1）=0，若x（i，j-1） [3，7]，則x（i，j-1）=1，同理量化像素點x（i，j-1）。即Contextci（g）表示有兩組Context（g=1，2），每組Context有兩種組合情況（i=0，1）。

本文用貝葉斯平均求得的權(quán)值和一段信源序列的最短碼長對應(yīng)的權(quán)值，分別對兩組Context模型進行加權(quán)合并，再用算術(shù)編碼對圖像進行編碼，最后得到每個像素點編碼后碼長的比特數(shù)。如表1所示：每幅圖第一列表示用貝葉斯平均求權(quán)值得到的結(jié)果，第二列表示由一段信源序列的最短碼長求權(quán)值得到的結(jié)果。

由此表得知用一段信源序列最短碼長求權(quán)值進行Context編碼時，每個符號所需的比特數(shù)比用貝葉斯平均計算碼長求權(quán)值時編碼的比特數(shù)要少，編碼效果較好。權(quán)值更新頻率越快，每個像素點的碼長也越短，但是更新過于頻繁難免會消耗太多時間和計算量，造成浪費。

上述采用當前像素點的前50個像素的最短碼長來計算權(quán)值，接下來研究信源序列長度對實驗結(jié)果的影響，表2表示分別用不同長度的信源序列的最短碼長所對應(yīng)的那組權(quán)值進行加權(quán)編碼的結(jié)果：

4 結(jié)束語

由上訴實驗結(jié)果對比分析之后可以得出：用當前信源符號的前一段信源系列的最短碼長所對應(yīng)的那組權(quán)值進行Context加權(quán)編碼，其編碼長度比用貝葉斯平均計算權(quán)值進行加權(quán)的編碼長度短。權(quán)值的更新理論上越快越好，但是更新過快，計算過于頻繁會難免造成浪費，更新過慢可能會跳過最優(yōu)值。在已知信源序列的長度方面，采用長度為10的信源序列的最短碼長求權(quán)值，最終得到的馬長短且計算復雜度小。

參考文獻：

[1]Rissanen J.A universal data compression system[J].IEEE Transactions on information theory，1983（05）：656-664.

[2]Rissanen J.Universal coding，information，prediction，and estimation[J].Information Theory，IEEE Transactions on，1984（04）：629-636.

[3]Willems F M J，Shtarkov Y M，Tjalkens T J.The context-tree weighting method：Basic properties[J].Information Theory，IEEE Transactions on，1995（03）：653-664.

[4]Mahoney M V. Adaptive weighing of context models for lossless data compression[J]，2005.

[5]Cao M D，Dix T I，Allison L，et al.A simple statistical algorithm for biological sequence compression[C]//Data Compression Conference，2007.DCC'07.IEEE，2007：43-52.

[6]Pinho A J，Pratas D，F(xiàn)erreira P J S G.Bacteria DNA sequence compression using a mixture of finite-context models[C]//Statistical Signal Processing Workshop （SSP），2011 IEEE.IEEE，2011：125-128.

[7]Changxing Gou；Shi，Xin Ling；Li，Tian SongICMEME，A novel Multivariant Optimization Algorithm for Multimodal Optimization，ICMEME，2013：458-464.

作者簡介：羅迪（1989-），女，云南昆明人，通信與信息系統(tǒng)專業(yè)研究生，主要研究方向：圖像建模壓縮。

基金項目：云南大學研究生科研創(chuàng)新基金重點項目（項目編號：ynuy201383）。

作者單位：云南大學，昆明 650000