異構文本數據轉換中XML解析方法對比研究

何卓桁,劉志勇,李 璐,李長明,張 琳

(1.東北師范大學 信息科學與技術學院,長春 130024; 2.同濟大學 軟件學院,上海 200092;3.長春光華學院 電氣信息學院,長春 130033; 4.吉林大學 軟件學院,長春 130012)

0 概述

由于異構文本數據具有數據量大、形式多樣且來源復雜等特點,在數據預處理工作中,存在查找有效信息困難的問題。為了對數據進行過濾并達到篩選有效信息的目的,需要對數據結構進行轉換,保證數據的統一化,從而簡化后續文本的處理工作。在異構文本的數據預處理工作中,異構數據的轉換是不可或缺的步驟,主要分為直接轉換和間接轉換。直接轉換是利用正則表達式對異構文本進行過濾并建立其對應結構,間接轉換是將異構文本轉換為半結構化的XML文本,以XML文本為橋梁轉換為結構化文本[1]。間接轉換已經得到了學者們的普遍認可,其轉換過程主要包括2個階段,第1階段是通過制定轉換規則將異構文本轉換為XML文本,第2階段是通過一定的解析方法將XML文本轉換為結構化文本。采用XML文本作為中間轉換的標準,優勢在于利用XML文本的分層嵌套格式,以及在分層表示的各個元素中均包含屬性和值[2],使得語義表達能力突出。另外,XML具有格式規整的特點,XML文檔不需要符合特定文檔類型定義(Document Type Definition,DTD)或者架構[3],這些特點使得XML文檔表達的Web內容能夠更好地被用戶理解。因此,XML適合存儲半結構化的數據。

第1階段中轉換方法的研究相對比較成熟,主要是對超文本標記語言進行去標記、分類,制定XML模板,主要研究工作包括:文獻[4]利用DTD或者由一種用于描述和規范XML文檔邏輯結構的語言(Schema)制定對應的規則,生成XML Schema。文獻[5]通過從XML文件中提取結構信息來創建一個臨時的DTD,將XML文件映射為對象數據庫。文獻[6]通過分析DTD和XML Schema 2種模式的不同之處,參考基于DTD的XML函數依賴的相關研究,提出XML Schema形式化定義和XML的軸元素定義,給出基于XML Schema標準的XML函數依賴定義以及其推理規則集,規范了XML文檔。文獻[7]通過模板建立Schema并將XML文本結構存入其中后再進行解析。文獻[8]對DTD進行深入研究,并討論XML架構受元素聲明一致性(Element Declaration Consistency,EDC)規則的影響。文獻[9]針對Web日志中的元素存在屬性和值,利用XML文本自身的分層結構與其相關聯的優勢,使得Web日志內容能夠更好地被表達。第2階段的解析方法主要有DOM、SAX、JDOM和DOM4J等4種,然而這4種方法在什么情況下才會更加有效,目前還缺乏科學的實驗論證,尚未形成統一的結論。

綜上所述,XML文本在異構文本數據轉換過程中起到了至關重要的作用,重點關注在異構數據轉換過程的第2階段,即將XML文本通過解析方法轉換為結構化數據。本文結合方法組合的思想,采用多組實驗進行比較[10],在同一實驗環境下,保證限定條件的統一,以多角度的方式對DOM、SAX、JDOM和DOM4J解析方法進行研究。相較于以往的對比研究[11],本文引入內存占用空間、CPU占用率和解析時間作為評價指標,相比單一的以效率為評價指標的方法,本文的評價指標方法更為全面、客觀和準確。以加權和的方式考慮不同指標的影響因素,使解析方法之間的區分度增大,結果更加直觀。同時,在統一評價指標上設置多組實驗,對4種解析方法在不同的價值取向下,驗證其解析方法的優劣性,為后續研究者針對不同的研究目的提供更加直觀切實的研究方法。

1 解析方法

