何卓桁,劉志勇,李 璐,李長(zhǎng)明,張 琳

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

0 概述

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

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

綜上所述,XML文本在異構(gòu)文本數(shù)據(jù)轉(zhuǎn)換過(guò)程中起到了至關(guān)重要的作用,重點(diǎn)關(guān)注在異構(gòu)數(shù)據(jù)轉(zhuǎn)換過(guò)程的第2階段,即將XML文本通過(guò)解析方法轉(zhuǎn)換為結(jié)構(gòu)化數(shù)據(jù)。本文結(jié)合方法組合的思想,采用多組實(shí)驗(yàn)進(jìn)行比較[10],在同一實(shí)驗(yàn)環(huán)境下,保證限定條件的統(tǒng)一,以多角度的方式對(duì)DOM、SAX、JDOM和DOM4J解析方法進(jìn)行研究。相較于以往的對(duì)比研究[11],本文引入內(nèi)存占用空間、CPU占用率和解析時(shí)間作為評(píng)價(jià)指標(biāo),相比單一的以效率為評(píng)價(jià)指標(biāo)的方法,本文的評(píng)價(jià)指標(biāo)方法更為全面、客觀和準(zhǔn)確。以加權(quán)和的方式考慮不同指標(biāo)的影響因素,使解析方法之間的區(qū)分度增大,結(jié)果更加直觀。同時(shí),在統(tǒng)一評(píng)價(jià)指標(biāo)上設(shè)置多組實(shí)驗(yàn),對(duì)4種解析方法在不同的價(jià)值取向下,驗(yàn)證其解析方法的優(yōu)劣性,為后續(xù)研究者針對(duì)不同的研究目的提供更加直觀切實(shí)的研究方法。

1 解析方法

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

1.1 DOM解析方法

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

1.2 SAX解析方法

SAX解析方法是以時(shí)間為驅(qū)動(dòng)的API,采用類似流處理的方式在進(jìn)行掃描文本的同時(shí)自頂向下依次完成解析任務(wù)[15]。在解析XML過(guò)程中,SAX占用的內(nèi)存少且速度快。關(guān)于SAX解析方法的研究,文獻(xiàn)[16]提出基于SAX解析過(guò)程,利用列表以及關(guān)系指針2種方法相接合的方式來(lái)處理XPath查詢的QXSList方法,通過(guò)層次值計(jì)算判斷節(jié)點(diǎn)的結(jié)構(gòu)關(guān)系,利用關(guān)系指針鏈接多個(gè)候選節(jié)點(diǎn)列表來(lái)獲取查詢結(jié)果。雖然SAX在處理關(guān)系層次較多以及文本數(shù)據(jù)量大的情況下表現(xiàn)優(yōu)異,但是也存在SAX無(wú)法隨機(jī)訪問(wèn)XML節(jié)點(diǎn),也無(wú)法對(duì)XML文本進(jìn)行修改,只能對(duì)文本進(jìn)行讀取任務(wù)的缺點(diǎn)。

1.3 JDOM解析方法

JDOM解析方法是基于樹形結(jié)構(gòu),內(nèi)置Xerces解析器,使用具體類的文檔解析模型,運(yùn)用樹結(jié)構(gòu)對(duì)信息進(jìn)行存儲(chǔ),它所包含的轉(zhuǎn)換器將JDOM表示輸出成SAX事件流、DOM模型[17]。關(guān)于JDOM解析方法的研究,文獻(xiàn)[18]利用其解析XML和Schema文件,完成了異構(gòu)數(shù)據(jù)的轉(zhuǎn)換,該解析方法簡(jiǎn)化了異構(gòu)數(shù)據(jù)轉(zhuǎn)換的流程,并且保證了關(guān)系數(shù)據(jù)信息的完整性,但是這需要用戶充分地理解XML文本,說(shuō)明JDOM解析方法缺乏一定的靈活性。

1.4 DOM4J解析方法

