LCS算法在术语抽取中的应用研究

本文介绍了一种基于最大公共子串（Longest Common Substring,LCS）算法的术语抽取方法：按标点符号对领域文档进行切分;抽取切分后的语句片断的所有最大公共子串作为候选术语集;通过停用词过滤、对照领域词筛选和术语嵌套子串筛选等规则进行判别,得到最终的术语集。通过学前教育领域术语抽取的实验,验证了该算法可以有效地抽取中文领域术语：术语抽取平均准确率达84.2%;4～6字符双词术语抽取的效果尤佳,准确率接近100%。

改进的LCS方法在测试脚本序列比对中的应用

在自动化测试中,需要对录制和回放过程中的请求序列进行解析和比对,帮助用户进行脚本的修正和完善。为了实现请求序列的比对,采用最长公共子序列(LCS)算法对录制和回放的序列进行比较,其核心思想是把序列对比转化成图论问题,通过二维矩阵寻路来找到最优的匹配方式。文中对算法的原理和实现做了详细描述,并对算法的性能进行测试和分析,最后将算法应用到软件脚本修改器中,验证算法在自动化测试实际应用中的效果。结果表明,LCS算法可以高效地对序列进行解析和比对,提高了自动化测试的效率。

基于LCS的逻辑重构算法的研究

在逆向工程的研究中,逻辑重构中的等级簇聚合算法计算效率较低。为了改进计算效率,基于最长公共子序列(LCS)与高内聚的思想提出改进的逻辑重构算法。利用组件和数据表的关系以及存在交集的组件之间的相似程度来生成模块,并循环迭代,从而可以得到清晰的组件关系。与现有的等级簇聚合算法相比,该算法无需反复计算距离,时间复杂度更低,计算效率更高。

基于LCS的应急决策文本相似性比对分析模型

作为应急管理中的主要工作内容,应急决策在整个应急管理工作中具有战略意义,为了对危机情境下的应急决策主体进行聚类分析,定量计算不同决策主体之间相应决策文本的区别。借鉴最长公共子序列模型(LCS)的原理,从决策文本中提取主题词,根据决策文本的特点将其分为"目标"和"行动"2级,结合样本总体确定替换矩阵、空位罚分规则和目标函数,构建高层应急决策文本相似性比对分析模型;运用Needleman-Wunsch算法对该模型进行求解;通过对得到的地震情景下的高层应急决策文本的分析,证明模型的有效性和可行性;为了避免序列长度差过大对聚类分析的结果影响,在此基础上提出相对相似性得分的概念,并通过与VSM算法得到的结果进行比较,证明该模型在应急决策文本相似性分析中的优越性。

最长公共子序列算法在程序代码相似度度量中的应用

阐述了最长公共子序列算法在程序代码结构相似度度量中的应用,列举了两种计算最优值和一种获取最长公共标识符子序列的算法.根据最优值得到结构相似度值,进而可以查找出结构相似程序对.最后探讨了程序代码相似度的实际应用.

求最长公共子串长度的算法

给出求２个字符串最长公共子串（ＬＣＳ）长度的递归算法、递推算法和心动阵列算法．对２个长度分别为ｎ，ｍ（ｎ≥ｍ）的字符串，递归算法的最坏时空复杂性为（ｍ＋ｎ）！／（ｍ！ｎ！），而递推算法的时空复杂性分别仅为ｍ＋ｎｍ＋Ｏ（１），２ｍ＋Ｏ（１）．在心动阵列算法中，需ｍ个ＰＥ和ｎ＋ｍ的时间．最后给出了一个应用实例．

基于格代数的最长公共子序列近似求解

多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等。求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题。一些近似算法虽然时间复杂度较低,但只能求出单解,对于有多解的序列集合,求得的结果信息量损失较大。因此提出一个新的近似算法来解决最长公共子序列问题。算法引入了代数结构"格",通过动态规划求解出两条序列的公共格,并递归求解当前格与当前序列的公共格。公共格中的路径保存了多条公共子序列使得最终求解出的最长公共子序列为多个。对算法的相关定理给出了理论证明,并通过实验验证了算法的正确性。

基于改进编辑距离的字符串相似度求解算法

编辑距离(LD)算法在求解两个字符串的相似问题时只考虑了编辑操作次数,未考虑字符串之间的公共子串对相似度的影响。为此,提出一种基于改进编辑距离的字符串相似度求解算法,对字符串相似度度量公式及Levenshtein矩阵计算方法进行改进。在计算编辑距离时,以原有矩阵求出两字符串的最长公共子串及所有LD回溯路径。选取一个单词作为源串,一组与源串不同程度相似的单词为目标串,将改进的相似度度量公式与现有的字符串相似度计算方法进行比较,改进公式减少了进入胜者表的目标串数,相似度的样本极差和标准差分别为0.331和0.150。实验结果表明,改进算法在不改变空间复杂度的情况下,计算字符串相似度的准确性更高,且查询方式更灵活。

寻找序列的变化内容

寻找两个序列X、Y的差异内容,产生Y相对X的差异信息Z,使得X能够根据Z变化为Y。如果X、Y是同一种文件的不同版本,Z往往比Y小得多,这样存储或传送Z将比直接存储或传送Y更节约资源。提出一种基于序列结构因素的启发式算法,对两个序列进行划分,再进行相同内容的匹配。算法时间复杂度为O((n+m)log(min(n,m))),空间复杂度为O(n+m),其中n、m分别为X、Y的长度。在实际应用中该算法的执行速度是接近线性的。