以XML為介質,采用4種目前主流的解析方法DOM、SAX、JDOM和DOM4J對數據進行轉換。其中,DOM是目前解析XML文本的基礎解析方法,通過樹形結構存儲,該方法與XML存儲方法吻合,使用戶能夠更好地理解。SAX采用流處理方式,占用內存少,適用于處理文本量大的工作。JDOM結合了DOM與SAX的優點,基于樹形結構,提供更加簡單的邏輯訪問方法。DOM4J是JDOM的一種智能分支,它合并了包括集成XPath支持、XML Schema支持以及用于長文檔或流化式文檔的基于事件處理的功能。

1.1 DOM解析方法

DOM解析方法是將XML文本轉換為對象模型,運用樹結構對信息進行存儲,通過接口的方式進行訪問且可以訪問任意節點[12]。關于DOM解析方法的研究,文獻[13]利用DOM樹中的文本內容和層次結構對Web中的菜單和導航指示器的關鍵信息進行提取,通過在目標網頁中點選元素的方式,自動生成基于DOM路徑的抽取模板,從而達到解析并提取信息的目的。文獻[14]針對本地存儲結構化數據的XML文檔,設計一個基于DOM樹的輕量級文檔解析庫。但上述方法也存在一定的缺陷,如將文本轉換為樹結構時,若需要轉換的文件較大,則對樹結構的遍歷十分耗時,將導致整個解析過程十分緩慢。

1.2 SAX解析方法

SAX解析方法是以時間為驅動的API,采用類似流處理的方式在進行掃描文本的同時自頂向下依次完成解析任務[15]。在解析XML過程中,SAX占用的內存少且速度快。關于SAX解析方法的研究,文獻[16]提出基于SAX解析過程,利用列表以及關系指針2種方法相接合的方式來處理XPath查詢的QXSList方法,通過層次值計算判斷節點的結構關系,利用關系指針鏈接多個候選節點列表來獲取查詢結果。雖然SAX在處理關系層次較多以及文本數據量大的情況下表現優異,但是也存在SAX無法隨機訪問XML節點,也無法對XML文本進行修改,只能對文本進行讀取任務的缺點。

1.3 JDOM解析方法

JDOM解析方法是基于樹形結構,內置Xerces解析器,使用具體類的文檔解析模型,運用樹結構對信息進行存儲,它所包含的轉換器將JDOM表示輸出成SAX事件流、DOM模型[17]。關于JDOM解析方法的研究,文獻[18]利用其解析XML和Schema文件,完成了異構數據的轉換,該解析方法簡化了異構數據轉換的流程,并且保證了關系數據信息的完整性,但是這需要用戶充分地理解XML文本,說明JDOM解析方法缺乏一定的靈活性。

1.4 DOM4J解析方法

DOM4J解析方法是JDOM的分支,集成了DOM和SAX的XML文件解析器,提供大量接口用于對XML文件進行處理,且DOM4J API和標準DOM接口具有并行訪問功能[19]。關于DOM4J的研究,文獻[20]以XML文本作為數據庫存儲學生信息,利用DOM4J樹結構進行解析,結果表明,其解析時間較DOM解析方法短,這說明DOM4J在理論上較DOM表現良好。

通過對大量文獻進行分析,結果發現,間接轉換過程中的主要問題在于對目前主流的4種解析方法的優劣存在矛盾的結論。在各自領域中,運用不同的解析方法均能達到其預期效果,并不能體現出解析方法的優劣。因此需要在相同條件下進行比較并通過實驗證明目前主流的4種解析方法的優劣。

2 算法分析

在相同條件下,實驗利用4種解析方法對相同的數據集進行解析,其解析機制是根據文檔內容對其節點和元素進行讀取并輸出,解析的質量以消耗的時間和空間為評價指標,處理結果的正確性取決于程序是否能夠運行至結束。在實驗過程中,數據集的數據量和屬性個數在理論上對實驗結果的精度沒有影響,在算法分析過程中主要以解析方法的時間開銷來對算法的優劣性進行區分。

