不同時(shí)間戳的地圖差異匹配改進(jìn)算法

杜慶峰，趙亞男

（同濟(jì)大學(xué) 軟件學(xué)院，上海201804）

可升伸縮矢量圖形（SVG）是一種使用XML 來描述二維圖形及其應(yīng)用的語言.一個(gè)SVG 文檔可以被解析成一棵倒立的樹形結(jié)構(gòu)，與XML文檔的差異匹配算法類似.XML文檔的差異匹配算法可以分為3類：第1類是針對有序節(jié)點(diǎn)樹的差異匹配算法，第2類是針對無序節(jié)點(diǎn)樹的差異匹配算法，第3類算法不是將XML結(jié)構(gòu)樹中所有節(jié)點(diǎn)看作有序節(jié)點(diǎn)或者全部看作無序節(jié)點(diǎn).

針對有序節(jié)點(diǎn)樹，Cobena等［1］提出了一種檢測XML文檔變化算法XyDiff.該算法首先采用自底向上的方式計(jì)算每個(gè)結(jié)點(diǎn)的簽名（hash值）和權(quán)重（子樹的大?。?，然后從2個(gè)文檔的根結(jié)點(diǎn)開始比較2個(gè)結(jié)點(diǎn)的簽名.由于在算法中使用了貪婪規(guī)則，XyDiff不能保證任何形式的最優(yōu)和近似最優(yōu)的匹配檢測.該算法的時(shí)間復(fù)雜度為O（nh），其中n為節(jié)點(diǎn)個(gè)數(shù)，h為樹的高度.

針對無序節(jié)點(diǎn)樹，Wang 等［2］提出了X－Diff算法，該算法采用自頂向下的匹配機(jī)制，對XML 結(jié)構(gòu)樹進(jìn)行“最小修改代價(jià)”搜索匹配，該算法是針對無序節(jié)點(diǎn)樹的匹配檢測最快的算法.該算法的時(shí)間復(fù)雜度為O（n2dlgd），其中d為最大深度.

第3種算法是由Al－Ekram 等［3］提出 的DiffX算法，該算法根據(jù)節(jié)點(diǎn)的不同類型將其分為元素節(jié)點(diǎn)、屬性節(jié)點(diǎn)和文本節(jié)點(diǎn)，DiffX 算法將元素節(jié)點(diǎn)看成有序節(jié)點(diǎn)而將屬性節(jié)點(diǎn)看成無序節(jié)點(diǎn)，這樣的數(shù)據(jù)模型更符合XML文檔的性質(zhì).該算法的時(shí)間復(fù)雜度為O（n2）.

現(xiàn)有的DiffS［4］算法是在DiffX 算法的基礎(chǔ)上定義宏元素節(jié)點(diǎn)，以元素節(jié)點(diǎn)或宏元素節(jié)點(diǎn)作為最小匹配 元 素，創(chuàng) 建2 個(gè) 以｛id：String，et：String，e：Element｝為元素的數(shù)組E1，E2.該算法的時(shí)間復(fù)雜度降低至O（nlgn）.

在現(xiàn)有的DiffS算法中，數(shù)組E1，E2 中的元素個(gè)數(shù)太多，導(dǎo)致數(shù)組排序和查找的時(shí)間太長.另外，對于數(shù)組中的每個(gè)元素節(jié)點(diǎn)，它們的屬性字符串太長，導(dǎo)致屬性排序的時(shí)間也太長.

考慮到現(xiàn)有研究存在的不足，可以重新定義宏元素節(jié)點(diǎn)，提出一種新的元素節(jié)點(diǎn)：節(jié)點(diǎn)集元素，達(dá)到減少數(shù)組元素個(gè)數(shù)、降低數(shù)組排序和查找時(shí)間的目的.另外，通過一種標(biāo)號定義規(guī)則來重新標(biāo)識SVG結(jié)構(gòu)樹，使得屬性字符串的長度大大縮短，達(dá)到減少屬性排序時(shí)間的目的.

1 改進(jìn)算法I－DiffS的思想及實(shí)現(xiàn)

