嵌入式HTML文檔解析器的設(shè)計(jì)與實(shí)現(xiàn)

1、第卷場(chǎng)正第期計(jì)算機(jī)工程年月文獻(xiàn)標(biāo)識(shí)碼：開(kāi)發(fā)研究與設(shè)計(jì)技術(shù)文章編號(hào)（）爭(zhēng)卅番珈中圖分類(lèi)號(hào)：嵌入式文檔解析器的設(shè)計(jì)與實(shí)現(xiàn)李慶誠(chéng)，彭潔，宮曉利，劉嘉欣（南開(kāi)大學(xué)信息技術(shù)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，天津）要：針對(duì)文檔在手持移動(dòng)閱讀設(shè)備上的閱讀有效性問(wèn)題，設(shè)計(jì)實(shí)現(xiàn)一種面向嵌入式應(yīng)用的、平臺(tái)無(wú)關(guān)的文檔解析器，對(duì)其關(guān)鍵技術(shù)進(jìn)行闡述和分析。提出一種屏幕適配探測(cè)機(jī)制，實(shí)現(xiàn)對(duì)當(dāng)前屏幕閱讀無(wú)效內(nèi)容的過(guò)濾。實(shí)驗(yàn)結(jié)果表明，該解析器降低了對(duì)嵌入式系統(tǒng)處理能力與內(nèi)存配置的要求，能滿足手持閱讀設(shè)備的需要。關(guān)黼：嵌入式；文檔；解析器；屏幕適配探測(cè)；手持閱讀設(shè)備，）（，船，（），；（）；概述隨著瓦聯(lián)網(wǎng)的高速發(fā)展和各種數(shù)字技術(shù)的不

2、斷進(jìn)步，信息數(shù)字化浪潮席卷全球。文檔作為應(yīng)用最為廣泛的互聯(lián)網(wǎng)信息載體，大多數(shù)都采用（文檔中合法有效的成分。針對(duì)面向屏幕顯示的嵌入式應(yīng)用，解析器的主要工作是將構(gòu)成文檔的基本元素（稱為顯示對(duì)象，包括文字、直線、圖片等）提取出來(lái)，并進(jìn)行合理的組織排版，最終顯示在屏幕上。因此，對(duì)于文檔中可能包含的一些服務(wù)器端腳本（如和腳本），以及不同的用戶代理對(duì)于標(biāo)準(zhǔn)的擴(kuò)展，解析器均予以忽略。解析架構(gòu)本解析器由詞法語(yǔ)法分析模塊、排版控制模塊、屏幕顯示模塊、多頁(yè)面緩沖模塊部分組成，層次結(jié)構(gòu)如圖所示。屏幕顯示模塊）語(yǔ)言書(shū)寫(xiě)而成。消費(fèi)電子、計(jì)算機(jī)、通信一體化趨勢(shì)日趨明顯，嵌入式技術(shù)成為研究熱點(diǎn)，其中手持閱讀設(shè)備的快速發(fā)展，

3、使得格式的文檔在這些設(shè)備上的閱讀有效性問(wèn)題日益顯現(xiàn)。在文檔解析領(lǐng)域，已經(jīng)有大量的研究工作，其中最具普遍性的設(shè)計(jì)思想是采用對(duì)象樹(shù)模型（，）來(lái)表示文件的內(nèi)部結(jié)構(gòu)。在對(duì)象樹(shù)模型中，網(wǎng)頁(yè)中的標(biāo)簽按嵌套關(guān)系被整理成一棵樹(shù)狀結(jié)構(gòu)，諸如字體大小、顏色等屬性均被保存在每個(gè)節(jié)點(diǎn)中。對(duì)象樹(shù)模型作為組織頁(yè)面內(nèi)部數(shù)據(jù)的標(biāo)準(zhǔn)形式，被用于當(dāng)前流行的測(cè)覽器中。但在嵌入式應(yīng)用中，采用方法對(duì)整個(gè)文件進(jìn)行完整解析后再排版、顯示，對(duì)系統(tǒng)動(dòng)態(tài)內(nèi)存空間的要求過(guò)高，有可能在解析環(huán)節(jié)由于內(nèi)存不足造成系統(tǒng)崩潰，因此，該方法并不完全適用于嵌入式應(yīng)用。本文提出一種新的文檔解析器設(shè)計(jì)方法屏幕適配探測(cè)（，）法。該方法打破了模型中必須先進(jìn)行完整解析后