4種解析方法的時間開銷是實驗中對文檔進行解析所需要的時間,在本節中主要針對解析文檔時處理耗費的運行時間復雜度進行理論計算。其中,對代碼的運行次數記為n,每行代碼的時間開銷記為Cx,x代表程序對應的行,以下是4種解析方法的運行時間復雜度的分析。

DOM解析方法的運行時間復雜度如表1所示,由此可知,由于C8遠遠大于C1～C7,因此T(n)=C8n3=O(n3)。

表1 DOM解析方法的運行時間復雜度

SAX解析方法的運行時間復雜度如表2所示,由此可知,由于C3遠大于C1～C2,因此T(n)=C3n=O(n)。

表2 SAX解析方法的運行時間復雜度

JDOM解析方法的運行時間復雜度如表3所示,由表3可知,由于C6遠大于C1～C5,因此T(n)=C6n2=O(n2)。

表3 JDOM解析方法的運行時間復雜度

DOM4J解析方法的運行時間復雜度如表4所示,由此可知,由于C6遠大于C1～C5,因此T(n)=C6n2=O(n2)。

表4 DOM4J解析方法的運行時間復雜度

根據以上4種解析方法運行時間復雜度的分析可知,SAX解析方法的運行時間復雜度相比其他3種解析方法都較小,且DOM解析方法的運行時間復雜度最大。這是因為SAX解析方法采用的是流式處理文件的方法,即用即停,不需要將XML文本存入內存中,理論上適合用于數據量較大的情況。DOM、JDOM以及DOM4J解析方法均需要建立根節點,DOM4J區別于DOM主要是因為對應接口不同,其采用了SAXREADER,因此雖然時間復雜度相同,但是實際開銷比DOM小很多,而JDOM是DOM方法在JAVA語言中的API,因此時間開銷也比DOM4J大,由此可得出4種解析方法的理論時間開銷由大到小排序為CDOM>CJDOM>CDOM4J>CSAX。

3 評價指標

以解析時間與XML文本大小的比值作為效率,目前公認的評價指標是以效率的高低對實驗結果進行判定。文獻[21]利用解析時間為研究重點,在相同大小的文件下對DOM、SAX解析方法進行比較,得出SAX解析方法比DOM解析方法效率高的結論,但存在SAX解析方法在價值取向上過于單一的缺點。

由于解析時間和XML文本大成正比例關系,對結果的評價區分度不大。針對該問題,本文以解析時間t(ms)、內存堆占用空間d(MB)、CPU占用率c作為評價指標,將時間和空間2個維度劃分為分母和分子表示,并分別進行加權,加權和記為T、M。時間加權值指影響值I在時間維度上的加權值,記作β,表示為分子的加權值;空間加權值指對影響值I在空間維度上的加權值,記作α,表示為分母的加權值。為了數據的歸一化,將α和β的取值范圍設定在0～1之間,并且控制α和β成反比例關系,使結果受正比例關系的影響減小。影響值I的計算方法如下:

I(影響值)=(c×100+d)×α/(t×β)

(1)

β(時間加權值)=1-α(空間加權值)

(2)

在式(1)中,將影響值I作為解析方法優劣的判定依據,主要分為以下3種情況:

1)當時間加權值β和空間加權值α比重一樣時,影響值I作為直接影響值。

當不考慮時間和空間為價值取向時,影響值I越小,則解析方法越差;當以縮短解析時間為重點時,對堆內存容量和CPU占用率的要求高,同時對處理時間的縮減要求也高,因此此時影響值I值越小,則該解析方法在此條件下越差;相反,以占用空間為重點時,則對堆內存容量和CPU占用率要求低,對處理時間縮減的要求也降低,此時影響值I越大,則該解析方法越差。以空間占用為重點(縮短解析時間為重點)時,影響值I越大,解析方法越好;以解析時間為重點(占用堆內存空間為重點)時,影響值I越小,解析方法越好。在空間和時間加權和確定情況下,加權值分配對影響值的影響如圖1所示。