1.1 I－DiffS算法思想

1.1.1 相關(guān)定義

（1）節(jié)點(diǎn)集元素.在某時(shí)間戳的SVG 格式地圖對應(yīng)的倒?fàn)罱馕觯?］結(jié)構(gòu)樹中，從根節(jié)點(diǎn)開始將某特定的分支中的元素節(jié)點(diǎn)、屬性節(jié)點(diǎn)和值節(jié)點(diǎn)看成一個(gè)整體，稱為節(jié)點(diǎn)集元素.如某id為c2的節(jié)點(diǎn)集元素，它的元素節(jié)點(diǎn)集合為｛I，J，J，C｝，屬性節(jié)點(diǎn)為“SY”，值節(jié)點(diǎn)為“rgb（0，255，255）60”.

（2）倒?fàn)罱馕鼋Y(jié)構(gòu)樹標(biāo)號規(guī)則.在SVG 格式地圖中主要包括基本圖形元素集｛line，rect，circle，eclipse，polyine，polygon，path，text｝，常見框架元素集｛SVG，g，defs，use，symbol，desc，title，image｝，常用屬性元素集｛x，y，r，rx，ry，width，height，stroke／style，fill，tspan｝.共有26個(gè)主要基本元素，可以用1位大寫字母標(biāo)識，在這26個(gè)主要基本元素之外的元素可用1位小寫字母標(biāo)識，如果1位字母標(biāo)識完畢，可采用2位或多位字母標(biāo)識，以此類推.

按照倒裝解析結(jié)構(gòu)樹的標(biāo)號定義規(guī)則，主要基本元素的標(biāo)號定義如表1.

1.1.2 算法思路和實(shí)現(xiàn)

（1）優(yōu)化后的解析結(jié)構(gòu)樹.將原SVG 文件通過節(jié)點(diǎn)集元素的定義來得到一棵SVG［6］節(jié)點(diǎn)集元素結(jié)構(gòu)樹，之后再根據(jù)倒裝解析樹的標(biāo)號定義規(guī)則將SVG 節(jié)點(diǎn)集元素結(jié)構(gòu)樹轉(zhuǎn)化成優(yōu)化后的標(biāo)號節(jié)點(diǎn)集元素結(jié)構(gòu)樹.

表1 SVG 格式地圖主要基本元素的標(biāo)號定義Tab.1 Labeling rule of major basic labeling rule of major basic element on SVG map

（2）生成匹配節(jié)點(diǎn)集元素集合M.首先對SVG［7］格式地圖文檔對應(yīng)的結(jié)構(gòu)樹中的屬性元素節(jié)點(diǎn)（除id屬性外）按字典順序排列，該屬性元素節(jié)點(diǎn)對應(yīng)的值節(jié)點(diǎn)按照排序好的屬性元素節(jié)點(diǎn)順序排列.如，一個(gè)屬性元素節(jié)點(diǎn)排序前為“SWV”，排序后為“SVW”，則值元素節(jié)點(diǎn)為“none100100”.

接著創(chuàng)建2個(gè)以節(jié)點(diǎn)集元素為元素的數(shù)組E1，E2；E1 中數(shù)組個(gè)數(shù)等于第1 個(gè)版本SVG 格式地圖［8］對應(yīng)的樹結(jié)構(gòu)中節(jié)點(diǎn)集元素的個(gè)數(shù)m1，同理E2中數(shù)組個(gè)數(shù)等于第2個(gè)版本SVG 格式地圖對應(yīng)的樹結(jié)構(gòu)中節(jié)點(diǎn)集元素的個(gè)數(shù)m2.

