贪婪算法的基本原理

前言：想要写出一篇令人眼前一亮的文章吗？我们特意为您整理了5篇贪婪算法的基本原理范文，相信会为您的写作带来帮助，发现更多的写作思路和灵感。

贪婪算法的基本原理范文第1篇

关键词：压缩感知；图像快速重建；稀疏表示；小波分解；正交匹配追踪

中图分类号：TP391.41 文献标识码：A 文章编号：1007-9599 （2013） 01-0065-02

1 压缩感知概述

1.1 压缩感知理论

美国工程师奈奎斯特于1928年提出，又由信息论创始人香农于1948年将压缩感知理论加以说明并将其以定理形式进行引用。奈奎斯特理论认为，在转换模拟/数字信号时，如果采样频率2倍于信号最高频率时，那么采样后的数字信号就能够对原始信号的信息进行完整保留。在这种背景之下，近年来，美国科学家在此基础上提出了新的信息获取理论，也就是压缩感知。压缩感知理论认为，如果利用远低于奈奎斯特标准的方法实现对可压缩信号的数据采样，仍然可以将原始信号进行精确恢复。压缩感知理论一经提出，便解决了一系列发展与应用瓶颈，使其在各个领域都得到了巨大发展。

1.2 压缩感知原理

（1）基本原理。压缩传感信号x?Rn*1测量过程的公式为y=Ax?RM*1，M??N式中A表示测量矩阵，y表示所获取的信号测量矢量。而信号重建公式则表示为min||x||0，s.t.y=Ax式中||·||0表示x中非零值元素，即信号的稀疏度。信号重建公式属于组合优化问题，压缩感知理论的提出者认为，能够使用11范数的最小化对矩阵测量进行求解，其公式为min||x||1，s.t.y=Ax。

（2）组成部分。信号恢复算法，即以M个观测值对N长度的原始信号进行无失真恢复、矩阵测量，即保证当原始信号在维数降低时，维持在最小的信息损失量、信号稀疏表示这三部分组成了压缩感知的理论。

1）信号恢复算法。与奈奎斯特理论中线性感知特点不同，压缩感知理论中要复原信号，就要将非线性优化问题进行求解。目前压缩感知重建算法有三种，一是贪婪算法，它的特点是精度低且测量数据多，二是凸优化算法，其特点是精度高且测量数据少，三是统计优化算法，这种算法介于其他两种算法。2）测量矩阵。当信号x为长度N时，其在M??N个测量中进行重建，如果非零系数位置为已知，只要K?M，那么这个公式就有解。目前在采样方式上，较为常见的有JITTER采样、随机采样以及均匀采样等，而在测量波形上，则包括正交函数、随机波形以及高期随机波形等。3）信号稀疏表示。在可压缩信号的基础上，压缩感知可通过两步骤实现，即先设计不相关于变换基的测量矩阵并对其实施观测，得到测量向量后，从维度测量向量进行信号的重建。

2 基于压缩感知的图像快速重建方法设计

通过设计一种基于观测矩阵与多稀疏变换基的组合并利用正交匹配追踪计算法来重建图像，同时通过实验使用一级小波分解图像，将相似的分子量图像进行提取，而后应用于压缩感知技术实现对其的恢复操作，最终借助小波逆变换得到图像的快速重建效果。

2.1 观测矩阵、稀疏变换基与算法

在本实验中选取了不相同的稀疏变换基5种，分别是离散傅里叶、离散余弦以及三种各不相同的小波变换基。而观测矩阵则包括非常稀疏投影、局部哈达玛、非相关测量、BERNOULLI随机以及高斯随机矩阵5种。所采取的恢复算法则是贪婪算法中的正交匹配追踪算法。

从表1的数据结果显示，基于观测次数相同的条件下，本文提出的方法与直接将压缩感知重建技术应用于整幅图像相比，显著提升了其运行的时间与效率，另外对于重建图像的也有了相当明显的改善效果。

3 结语

将压缩感知理论应用于重建二维图像上，已获得较好的重建图像质量，本文在此基础上，利用观测矩阵、稀疏变换基的相关算法，并引入小波变换，设计了一种经改进后的图像快速重建方法，在获得同等重建质量的图像同时，还能够将程序运行时间明显缩短，使得图像快速重建的效率得到大幅度提升，因此具备一定的推广应用前景。

