數(shù)據(jù)結(jié)構(gòu)(本)課程輔導(dǎo)與練習(xí)第6章(編輯修改稿)
2025-07-14 06:43 本頁面
【文章內(nèi)容簡介】 。即將文件中的每個字符均轉(zhuǎn)換為一個惟一的二進(jìn)制位串。 數(shù)據(jù)解壓過程稱為解碼。即將二進(jìn)制位串轉(zhuǎn)換為對應(yīng)的字符。2．等長編碼方案和變長編碼方案 給定的字符集C，可能存在多種編碼方案。（1） 等長編碼方案 等長編碼方案將給定字符集C中每個字符的碼長定為[lg|C|]，|C|表示字符集的大小?！纠吭O(shè)待壓縮的數(shù)據(jù)文件共有100000個字符，這些字符均取自字符集C={a，b，c，d，e，f}，等長編碼需要三位二進(jìn)制數(shù)字來表示六個字符，因此，整個文件的編碼長度為300000位。（2）變長編碼方案 變長編碼方案將頻度高的字符編碼設(shè)置短，將頻度低的字符編碼設(shè)置較長。【例】設(shè)待壓縮的數(shù)據(jù)文件共有100000個字符，這些字符均取自字符集C={a，b，c，d，e，f}，其中每個字符在文件中出現(xiàn)的次數(shù)(簡稱頻度)見表。 字符編碼問題 字符 a b c d e f 頻度（單位：千次） 45 13 12 16 9 5 定長編碼 000 001 010 011 100 101 變長編碼 0 101 100 111 1101 1100 根據(jù)計算公式： (45*1+13*3+12*3+16*3+9*4+584)*1000=224000整個文件被編碼為224000位，比定長編碼方式節(jié)約了約25％的存儲空間。 注意： 變長編碼可能使解碼產(chǎn)生二義性。產(chǎn)生該問題的原因是某些字符的編碼可能與其他字符的編碼開始部分(稱為前綴)相同。 【例】設(shè)E、T、W分別編碼為00、00001，則解碼時無法確定信息串0001是ET還是W。3． 前綴碼方案 對字符集進(jìn)行編碼時，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編碼稱為前綴(編)碼。 注意： 等長編碼是前綴碼4．最優(yōu)前綴碼平均碼長或文件總長最小的前綴編碼稱為最優(yōu)的前綴碼。最優(yōu)的前綴碼對文件的壓縮效果亦最佳。 其中
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1