4、再排版顯示的舊有思路，將排版環(huán)節(jié)確立為解析工作的控制中心，對(duì)目標(biāo)顯示區(qū)域外的內(nèi)容進(jìn)行過(guò)濾，實(shí)現(xiàn)了有針對(duì)性的解析。詞法語(yǔ)法分析模塊排版孛制模塊圈。解析詞法語(yǔ)法分析模塊按照語(yǔ)言規(guī)范識(shí)別標(biāo)簽以及標(biāo)簽之間的內(nèi)容，每個(gè)標(biāo)簽都有對(duì)應(yīng)的處理函數(shù)，由處理數(shù)生成顯示對(duì)象。詞法語(yǔ)法分析模塊是解析工作的基礎(chǔ)，被排版控制模塊反復(fù)調(diào)用。排版控制模塊在解析器系統(tǒng)架構(gòu)中處于中心的地位。它基金嘎目：天津市科技發(fā)展計(jì)劃基金資助項(xiàng)目（）作者筲介：李慶誠(chéng)（一），男，教授、博士、博：生導(dǎo)師，主研方向：電子閱讀平臺(tái)，數(shù)字版權(quán)保護(hù)，嵌入式數(shù)據(jù)庫(kù)，中間傳；彭潔，碩上研究生；宮曉利，博士研究生；劉嘉欣，工程師、碩士收穡日期：蚰：文檔解析器設(shè)

5、計(jì)概要解析的一般考慮解析的過(guò)程是將文檔的流式數(shù)據(jù)結(jié)構(gòu)化的過(guò)程”，它并不以發(fā)現(xiàn)和糾正文檔的語(yǔ)法錯(cuò)誤為目的，而是要盡量忽略遇到的語(yǔ)法錯(cuò)誤，最大程度地解析出一萬(wàn)方數(shù)據(jù)負(fù)責(zé)調(diào)用詞法語(yǔ)法分析模塊生成顯示對(duì)象，并對(duì)顯示對(duì)象進(jìn)行排版，將其中有效的顯示對(duì)象送入屏幕顯示模塊。排版控制模塊協(xié)調(diào)解析器的運(yùn)行，這是實(shí)現(xiàn)方法的關(guān)鍵。屏幕顯示模塊實(shí)現(xiàn)了與具體系統(tǒng)相關(guān)的屏幕顯示接口調(diào)用。屏幕顯示模塊與其他模塊相互獨(dú)立，針對(duì)不同的，只須相應(yīng)改變的函數(shù)，而無(wú)須改變內(nèi)部的解析調(diào)用機(jī)制，實(shí)現(xiàn)了解析過(guò)程與顯示過(guò)程相分離，使解析器能夠快速移植到不同的系統(tǒng)下。多頁(yè)面緩沖模塊是一個(gè)可裁減的功能模塊，負(fù)責(zé)管理頁(yè)面位圖緩沖區(qū)，緩沖區(qū)中存放著與

