軟件執(zhí)行軌跡中相似路徑挖掘算法研究.pdf

1、隨著信息技術(shù)的飛速發(fā)展，序列數(shù)據(jù)庫(kù)呈現(xiàn)出爆炸性增長(zhǎng)，序列的相似性查詢(xún)技術(shù)也面臨著嚴(yán)峻的挑戰(zhàn)。從大量的軟件執(zhí)行軌跡中挖掘出相似的函數(shù)調(diào)用序列，對(duì)優(yōu)化用例集、減少高冗余度、查找關(guān)鍵路徑等應(yīng)用提供了可靠的保證。
　　本文在復(fù)雜網(wǎng)絡(luò)的背景之下，對(duì)序列相似性算法進(jìn)行深入的研究收集，整理軟件測(cè)試用例的執(zhí)行信息，挖掘出相似的執(zhí)行路徑。論文的主要內(nèi)容如下。
　　首先，本文提出了軟件執(zhí)行路徑的序列構(gòu)建算法。此算法把用例中每一個(gè)函數(shù)作為網(wǎng)絡(luò)中的

2、節(jié)點(diǎn)，將調(diào)用關(guān)系看作是節(jié)點(diǎn)的邊，并為每一個(gè)函數(shù)進(jìn)行唯一標(biāo)識(shí)，將執(zhí)行路徑轉(zhuǎn)換為函數(shù)調(diào)用序列。
　　其次，本文提出了基于完全公共子序列的相似路徑挖掘算法。該算法在兩條函數(shù)調(diào)用序列的基礎(chǔ)上建立動(dòng)態(tài)矩陣和路徑矩陣，通過(guò)計(jì)算路徑矩陣便可得出兩條序列的完全公共子序列集合，之后進(jìn)行序列相似性度量，得到軟件執(zhí)行路徑之間的相似度。本算法設(shè)計(jì)了公共子序列回溯的規(guī)則，能夠精確查找到序列的相同之處。
　　再次，本文提出了基于改進(jìn)編輯距離的相似路徑挖