参考文献：

[1]王天荆，郑宝玉，杨震.基于自适应冗余字典的语音信号稀疏表示算法[J].电子与信息学报.2011，33（10）.

贪婪算法的基本原理范文第2篇

【关键词】稀疏表示；MRI；图像处理

1.引言

磁共振成像技术（Magnetic Resonance Imaging，MRI）是一种利用图像进行医疗诊断的检查技术。它没有电离辐射伤害，能够直接扫描出器官各个体层的图像，避免了开颅、开胸、开腹探查等手术。MRI技术可以给医生带来清晰实用的人体内部结构图像，在临床检查上得到普遍的应用。但是MRI有一个缺点，它的成像过程太过漫长，一次成像过程要10分钟到30分钟。因此如何快速地获取MRI图像就成为一个热点问题，而压缩感知[1]和稀疏表示理论在MRI上的应用使得在不改变现有MRI系统硬件的条件下减少成像时间成为可能。

2007年Lustig和Donoho等人发表了Sparse-MRI[2]，首次将压缩感知理论应用到MRI中。在SparseMRI方法中作者应用了MR图像在小波域的稀疏性，对下采样的K空间数据进行重建，取得较好的重建效果。此后MR图像的不同稀疏特性不断被挖掘，MRI重构的效果得到很大的提升。

2.稀疏表示理论

令信号，稀疏字典，稀疏系数。则信号可以表示为，其中是字典原子。是信号在字典域的稀疏系数，如果仅有K个非零项，或者中仅有K个大系数，其它都是接近0的小系数，则我们称是稀疏度为K。由于实际中K=N，所以我们只要记住这K个项的位置及值我们就可以精确重构信号x。稀疏度K越小，则系数越稀疏，重构信号x所需要保存的数据量就越少。字典D可以是解析字典，例如DCT基底、小波基底，也可以是自适应训练字典或随机字典。如图1是一维信号稀疏表示的示意图，白的方格表示0，不同的灰度表示不同的值。

图1 一维信号在高斯随机字典投影下的2稀疏表示

实际应用中我们通常是观测到有噪声的信号x，为了恢复原始信号我们建立如下的目标函数：

（1）

但是这个目标函数的求解是NP难问题，目前解该问题的方法主要有两种：

一种是贪婪算法，如匹配追踪（MP）[3]、正交匹配追踪（OMP）算法[4]；一种是松弛算法，比如基追踪算法（BP）[5]。

匹配追踪算法（Matching Pursuit，MP）是一种贪婪迭代算法，其基本思想在每一次的迭代过程中，从过完备原子库里选择与残差信号最匹配的原子来进行信号表达，同时从残差信号中剔除其投影，获得新的残差信号。当迭代次数达到设定值，或者重构残差小于设定阈值时，迭代停止。其算法流程如下：

输入：字典D，观测信号x，稀疏度L

输出：的L稀疏逼近%

初始化：残差r0=x，索引集，迭代次数t=1；

循环执行步骤1-5

步骤1：找出残差r0与字典D中最相似列dk的角标，所谓最相似，即：

步骤2：更新索引集，纪录找到的重建信号字典原子集合（也称为支撑集）Dt=[Dt-1，d]

步骤3：由最小二乘算法得到t%=argmin ||x-Dtt%||2

步骤4：更新残差rt=y-Dtt%，t=t+1

步骤5：判断迭代次数是否满足，若满足则停止迭代，否则继续执行步骤1。

由于MP算法中信号在已选定的原子上的投影并非正交的，MP算法每一次迭代结果有可能是次优，为获得收敛需要经过较多次的迭代。

3.稀疏表示在MRI领域的应用

信号的稀疏性是压缩感知理论的一个重要前提，在压缩感知MRI系统的设计中稀疏表示问题可以归结为稀疏字典的设计[6]。我们可以从不同的角度，对不同的字典进行分类，因此基于稀疏表示的MRI重构问题也会有不同的重构模型。例如我们可以把字典分为解析字典和训练字典两大类：一是解析字典，解析字典是由具有明确的数学理论推导直接产生的基底的集合，常用的如DCT基底组成的DCT字典以及小波基底组成的小波字典。二是训练字典，训练字典是根据实际数据自适应的学习字典，这种字典在实际中已经证明了可以对信号有更好的稀疏表示，但是自适应训练的字典耗时较长，应用没有解析字典方便。

