信息索引技術(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ù)與計算研究所 統(tǒng)計方法 ? 統(tǒng)計方法依賴于對每個符號在文本中出現(xiàn)的概率進行估計，估計得越準(zhǔn)確，壓縮的效果就越好。 ? 文本中所有可能的符號的集合稱為字母表。對每個符號進行概率估計的任務(wù)稱為建模。 ? 模型的本質(zhì)是建立信息庫中文檔的概率分布。一旦有了這些概率，符號就轉(zhuǎn)成二進制數(shù)，這個過程稱為編碼。編碼和解碼都使用了同一個模型，解碼是編碼的逆過程。常見的統(tǒng)計編碼方案有兩種：霍夫曼編碼和算術(shù)編碼。 51 深圳大學(xué)未來媒體技術(shù)與計算研究所 霍夫曼（ Huffman）編碼 ? 霍夫曼編碼的思想是為每一個不同的符號分配一個固定長度的位編碼。對給定的數(shù)據(jù)流，計算每個字符的出現(xiàn)頻率。根據(jù)頻率表，運用霍夫曼算法可確定分配各字符的最小位數(shù)，然后給出一個最優(yōu)的編碼。 ? 給出現(xiàn)頻率較高的字符賦以較短編碼，而給出現(xiàn)頻率較低的字符賦以較長的編碼。每個數(shù)據(jù)的編碼各不相同。 ? 這些代碼都是二進制碼，且碼的長度是可變的。分配的碼字存入編碼表中，從而實現(xiàn)壓縮。解壓的唯一性能夠得以保證是因為不會有代碼是另一個代碼的前綴。 52 深圳大學(xué)未來媒體技術(shù)與計算研究所 霍夫曼編碼的例子 ? 我們假定字符集是 {A， B， C， D， E， F， G， H}，在給每個字符分配比特模式之前，我們給每個字符賦予一個出現(xiàn)頻率的權(quán)值。假定對應(yīng)的權(quán)值分別是 18和 40。然后我們建立字符樹，過程按照下面的步驟進行。 ? ①統(tǒng)計頻率。將原始符號按照出現(xiàn)概率遞減 (或遞增 )的順序排列； ? ②將兩個最小出現(xiàn)概率進行合并相加，得到的結(jié)果作為新符號的出現(xiàn)概率； 53 深圳大學(xué)未來媒體技術(shù)與計算研究所 霍夫曼編碼的例子 ? ③重復(fù)進行步驟①和②直到概率相加的結(jié)果等于 1為止； ? ④分配碼字。將形成的二叉樹左結(jié)點標(biāo) 0，右結(jié)點標(biāo) 1（或左結(jié)點標(biāo) 1，右結(jié)點標(biāo) 0），從根結(jié)點回溯到原始符號，記錄根結(jié)點到當(dāng)前符號之間的 0， 1序列，從而得到每個符號的編碼。 ? 因為每個編碼都是通過樹上從根開始的不同路徑得到的，所以沒有一個編碼是其他編碼的前綴。 54 深圳大學(xué)未來媒體技術(shù)與計算研究所 霍夫曼編碼的例子 55 深圳大學(xué)未來媒體技術(shù)與計算研究所 霍夫曼編碼的例子 56 深圳大學(xué)未來媒體技術(shù)與計算研究所 霍夫曼編碼的例子 57 深圳大學(xué)未來媒體技術(shù)與計算研究所 霍夫曼編碼的例子 編碼分配 字符 權(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ù)與計算研究所 算術(shù)編碼 ? 算術(shù)編碼的基本原理是將編碼的消息表示成實數(shù) 0和 1之間的一個間隔（ Interval），消息越長，編碼表示它的間隔就越小，表示這一間隔所需的二進制位就越多。 ? 算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在 0到 1之間。編碼過程中的間隔決定了符號壓縮后的輸出。 59 深圳大學(xué)未來媒體技術(shù)與計算研究所 算術(shù)編碼步驟 ? ①編碼器在開始時將當(dāng)前間隔 [ L， H）設(shè)置為 [0， 1）。 ? ②對每一事件，編碼器按步驟（ a）和（ b）進行處理 ? （ a）編碼器將當(dāng)前間隔分為子間隔，每一個事件一個。 ? （ b）一個子間隔的大小與下一個將出現(xiàn)的事件的概率成比例，編碼器選擇子間隔對應(yīng)于下一個確切發(fā)生的事件相對應(yīng)，并使它成為新的當(dāng)前間隔。 ? ③最后
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1