楊會廷
　　(東方地球物理公司 物探技術(shù)研究中心，河北 涿州 072750）

       摘要：當(dāng)前軟件普遍采用爬蟲程序完成部分測試功能，分析當(dāng)前測試用的爬蟲程序，發(fā)現(xiàn)耗時(shí)最多的是查找可用路徑。為了避免撒網(wǎng)式的、無明確目地的、重復(fù)查找，提出了將集合因子最短路徑算法應(yīng)用于當(dāng)前的爬蟲程序中，以改善并提高爬蟲程序在軟件測試中的效率和有效性。此算法可以大大縮減爬蟲程序在查找有效可用路徑的時(shí)間，提高整個(gè)測試的效率。
　　關(guān)鍵詞：最短路徑；軟件測試；集合因子　　

0引言
　　為了滿足市場的需要，一般軟件都需要支持多個(gè)語言版本，例如：微軟的Windows 系統(tǒng)和Office軟件需要支持幾百種語言。因此針對多個(gè)語言的本地化軟件測試不可避免地提上了日程。在本地化軟件測試中，除了本地化的功能測試外，為了保證本地化軟件的翻譯質(zhì)量，往往需要對軟件的所有本地化頁面進(jìn)行檢查。對于支持幾百種語言的軟件，如何快速有效地獲取多種語言的所有本地化頁面就成為降低此項(xiàng)測試成本的關(guān)鍵［1］。
1如何獲取所有軟件頁面
　　一個(gè)軟件有多少界面對于開發(fā)者來說是透明的。如何獲取一個(gè)軟件所有的界面，對于不同的軟件設(shè)計(jì)會有不同的策略。基于Web的軟件尤為如此。
　?。?）訪問URL列表: 這個(gè)策略是針對基于Web的軟件才可以使用。整個(gè)軟件所有不同的頁面對應(yīng)的是不同且唯一的URL。通過訪問不同的URL以獲取軟件所有界面是比較簡單的方式。前提就是需要獲取整個(gè)軟件的URL 列表。不過目前大多數(shù)基于Web 的軟件，特別是外網(wǎng)可以訪問的軟件，為了保證軟件的安全都要屏蔽掉實(shí)際的URL。所以要獲取整個(gè)軟件的不同URL 列表也不是容易的事。
　　（2）定制腳本：目前許多軟件在開發(fā)的階段就同時(shí)開始定制許多測試腳本，并在以后的開發(fā)測試階段反復(fù)用來測試以保證軟件功能正常。但是這些腳本一般都是由開發(fā)人員編寫的，主要針對軟件的功能和復(fù)雜的業(yè)務(wù)邏輯，并且主要運(yùn)行在英文版的軟件上，很少運(yùn)行在本地化的軟件上。根據(jù)調(diào)查，大概只有6.7%的軟件開發(fā)小組會把腳本在本地化軟件上試運(yùn)行。所以很多開發(fā)腳本都很難直接運(yùn)行在本地化的軟件上并獲取本地化的界面［2］。
　?。?）自動爬蟲：目前自動爬蟲的程序有很多。用戶只需要提供登錄信息，爬蟲程序就能自動查找頁面上可能產(chǎn)生的新頁面元素，并依次觸發(fā)，循環(huán)迭代直到找到所有頁面。為了減少本地化測試成本，對于支持多種語言的軟件，要獲取多種語言的本地化頁面，采取自動爬蟲程序是一個(gè)很好的選擇。讓多個(gè)線程同時(shí)分別運(yùn)行在多個(gè)語言環(huán)境下截取所有頁面，從而可以大大節(jié)省成本。如果讓爬蟲程序撒網(wǎng)式查找并自由運(yùn)行，則整個(gè)運(yùn)行過程比較冗長。為了優(yōu)化爬蟲程序，加入最短路徑算法，使得整個(gè)爬蟲程序更有效［3］。
2集合因子最短路徑算法的介紹
　　隨著社會的發(fā)展，最短路徑問題在現(xiàn)實(shí)生活中占據(jù)的地位越來越重要。求解這一類問題的方法有很多，包括Floyd算法、Dijkstra算法、BellmanFord算法、動態(tài)規(guī)劃算法和智能優(yōu)化算法等。最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題，旨在尋找圖（由節(jié)點(diǎn)和路徑組成的）中兩節(jié)點(diǎn)之間的最短路徑。算法的具體形式包括［4］：
　?。?）確定起點(diǎn)的最短路徑問題：即已知起始節(jié)點(diǎn)，求最短路徑的問題。
　　（2）確定終點(diǎn)的最短路徑問題：與確定起點(diǎn)的問題相反，該問題是已知終結(jié)節(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。
　?。?）確定起點(diǎn)終點(diǎn)的最短路徑問題：即已知起點(diǎn)和終點(diǎn)，求兩節(jié)點(diǎn)之間的最短路徑。
　?。?）全局最短路徑問題：求圖中所有的最短路徑。
　　用于解決最短路徑問題的算法被稱作“最短路徑算法”，有時(shí)被簡稱作“路徑算法”。這里主要介紹可以應(yīng)用于自動爬蟲程序的集合因子最短路徑算法。
　　2.1集合因子最短路徑算法介紹
　　集合因子最短路徑算法是單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。其主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展，在擴(kuò)散過程中每次擴(kuò)散都以一個(gè)集合為因子，直到擴(kuò)展到所有節(jié)點(diǎn)為止。
　　問題描述：在無向圖G=(V,E)中，假設(shè)每條邊E［i］的長度為w［i］，找到由頂點(diǎn)V0到其余各點(diǎn)的最短路徑［5］。
　　2.2算法描述
　　2.2.1算法思想原理
　　設(shè)G=(V,E)是一個(gè)帶權(quán)無向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每次求得最短路徑的頂點(diǎn), 就被加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度，U中的頂點(diǎn)的距離是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。
　　2.2.2算法過程描述
　　算法過程如下：
　?。?）初始時(shí)，S只包含源點(diǎn)，即S＝{v}，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U={其余頂點(diǎn)}，若v與U中頂點(diǎn)u有邊，則<u,v>正常有權(quán)值，若u不是v的出邊鄰接點(diǎn)，則<u,v>權(quán)值為∞。
　?。?）從U中選取距離v最小的頂點(diǎn)集合<k1,k2>，把k1、k2加入S中（該選定的距離就是v到k1=v到k2, 且是最短路徑長度）。
　?。?）以<k1、k2>組成的集合為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過頂點(diǎn)ki）比原來距離（不經(jīng)過頂點(diǎn)ki）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)ki的距離加上邊上的權(quán)。
　?。?）重復(fù)步驟（2）和（3）直到所有頂點(diǎn)都包含在S中。
　　2.3算法適用范圍
　　（1）單源最短路徑；
　?。?）有向圖和無向圖。
3集合因子最短路徑算法在爬蟲程序中的應(yīng)用
　　每個(gè)軟件一般都有一個(gè)登錄頁面，把登錄后的第一個(gè)頁面命名序號為001，然后以從上到下，從左到右的順序分別定義自動爬蟲程序掃描出來的新頁面，分別是002、003等。而每個(gè)頁面之間的距離，即權(quán)值，都為1（實(shí)際中，訪問不同頁面需要的時(shí)間是不同的，這里在服務(wù)器性能很好的情況下，忽略訪問時(shí)間的不同，都設(shè)定為1）。所有頁面從第一個(gè)頁面001出發(fā)，可以直接到達(dá)或者經(jīng)過若干個(gè)節(jié)點(diǎn)后到達(dá)。其他不同的節(jié)點(diǎn)間也可能存在到達(dá)的路徑。這樣由所有頁面作為節(jié)點(diǎn)組成一個(gè)所有頁面可到達(dá)的圖，且每個(gè)節(jié)點(diǎn)之間的距離都為1。由于整個(gè)軟件過于龐大，下面只畫出部分節(jié)點(diǎn)來說明問題，如圖1所示。

　　設(shè)001為源點(diǎn)，求001到其他各頂點(diǎn)〈002，003，004，005，006，007，008，009，010，011，012，013〉的最短路徑。算法執(zhí)行步驟如表1。

4試驗(yàn)數(shù)據(jù)和性能對比
　　通過對比數(shù)據(jù)更能體現(xiàn)這一算法應(yīng)用在爬蟲程序中的優(yōu)勢，如表2所示。下面的數(shù)據(jù)采集采用的是相同性能和型號的服務(wù)器，且使用相同軟件。整個(gè)軟件共有956張圖。程序運(yùn)行過程中，在剛開始速度會比較快，到后面時(shí)由于需要花費(fèi)更多時(shí)間判斷處理，速度會慢下來。表2中的數(shù)據(jù)屬于平均數(shù)據(jù)。需要運(yùn)行多個(gè)語言平臺時(shí)，是多個(gè)表1算法執(zhí)行步驟步驟S集合中U集合中1選入 001，此時(shí)S=<001>
　　此時(shí)最短路徑001→001=0
　　以集合<001>為中間點(diǎn)集合開始找U=<002,003,004,005,006,007,008,009,010,011,012,013>
　　001→002=1
　　001→003=1
　　001→004=1
　　001→005=1
　　001→其他U中的節(jié)點(diǎn)=∞2選入002、003、004、005，此時(shí)S=<001,002,003,004,005>，001→001=0，
　　001→002=1，
　　001→003=1，
　　001→004=1，
　　001→005=1，
　　以集合<002，003，004，005>為中間點(diǎn)集合，從001→002，001→003，001→004，001→005最短路徑開始找U=<006,007,008,009,010,011,012,013>
　　002→U中的節(jié)點(diǎn)=∞
　　003→006=1
　　003→007=1
　　003→008=1
　　004→U中的結(jié)點(diǎn)=∞
　　005→008=1（由于003→008=1已存在，直接放棄此條路徑）3選入006、007、008，
　　此時(shí)，S=<001,002,003,004,005,006,007,008>，
　　001→001=0，001→002=1，001→003=1，001→004=1，001→005=1，001→003→006=2，001→003→007=2，001→003→008=2，
　　以集合<006，007，008>為中間點(diǎn)集合，從001→003→006=2，001→003→007=2，001→003→008=2
　　分別為最短路徑開始找U=<009,010,011,012,013>
　　006→U中的節(jié)點(diǎn)=∞
　　007→010=1
　　007→011=1
　　008→009=1
　　008→012=14選入010、011、009，012，此時(shí)，S=<001,002,003,004,005,006,007,008,009,010,011,012>，
　　001→001=0，001→002=1，001→003=1，001→004=1，001→005=1，001→003→006=2，001→003→007=2，001→003→008=2，001→003→007→010=3，001→003→007→011=3，001→003→008→009=3，001→003→008→012=3，
　　以集合<009，010，011，012>為中間點(diǎn)集合，從001→003→007→010=3，
　　001→003→007→011=3，
　　001→003→008→009=3，
　　001→003→008→012=3，
　　分別為最短路徑開始找U=<013>
　　009→013=1
　　010→U中的節(jié)點(diǎn)=∞
　　011→U中的節(jié)點(diǎn)=∞
　　012→U中的節(jié)點(diǎn)=∞5選入013，此時(shí)，S=<001,002,003,004,005,006,007,008,009,010,011,012,013>，001→001=0，
　　001→002=1，001→003=1，001→004=1，001→005=1，001→003→006=2，001→003→007=2，001→003→008=2，001→003→007→010=3，001→003→007→011=3，001→003→008→009=3，001→003→008→012=3，001→003→008→009→013=4U集合已空，查找完畢線程訪問同一個(gè)服務(wù)器，只要改變?yōu)g覽器的語言即可。從實(shí)驗(yàn)數(shù)據(jù)可以看到在使用集合因子最短路徑算法后，不論是單個(gè)線程還是多個(gè)線程，整個(gè)程序的運(yùn)行時(shí)間會大大縮短，性能大幅度提高。
5結(jié)論
　　通過把集合因子最短路徑算法應(yīng)用在自動爬蟲程序中，使得程序無論在單位時(shí)間的吞吐率還是單位事務(wù)的響應(yīng)速度都大大提高。對于某些支持多個(gè)語言的軟件來說集合因子最短路徑算法會使得程序運(yùn)行效率大幅度提高。
　　參考文獻(xiàn)
　?。?］ 張茂林.軟件自動測試的研究與程序?qū)崿F(xiàn)［J］.北京航空航天大學(xué)學(xué)報(bào), 1997, 23 (1):7480.
　?。?］ 凌永發(fā), 張?jiān)粕? 郭秀萍. 軟件測試自動化的腳本技術(shù) ［J］. 云南民族學(xué)院學(xué)報(bào)(自然科學(xué)版)，2002, 11(1):544548.
　?。?］ 王華偉,崔啟亮.軟件本地化——本地化行業(yè)透視與實(shí)現(xiàn)指南［M］.北京:電子工業(yè)出版社,2005.
　　［4］ 侯俊杰.深入淺出MFC(第2 版)［M］. 武漢:華中科技大學(xué)出版社,2005.
　?。?］ 李春葆.數(shù)據(jù)結(jié)構(gòu)教程［M］.北京：清華大學(xué)出版社，2005.