当我们采用解析字典对下采样的MRI数据进行重构时，重构模型可以写成：

（2）

其中D是稀疏表示字典，在参考文献[2]中采用小波基组成字典D。y是部分K空间数据，即下采样后的K空间数据。Fu表示部分傅里叶变换，x是我们要重构的MR图像。对x进行小波变换后的系数满足稀疏条件，解这个目标函数就可以得到精确重构的MR图像。在文献[2]中，作者采用非线性共轭梯度下降算法解这个目标函数。

当采用自适应训练学习稀疏字典时，一般是对图像块进行训练得到字典，影响较大的有KSVD[7]训练模型，基于自适应字典学习的MRI重构模型可以写为：

（3）

其中Ri是取图像块操作，是MR图像x在字典域的稀疏系数。这种采用自适应训练学习稀疏字典的MRI重构方法影响较大的有文献[8]。在文献[8]中，作者把这个约束函数分成两个子问题：字典训练问题和最小二乘问题。字典训练子问题可以写成为：

（4）

解这个子问题的时候先固定x，对上一次的重构的x进行字典训练，字典训练过程和文献[7]KSVD算法的过程一样，利用迭代训练字典D。最小二乘子问题目标函数可以写成：

（5）

在这个子问题中利用字典训练子问题训练出来的字典D和稀疏系数，更新MR图像x。由于这个子问题是一个非约束的2范数形式，所以可以用最小二乘来解这个问题。图2是文献[2]和文献[8]在10%随机下采样时的重构结果。文献[2]重构结果PSNR值为29.55dB，文献[8]的重构PSNR值为39.67dB。从PSNR值上来看，文献[8]的重建结果比文献[2]有了较大的提高，这说明了自适应训练的字典在对MR图像的稀疏表示上有着比解析字典更好的效果。

图2 脑部图像10%随机下采样的重构结果

4.总结与展望

稀疏表示理论挖掘信号的稀疏特性，利用MR图像稀疏性构建目标函数重构MR图像，在降低K空间数据采样率的同时不降低MR图像品质，大大降低了MRI成像过程的时间。本文介绍了两种主要的基于稀疏表示的MRI重构的模型，同时越来越多的人对于低秩矩阵的特性与稀疏性的联系进行了研究，相信这些研究会进一步的推动稀疏表示在MRI重构领域的应用。

参考文献

[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].电子学报，2011，39（7）：1651-1662.

贪婪算法的基本原理范文第3篇

考试随笔 阮儿

意外 曾卫星

摘走果子的那个人叫朋友 李莎莎

超级另类的检讨书

如此请假 如此批示

千奇百怪的外国高考

现代文阅读应试对策(下) 陈蒙

巧抓时态突破口 妙解中考单选题 卢爱龙

话题作文的审题 张达富

考场作文的"三避""三就" 徐大才

值得初学者借鉴的"拆分记忆"法和"阴阳怪调"法 李全

独有的方法让我的高考作文仅扣2分 范丽丽

我为什么不花大量的时间做题 杨琦

一元二次方程题型全貌 王英

密度的测定方法 王元锋，魏正宏

质量守恒定律的考查法两例 吴海洋，沈家文

学习欧姆定律应注意的几个问题 张友金

伤脑筋的天平

四色猜想

价格令人乍舌的名画(二)

海洋猎手

未来世界的几种能源 郭新

决战前夕 韩宏宜

"大话西游"式的高考作文

"苦读"经 阳林霞

解解元对乐乐府

"英雄"的悲哀 吴勇

中外知名企业面试"奇招"

中考文言文阅读开放性试题例说 曹津源

非谓语动词考例精彩再现 王先玲

验证猜想类考题例析 张北春

现代文阅读应试对策(上) 陈蒙

遇到新题不会怎么办 李瑞鹏

语文"学什么不考什么" 白海峰

定时定量练习每一种题型 夏晨钟

七位朋友

电梯遇险怎么办

阅卷归来话创新 顾明

巧用估算法解决物理问题 王英

直觉思维法

提取公因式易犯的八种错误 王保华

光的折射问题例析 张友金

怎样证明同一条直线上的四条线段成比例 金中鲜

巧求一元二次方程的公共根 宋子模

