第2章-2數據存儲及數據壓縮

西安交通大學衛(wèi)顏俊2013.9大學計算機基礎1第2章信息的表示與存儲2.2信息的存儲2.3數據壓縮本章主要內容信息及其表示√信息的存儲數據壓縮2本講主要內容布爾運算邏輯門電路存儲器信息熵基本壓縮方法多媒體的壓縮3信息的存儲51.布爾運算取值：0,1運算符：非~、與&、或|、異或^運算規(guī)則表：

NOTANDORXOR非與或異或6位向量布爾變量p,q取值∈{0,1}邏輯變量，P,Q，取值∈{真,假}，或{true,false}布爾運算可以作用于單獨的位，還能作用于位向量位向量：長度為w的由0，1組成的序列。位向量的布爾運算:位向量對應分量的布爾運算【課堂練習2-34】已知位向量a=01101001和b=01010101，計算:

~a，~b，a&b，a︱b，a^b。~a=10010110~b=10101010a=01101001&b=0101010101000001a=01101001|b=0101010101111101a=01101001^b=01010101001111007【課堂練習2-34】已知位向量a=01101001和b=01010101，計算:

~a，~b，a&b，a︱b，a^b。~a=10010110~b=10101010a=01101001&b=0101010101000001a=01101001|b=0101010101111101a=01101001^b=01010101001111008布爾運算的應用(1)布爾運算表示有限集合，如：a=[01101001]表示集合A=｛0，3，5，6｝b=[01010101]表示集合B=｛0，2，4，6｝位向量的a,b的布爾運算|，&，~對應集合的并交補(2)配色長度為3的0，1序列表示一種紅綠藍三原色構成的顏色如，[100]表示紅,[010]表示綠,[001]表示藍。[100]|[010]=[110]=>紅+綠=黃相加混色[110]&[011](青)=[010]=>綠色相減混色~[100]=[011](青)，補色(3)文獻檢索表達檢索意愿文獻的關鍵詞特征筆記本電腦；電腦(筆記本)筆記本-(電腦)布爾代數設{0，1}w表示長度為w由0，1組成的串的集合aw表示由w個a組成的串，那么，<{0,1}w,|,&,~,0w,1w>構成布爾代數。不同的w就是不同的布爾代數102.門電路和觸發(fā)器門？一種物理器件，輸入布爾值，輸出為某種布爾運算的結果。門電路？實現邏輯運算的電路。門電路可以通過多種技術制造出來，如齒輪、繼電器、光學器件、半導體器件等。門電路是信息存儲、處理部件的基本構件。計算機中，門電路通過微電子集成電路實現。11基本的門電路-與門12基本的門電路-或門、非門或門非門13基本的門電路-異或門14基本門電路的國外符號

