貪婪算法的基本原理
前言：想要寫出一篇令人眼前一亮的文章嗎？我們特意為您整理了5篇貪婪算法的基本原理范文，相信會(huì)為您的寫作帶來(lái)幫助，發(fā)現(xiàn)更多的寫作思路和靈感。
貪婪算法的基本原理范文第1篇
關(guān)鍵詞：壓縮感知；圖像快速重建；稀疏表示；小波分解；正交匹配追蹤
中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2013） 01-0065-02
1 壓縮感知概述
1.1 壓縮感知理論
美國(guó)工程師奈奎斯特于1928年提出，又由信息論創(chuàng)始人香農(nóng)于1948年將壓縮感知理論加以說(shuō)明并將其以定理形式進(jìn)行引用。奈奎斯特理論認(rèn)為，在轉(zhuǎn)換模擬/數(shù)字信號(hào)時(shí)，如果采樣頻率2倍于信號(hào)最高頻率時(shí)，那么采樣后的數(shù)字信號(hào)就能夠?qū)υ夹盘?hào)的信息進(jìn)行完整保留。在這種背景之下，近年來(lái)，美國(guó)科學(xué)家在此基礎(chǔ)上提出了新的信息獲取理論，也就是壓縮感知。壓縮感知理論認(rèn)為，如果利用遠(yuǎn)低于奈奎斯特標(biāo)準(zhǔn)的方法實(shí)現(xiàn)對(duì)可壓縮信號(hào)的數(shù)據(jù)采樣，仍然可以將原始信號(hào)進(jìn)行精確恢復(fù)。壓縮感知理論一經(jīng)提出，便解決了一系列發(fā)展與應(yīng)用瓶頸，使其在各個(gè)領(lǐng)域都得到了巨大發(fā)展。
1.2 壓縮感知原理
（1）基本原理。壓縮傳感信號(hào)x?Rn*1測(cè)量過(guò)程的公式為y=Ax?RM*1，M??N式中A表示測(cè)量矩陣，y表示所獲取的信號(hào)測(cè)量矢量。而信號(hào)重建公式則表示為min||x||0，s.t.y=Ax式中||·||0表示x中非零值元素，即信號(hào)的稀疏度。信號(hào)重建公式屬于組合優(yōu)化問(wèn)題，壓縮感知理論的提出者認(rèn)為，能夠使用11范數(shù)的最小化對(duì)矩陣測(cè)量進(jìn)行求解，其公式為min||x||1，s.t.y=Ax。
（2）組成部分。信號(hào)恢復(fù)算法，即以M個(gè)觀測(cè)值對(duì)N長(zhǎng)度的原始信號(hào)進(jìn)行無(wú)失真恢復(fù)、矩陣測(cè)量，即保證當(dāng)原始信號(hào)在維數(shù)降低時(shí)，維持在最小的信息損失量、信號(hào)稀疏表示這三部分組成了壓縮感知的理論。
1）信號(hào)恢復(fù)算法。與奈奎斯特理論中線性感知特點(diǎn)不同，壓縮感知理論中要復(fù)原信號(hào)，就要將非線性優(yōu)化問(wèn)題進(jìn)行求解。目前壓縮感知重建算法有三種，一是貪婪算法，它的特點(diǎn)是精度低且測(cè)量數(shù)據(jù)多，二是凸優(yōu)化算法，其特點(diǎn)是精度高且測(cè)量數(shù)據(jù)少，三是統(tǒng)計(jì)優(yōu)化算法，這種算法介于其他兩種算法。2）測(cè)量矩陣。當(dāng)信號(hào)x為長(zhǎng)度N時(shí)，其在M??N個(gè)測(cè)量中進(jìn)行重建，如果非零系數(shù)位置為已知，只要K?M，那么這個(gè)公式就有解。目前在采樣方式上，較為常見(jiàn)的有JITTER采樣、隨機(jī)采樣以及均勻采樣等，而在測(cè)量波形上，則包括正交函數(shù)、隨機(jī)波形以及高期隨機(jī)波形等。3）信號(hào)稀疏表示。在可壓縮信號(hào)的基礎(chǔ)上，壓縮感知可通過(guò)兩步驟實(shí)現(xiàn)，即先設(shè)計(jì)不相關(guān)于變換基的測(cè)量矩陣并對(duì)其實(shí)施觀測(cè)，得到測(cè)量向量后，從維度測(cè)量向量進(jìn)行信號(hào)的重建。
2 基于壓縮感知的圖像快速重建方法設(shè)計(jì)
通過(guò)設(shè)計(jì)一種基于觀測(cè)矩陣與多稀疏變換基的組合并利用正交匹配追蹤計(jì)算法來(lái)重建圖像，同時(shí)通過(guò)實(shí)驗(yàn)使用一級(jí)小波分解圖像，將相似的分子量圖像進(jìn)行提取，而后應(yīng)用于壓縮感知技術(shù)實(shí)現(xiàn)對(duì)其的恢復(fù)操作，最終借助小波逆變換得到圖像的快速重建效果。
2.1 觀測(cè)矩陣、稀疏變換基與算法
在本實(shí)驗(yàn)中選取了不相同的稀疏變換基5種，分別是離散傅里葉、離散余弦以及三種各不相同的小波變換基。而觀測(cè)矩陣則包括非常稀疏投影、局部哈達(dá)瑪、非相關(guān)測(cè)量、BERNOULLI隨機(jī)以及高斯隨機(jī)矩陣5種。所采取的恢復(fù)算法則是貪婪算法中的正交匹配追蹤算法。
從表1的數(shù)據(jù)結(jié)果顯示，基于觀測(cè)次數(shù)相同的條件下，本文提出的方法與直接將壓縮感知重建技術(shù)應(yīng)用于整幅圖像相比，顯著提升了其運(yùn)行的時(shí)間與效率，另外對(duì)于重建圖像的也有了相當(dāng)明顯的改善效果。
3 結(jié)語(yǔ)
將壓縮感知理論應(yīng)用于重建二維圖像上，已獲得較好的重建圖像質(zhì)量，本文在此基礎(chǔ)上，利用觀測(cè)矩陣、稀疏變換基的相關(guān)算法，并引入小波變換，設(shè)計(jì)了一種經(jīng)改進(jìn)后的圖像快速重建方法，在獲得同等重建質(zhì)量的圖像同時(shí)，還能夠?qū)⒊绦蜻\(yùn)行時(shí)間明顯縮短，使得圖像快速重建的效率得到大幅度提升，因此具備一定的推廣應(yīng)用前景。
參考文獻(xiàn)：
[1]王天荊，鄭寶玉，楊震.基于自適應(yīng)冗余字典的語(yǔ)音信號(hào)稀疏表示算法[J].電子與信息學(xué)報(bào).2011，33（10）.
貪婪算法的基本原理范文第2篇
【關(guān)鍵詞】稀疏表示；MRI；圖像處理
1.引言
磁共振成像技術(shù)（Magnetic Resonance Imaging，MRI）是一種利用圖像進(jìn)行醫(yī)療診斷的檢查技術(shù)。它沒(méi)有電離輻射傷害，能夠直接掃描出器官各個(gè)體層的圖像，避免了開顱、開胸、開腹探查等手術(shù)。MRI技術(shù)可以給醫(yī)生帶來(lái)清晰實(shí)用的人體內(nèi)部結(jié)構(gòu)圖像，在臨床檢查上得到普遍的應(yīng)用。但是MRI有一個(gè)缺點(diǎn)，它的成像過(guò)程太過(guò)漫長(zhǎng)，一次成像過(guò)程要10分鐘到30分鐘。因此如何快速地獲取MRI圖像就成為一個(gè)熱點(diǎn)問(wèn)題，而壓縮感知[1]和稀疏表示理論在MRI上的應(yīng)用使得在不改變現(xiàn)有MRI系統(tǒng)硬件的條件下減少成像時(shí)間成為可能。
2007年Lustig和Donoho等人發(fā)表了Sparse-MRI[2]，首次將壓縮感知理論應(yīng)用到MRI中。在SparseMRI方法中作者應(yīng)用了MR圖像在小波域的稀疏性，對(duì)下采樣的K空間數(shù)據(jù)進(jìn)行重建，取得較好的重建效果。此后MR圖像的不同稀疏特性不斷被挖掘，MRI重構(gòu)的效果得到很大的提升。
2.稀疏表示理論
令信號(hào)，稀疏字典，稀疏系數(shù)。則信號(hào)可以表示為，其中是字典原子。是信號(hào)在字典域的稀疏系數(shù)，如果僅有K個(gè)非零項(xiàng)，或者中僅有K個(gè)大系數(shù)，其它都是接近0的小系數(shù)，則我們稱是稀疏度為K。由于實(shí)際中K=N，所以我們只要記住這K個(gè)項(xiàng)的位置及值我們就可以精確重構(gòu)信號(hào)x。稀疏度K越小，則系數(shù)越稀疏，重構(gòu)信號(hào)x所需要保存的數(shù)據(jù)量就越少。字典D可以是解析字典，例如DCT基底、小波基底，也可以是自適應(yīng)訓(xùn)練字典或隨機(jī)字典。如圖1是一維信號(hào)稀疏表示的示意圖，白的方格表示0，不同的灰度表示不同的值。
圖1 一維信號(hào)在高斯隨機(jī)字典投影下的2稀疏表示
實(shí)際應(yīng)用中我們通常是觀測(cè)到有噪聲的信號(hào)x，為了恢復(fù)原始信號(hào)我們建立如下的目標(biāo)函數(shù)：
（1）
但是這個(gè)目標(biāo)函數(shù)的求解是NP難問(wèn)題，目前解該問(wèn)題的方法主要有兩種：
一種是貪婪算法，如匹配追蹤（MP）[3]、正交匹配追蹤（OMP）算法[4]；一種是松弛算法，比如基追蹤算法（BP）[5]。
匹配追蹤算法（Matching Pursuit，MP）是一種貪婪迭代算法，其基本思想在每一次的迭代過(guò)程中，從過(guò)完備原子庫(kù)里選擇與殘差信號(hào)最匹配的原子來(lái)進(jìn)行信號(hào)表達(dá)，同時(shí)從殘差信號(hào)中剔除其投影，獲得新的殘差信號(hào)。當(dāng)?shù)螖?shù)達(dá)到設(shè)定值，或者重構(gòu)殘差小于設(shè)定閾值時(shí)，迭代停止。其算法流程如下：
輸入：字典D，觀測(cè)信號(hào)x，稀疏度L
輸出：的L稀疏逼近%
初始化：殘差r0=x，索引集，迭代次數(shù)t=1；
循環(huán)執(zhí)行步驟1-5
步驟1：找出殘差r0與字典D中最相似列dk的角標(biāo)，所謂最相似，即：
步驟2：更新索引集，紀(jì)錄找到的重建信號(hào)字典原子集合（也稱為支撐集）Dt=[Dt-1，d]
步驟3：由最小二乘算法得到t%=argmin ||x-Dtt%||2
步驟4：更新殘差rt=y-Dtt%，t=t+1
步驟5：判斷迭代次數(shù)是否滿足，若滿足則停止迭代，否則繼續(xù)執(zhí)行步驟1。
由于MP算法中信號(hào)在已選定的原子上的投影并非正交的，MP算法每一次迭代結(jié)果有可能是次優(yōu)，為獲得收斂需要經(jīng)過(guò)較多次的迭代。
3.稀疏表示在MRI領(lǐng)域的應(yīng)用
信號(hào)的稀疏性是壓縮感知理論的一個(gè)重要前提，在壓縮感知MRI系統(tǒng)的設(shè)計(jì)中稀疏表示問(wèn)題可以歸結(jié)為稀疏字典的設(shè)計(jì)[6]。我們可以從不同的角度，對(duì)不同的字典進(jìn)行分類，因此基于稀疏表示的MRI重構(gòu)問(wèn)題也會(huì)有不同的重構(gòu)模型。例如我們可以把字典分為解析字典和訓(xùn)練字典兩大類：一是解析字典，解析字典是由具有明確的數(shù)學(xué)理論推導(dǎo)直接產(chǎn)生的基底的集合，常用的如DCT基底組成的DCT字典以及小波基底組成的小波字典。二是訓(xùn)練字典，訓(xùn)練字典是根據(jù)實(shí)際數(shù)據(jù)自適應(yīng)的學(xué)習(xí)字典，這種字典在實(shí)際中已經(jīng)證明了可以對(duì)信號(hào)有更好的稀疏表示，但是自適應(yīng)訓(xùn)練的字典耗時(shí)較長(zhǎng)，應(yīng)用沒(méi)有解析字典方便。
當(dāng)我們采用解析字典對(duì)下采樣的MRI數(shù)據(jù)進(jìn)行重構(gòu)時(shí)，重構(gòu)模型可以寫成：
（2）
其中D是稀疏表示字典，在參考文獻(xiàn)[2]中采用小波基組成字典D。y是部分K空間數(shù)據(jù)，即下采樣后的K空間數(shù)據(jù)。Fu表示部分傅里葉變換，x是我們要重構(gòu)的MR圖像。對(duì)x進(jìn)行小波變換后的系數(shù)滿足稀疏條件，解這個(gè)目標(biāo)函數(shù)就可以得到精確重構(gòu)的MR圖像。在文獻(xiàn)[2]中，作者采用非線性共軛梯度下降算法解這個(gè)目標(biāo)函數(shù)。
當(dāng)采用自適應(yīng)訓(xùn)練學(xué)習(xí)稀疏字典時(shí)，一般是對(duì)圖像塊進(jìn)行訓(xùn)練得到字典，影響較大的有KSVD[7]訓(xùn)練模型，基于自適應(yīng)字典學(xué)習(xí)的MRI重構(gòu)模型可以寫為：
（3）
其中Ri是取圖像塊操作，是MR圖像x在字典域的稀疏系數(shù)。這種采用自適應(yīng)訓(xùn)練學(xué)習(xí)稀疏字典的MRI重構(gòu)方法影響較大的有文獻(xiàn)[8]。在文獻(xiàn)[8]中，作者把這個(gè)約束函數(shù)分成兩個(gè)子問(wèn)題：字典訓(xùn)練問(wèn)題和最小二乘問(wèn)題。字典訓(xùn)練子問(wèn)題可以寫成為：
（4）
解這個(gè)子問(wèn)題的時(shí)候先固定x，對(duì)上一次的重構(gòu)的x進(jìn)行字典訓(xùn)練，字典訓(xùn)練過(guò)程和文獻(xiàn)[7]KSVD算法的過(guò)程一樣，利用迭代訓(xùn)練字典D。最小二乘子問(wèn)題目標(biāo)函數(shù)可以寫成：
（5）
在這個(gè)子問(wèn)題中利用字典訓(xùn)練子問(wèn)題訓(xùn)練出來(lái)的字典D和稀疏系數(shù)，更新MR圖像x。由于這個(gè)子問(wèn)題是一個(gè)非約束的2范數(shù)形式，所以可以用最小二乘來(lái)解這個(gè)問(wèn)題。圖2是文獻(xiàn)[2]和文獻(xiàn)[8]在10%隨機(jī)下采樣時(shí)的重構(gòu)結(jié)果。文獻(xiàn)[2]重構(gòu)結(jié)果PSNR值為29.55dB，文獻(xiàn)[8]的重構(gòu)PSNR值為39.67dB。從PSNR值上來(lái)看，文獻(xiàn)[8]的重建結(jié)果比文獻(xiàn)[2]有了較大的提高，這說(shuō)明了自適應(yīng)訓(xùn)練的字典在對(duì)MR圖像的稀疏表示上有著比解析字典更好的效果。
圖2 腦部圖像10%隨機(jī)下采樣的重構(gòu)結(jié)果
4.總結(jié)與展望
稀疏表示理論挖掘信號(hào)的稀疏特性，利用MR圖像稀疏性構(gòu)建目標(biāo)函數(shù)重構(gòu)MR圖像，在降低K空間數(shù)據(jù)采樣率的同時(shí)不降低MR圖像品質(zhì)，大大降低了MRI成像過(guò)程的時(shí)間。本文介紹了兩種主要的基于稀疏表示的MRI重構(gòu)的模型，同時(shí)越來(lái)越多的人對(duì)于低秩矩陣的特性與稀疏性的聯(lián)系進(jìn)行了研究，相信這些研究會(huì)進(jìn)一步的推動(dòng)稀疏表示在MRI重構(gòu)領(lǐng)域的應(yīng)用。
參考文獻(xiàn)
[1]Donoho D pressed sensing[J].Information Theory，IEEE Transactions on，2006，52（4）：1289-1306.
[2]Lustig M，Donoho D，Pauly J M.Sparse MRI：The application of compressed sensing for rapid MR imaging[J].Magnetic resonance in medicine，2007，58（6）：1182-1195.
[3]Mallat S G，Zhang Z.Matching pursuits with time-frequency dictionaries[J].Signal Processing，IEEE Transactions on，1993，41（12）：3397-3415.
[4]Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit[J].Information Theory，IEEE Transactions on，2007，53（12）： 4655-4666.
[5]Chen S S，Donoho D L，Saunders M A.Atomic decompos-ition by basis pursuit[J].SIAM journal on scientific computing，1998，20（1）：33-61.
[6]焦李成，楊淑媛，劉芳，等.壓縮感知回顧與展望[J].電子學(xué)報(bào)，2011，39（7）：1651-1662.
貪婪算法的基本原理范文第3篇
考試隨筆 阮兒
意外 曾衛(wèi)星
摘走果子的那個(gè)人叫朋友 李莎莎
超級(jí)另類的檢討書
如此請(qǐng)假 如此批示
千奇百怪的外國(guó)高考
現(xiàn)代文閱讀應(yīng)試對(duì)策(下) 陳蒙
巧抓時(shí)態(tài)突破口 妙解中考單選題 盧愛(ài)龍
話題作文的審題 張達(dá)富
考場(chǎng)作文的"三避""三就" 徐大才
值得初學(xué)者借鑒的"拆分記憶"法和"陰陽(yáng)怪調(diào)"法 李全
獨(dú)有的方法讓我的高考作文僅扣2分 范麗麗
我為什么不花大量的時(shí)間做題 楊琦
一元二次方程題型全貌 王英
密度的測(cè)定方法 王元鋒，魏正宏
質(zhì)量守恒定律的考查法兩例 吳海洋，沈家文
學(xué)習(xí)歐姆定律應(yīng)注意的幾個(gè)問(wèn)題 張友金
傷腦筋的天平
四色猜想
價(jià)格令人乍舌的名畫(二)
海洋獵手
未來(lái)世界的幾種能源 郭新
決戰(zhàn)前夕 韓宏宜
"大話西游"式的高考作文
"苦讀"經(jīng) 陽(yáng)林霞
解解元對(duì)樂(lè)樂(lè)府
"英雄"的悲哀 吳勇
中外知名企業(yè)面試"奇招"
中考文言文閱讀開放性試題例說(shuō) 曹津源
非謂語(yǔ)動(dòng)詞考例精彩再現(xiàn) 王先玲
驗(yàn)證猜想類考題例析 張北春
現(xiàn)代文閱讀應(yīng)試對(duì)策(上) 陳蒙
遇到新題不會(huì)怎么辦 李瑞鵬
語(yǔ)文"學(xué)什么不考什么" 白海峰
定時(shí)定量練習(xí)每一種題型 夏晨鐘
七位朋友
電梯遇險(xiǎn)怎么辦
閱卷歸來(lái)話創(chuàng)新 顧明
巧用估算法解決物理問(wèn)題 王英
直覺(jué)思維法
提取公因式易犯的八種錯(cuò)誤 王保華
光的折射問(wèn)題例析 張友金
怎樣證明同一條直線上的四條線段成比例 金中鮮
巧求一元二次方程的公共根 宋子模
一例測(cè)電阻擴(kuò)展實(shí)驗(yàn)的分析 張金曦
拓展思維的微觀模擬題 鄒杰
雨衣上的學(xué)問(wèn)
生活中數(shù)學(xué)的問(wèn)與答 袁黎
窗外的風(fēng)景 陳文峰
過(guò)往 曲寒江
簡(jiǎn)單的結(jié)局 仇春雷
天使的"錯(cuò)誤" 明要楠
真假美猴王 劉成
我們班的花名冊(cè)
妙斷漏字詩(shī)
擁有專利中考加分等
弱水三千飲一瓢--考場(chǎng)話題作文策略藝術(shù)之組材篇 馬興貴
數(shù)學(xué)思想在有理數(shù)中的體現(xiàn) 金建來(lái)
長(zhǎng)度測(cè)量中幾個(gè)特殊問(wèn)題的分析 張友金
機(jī)械能一章的易錯(cuò)題辨析 王英
分子和原子一章的易錯(cuò)題辨析
添設(shè)輔助線拾遺 肖繼森
歷史學(xué)習(xí)中的比較法 劉海靜，叢華彬
一類幾何題的證明技巧 朱秀蘭
用玻璃板做幾個(gè)小實(shí)驗(yàn) 張友金
中考英語(yǔ)補(bǔ)全對(duì)話題型分析與解題指導(dǎo) 冬青
向教材要答案 朱文松
讓機(jī)器聽懂中國(guó)話等
改變命運(yùn)的《夜巡》 高飛
如何確定古木的年代
相似的浮沉 張北春
快樂(lè)萬(wàn)歲 高飛
走在晨曦 文志平
幾家歡樂(lè)幾家愁 陳丹華
心情小屋 高旭東
安徒生的再創(chuàng)作
人蟲大戰(zhàn) 王堯
數(shù)學(xué)家的笑話
美國(guó)高考的刁鉆考題
解決物理問(wèn)題的邏輯思想方法(三) 林迪
解中考英語(yǔ)"閱讀理解"題秘訣 任民
吃水果看性格
默寫情境題如何考(二) 邱會(huì)榮
考場(chǎng)作文審題"五要" 閆永鋒
向著每一個(gè)方向微笑 張翔
認(rèn)真
計(jì)劃·行動(dòng)·堅(jiān)持 佟欣
從中考看反意疑問(wèn)句 劉世一
小細(xì)節(jié)有大作用
從名著中學(xué)語(yǔ)言描寫(功能篇) 曹津源
"設(shè)而不求"與"不設(shè)而求" 周奕生
"等腰"障目,問(wèn)題多多 王保華
學(xué)會(huì)拾起生活的小樹枝--讀《改變一生的閃念》 曉君
改變一生的閃念 李陽(yáng)波
學(xué)生作文《起名字》評(píng)改 黑子
聚焦《一元二次方程》 李慶社
人造衛(wèi)星為什么會(huì)飛出地球
科學(xué)史上④個(gè)著名的夢(mèng)
70規(guī)則的魔力--復(fù)利的巨大能量
饅頭、餅干里的小洞洞
電梯里的兇殺案
超完美銜接
幽默叢林
大學(xué)生哥哥們的談話
真情傳遞
時(shí)空連線
2005年中考英語(yǔ)書面表達(dá)題集錦(一) 佴啟龍
找尋規(guī)律記憶化學(xué)方程式 徐雙華
創(chuàng)建"素材庫(kù)"妙用"整容術(shù)" 黃松海
作文擂臺(tái)
分散時(shí)間等于沒(méi)有時(shí)間 書源
與發(fā)電有關(guān)的中考物理題 王梅軍
你像他們中的哪一個(gè)
用幻想飛翔 小雨
當(dāng)你作弊的時(shí)候 劉墉
可怕的期末作文 查里琳·特雷爾
沒(méi)有天生的第一名——學(xué)習(xí)成績(jī)的轉(zhuǎn)變
不可忽視的非智力因素——班級(jí)環(huán)境的影響
數(shù)學(xué)解題意識(shí)當(dāng)先
聯(lián)想——數(shù)學(xué)解題的導(dǎo)航塔 任小牧
四邊形難點(diǎn)剖析 陳振良
讓古典詩(shī)詞成為作文的一道亮麗風(fēng)景
讓你的文章"會(huì)說(shuō)話" 李冬梅
動(dòng)詞不定式專項(xiàng)練習(xí)
中考物理實(shí)驗(yàn)題題型大觀 雨林
初中化學(xué)基本概念和基本原理復(fù)習(xí)方法及常見(jiàn)題型
虛擬世界也需知榮辱——一個(gè)大學(xué)生網(wǎng)友的心聲
放大你的價(jià)值
英漢文化的常見(jiàn)差異
世界最經(jīng)典的雕像
新新玩意兒(5)
地球的故事
A4紙帶來(lái)的驚嘆
巴霍姆的貪婪 李慶社
架橋
橡膠的黑與白
多普勒效應(yīng)與雷達(dá)測(cè)速
視覺(jué)的游戲(下)
骨灰盒里的鉆石
實(shí)習(xí)醫(yī)生的一星期
漫畫也能助學(xué)習(xí)
向偵探學(xué)習(xí)推理能力
貪婪算法的基本原理范文第4篇
關(guān)鍵詞：編譯原理；教學(xué)案例；相似性檢測(cè)
中圖分類號(hào)：G64文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1673-9795（2014）04（A）-0000-00
Design of an Integrated Application-oriented Teaching Instance
in “Compiler Principle”
ZHANG Ni，YAN Di-xin，LU Wei-zhong
（School of Electronic and Information Engineering， USTS， Suzhou 215011）
Abstract： Facing to the practice problems of the lack of the "compiler principle" teaching，the paper designed an integrated application-oriented teaching instance . The instance make compiler principle course as center， and integrate using of the relations knowledge of other professional courses，and has a similar detection function which can detect similarity of the students’ project， and verify the originality of students’ project. The design and implementation of the instance are completed by different combinations and expansion of knowledge. The instance make up for the deficiencies in teaching process， and also has a certain practicality.
Key words： Compiling Principles； teaching instance； similarity detection
“卓越工程師教育培養(yǎng)計(jì)劃”是教育部于2010年6月啟動(dòng)的為期10年（2010―2020年）的重大改革項(xiàng)目。該計(jì)劃旨在培養(yǎng)一大批創(chuàng)新能力強(qiáng)、適應(yīng)社會(huì)經(jīng)濟(jì)發(fā)展需要的高質(zhì)量工程技術(shù)人才[1-3]。編譯原理課程作為計(jì)算機(jī)專業(yè)卓越工程師培養(yǎng)計(jì)劃中一門核心專業(yè)基礎(chǔ)課程，在新形勢(shì)下要求其教學(xué)過(guò)程必須以學(xué)生為中心，鞏固理論知識(shí)，加強(qiáng)實(shí)踐教學(xué)，注重學(xué)生創(chuàng)新意識(shí)的培養(yǎng)。
然而，由于編譯原理課程教學(xué)內(nèi)容不僅包含形式語(yǔ)言、有限自動(dòng)機(jī)、正規(guī)文法、正規(guī)表達(dá)式和LL（1）分析法等理論知識(shí)，而且編譯的每個(gè)階段都包含大量的復(fù)雜算法，學(xué)生在學(xué)習(xí)過(guò)程中感到抽象和難以理解[4]。通過(guò)對(duì)國(guó)內(nèi)各高等院校教學(xué)現(xiàn)狀的調(diào)查，目前編譯原理課程教學(xué)過(guò)程中存在編譯教學(xué)難點(diǎn)較多[5]，實(shí)踐環(huán)節(jié)缺少實(shí)際應(yīng)用背景和以及未與其他課程進(jìn)行有效的融合[6]等幾個(gè)方面問(wèn)題。為了達(dá)到“卓越計(jì)劃”培養(yǎng)目標(biāo)，必須對(duì)現(xiàn)有的教學(xué)方法和手段進(jìn)行改革，探討如何將編譯原理課程的理論知識(shí)應(yīng)用于實(shí)踐或?qū)嶋H項(xiàng)目和如何加強(qiáng)編譯原理課程與其他計(jì)算機(jī)課程之間的聯(lián)系的問(wèn)題，更好地將理論知識(shí)點(diǎn)貫穿融合到實(shí)踐教學(xué)或?qū)嶋H項(xiàng)目中。
本文在“卓越計(jì)劃項(xiàng)目”的資助下，將案例教學(xué)法[7，12，13]引入編譯原理課程的教學(xué)過(guò)程中。通過(guò)選取恰當(dāng)?shù)睦碚撝R(shí)點(diǎn)，結(jié)合數(shù)據(jù)結(jié)構(gòu)、面向?qū)ο蟪绦蛟O(shè)計(jì)等計(jì)算機(jī)專業(yè)的相關(guān)課程，設(shè)計(jì)了一個(gè)能吸引學(xué)生興趣，實(shí)踐強(qiáng)化的綜合應(yīng)用型教學(xué)案例。
1 案例設(shè)計(jì)思想及意義
在計(jì)算機(jī)專業(yè)程序設(shè)計(jì)類課程的教學(xué)過(guò)程中，學(xué)生提交作業(yè)的形式是源程序的電子文檔，這為有些同學(xué)拷貝和抄襲提供了便利，不僅影響學(xué)生對(duì)課程的掌握度，還影響了老師判分的公正性。程序相似性檢測(cè)技術(shù)能夠?qū)W(xué)生提交的程序設(shè)計(jì)作業(yè)進(jìn)行檢測(cè)，驗(yàn)證學(xué)生作業(yè)的原創(chuàng)性，幫助教師在大量的學(xué)生作業(yè)中找出相似性較高，即存在抄襲嫌疑的作業(yè)對(duì)象[11]，也有利于發(fā)現(xiàn)學(xué)生的創(chuàng)新性成果。通常程序相似性檢測(cè)過(guò)程由程序源代碼預(yù)處理，源代碼轉(zhuǎn)化，相似性比較，結(jié)果檢測(cè)四個(gè)階段構(gòu)成。
在設(shè)計(jì)案例時(shí)，我們用編譯原理課程中詞法分析和語(yǔ)法分析算法思想來(lái)完成代碼相似性檢測(cè)過(guò)程中的源代碼預(yù)處理和源代碼轉(zhuǎn)化兩個(gè)階段，使用數(shù)據(jù)結(jié)構(gòu)課程中學(xué)過(guò)的字符串比較算法（如最長(zhǎng)公共子序列算法等）作為相似性檢測(cè)算法，可以選擇案例開發(fā)環(huán)境有Eclipse，VC6.0和VS2010等。
此案例以編譯原理課程為中心，結(jié)合了數(shù)據(jù)結(jié)構(gòu)、面向?qū)ο蟪绦蛟O(shè)計(jì)等計(jì)算機(jī)專業(yè)的相關(guān)課程，實(shí)現(xiàn)了具有程序相似性檢測(cè)功能的系統(tǒng)。大多數(shù)學(xué)生在理解和掌握案例中給出知識(shí)點(diǎn)的基礎(chǔ)上，通過(guò)對(duì)其進(jìn)行不同組合來(lái)完成案例的設(shè)計(jì)和程序?qū)崿F(xiàn)，達(dá)到教學(xué)的基本要求，基礎(chǔ)好的學(xué)生在掌握已給出案例的基礎(chǔ)上選擇更難的知識(shí)點(diǎn)來(lái)設(shè)計(jì)和實(shí)現(xiàn)案例，學(xué)到更多知識(shí)。使學(xué)生通過(guò)一個(gè)綜合案例的設(shè)計(jì)和實(shí)現(xiàn)，鞏固了多門課程的相關(guān)知識(shí)點(diǎn)，彌補(bǔ)了課程教學(xué)中缺乏實(shí)踐的問(wèn)題，加強(qiáng)計(jì)算機(jī)相關(guān)課程之間的橫向聯(lián)系，培養(yǎng)學(xué)生的學(xué)以致用的實(shí)踐能力和創(chuàng)新能力。
2 案例相關(guān)的知識(shí)點(diǎn)
案例教學(xué)法的核心是案例的設(shè)計(jì)，案例設(shè)計(jì)應(yīng)該與教學(xué)內(nèi)容、教學(xué)進(jìn)度相適宜，能恰當(dāng)?shù)厝谌胂嚓P(guān)的知識(shí)點(diǎn)。本案例的相關(guān)知識(shí)點(diǎn)有：與編譯原理課程相關(guān)的基于程序設(shè)計(jì)語(yǔ)言的詞法分析程序?qū)崿F(xiàn)方法（手工方式）和基于LEX的詞法分析程序?qū)崿F(xiàn)方法（自動(dòng)方式）；與數(shù)據(jù)結(jié)構(gòu)課程相關(guān)的一些字符串比較算法，如最長(zhǎng)公共子序列（LCS）算法，Halstead算法和RKR-GST算法等；以及有一定的面向?qū)ο缶幊袒A(chǔ)，能使用JAVA，C++，C#等其中一種語(yǔ)言編寫程序。學(xué)生在熟悉和掌握這些知識(shí)點(diǎn)的基礎(chǔ)上進(jìn)行案例的設(shè)計(jì)和實(shí)現(xiàn)。
2.1 詞法分析程序的實(shí)現(xiàn)方法
詞法分析程序的工作原理是，從左至右掃描源程序的字符串，按照詞法規(guī)則（正則文法規(guī)則）識(shí)別出一個(gè)個(gè)正確的單詞，并轉(zhuǎn)換成該單詞相應(yīng)的二元式（種別碼、屬性值），以數(shù)組、鏈表或文本文件等形式保存，交給后續(xù)模塊使用。通常構(gòu)造詞法分析程序有兩種方法。第一種是手工方式，即根據(jù)識(shí)別語(yǔ)言單詞的狀態(tài)轉(zhuǎn)換圖，使用某種高級(jí)程序設(shè)計(jì)語(yǔ)言，如C、C++、JAVA等，直接編寫詞法分析程序。第二種是自動(dòng)方式，即利用LEX工具自動(dòng)生成詞法分析程序。
2.1.1 基于程序設(shè)計(jì)語(yǔ)言的詞法分析程序
設(shè)計(jì)的主要思想就是構(gòu)造出目標(biāo)語(yǔ)言單詞符號(hào)的有窮自動(dòng)機(jī)（DFA）。手工方式實(shí)現(xiàn)詞法分析的程序的步驟分為四個(gè)階段，第一，定義目標(biāo)語(yǔ)言的可用符號(hào)表和構(gòu)詞規(guī)則，即目標(biāo)語(yǔ)言單詞的狀態(tài)轉(zhuǎn)換圖；第二，依次讀入源程序符號(hào)，對(duì)源程序進(jìn)行單詞切分和識(shí)別，直到源程序結(jié)束；第三，對(duì)正確的單詞，按照它的種別以〈記號(hào)類別，屬性值〉的形式保存在符號(hào)表（ 數(shù)組或鏈表）中；最后對(duì)不正確的單詞，做出錯(cuò)誤處理。
2.1.2 基于 LEX的詞法分析程序
LEX是一個(gè)詞法分析器[8]的自動(dòng)生成系統(tǒng)，它的輸入是一個(gè)文本文件，文件的擴(kuò)展名習(xí)慣用.l表示，稱之為L(zhǎng)EX源文件，該文件包含了用戶定義的正規(guī)表達(dá)式以及每個(gè)正規(guī)表達(dá)式相對(duì)應(yīng)的處理動(dòng)作。LEX的工作原理是將源程序中的正規(guī)式轉(zhuǎn)換成相應(yīng)的DFA，而相應(yīng)的動(dòng)作則插入到輸出的詞法分析器中適當(dāng)?shù)牡胤剑刂屏饔稍揇FA的解釋器掌握。對(duì)不同的源程序，這個(gè)解釋器是相同的。LEX最常見(jiàn)的版本是Flex，可以免費(fèi)得到。基于 LEX的詞法分析程序設(shè)計(jì)思路：編寫LEX源文件，按要求抽象出正規(guī)表達(dá)式，同時(shí)濾掉輸入串中所有的空格、Tab、回車及注釋，最終形成.l文件。最后使用Flex編譯器生成詞法分析程序。
2.2 字符串匹配算法
除了數(shù)據(jù)結(jié)構(gòu)課程已經(jīng)介紹的字符串匹配算法（KMP算法），本案例還可以使用其他的字符串匹配算法，如最長(zhǎng)公共子序列（LCS）算法，Halstead算法和RKR-GST算法等。依據(jù)詞法分析程序的輸出結(jié)果（單詞符號(hào)串），利用字符串匹配算法來(lái)度量?jī)蓚€(gè)標(biāo)記串的相似度。本案例提供這些算法的實(shí)現(xiàn)思想和源代碼，供學(xué)生參考和進(jìn)一步改進(jìn)。
2.2.1 最長(zhǎng)公共子序列（LCS）算法
LCS（Longest Common Subsequence）算法[9]即求兩個(gè)字符串的最長(zhǎng)公共子序列算法。算法的主要思想是用一個(gè)矩陣來(lái)記錄兩個(gè)字符串中所有位置的兩個(gè)字符之間的匹配情況，若是匹配則為1，否則為0。然后求出對(duì)角線最長(zhǎng)的1序列，其對(duì)應(yīng)的位置就是最長(zhǎng)公共子序列的位置。其算法由求最長(zhǎng)公共子序列的長(zhǎng)度Length（l，j）和最長(zhǎng)公共子序列LCS（A，B）兩步構(gòu)成。
2.2.2 Halstead算法
Halstead算法[10]以源代碼中出現(xiàn)的操作符和操作數(shù)為計(jì)數(shù)對(duì)象，以它們的出現(xiàn)次數(shù)作為計(jì)數(shù)目標(biāo)來(lái)測(cè)算程序容量和工作量。其基本原理是：統(tǒng)計(jì)每個(gè)程序段中用到的操作符和操作數(shù)，最終生成一個(gè)特征向量。操作符包括所使用編程語(yǔ)言的關(guān)鍵字、運(yùn)算符和標(biāo)準(zhǔn)庫(kù)名稱。操作數(shù)是指程序段中所有由用戶自己定義的符號(hào)串。系統(tǒng)為每個(gè)待檢測(cè)相似性的源代碼生成一個(gè)特征向量之后，再計(jì)算每?jī)蓚€(gè)向量之間的歐幾里德距離，若兩個(gè)程序段的特征向量之間的距離很小，就可以認(rèn)為這兩段程序很相似。
2.2.3 RKR-GST算法
RKR-GST （Running Karp Rabin Greedy String Tiling）是一種貪婪式字符串匹配算法[14]，循環(huán)求取兩個(gè)標(biāo)記串中未被匹配部分的最大公共子串，并根據(jù)相應(yīng)公式求出兩個(gè)字符串的相似度。對(duì)源程序代碼進(jìn)行相似性檢測(cè)的過(guò)程通常可分為兩個(gè)階段：第一階段，對(duì)源程序進(jìn)行詞法分析或語(yǔ)法分析，剔除與程序結(jié)構(gòu)無(wú)關(guān)的表面元素，產(chǎn)生標(biāo)準(zhǔn)化輸出。第二階段，采用字符串匹配技術(shù)兩兩比較各程序的標(biāo)準(zhǔn)化輸出，進(jìn)行相似度度量，求出其相似度。
3 案例設(shè)計(jì)與實(shí)現(xiàn)
本案例要求學(xué)生選擇一種熟悉的開發(fā)平臺(tái)（VC 6.0，Eclipse，VS 2010等），依照第二節(jié)中給出的基本知識(shí)點(diǎn)（學(xué)生需提前查閱相關(guān)資料，做好預(yù)習(xí)），通過(guò)對(duì)知識(shí)點(diǎn)的不同組合和擴(kuò)展，如基于程序設(shè)計(jì)語(yǔ)言的詞法分析程序+ LCS算法，基于 LEX的詞法分析程序+RKR-GST算法和基于程序設(shè)計(jì)語(yǔ)言的詞法分析程序+RKR-GST算法等，設(shè)計(jì)具有程序相似性檢測(cè)功能的系統(tǒng)，然后編程實(shí)現(xiàn)綜合教學(xué)案例系統(tǒng)。
在此，將以采用基于 LEX的詞法分析程序（自動(dòng)方式）來(lái)完成代碼預(yù)處理及轉(zhuǎn)換，使用RKR-GST算法進(jìn)行代碼相似性檢測(cè)為例，給出設(shè)計(jì)和實(shí)現(xiàn)程序相似性檢測(cè)系統(tǒng)的過(guò)程。在學(xué)生設(shè)計(jì)和實(shí)現(xiàn)本案例前，教師先演示這個(gè)已事先設(shè)計(jì)好的案例供學(xué)生參考，讓學(xué)生對(duì)案例實(shí)現(xiàn)過(guò)程有一個(gè)直觀的認(rèn)識(shí)。本次設(shè)計(jì)具體分為代碼預(yù)處理及轉(zhuǎn)換、將源代碼轉(zhuǎn)化為標(biāo)記串、RKR-GST算法實(shí)現(xiàn)及結(jié)果分析四個(gè)階段。
3.1代碼預(yù)處理及轉(zhuǎn)換階段
在理解有窮自動(dòng)機(jī)知識(shí)點(diǎn)的基礎(chǔ)上，結(jié)合第二節(jié)中給出的設(shè)計(jì)思想，設(shè)計(jì)了LEX源文件――LexScanning.l，其中自定義了一些詞法規(guī)則、getToken（）以及printToken（）等函數(shù)，實(shí)現(xiàn)了詞法分析功能，同時(shí)濾掉了用戶源程序中所有的空格、Tab、回車及注釋。如圖1所示。之后使用Flex編譯器將LexScanning.l文件編譯生成名為CiFa.exe詞法分析程序。
圖1 LexScanning.l文件
3.2將源代碼轉(zhuǎn)化為標(biāo)記串
在主程序中運(yùn)行時(shí)，通過(guò)創(chuàng)建一個(gè)線程來(lái)調(diào)用CiFa.exe文件，進(jìn)行詞法分析，將用戶源代碼轉(zhuǎn)化為標(biāo)記串。
3.2.1參數(shù)設(shè)置
STARTUPINFO si；
memset（&si，0，sizeof（STARTUPINFO））；
si.cb=sizeof（STARTUPINFO）；
si.dwFlags=STARTF_USESHOWWINDOW；
si.wShowWindow = SW_HIDE；
PROCESS_INFORMATION pi；
3.2.2 創(chuàng)建線程
CString cmd = _T（"CiFa.exe "）+m_file_path_1；
if（CreateProcess（_T（"CiFa.exe"），（LPTSTR）（LPCTSTR）cmd，NULL，NULL，F(xiàn)ALSE，0，NULL，NULL，&si，&pi））
{ WaitForSingleObject（pi.hProcess，INFINITE）；
CFile file（_T（"C：＼＼temp.txt"），CFile：：modeRead）；
……
dwFileLen=file.GetLength（）；
pBuf=new CHAR[dwFileLen+1]；
pBuf[dwFileLen]=0；
…… }
3.3 RKR-GST算法
兩個(gè)程序段之間的相似性即為它們對(duì)應(yīng)的標(biāo)記串之間的相似性。可將每個(gè)標(biāo)記串看成由若干個(gè)子串組成，那么兩個(gè)標(biāo)記串中相同的子串就是它們的公共子串，其相似性可用所有公共子串在整個(gè)串中所占的百分比表示。公式如下[14]：
其中： | A |、|B |為token串A、B的長(zhǎng)度。match（i，j，length ） ： 在 A 中起始位置為i，在B中起始位置為j， 長(zhǎng)度為n 的子串。Matches為公共子串集合。
案例中設(shè)計(jì)了函數(shù)void Greedy_String_Tiling （tile_type *tiles， char *A， char *B， unsigned MML） 循環(huán)求取兩個(gè)標(biāo)記串中未被匹配部分的最大公共子串，并根據(jù)公式求出兩個(gè)token串A、B的相似度。其中參數(shù) *tiles存放求出的所有最長(zhǎng)公共子串，*A和*B分別來(lái)存放字符串A和字符串B，MML給出公共子串應(yīng)達(dá)到的最小長(zhǎng)度。
4 系統(tǒng)的測(cè)試及結(jié)果分析
準(zhǔn)備了三個(gè)C語(yǔ)言源程序作為測(cè)試用例，其中測(cè)試用例一（test1.c）和測(cè)試用例二（test2.c）有少數(shù)變量名不一樣和源程序的組織結(jié)構(gòu)稍有差別之外，其他的內(nèi)容幾乎一樣。測(cè)試用例三（test3.c）與測(cè)試用例一和測(cè)試用例二在內(nèi)容和結(jié)構(gòu)上則完全不一樣。
4.1 test1.c與test2.c的比較
運(yùn)行程序，點(diǎn)擊“瀏覽”按鈕選擇要比較的兩個(gè)源程序文件test1.c和test2.c，點(diǎn)擊“詞法分析”按鈕輸出test1.c和test2.c經(jīng)詞法分析后的結(jié)果，如圖2所示。
圖2 詞法分析結(jié)果
接下來(lái)，設(shè)置相似閾值為5之后，點(diǎn)擊“比較”按鈕，則進(jìn)行兩個(gè)源程序的相似性比較，比較的結(jié)果如圖3所示。兩個(gè)文件的相似度為91.089112%，結(jié)果符合我們的預(yù)想。
圖3 相似性檢測(cè)結(jié)果
4.2 test1.c與test3.c的比較圖4給出了test1.c和test3.c的相似性檢測(cè)結(jié)果，過(guò)程與上面相類似。相似度為13.265306%，符合我們的預(yù)期。
圖4 相似性檢測(cè)結(jié)果
5 結(jié)語(yǔ)
本文給出了筆者在編譯原理教學(xué)過(guò)程中使用的一個(gè)案例。該案例以編譯原理課程為中心，結(jié)合數(shù)據(jù)結(jié)構(gòu)、面向?qū)ο蟪绦蛟O(shè)計(jì)等計(jì)算機(jī)核心專業(yè)課程，將幾門課程的知識(shí)點(diǎn)聯(lián)系在一起，突出“編譯原理”課程的實(shí)用性。學(xué)生在實(shí)現(xiàn)綜合案例之前，教師通過(guò)對(duì)已實(shí)現(xiàn)案例的演示，讓學(xué)生有對(duì)實(shí)驗(yàn)過(guò)程及要求有了直觀的了解，促使學(xué)生設(shè)計(jì)實(shí)現(xiàn)出更好的具有程序的相似性檢測(cè)功能系統(tǒng)，鞏固編譯原理和數(shù)據(jù)結(jié)構(gòu)等課程相關(guān)的知識(shí)點(diǎn)，激發(fā)學(xué)習(xí)興趣，提高學(xué)生的學(xué)習(xí)質(zhì)量和效率。今后的教學(xué)研究中，我們將對(duì)該案例進(jìn)行擴(kuò)展，使之能分析如.net等高級(jí)語(yǔ)言編寫的源程序代碼，增加一些新的知識(shí)點(diǎn)，進(jìn)而可供高年級(jí)學(xué)生在課程設(shè)計(jì)中使用。
參考文獻(xiàn)
[1] 林健.面向卓越工程師培養(yǎng)的研究性學(xué)習(xí)[J]. 高等工程教育研究，2011，（6）：5-15.
[2] 徐世軍，范偉，黃賢英.面向卓越工程師培養(yǎng)的專業(yè)課程教學(xué)實(shí)踐. 計(jì)算機(jī)教育.2013（13） 22-25.
[3] 李鋒，夏小玲.計(jì)算機(jī)軟件工程專業(yè)卓越計(jì)劃實(shí)踐教學(xué). 計(jì)算機(jī)教育.2013（13） 18-21.
[4] 李冬梅，施海虎."編譯原理"課程的教學(xué)研究與探索. 計(jì)算機(jī)教育.2008（08）：10-12.
[5] 張昱，陳意云，鄭啟龍. 編譯原理課程的教學(xué)方法和教材建設(shè)[J]. 中國(guó)大學(xué)教學(xué)，2005，（7）：61-62.
[6] 計(jì)衛(wèi)星，陳英等.簡(jiǎn)析計(jì)算機(jī)專業(yè)知識(shí)在編譯課程教學(xué)中的滲透與融合.計(jì)算機(jī)教育. 2010（03）：23-25.
[7] 秦艷琳，吳曉平.“信息安全數(shù)學(xué)基礎(chǔ)” 案例教學(xué)[J].計(jì)算機(jī)教育，2010（01）：141-144.
[8] 陳火旺，劉春林，譚慶平等. 程序設(shè)計(jì)語(yǔ)言編譯原理[M].北京：國(guó)防工業(yè)出版社，2000.
[9] 于海英.字符串相似度度量中LCS和GST算法比較[J].電子科技，2011（3）：101-103.
[10] Halstead， Howard M. Elements of Software Science[Z].Elsevier，1977.
[11] 張莉，周祖林.代碼相似性檢測(cè)在程序設(shè)計(jì)教學(xué)中的應(yīng)用.計(jì)算機(jī)教育.2009（13）：116-118.
[12] 張?jiān)虑伲瑢O冰.案例教學(xué)法在“大學(xué)信息技術(shù)”課程中的應(yīng)用研究[J].中國(guó)電力教育，2012，（25）：63-64.