一例测电阻扩展实验的分析 张金曦

拓展思维的微观模拟题 邹杰

雨衣上的学问

生活中数学的问与答 袁黎

窗外的风景 陈文峰

过往 曲寒江

简单的结局 仇春雷

天使的"错误" 明要楠

真假美猴王 刘成

我们班的花名册

妙断漏字诗

拥有专利中考加分等

弱水三千饮一瓢--考场话题作文策略艺术之组材篇 马兴贵

数学思想在有理数中的体现 金建来

长度测量中几个特殊问题的分析 张友金

机械能一章的易错题辨析 王英

分子和原子一章的易错题辨析

添设辅助线拾遗 肖继森

历史学习中的比较法 刘海静，丛华彬

一类几何题的证明技巧 朱秀兰

用玻璃板做几个小实验 张友金

中考英语补全对话题型分析与解题指导 冬青

向教材要答案 朱文松

让机器听懂中国话等

改变命运的《夜巡》 高飞

如何确定古木的年代

相似的浮沉 张北春

快乐万岁 高飞

走在晨曦 文志平

几家欢乐几家愁 陈丹华

心情小屋 高旭东

安徒生的再创作

人虫大战 王尧

数学家的笑话

美国高考的刁钻考题

解决物理问题的逻辑思想方法(三) 林迪

解中考英语"阅读理解"题秘诀 任民

吃水果看性格

默写情境题如何考(二) 邱会荣

考场作文审题"五要" 闫永锋

向着每一个方向微笑 张翔

认真

计划·行动·坚持 佟欣

从中考看反意疑问句 刘世一

小细节有大作用

从名著中学语言描写(功能篇) 曹津源

"设而不求"与"不设而求" 周奕生

"等腰"障目,问题多多 王保华

学会拾起生活的小树枝--读《改变一生的闪念》 晓君

改变一生的闪念 李阳波

学生作文《起名字》评改 黑子

聚焦《一元二次方程》 李庆社

人造卫星为什么会飞出地球

科学史上④个著名的梦

70规则的魔力--复利的巨大能量

馒头、饼干里的小洞洞

电梯里的凶杀案

超完美衔接

幽默丛林

大学生哥哥们的谈话

真情传递

时空连线

2005年中考英语书面表达题集锦(一) 佴启龙

找寻规律记忆化学方程式 徐双华

创建"素材库"妙用"整容术" 黄松海

作文擂台

分散时间等于没有时间 书源

与发电有关的中考物理题 王梅军

你像他们中的哪一个

用幻想飞翔 小雨

当你作弊的时候 刘墉

可怕的期末作文 查里琳·特雷尔

没有天生的第一名——学习成绩的转变

不可忽视的非智力因素——班级环境的影响

数学解题意识当先

联想——数学解题的导航塔 任小牧

四边形难点剖析 陈振良

让古典诗词成为作文的一道亮丽风景

让你的文章"会说话" 李冬梅

动词不定式专项练习

中考物理实验题题型大观 雨林

初中化学基本概念和基本原理复习方法及常见题型

虚拟世界也需知荣辱——一个大学生网友的心声

放大你的价值

英汉文化的常见差异

世界最经典的雕像

新新玩意儿(5)

地球的故事

A4纸带来的惊叹

巴霍姆的贪婪 李庆社

架桥

橡胶的黑与白

多普勒效应与雷达测速

视觉的游戏(下)

骨灰盒里的钻石

实习医生的一星期

漫画也能助学习

向侦探学习推理能力

贪婪算法的基本原理范文第4篇

关键词：编译原理；教学案例；相似性检测

中图分类号：G64文献标识码：A 文章编号：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

“卓越工程师教育培养计划”是教育部于2010年6月启动的为期10年（2010―2020年）的重大改革项目。该计划旨在培养一大批创新能力强、适应社会经济发展需要的高质量工程技术人才[1-3]。编译原理课程作为计算机专业卓越工程师培养计划中一门核心专业基础课程，在新形势下要求其教学过程必须以学生为中心，巩固理论知识，加强实践教学，注重学生创新意识的培养。

