信息索引技術(shù)(編輯修改稿)
2025-03-18 18:23 本頁面
【文章內(nèi)容簡介】 l numbers and few larger numbers ? encode small numbers with small codes ? Document numbers are less predictable ? but differences between numbers in an ordered list are smaller and more predictable ? Delta encoding: ? encoding differences between document numbers (dgaps) Delta編碼 ? Inverted list (without counts) ? Differences between adjacent numbers ? Differences for a highfrequency word are easier to press, ., ? Differences for a lowfrequency word are large, ., 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 統(tǒng)計(jì)方法 ? 統(tǒng)計(jì)方法依賴于對每個(gè)符號在文本中出現(xiàn)的概率進(jìn)行估計(jì)，估計(jì)得越準(zhǔn)確，壓縮的效果就越好。 ? 文本中所有可能的符號的集合稱為字母表。對每個(gè)符號進(jìn)行概率估計(jì)的任務(wù)稱為建模。 ? 模型的本質(zhì)是建立信息庫中文檔的概率分布。一旦有了這些概率，符號就轉(zhuǎn)成二進(jìn)制數(shù)，這個(gè)過程稱為編碼。編碼和解碼都使用了同一個(gè)模型，解碼是編碼的逆過程。常見的統(tǒng)計(jì)編碼方案有兩種：霍夫曼編碼和算術(shù)編碼。 51 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 霍夫曼（ Huffman）編碼 ? 霍夫曼編碼的思想是為每一個(gè)不同的符號分配一個(gè)固定長度的位編碼。對給定的數(shù)據(jù)流，計(jì)算每個(gè)字符的出現(xiàn)頻率。根據(jù)頻率表，運(yùn)用霍夫曼算法可確定分配各字符的最小位數(shù)，然后給出一個(gè)最優(yōu)的編碼。 ? 給出現(xiàn)頻率較高的字符賦以較短編碼，而給出現(xiàn)頻率較低的字符賦以較長的編碼。每個(gè)數(shù)據(jù)的編碼各不相同。 ? 這些代碼都是二進(jìn)制碼，且碼的長度是可變的。分配的碼字存入編碼表中，從而實(shí)現(xiàn)壓縮。解壓的唯一性能夠得以保證是因?yàn)椴粫写a是另一個(gè)代碼的前綴。 52 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 霍夫曼編碼的例子 ? 我們假定字符集是 {A， B， C， D， E， F， G， H}，在給每個(gè)字符分配比特模式之前，我們給每個(gè)字符賦予一個(gè)出現(xiàn)頻率的權(quán)值。假定對應(yīng)的權(quán)值分別是 18和 40。然后我們建立字符樹，過程按照下面的步驟進(jìn)行。 ? ①統(tǒng)計(jì)頻率。將原始符號按照出現(xiàn)概率遞減 (或遞增 )的順序排列； ? ②將兩個(gè)最小出現(xiàn)概率進(jìn)行合并相加，得到的結(jié)果作為新符號的出現(xiàn)概率； 53 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 霍夫曼編碼的例子 ? ③重復(fù)進(jìn)行步驟①和②直到概率相加的結(jié)果等于 1為止； ? ④分配碼字。將形成的二叉樹左結(jié)點(diǎn)標(biāo) 0，右結(jié)點(diǎn)標(biāo) 1（或左結(jié)點(diǎn)標(biāo) 1，右結(jié)點(diǎn)標(biāo) 0），從根結(jié)點(diǎn)回溯到原始符號，記錄根結(jié)點(diǎn)到當(dāng)前符號之間的 0， 1序列，從而得到每個(gè)符號的編碼。 ? 因?yàn)槊總€(gè)編碼都是通過樹上從根開始的不同路徑得到的，所以沒有一個(gè)編碼是其他編碼的前綴。 54 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 霍夫曼編碼的例子 55 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 霍夫曼編碼的例子 56 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 霍夫曼編碼的例子 57 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 霍夫曼編碼的例子 編碼分配 字符 權(quán) 編碼 字符 權(quán) 編碼 A 4 00011 E 10 0000 B 5 0000 F 10 011 C 6 0101 G 18 001 D 7 0100 H 40 1 58 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 算術(shù)編碼 ? 算術(shù)編碼的基本原理是將編碼的消息表示成實(shí)數(shù) 0和 1之間的一個(gè)間隔（ Interval），消息越長，編碼表示它的間隔就越小，表示這一間隔所需的二進(jìn)制位就越多。 ? 算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在 0到 1之間。編碼過程中的間隔決定了符號壓縮后的輸出。 59 深圳大學(xué)未來媒體技術(shù)與計(jì)算研究所 算術(shù)編碼步驟 ? ①編碼器在開始時(shí)將當(dāng)前間隔 [ L， H）設(shè)置為 [0， 1）。 ? ②對每一事件，編碼器按步驟（ a）和（ b）進(jìn)行處理 ? （ a）編碼器將當(dāng)前間隔分為子間隔，每一個(gè)事件一個(gè)。 ? （ b）一個(gè)子間隔的大小與下一個(gè)將出現(xiàn)的事件的概率成比例，編碼器選擇子間隔對應(yīng)于下一個(gè)確切發(fā)生的事件相對應(yīng)，并使它成為新的當(dāng)前間隔。 ? ③最后
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1