董 欣

（沈陽師范大學計算機與數學基礎教學部，遼寧 沈陽 110034）

1 概述

對XML文檔的編碼，是指按照某種規(guī)則對XML文檔樹中的每一個結點分配唯一的編碼，目的是通過任意兩個結點的編碼，能夠直接判斷出兩個結點之間的結構關系，進而能夠高效地支持對XML數據的索引和查詢。

2 起止編碼

起止編碼采用深度優(yōu)先遍歷XML文檔中所有結點，每個結點用三元組（start，end，level）表示。用level代表結點在文檔樹中的層次。這樣由start，end，level構成了一個三元組（start，end，level）來代表一個文檔結點。對XML文檔的每個結點依次分配這樣的三元組編碼，就是對XML文檔的起止編碼。同區(qū)域編碼一樣，起止編碼很容易通過前兩個元素判斷出文檔結點間的祖先/后代、父親/孩子關系，所以能夠在XML文檔索引和查詢中起到重要的作用。

對于給定的XML文檔中的兩個結點m、n，其對應的起止編碼分別為Cm=（m.start，m.end，m.level）、Cn=（n.start，n.end，n.level），當m.start < n.start

3 XML文檔的新起止編碼方案及實現算法

3.1 新起止（Start-End-Type Coding）編碼方案

為了在查詢過程中不但能判斷出文檔結點間的祖先/后代、父親/孩子關系，還要能識別出XML文檔中各結點的類型，本文提出了對XML文檔的起止編碼。起止編碼是在起止編碼的基礎上，把起止編碼表示結點的三元組（start，end，level）改進為四元組（start，end，level，type），其中第四個元素type代表該結點的類型。根據文獻[30,31]，結點類型可分為4種：實體結點、屬性結點、葉子結點和連接結點。具體定義如下：

實體結點：DTD中帶*的結點或含有多個屬性的結點。屬性結點：只含有一個值結點的結點。

葉子結點：屬性的值結點（葉子結點不做起止編碼）。

連接結點：如果一個結點不是實體結點，屬性結點，葉子結點即為連接結點

這樣，根據起止編碼不僅可以判斷Twig查詢樹及XML文檔中結點之間的關系，而且還能識別出每個結點的類型，為支持對XML文檔進行柔性查詢提供條件。

3.2 起止編碼實現算法

起止編碼四元組中前三個元素的編碼與起止編碼的編碼思想基本相同，但本文提出了計算前三個元素值的新算法，而四元組中的type元素值是按照上述XML文檔結點分類方法并根據四元組中的前3個編碼值計算出來的。

當計算得出起止編碼的前3個元素的值后，就可以根據這三個元素的值自動計算出第4個元素type的值，即結點的類型。

綜上所述，起止編碼可以分為計算start，end值；level值；type值3個部分，具體的起止算法如下：

算法：XML文檔起止編碼

輸入：XML文檔；輸出：XML文檔的起止編碼

//計算起止編碼前3個元組，start，end，level編碼

讀取XML文檔元素標簽

If（qName是元素開始標簽）{

tagsStack.push（qName）//結點名稱入堆棧

入棧元素開始編碼設為i=i+1；元素讀取指針深度設為j=j+1；

Hashmap.put(qName,estart)；//把元素開始標簽編碼存入hashmap中//處理屬性，屬性也是XML文檔樹的一個結點，也需要編碼

int len=attrs.getLength()；

for (int k=0;k

{i=i+2；//屬性結點也是元素的一個分支，占兩個編碼

String attrsname=(String)attrs.getQName(k)；

//屬性結點可以直接放入indenhashmap中

int start=i-1；//開始編碼

int end=i；//終止編碼

int level=j+1；//結點的層次

inputhashmap(attrsname,start,end,level)；

If（qName是元素結束標簽）

本算法是根據起止編碼的前三個元素（start,end,level）的值計算出第四個元素type的值。主要通過函數inputhashmap（）來計算實體的匹配結點，而結點的匹配用堆棧技術來實現的。

4 結束語

本章主要介紹了對XML文檔的新起止編碼，不僅很容易判斷出文檔結點間的祖先/后代、父親/孩子關系及結點之間的層次關系，還可以根據type元組的值快速地判斷出XML文檔中各結點的類型，使它能夠對XML文檔進行柔性查詢提供編碼上的支持。