然而，由于编译原理课程教学内容不仅包含形式语言、有限自动机、正规文法、正规表达式和LL（1）分析法等理论知识，而且编译的每个阶段都包含大量的复杂算法，学生在学习过程中感到抽象和难以理解[4]。通过对国内各高等院校教学现状的调查，目前编译原理课程教学过程中存在编译教学难点较多[5]，实践环节缺少实际应用背景和以及未与其他课程进行有效的融合[6]等几个方面问题。为了达到“卓越计划”培养目标，必须对现有的教学方法和手段进行改革，探讨如何将编译原理课程的理论知识应用于实践或实际项目和如何加强编译原理课程与其他计算机课程之间的联系的问题，更好地将理论知识点贯穿融合到实践教学或实际项目中。

本文在“卓越计划项目”的资助下，将案例教学法[7，12，13]引入编译原理课程的教学过程中。通过选取恰当的理论知识点，结合数据结构、面向对象程序设计等计算机专业的相关课程，设计了一个能吸引学生兴趣，实践强化的综合应用型教学案例。

1 案例设计思想及意义

在计算机专业程序设计类课程的教学过程中，学生提交作业的形式是源程序的电子文档，这为有些同学拷贝和抄袭提供了便利，不仅影响学生对课程的掌握度，还影响了老师判分的公正性。程序相似性检测技术能够对学生提交的程序设计作业进行检测，验证学生作业的原创性，帮助教师在大量的学生作业中找出相似性较高，即存在抄袭嫌疑的作业对象[11]，也有利于发现学生的创新性成果。通常程序相似性检测过程由程序源代码预处理，源代码转化，相似性比较，结果检测四个阶段构成。

在设计案例时，我们用编译原理课程中词法分析和语法分析算法思想来完成代码相似性检测过程中的源代码预处理和源代码转化两个阶段，使用数据结构课程中学过的字符串比较算法（如最长公共子序列算法等）作为相似性检测算法，可以选择案例开发环境有Eclipse，VC6.0和VS2010等。

此案例以编译原理课程为中心，结合了数据结构、面向对象程序设计等计算机专业的相关课程，实现了具有程序相似性检测功能的系统。大多数学生在理解和掌握案例中给出知识点的基础上，通过对其进行不同组合来完成案例的设计和程序实现，达到教学的基本要求，基础好的学生在掌握已给出案例的基础上选择更难的知识点来设计和实现案例，学到更多知识。使学生通过一个综合案例的设计和实现，巩固了多门课程的相关知识点，弥补了课程教学中缺乏实践的问题，加强计算机相关课程之间的横向联系，培养学生的学以致用的实践能力和创新能力。

2 案例相关的知识点

案例教学法的核心是案例的设计，案例设计应该与教学内容、教学进度相适宜，能恰当地融入相关的知识点。本案例的相关知识点有：与编译原理课程相关的基于程序设计语言的词法分析程序实现方法（手工方式）和基于LEX的词法分析程序实现方法（自动方式）；与数据结构课程相关的一些字符串比较算法，如最长公共子序列（LCS）算法，Halstead算法和RKR-GST算法等；以及有一定的面向对象编程基础，能使用JAVA，C++，C#等其中一种语言编写程序。学生在熟悉和掌握这些知识点的基础上进行案例的设计和实现。

2.1 词法分析程序的实现方法

词法分析程序的工作原理是，从左至右扫描源程序的字符串，按照词法规则（正则文法规则）识别出一个个正确的单词，并转换成该单词相应的二元式（种别码、属性值），以数组、链表或文本文件等形式保存，交给后续模块使用。通常构造词法分析程序有两种方法。第一种是手工方式，即根据识别语言单词的状态转换图，使用某种高级程序设计语言，如C、C++、JAVA等，直接编写词法分析程序。第二种是自动方式，即利用LEX工具自动生成词法分析程序。

2.1.1 基于程序设计语言的词法分析程序

设计的主要思想就是构造出目标语言单词符号的有穷自动机（DFA）。手工方式实现词法分析的程序的步骤分为四个阶段，第一，定义目标语言的可用符号表和构词规则，即目标语言单词的状态转换图；第二，依次读入源程序符号，对源程序进行单词切分和识别，直到源程序结束；第三，对正确的单词，按照它的种别以〈记号类别，属性值〉的形式保存在符号表（ 数组或链表）中；最后对不正确的单词，做出错误处理。

2.1.2 基于 LEX的词法分析程序