6、當(dāng)前屏幕請(qǐng)求頁(yè)面最鄰近的頁(yè)面佗圖，當(dāng)用戶改變當(dāng)前屏幕請(qǐng)求頁(yè)面（如通過(guò)翻頁(yè)操作）時(shí)，多頁(yè)面緩沖模塊將更新緩沖區(qū)中的頁(yè)面位圖，總保持對(duì)用戶下一操作的高命中率。解析器的工作漉程解析器的工作流程如下：（）解析器將文件讀入內(nèi)存（對(duì)于較大的文件采用分塊讀入的方法），調(diào)用詞法語(yǔ)法分析模塊對(duì)文件字符流進(jìn)行分析。分析的具體過(guò)程包括：從字符流中識(shí)別出標(biāo)簽并進(jìn)入相應(yīng)的標(biāo)簽處理函數(shù)，在處理函數(shù)中修改屬性狀態(tài)和生成顯示對(duì)象。詞法語(yǔ)法分析的過(guò)程就是一個(gè)邊提取標(biāo)簽邊分析整合，最終生成顯示對(duì)象的過(guò)程。（）排版控制模塊接收到顯示對(duì)象后，根據(jù)當(dāng)前屏幕游標(biāo)的位置，計(jì)算出該顯示對(duì)象在版面上的絕對(duì)坐標(biāo)，從而判斷出該顯示對(duì)象是否落入目標(biāo)

7、顯示區(qū)域內(nèi)，所有落入目標(biāo)顯示區(qū)域的顯示對(duì)象均為有效顯示對(duì)象。（）對(duì)于有效顯示對(duì)象，排版控制模塊將調(diào)用屏幕顯示模塊，將顯示對(duì)象的內(nèi)容（如文字、直線、圖片）填入目標(biāo)顯示區(qū)域，隨后調(diào)用詞法語(yǔ)法分析模塊繼續(xù)解析；而對(duì)于無(wú)效顯示對(duì)象，排版控制模塊將對(duì)目標(biāo)顯示區(qū)域進(jìn)行探測(cè)，當(dāng)發(fā)現(xiàn)目標(biāo)顯示區(qū)域已填滿，則停止解析并轉(zhuǎn)去屏幕顯示。關(guān)鍵問(wèn)題及解決方案表格的處理表格承擔(dān)著設(shè)計(jì)排版文檔的重要功能，表格的處理一直是解析工作的重點(diǎn)怕。表格結(jié)構(gòu)可視作一個(gè)封閉的塊，由若干個(gè)小的單元塊組成。解析器將表格視作一個(gè)獨(dú)立對(duì)象，圖是系統(tǒng)中定義的表格對(duì)象的數(shù)據(jù)結(jié)構(gòu)。一葉亟悃圈表格對(duì)象的敦?fù)?jù)鰭鞠當(dāng)遇到表格對(duì)象，詞法語(yǔ)法分析模塊將對(duì)表格起始

8、標(biāo)簽萬(wàn)方數(shù)據(jù)和表格結(jié)束標(biāo)簽之間的內(nèi)容進(jìn)行次掃描分析。第次掃描利用，等標(biāo)簽的屬性獲取表格結(jié)構(gòu)，并且記錄每一個(gè)單元格的寬度、高度和單元格內(nèi)包含的文字。第次掃描對(duì)取得的結(jié)構(gòu)進(jìn)行分析和定位，利用語(yǔ)言中關(guān)千內(nèi)層標(biāo)簽?zāi)J(rèn)繼承外層標(biāo)簽屬性的規(guī)定，對(duì)屬性信息不完整的單元格進(jìn)行信息補(bǔ)全。經(jīng)過(guò)次掃描，解析器得到了清晰完整的表格結(jié)構(gòu)，并交由排版控制模塊處理。性狀態(tài)棧的使用語(yǔ)言中規(guī)定，系統(tǒng)的顯示屬性（如字體大小、顏色、對(duì)齊方式等）具有可繼承性和叮還原性，可繼承性是指如果當(dāng)前層標(biāo)簽沒(méi)有顯式地注明屬性值，則它將默認(rèn)繼承外層標(biāo)簽的屬性；可還原性是指如果當(dāng)前層標(biāo)簽修改了屬性值，則修改后的屬性值只在當(dāng)前層標(biāo)簽起始的范圍內(nèi)有效，