DOM4J解析方法是JDOM的分支,集成了DOM和SAX的XML文件解析器,提供大量接口用于對(duì)XML文件進(jìn)行處理,且DOM4J API和標(biāo)準(zhǔn)DOM接口具有并行訪問(wèn)功能[19]。關(guān)于DOM4J的研究,文獻(xiàn)[20]以XML文本作為數(shù)據(jù)庫(kù)存儲(chǔ)學(xué)生信息,利用DOM4J樹結(jié)構(gòu)進(jìn)行解析,結(jié)果表明,其解析時(shí)間較DOM解析方法短,這說(shuō)明DOM4J在理論上較DOM表現(xiàn)良好。

通過(guò)對(duì)大量文獻(xiàn)進(jìn)行分析,結(jié)果發(fā)現(xiàn),間接轉(zhuǎn)換過(guò)程中的主要問(wèn)題在于對(duì)目前主流的4種解析方法的優(yōu)劣存在矛盾的結(jié)論。在各自領(lǐng)域中,運(yùn)用不同的解析方法均能達(dá)到其預(yù)期效果,并不能體現(xiàn)出解析方法的優(yōu)劣。因此需要在相同條件下進(jìn)行比較并通過(guò)實(shí)驗(yàn)證明目前主流的4種解析方法的優(yōu)劣。

2 算法分析

在相同條件下,實(shí)驗(yàn)利用4種解析方法對(duì)相同的數(shù)據(jù)集進(jìn)行解析,其解析機(jī)制是根據(jù)文檔內(nèi)容對(duì)其節(jié)點(diǎn)和元素進(jìn)行讀取并輸出,解析的質(zhì)量以消耗的時(shí)間和空間為評(píng)價(jià)指標(biāo),處理結(jié)果的正確性取決于程序是否能夠運(yùn)行至結(jié)束。在實(shí)驗(yàn)過(guò)程中,數(shù)據(jù)集的數(shù)據(jù)量和屬性個(gè)數(shù)在理論上對(duì)實(shí)驗(yàn)結(jié)果的精度沒(méi)有影響,在算法分析過(guò)程中主要以解析方法的時(shí)間開(kāi)銷來(lái)對(duì)算法的優(yōu)劣性進(jìn)行區(qū)分。

4種解析方法的時(shí)間開(kāi)銷是實(shí)驗(yàn)中對(duì)文檔進(jìn)行解析所需要的時(shí)間,在本節(jié)中主要針對(duì)解析文檔時(shí)處理耗費(fèi)的運(yùn)行時(shí)間復(fù)雜度進(jìn)行理論計(jì)算。其中,對(duì)代碼的運(yùn)行次數(shù)記為n,每行代碼的時(shí)間開(kāi)銷記為Cx,x代表程序?qū)?yīng)的行,以下是4種解析方法的運(yùn)行時(shí)間復(fù)雜度的分析。

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

表1 DOM解析方法的運(yùn)行時(shí)間復(fù)雜度

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

表2 SAX解析方法的運(yùn)行時(shí)間復(fù)雜度

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

表3 JDOM解析方法的運(yùn)行時(shí)間復(fù)雜度

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

表4 DOM4J解析方法的運(yùn)行時(shí)間復(fù)雜度

根據(jù)以上4種解析方法運(yùn)行時(shí)間復(fù)雜度的分析可知,SAX解析方法的運(yùn)行時(shí)間復(fù)雜度相比其他3種解析方法都較小,且DOM解析方法的運(yùn)行時(shí)間復(fù)雜度最大。這是因?yàn)镾AX解析方法采用的是流式處理文件的方法,即用即停,不需要將XML文本存入內(nèi)存中,理論上適合用于數(shù)據(jù)量較大的情況。DOM、JDOM以及DOM4J解析方法均需要建立根節(jié)點(diǎn),DOM4J區(qū)別于DOM主要是因?yàn)閷?duì)應(yīng)接口不同,其采用了SAXREADER,因此雖然時(shí)間復(fù)雜度相同,但是實(shí)際開(kāi)銷比DOM小很多,而JDOM是DOM方法在JAVA語(yǔ)言中的API,因此時(shí)間開(kāi)銷也比DOM4J大,由此可得出4種解析方法的理論時(shí)間開(kāi)銷由大到小排序?yàn)镃DOM>CJDOM>CDOM4J>CSAX。