圖1 加權值分配比對影響值I的影響

采用上述評價方法具有以下優點:

1)將各個方法采用量值的方式進行比對,尤其在數據量不大以及屬性個數不多的情況下,能夠將解析方法對異構文本數據的轉換結果影響程度劃分,評價指標以時間和空間劃分的方式更加合理,且計算簡單。

2)隨著數據量增大,不同解析方法的影響值差I值增大,區分更加明顯。

4 實驗與結果分析

4.1 數據集

本文實驗數據采用八爪魚V8.0爬蟲軟件抓取電子商務網站用戶ID、名稱、登陸地等基本用戶標識及行為的日志信息,并利用.txt文件對信息進行存儲,在Eclipse環境下將.txt信息轉換成XML文件,從而獲得Web日志中XML文件資源,該資源主要記錄用戶訪問瀏覽網站的信息,且具有數據量大、屬性簡單明確的特點,數據總量為2 207 620條,數據屬性總共有7個。采用梯度劃分法將數據分為6個梯度數據量的數據集,并根據屬性個數不同增加4個不同屬性個數的數據集,總共10份數據并按編號1～10進行排列,數據集信息數量(條)的變化范圍為14 620～731 000,屬性個數(個)變化范圍為5～7,命名方式采用“Test_數據量_屬性個數”,具體如表5所示。其中,編號8用于實驗1、實驗4和實驗5,編號1、4、5、6、7、8用于實驗2,編號1～編號3和編號8～編號10用于實驗3。

表5 數據集的具體參數

根據DTD[22]規則,XML文本的具體參數如表6所示。

表6 XML文本的具體參數

4.2 實驗環境

系統環境為64位Win 10操作系統,8GB內存,Intel(R)Core(TM)i7@2.40GHZ。程序語言為Java8.0,XML。實驗工具為Eclipse Java 4.9.0,Navicat10.7。數據庫為Mysql5.6.41。

4.3 實驗過程

首先,進行“參數確定”的實驗,其次,分別進行數據量、屬性個數發生變化情況下的對比實驗,以此確定其影響大小,最后,從占用空間和縮短時間角度分別進行實驗,完成4種解析方法的對比。為了減少隨機數據集帶來的誤差,所有實驗均重復進行10次,并將所得的平均值作為最終結果。

4.3.1 參數確定

為了選取合理的時間和空間加權值,將10份異構數據分別轉換為XML文本的半結構化數據,每份數據均采用4種解析方法對其解析并計算影響值I。實驗通過區間分配權值的方法,取各種解析方法在6種不同數據量情況下影響值I的算數平均值,然后分別在5個不同區間下進行計算,對比在不同的α和β組合情況下,影響值I的變化范圍,實驗結果如圖2～圖4所示。由圖2可知,以時間占用為重點,0.8≤β≤0.9時,影響值I的變化情況最為明顯。由圖3可知,以空間占用為重點,0.8≤α≤0.9時,影響值I的變化情況最為明顯。由圖4可知,以數據量較大的Test_70w_6數據集為例,隨著權值比例的降低,時間與空間之間的影響值I差值越來越小。根據文件大小及解析時間的差值分析,權重過大會導致結果不穩定。

圖2 以時間占用為重點時的影響值I

圖3 以空間占用為重點時的影響值I

圖4 在數據集Test_70w_6上影響值I的變化

經過多次比對,以空間為重點時,本文選取α=0.85,β=0.15進行后續實驗,以時間為重點時,本文選取α=0.15,β=0.85進行后續實驗。

4.3.2 數據量對解析方法的影響

當數據量n從1.4萬條逐漸變化至70萬條時,在不考慮時間以及空間關系的情況下,實驗比較了4種解析方法的影響值I,結果如圖5、圖6所示,圖6為圖5中影響值I的局部放大。