由門電路組成觸發(fā)器15觸發(fā)器一個可以產生0或1輸出值的電路，它會一直保持輸出不變，直到外部送來一個觸發(fā)脈沖使其改變成另一個值。16觸發(fā)器的另外方案或門、非門組成的觸發(fā)器觸發(fā)器的電路圖17觸發(fā)器的應用觸發(fā)器、門電路組成更復雜的電路，實現更高級的功能.18演示3存儲器的結構存儲設備是用于儲存信息的設備或設備。通常是將信息數字化后再以利用電、磁或光學等方式的媒體加以存儲。常見的存儲設備有：利用電能方式存儲信息的設備如：如各式隨機存取存儲器（RAM）、只讀存儲器（ROM）等利用磁能方式存儲信息的設備如：硬盤、軟盤、磁帶、磁芯存儲器、磁泡存儲器利用光學方式存儲信息的設備如：CD或DVD利用磁光方式存儲信息的設備如：MO（磁光盤）利用其他實體物如紙卡、紙帶等存儲信息的設備如：打孔卡、打孔帶等19202122233存儲器的結構存儲器：主存、內存外存內存使用了大量的半導體電路（如觸發(fā)器）來構造存儲器，每一個單元電路能夠存儲一個二進制位。這種存儲器稱為主存儲器（mainmemory）或內部存儲器，簡稱主存或內存。每8位組成一個存儲單元，8位稱為一個字節(jié)。76543210最高有效位（第7位）最低有效位（第0位）24若干存儲單元集成到一起組成內存芯片若干內存芯片集成到一個小的板子上做成內存條內存條插到主機板中，稱為計算機的內存。觸發(fā)器→儲存單元→存儲芯片→內存條2526計算機的內存由成千上萬的存儲單元組成。一個存儲單元可以存放？一組有意義的信息需要多少存儲單元？如何存放?如何在內存中有效地存取數據？【思考】要到某個住宅小區(qū)找人，需要知道什么信息才能找到他？從0開始，按順序每個存儲單元有一個編號，稱為地址（內存地址）地址由CPU產生，地址譯碼器確定選擇的存取單元數據線上讀出/寫入數據27內存芯片的結構示意總線地址總線數據總線控制總線地址總線的條數，決定能訪問的內存數量28主存儲器的邏輯視圖與編址29連續(xù)存儲的數據的地址=起始地址+偏移地址隨機存取inta[10];表示能存放10個整數的數組內存中分配4*10=40個字節(jié)的存儲空間a[0]表示第1個元素，a[i]表示第i+1元素int*p=a;p表示a的地址（第1個元素的地址）p+5表示第6個元素的地址30主存的讀寫特點“拷貝”讀，“破壞”寫存儲器存取信息和倉庫存取貨物這兩件事情，抽象后可以認為都是存取某種對象。討論二者之間的區(qū)別。【課堂練習2-39】已知5號存儲單元中存放了數值8。以下兩個操作有什么關系？（相同之處？不同之處？）將數值5寫入6號存儲單元；將5號存儲單元的內容移到6號存儲單元?！半S機”讀寫主存儲器對每一個存儲單元編址，所以每一個存儲單元都可以獨立存取。為了反映這種能力，主存儲器經常被稱為隨機存取存儲器（RandomAccessMemory，RAM）。31內存的類型只讀存儲器只讀存儲器ROM（ReadOnlyMemory）ROM的特點計算機中為什么需要ROM？常見ROM的種類EPROMEEPROMFLASHROM計算機中的ROMBIOS嵌入式系統中的程序存儲器USB移動存儲器（U盤）SSD（固態(tài)硬盤）RAM(RandomAccessMemory)32常見DRAM種類目前微機中常用的DRAM都屬于SDRAM（SynchronousDynamicRandomAccessMemory，同步動態(tài)隨機存儲器）。名字中的“同步”是指SDRAM能與CPU以相同的速度同步工作。SDRAM又分為DDR2SDRAM、DDR3SDRAM、DDR4SDRAM等。DDR（DoubleDataRate）即雙倍數據速率，意思是每個存儲周期傳輸兩或更多次的數據。DDR2的傳輸帶寬（每秒傳輸數據的字節(jié)數）為640MB/s，DDR3的傳輸帶寬為1.28GB/s，而DDR4可達到2.56GB/s。DRAM在計算機中的應用主存儲器顯示存儲器信息的壓縮34本節(jié)內容基本壓縮方法游程編碼huffman編碼字典編碼圖像和音視頻的壓縮35引言什么是數據壓縮？為什么要壓縮？數據壓縮的可能性？信息以二進制數或二進制編碼的形式在存儲器中存放然而，存儲器是非常有限的能否用僅可能少的空間，存放更多的信息？這就是數據的壓縮問題數據壓縮的本質是重新編碼，使表示的信息的意義不變而使數據量減少36壓縮的必要性數字電話采樣頻率8kHz,樣本精度8位，數據率64kb/s數據率——比特率、數碼率、碼率、速率、數據率一小時的數據量64/8*3600=28800kB=28MB數字圖像3072*2304*3=20.25MB廣播級彩色數字電視4:2:2分量采樣，采樣頻率13.5/6.75/6.57Hz,每樣本精度8位，數據率I=(13.5+6.57+6.57)*8=216Mb/s一小時約95GB的數據量高清數字電視碼率=1280*720*60*3*8=1327Mb/s衛(wèi)星云圖、遙感數據…37壓縮的可能性——信息冗余空間冗余規(guī)則物體和規(guī)則背景的表面物理特性都具有相關性時間冗余序列圖像(如電視圖像和運動圖像)和語音數據的前后有著很強的相關性38AA結構冗余圖像中紋理結構的相似性39信息熵冗余數據攜帶的信息量少于數據本身視覺冗余（感官冗余）：由人的視覺特性所產生的冗余，人的視覺系統一般的分辨能力約為26灰度等級，而圖像量化一般采用28灰度等級，這樣的冗余就稱為視覺冗余知識冗余圖像的記錄方式與人對該圖像的知識之間的差異而產生。例如人臉的圖像就有固定的結構，鼻子位于臉的中線上，上方是眼睛，下方是嘴等。我們可以構造其基本模型，并創(chuàng)建對應各種特征的圖像庫，進而圖像的存儲只需要保存一些特征參數，就可以大大減少數據量4041數據壓縮對猜數游戲0000100400111015010211060113111742