數(shù)組E1和E2 中元素的屬性由以下6 部分構(gòu)成：第1個(gè)字符串是節(jié)點(diǎn)集元素的id值；第2個(gè)字符串是節(jié)點(diǎn)集元素的元素節(jié)點(diǎn)所組成的字符串path；第3個(gè)字符串是節(jié)點(diǎn)集元素的屬性節(jié)點(diǎn)所組成的字符串et；第4個(gè)字符串是節(jié)點(diǎn)集元素的值節(jié)點(diǎn)所組成的字符串value；第5個(gè)指針用來記錄所對應(yīng)的節(jié)點(diǎn)集元素的指針e；第6個(gè)是用來記錄所對應(yīng)節(jié)點(diǎn)集元素的頭指針h，指向一個(gè)由元素節(jié)點(diǎn)指針?biāo)M成的鏈表；第7個(gè)是一個(gè)數(shù)組flag，用來記錄節(jié)點(diǎn)集元素的元素節(jié)點(diǎn)使用次數(shù)，數(shù)組flag中的元素初始值為零.

如某節(jié)點(diǎn)集元素在數(shù)組E1中的表示為：該節(jié)點(diǎn)集元素的id值為c2，元素節(jié)點(diǎn)所組成的字符串path為“IJJC”，屬性節(jié)點(diǎn)所組成的字符串et為“SY”，值節(jié)點(diǎn)所組成的字符串value為“rgb（0，255，255）60”，該節(jié)點(diǎn)集元素的指針e為A11，指向元素節(jié)點(diǎn)指針?biāo)M成的鏈表的頭指針h為→A1→A4→A8→A11，用來記錄各元素節(jié)點(diǎn)使用次數(shù)的數(shù)組flag的長度為4，其中flag［A1］的值為9，flag［A4］的值為2，flag［A8］的值為2，flag［A11］的值1.

對數(shù)組E2 中數(shù)組元素依據(jù)id值進(jìn)行排序，這樣無id值的數(shù)組元素被全部排在數(shù)組元素的前面，接著對前面無id值的數(shù)組元素依據(jù)path值進(jìn)行排序.

依次遍歷E1數(shù)組元素，如果當(dāng)前數(shù)組元素s對應(yīng)的樹結(jié)構(gòu)的節(jié)點(diǎn)集元素已經(jīng)在匹配節(jié)點(diǎn)集元素集合M當(dāng)中（即s.e∈Array（M.X）），則結(jié)束本次循環(huán)進(jìn)入下一次循環(huán)，否則繼續(xù)；當(dāng)s的id不為空時(shí)根據(jù)id對數(shù)組E2進(jìn)行折半查找得到數(shù)組元素d，其中元素d和s的id值、path值、et值和value值均相等；當(dāng)s的id為空時(shí)根據(jù)path折半查找得到元素，其中元素d和s的path值、et值和value值均相等；同時(shí)遍歷d.h和s.h所對應(yīng)的2個(gè)鏈表，如果2個(gè)鏈表中對應(yīng)的每一項(xiàng)都相同，則將（s.e，d.e）合并入匹配節(jié)點(diǎn)集元素集合M.該子算法的具體實(shí)現(xiàn)（偽代碼）如下，其中序號為數(shù)值標(biāo)號.

（3）依據(jù)匹配節(jié)點(diǎn)集元素集合M生成差異腳本.該算法是以子算法I－SVG－Match得到的匹配節(jié)點(diǎn)集元素集合M為基礎(chǔ)，首先，對SVG1對應(yīng)的結(jié)構(gòu)樹進(jìn)行遍歷，如果被遍歷的節(jié)點(diǎn)集元素在SVG2中不能找到對應(yīng)的節(jié)點(diǎn)集元素對在匹配節(jié)點(diǎn)集元素集合M中，則對于SVG1中被遍歷的節(jié)點(diǎn)集元素s，順序遍歷節(jié)點(diǎn)集元素頭指針s.h所指向的鏈表，每當(dāng)遍歷到鏈表中一個(gè)指針對應(yīng)的元素節(jié)點(diǎn)時(shí)，如果該元素節(jié)點(diǎn)的flag 值為1，則在DiffXml中加入delete操作，同時(shí)對SVG1 的副本SVG0 所對應(yīng)的結(jié)構(gòu)樹執(zhí)行delete操作，并對鏈表中的每個(gè)元素節(jié)點(diǎn)的flag值做減1操作；否則，不執(zhí)行任何操作.不斷循環(huán)此過程，直到遍歷到null停止.其中對于與屬性節(jié)點(diǎn)相鄰的元素節(jié)點(diǎn)執(zhí)行delete操作時(shí)，除了刪除該元素節(jié)點(diǎn)之外，還要將與其相鄰的屬性節(jié)點(diǎn)和值節(jié)點(diǎn)也一并刪除.