LEX是一个词法分析器[8]的自动生成系统，它的输入是一个文本文件，文件的扩展名习惯用.l表示，称之为LEX源文件，该文件包含了用户定义的正规表达式以及每个正规表达式相对应的处理动作。LEX的工作原理是将源程序中的正规式转换成相应的DFA，而相应的动作则插入到输出的词法分析器中适当的地方，控制流由该DFA的解释器掌握。对不同的源程序，这个解释器是相同的。LEX最常见的版本是Flex，可以免费得到。基于 LEX的词法分析程序设计思路：编写LEX源文件，按要求抽象出正规表达式，同时滤掉输入串中所有的空格、Tab、回车及注释，最终形成.l文件。最后使用Flex编译器生成词法分析程序。

2.2 字符串匹配算法

除了数据结构课程已经介绍的字符串匹配算法（KMP算法），本案例还可以使用其他的字符串匹配算法，如最长公共子序列（LCS）算法，Halstead算法和RKR-GST算法等。依据词法分析程序的输出结果（单词符号串），利用字符串匹配算法来度量两个标记串的相似度。本案例提供这些算法的实现思想和源代码，供学生参考和进一步改进。

2.2.1 最长公共子序列（LCS）算法

LCS（Longest Common Subsequence）算法[9]即求两个字符串的最长公共子序列算法。算法的主要思想是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长公共子序列的位置。其算法由求最长公共子序列的长度Length（l，j）和最长公共子序列LCS（A，B）两步构成。

2.2.2 Halstead算法

Halstead算法[10]以源代码中出现的操作符和操作数为计数对象，以它们的出现次数作为计数目标来测算程序容量和工作量。其基本原理是：统计每个程序段中用到的操作符和操作数，最终生成一个特征向量。操作符包括所使用编程语言的关键字、运算符和标准库名称。操作数是指程序段中所有由用户自己定义的符号串。系统为每个待检测相似性的源代码生成一个特征向量之后，再计算每两个向量之间的欧几里德距离，若两个程序段的特征向量之间的距离很小，就可以认为这两段程序很相似。

2.2.3 RKR-GST算法

RKR-GST （Running Karp Rabin Greedy String Tiling）是一种贪婪式字符串匹配算法[14]，循环求取两个标记串中未被匹配部分的最大公共子串，并根据相应公式求出两个字符串的相似度。对源程序代码进行相似性检测的过程通常可分为两个阶段：第一阶段，对源程序进行词法分析或语法分析，剔除与程序结构无关的表面元素，产生标准化输出。第二阶段，采用字符串匹配技术两两比较各程序的标准化输出，进行相似度度量，求出其相似度。

3 案例设计与实现

本案例要求学生选择一种熟悉的开发平台（VC 6.0，Eclipse，VS 2010等），依照第二节中给出的基本知识点（学生需提前查阅相关资料，做好预习），通过对知识点的不同组合和扩展，如基于程序设计语言的词法分析程序+ LCS算法，基于 LEX的词法分析程序+RKR-GST算法和基于程序设计语言的词法分析程序+RKR-GST算法等，设计具有程序相似性检测功能的系统，然后编程实现综合教学案例系统。

在此，将以采用基于 LEX的词法分析程序（自动方式）来完成代码预处理及转换，使用RKR-GST算法进行代码相似性检测为例，给出设计和实现程序相似性检测系统的过程。在学生设计和实现本案例前，教师先演示这个已事先设计好的案例供学生参考，让学生对案例实现过程有一个直观的认识。本次设计具体分为代码预处理及转换、将源代码转化为标记串、RKR-GST算法实现及结果分析四个阶段。

3.1代码预处理及转换阶段

在理解有穷自动机知识点的基础上，结合第二节中给出的设计思想，设计了LEX源文件――LexScanning.l，其中自定义了一些词法规则、getToken（）以及printToken（）等函数，实现了词法分析功能，同时滤掉了用户源程序中所有的空格、Tab、回车及注释。如图1所示。之后使用Flex编译器将LexScanning.l文件编译生成名为CiFa.exe词法分析程序。

图1 LexScanning.l文件

3.2将源代码转化为标记串

在主程序中运行时，通过创建一个线程来调用CiFa.exe文件，进行词法分析，将用户源代码转化为标记串。

3.2.1参数设置

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 创建线程

CString cmd = _T（"CiFa.exe "）+m_file_path_1；