3 評(píng)價(jià)指標(biāo)

以解析時(shí)間與XML文本大小的比值作為效率,目前公認(rèn)的評(píng)價(jià)指標(biāo)是以效率的高低對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行判定。文獻(xiàn)[21]利用解析時(shí)間為研究重點(diǎn),在相同大小的文件下對(duì)DOM、SAX解析方法進(jìn)行比較,得出SAX解析方法比DOM解析方法效率高的結(jié)論,但存在SAX解析方法在價(jià)值取向上過(guò)于單一的缺點(diǎn)。

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

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

(1)

β(時(shí)間加權(quán)值)=1-α(空間加權(quán)值)

(2)

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

1)當(dāng)時(shí)間加權(quán)值β和空間加權(quán)值α比重一樣時(shí),影響值I作為直接影響值。

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

圖1 加權(quán)值分配比對(duì)影響值I的影響

采用上述評(píng)價(jià)方法具有以下優(yōu)點(diǎn):

1)將各個(gè)方法采用量值的方式進(jìn)行比對(duì),尤其在數(shù)據(jù)量不大以及屬性個(gè)數(shù)不多的情況下,能夠?qū)⒔馕龇椒▽?duì)異構(gòu)文本數(shù)據(jù)的轉(zhuǎn)換結(jié)果影響程度劃分,評(píng)價(jià)指標(biāo)以時(shí)間和空間劃分的方式更加合理,且計(jì)算簡(jiǎn)單。

2)隨著數(shù)據(jù)量增大,不同解析方法的影響值差I(lǐng)值增大,區(qū)分更加明顯。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 數(shù)據(jù)集

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

表5 數(shù)據(jù)集的具體參數(shù)

根據(jù)DTD[22]規(guī)則,XML文本的具體參數(shù)如表6所示。

表6 XML文本的具體參數(shù)

4.2 實(shí)驗(yàn)環(huán)境

系統(tǒng)環(huán)境為64位Win 10操作系統(tǒng),8GB內(nèi)存,Intel(R)Core(TM)i7@2.40GHZ。程序語(yǔ)言為Java8.0,XML。實(shí)驗(yàn)工具為Eclipse Java 4.9.0,Navicat10.7。數(shù)據(jù)庫(kù)為Mysql5.6.41。

4.3 實(shí)驗(yàn)過(guò)程

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

4.3.1 參數(shù)確定

為了選取合理的時(shí)間和空間加權(quán)值,將10份異構(gòu)數(shù)據(jù)分別轉(zhuǎn)換為XML文本的半結(jié)構(gòu)化數(shù)據(jù),每份數(shù)據(jù)均采用4種解析方法對(duì)其解析并計(jì)算影響值I。實(shí)驗(yàn)通過(guò)區(qū)間分配權(quán)值的方法,取各種解析方法在6種不同數(shù)據(jù)量情況下影響值I的算數(shù)平均值,然后分別在5個(gè)不同區(qū)間下進(jìn)行計(jì)算,對(duì)比在不同的α和β組合情況下,影響值I的變化范圍,實(shí)驗(yàn)結(jié)果如圖2～圖4所示。由圖2可知,以時(shí)間占用為重點(diǎn),0.8≤β≤0.9時(shí),影響值I的變化情況最為明顯。由圖3可知,以空間占用為重點(diǎn),0.8≤α≤0.9時(shí),影響值I的變化情況最為明顯。由圖4可知,以數(shù)據(jù)量較大的Test_70w_6數(shù)據(jù)集為例,隨著權(quán)值比例的降低,時(shí)間與空間之間的影響值I差值越來(lái)越小。根據(jù)文件大小及解析時(shí)間的差值分析,權(quán)重過(guò)大會(huì)導(dǎo)致結(jié)果不穩(wěn)定。

