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

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

基于序列比对检测的优化SRE多态蠕虫防御方法

针对简化正则表达式(SRE)的多态蠕虫防御方法不足以处理蠕虫的不变部分和距离限制等问题,提出一种利用序列比对检测的优化SRE。比对一个序列在另一个序列上编写字符的过程包括3个步骤,即初始化步骤、矩阵填充和回溯步骤。初始化矩阵用于比较两个序列间字符的得分;填充矩阵选择最大数,保持指针指向导出参数的先前得分位置;回溯的每个分支代表一个最优的比对。考虑到上述步骤最大化了匹配总数量,而非匹配连续子串,采用逐对序列比对检测,对最长公共子串(LCS)的字符串进行匹配。评价结果表明,优化SRE方法能够成功获得连续序列,保留了多态蠕虫的所有通配符,相比于Autograph、Polygraph和SRE方法,其生成的特征码更加精确和高效。

多种字符串相似度算法的比较研究

对计算字符串相似度的编辑距离算法、最长公共子串算法、贪心字符串匹配算法、RKR-GST等多种算法,根据匹配过程是否有序,对这些算法进行了分类。然后对每种算法的实现原理进行了描述,并给出每个算法的运行步骤,结合一个实际的例子列出了算法运行的结果,最后给出每种算法计算相似度的计算公式和算法时间复杂度及应用领域。由于字符串相似度具有广泛的应用领域,对其中经典的几种算法进行总结对比是一件十分有意义的研究工作。

一种基于熵的文本相似性计算方法

文本比较是求解两个文本间相似度的过程,文本间的相似度越高代表两个文本越趋于类似。传统的相似度算法主要从字符的角度度量文本的相似性,忽略了文本内多个共同文本串对于文本相似度的影响。针对此问题提出一种基于熵的相似度求解方法,在对文本间字符信息的提取基础上,建立共同子文本串度量维度,然后采用熵的方法进行相似度度量。实验表明,该方法具有更平滑的相似度曲线,从而验证了算法的有效性和准确性。

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

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

代码抄袭检测中串匹配算法的比较

对程序代码抄袭检测中多种字符串匹配算法的实现原理进行了描述,给出匹配算法计算相似度的公式以及相对应的时间复杂度。由于字符串匹配算法在程序代码抄袭检测中应用较为广泛,对其中的B-F(Brute-Force)朴素算法、LCS(Longest Common Subsequence)最长公共字串算法、GST(Greedy String Tiling)贪心字符串匹配算法等经典算法的总结比较是一件有意义的研究工作。

字符串匹配的自动机方法

本文讨论了字符串的连续匹配、离散匹配及求解最长公共子串的自动机算法。

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

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