[發(fā)明專(zhuān)利]一種基于語(yǔ)義壓縮的文檔存儲(chǔ)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210329421.X
• 申請(qǐng)日: 2012-09-08
• 公開(kāi)（公告）號(hào): CN102867048A
• 公開(kāi)（公告）日: 2013-01-09
• 發(fā)明（設(shè)計(jì)）人: 曾嘉;曹小琴;嚴(yán)建峰;劉曉升
• 申請(qǐng)（專(zhuān)利權(quán)）人: 蘇州大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 蘇州創(chuàng)元專(zhuān)利商標(biāo)事務(wù)所有限公司 32103
• 代理人: 陶海鋒

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

本發(fā)明涉及一種計(jì)算機(jī)文檔存儲(chǔ)方法，具體涉及一種基于語(yǔ)義壓縮的文檔存儲(chǔ)方法。

背景技術(shù)

隨著計(jì)算機(jī)技術(shù)的發(fā)展和網(wǎng)絡(luò)技術(shù)的廣泛應(yīng)用，由計(jì)算機(jī)處理的文檔數(shù)量急劇增加，信息的存儲(chǔ)、檢索和傳送對(duì)存儲(chǔ)設(shè)備的容量、處理系統(tǒng)的內(nèi)存、傳輸網(wǎng)絡(luò)的帶寬等提出了越來(lái)越高的要求。如果能夠?qū)Υ鎯?chǔ)的文件進(jìn)行有效的壓縮，對(duì)于減少存儲(chǔ)需求，加快數(shù)據(jù)檢索將起到重要的作用。

現(xiàn)有技術(shù)中，對(duì)于文檔的壓縮存儲(chǔ)的研究，基本上都局限于文檔的無(wú)損壓縮技術(shù)，通過(guò)以二進(jìn)制方式對(duì)計(jì)算機(jī)文檔進(jìn)行壓縮，減小存儲(chǔ)中占用的冗余空間，從而減小文檔對(duì)存儲(chǔ)空間的要求。這種方式能夠減小文檔存儲(chǔ)空間，但是由于需要保留全部的文檔信息，存儲(chǔ)空間難以進(jìn)一步縮小。

文檔的語(yǔ)義壓縮是將文檔用主題進(jìn)行描述，通過(guò)主題來(lái)反映文檔，確定文檔的類(lèi)別。主題信息遠(yuǎn)遠(yuǎn)小于文檔信息，但是主題信息能充分體現(xiàn)文檔信息。由此，用少量主題信息就能刻畫(huà)文檔信息，從而實(shí)現(xiàn)文檔的語(yǔ)義壓縮。語(yǔ)義壓縮屬于有損壓縮，其壓縮比跟選取的主題數(shù)目相關(guān)。主題數(shù)目越大，壓縮精度越高，但是壓縮比低（壓縮比定義為壓縮前所占用的存儲(chǔ)空間除以壓縮后所占用的存儲(chǔ)空間）。反之，主題數(shù)目越小，壓縮精度低，但是壓縮比高。通常，主題數(shù)目根據(jù)實(shí)際需求進(jìn)行設(shè)定。

文檔的語(yǔ)義壓縮的實(shí)現(xiàn)原理是：把文檔表示為單詞的集合，主題表示成單詞的分布，某個(gè)主題用該主題中出現(xiàn)頻率最高的若干單詞來(lái)表示；根據(jù)文檔和單詞的關(guān)系以及主題和單詞的關(guān)系，把文檔變?yōu)槿舾蓚€(gè)主題的多項(xiàng)分布，即某幾個(gè)主題組成了一個(gè)文檔，一個(gè)文檔用幾個(gè)主題來(lái)描述。

文檔的信息的表示用W×D矩陣進(jìn)行表示，W是語(yǔ)料庫(kù)的單詞表，D是文檔的集合，W×D矩陣記錄了單詞表中的單詞在文檔中出現(xiàn)的次數(shù)，如表1所示，W₀D₀對(duì)應(yīng)的元素值為3，表示單詞表中索引號(hào)為0的單詞W₀在第D₀篇文檔中出現(xiàn)3次。

