[發(fā)明專利]XML數(shù)據(jù)的壓縮

有效

• 申請?zhí)枺?/td>: 200980160715.0
• 申請日: 2009-07-31
• 公開（公告）號: CN102473175A
• 公開（公告）日: 2012-05-23
• 發(fā)明（設(shè)計）人: D.B.埃爾津加;S.克里什納穆爾蒂
• 申請（專利權(quán)）人: 惠普開發(fā)有限公司
• 主分類號: G06F17/21
• 分類號: G06F17/21;G06F9/06
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 段俊峰;盧江

背景技術(shù)

數(shù)據(jù)壓縮涉及將原始數(shù)據(jù)編碼成使用比原來的原始數(shù)據(jù)更少比特的表示。這種壓縮是有用的，因為需要較少的資源來存儲和/或傳輸壓縮的數(shù)據(jù)。然而，只有壓縮數(shù)據(jù)的創(chuàng)作者和壓縮數(shù)據(jù)的用戶二者都能夠取得編碼方案，壓縮才是有用的。

XML（可擴(kuò)展標(biāo)記語言）是用于結(jié)構(gòu)化數(shù)據(jù)的開放標(biāo)準(zhǔn)。XML將數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)內(nèi)容分離，以及從而提供用于數(shù)據(jù)歸檔的基于標(biāo)準(zhǔn)的良好平臺。然而，XML通常將原來的結(jié)構(gòu)化數(shù)據(jù)的大小擴(kuò)大10-20倍，除非XML數(shù)據(jù)被壓縮。此外，標(biāo)準(zhǔn)的數(shù)據(jù)壓縮技術(shù)傾向于將XML數(shù)據(jù)縮減到僅大約非壓縮數(shù)據(jù)內(nèi)容的原來大小。Lempel-Ziv?（LZ）壓縮是數(shù)據(jù)壓縮技術(shù)的一個示例。

操縱、訪問或以其他方式解析壓縮XML文件一般要求該文件首先被解壓縮。這通常導(dǎo)致需要將整個XML文件讀入到存儲器中，或者從該文件順序地讀取數(shù)據(jù)。示例解析技術(shù)包括DOM?XML解析、SAX?XML解析和VTD?XML解析。

由于上述原因以及由于在閱讀并理解本說明書后對本領(lǐng)域的技術(shù)人員將變得顯而易見的其他原因，在本領(lǐng)域中存在對用于壓縮XML數(shù)據(jù)的可選方法和裝置的需求。

附圖說明

圖1示出了根據(jù)本公開實施例的適合于壓縮XML源數(shù)據(jù)的示例性計算機(jī)系統(tǒng)100。

圖2A-2C共同表示待用于描述本公開實施例的各個特征的XML源數(shù)據(jù)的示例。

圖3A-3C共同表示根據(jù)本公開實施例的響應(yīng)于圖2A-2C的XML源數(shù)據(jù)而生成的壓縮數(shù)據(jù)結(jié)構(gòu)的示例。

圖4是根據(jù)本公開實施例的用于生成圖3C的壓縮數(shù)據(jù)結(jié)構(gòu)的樣本壓縮字典的表示。

圖5描繪了根據(jù)本公開實施例的將圖2A-2C的XML源數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)的層級表示為樹索引。

圖6A-6B表示根據(jù)本公開實施例的壓縮文件結(jié)構(gòu)。

具體實施方式

在下文對本實施例的詳細(xì)描述中，參考形成其一部分的附圖，并且在附圖中通過圖示方式示出了可以實踐的本公開的特定實施例。對這些實施例進(jìn)行了充分詳細(xì)的描述，以使得本領(lǐng)域的技術(shù)人員能夠?qū)嵺`本公開的主題，并且要理解的是，可以利用其他實施例并且可以做出過程、電或機(jī)械的改變而不脫離本公開的范圍。因此，下文詳細(xì)描述不要被理解為限制性含義，并且本公開的范圍僅由隨附的權(quán)利要求及其等效物限定。

XML（可擴(kuò)展標(biāo)記語言）是存儲并傳送數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。XML包括根元素，所有其他元素依賴于該根元素。每個元素包括開始標(biāo)簽（例如，<Root_Element>）以及結(jié)束標(biāo)簽（例如，</Root_Element>）。每個元素在其開始和結(jié)束標(biāo)簽之間可以包括其他元素（即，子元素）或文本內(nèi)容（即，數(shù)據(jù)內(nèi)容）。包含子元素的任何元素將被視為該子元素的父元素。子元素將分成兩類，即包含其他元素的那些元素以及僅包含數(shù)據(jù)內(nèi)容的那些元素。

各種實施例提供了一種方法，該方法用于以高壓縮比將XML數(shù)據(jù)歸檔并且同時實現(xiàn)對壓縮XML數(shù)據(jù)的高速、隨機(jī)訪問而不需要讀取或解壓縮整個文件。各種實施例通過重組數(shù)據(jù)結(jié)構(gòu)以將元素名稱和數(shù)據(jù)內(nèi)容分離來促進(jìn)壓縮和訪問。首先識別XML數(shù)據(jù)的層級。將共享相同結(jié)構(gòu)的數(shù)據(jù)層級的組物理地歸集到一起作為父元素和僅包含數(shù)據(jù)內(nèi)容的任何其子元素。為與表示父元素的元素名稱相關(guān)的每個元素類型定義層級組。也就是說，作為一個或多個子元素的父元素的每個元素將表示元素類型，并且將與相同層級分組在一起。注意的是，特定層級組的元素類型可能進(jìn)一步包含一個或多個包含其他元素的子元素，這對于進(jìn)一步作為其他元素的父元素的每個這種子元素而言將導(dǎo)致不同元素類型的另一層級組。

通過將數(shù)據(jù)層級分組，可以將通常冗長的元素名稱與數(shù)據(jù)內(nèi)容分離，并且對該層級僅存儲一次而非被重復(fù)，從而轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)。為層級內(nèi)的每個實例創(chuàng)建計數(shù)器，因為其被邏輯地移到相同層級的塊。這允許解壓縮復(fù)制層級之間的相對順序。這一過程生成表示XML源數(shù)據(jù)文件的壓縮版本的文件，例如純文本文件。

對于某些實施例，創(chuàng)建跳轉(zhuǎn)列表以促進(jìn)壓縮文件的隨機(jī)訪問。跳轉(zhuǎn)列表可以包含指示與特定元素類型相關(guān)的元素名稱的列表的位置和元素名稱的長度，以及用于該元素類型的一個或多個實例的與跟該特定元素類型相關(guān)的元素名稱對應(yīng)的數(shù)據(jù)內(nèi)容的位置的值。例如，跳轉(zhuǎn)列表可以包含指示與特定元素類型相關(guān)的元素名稱的列表在壓縮文件中的位置的值以及指示該元素名稱的列表的長度的值；指示表示該特定元素類型的第一實例的數(shù)據(jù)內(nèi)容的數(shù)據(jù)值的列表在壓縮文件中的位置和其長度的值；指示表示該特定元素類型的第二實例的數(shù)據(jù)內(nèi)容的數(shù)據(jù)值的列表在壓縮文件中的位置和其長度的值等。跳轉(zhuǎn)列表可以與壓縮文件分離，或者其可以被添加到壓縮文件。