一种扩展Winnowing剽窃检测算法

剽窃是目前学术界和教育界面临的普遍问题,成熟的商业化剽窃检测系统运行时间和经济代价高,不适合实时性、轻量级的学生作业等日常检测。对基于文本指纹的Winnowing剽窃检测算法进行扩展,在提取指纹的同时记录文本定位及其长度信息,给出了指纹提取、文本定位、剽窃指纹索引合并等算法,实现了剽窃文本的检测、定位、标记。实验结果及算法在应用系统中实际运行状况表明,算法的扩展对其性能影响不大,普通硬件配置条件下即可满足中小规模应用需求。扩展算法在原算法轻量级、高效率、可靠性和灵活度高等特点基础上,进一步拓展了Winnowing的功能,增强了原算法的适应性和应用价值。     

基于状态压缩的最长公共上升子序列快速算法

探讨了最长公共上升子序列（LCIS）问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列（LCS）和最长上升子序列（LIS）相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O（mn）、空间复杂度为O（m）或O（n）的基于状态压缩的快速LCIS算法。     

代码对比与动态规划

程序员几乎每天都在借助代码比较的工具来完成代码对比工作,粗浅地介绍了代码对比中的LCS问题以及通过动态规划来计算LCS.     

最长公共子序列算法在填空题评分程序中的应用

讨论最长公共子序列算法在填空题评分中的应用,并具体设计一种基于网络环境下,考试系统中的填空题题型的通用答案识别逻辑,在独立学院网络考试系统中操作可行。     

程序源代码剽窃检测串匹配算法的研究

检测剽窃的源代码,在验证学生的作业中很重要。代码的相似度度量是剽窃检测的关键技术。首先本文介绍了源代码剽窃检测技术在国内外的发展情况,然后提出了一种改进的基于Karp-Rabin和GST算法的程序源代码相似度测量方法。     

最长公共子充列问题的改进快速算法

现在几个最常用的解决最长公共子序列（ＬＣＳ）问题的算法的时间复杂度分别是Ｏ（ｐｎ）,Ｏ（ｎ（ｍｐ））。这里Ｍ、ｎ为两个待比较字符串的长度,Ｐ是最长公共子串的长度。给出一种时间复杂度为Ｏ（ｐ（ｍｐ））,空间复杂度为Ｏ（ｍ＋ｎ）的算法。与以前的算法相比,不管在Ｐ〈〈ｍ的情况下,还是在Ｐ接近Ｍ时,这种算法都有更快的速度。     

改进的基音检测方法及在音乐检索中的应用

基音检测是音频分析和基于内容的音乐检索中的关键技术,是基于内容音乐检索中实现哼唱检索的基础。提出一种改进的自相关函数（autocorrelation function,ACF）方法进行基音检测。从对音频信号进行去噪预处理、清浊音判断及后处理等方面对ACF进行改进,使之能够生成规整的音高变化曲线。在音乐检索的实现中,提出一种有限长度的最长公共子序列（Local Longest Common String,LLCS）方法,该方法可有效解决传统方法存在的误检问题。开发实现了一个通过哼唱/歌唱进行歌曲检索的原型系统。对大量的歌曲哼唱的实验表明,提出的改进ACF算法和LLCS算法对于提高检索正确率是正确有效的。     

动态规划算法在软件工程管理中的应用

软件工程学科在理论研究和实践应用中都取得了巨大成就，逐渐形成了方法、工具和管理三大要素。然而，这三要素的发展是不均衡的，相对于方法和工具，管理的理论研究和科学应用都显得滞后，已经成为软件工程学科发展的瓶颈问题。软件工程管理的本质是如何在软件工程生命周期的各个阶段最佳地配置人员、资金和时间三种资源，以取得软件质量最优化。它是一个多阶段决策问题．具有动态规划算法中多段图的特点。文中将动态规划算法应用到软件工程管理的决策之中。     

求解最长循环公共子序列问题的两个算法

最长循环公共子序列（LCCS）是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列（LCS）。针对穷举移位量求解LCCS效率过低的问题,设法对候选移位量进行筛选。通过证明循环移位操作对两字符串间LCS长度增量影响的上下限,得到最优移位量的必要条件,从而减小了求解LCCS的枚举量;在此基础上,建立了求解LCCS的迭代方法,只经过少数几次迭代便可消除绝大部分无效候选移位量;此外,还提出一个可在◢O（mn）◣时间复杂度下快速估算LCCS长度的近似算法。大量随机模拟表明,当两字符串间的相似度明显高于随机字符串的相似度时,提出的两种算法表现良好。     

基于比对相似度动态矩阵聚类算法在基因序列中的应用

基于BAG图的聚类算法 ,利用聚类单元引导类的分割 ,保证聚类结果不会产生过多的类碎片 ,但其相似分数阈值Cutoff初始值和最长公共子串最小长度阈值Threshold如何确定并没有明确给出。提出基于比对相似度动态矩阵的聚类算法 ,并在此基础上明确给出了确定cutoff初始值和Threshold阈值的方法。实验结果表明该算法可以获得较好的聚类正确率。     

基于行为motifs的多线程程序抄袭检测方法

软件动态胎记技术是实现混淆对抗的软件抄袭检测的有效手段之一.然而,多线程程序中线程交织的不确定性对其造成了不可忽视的影响;极端情况下,传统动态胎记技术甚至会判定同一个程序与其自身不存在抄袭关系.对此,提出从多线程程序在同一输入下的多条执行轨迹中进行相似部分的识别,并从中抽象出不易受线程交织影响的行为motifs来实现多线程程序的抄袭检测.该方法捕捉程序的动态执行轨迹,经过轨迹修剪、gram匹配以及扩展和抽象,从中提取motifs胎记建模多线程程序的行为;最终,通过衡量motifs胎记的相似性实现程序间潜在抄袭的判定.在一个包含234个不同版本多线程程序的公共数据集上开展的实验表明,motifs胎记是一种可靠的线程感知胎记方法,不仅可有效对抗当下主流的代码混淆技术,相比现有的2种多线程程序抄袭检测方法TreSB(thread-related system call birthmark)和TOB(thread-oblivious birthmark),也体现出更优秀的检测能力.     

