基本介紹
- 中文名：區間編碼
- 外文名：Interval coding
- 工作途徑：去除數字信息中冗餘的算法
- 定義：將訊息符號編碼成一個數字
簡介,編碼方式,套用實例,與算術編碼的關係,XML動態區間編碼方法,
簡介
區間編碼是一種基於統計模型的無損壓縮算法。G.N.N.Martin在1979年的視頻和數據記錄會議（Video&Data Recording Conference）上提交了一篇論文：《區間編碼：去除數字信息中冗餘的算法》（Rangeencoding:analgorithm for removing redundancy from a digitised message.），第一次提出了區間編碼算法的思想。區間編碼的實現都是基於該論文中描述的方法。儘管從本質上說區間編碼與算術編碼是相同的，但是根據該論文的發表年代，通常認為區間編碼算法不受與算術編碼算法相關的專利約束。正是因為如此，越來越多的研究人員將目光轉向了區間編碼算法。
與經典的哈夫曼編碼相比，區間編碼可以獲得更高的壓縮率。因為傳統上的哈夫曼編碼是以位作為單位為符號分配編碼。即使一個符號具有非常高的頻度，哈夫曼編碼也只能為其分配一個位的編碼。這限制了壓縮率的進一步提升。與哈夫曼編碼不同，區間編碼將所有的數據映射到一個整數區間內。然後輸出一個屬於該區間的整數作為輸出編碼。這意味著區間編碼可以無限的接近數據的熵極限。另外，區間編碼由於其特點可以很好的與高階模型相配合。區間編碼已經開始大量的套用。
編碼方式
區間編碼概念上要把所有的訊息符號都編碼成一個數字，這與哈夫曼編碼為每個符號賦予一個位組合格式並且將所有這些位組合格式連線到一起不同。這樣區間編碼能夠實現比哈夫曼編碼一個符號一位這個上限還要高的壓縮率，並且它沒有哈夫曼編碼處理機率不為 2 的倍數時的效率問題。
區間編碼的核心概念是：對於給定的一個範圍足夠大的整數區間以及符號的機率估計，最初的區間很容易切分成與所表示的符號機率成比例的子區間。將當前區間切分成與下一個待編碼符號的機率對應的子區間，通過這種方法就可以對訊息中的每個符號進行編碼。解碼器必須與編碼器有同樣的機率估計，這種機率估計可以事先傳送過去、從已經傳送的數據導出或者作為壓縮器或者解壓器的一部分。
當所有的符號已經編碼完成後，僅僅用子區間就可以表示整個信息（當然我們假定解碼器提取了整個訊息之後通過某種方式得到）。單個的整數實際上已經足夠表示子區間，並且可能不需要傳輸整個的整數；如果有這樣一個數字序列，即每個整數的前綴都落在某個子區間，那么前綴本身就已經足夠標識字區間並且傳輸訊息。
套用實例
假設我們打算編碼訊息“AABA<EOM>”，其中 <EOM> 是訊息結束符。對於這個例子來說，假設編碼器知道我們打算用十進制數表示，也知道最初的區間是 [0, 100000) 並且頻率是 {A: .60; B: .20; <EOM>: .20}，第一個符號將 [0, 100000) 分成三個子區間：
A: [ 0, 60000)
B: [ 60000, 80000)
<EOM>: [ 80000, 100000)
由於第一符號是 A，所以最初的區間縮減為 [0, 60000)。第二個符號再次將這個區間分成三個子區間，跟在已經編碼的 'A' 後面表示：
AA: [ 0, 36000)
AB: [ 36000, 48000)
A<EOM>: [ 48000, 60000)
兩個符號編碼之後，區間變成 [000000, 036000)，第三個符號得到下面的結果：
AAA: [ 0, 21600)
AAB: [ 21600, 28800)
AA<EOM>: [ 28800, 36000)
這一次第二段表示我們要編碼的訊息，這樣區間就變成了 [21600, 28800)。在這種情況下看起來確定子區間變得困難了一些，實際上並非如此：我們可以直接用上限減去下限得到 7200，它最前面的 4320 區間是它的 .60，後面的 1440 區間表示隨後的 .20，剩餘的 1440 表示剩餘的 .20，然後加上下限得到區間：
AABA: [21600, 25920)
AABB: [25920, 27360)
AAB<EOM>: [27360, 28800)
最後，區間縮小到 [21600, 25920)，我們還有一個符號要進行編碼。與前面一樣我們區間進行切分得到：
AABAA: [21600, 24192)
AABAB: [24192, 25056)
AABA<EOM>: [25056, 25920)
由於 <EOM> 是最後一個符號，所以最後的區間就是 [25056, 25920)。因為以“251”開頭的五位整數都落在最後的區間內，這樣任何一個三位前綴在這個範圍的整數都能夠明確地傳達原始信息。存在八個這樣的前綴這個事實暗示效率仍然不是最高的，這是由於我們使用十進制而不是二進制整數引起的。
這樣看起來主要問題就是我們要選擇一個足夠大的區間，這樣不管需要編碼多少符號我們都有足夠大的區間使得子區間不為 0。但是，實際上這不是一個問題，因為編碼器不是從一個非常大的區間開始不斷減小這個區間，編碼器在任何時刻都只在一個更小的區間工作。在編碼一定熟練的數位之後，最左面的數位不再變化。在這個例子中編碼三個符號之後，我們就已經知道結果將以“2”開始。隨著更多數位從右側進來，左側的數位將不斷發送出去。
與算術編碼的關係
XML動態區間編碼方法
DCLS(dynamic containment labelingscheme).DCLS 將基於整數的編碼泛化到基於向量的編碼,擴展了傳統靜態區間編碼方法,有效避免了 XML 文檔更新時的重新編碼.不論文檔更新與否,DCLS 都顯示了良好的性能:DCLS 利用基於整數的靜態區間編碼方法進行初始編碼,在文檔不更新的環境下,具有較高的存儲效率和查詢性能;同時,DCLS 將整數視為特殊向量,不僅能夠支持文檔更新,而且更新效率高;特別是傾斜插入時,DCLS 可以避免編碼位長的快速增加.實驗結果表明,與已有的動態區間編碼方法相比,DCLS 具有更好的性能。
傳統的靜態區間編碼方法中,每個節點都被賦予一對整數,這對整數表達了節點覆蓋區域,進而支持了節點間位置關係和結構關係計算.但是使用靜態區間編碼不能有效處理 XML 文檔更新,一旦更新發生,整個樹需要重新編碼,系統代價高.為解決該問題,一些研究人員提出了動態區間編碼方法,包括浮點數區間 、CDBS以及QED等.相比較靜態區間編碼,這些方法支持文檔更新操作,但同時需要更多時空開銷,也降低了查詢性能.特別在文檔不更新或者少更新環境下,效率偏低。
靜態區間編碼和動態區間編碼各有利弊.當文檔不更新或者少更新時,靜態區間編碼無疑是更好的選擇;但當 XML 頻繁更新時,靜態區間編碼性能急劇下降,而動態區間編碼則顯示出優勢.通常情況下,人們很難事先判斷文檔更新頻率,進而不易選擇合適的編碼方法.這個意義下,開發出有效的動態編碼,滿足文檔更新與否情況下都具有良好性能顯得尤為重要.基於此,本文提出了新的動態區間編碼方法——DCLS(dynamic containmentlabeling scheme),DCLS 直接在靜態區間編碼基礎上進行擴展,可以有效地支持 XML 動態更新,同時又確保了文檔不更新環境下的良好性能。