接著，對SVG2對應(yīng)的結(jié)構(gòu)樹進(jìn)行遍歷，如果被遍歷的節(jié)點(diǎn)集元素在SVG1沒有對應(yīng)的節(jié)點(diǎn)集元素構(gòu)成的節(jié)點(diǎn)集元素對在匹配節(jié)點(diǎn)集元素集合M中，則對于SVG2中被遍歷的節(jié)點(diǎn)集元素d，順序遍歷節(jié)點(diǎn)集元素頭指針d.h所指向的鏈表，每當(dāng)遍歷到鏈表中一個(gè)指針對應(yīng)的元素節(jié)點(diǎn)時(shí)，如果該元素節(jié)點(diǎn)的flag值為零，則在DiffXml中加入insert操作，同時(shí)對SVG1 的副本SVG0 所對應(yīng)的結(jié)構(gòu)樹執(zhí)行insert操作，并對鏈表中的每個(gè)元素節(jié)點(diǎn)的flag值做加1操作.不斷循環(huán)此過程，直到遍歷到null停止.其中對于與屬性節(jié)點(diǎn)相鄰的元素節(jié)點(diǎn)執(zhí)行insert操作時(shí)，除了添加該元素節(jié)點(diǎn)之外，還要將與其相鄰的屬性節(jié)點(diǎn)和值節(jié)點(diǎn)也一起添加進(jìn)去.

算法執(zhí)行后生成差異腳本文件DiffXml算法對SVG0的操作結(jié)果就是SVG2格式地圖對應(yīng)的結(jié)構(gòu)樹，這說明可通過對SVG1 的結(jié)點(diǎn)樹施加DiffXml腳本中的操作可以再現(xiàn)第2版本地圖SVG2.該子算法的具體實(shí)現(xiàn)（偽代碼）如下.

1.2 I－DiffS算法復(fù)雜度

1.2.1 時(shí)間復(fù)雜度

在算法I－DiffS中，假設(shè)SVG1中的元素個(gè)數(shù)為n1，節(jié)點(diǎn)集元素個(gè)數(shù)為m1；SVG2 中的元素個(gè)數(shù)為n2，節(jié)點(diǎn)集元素個(gè)數(shù)為m2.并假設(shè)SVG1 中每個(gè)節(jié)點(diǎn)集元素的最大屬性個(gè)數(shù)為ta，SVG2中每個(gè)節(jié)點(diǎn)集元素的最大屬性個(gè)數(shù)為tb；SVG1的最大深度為d1，SVG2的最大深度為d2.

在I－DiffS的子算法I－SVG－Match中的第5行，對SVG1和SVG2中節(jié)點(diǎn)集元素的屬性節(jié)點(diǎn)排序，時(shí)間復(fù)雜度近似為m1O（talgta）＋m2O（tblgtb）.第10～19行，深度遍歷SVG1和SVG2，并將SVG1和SVG2中的節(jié)點(diǎn)集元素添加到SVG1對應(yīng)的數(shù)組E1和SVG2中的數(shù)組E2 中，時(shí)間復(fù)雜度為O（n1）＋O（n2）.第20～21行，依據(jù)id值對數(shù)組E2進(jìn)行排序，時(shí)間復(fù)雜度為O（m2lgm2）.第24～43 行，遍歷E1，對于E1中的每一個(gè)元素在E2中查找與之匹配的元素，由于E2已經(jīng)排好序，每次查找時(shí)間復(fù)雜度為O（lgm2），循環(huán)的總的時(shí)間復(fù)雜度為O（m1lgm2）.因此，子算法I－SVG－Match的總的時(shí)間復(fù)雜度為