圖2 以時(shí)間占用為重點(diǎn)時(shí)的影響值I

圖3 以空間占用為重點(diǎn)時(shí)的影響值I

圖4 在數(shù)據(jù)集Test_70w_6上影響值I的變化

經(jīng)過(guò)多次比對(duì),以空間為重點(diǎn)時(shí),本文選取α=0.85,β=0.15進(jìn)行后續(xù)實(shí)驗(yàn),以時(shí)間為重點(diǎn)時(shí),本文選取α=0.15,β=0.85進(jìn)行后續(xù)實(shí)驗(yàn)。

4.3.2 數(shù)據(jù)量對(duì)解析方法的影響

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

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

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

從圖5和圖6可得出以下結(jié)論:

1)隨著數(shù)據(jù)量n的增大,4種解析方法所花費(fèi)的時(shí)間均增加,并且數(shù)據(jù)量n越大,4種解析方法的差距越小,因此本文主要針對(duì)數(shù)據(jù)量n增大的情況進(jìn)行后續(xù)實(shí)驗(yàn)。

2)當(dāng)數(shù)據(jù)量n低于35萬(wàn)條時(shí),DOM解析方法的影響值I比DOM4J解析方法高,數(shù)據(jù)量繼續(xù)增大至高于35萬(wàn)條時(shí),DOM4J解析方法的影響值I逐漸高于DOM解析方法,且始終比DOM解析方法的影響值I高。在時(shí)間和空間加權(quán)值比重相同時(shí),DOM4J解析方法在35萬(wàn)條～70萬(wàn)條數(shù)據(jù)量時(shí)最優(yōu)。

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

實(shí)驗(yàn)結(jié)果表明,時(shí)間和空間加權(quán)值分配一致即不考慮時(shí)間空間影響時(shí),當(dāng)數(shù)據(jù)量n較小時(shí),DOM解析方法具有很高的效率,繼續(xù)增大數(shù)據(jù)量n時(shí),該解析方法的效率反而降低,這是因?yàn)镈OM解析方法采用的是樹節(jié)點(diǎn)遍歷全文的方式對(duì)文檔解析,當(dāng)數(shù)據(jù)量n較大時(shí),建立樹節(jié)點(diǎn)的時(shí)間會(huì)大幅增加,會(huì)造成效率變差,影響值I降低。

當(dāng)數(shù)據(jù)量n較小時(shí),從影響值I大小的角度分析,SAX解析方法的時(shí)間占用相對(duì)空間占用比其他3種解析方法多,且效果最差,當(dāng)數(shù)據(jù)量n增大時(shí),效率逐漸升高,且幅度較大。這是因?yàn)镾AX解析方法采用的是流式處理文件的方式,逐行解析可以隨時(shí)停止,不耗費(fèi)空間資源,因此當(dāng)數(shù)據(jù)量n增大時(shí),影響值I會(huì)相對(duì)其他解析方法升高。

JDOM解析方法的影響值I隨著數(shù)據(jù)量n的增大呈降低趨勢(shì),這是因?yàn)楫?dāng)數(shù)據(jù)量n增大時(shí),在空間資源相差不大的情況下,JDOM解析方法耗費(fèi)的時(shí)間遠(yuǎn)大于其他3種解析方法。

DOM4J解析方法的影響值I隨著數(shù)據(jù)量n的增大呈升高趨勢(shì),這是因?yàn)殡m然DOM4J解析方法采用獲取根節(jié)點(diǎn)的方式遍歷其子節(jié)點(diǎn)和屬性,但是處理過(guò)程中可以根據(jù)接口選擇SAX讀取器,因此相對(duì)其他3種解析方法,其處理方式更快。

