（計(jì)算機(jī)軟件與理論專業(yè)論文）針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究.pdf

論文獨(dú)創(chuàng)性聲明 本論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果論文中 除了特別加以標(biāo)注和致謝的地方外不包含其他人或其它機(jī)構(gòu)已經(jīng)發(fā)表或撰寫 ： 過(guò)的研究成果其他同志對(duì)本研究的啟發(fā)和所做的貢獻(xiàn)均已在論文中作了明確 的聲明并表示了謝意 論文使用授權(quán)聲明 本人完全了解復(fù)旦大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定即：學(xué)校有權(quán)保 留送交論文的復(fù)印件，允許論文被查閱和借閱；學(xué)?？梢怨颊撐牡娜炕虿?分內(nèi)容可以采用影印、縮印或其它復(fù)襯手段保存論文保密的論文在解密后 遵守此規(guī)定 作者簽名：導(dǎo)師簽名： 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 【摘要】 軟件重構(gòu)是軟件工程的一個(gè)重要研究領(lǐng)域，是當(dāng)前軟件工程界的一個(gè)重要研 究課題。通過(guò)軟件重構(gòu)，人們可以去除軟件中的不良設(shè)計(jì)，改進(jìn)軟件質(zhì)量。代碼 克隆是軟件源程序中普遍存在的一個(gè)問(wèn)題，一個(gè)軟件中往往存在著很多相同或基 本相似的代碼片段。代碼克隆不利于軟件的維護(hù)及更新，因?yàn)榧偃缬幸惶幮枰?改，其他克隆之處都要作相應(yīng)修改。 由于代碼克隆存在這種負(fù)面影響，我們有必要針對(duì)代碼克隆進(jìn)行軟件重構(gòu)。 針對(duì)代碼克隆的軟件重構(gòu)研究主要包括克隆的度量、檢測(cè)及消除。其目的就是盡 可能全面地找出源程序中的代碼克隆，并根據(jù)不同的克隆情況采取最合理的消除 措施，以得到最優(yōu)的重構(gòu)效果 本文從代碼克隆出發(fā)，以j a v a 語(yǔ)言為例，討論面向?qū)ο蟪绦蛑嗅槍?duì)代碼克隆 的重構(gòu)方法本文首先用基于編輯距離的相似度來(lái)度量代碼克隆，即通過(guò)計(jì)算兩 個(gè)代碼片段對(duì)應(yīng)的標(biāo)符序列的編輯距離，并求出其相似度來(lái)判斷是否克隆。本文 接著討論源程序中的克隆檢測(cè)，詳細(xì)闡述克隆檢測(cè)的各個(gè)步驟，包括確定代碼片 段、生成標(biāo)符序列、計(jì)算編輯距離及相似度。本文同時(shí)考慮了滿足語(yǔ)義邏輯等價(jià) 性的代碼克隆，即將形式上不相似但邏輯上等價(jià)的代碼片段也視為克隆，本文使 用程序邏輯圖來(lái)判斷邏輯等價(jià)性。本文最后針對(duì)不同的克隆情況實(shí)行不同的消除 克隆方法以實(shí)現(xiàn)最有效的重構(gòu)。 【關(guān)鍵字】 軟件重構(gòu)，代碼克隆，克隆度量，克隆檢測(cè)，克隆消除 【中圖分類號(hào)】t p 3 1 1 5 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 a b s t r a c t r e f a c t o r i n gi sa l li m p o r t a n tr e s e a r c hf i e l do fs o f t , r a r ee n g i n e e r i n g ，a n di ti sn o w w i d e l ys t u d i e db yr e s e a r c h e r s t h r o u g hr e f a c t o r i n g ，p e o p l ec a nr e m o v et h ef a u l t so r d e f e c t sa n di m p r o v et h eq u a l i t yo fs o f t w a r e c o d ec l o n ei saw i d e s p r e a dp r o b l e m e x i s t i n gi ns o u r c o d e s ，as o i t w a r eu s u a l l yc o n t a i n sm a n yi d e n t i c a lo rs i m i l a rc o d e f i a g m e n t s o b v i o u s l yc o d ec l o n e sa r eh a r m f u lt ot h em a i n t e n a n c ea n de n h a n c e m e n to f s o f t w a r e ，b e c a u s em o d i f i c a t i o n so ft h eo r i g i n a lc o d em u s ta l s ob ea p p l i e dt ot h e d u p l i c a t e dc o d e s b e c a u s eo ft h eh a r m f u li m p a c tp r o d u c e db yt h ec o d ec l o n e s ，“i sn e c e s s a r yt o r e f a c t o rt h es o r w a r ea i m i n ga tc o d ec l o n e s r e f a e t o r i n gr e s e a r c h e sa i m i n ga tc o d e c l o n e sm a i n l yi n c l u d ec l o n em e a s u r e m e n t , d e t e c t i o na n de l i m i n a t i o n 1 1 l eg o a lo ft h e r e f a c t o r i n gi st of i n dt h ec o d ec l o n e se x i s t i n gi ns o u r c ec o d e sa sc o m p r e h e n s i v e l ya s p o s s i b l e ，t h e na d o p ta no p t i m a le l i m i n a t i o na p p r o a c ha c c o r d i n gt od i f f e r e n tc l o n e s i t u a t i o n si no r d e rt oa c h i e v eab e s tr e f a c t o r i n gr e s u l t m sa r t i c l e ，蛐j a v aa se x a m p l e ，d i s c u s s e st h er e f a c t o r m ga p p r o a c h e sa i m i n g a tc o d ec l o n e si n0 0c o d e s t h i sa r t i c l ef i r s t l ya d o p t st h ee d i td i s t a n c eb a s e d s i m i l a r i t yt om e a s u r et h ec o d ec l o n e , w h i c hm e a n st h ec l o n ec a nb ed e t e r m i n e db y c o m p u t i n gt h ee d i td i s t a n c eo ft w ot o k e ns e q u e n c e sc o r r e s p o n d i n gt ot w oc o d e f r a g m e n t st h e nc a l c u l a t i n gt h e i rs i m i l a r i t y t h e nt h i sa r t i c l ed i s c u s s e s t h ec l o n e d e t e c t i n gi nt h es o n r c ec o d e 。i l l u s t r a t e s a ud e t e c t i n gs t e p si nd e t a i l ，i n c l u d i n g i d e n t i l y i n gc o d ef r a g m e n t s ，g e n e r a t i n gt o k e ns e q u e n c e s ，c a l c u l a t i n ge d i td i s t a n c ea n d s i m i l a r i t y t h i sa r t i c l ea l s ot a k e s t h ec o d ec l o n ee q u i v a l e n ti ns e m a n t i cl o g i ci n t o a c c o u n t , i td e e m st h ec o d ef r a g m e n t sw h i c ha l en o ts i m i l a ri ns h a p eb u te q u i v a l e n ti n l o g i ca sc l o n et o o ，a n du s e st h ep r o g r a ml o g i cg r a p ht oj a d g et h el o g i ce q u i v a l e n c e a t l a s tt h i sa r t i c l eg i v e ss o i n ed i f f e r e n tm e t h o d sw h i c hc a nb ea p p l i e dt or f f m o v ec o d e c l o n e sa c c o r d i n gt od i f f e r e n tc l o n es i t u a t i o n st og e tt h eb e s tr e s u l to f r e f a e t o r i n g k e yw o r d s s o f t w a r er e f a c t o r i n g ，c o d ec l o n e ，c l o n em e a s u r e m e n t , c l o n ed e t e c t i o n , c l o n e e l i m i n a t i o n c h i n e s e l i b r a r y c l a s s i f i c a t i o n t p 3 1 1 5 2 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 第一章引言 1 1 軟件重構(gòu) 在軟件生命周期中，維護(hù)所占的比重越來(lái)越大，據(jù)統(tǒng)計(jì)，軟件維護(hù)約占軟件 總成本的6 6 2 9 1 。隨著軟件規(guī)模的不斷擴(kuò)大，維護(hù)現(xiàn)有軟件變得越來(lái)越難。很 多軟件存在著大量不合理的設(shè)計(jì)，代碼冗余，結(jié)構(gòu)混亂，注釋不詳，這嚴(yán)重影響 了程序的可閱讀性，給軟件維護(hù)帶來(lái)了巨大的不便。 所以我們很有必要改善軟件中的不良設(shè)計(jì)，以提高軟件的可維護(hù)性，這就是 軟件重構(gòu)。m a r t i n f o w l e r 在( r e f a c t o r i n g ：i m p r o v i n g t h e d e s i g n o t e x 硒u g c o d e 一書(shū)中提出：“軟件重構(gòu)是指在不改變軟件的功能和外部可見(jiàn)性的情況下，為了 改善軟件的結(jié)構(gòu)，提高清晰性、可擴(kuò)展性和可重用性而對(duì)軟件進(jìn)行的改造?！薄緇 】 m a r t i nf o w l e r 同時(shí)也提出了很多重構(gòu)的方法例如將一串較長(zhǎng)的代碼重構(gòu)成一系 列函數(shù)的調(diào)用以縮短長(zhǎng)度，s w i t c h 語(yǔ)句用多態(tài)來(lái)代替，根據(jù)不同情況在父類和子 類之間交換f i e l d 或m e t h o d ，等等。此外在面向?qū)ο笙到y(tǒng)中應(yīng)該盡量使用設(shè)計(jì)模 式去改進(jìn)源程序，因?yàn)樵O(shè)計(jì)模式代表了良好的設(shè)計(jì)架構(gòu)，使程序編制真正工程化。 軟件重構(gòu)的主要目的有： 簡(jiǎn)化測(cè)試 使設(shè)計(jì)更加簡(jiǎn)單 更加容易理解 提高軟件設(shè)計(jì)的質(zhì)量 容易發(fā)現(xiàn)原有代碼中的b u g 使編碼的效率提高 提高軟件的可維護(hù)性 提高軟件的擴(kuò)展性 軟件重構(gòu)已成為軟件工程領(lǐng)域的一個(gè)重要研究課題。j i al i u 在2 0 0 6 國(guó)際軟 件工程會(huì)議上提出了一種面向特征的重構(gòu)技術(shù)，他以特征為單位將程序進(jìn)行分 片，并結(jié)合代數(shù)學(xué)理論來(lái)實(shí)現(xiàn)重構(gòu)【2 】d a v ea s t e l s 利用u m l 來(lái)實(shí)現(xiàn)重構(gòu)他先 從源程序中得到u m l 圖，然后對(duì)u m l 圖進(jìn)行改造以滿足合理的設(shè)計(jì)模式【4 】。 t o m t o u r w e 和t o m m e n 使用邏輯元編程的方法來(lái)檢測(cè)程序中的不良設(shè)計(jì)【5 】。 1 2 本文的研究目的 代碼克隆是當(dāng)今軟件中普遍存在的一種不良設(shè)計(jì)，在軟件源程序中往往出現(xiàn) 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 相同或相似的代碼片段，很多程序員為了復(fù)用源程序而執(zhí)行復(fù)制粘貼操作從而 產(chǎn)生了代碼克隆。代碼克隆對(duì)于軟件的修改和維護(hù)是不利的，因?yàn)榧偃缬幸惶幮?要修改，其他各處都要作相應(yīng)修改。 正因?yàn)榇a克隆的存在嚴(yán)重影響了軟件的修改和維護(hù)，所以我們有必要研究 針對(duì)代碼克隆的軟件重構(gòu)。本文研究了面向?qū)ο蟪绦蛑械拇a克隆，討論了代碼 克隆的度量、檢測(cè)及消除的一系列措施，其目的在于找出并消除源程序中的代碼 克隆，從而改善軟件中的不良設(shè)計(jì)，以提高軟件的可維護(hù)性。 1 3 相關(guān)研究 當(dāng)前有不少針對(duì)代碼克隆的研究，主要圍繞代碼克隆的度量、檢測(cè)及消除。 在代碼克隆的度量方面，當(dāng)前最普遍的方法就是求出兩段代碼的公共部分。 并且根據(jù)公共部分在代碼中所占的比重來(lái)衡量相似程度。這種方法簡(jiǎn)單直觀，因 為人們對(duì)于克隆的傳統(tǒng)習(xí)慣就是看相同部分有多少。 9 1 1 2 0 i 使用這種度量方法對(duì) 代碼進(jìn)行逐行比較，即比較兩行代碼中公共字符序列有多少。 在代碼克隆的檢測(cè)方面，因?yàn)闄z測(cè)是按照度量標(biāo)準(zhǔn)進(jìn)行的，所以當(dāng)前檢測(cè)代 碼克隆用得最普遍的方法就是基于字符的比較，即找出公共字符有多少。在比較 的時(shí)候需要先確定代碼片段，然后對(duì)兩個(gè)代碼片段作比較，顯然代碼片段的長(zhǎng)度 會(huì)影響相似度。【9 1 1 2 0 i 使用單個(gè)代碼行當(dāng)作代碼片段，對(duì)源文件進(jìn)行逐行比較， 同時(shí)用s c a t t e rs l o t 這種點(diǎn)狀矩陣圖來(lái)直觀地顯示克隆情況，如果片段1 的第f 行 跟片段2 的第，行在字符上相似，則在矩陣圖的第f 行，第_ ，列的方格中畫一個(gè) 點(diǎn)，這種可視化的方法可以直觀地反映克隆情況。在 1 4 5 即l i j 選取函數(shù)體作為代 碼片段，通過(guò)計(jì)算兩個(gè)函數(shù)體的公共部分來(lái)判斷是否克隆。 除了字符比較之外，【1 2 】提出了抽象語(yǔ)法樹(shù)，【1 9 提出了抽象語(yǔ)法后綴樹(shù)來(lái)檢 測(cè)代碼克隆。這兩種方法通過(guò)分析源代碼的語(yǔ)法樹(shù)來(lái)檢測(cè)代碼克隆，語(yǔ)句a b j 跟x = y ；具有類似的語(yǔ)法樹(shù)，這種方法適合于檢測(cè)語(yǔ)句內(nèi)容不同但形式上相似的 克隆。 在消除克隆方面，當(dāng)前的研究普遍將克隆部分抽取成一個(gè)函數(shù)，并調(diào)用該函 數(shù)來(lái)消除克隆，這也是最直接易行的措旅?！? 1 1 8 1 都提出了抽取函數(shù)這種措施， 而在很多研究中，研究人員只檢測(cè)出代碼克隆，不給出消除代碼克隆的措施，因 為消除最終應(yīng)由程序開(kāi)發(fā)員人為決定。 當(dāng)前關(guān)于代碼克隆的研究存在一些不足之處。在檢測(cè)代碼克隆的時(shí)候必須先 確定用來(lái)比較的代碼片段，代碼片段的長(zhǎng)度會(huì)影響相似度。在【1 4 】中選取函數(shù)體 作為代碼片段而不同的函數(shù)體往往長(zhǎng)短變化很大。如果代碼片段選得太長(zhǎng)，則 會(huì)降低相似度；如果選得太短，則沒(méi)有消除克隆的意義，例如在 9 】中選取單一 4 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 代碼行作為代碼片段進(jìn)行比較，顯然這樣傲只能檢測(cè)出程序里克隆的代碼行，而 沒(méi)有消除克隆的意義。當(dāng)前的檢測(cè)代碼克隆的方法集中于研究字符的匹配程度， 而不考慮程序語(yǔ)句之間的邏輯關(guān)聯(lián)。在實(shí)際中，我們常常看到有的語(yǔ)句可以等價(jià) 調(diào)換。我們應(yīng)該把這種滿足邏輯等價(jià)性的代碼片段也看作克隆。如果兩段不連續(xù) 的克隆塊能夠通過(guò)等價(jià)調(diào)換語(yǔ)句變成連續(xù)塊，這可以合并成一個(gè)大的克隆塊，這 樣顯然有利于克隆的消除此外，當(dāng)前關(guān)于消除代碼克隆的研究大多是僅僅將克 隆的代碼抽取成一個(gè)新函數(shù)，而對(duì)新函數(shù)應(yīng)擱放的位置缺少必要的研究，這種做 法雖然在一定程度上減少了克隆，但不一定能夠最有效地消除克隆在面向?qū)ο?系統(tǒng)中，代碼克隆可能存在于同一個(gè)類中或不同的類中，有時(shí)克隆的方法之間存 在調(diào)用關(guān)系而形成克隆鏈，對(duì)這些情況應(yīng)采取不同的重構(gòu)方法。 1 4 本文主要工作 本文研究了面向?qū)ο蟪绦蛑嗅槍?duì)代碼克隆的軟件重構(gòu)，針對(duì)當(dāng)前研究的上述 不足之處，提出了一系列改進(jìn)措施。 在克隆度量方面，本文不用兩段代碼含有多少公共字符來(lái)度量，而采用編輯 距離來(lái)度量。編輯距離即一段代碼轉(zhuǎn)換成另一段代碼需要進(jìn)行插入、刪除或者修 改的最少次數(shù)，如果編輯距離越短，則相似程度越高。求編輯距離的算法具有較 好的時(shí)間復(fù)雜度，而且編輯距離能夠反映出兩段代碼之間做了多少次修改。 在克隆檢測(cè)方面，本文對(duì)代碼片段的選取考慮了合適的長(zhǎng)度，在j a v a 程序中， 選取方法中包含的語(yǔ)句塊作為代碼片段，而不是整個(gè)方法體。對(duì)于復(fù)合語(yǔ)句塊， 則對(duì)嵌套的語(yǔ)句塊進(jìn)行分層處理，這樣做能夠檢測(cè)出更多的克隆，因?yàn)閮蓚€(gè)復(fù)合 語(yǔ)句塊不存在克隆，但是里面可能包含克隆的小語(yǔ)句塊。同時(shí)，本文中檢測(cè)代碼 克隆的措施考慮了語(yǔ)句之間的邏輯等價(jià)性，即滿足語(yǔ)義邏輯等價(jià)性的代碼克隆。 本文采用程序邏輯圖來(lái)判斷語(yǔ)句之問(wèn)的邏輯等價(jià)性，語(yǔ)句之間的邏輯關(guān)聯(lián)用圖的 邊來(lái)表示。兩個(gè)程序邏輯圖同構(gòu)則可以反映兩段代碼在邏輯上的等價(jià)性 在克隆消除方面，本文考慮了面向?qū)ο蟪绦蛑锌寺〉母鞣N存在形式，并且根 據(jù)不同的存在形式提出不同的消除措施。如果僅使用抽取函數(shù)，并不能得到最佳 的重構(gòu)效果。在面向?qū)ο蟪绦蛑校寺】赡艽嬖谟谕粋€(gè)方法中，同一個(gè)類的不 同方法中，以及不同類的方法中，對(duì)于這些復(fù)雜的情形，本文詳細(xì)探討合理的消 除措施，以求最佳重構(gòu)效果。 1 5 本文組織 本文各章節(jié)的內(nèi)容如下： 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 第二章介紹代碼克隆的概念及度量，給出判斷是否克隆的標(biāo)準(zhǔn)。要研究針對(duì) 代碼克隆的軟件重構(gòu)，首先必須明確什么樣的情形才是代碼克隆。這一章用基于 標(biāo)符的相似度來(lái)衡量代碼克隆。 第三章討論如何在源程序中檢測(cè)代碼克隆。在這一章提出了用基于編輯距離 的算法來(lái)計(jì)算相似度，并以此檢測(cè)代碼克隆。然后提出程序邏輯圖來(lái)判斷語(yǔ)句之 間的邏輯等價(jià)性，并以此來(lái)討論滿足語(yǔ)義邏輯等價(jià)性的代碼克隆。 第四章針對(duì)不同的克隆情況提出不同的消除克隆方法以實(shí)現(xiàn)最有效的重構(gòu)。 檢測(cè)出來(lái)的代碼克隆其存在方式可能多種多樣，這一章詳細(xì)討論代碼克隆的處理 方法。 第五章對(duì)所提出的算法和步驟用實(shí)驗(yàn)進(jìn)行驗(yàn)證 第六章總結(jié)和展望。對(duì)本文所做的工作進(jìn)行總結(jié)，并提出以后的研究方向。 6 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 第二章代碼克隆的概念及度量 2 1 代碼克隆的概念 2 1 i 什么是代碼克隆 我們?cè)陂喿x程序時(shí)，經(jīng)常會(huì)發(fā)現(xiàn)有兩處或多處代碼片段完全相同或基本相似 的情況，我們將這種完全相同或基本相似的代碼片段稱為代碼克隆，或者我們可 以將基本相似的代碼片段稱為準(zhǔn)代碼克隆，但是本文統(tǒng)一稱作代碼克隆。 例如，在開(kāi)源項(xiàng)目5 h o t d r a w 2 2 的餓忙h i f a 、d r 抓幅訇】耐r e c t a l l 9 1 e f i g u 陀j a v a 和s r c c h k i f a d r a w k f i g u r e s l r o u n d r e e m n g l e f i g u r e j a v a 這兩個(gè)文件中都存在圖2 1 所示的代碼片段： s u p e r w r i t e ( d w ) ； d w w r i t e i n t ( f d i s p l a y b o x x ) ； d w w r i t e i n t ( f d i s p l a y b o x y ) ； d w w r i t e i n t ( f d i s p l a y b o x w i d t h ) ； d w w r i t e i n t ( f d i s p l a y b o x h e i g h t ) ； 如果兩個(gè)代碼片段一和占是代碼克隆，則稱a 和曰滿足克隆關(guān)系，記作： c a = b 顯然克隆關(guān)系是一個(gè)符合自反、傳遞和對(duì)稱的關(guān)系。一和曰稱為克隆對(duì)。 如果一個(gè)代碼片段集合，其內(nèi)部任意兩個(gè)代碼片段都有克隆關(guān)系，則稱這個(gè)集合 為克隆集，也就是： c 對(duì)于集合墨v qc ，e 墨c ，= c ，o d ，則勛克隆集。 2 1 2 代碼克隆的產(chǎn)生 據(jù)統(tǒng)計(jì)，在大型程序代碼中，大約存在5 - 1 0 的克隆。代碼克隆的產(chǎn)生有很 多原因，最常見(jiàn)的情況是，當(dāng)一個(gè)程序員在編寫程序時(shí)。經(jīng)常會(huì)編寫相似功能的 程序，這時(shí)他往往會(huì)采取一種簡(jiǎn)單快速的方法，即復(fù)制已有程序，并執(zhí)行粘貼操 7 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 作，這樣就產(chǎn)生了代碼克隆。 例如，假設(shè)有人在編寫一個(gè)作圖程序，用來(lái)畫直線、多邊形、圓等圖形，當(dāng) 他編寫完畫直線的代碼時(shí)，他會(huì)發(fā)現(xiàn)畫多邊形跟直線有很多代碼是相同的( 如設(shè) 置畫筆粗細(xì)、顏色等，不同之處僅在于調(diào)用畫直線和多邊形的庫(kù)函數(shù)) ，這時(shí)他 就采取復(fù)制粘貼操作，于是就有了代碼克隆同樣他在編寫畫其它圖形的程序 時(shí)也會(huì)復(fù)用這部分代碼。 此外，一個(gè)軟件系統(tǒng)是由很多人共同編寫的，如果這些成員之間沒(méi)有溝通好， 也會(huì)編寫出很多冗余的相似代碼。有的軟件公司以代碼量來(lái)衡量員工的工作，這 使得很多員工會(huì)插入大量的克隆代碼以增加代碼量。 在面向?qū)ο蟪绦蛑校a克隆的產(chǎn)生大多集中在關(guān)系密切的類中( 如有公共 父類) ，關(guān)系越密切，則其包含的代碼所實(shí)現(xiàn)的功能越相似，于是它們的很多方 法中包含相似的代碼。例如在作圖程序中的直線類和箭頭類，它們有很多相似的 地方，如果編寫它們的d r a w ( ) 方法，則畫箭頭實(shí)質(zhì)上就是先畫直線再畫末端，這 就會(huì)跟直線類有代碼克隆。 2 1 3 代碼克隆對(duì)軟件的影響 代碼克隆是一種不良的設(shè)計(jì)，它的存在使程序難以作一致的修改，從而影響 軟件的更新和維護(hù)。程序編寫完成以后，我們要對(duì)它進(jìn)行多次測(cè)試以找出其中的 錯(cuò)誤，同時(shí)為了適應(yīng)客戶不斷變化的需求也要對(duì)程序作修改。假如有克隆關(guān)系的 那部分代碼中，發(fā)現(xiàn)有一處需要改動(dòng)，則其余克隆之處都要被改動(dòng)。 以上面的作圖程序?yàn)槔?，程序員復(fù)用了畫直線的代碼，使得多個(gè)地方存在著 克隆，假如以后需求發(fā)生了變化，畫筆顏色需要修改，則很多地方需要修改畫筆 顏色，顯然很費(fèi)力。 此外，代碼克隆的存在也會(huì)影響程序的閱讀性。程序員在閱讀程序的時(shí)候， 肯定不愿意多次看到克隆的代碼。如果第一次看到一段代碼他會(huì)認(rèn)真地研究程序 的功能，當(dāng)?shù)诙斡龅降臅r(shí)候，他肯定是希望對(duì)這部分代碼進(jìn)行封裝，因?yàn)樗?經(jīng)掌握了這部分代碼的功能，以后如果再用到的話，希望只調(diào)用一下接口即可， 而不必再去仔細(xì)地閱讀。 正因?yàn)榇a克隆的存在嚴(yán)重影響了軟件的修改和維護(hù)，所以我們有必要研究 針對(duì)代碼克隆的軟件重構(gòu)，檢測(cè)并設(shè)法消除源程序中的大量重復(fù)代碼。這正是本 文的研究目的，通過(guò)檢測(cè)并消除源程序中的代碼克隆，來(lái)改善軟件中的不良設(shè)計(jì)， 以提高軟件的可維護(hù)性。 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 2 1 4 代碼克隆的語(yǔ)義完整性 在研究代碼克隆的時(shí)候，不能忽視程序設(shè)計(jì)語(yǔ)言的語(yǔ)義。程序設(shè)計(jì)語(yǔ)言都是 按照特定的文法規(guī)則編寫的，所以我們討論的克隆代碼片段也必須符合這個(gè)文法 規(guī)則，這就是我們要考慮的語(yǔ)義完整性。 看以下兩個(gè)j a v a 代碼片段： 圖2 2 兩個(gè)代碼片段 這兩段代碼含有完全相同的片段： 圖2 3完全相同部分 這個(gè)片段雖然也屬于代碼克隆，但它不是一個(gè)語(yǔ)義完整的片段，因?yàn)閕 f 語(yǔ)句 是不完整的。對(duì)于這種語(yǔ)義不完整的代碼克隆，我們不予分析。在第四章討論消 除代碼克隆的時(shí)候，我們會(huì)講到將克隆的代碼片段用其他語(yǔ)句來(lái)代替，而語(yǔ)義不 完整的片段顯然沒(méi)法代替。 本文我們只討論語(yǔ)義完整的代碼克隆，在j a v a 語(yǔ)言中，語(yǔ)義的完整性可以用 和) 的匹配來(lái)判斷。 2 2 代碼克隆的度量 為了找出程序中的代碼克隆，首先必須給出一個(gè)代碼克隆的度量方法，即滿 足什么條件的代碼片段才是代碼克隆。下面我們?cè)敿?xì)討論度量方法。 9 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 2 2 i 源代碼中的標(biāo)符 根據(jù)代碼克隆的定義，代碼克隆是指完全相同或基本相似的代碼片段，這種 相同或相似可以通過(guò)比較兩段程序的字符來(lái)判斷，找出它們之間最大的公共字符 序列，然后從公共字符序列的長(zhǎng)度來(lái)分析其相似程度。 這一方法確實(shí)能夠比較代碼之間的相似性，但是對(duì)于程序語(yǔ)言來(lái)說(shuō)，單單考 慮字符是沒(méi)有意義的，因?yàn)樽址荒芡耆从吵绦虻恼Z(yǔ)義。例如在j a v a 程序中， 操作符一和= 雖然有公共的字符，但它們的語(yǔ)義卻是完全不一樣的，前者為邏輯 操作符，而后者為賦值操作符。為此我們?cè)诜治龀绦虻南嗨贫戎?，先引入?biāo)符 這一概念 源代碼中的標(biāo)符是指能夠保持語(yǔ)義的不可分割的字符序列例如程序中的 = = ，我們不能把它分割成= ，= ，因?yàn)榉指詈笳Z(yǔ)義就變了。我們知道，程序中的關(guān) 鍵詞，變量，常量，操作符等都是不可分割的，它們都有完整的語(yǔ)義，不能分割 成字符序列，所以它們都是標(biāo)符。對(duì)于j a v a 語(yǔ)言，標(biāo)符的種類見(jiàn)下表： 表2 1標(biāo)符類型 類型舉例 i fw h i l ef o r 關(guān)鍵詞 n e wc l a s sp u b l i c +一 操作符 + =一i 搴= 1 變量程序員命名的標(biāo)識(shí)符 常量 10 s 舉個(gè)例子，在語(yǔ)句i f l a = - b ) 中，有i f ，l ，a ，一，b ，) 這6 個(gè)標(biāo)符。 有了標(biāo)符這個(gè)概念后，我們就可以將代碼片段視作標(biāo)符的序列。標(biāo)符序列v 的長(zhǎng)度記為上o ，) ，代碼片段c 對(duì)應(yīng)的標(biāo)符序列長(zhǎng)度記為( c ) 。 既然代碼片段是標(biāo)符的序列，那么我們可以通過(guò)比較標(biāo)符來(lái)分析代碼的相似 程度。不過(guò)在實(shí)際比較中，對(duì)于長(zhǎng)度過(guò)小的代碼是沒(méi)有意義的，例如在源代碼中 存在著很多i f ，如果把這些i f 看作代碼克隆，那是沒(méi)有任何意義的。所以我們 只去分析具有一定長(zhǎng)度的代碼片段，為此引入最小標(biāo)符長(zhǎng)度這一概念。 最小標(biāo)符長(zhǎng)度是一段代碼要進(jìn)行相似程度比較所應(yīng)具有的最小標(biāo)符數(shù)量，記 為厶。，其數(shù)值可根據(jù)實(shí)際情況指定。指定了最小標(biāo)符長(zhǎng)度后，我們不再去分析 那些很短的代碼，使得找到的代碼克隆更有意義。 當(dāng)兩個(gè)代碼片段都轉(zhuǎn)變成標(biāo)符序列后( 并且標(biāo)符序列長(zhǎng)度都超過(guò)上脅) ，就 可以通過(guò)度量方法來(lái)比較相似程度，我們采用基于編輯距離的相似度來(lái)度量，后 1 0 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 面幾節(jié)將詳細(xì)介紹這些度量方法。 2 2 2 編輯距離 對(duì)于兩個(gè)標(biāo)符序列，如果要度量其相似程度，最常見(jiàn)的方法就是求出它們的 公共子序列，然后根據(jù)公共子序列的長(zhǎng)度來(lái)衡量相似程度這種方法雖然直觀易 懂，但是求出公共子序列的算法的時(shí)間復(fù)雜度較差本文通過(guò)編輯距離來(lái)反映相 似程度，下面介紹編輯距離的定義 如果兩個(gè)標(biāo)符序列v 1 和1 ，2 ，v l 要轉(zhuǎn)變成v 2 需要經(jīng)過(guò)插入、刪除或者修改標(biāo) 符的最少次數(shù)，稱為兩個(gè)標(biāo)符序列的編輯距離，記為e d i s t a n c e 。顯然編輯距離 越小，則表明兩個(gè)序列越相似 例如兩個(gè)標(biāo)符序列a b c d 和a c e ，前者最少經(jīng)過(guò)兩次操作刪除b ，并將d 改成e 后可以轉(zhuǎn)變?yōu)楹笳?，所以它們的編輯距離為2 。 編輯距離不僅可以體現(xiàn)兩個(gè)標(biāo)符序列的相似程度，還可以指明它們之間作了 多少次修改，這有利于我們對(duì)克隆代碼的分析，可以讓我們立即知道程序員在復(fù) 制粘貼一段代碼后作了幾次修改。 求編輯距離的算法將在第三章作介紹。 2 2 3 相似度 設(shè)有兩段代碼c l 和c 2 ，其標(biāo)符序列分別為v l 和v 2 ，定義這兩段代碼之間的 相似度為： s 幽毗兄) = l 一忑e 瓦d i s t j a 而n e e 可以看出，如果編輯距離越小，則相似度越大。如果編輯距離為0 ，則有 s i m i l a r i t y ( c i ，c 2 產(chǎn)l ，即表明兩段代碼完全相同。 我們可以指定一個(gè)相似度閾值t h r e s h o l d ，兩段代碼c i ，c 2 ，如果有 s i m i l a r i t y ( e , ，c 2 ) 一 t h r e s h o l d 則表示它們之間有克隆關(guān)系，即c - - - - c 2 。 有了相似度閾值，我們可以設(shè)定檢測(cè)出來(lái)的代碼克隆的最小相似度。如果我 們只檢測(cè)完全相同的代碼，則將闞值設(shè)為l ；如果需要找出基本相似的代碼，則 可以適當(dāng)降低閱值。 看一下圖2 4 所示的兩段代碼： 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 這兩段代碼的標(biāo)符序列為： 圖2 4代碼片段舉例 圖2 5代碼片段對(duì)應(yīng)的標(biāo)符序列 第一個(gè)標(biāo)符序列最少可以經(jīng)過(guò)以下7 次操作轉(zhuǎn)變?yōu)榈诙€(gè)標(biāo)符序列： 插入，插入j插入， 插入j插入一+ = 改為+ +刪除2 兩個(gè)標(biāo)符序列的e d i s t a n c e = 7 ，m a x ( l ( v , ) , l ( 屹) ) - - 2 6 ，所以 s i i i l i t y = 1 一里望皇竺：1 7 0 7 3 2 2 4 滿足語(yǔ)義邏輯等價(jià)性的克隆度量 前面分析的度量是基于標(biāo)符的，即分析標(biāo)符序列的相似度。然而程序設(shè)計(jì)語(yǔ) 言是有一定的語(yǔ)義的，不是簡(jiǎn)單的字符串。程序設(shè)計(jì)語(yǔ)言的語(yǔ)義使我們必須考慮 這樣一個(gè)問(wèn)題：如果兩段程序雖然從表面上看不相似，但是如果在不改變語(yǔ)義邏 輯的情況下對(duì)語(yǔ)句進(jìn)行調(diào)換，從而將相似度提升到閾值之上，那么這是不是代碼 克隆呢? 本文將這種情況也視作代碼克隆，因?yàn)檫@種情況下程序之間存在邏輯等價(jià) 性，代碼克隆不能只看表面上的相似性，也要看本質(zhì)上的相似性。我們來(lái)看一個(gè) 最簡(jiǎn)單的例子：有這樣兩個(gè)代碼片段，a + + ；b 一，和b - - 7a + + ；這兩段代碼如 果僅從標(biāo)符序列上看則會(huì)認(rèn)為是不相似的，但是我們知道a + + ；b - - ，可以進(jìn)行 語(yǔ)句調(diào)換變成b 一；a + + j 邏輯上是等價(jià)的，通過(guò)調(diào)換后可以發(fā)現(xiàn)兩段代碼是完 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 全相同的。 這種滿足語(yǔ)義邏輯等價(jià)性的克隆度量，首先需要判斷邏輯上的等價(jià)性，在邏 輯等價(jià)的前提下對(duì)代碼進(jìn)行調(diào)換，然后再利用基于標(biāo)符的相似性度量方法。判斷 邏輯等價(jià)性的算法將在第三章討論。 2 3 本章小結(jié) 本章的主要工作為針對(duì)代碼克隆的軟件重構(gòu)提供了前提和基礎(chǔ)，只有確定克 隆度量標(biāo)準(zhǔn)，才能在源代碼中檢測(cè)克隆并設(shè)法將它消除。本章提出的度量標(biāo)準(zhǔn)是 基于編輯距離的相似度比較，同時(shí)考慮了代碼的語(yǔ)義完整性，以及滿足語(yǔ)義邏輯 等價(jià)性的代碼克隆。有了克隆度量，我們就可以檢測(cè)源程序中的代碼克隆了，下 一章我們將詳細(xì)討論代碼克隆的檢測(cè)。 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 第三章代碼克隆的檢測(cè) 在前一章我們定義了代碼克隆的度量方法，即通過(guò)計(jì)算標(biāo)符序列的相似度來(lái) 判斷克隆。由相似度計(jì)算公式 s i i n i t y 如, e 2 ) = l 一忑e 面d i s t 面a n c e 麗 可知，我們只要得到兩段代碼的編輯距離就可以求出相似度。所以為了檢測(cè)代碼 克隆，我們需要有一個(gè)求編輯距離的算法。 有了這個(gè)算法以后，我們可以將代碼片段視作標(biāo)符的序列，運(yùn)用這一算法求 出編輯距離，然后計(jì)算相似度的值，如果相似度超過(guò)闕值，則表明這兩段代碼存 在克隆關(guān)系。 本章同時(shí)討論滿足語(yǔ)義邏輯等價(jià)性的代碼克隆的檢測(cè)，詳細(xì)分析兩段形式上 不相似但邏輯上等價(jià)的代碼，提出程序邏輯圖來(lái)判斷代碼語(yǔ)句之間的邏輯等價(jià) 性。 3 1 檢測(cè)代碼克隆的基本過(guò)程 檢測(cè)代碼克隆，要對(duì)代碼片段進(jìn)行比較，根據(jù)克隆度量，其實(shí)是對(duì)標(biāo)符序列 的比較。所以首先我們要將代碼片段生成標(biāo)符序列，再設(shè)計(jì)算法求出兩個(gè)標(biāo)符序 列的最長(zhǎng)公共標(biāo)符序列，從而計(jì)算相似度，最后將相似度跟閾值進(jìn)行比較以決定 是否克隆?；玖鞒虉D如下： 圖3 1檢測(cè)代碼克隆的流程圖 1 4 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 在上述流程圖中，我們看到檢測(cè)代碼克隆的核心在于代碼片段的相似度比 較。首先我們確定用于比較相似度的代碼片段，然后將代碼片段轉(zhuǎn)變?yōu)閷?duì)應(yīng)的標(biāo) 符序列，再對(duì)標(biāo)符序列求出編輯距離并計(jì)算相似度值，如果相似度大于閾值則表 明找到了一個(gè)克隆，此后繼續(xù)對(duì)其他代碼片段進(jìn)行比較。下面逐個(gè)討論上圖所示 的檢測(cè)過(guò)程。 3 2 代碼片段的選取 在檢測(cè)的時(shí)候我們要選取合適的代碼片段，然后運(yùn)用編輯距離算法進(jìn)行相似 度比較。最直接的辦法是將單個(gè)源文件當(dāng)作代碼片段，但是這樣的話可能由于源 文件太長(zhǎng)而檢測(cè)不到克隆。實(shí)際中可以采取將類( c l a s s ) 、方法( m e t h o d ) ( 或方法中 的語(yǔ)句塊) 當(dāng)作代碼片段。本文中，我采取方法中的語(yǔ)句塊當(dāng)作代碼片段，而不 用類。所謂語(yǔ)句塊就是連續(xù)的語(yǔ)句集合。先確定方法中的語(yǔ)句塊，然后轉(zhuǎn)變成標(biāo) 符序列，再求出其相似度。選取方法中的語(yǔ)句塊有以下好處： 方法中的語(yǔ)句塊長(zhǎng)度比較適中。如果比較兩個(gè)類的相似度，則很可能得不 到較大的相似度值，要找到代碼克隆就必須降低閾值，這樣一來(lái)會(huì)使檢測(cè)到的克 隆缺乏意義。 我們檢測(cè)到的代碼克隆，最終要設(shè)法去除。如果我們檢測(cè)到兩個(gè)克隆的方 法中的語(yǔ)句塊，則比較容易消除克隆( 例如將兩個(gè)方法中的相同部分提取成一個(gè) 新的方法，并調(diào)用該方法即可) ，而方法外的代碼克隆不易消除。 j a v a 程序中，不在方法中的代碼( 例如i m p o r t 語(yǔ)句，類中的成員聲明語(yǔ)句 等) ，即使存在克隆也不是不良設(shè)計(jì)，因?yàn)楹芏囝惪赡艽嬖谙嗤某蓡T變量，很 多源文件都要用到一系列相同的類從而都要寫對(duì)應(yīng)的i m p o r t 語(yǔ)句，所以我們只 需考慮方法中的代碼克隆 3 2 1 代碼片段的語(yǔ)義完整性 在第二章中，我們提出了代碼克隆的語(yǔ)義完整性這一概念，即代碼片段必須 是語(yǔ)義完整的，我們?cè)谶x取代碼片段的時(shí)候必須確保語(yǔ)義完整性。 在j a v a 語(yǔ)言中，我們可以通過(guò) 和 的匹配來(lái)判斷是否語(yǔ)義完整。一段代碼中 每遇到一個(gè)( ，如果后面沒(méi)有對(duì)應(yīng)的 ，則它的語(yǔ)義肯定不完整，這可以通過(guò)棧的 操作來(lái)判斷 看圖3 2 中的例子，這是一段i fe l s e 語(yǔ)句塊。 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 圖3 2 代碼片段舉例 在這段代碼中，我們不能選取下圖所示的代碼片段： 圖3 3 語(yǔ)義不完整的代碼片段 這個(gè)代碼片段顯然是語(yǔ)義不完整的。為了確保語(yǔ)義完整性，我們應(yīng)該選取完 整的i f , f o r ，w h i l e 等語(yǔ)句塊，一旦遇到這類關(guān)鍵詞，我們向后搜索一對(duì)匹配的 i 和】。為了便于處理，我們對(duì)mf o r ，w h i l e 等后面只包含單一語(yǔ)句的情形加一 對(duì)( 和。 3 2 2 確定代碼片段 對(duì)于j a v a 程序，代碼一般都包含在類中( 除i m p o r t 語(yǔ)句以外) ，包含在類中 的代碼有成員變量和方法兩種，我們?cè)谘芯看a克隆的時(shí)候只考慮方法。為了得 到盡可能高的相似度值，我們不宜選取太長(zhǎng)的代碼片段，而應(yīng)該選取長(zhǎng)度適宜的 代碼片段。最后可以將連續(xù)的小克隆塊合并成大克隆塊。根據(jù)前面的語(yǔ)義完整性 分析，我們將方法中的完整語(yǔ)句塊當(dāng)作代碼片段來(lái)比較相似度，為了確定代碼片 段，我們考慮三種基本語(yǔ)句塊： 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 順序語(yǔ)句塊，即由連續(xù)的聲明變量、賦值等語(yǔ)句組成的語(yǔ)句塊。 選擇語(yǔ)句塊，即i fe l 辯，s 晰t c h 這樣的語(yǔ)句塊。 循環(huán)語(yǔ)句塊，即矗扔w h i l e 這樣的語(yǔ)句塊。 而對(duì)于選擇，循環(huán)這樣的復(fù)合語(yǔ)句塊( 即存在嵌套的語(yǔ)句結(jié)構(gòu)) ，我們可以對(duì)它 進(jìn)行分層處理，當(dāng)遇到一個(gè)復(fù)合語(yǔ)句塊時(shí)，向里面分析被嵌套的語(yǔ)句塊，最終可 以把它分為若干基本語(yǔ)句塊。在克隆檢測(cè)時(shí)，我們通過(guò)先分析這些基本語(yǔ)句塊的 克隆情況，再得出復(fù)合語(yǔ)句塊的克隆結(jié)果。當(dāng)劃分好基本語(yǔ)句塊后。如果一個(gè)代 碼片段的標(biāo)符長(zhǎng)度小于工橢，則跟它前面或后面的代碼片段進(jìn)行合并( 合并前面 還是后面的代碼片段，采取優(yōu)先合并長(zhǎng)度較小的代碼片段這一策略) ，使得代碼 片段的長(zhǎng)度超過(guò)上。 3 3 生成標(biāo)符序列 要檢測(cè)代碼克隆，就必須首先將代碼生成相應(yīng)的標(biāo)符序列，在克隆度量那一 章我們知道了標(biāo)符的一些基本類型，包括關(guān)鍵詞、操作符、變量和常量。所以可 以根據(jù)這四種類型將代碼轉(zhuǎn)變成標(biāo)符序列，下面介紹生成標(biāo)符序列的過(guò)程。 3 3 1 去除代碼中的注釋 注釋對(duì)程序的語(yǔ)義沒(méi)有作用，我們?cè)跈z測(cè)代碼克隆的時(shí)候，無(wú)須考慮這些東 西可以對(duì)程序代碼片段作一遍掃描，如果遇到，則將以及在這一行中 后面的所有字符都去除；如果遇n * ，則向后掃描直到。并將和以及夾 在它們之間的所有字符都去除。 3 3 2 將程序的字符組合成標(biāo)符 去除注釋以后，我們把代碼片段中的字符逐個(gè)組合成標(biāo)符，基本算法為： i n p u t ：代碼片段c o d e ，類型為字符串s t r i n g o u t p u t ：標(biāo)符序列v ，類型為向量v e c t o r c l a s st o k e nl s t r i n gt o k e n ； i n tt y p e ；標(biāo)符類型，0 關(guān)鍵詞，1 操作符，2 變量標(biāo)識(shí)符，3 常量 t o k e n s t r i n gt o k e n ，i n tt y p e ) l t h i s t o k e n = t o k e n ， t h i s t y p e = t y p e ； 1 7 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 j j i n ti = 0 ，j ； v e c t o rv ； w h i l e ( i c o d e 1 e n g t h ( i f ( c o d e 【i 】是字母或下劃線) ii 這表明遇到了關(guān)鍵詞或標(biāo)識(shí)符 j 篁i + 1 7 w h i l e ( c o d e 【j 】是字母或下劃線或數(shù)字) i 往后掃描以確定一個(gè)完整的標(biāo)符 j + + ， i f ( c o d e s u b s t r i n g ( i ，j ) 屬于關(guān)鍵詞集合) v a d d ( n e wt o k e n ( c o d e s u b s t r i n g ( i ，j ) ，0 ) ) ， e l s e v a d d ( n e wt o k e n ( c o d e s u b s t r i n g ( i ，) ) ，2 ) ) ； i = j ， ) e l s ei f ( c o d e 【i 】是數(shù)字) 這表明遇到了常量，可能為整型或浮點(diǎn)型 j = i + l ； w h i l e ( c o d e j 】是數(shù)字或小數(shù)點(diǎn)) i ，+ + ； v 。a d d ( n e wt o k e n ( c o d e 。s u b s t r i n g ( i ，j ，3 ”； 1 = 】； e l s ei f ( c o d e 【i 】是操作符) i j = “1 7 w h i l e ( c o d e 【j 】是操作符) i j + + ； ， v a d d ( n e wt o k e n ( c o d e s u b s t r i n g ( i ，j ) ，1 ) ) ； i = j ； e l s e 空格或換行符 i + + ； 1 8 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 下圖是以上算法的程序?qū)崿F(xiàn)，運(yùn)行于j d k i 5 。 3 4 求編輯距離的算法 圖3 4生成標(biāo)符序列 設(shè)有兩個(gè)標(biāo)符序列”l = f l t 2 k ，屹= 苫l 兜翰，現(xiàn)要計(jì)算n 轉(zhuǎn)變成屹所需最少 的插入、刪除或修改標(biāo)符的次數(shù)。 設(shè)一個(gè)矩陣a 0 塒】【0 。棚，用它來(lái)記錄插入刪除或者修改的次數(shù)，例如a 【3 】 2 】 表示h t 2 t s 轉(zhuǎn)變成s i s 2 所需的最少次數(shù)。很顯然a 【司【o 】= f ，a 0 y - - y 。 對(duì)于a 0 陰我們考慮三種情況： a i - q ：3 表示“f 2 f j 1 轉(zhuǎn)變成s i s 2 研所需的最少次數(shù)，那么 f 2 t t 只要在 原來(lái)基礎(chǔ)上刪除一個(gè)厶即可，所以a 【習(xí) t = a i - l l i d l + l 。 同理，a 【司 - 1 】表示t i t 2 6 轉(zhuǎn)變成s i s 2 s j i 所需的最少次數(shù)，那么h t 2 ，1 只要在原來(lái)基礎(chǔ)上插入一個(gè)自即可，所以a 0 陰- a 【f 】 - l 】+ 1 。 a 【“】【- 1 】表示，l ，2 軋l 轉(zhuǎn)變成s i s 2 s j 1 所需的最少次數(shù)，這時(shí)如果，雨， 1 9 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 則無(wú)需改動(dòng)，否則在原來(lái)基礎(chǔ)上作一次修改，即將 改成毋，所以 a 【f m 書(shū)a - 1 】i - 1 j - 】+ 1 1 , ，6 麓 綜上所述，a 【刁們應(yīng)該取以上三種情況的最小值。最終a 【坍】陋】的值就是我們 要得到的編輯距離。 該算法的代碼描述如下： t o k e nv l 【m + 1 】，v 2 【n + l 】，v l 【1 】v l 【m 】，v 2 1 】v 2 【n 1 存放標(biāo)符序列 i n ta 【m + 1 】【n + 1 】， i n tc o s t ，i ，j ， f o r ( i = 0 ，i = 嘲；i + + ) a 【i 】【0 】= i ； f o r ( i f f i o j i f f i n ；i + 十j f o r i i = 1 ，i = 潮，i + + ) f o r ( j 。l ，j = n ，9 + + ) i f ( v l 【i 一1 】f f i = v 2 【j 一1 】j c o s t = 0 ； e l s e c o s t = 1 ； a 【i 】【j 】- - m i n ( a 【i - 1 】【j 】+ 1 ，a 【i j 【j 。1 】+ 1 ，a i - 1 】【j 一1 】+ c o s t ) ； l 其中m i n 函數(shù)如下 i n tm i n ( i n ta ，i n tb ，i n tc ) f i n tr e s u l t ? r e s u l t = a c ) r e s u l t f f i c ； r e t u r nr e s u l t ； 可以看一個(gè)例子，有兩個(gè)標(biāo)符序列a b c d e ，a a b b d e ，運(yùn)用以上算法可得到以 下矩陣： 針對(duì)代碼克隆的面向?qū)ο蟪绦虻闹貥?gòu)研究 表3 1 編輯距離矩陣 口abbde ol2 345 6 lo12 3 4 5 21l l 2 34 3 2 222 34 43 3 3 3 2 3 544443 2 最右下角的數(shù)字為2 ，這就是