一個適於二元搜尋的修飾算術編碼法

Abstract

資料壓縮的技術在檔案存放和分散系統方面有很重要的應用，除了增加傳輸速率外， 同時也加強了資料保密的特性。事實上，資料壓縮也是一種資料保密的方法，然而， 資料編碼的技術在達到資料保密的同時往往也破壞一些在應用上非常重要的資料檔案 原有的特性，因為編碼後將改變原來資料的面貌，如此一來，諸如資料搜尋的能力將 失去。而如果在須要受保護的資料檔案上搜尋資料，若事先須將整個檔案還原，則不 疑會增加資料曝光的機會，對於資料的性必大受影響。因此，如何設計一個可以在加 密後的資料檔案上直接搜尋資料的方法，似乎是一個非常值得研究的方法。 資料搜尋往往是一個系統最耗時間的部分，二元搜尋法是一個相當有效率的搜尋方法 ，對一個N 筆資料的循序檔案，它最多僅須要0 （log N）個比較。在本篇論文中， 我們將關注於對編碼後的資訊能有效率在被擷取回來。同時一些植基於二元搜尋的應 用能很容易的達到。我們的理念來自於１９８７年witten等所提之算術編碼的技術。 本文將簡單介紹算術編碼的觀念。之後，我們提出一個植基於算術編碼（Arithmetic Coding） 的修飾的編碼策略來針對數值資料檔案作編碼，同時，提出相對的解碼方 法。利用這個解碼的方式，我們可以很容易在編碼後的資料檔案上達到二元搜尋的目 的。