I－DiffS的子算法I－SVG－DiffScript中，第6～21行，遍歷SVG1，如果被遍歷的節(jié)點(diǎn)集元素在SVG2中不能找到對應(yīng)的節(jié)點(diǎn)集元素對在匹配節(jié)點(diǎn)集元素集M中，再順序遍歷該節(jié)點(diǎn)集元素頭指針?biāo)鶎?yīng)的鏈表，時(shí)間復(fù)雜度近似為O（m1d1）≈O（m1）；第22～37行，遍歷SVG2，對于每一個(gè)在匹配節(jié)點(diǎn)集元素集合M中找不到配對的節(jié)點(diǎn)集元素，再順序遍歷該節(jié)點(diǎn)集元素頭指針?biāo)鶎?yīng)的鏈表，時(shí)間復(fù)雜度近似為O（m2d2）≈O（m2）.因此子算法I－SVG－DiffScript的總的時(shí)間復(fù)雜度為O（m1＋m2）.

基于以上分析，算法I－DiffS的總的時(shí)間復(fù)雜度為O（n）＋O（m1＋m2）≈O（n）.

1.2.2 空間復(fù)雜度

數(shù)組E1，E2對應(yīng)SVG1和SVG2，所需的空間復(fù)雜度為O（m1＋m2）.SVG0為SVG1對應(yīng)的副本，所需空間為O（m1）.最壞情況下，E1中的所有元素能在E2中找到匹配節(jié)點(diǎn)集元素，因此得到的匹配節(jié)點(diǎn)集元素集合M所需的空間復(fù)雜度為O（m1）.因此算法I－DiffS 最壞情況下的空間復(fù)雜度為O（m1＋

2 I－DiffS算法的驗(yàn)證

2.1 算法驗(yàn)證SVG 原文件

這里驗(yàn)證的是一幅2個(gè)不同時(shí)間戳的SVG 格式的地圖文件，文件名分別為FirstTimestamp.SVG和SecondTimestamp.SVG.

2.2 通過定義節(jié)點(diǎn)集元素得到的結(jié)構(gòu)樹

圖1是文件SVG1和SVG2在定義了節(jié)點(diǎn)集元素之后得到的解析結(jié)構(gòu)樹，其中橢圓表示元素節(jié)點(diǎn)，矩形表示屬性節(jié)點(diǎn)和其對應(yīng)的值節(jié)點(diǎn)，虛線標(biāo)出的是文件SVG1和SVG2存在的差異.

2.3 通過標(biāo)號的定義規(guī)則得到的優(yōu)化后的結(jié)構(gòu)樹

圖2使用了倒裝解析結(jié)構(gòu)樹標(biāo)號定義規(guī)則對圖1的解析結(jié)構(gòu)樹進(jìn)行了優(yōu)化，并將圖1中屬性節(jié)點(diǎn)和值節(jié)點(diǎn)組成的矩形進(jìn)行了分離，使用圓形表示元素節(jié)點(diǎn)和屬性節(jié)點(diǎn)，使用矩形表示值節(jié)點(diǎn)，每個(gè)與矩形相鄰的圓形即為屬性節(jié)點(diǎn)，其余圓形為元素節(jié)點(diǎn).其中屬性元素節(jié)點(diǎn)中屬性順序按字典順序排序，值節(jié)點(diǎn)中值的順序按屬性節(jié)點(diǎn)順序?qū)?yīng)排列.每個(gè)元素節(jié)點(diǎn)旁邊由An（n＝1，2，…，13）和Bn（n＝1，2，…，13）標(biāo)出該元素節(jié)點(diǎn)的指針（如A1，A2等和B1，B2等），用虛線標(biāo)出文件SVG1和SVG2的差異.

2.4 生成的節(jié)點(diǎn)集元素?cái)?shù)組