9、遇到匹配的結(jié)束標(biāo)簽時(shí)要將系統(tǒng)屬性值還原到修改之前的狀態(tài)。針對(duì)必須對(duì)屬性值進(jìn)行嵌套繼承、還原這些特點(diǎn)，解析器使用棧這種數(shù)據(jù)結(jié)構(gòu)來(lái)記錄屬性信息，并為棧元素定制了如圖所示的數(shù)據(jù)結(jié)構(gòu)。圈一性狀態(tài)棧的據(jù)結(jié)構(gòu)棧頂元素中總保存著當(dāng)前系統(tǒng)正在處理的顯示對(duì)象的屬性值。當(dāng)解析遇到標(biāo)簽引發(fā)系統(tǒng)屬性值發(fā)生改變時(shí)（如標(biāo)簽改變了當(dāng)前字符的顏色），解析器將對(duì)棧頂元素進(jìn)行復(fù)制，修改相應(yīng)屬性值后壓入棧中，成為新的棧頂元素，這樣既完成了當(dāng)前系統(tǒng)屬性值的改變，又保存了修改前的屬性值；當(dāng)屬性狀態(tài)需要還原時(shí)（如遇到對(duì)應(yīng)的標(biāo)簽），只須將新的棧頂元素出棧即可。屏幕適配探測(cè)方法的實(shí)現(xiàn)手持閱讀設(shè)備的屏幕顯示需要大量浮點(diǎn)運(yùn)算，這是時(shí)間消耗的主要

10、原因，因此，為了高效地顯示目標(biāo)頁(yè)面，解析器需要對(duì)目標(biāo)頁(yè)面之外的顯示對(duì)象進(jìn)行過(guò)濾。定義文檔的全部頁(yè)面為樣本空問(wèn)，其中目標(biāo)頁(yè)面所占的區(qū)域?yàn)槠聊豢臻g。屏幕匹配探測(cè)方法通過(guò)計(jì)算顯示對(duì)象在樣本空間中的坐標(biāo)，判斷其是否落入屏幕空間，對(duì)落入屏幕空間之外的顯示對(duì)象進(jìn)行過(guò)濾，并在適當(dāng)?shù)臅r(shí)候?qū)ζ聊豢諉?wèn)是否已填滿進(jìn)行探測(cè)。實(shí)現(xiàn)屏幕適配探測(cè)方法的關(guān)鍵是排版控制模塊，屏幕適配探測(cè)的流程如圖所示。在詞法語(yǔ)法分析模塊生成一個(gè)顯示對(duì)象后，解析器并不立即調(diào)用顯示，而是先將該顯示對(duì)象送入排版控制模塊，排版控制模塊利用顯示對(duì)象附帶的屬性信息（如對(duì)齊屬性），計(jì)爭(zhēng)一算出該顯示對(duì)象在樣本空間中的坐標(biāo)，從而可以判斷出該顯示對(duì)象是否落入屏幕

11、空間，決定是否將該顯示對(duì)象送入屏幕顯示模塊。圈屏幕適配探測(cè)的藏程顯示對(duì)象在樣本空間中的位置與屏幕空間共存在種相互關(guān)系，如圖所示。其中，對(duì)象與對(duì)象同屬落入屏幕空間外的情況，為無(wú)效內(nèi)容；對(duì)象、對(duì)象、對(duì)象均部分或全部落入屏幕宅間，為有效內(nèi)容，所不同的是對(duì)象、對(duì)象只需顯示落入屏幕空間的部分即可。對(duì)象完全落入屏幕空間之外，且縱坐標(biāo)大于屏幕牢問(wèn)的下邊界，因此，可以作為屏幕請(qǐng)求已完成的標(biāo)志，當(dāng)解析器遇到對(duì)象時(shí)，即可結(jié)束對(duì)目標(biāo)頁(yè)面的解析，完成屏幕顯示。彤像素懈毯釜顯示對(duì)象樣車(chē)空問(wèn)屏幕空間圈顯示對(duì)象在樣本空闊中曲位置關(guān)系本解析器采用標(biāo)準(zhǔn)語(yǔ)言編寫(xiě)，擁有獨(dú)立的文字處理和圖形圖像渲染引擎，具有良好的跨平臺(tái)性，目前在、

