[發明專利]一種軟件開發過程模型差異檢測方法

有效

• 申請號: 201810595370.2
• 申請日: 2018-06-11
• 公開（公告）號: CN108920360B
• 公開（公告）日: 2021-06-08
• 發明（設計）人: 曹斌;洪峰;范菁;侯晨煜
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

1.一種軟件開發過程模型差異檢測方法，包括下列步驟：

步驟1.計算過程循環復雜度；

所有模型以各自路徑上第一個變遷的編號為標準，按字典序從小到大排列；通過這樣的約束，一個并行結構轉換為唯一的順序結構；

基于以上對于并行結構的策略，過程循環復雜度的計算公式：

V(G)＝E-V+2-(n-m) (2)

其中E是過程模型圖中的連線數量，V是過程模型圖中的節點數量，m是過程中并行結構的數量，n是并行結構中模型的總數；

步驟2、構造過程結構樹；

基于任務的過程結構樹TPST是基于過程結構樹PST改進的一種半有序樹；TPST中包含有序節點和無序節點；其中有序節點是用來表示順序結構、循環結構；無序節點是用來表示選擇結構XOR和并行結構AND；有序節點的子節點按照從左到右的順序排列，而無序節點的子節點則沒有順序；

步驟3.建立獨立路徑；

所謂獨立路徑，就是過程中從開始節點到結束節點的一個可執行模型；每一個新的獨立路徑，都要求引入至少一個新的節點；對TPST采用寬度優先遍歷方法；從樹的根節點開始遍歷，每次遍歷完樹的一層后，把得到的模型作為臨時模型，繼續遍歷下一層時；遍歷下一層時，將之前臨時模型中的非變遷節點，即Sequence、XOR、AND、Loop，用它的子節點代替；共分為三種不同的情況：

1)其中Sequence和Loop節點，將它們的子節點按照從左到右的順序排列并代替；

2)XOR節點，有已訪問和未訪問兩種狀態；最初所有XOR節點都是未訪問的；當使用子節點對XOR節點進行代替時，分為兩種情況：(1)XOR節點未訪問：將它的兩個子節點分別代替該XOR節點，并將XOR節點標記為已訪問；這樣就會將原來一個的臨時模型變成兩個；(2)XOR節點已訪問：選擇它的第一個子節點代替；

3)AND節點的子節點直接代替，并做標記；在得到最終獨立路徑后，對標記的模型再按照字典序排列；這樣一直按照寬度優先遍歷，直到遍歷完樹的最后一層，就能把臨時模型中的所有非變遷節點都用變遷節點代替；當一個模型中的節點都是變遷節點時，則把該模型作為一個獨立路徑；當得到的獨立路徑數量等于過程循環復雜度后，則終止搜索；

得到每個業務過程的獨立路徑后，定義兩種類型的編輯操作：刪除和插入；對于兩個獨立路徑x和y，通過一系列刪除和插入的組合，將x轉化為y；兩種操作的次數代表了x和y的差異，記為dist(x,y)；最后通過公式計算兩個獨立路徑的相似度；

刪除：Delete(T,P)，表示從獨立路徑P中刪除節點T；

插入：Insert(T,P,D)，表示向獨立路徑P中的第D位置插入節點T；

步驟4.過程模型差異檢測；

得到過程的獨立路徑后，通過對兩個過程的獨立路徑進行差異識別來衡量兩個過程之間的差別；定義了兩種編輯操作，分別是刪除節點和插入節點；這兩種編輯操作能夠對模型中任何位置的節點進行執行，所以進行差異識別時通過計算兩個模型之間的最長公共子序列來作為兩者之間的共同部分，模型中剩余節點作為兩者之間的差別；最后利用公式(3)計算兩個模型之間的相似度；

對于兩個過程的所有獨立路徑，計算兩兩之間的相似度，最后利用KM算法進行全局最優匹配，使得整體的相似度最高；KM算法的輸入是兩個過程之間兩個獨立路徑的相似度，根據要求全局的相似度最高，得到最優的匹配結果；KM算法的輸出是一個只有兩列的二維數組，數組中每行的兩列數據代表一個匹配；結果中一個過程的一個獨立路徑與另外一個過程的一個獨立路徑匹配；

對于得到的匹配對(path₁，path₂)，將path₁通過編輯操作得到path₂的操作序列則為最終的編輯序列；具體方法如下：在path₁中去掉最長公共子序列的節點后，刪除剩余節點；接著向path₁中插入path₂除最長公共子序列部分之外的剩余節點，位置與在path₂中的位置保持一致；另外對于兩個過程的獨立路徑數量不同的情況，直接刪除經過KM匹配剩余的獨立路徑。