圖5 4種解析方法在數據集Test_1.4w_6～Test_70w_6下的影響值I

圖6 4種解析方法在數據集Test_28w_6 ～ Test_70w_6下的影響值I

從圖5和圖6可得出以下結論:

1)隨著數據量n的增大,4種解析方法所花費的時間均增加,并且數據量n越大,4種解析方法的差距越小,因此本文主要針對數據量n增大的情況進行后續實驗。

2)當數據量n低于35萬條時,DOM解析方法的影響值I比DOM4J解析方法高,數據量繼續增大至高于35萬條時,DOM4J解析方法的影響值I逐漸高于DOM解析方法,且始終比DOM解析方法的影響值I高。在時間和空間加權值比重相同時,DOM4J解析方法在35萬條～70萬條數據量時最優。

3)在數據集Test_42w_6與Test_56w_6之間,SAX解析方法的影響值I逐漸高于JDOM解析方法,且與DOM4J、DOM解析方法的差值逐漸縮小,當時間和空間加權值比重相同時,SAX解析方法可能會隨著數據量n的增大,影響值I逐漸升高。

實驗結果表明,時間和空間加權值分配一致即不考慮時間空間影響時,當數據量n較小時,DOM解析方法具有很高的效率,繼續增大數據量n時,該解析方法的效率反而降低,這是因為DOM解析方法采用的是樹節點遍歷全文的方式對文檔解析,當數據量n較大時,建立樹節點的時間會大幅增加,會造成效率變差,影響值I降低。

當數據量n較小時,從影響值I大小的角度分析,SAX解析方法的時間占用相對空間占用比其他3種解析方法多,且效果最差,當數據量n增大時,效率逐漸升高,且幅度較大。這是因為SAX解析方法采用的是流式處理文件的方式,逐行解析可以隨時停止,不耗費空間資源,因此當數據量n增大時,影響值I會相對其他解析方法升高。

JDOM解析方法的影響值I隨著數據量n的增大呈降低趨勢,這是因為當數據量n增大時,在空間資源相差不大的情況下,JDOM解析方法耗費的時間遠大于其他3種解析方法。

DOM4J解析方法的影響值I隨著數據量n的增大呈升高趨勢,這是因為雖然DOM4J解析方法采用獲取根節點的方式遍歷其子節點和屬性,但是處理過程中可以根據接口選擇SAX讀取器,因此相對其他3種解析方法,其處理方式更快。

4.3.3 屬性個數對解析方法的影響

實驗對算法的時間復雜度進行分析,為了比較屬性個數對解析結果的影響程度,在不考慮空間的影響因素下,以分子不變的影響值I作為判定依據。本文實驗利用Test_1.4w_6和Test_70w_6數據集對屬性加減,得到Test_1.4w_7、Test_1.4w_5、Test_70w_7和Test_70w_5這4個不同屬性個數的數據集,比較6個數據集的影響值I,實驗結果如圖7和圖8所示。

圖7 4種解析方法在數據集Test_1.4w_6中的影響值I

圖8 4種解析方法在數據集Test_70w_6中的影響值I

從圖7和圖8可以得出以下結論:

1)在數據集Test_1.4w_6屬性加減后的3個數據集上,當屬性個數減少時,DOM解析方法的影響值I比原數據集小;當屬性個數增大或者減少時,JDOM和DOM4J解析方法的影響值都比原數據集小。

2)在6個數據集上,屬性個數的增加或者減少對SAX解析方法的影響值I影響不大,且影響值差值均低于其他3種解析方法。

3)在Test_70w_6屬性加減后的3個數據集上,4種解析方法的影響值I變化情況基本一致,當屬性個數減少時,4種解析方法的影響值I最高,而當屬性個數增加時,4種解析方法的影響值I最低。