12、等系統(tǒng)臺(tái)上運(yùn)行良好，且已被用于某商業(yè)化手持電子閱讀器。在主頻、內(nèi)存的運(yùn)行條件下，以隨機(jī)選取的中文新聞?lì)惥W(wǎng)頁(yè)為樣本，對(duì)使用方法前后，顯示同一頁(yè)面所需的顯示調(diào)用次數(shù)、解析時(shí)間以及內(nèi)存占用情況進(jìn)行了統(tǒng)計(jì)，如表所示。顯示調(diào)用的過(guò)程通常會(huì)占用大量的動(dòng)態(tài)內(nèi)存窄間，例如生成矢量字庫(kù)中的字模、調(diào)用圖片庫(kù)解析圖片等。方法從機(jī)制上避免了所有在目標(biāo)顯示區(qū)域外的顯示調(diào)用，節(jié)省了大量系統(tǒng)資源，降低解析器對(duì)系統(tǒng)動(dòng)態(tài)內(nèi)存空間的要求，一伊一萬(wàn)方數(shù)據(jù)并加快了解析速度。圖是某樣本在手持閱讀設(shè)備上的解析實(shí)例。表豆示弭用次致、解析時(shí)問(wèn)及內(nèi)存占用的統(tǒng)計(jì)結(jié)果圈萊樣本在手持閱讀設(shè)魯上曲解析實(shí)倒文檔是互聯(lián)網(wǎng)應(yīng)用最廣泛的信息載體，在嵌入式設(shè)備

13、上實(shí)現(xiàn)對(duì)文檔的解析具有很重要的意義?；谝话闱度胧皆O(shè)備處理能力低、可用內(nèi)存空間小的特點(diǎn)，本文提出一種新的文檔解析器設(shè)計(jì)方法，實(shí)現(xiàn)了有針對(duì)性的解析，降低了解析器對(duì)嵌入式系統(tǒng)動(dòng)態(tài)內(nèi)存空間的要求，可適用于手持閱讀設(shè)備。參考文獻(xiàn)【】，【一：【】李效東，顧毓清基于的信息提取計(jì)算機(jī)學(xué)報(bào)，（）：【】王強(qiáng)，王繼成，武港山，等文檔清洗系統(tǒng)中解析器的開(kāi)發(fā)計(jì)算機(jī)應(yīng)用研究，（）：【】李慶誠(chéng)劉永超，劉嘉欣平臺(tái)無(wú)關(guān)的嵌入式高性價(jià)比解析器設(shè)計(jì)與實(shí)現(xiàn)】計(jì)算機(jī)應(yīng)用，（增刊）：【】于滿泉，陳鐵睿，許洪波基于分塊的網(wǎng)頁(yè)信息解析器的研究與設(shè)計(jì)【】計(jì)算機(jī)應(yīng)用，（）：【伍星王茜設(shè)計(jì)模式在解析器中的應(yīng)用【】計(jì)算機(jī)工程，（）： 編輯顧姣健結(jié)

14、束語(yǔ) 嵌入式HTML文檔解析器的設(shè)計(jì)與實(shí)現(xiàn)作者：作者單位：刊名：英文刊名：年，卷(期：被引用次數(shù)：李慶誠(chéng)， 彭潔， 宮曉利， 劉嘉欣， LI Qing-cheng， PENG Jie， GONG Xiao-li， LIU Jia-xin南開(kāi)大學(xué)信息技術(shù)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系,天津,300071計(jì)算機(jī)工程COMPUTER ENGINEERING2009,35(91次參考文獻(xiàn)(6條1. 于滿泉;陳鐵睿;許洪波 基于分塊的網(wǎng)頁(yè)信息解析器的研究與設(shè)計(jì)期刊論文-計(jì)算機(jī)應(yīng)用 2005(042. 李慶減;劉永超;劉嘉欣 平臺(tái)無(wú)關(guān)的PDF嵌入式高性價(jià)比解析器設(shè)計(jì)與實(shí)現(xiàn)期刊論文-計(jì)算機(jī)應(yīng)用 2007(zk3. 伍星;王茜 設(shè)計(jì)模式在HTML解析器中的應(yīng)用期刊論文-計(jì)算機(jī)工