表1??W×D矩陣

。

?通過(guò)對(duì)文檔信息的迭代處理，得到主題在單詞表的分布phi矩陣和文檔在主題的分布theta矩陣，如表2和表3所示。當(dāng)文檔數(shù)量比較大時(shí)，如幾千萬(wàn)篇文檔，W×D矩陣是一個(gè)極其龐大的矩陣，將W×D矩陣分解為phi矩陣和theta矩陣，就可以實(shí)現(xiàn)語(yǔ)義信息的壓縮，方便存儲(chǔ)，為后續(xù)的文檔分析、數(shù)據(jù)挖掘、信息檢索等操作提供方便。

表2??主題在單詞表的分布?phi矩陣

。

表3??文檔在主題的分布theta矩陣

。

目前，常用的語(yǔ)義壓縮方法有吉布斯采樣（Gibbs?Sampling?or?GS）和變分貝葉斯（Variational?Bayes?or?VB）兩種方法。

吉布斯采樣方法對(duì)每篇文檔的單詞元進(jìn)行掃描。單詞元是文檔中單詞索引重復(fù)出現(xiàn)的實(shí)例。例如，“家”這個(gè)單詞在文檔中出現(xiàn)10次，那么就有10個(gè)“家”單詞元。每掃描一個(gè)單詞元，吉布斯采樣方法就推理出單詞元在主題上的語(yǔ)義分布，然后從該分布中隨機(jī)采樣一個(gè)主題賦予該單詞元。如果文檔中存在許多重復(fù)的單詞元，例如“家”重復(fù)1000次，吉布斯采樣方法的掃描時(shí)間就會(huì)大大增長(zhǎng)。同時(shí)，從單詞元的主題分布中采樣主題會(huì)丟掉分布中的部分信息，也使得語(yǔ)義壓縮的精度不高。通過(guò)多次掃描（通常大于500次）整個(gè)文檔集合，吉布斯采樣方法推理得到每篇文檔的主題分布參數(shù)，以及每個(gè)主題在單詞表上的分布參數(shù)，實(shí)現(xiàn)了語(yǔ)義壓縮的目標(biāo)。以10000篇文檔，每篇文檔含有100個(gè)單詞元為例，假設(shè)掃描一個(gè)單詞元并壓縮其語(yǔ)義需要0.00001秒，當(dāng)主題數(shù)目J=10，理論上吉布斯方法需要0.00001秒×10主題×10000文檔×100單詞元×500循環(huán)?=?50000秒時(shí)間完成語(yǔ)義壓縮。

變分貝葉斯方法僅對(duì)每篇文檔的單詞索引進(jìn)行掃描，例如文檔中“家”重復(fù)出現(xiàn)1000次，變分貝葉斯方法僅需掃描一次“家”在單詞表中的索引即可。這樣，變分貝葉斯方法在掃描整個(gè)文本集合方面比吉布斯采樣方法更有效率。但是，變分貝葉斯方法在推理每個(gè)單詞索引的語(yǔ)義信息時(shí)引入了復(fù)雜的digamma操作，該操作實(shí)際上消耗4-6倍于普通操作的時(shí)間。同時(shí)，digamma操作也給語(yǔ)義壓縮帶來(lái)了誤差。如果掃描10000篇文檔，每篇文檔雖然含有100個(gè)單詞元，但是單詞索引數(shù)目是50個(gè)，那么理論上變分貝葉斯方法需要0.00001秒×10主題×10000文檔×50單詞索引×500循環(huán)×5倍digamma操作?=?125000秒。

可見(jiàn)，吉布斯采樣和變分貝葉斯方法對(duì)語(yǔ)義壓縮都存在速度慢、精度不高的缺點(diǎn)。

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