非連續(xù)上下文建模及其在可執(zhí)行文件壓縮中的應(yīng)用.pdf

1、數(shù)據(jù)壓縮技術(shù)在過去的20年中迅速發(fā)展，并且廣泛地應(yīng)用于文本、語音、圖像、視頻以及可執(zhí)行文件等領(lǐng)域。數(shù)據(jù)壓縮的過程一般嚴(yán)格地分為兩步：建模過程和編碼過程。在編碼算法得到的碼長已經(jīng)十分接近香農(nóng)極限的今天，建模過程對于數(shù)據(jù)壓縮中效率的提升起到了決定性的作用。迄今為止研究人員對于上下文建模進(jìn)行了大量工作，并且提出了一系列經(jīng)典的建模方法。 可執(zhí)行文件壓縮作為數(shù)據(jù)壓縮的一個分支，隨著網(wǎng)絡(luò)設(shè)施和手持終端的普及，各種網(wǎng)絡(luò)程序分發(fā)和手持設(shè)備驅(qū)動程

2、序存儲等應(yīng)用要求的出現(xiàn)，逐漸顯現(xiàn)出其重要的意義。然而經(jīng)典的建模方法一般僅考慮連續(xù)的上下文模型，雖然在諸如文本壓縮中取得良好的效果，但在可執(zhí)行文件壓縮中則不盡如人意。 本文首先回顧了經(jīng)典的基于連續(xù)上下文建模的算法及其冗余的估計(jì)。在此基礎(chǔ)上，通過對于連續(xù)上下文限制條件的松弛，考慮采用已預(yù)測子序列中字符的任意組合而非之前的后綴來構(gòu)成非連續(xù)上下文，從而延伸出更廣泛的非連續(xù)上下文及其模型的定義，并就此討論基于非連續(xù)上下文的建模。對于非連續(xù)

3、上下文建模，討論的主要內(nèi)容包括三點(diǎn)：第一，通過引入模型樹來為非連續(xù)上下文建立一系列的上下文加權(quán)樹，從而可以得出基于非連續(xù)上下文模型的加權(quán)概率估計(jì)；其二，針對所得到的加權(quán)概率估計(jì)，討論它的模型估計(jì)冗余并與經(jīng)典的連續(xù)上下文建模方法中的相應(yīng)結(jié)果進(jìn)行比較，體現(xiàn)出其對具有非連續(xù)相關(guān)性數(shù)據(jù)估計(jì)時得優(yōu)勢；最后對于存在或不存在訓(xùn)練數(shù)據(jù)的情況，分別建立對于指定數(shù)據(jù)的上下文模型選擇的方法：當(dāng)不存在訓(xùn)練數(shù)據(jù)時可以通過本文提出的方法，用已預(yù)測數(shù)據(jù)快速近似判斷上

4、下文模型；而當(dāng)存在訓(xùn)練數(shù)據(jù)時可以依據(jù)最小描述長度準(zhǔn)則，通過貪心算法選定一系列最優(yōu)的模型。 對于可執(zhí)行文件壓縮，本文考慮同時采用連續(xù)上下文模型和非連續(xù)上下文模型來進(jìn)行估計(jì)，并由這些估計(jì)最終給出加權(quán)概率估計(jì)。在總結(jié)了可執(zhí)行文件，尤其是IA-32 指令集中的連續(xù)和非連續(xù)相關(guān)性后，將非連續(xù)建模方法結(jié)合其中的相關(guān)性應(yīng)用到IA-32 指令集中，并通過訓(xùn)練數(shù)據(jù)采用前述的貪心算法依據(jù)最小描述長度準(zhǔn)則選擇出一組最優(yōu)估計(jì)的上下文模型。在具體的實(shí)現(xiàn)中