[發(fā)明專利]文件壓縮、解壓縮方法、裝置及壓縮文件搜索方法、裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 200910076795.3
• 申請(qǐng)日: 2009-01-21
• 公開(kāi)（公告）號(hào): CN101783788A
• 公開(kāi)（公告）日: 2010-07-21
• 發(fā)明（設(shè)計(jì)）人: 范昂
• 申請(qǐng)（專利權(quán)）人: 聯(lián)想（北京）有限公司
• 主分類號(hào): H04L29/06
• 分類號(hào): H04L29/06;H04L29/08
• 代理公司: 北京銀龍知識(shí)產(chǎn)權(quán)代理有限公司 11243
• 代理人: 許靜

技術(shù)領(lǐng)域

本發(fā)明涉及文件壓縮技術(shù)領(lǐng)域，特別是一種文件壓縮、解壓縮方法、裝置 及壓縮文件搜索方法、裝置。

背景技術(shù)

隨著計(jì)算機(jī)技術(shù)的不斷前進(jìn)，各種類型的數(shù)據(jù)文件越來(lái)越龐大，因此，導(dǎo) 致其存儲(chǔ)占用越來(lái)越多的存儲(chǔ)空間，而傳輸?shù)臅r(shí)候需要占用越來(lái)越多的帶寬。 因此，數(shù)據(jù)文件壓縮在計(jì)算機(jī)技術(shù)中顯得越來(lái)越重要。

現(xiàn)在，針對(duì)數(shù)據(jù)文件的壓縮分為有損壓縮和無(wú)損壓縮兩種，我們常用的 WinRAR、WinZip都是屬于無(wú)損壓縮，其基本原理都是一樣的，簡(jiǎn)單地說(shuō)也就 是把文件中的重復(fù)數(shù)據(jù)用更簡(jiǎn)潔的方法表示，也就是去除數(shù)據(jù)冗余。

現(xiàn)有的文本壓縮算法中，包括一類統(tǒng)計(jì)壓縮算法，如Huffman(哈夫曼) 算法等，說(shuō)明如下。

Huffman算法是一種基于統(tǒng)計(jì)的壓縮方法。它的本質(zhì)就是對(duì)文本文件中的 字符進(jìn)行重新編碼，對(duì)于使用頻率越高的字符，其編碼也越短。

經(jīng)過(guò)編碼后的文本文件，主要包含2個(gè)部分：Huffman碼表部分和壓縮內(nèi) 容部分。解壓縮的時(shí)候，先把Huffman碼表取出來(lái)，然后對(duì)壓縮內(nèi)容部分各個(gè) 字符進(jìn)行逐一解碼，形成源文件。

由此可見(jiàn)，使用Huffman算法的關(guān)鍵是形成Huffman碼表。這里就要用 到Huffman樹(shù)的數(shù)據(jù)結(jié)構(gòu)。當(dāng)把一棵Huffman樹(shù)生成后，碼表也就生成了。

下舉例說(shuō)明，假定我們的原始文本為″abcbbcccc″。

Huffman樹(shù)的生成包括如下步驟：

步驟A1，掃描源文件，對(duì)字符頻率進(jìn)行統(tǒng)計(jì)。

對(duì)于樣例，統(tǒng)計(jì)結(jié)果是：a出現(xiàn)1次，b出現(xiàn)3次，而c出現(xiàn)5次，記為 如圖1所示的隊(duì)列，a：1?b：3?c：5。

步驟A2，從上述隊(duì)列中取出頻率最低的2個(gè)節(jié)點(diǎn)，合并成一個(gè)頻率為2 節(jié)點(diǎn)頻率之和的樹(shù)枝節(jié)點(diǎn)X，加入到原隊(duì)列中，加入后，繼續(xù)保持隊(duì)列按頻率 升序排列；

對(duì)于樣例，得到如圖2所示的隊(duì)列；

步驟A3，重復(fù)步驟A2，直到隊(duì)列中只有一個(gè)節(jié)點(diǎn)。

步驟A4，通過(guò)上述步驟得到圖3所示的Huffman樹(shù)，葉子節(jié)點(diǎn)為字符， 而從樹(shù)根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑即為該字符的Huffman編碼。從一個(gè)節(jié)點(diǎn)導(dǎo)航 到其左孩子，該段路徑為0，導(dǎo)航到右孩子，該段路徑為1。

如圖3所示，可以知道a字符的編碼就是00，b字符的編碼為01，而c 字符的編碼為1，Huffman碼表生成后，原文本″abcbbcccc″就變成了 0001101011111的位串，按每個(gè)字符占用2個(gè)byte計(jì)算，大小由原來(lái)的18個(gè) 字節(jié)(9*2)，共144個(gè)bit，變成了13個(gè)bit，2個(gè)字節(jié)。達(dá)到了壓縮的目的。

解壓縮過(guò)程如下所述，首先根據(jù)Huffman碼表生成一棵Huffman樹(shù)，然 后，根據(jù)Huffman樹(shù)，對(duì)壓縮內(nèi)容進(jìn)行解壓縮。

比如如果壓縮內(nèi)容為位串0001101011111，結(jié)合圖3所示，那么從樹(shù)根節(jié) 點(diǎn)起，因?yàn)榈谝粋€(gè)bit為0，先轉(zhuǎn)向左子樹(shù)，第二個(gè)bit為0，再轉(zhuǎn)向左子樹(shù)， 到達(dá)葉子節(jié)點(diǎn)a，所以解碼出來(lái)的第一個(gè)字符就是a，每次解壓一個(gè)字符，都 從根節(jié)點(diǎn)起，根據(jù)bit流，向左或向右轉(zhuǎn)，直到到達(dá)葉子節(jié)點(diǎn)，也就是解壓出 來(lái)的字符，一直重復(fù)此過(guò)程，直到所有的字符都被解壓縮。

然而發(fā)明人在實(shí)現(xiàn)本發(fā)明的過(guò)程中，發(fā)現(xiàn)現(xiàn)有技術(shù)至少存在如下缺點(diǎn)：

現(xiàn)有技術(shù)中，針對(duì)每一個(gè)文本壓縮文檔都必須包括兩部分，一部分是用于 編碼的碼表，另一部分為文本壓縮后的編碼序列，由于這二者是在一個(gè)壓縮文 檔中，所以導(dǎo)致壓縮率不是很理想，因此有必要提出新的壓縮方案，以進(jìn)一步 提高文本壓縮算法的壓縮率。

發(fā)明內(nèi)容

本發(fā)明實(shí)施例的目的是提供一種文件壓縮、解壓縮方法、裝置及壓縮文件 搜索方法、裝置，以提高文本壓縮算法的壓縮率。

為了實(shí)現(xiàn)上述目的，本發(fā)明實(shí)施例提供了一種文件壓縮裝置，包括：

第一保存模塊，用于保存一編碼表，所述編碼表記錄了標(biāo)準(zhǔn)字串與編碼標(biāo) 識(shí)之間的對(duì)應(yīng)關(guān)系，每個(gè)所述標(biāo)準(zhǔn)字串具有唯一的所述編碼標(biāo)識(shí)；

第一獲取模塊，用于獲取待壓縮文件中的部分或全部文本，形成待編碼文 本；

第一分詞模塊，用于根據(jù)所述標(biāo)準(zhǔn)字串對(duì)所述待編碼文本進(jìn)行分詞，將所 述待編碼文本分解成至少一個(gè)待編碼字串；