表2和表3中的E1和E2是由優(yōu)化后的SVG1和SVG2解析結(jié)構(gòu)樹生成的數(shù)組，數(shù)組的元素為節(jié)點(diǎn)集元素，每個(gè)元素由7種屬性構(gòu)成，分別是節(jié)點(diǎn)集元素id、節(jié)點(diǎn)集元素的元素節(jié)點(diǎn)所組成的字符串path、節(jié)點(diǎn)集元素的屬性節(jié)點(diǎn)所組的字符串et、節(jié)點(diǎn)集元素的值節(jié)點(diǎn)所組成的字符串value、節(jié)點(diǎn)集元素的指針e、節(jié)點(diǎn)集元素的元素節(jié)點(diǎn)指針?biāo)鶚?gòu)成的鏈表的頭指針h以及記錄了節(jié)點(diǎn)集元素的各元素節(jié)點(diǎn)使用次數(shù)的數(shù)組flag.其中數(shù)組E2是通過id值按字典順序排序后生成的.

圖1 SVG1和SVG2對應(yīng)的解析結(jié)構(gòu)樹Fig.1 Structural tree corresponding to SVG1and SVG2

圖2 基于SVG1和SVG2優(yōu)化后的定義了節(jié)點(diǎn)集元素的結(jié)構(gòu)樹Fig.2 Structural tree corresponding to SVG1and SVG2including node set elements

表2 依據(jù)節(jié)點(diǎn)集元素的屬性節(jié)點(diǎn)排序后SVG1對應(yīng)的結(jié)構(gòu)樹生成的數(shù)組E1和E2Tab.2 Array E1 and E2 corresponding to SVG1 and SVG2including sorted attribute nodes in node set elements

2.5 生成的匹配節(jié)點(diǎn)集元素集合M

I－SVG－Match執(zhí)行匹配過程：當(dāng)遍歷到E1［0］時(shí)，M＝｛（A1，B1）｝；當(dāng)遍歷到E1［1］時(shí)，M＝｛（A1，B1）｝；當(dāng)遍歷到E1［2］時(shí)，M＝｛（A1，B1）｝；當(dāng)遍歷到E1［3］時(shí)，M＝｛（A1，B1），（A7，B7）｝；當(dāng)遍歷到E1［4］時(shí)，M＝｛（A1，B1），（A7，B7），（A11，B11）｝；當(dāng)遍歷到E1［5］時(shí)，M＝｛（A1，B1），（A7，B7），（A11，B11），（A12，B12）｝；當(dāng)遍歷到E1［6］時(shí)，M＝｛（A1，B1），（A7，B7），（A11，B11），（A12，B12）｝；當(dāng) 遍 歷 到E1［7］時(shí)，M＝｛（A1，B1），（A7，B7），（A11，B11），（A12，B12），（A13，

B13）｝；當(dāng)遍歷到E1［8］時(shí)，M＝｛（A1，B1），（A7，B7），（A11，B11），（A12，B12），（A13，B13）｝.以上是執(zhí)行子算法I－SVG－Match第24～43行的循環(huán)過程，最終得到匹配節(jié)點(diǎn)集元素集合M.

表3 依據(jù)節(jié)點(diǎn)集元素的屬性節(jié)點(diǎn)排序后SVG2對應(yīng)的結(jié)構(gòu)樹生成的數(shù)組E1和E2Tab.3 Array E1 and E2 corresponding to SVG1 and SVG2including sorted attribute nodes in node set elements

2.6 生成的差異腳本I－DiffXml

子算法I－SVG－DiffScript依據(jù)匹配節(jié)點(diǎn)集元素集合M對SVG1對應(yīng)的結(jié)構(gòu)樹進(jìn)行遍歷，其中節(jié)點(diǎn)集元素A2，A3，A9，A6不在集合M中，則首先訪問A2.h指向的元素節(jié)點(diǎn)指針鏈表，由于flag［A2］的值為1，則在I－DiffXml腳本中加入了對SVG1中的A2執(zhí)行delete的操作，并對flag［A1］和flag［A2］做減1操作，flag［A1］的值為8，flag［A2］的值為零；接著順次訪問A3.h，A9.h和A6.h指向的元素節(jié)點(diǎn)指針鏈表，執(zhí)行的操作步驟同理；此時(shí)在I－DiffXml中已加入了對SVG1中的A2，A3，A9，A6執(zhí)行delete的操作，即在SVG1 對應(yīng)的結(jié)構(gòu)樹中刪除了A2，A3，A9和A6，并且flag［A1］的值為6，flag［A2］的值為零，flag［A3］的值為零，flag［A5］的值為1，flag［A9］的值為零，flag［A6］的值為零.