對于乘何種交通工具來到學?？赡苄裕夯疖?0%，汽車10，自行車5，飛機5，船0%

0123火車0自行車110汽車10飛機111傳輸100次，告訴100人到校的交通方式火車的數據量80位，汽車20位，自行車15，飛機15，共130位，平均1.3個位。1.3稱為平均編碼長度43平均編碼長度平均編碼長度=(80*1+10*2+5*3+5*3)/100=0.8*1+0.1*2+0.05*3+0.05*3=1.344信息熵理論上，計算平均編碼長度的公式叫熵對交通工具問題：4550萬字的中文書信息量有多少了？信息量500000*(-log2(1/500000))≈9465784（bit）

≈1183223.0（Byte）按前面的兩字節(jié)編碼，50萬漢字，數據量100萬字節(jié)，約1M(1000000Byte)常用7000個漢字。假如每個字出現的概率相等，那么需要多少比特表示一個漢字？（提示212＜7000＜213）取整13位46如果用13位編碼每個漢字，50萬字的書的數據量為500000*13/8=812500Byte實際上，漢字的使用不是等概率的。經過統計，使用概率最大的前10%的漢字使用率占95%以上?？紤]每個漢字的出現概率以及上下文相關性，漢字的信息熵只有5比特左右。由此，50萬字的中文書的信息量大約是250萬比特，或313K字節(jié)。這兩個數量的差距，在信息論中稱作冗余度（redundancy)。冗余度越大的信息，通過壓縮能夠獲得好處就越大（減小存儲空間和傳輸時間）。47信息熵的意義信息熵給出了表示信息的最小平均比特數當一種信息出現概率更高的時候，表明它被傳播得更廣泛，或者說，被引用的程度更高。從信息傳播的角度來看，信息熵可以表示信息的價值。信息熵也可以說是系統有序化程度的一個度量。一個系統越是有序，信息熵就越低；一個系統越是混亂，信息熵就越高。48基本壓縮方法數據壓縮方案有兩大類無損壓縮（losslesscompress）有損壓縮（lossycompress）無損壓縮壓縮過程中不丟失信息壓縮率低常用于文字信息、程序的壓縮有損壓縮壓縮過程中丟失部分信息壓縮率高常用于圖像、聲音、視頻的壓縮49(1)行程長度編碼(run-lengthencoding)【課堂練習】有字符串“aaaaaabbccccdddffffff”,請用另一種表示方法,使數據量減少,但能準確還原原來的信息。？行程編碼，又稱游程編碼，適合于被壓縮數據中重復信息較多的情況。是一種無損壓縮方法壓縮方法：將一組相同的數據序列轉換成一個二元組，指出重復的成分以及在其序列中出現的次數。形式如（x，n）。50(2)Huffman編碼【例】字符串“accacccbcc”中，a出現的頻率為0.2，b出現的頻率為0.1，c出現的頻率為0.7。計算頻率相關編碼方法的壓縮率。解：按照一般的編碼方法，三個字符需要2位二進制編碼，則該字符串需要用20位二進制編碼來表示。采用頻率相關編碼，可將c編碼為0、a編碼為10、b編碼為11，這樣該字符串只需要用13位二進制編碼來表示。壓縮比=13/20=0.65這意味著可節(jié)省35%的數據存儲空間或節(jié)省35%的數據傳輸時間。51huffman編碼算法字符串“accacccbcc”中，a出現的頻率為0.2，b出現的頻率為0.1，c出現的頻率為0.7。用霍夫曼算法對a、b、c進行編碼。c0.7a0.2b0.11初始態(tài)c0.72排序a0.2b0.1c0.73合并排序a0.2b0.10.3c0.74合并排序a0.2b0.10.31c0.75標注a0.2b0.10.31最優(yōu)二叉樹0101霍夫曼編碼：c：0a：10b：11最優(yōu)二叉樹52最優(yōu)二叉樹樹二叉樹有兩個葉子節(jié)點帶權二叉樹節(jié)點上帶有權值的二叉樹帶權路徑長度最優(yōu)二叉樹給定n個權值（在此是指符號出現的概率）作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹53huffman編碼編碼思想：經常出現的編碼較短，不常出現的編碼較長特點變長編碼需要知道被壓縮信息碼元出現概率是一種頻率相關的編碼方法適用于文本信息的壓縮無損壓縮傳輸壓縮數據時需要帶編碼表54(3)字典編碼壓縮