基于动态规划的汉语句子相似度算法

传统汉语句子相似度计算算法在处理大量专业词汇时准确率较低。为此,提出一种基于动态规划的汉语句子相似度算法。通过获取2个句子的公共子串集合,结合链表消重机制,从集合中获取2个句子的所有最长公共子串,并以此计算相似度。实验结果表明,对于含有大量专有名词的问题集合,该算法的测试正确率达93.6%,计算效率较高。     

动态克隆选择算法在入侵检测应用中的研究

内嵌阴性选择算子的克隆选择算法（N-AIS）只能作为误用检测器,检测给定静态环境下的入侵行为,而不能自适应动态变化的网络环境.本文引入一种动态克隆选择算法DynamiCS对N-AIS进行扩展,并在人工生成的IDS环境中对影响DynamiCS性能的三个重要参数：耐受期、激活阈值和生命期进行了测试和分析.结果表明,它能够更好地处理和应用于入侵检测系统自身行为不断变化及每次仅提呈部分自身抗原的环境.     

基于分层匹配和最长公共子序列的SCD文件比较算法

IEC61850通信已经在电力系统中广泛使用,其中变电站通信系统使用SCD文件进行描述.SCD文件是XML格式的层次化结构,不适合直接用文本按行对比来分析差异.同时由于SCD文件层次结构多,使用纯结构化的比较方法,会导致比较结果冗长,执行效率低.本文基于SCD文件的特征,提出了分层匹配的半结构化半文本比较思路.先按照智能电子设备、连接接入点、逻辑设备等层次结构,提取关键属性名,进行对齐匹配.之后在逻辑设备范围内,针对逻辑节点的内容,采用最长公共子序列的匹配算法对比局部文本内容,该算法可去除仅调整顺序不影响实体内容的无效差异,比较速度快,比较结果准确直观.     

PCB贴装中供料器分配问题的动态规划改进算法

供料器分配问题是贴片机工艺优化问题中的一个关键问题,直接影响PCB贴装效率的高低;针对多头拱架型贴片机,首先根据取贴循环数,把问题分解为相互联系的子问题,然后针对每个取贴循环分别建立动态规划模型,并为了提高多阶段决策动态规划问题的搜索效率,提出了一种动态规划改进算法;当所有的子问题都获得解决后,整个供料器分配问题就获得解决;实验证明,所提算法能有效提高贴片机贴片效率,减少贴片时间。     

基于二维Gabor小波变换的角点匹配算法

图像配准研究的核心问题在于提高配准的速度和精度,而图像配准的结果主要取决于特征的匹配精度。为了提高特征匹配精度,本文提出了一种基于二维Gabor小波变换的角点匹配算法。该算法首先采用改进的Harris角点检测方法提取角点,得到角点位置的坐标,利用多个二维Gabor小波模板对参考图像和待配准图像进行滤波,从滤波图像中提取角点坐标处的复Gabor小波系数,并以此作为角点的特征描述,然后引入两种相似性度量因子对角点进行匹配。通过对不同图像进行大量的实验,该算法在选择合适的参数,同时采用最长公共子序列度量因子的情况下,能成功提取较多的同名点对,并且能够取得较高的匹配率。     

基于序列匹配的作业相似度检测系统

为辅助教师进行电子作业的批改和抄袭鉴别,设计并实现一种基于序列匹配的作业相似度检测系统。以班级为分组建立相似度计算模型,利用序列匹配算法计算公共子序列的长度,得到每组作业两两之间的相似度,并在此基础上进行聚类分析,给出可视化结果。实验结果表明,该系统具有较强的实用性,能够辅助教师在批改作业时快速高效地鉴别疑似抄袭的情况。     

基于FSA的DNA重复体频率统计算法

针对现有DNA重复体频率统计算法效率低、灵活性差等不足,基于字符串多模式匹配的有限状态自动机,构造DNA子序列比对自动机,利用KMP算法对自动机进行状态转移优化,由此提出一种高效的重复体频率统计算法。该算法通过对DNA数据库的线性扫描,得到每个DNA子序列在全局数据库中重叠与非重叠的重复体频率统计信息以及指定DNA序列集合的最长公共子序列信息。实验结果表明,该算法具有效率高、匹配精确、信息获取方式灵活、支持在线操作等优势。     

基于LCSS的数据流相似性查询处理算法研究

数据流相似性查询广泛应用于智能家居、环境监测等领域.当前以LCSS(longest common subsequence)作为相似性测度函数的研究并不多.NAIVE算法使用基本动态规划方法计算测度函数值,通过该值与相似阈值的比较得到查询结果,对基于LCSS的数据流相似性查询问题进行研究.针对NAIVE算法必须在动态规划矩阵所有成员取值的计算完成后才能得到查询结果的缺点,提出了一种基于PS(possible solution)-CC(column critical)域优化策略的数据流相似性查询处理算法.该算法划定了每个窗口上动态规划矩阵的PS域和CC域,很好地利用了这2个域中成员所具有的性质和相似性查询的特点,无须获得测度函数的最终值便可得到查询结果,省略了很多矩阵成员的计算.实验部分证明了该算法的有效性,与同类算法相比,在处理具有更高精度结果要求的查询时效果更好.