接著，對SVG2對應(yīng)的結(jié)構(gòu)樹進(jìn)行遍歷，其中節(jié)點(diǎn)集元素B3，B9，B6不在集合M中，則首先訪問B3.h指向的元素節(jié)點(diǎn)指針鏈表，由于flag［B2］初值為零，則在I－DiffXml腳本中加入了SVG2中的B2，由于flag［B3］初值為零，則在I－DiffXml腳本中加入了SVG2中的B3；接著順次訪問B9.h和B6.h指向的元素節(jié)點(diǎn)指針鏈表，執(zhí)行的操作步驟同理，即在IDiffXml腳本中加入了SVG2中的B2，B3，B9和B6.I－DiffXml差異腳本的具體實(shí)現(xiàn)如下.

3 結(jié)論

在現(xiàn)有的SVG（XML）差異算法的基礎(chǔ)上著重分析了目前最新的DiffS算法，并提出了一種改進(jìn)算法I－DiffS.該算法主要對以下幾方面進(jìn)行了改進(jìn)：①定義了節(jié)點(diǎn)集元素，減少了結(jié)構(gòu)樹對應(yīng)數(shù)組的元素個(gè)數(shù)，縮短了匹配過程；②使用了基于結(jié)構(gòu)樹的標(biāo)號定義規(guī)則，使得原本的結(jié)構(gòu)樹得到了進(jìn)一步的優(yōu)化，減少了排序時(shí)間；③算法復(fù)雜度為O（n），低于現(xiàn)有的最優(yōu)匹配算法DiffS的時(shí)間復(fù)雜度O（nlgn），適合對大規(guī)模SVG 格式地圖進(jìn)行差異匹配；④由于定義了節(jié)點(diǎn)集元素，差異腳本中的操作由原本的insert，move和delete 3種操作轉(zhuǎn)變成insert和delete 2種操作.該算法為今后基于SVG 的相關(guān)研究提供了理論基礎(chǔ).

［1］ Cobena G，Abiteboul S，Marian A.Detecting changes in XML documents［C］／／Proceedings of the 18th International Conference on Data Engineering.San Jose：IEEE，2002：1－3.

［2］ Wang Y，DeWitt D，Cai J.X－Diff：an effective change detection algorithm for XML documents［C］／／Proceedings of the 19th International Conference on Data Engineering.Bangalore：IEEE，2003：2－4.

［3］ Al－Ekram R，Adma A，Baysal O.diffX：an algorithm to detect changes in multi－version XML documents［C］／／Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative Research.Markham：IBM，2005：5－10.

［4］ Du Q，Guo ZC，Tang X.DiffSvg－matching algorithm of different timestamp maps based on SVG ［C］／／IEEE International Conference on Computer Science and Service System，Nanjing：［s.n.］，2012：1－5.

［5］ DU Q，TANG X.The Improvement of VTD－XML processing model［C］／／IEEE International Conference on Computer Science and Service System.Nanjing：IEEE，2011：2－4.

［6］ Tomokazu Fujino.SVG＋Ajax＋R：a new framework for WebGIS［J］.Computational Statistics，2007，22（4）：511.

［7］ YUAN Man，CHEN Xiuhong，YANG Chunling，et al.A practical and light integrated WebGIS based on SVG［C］／／CMC’09 Proceedings of the 2009 WRI International Conference on Communications and Mobile Computing.Kunming：CMC，2009：142－146.

［8］ DONG Xuemin， LI Yan. Standardization of SVG in implementing WebGIS［J］.ESIAT’09 Proceedings of the 2009 International Conference on Environmental Science and Information Application Technology.Wuhan：ESIAT，2009：534－537.