欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標(biāo)題: 字典算法 [打印本頁(yè)]

作者: 51黑tt 時(shí)間: 2016-3-5 17:36
標(biāo)題: 字典算法
最近寫(xiě)了一個(gè)文件壓縮程序，采用的是字典壓縮算法中的一種。
首先介紹一下我的字典壓縮算法：
字典壓縮算法就是用盡可以短(占用的二進(jìn)制bit 位)的標(biāo)記數(shù)據(jù)，代替盡可能長(zhǎng)的原始文件數(shù)據(jù),從而達(dá)到壓縮的效果。
總的來(lái)說(shuō),字典壓縮算法可以理解為一個(gè)壓縮機(jī)。一頭輸入(從源文件中讀取數(shù)據(jù)）要壓縮的數(shù)據(jù)，另一頭輸出(輸入到壓縮文件)或不輸出。
與赫夫曼算法比較可知采用服這種算法內(nèi)存中不須要滯留太多原始數(shù)據(jù)，這里說(shuō)的不須要滯留原始數(shù)據(jù)指的是不須要先將要壓縮的全部數(shù)據(jù)讀入內(nèi)存。因?yàn)檫@種算法不須要對(duì)整個(gè)文件數(shù)據(jù)進(jìn)行統(tǒng)計(jì)。
當(dāng)然完全不要滯留是不可能的。這里要滯留的僅僅是字典。

首先我們明白字典里裝的是什么    prefix (前綴) 和  suffix (后綴) . 例如:  index :1  content:  preffix : a suffix : b  ;
前綴可以是原始數(shù)據(jù)也可以是原始數(shù)據(jù)的標(biāo)記,我們知道對(duì)于任可數(shù)據(jù)都是由二進(jìn)制0或1組成的。所有我們?cè)谝淮巫x一個(gè)byte后得到的原始數(shù)據(jù)的范圍在0到255之間。之所以能夠達(dá)到壓縮的效果是因?yàn)?br /> 我們可以用0到255范圍外的數(shù)來(lái)代替很多個(gè)原始byte 原始數(shù)據(jù)重復(fù)數(shù)據(jù)越多壓縮效果就越好。這很好理解，然而關(guān)鍵就是怎么才能做到用0到255范圍外的數(shù)據(jù)代替原來(lái)的數(shù)據(jù)呢。所以這里我們就要擴(kuò)展
數(shù)據(jù)位了。也就是說(shuō)原來(lái)8個(gè)bit表示的數(shù)據(jù)現(xiàn)在我們要用9個(gè)bit來(lái)表示.最高位我們讓他為0，因?yàn)?位能表示的范圍達(dá)到了0到511。當(dāng)然我們也可能要擴(kuò)展到十二位來(lái)表示一個(gè)數(shù)據(jù)單元.這就取決于我們
的字典造多大。按理來(lái)說(shuō)字典構(gòu)造得越大達(dá)到的壓縮效果是越好。但是這樣程序的復(fù)雜度也將增加。我采用的字典最大index 為4095,達(dá)到最大index后重新構(gòu)造字典也就是十二個(gè)bit所能表示的范圍。
然而還有一個(gè)關(guān)鍵的問(wèn)題就是我們解壓的時(shí)候怎么知道我們現(xiàn)在一次要讀多少個(gè)bit位，字典index 達(dá)到最大值后，怎么知道要重構(gòu)字典呢。所以我們還得加上6個(gè)數(shù)據(jù)擴(kuò)展標(biāo)記位(bit位有變時(shí)標(biāo)記)，和一個(gè)字典重構(gòu)標(biāo)記。
達(dá)到擴(kuò)展數(shù)據(jù)位的方法就是位運(yùn)算。所以字典壓縮和解壓程序整個(gè)就是位運(yùn)算.
下面就說(shuō)壓縮算法:
先來(lái)一個(gè)例子，便于理解算法

input index prefix suffix string outPut
A                   A
B    263       A       B             AB       A

A    264       B       A          BA       B
B
A    265       263    A          ABA       263
B
A
B    266       265    B          ABAB    265
B    267       B       B          BB       B
B
A    268    267    A          BBA       267
B
A
B
A    269    266    A       ABABA    266
A    270    A       A          AA          A
C    271    A       C          AC          A
D    272    C       D          CD          C
A    273    D       A          DA          D
C
D    274    271    D       ACD       271
A
D    275    273    D       DAD       273
C    276    D       C       DC          D
A    277    C          A       CA          C
B
A
A    278    265    A       ABAA       265
A
B    279    270    B       AAB          270
A
B    280    264    B       BAB          264
                                                            B
原始數(shù)據(jù)占用bit位數(shù):
32*8=256
壓縮后數(shù)據(jù)占用bit位數(shù):
18*9=162
顯然 162<256 原始數(shù)據(jù)被壓縮了。
以C語(yǔ)言為例字典數(shù)據(jù)結(jié)構(gòu)為：
struct 標(biāo)號(hào)｛
            word    前綴；
            word    后綴；
｝;
結(jié)構(gòu)數(shù)組為：
標(biāo)號(hào)標(biāo)號(hào)組[4095]；
壓縮算法如下：