4.3.3 屬性個(gè)數(shù)對(duì)解析方法的影響

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

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

圖8 4種解析方法在數(shù)據(jù)集Test_70w_6中的影響值I

從圖7和圖8可以得出以下結(jié)論:

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

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

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

實(shí)驗(yàn)結(jié)果表明,當(dāng)數(shù)據(jù)量n不大時(shí),屬性個(gè)數(shù)的變化對(duì)結(jié)果的影響是非穩(wěn)定性因素;當(dāng)數(shù)據(jù)量n增大時(shí),屬性的變化對(duì)結(jié)果的影響是穩(wěn)定性因素。因?yàn)樵跀?shù)據(jù)量n較小時(shí),無(wú)論是解析空間還是解析時(shí)間,受實(shí)驗(yàn)環(huán)境的影響,限制條件被忽略,干擾性增強(qiáng),當(dāng)數(shù)據(jù)量n增大后,實(shí)驗(yàn)環(huán)境的影響對(duì)處理事件所耗費(fèi)的時(shí)間干擾性減弱。由此表明,在不考慮時(shí)間和空間為重點(diǎn)并且數(shù)據(jù)量n較大的條件下,當(dāng)屬性個(gè)數(shù)增加時(shí),影響值I降低,當(dāng)屬性個(gè)數(shù)減少時(shí),影響值I升高。

4.3.4 縮短時(shí)間為重點(diǎn)時(shí)不同解析方法對(duì)比

本文實(shí)驗(yàn)將以α=0.15,β=0.85分別賦予空間和時(shí)間加權(quán)值。當(dāng)考慮縮短時(shí)間為重點(diǎn)時(shí),在數(shù)據(jù)集Test_70w_6上,對(duì)比4種解析方法影響值I的變化情況,并表示出該權(quán)重比與權(quán)重比為1時(shí)的差值,此差值表示為函數(shù)以時(shí)間為重點(diǎn)價(jià)值取向時(shí)的突出程度,結(jié)果如圖9和圖10所示。

圖9 在數(shù)據(jù)集Test_70w_6中以時(shí)間為重點(diǎn)的4種解析方法的比較

圖10 4種解析方法的權(quán)重比差值比較

從圖9和圖10可以得出以下結(jié)論:

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

2)在差值對(duì)比分析過(guò)程中,JDOM解析方法的差值最高(-0.017 67),說(shuō)明在縮短數(shù)據(jù)解析時(shí)間上,JDOM解析方法的時(shí)間開(kāi)銷最大。

實(shí)驗(yàn)結(jié)果表明,DOM4J解析方法適用于以縮短解析時(shí)間為重點(diǎn)的實(shí)驗(yàn)環(huán)境。在實(shí)際的XML文本解析中,在實(shí)驗(yàn)條件較好且數(shù)據(jù)量n較大的情況下,DOM4J解析方法的性價(jià)比最高,且實(shí)用性很強(qiáng)。

4.3.5 占用空間為重點(diǎn)時(shí)不同解析方法對(duì)比

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

圖11 以空間為重點(diǎn)時(shí)的SAX和DOM解析方法的比較

從圖11可以得出以下結(jié)論:

1)以占用空間為重點(diǎn)時(shí),以DOM解析方法的樹形結(jié)構(gòu)方式空間占用比大于用SAX解析方法的流式處理文件結(jié)構(gòu),且在數(shù)據(jù)量n為70萬(wàn)條時(shí),平均堆內(nèi)存空間占用差值為126 MB。

2)以樹結(jié)構(gòu)的存儲(chǔ)數(shù)據(jù)的方式堆空間占用是流式文件處理方式的堆空間占用的1.52倍。

實(shí)驗(yàn)結(jié)果表明,當(dāng)數(shù)據(jù)量n增大時(shí),若考慮以空間占用為重點(diǎn)的實(shí)驗(yàn)環(huán)境,則采用SAX解析方法效果最好。

5 結(jié)束語(yǔ)

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