一種基於文件差異的xml文檔壓縮方法
2023-05-25 08:20:31 1
專利名稱：一種基於文件差異的xml文檔壓縮方法
技術領域：
本發明屬資料庫技術領域，具體涉及一種新穎高效的XML文檔壓縮算法，XDrill壓縮算法。XDrill通過對XML文檔進行劃分來挖掘文檔內部以及文檔間的冗餘信息，得到了良好的壓縮效果。
背景技術：
XML作為一種自描述標記語言已廣泛應用於各個領域，例如電子文書的交換，醫院中的電子病例等。XML被大量用來描述半結構化數據，為了支持XML的自描述特性，XML文檔中存在著大量標記用來區分文檔內容的結構。這種結構和內容並存的存儲結構方式在方便文檔查詢和機器交互的同時也帶來了大量的信息冗餘。在一些資源受限的系統中，XML文件的冗餘問題會造成傳輸數據時浪費大量帶寬。為了解決這一問題，許多研究工作提出了針對XML文檔進行壓縮的技術，包括XMill，XGrind，XPress等。
XMill首先提出了在XML文檔壓縮過程中分離結構信息。利用XML文檔已有的結構信息，XMill重新構造壓縮後的文檔結構，使其可以最大效率的利用結構信息提高壓縮率。XMill的壓縮策略在大多數情況下都能得到非常優秀的壓縮效果，但是當XML文檔非常小或者XML文檔內的標記種類非常多時，對標記名稱進行字典編碼等過程所帶來的附加結構會導致壓縮效果下降。實驗表明當文件小於20K時，XMill的壓縮效果並不明顯。這一特點導致XMill非常不適合壓縮大量結構簡單，體積較小的XML文檔集合。
發明內容
本發明的目的在於提出了一種基於文件差異的XML壓縮算法XDrill，使得不管對單一的XML文檔還是結構和內容相似的文檔集合都能取得良好的壓縮效果。
該方法步驟是 a，將XML文件劃分為64K的XML文檔片斷； b，計算XML文檔片斷之間的差異； c，壓縮文檔片斷之間的差異。
解壓縮步驟與該過程相反。
本發明的優點是，該算法通過對XML文檔樹結構進行劃分來挖掘文檔內部以及文檔間的冗餘信息，得到了良好的壓縮效果。本文提出的方法經擴展後，可以支持壓縮後XML文檔的增量式存儲和降低更新操作的系統開銷。
關於XML文檔樹 本發明中，一棵XML文檔樹T＝{V，E，Root}，其中V＝{VT，VC}，VT表示結構節點，VC表示內容節點，E表示XML文檔樹的邊，Root表示文檔根節點。
關於XML文檔樹的劃分和XML文檔片斷 T中Root的兒子節點集合W＝{d1，d2...di，...dn}，對以di為根節點的子樹，定義XML文檔樹T的劃分定義
對應的XML文檔為XML文檔片斷 關於
的內容信息片斷和結構信息片斷
的內容信息片斷是指按照前序遍歷遇到內容節點的順序，將節點內容通過連接符「＾「(假定「＾「符號不會在XML文檔中出現)連接成的字符串。
的結構信息片斷是指按照前序遍歷的順序，將結構內容連接成的字符串。這一過程中對遍歷到的內容節點，使用符號「＾「來代替。
關於參考文件和目標文件 這裡參考文件和目的文件都是指XML文檔片斷。參考文件被用作壓縮其它文件的參考。目的文件是指使用參考文件進行壓縮的文件。
關於XML文檔片斷間的相似度 為了消除結構和內容信息混合存儲所帶來的影響，這裡使用傳統的樹編輯距離DT和文本編輯距離DC來分別定義的結構信息和內容信息相似度。文檔片斷A通過基本操作達到文檔片斷B的最少步驟個數定義為兩個XML文檔片斷間的相似度，DiffA→B＝DT+DC。
定理1.DiffA→B＝DT+DC和DiffB→A＝DT+DC相等。由DT和DC定義知，兩種編輯距離的基本操作都是可逆的，例如由A轉換為B時的添加操作對應於由B轉換為A的刪除操作等，所以兩種編輯距離的值相等。
推論由於DiffA→B＝DT+DC和DiffB→A＝DT+DC值相同。對於片斷集合可以使用無向帶權圖G＝{V，E，W}來表示。其中 關於XDrill壓縮算法的參考文件關係圖 XDrill壓縮算法的參考文件關係圖R＝{V，E，W}為一個有向帶權無環圖。其中邊eij表示使用第i個文檔片斷為參考文件對第j個文檔片斷進行壓縮，稱為j依賴於i。首先參考文件關係圖必須保證每一個文件只能被壓縮一次。另一方面如果R內存在環，則壓縮文檔不能只依賴已壓縮的部分信息進行解壓縮。例如假設Di，Dj，Dk之間互相依賴，則三個文件無法在不依賴外部信息的情況下進行解壓縮，如圖一所示。
定2.當固定每一個文件使用唯一參考文件時(XDrill參考文件關係圖中任意一個節點入度最多為1)，使得XDrill壓縮壓縮效果最優的問題等價無向帶權圖的最小生成子樹問題。
定理3.當每一個文件使用兩個或兩個以上的參考文件時，XDrill壓縮壓縮效果最優的問題可以被抽象為hypergraph上的branching問題，已被證明是NPC問題。
由於這種計算方法需要提前計算任意兩個文檔間的關係，會消耗大量時間和資源，所以在實際使用中並不適用。
圖1 循環依賴關係圖。
圖2 XDrill系統框架。
具體實施例方式 關於XDrill壓縮系統框架 圖2是XDrill壓縮系統的框架結構圖。XDrill壓縮系統主要由兩大部分組成，一部分是SAX解析器部分，主要用來讀取原始文件並且通過調用切分模塊(segmentationmodule)來生成對應的參考文件以及目的文件。另一部分是壓縮器模塊(Compressor)，這一部分調用底層的zdelta壓縮器對原始文件進行壓縮。
其中XML segment是指通過切分模塊後生成的XML片斷。
關於 XDrill壓縮算法和流程 XDrill壓縮算法流程如表一所示。XDrill壓縮系統需要維護六個系統緩存，其中refl_structure，ref2_structure用來存儲兩個參考文件的結構片斷信息。refl_structure，ref2_contents用來存儲兩個參考文件的內容片斷信息。tar_structure和tar_contents用來維護當前的XML文件片斷的信息。SAX解析器不斷讀取XML文檔內容向tar_structure和tar_contents中寫入數據。如果當前的SAX事件滿足了切割規則的切割斷點，調用zdelta壓縮工具利用對應的結構和內容片斷對目的文件壓縮(對應於第7，8兩行代碼)。對應代碼中的第9至14行是對應的緩衝區數據交換。利用ref2_structure和ref2_contents更新refl_structure和ref2_contents中的數據。同樣，使用tar_structure和tar_contents中的數據替換ref2_structure和ref2_contents中的數據。最後清空tar_structure和tar_contents。SAX parser繼續讀入下面的數據。
解壓縮過程與此相反，不贅述。
在XDrill系統中為了降低XML文檔的操作粒度我們採用了分割XML文檔樹的做法。對於生成的每一個XML文檔片斷，依然可以使用已有的XML壓縮算法，例如XMill等進行壓縮。但是對於XML文檔整體來說，已有的XML壓縮算法只能利用單個XML文檔片斷內部的信息冗餘，而XDrill在利用該片斷自身冗餘信息的同時還通過參考文件內的信息預測了一部分冗餘信息。
關於XML文檔的更新和增量式存儲 由於XDrill對XML文檔劃分後進行壓縮，文件的操作粒度也得到相應的降低。XDrill系統中，XML文檔的更新首先需要定位更新XML片斷的位置，然後使用zdelta壓縮新文檔片斷與舊有信息的文件差異進行傳輸。
當用戶需要增量式存儲時，新的XML信息只要使用對應的原始XML文檔片斷為參考文件進行壓縮即可。
表— Xdrill算法
1if(SAX-Event是開始標籤事件) 2將開始標籤字符寫入 tar_structure； 3else if(SAX-Event是結束標籤事件) 4if(不滿足劃分規則) 5將結束標籤字符寫入 tar_structure； 6else 7zdelta(ref1_structure，ref2_structure，tar_structure) 8zdelta(ref1_contents，ref2_contents，tar_contents) 9移動ref2_structure的信息至refl_structure； 10 移動ref2_contents的信息至refl_contents； 11 移動tar_structure的信息至ref2_structure； 12 清除tar_structure中的內容； 13 移動tar_content中的信息至ref2_content； 14 清除tar_contents中的內容 15 else if(SAX-Event是文本事件) 16 將符號「＾」寫入tar_structure； 17 將文本內容寫入tar_contents； 18 將符號「＾」寫入tar_contents； 19 End。
權利要求
1、一種基於文件差異的XML文檔壓縮方法，該方法步驟是
a，將XML文件劃分為64K的XML文檔片斷；
b，計算XML文檔片斷之間的差異；
c，壓縮文檔片斷之間的差異；
解壓縮步驟與該過程相反。
全文摘要
本發明屬資料庫技術領域，具體提出了一種新型的XML文檔壓縮算法，該方法步驟是a.將XML文件劃分為64K的XML文檔片斷；b.計算XML文檔片斷之間的差異；c.壓縮文檔片斷之間的差異。解壓縮步驟與該過程相反。這是一種高效的基於計算文件差異的XML文檔壓縮算法。XDrill通過對XML文檔樹進行劃分來挖掘文檔內部以及文檔間的冗餘信息，得到了良好的壓縮效果。相比於傳統的XML壓縮算法，XDrill的文件操作粒度更小，使用也更加靈活。
文檔編號G06F17/30GK101364235SQ20081020069
公開日2009年2月11日 申請日期2008年9月27日 優先權日2008年9月27日
發明者周傲英, 耿志華, 王曉玲 申請人:復旦大學