(dictionaryencoding)【課堂練習2-44】下面是一首缺詞少字的歌詞，試著對它解碼以恢復它的原貌。（提示：從頭開始依照空白處箭頭的指示，復制所指示的內容來補齊缺少的字詞）注意：請不要指望計算機也熟悉這首歌詞，能夠倒背如流！55字典編碼壓縮上述練習中涉及的壓縮技術稱為字典編碼（dictionaryencoding）。壓縮后的信息是字典中單詞的索引號。字典編碼的一個實例就是字處理系統。在字處理系統中。為了拼寫檢查，已經包含了經過精心設計的字典。每個單詞可以編碼成字典的一個索引號。例如，一個字處理系統中的字典包括了50000個條目，那么一個條目就可以用0-49999中的一個整數來標識。也就是說，字典中的一個詞條用16位二進制就可識別。相反，如果一個單詞包括6個字母，使用8位ASCII則需要48位，使用Unicode則需要96位。針對這個案例計算一下（假定原始文本采用Unicode編碼）： 1）如果有5000個字典條目出現在原始文本中，按每個單詞包含6個字母計算，它

共有多少字節(jié)？ 2）用字典編碼方法壓縮后的文本包含多少字節(jié)？ 3）壓縮后比壓縮前縮小了多少？56字典編碼壓縮【課堂練習2-45】下面是一首外國詩歌，其中包含了許多重復的字母組合。TheRainPitterpatterPitterpatterListentotherainPitterpatterPitterpatterOnthewindowpane將此詩歌按照圖示方法壓縮。57現在歸納一下字典編碼壓縮的思想在文本中查找字母組合，如果這個字母組合曾經出現過（意味著可以被索引），它將被移除并用指針/索引（就像上面練習中畫出的箭頭和方格）代替。在計算機上的實現？所畫的指示箭頭和需要參照的字符串用當前位置與參照字符串的距離和拷貝字符數來表示。例如，Pitterpatter壓縮后的結果為Pitterpa（7，4）。其中，7表示從當前位置倒數7個字符（包括空格），4表示把從該處開始的4個字符復制到當前位置。58字典編碼壓縮還可以如何實現？在實際應用中，為了加快速度、提高壓縮比，往往采用的并不是文本自參照方法，而是需要使用一個字典來作為文本中出現的字母或單詞的參照。文本將被編碼為一個包含了許多字典索引號的數字串。同時，字典也是隨著編碼過程的進展而不斷擴充的（稱為自適應字典編碼）。初始字典僅包含基本字符和單詞，隨著壓縮過程的進展，信息中包含的更長的單詞會逐漸被加入字典，而新加入的單詞又可用在其后的編碼過程中。59字典編碼壓縮【例2-14】考慮壓縮文本：xyxxyxxyxxyx。首先要有一個包含3個條目的字典：第一個條目是x，第二個是y，第三個是空格。分別記為（1，x），（2，y）和（3，“”）。文本中的第1個單詞xyx編碼為121，這3個數字指出了文本中要參照的字典條目索引號。下一個字符是空格，所以編碼擴展為1213.空格意味前3個字符形成了一個單詞，于是將xyx添加到字典中作為第四個條目。字典變成了（1，x），（2，y），（3，“”）和（4，xyx）。以此類推，整段文本最終編碼為121343434。解壓縮時，仍用原始的3條目字典，首先將起始的1213解碼為xyx和一個空格。因為xyx形成了一個單詞，就將其添加到字典中作為第4個條目。接著發(fā)現后面的索引4是指字典中的第4個條目，于是將其解碼為xyx，由此得到12134表示的是xyxxyx。按這種方法，最終將121343434解碼為原始文本：xyxxyxxyxxyx。6061字典編碼壓縮的應用LZW（Lempel-Ziv-Welsh）壓縮——也稱LZ壓縮；RAR壓縮和ZIP壓縮格式的文件；圖像文件，如GIF和PNG格式的文件。62差分編碼壓縮(differentialencoding)2023/2/363預測編碼數字壓縮技術工作原理：把圖像按行掃描進行編碼。在掃到某一像素前，可以用此像素前面的一些像素值進行預測估計，然后與實際像素值進行比較。即用實際值減去預測估值得到差值信號，再將此差值信號量化、編碼和傳輸。在接收端用量化的差值信號重建圖像信號。2023/2/364預測編碼數字壓縮技術原理圖如下：量化器編碼器信道∑F(x,y)+-DQ(x,y)D(x,y)F’(x,y)解碼器∑F(x,y)+-DQ(x,y)F’(x,y)信道編碼系統解碼系統65特點無損壓縮有損壓縮，有不精確的量化器存在,預測編碼應用適用于動畫或視頻的壓縮動畫或視頻中的連續(xù)圖像幀（看成是很多連續(xù)的數據塊）之間的差別很小，幀與幀之間有很多重復的信息。因此只需記錄連續(xù)數據塊之間的差別即可，而無需記錄整個數據塊。66圖像和音視頻的壓縮1.圖像壓縮？【例2-15】再一次請出“a”的位圖。假定編碼中白色像素個數在前。在“a”的位圖中，第一行包含3個白色像素，接著是4個黑色像素，然后又是3個白色像素。于是這一行被編碼為（3，4，3）。其他行也用此方法進行編碼，……順利完成，似乎沒有什么問題。但是認真考慮第八行的編碼（注意它是以1開頭的）：編碼為（2，5，1，2）會出現什么問題？如何解決？用0表示開頭沒有白色像素！現在第八行的編碼是什么？進一步思考：如果同顏色像素的個數超出了行程長度的上限，如何解決？67其他的圖像壓縮方法除了RLE壓縮外，其他的圖像壓縮方法還包括GIF（用于簡單圖片）和JPEG（用于照片）等。GIF（GraphicInterchangeFormat）是一個典型的字典編碼壓縮技術。它的基本思想是，首先將像素色彩數減少到256個，并將色彩的編碼存儲在一個稱為調色板的色彩字典中。圖像中的每個像