if（CreateProcess（_T（"CiFa.exe"），（LPTSTR）（LPCTSTR）cmd，NULL，NULL，FALSE，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算法

两个程序段之间的相似性即为它们对应的标记串之间的相似性。可将每个标记串看成由若干个子串组成，那么两个标记串中相同的子串就是它们的公共子串，其相似性可用所有公共子串在整个串中所占的百分比表示。公式如下[14]：

其中： | A |、|B |为token串A、B的长度。match（i，j，length ） ： 在 A 中起始位置为i，在B中起始位置为j， 长度为n 的子串。Matches为公共子串集合。

案例中设计了函数void Greedy_String_Tiling （tile_type *tiles， char *A， char *B， unsigned MML） 循环求取两个标记串中未被匹配部分的最大公共子串，并根据公式求出两个token串A、B的相似度。其中参数 *tiles存放求出的所有最长公共子串，*A和*B分别来存放字符串A和字符串B，MML给出公共子串应达到的最小长度。

4 系统的测试及结果分析

准备了三个C语言源程序作为测试用例，其中测试用例一（test1.c）和测试用例二（test2.c）有少数变量名不一样和源程序的组织结构稍有差别之外，其他的内容几乎一样。测试用例三（test3.c）与测试用例一和测试用例二在内容和结构上则完全不一样。

4.1 test1.c与test2.c的比较

运行程序，点击“浏览”按钮选择要比较的两个源程序文件test1.c和test2.c，点击“词法分析”按钮输出test1.c和test2.c经词法分析后的结果，如图2所示。

图2 词法分析结果

接下来，设置相似阈值为5之后，点击“比较”按钮，则进行两个源程序的相似性比较，比较的结果如图3所示。两个文件的相似度为91.089112%，结果符合我们的预想。

图3 相似性检测结果

4.2 test1.c与test3.c的比较图4给出了test1.c和test3.c的相似性检测结果，过程与上面相类似。相似度为13.265306%，符合我们的预期。

图4 相似性检测结果

5 结语

本文给出了笔者在编译原理教学过程中使用的一个案例。该案例以编译原理课程为中心，结合数据结构、面向对象程序设计等计算机核心专业课程，将几门课程的知识点联系在一起，突出“编译原理”课程的实用性。学生在实现综合案例之前，教师通过对已实现案例的演示，让学生有对实验过程及要求有了直观的了解，促使学生设计实现出更好的具有程序的相似性检测功能系统，巩固编译原理和数据结构等课程相关的知识点，激发学习兴趣，提高学生的学习质量和效率。今后的教学研究中，我们将对该案例进行扩展，使之能分析如.net等高级语言编写的源程序代码，增加一些新的知识点，进而可供高年级学生在课程设计中使用。

参考文献

[1] 林健.面向卓越工程师培养的研究性学习[J]. 高等工程教育研究，2011，（6）：5-15.

[2] 徐世军，范伟，黄贤英.面向卓越工程师培养的专业课程教学实践. 计算机教育.2013（13） 22-25.

[3] 李锋，夏小玲.计算机软件工程专业卓越计划实践教学. 计算机教育.2013（13） 18-21.

[4] 李冬梅，施海虎."编译原理"课程的教学研究与探索. 计算机教育.2008（08）：10-12.

[5] 张昱，陈意云，郑启龙. 编译原理课程的教学方法和教材建设[J]. 中国大学教学，2005，（7）：61-62.

[6] 计卫星，陈英等.简析计算机专业知识在编译课程教学中的渗透与融合.计算机教育. 2010（03）：23-25.

[7] 秦艳琳，吴晓平.“信息安全数学基础” 案例教学[J].计算机教育，2010（01）：141-144.

[8] 陈火旺，刘春林，谭庆平等. 程序设计语言编译原理[M].北京：国防工业出版社，2000.

[9] 于海英.字符串相似度度量中LCS和GST算法比较[J].电子科技，2011（3）：101-103.

[10] Halstead， Howard M. Elements of Software Science[Z].Elsevier，1977.

[11] 张莉，周祖林.代码相似性检测在程序设计教学中的应用.计算机教育.2009（13）：116-118.

[12] 张月琴，孙冰.案例教学法在“大学信息技术”课程中的应用研究[J].中国电力教育，2012，（25）：63-64.