實驗結果表明,當數據量n不大時,屬性個數的變化對結果的影響是非穩定性因素;當數據量n增大時,屬性的變化對結果的影響是穩定性因素。因為在數據量n較小時,無論是解析空間還是解析時間,受實驗環境的影響,限制條件被忽略,干擾性增強,當數據量n增大后,實驗環境的影響對處理事件所耗費的時間干擾性減弱。由此表明,在不考慮時間和空間為重點并且數據量n較大的條件下,當屬性個數增加時,影響值I降低,當屬性個數減少時,影響值I升高。

4.3.4 縮短時間為重點時不同解析方法對比

本文實驗將以α=0.15,β=0.85分別賦予空間和時間加權值。當考慮縮短時間為重點時,在數據集Test_70w_6上,對比4種解析方法影響值I的變化情況,并表示出該權重比與權重比為1時的差值,此差值表示為函數以時間為重點價值取向時的突出程度,結果如圖9和圖10所示。

圖9 在數據集Test_70w_6中以時間為重點的4種解析方法的比較

圖10 4種解析方法的權重比差值比較

從圖9和圖10可以得出以下結論:

1)DOM和DOM4J解析方法在該條件下的影響值I均比JDOM和SAX解析方法高,且在10組實驗中,DOM4J解析方法的平均值大于DOM解析方法,說明以時間為重點時,DOM4J解析方法的解析效果最好。

2)在差值對比分析過程中,JDOM解析方法的差值最高(-0.017 67),說明在縮短數據解析時間上,JDOM解析方法的時間開銷最大。

實驗結果表明,DOM4J解析方法適用于以縮短解析時間為重點的實驗環境。在實際的XML文本解析中,在實驗條件較好且數據量n較大的情況下,DOM4J解析方法的性價比最高,且實用性很強。

4.3.5 占用空間為重點時不同解析方法對比

本實驗將以α=0.85,β=0.15分別賦予空間和時間加權值。在考慮占用空間重點時,同樣在數據集Test_70w_6上,對比4種解析方法影響值I的變化情況,并表示出該權重比與權重比為1時的差值,此差值為函數以空間為重點時的突出程度。由于DOM4J和JDOM解析方法均是根據DOM解析方法中的數據存儲方式來構建根節點樹,需要把文檔存至內存中,因此以空間為重點價值取向時,主要比較了DOM樹結構和SAX流式處理文件結構,實驗結果如圖11所示。

圖11 以空間為重點時的SAX和DOM解析方法的比較

從圖11可以得出以下結論:

1)以占用空間為重點時,以DOM解析方法的樹形結構方式空間占用比大于用SAX解析方法的流式處理文件結構,且在數據量n為70萬條時,平均堆內存空間占用差值為126 MB。

2)以樹結構的存儲數據的方式堆空間占用是流式文件處理方式的堆空間占用的1.52倍。

實驗結果表明,當數據量n增大時,若考慮以空間占用為重點的實驗環境,則采用SAX解析方法效果最好。

5 結束語

針對異構文本數據轉換中,DOM、SAX、JDOM、DOM4J解析方法在不同情況下選擇哪種方法更加有效,還存在缺乏科學實驗論證的問題,本文提出對異構文本數據轉換中XML解析方法進行對比研究,以3種不同評價指標來判定4種解析方法的優劣,得出了以解析時間為重點價值取向時,采用DOM4J解析方法最優,以空間占用為重點價值取向時,采用SAX解析方法最優的結論。但是本文也存在不足之處,如在進行不同梯度數據量的實驗時,未針對數據量極大的情況進行實驗,同時在CPU利用和空間占用的硬件利用問題上,也未嘗試負載運行實驗。在下一步研究中,擬選取數據量在100萬條～500萬條的XML數據集,調整數據梯度的縱向深度,對比觀察數據量梯度變化與影響值的比例關系,推算解析算法的極限算力。而對于實驗環境的硬件選擇,擬采用集群式機群,采用分布式原理調整實驗過程中的最大吞吐量,嘗試負載運行機器,對比觀察數據的處理時長,以期能夠利用數據結果直觀說明解析方法的內部處理方式。