int 當(dāng)前最大標(biāo)號(hào)＝263；
word 前綴，后綴；
char輸入流［x］；
int 輸入序號(hào)＝0
然后，我們讀入第一個(gè)字符 A和第二個(gè)字符B 。
前綴＝輸入流［輸入序號(hào)］；
輸入序號(hào)＋＋；
從這里開(kāi)始，我們開(kāi)始?jí)嚎s過(guò)程，直到把數(shù)據(jù)處理玩：
int I=263;
for(輸入序號(hào) ; 輸入序號(hào)<X ; 輸入序號(hào)++){
            后綴＝輸入流［輸入序號(hào)］；
            //查找當(dāng)前串在表中的位置
            bool found=false;
            while ( I<當(dāng)前最大標(biāo)號(hào) ) {
                  if ( 前綴 != 標(biāo)號(hào)組［I］。前綴) ｛I＋＋；continue;｝
                  if( 后綴 != 標(biāo)號(hào)組［I］。后綴 ) ｛I＋＋；continue;｝

                  //找到了，就是這個(gè)串
                  found=true;
                  前綴＝I；    //把當(dāng)前串規(guī)約到標(biāo)號(hào)
                  I＋＋；
                  break;
            ｝
            if ( ! found ) {                   //沒(méi)找到，把這個(gè)串加到標(biāo)號(hào)組中
                  標(biāo)號(hào)組［當(dāng)前最大標(biāo)號(hào)］。前綴＝前綴；
                  標(biāo)號(hào)組［當(dāng)前最大標(biāo)號(hào)］。后綴＝后綴；
                  當(dāng)前最大標(biāo)號(hào)＋＋；

                  輸出前綴

                  前綴＝后綴；
                  if （當(dāng)前最大標(biāo)號(hào)> 4095）{          //已經(jīng)超過(guò)了最大的長(zhǎng)度
                        當(dāng)前最大標(biāo)號(hào)＝263；

                     輸出字典重構(gòu) 標(biāo)志；

                  ｝
                  I=263;
            ｝
｝

解壓是壓縮的逆過(guò)程:
如圖

input index prefix suffix stack outPut
A                      A
B    263       A       B                      A

263 264    B       A                         B

265 265    263    A          AB          AB
B       266    265    B          ABA       ABA
267 267    B       B                         B
266 268    267    A          BB          BB
A       269       266    A          ABAB    ABAB
A       270       A       A                         A
C       271       A       C                         A
D       272       C       D                         C
271 273    D       A                         D
273 274    271    D          AC          AC
D    275       273    D       DA          DA

C       276       D       C                         D
265 277    C       A                         C
270 278    265    A          ABA       ABA
264 279    270    B          AA          AA
B       280       264    B          BA          BA

                                                            B

解壓算法如下：
int 當(dāng)前標(biāo)號(hào)＝263；
棧 stack;
int  前綴，后綴；
int 輸入流［x］；
int 輸入序號(hào)＝0
前綴＝輸入流［輸入序號(hào)］；
輸入流序號(hào)++；

for(輸入序號(hào) ; 輸入序號(hào)<X ; 輸入序號(hào)++){


標(biāo)號(hào)組[當(dāng)前標(biāo)號(hào)]。前綴=前綴；

后綴=輸入流[輸入流序號(hào)]；

  //確定當(dāng)前后綴
if(當(dāng)前后綴<256){
標(biāo)號(hào)組[當(dāng)前標(biāo)號(hào)]。后綴=后綴；
當(dāng)前標(biāo)號(hào)++；
}else {

后綴=標(biāo)號(hào)組[后綴]。前綴；

while(后綴>255){

后綴=標(biāo)號(hào)組[后綴]。前綴；
}
//在字典中找到了原始數(shù)據(jù)前綴
標(biāo)號(hào)組[當(dāng)前標(biāo)號(hào)]。后綴=后綴；
當(dāng)前標(biāo)號(hào)++；
}
//確定前綴并輸出
if(前綴<256){

輸出 (char)前綴；
} else{ /*前綴不是原始數(shù)據(jù)*/

            push(標(biāo)號(hào)組[前綴].后綴);//字典中序號(hào)為當(dāng)前前綴的，結(jié)構(gòu)體后綴入棧
            if((標(biāo)號(hào)組[前綴].前綴)<256){ //字典中序號(hào)為當(dāng)前前綴的，結(jié)構(gòu)體前綴為原始數(shù)據(jù),則入棧
            push(標(biāo)號(hào)[前綴].前綴); // 入棧

            }else{
                     前綴=標(biāo)號(hào)組[前綴].前綴;
                  while(前綴>256){/*字典中序號(hào)為當(dāng)前前綴的，結(jié)構(gòu)體前綴為原始數(shù)據(jù)的標(biāo)記*/
                        push(標(biāo)號(hào)組[前綴].后綴）;//后綴入棧
                        前綴=標(biāo)號(hào)組[前綴].前綴;改變當(dāng)前前綴

                     }


            //字典中找到了序號(hào)為當(dāng)前前綴的，結(jié)構(gòu)體前綴為原始數(shù)據(jù)
                     push(前綴)//前綴入棧
            while(stack不空){

               輸出(pop());
               }
            }

         前綴=輸入流[輸入流序號(hào)]；
}

歡迎光臨 (http://www.raoushi.com/bbs/)