基于最优路径策略方法快速计算字符串编辑距离

王远超; 安俊秀; 程芃森; 王鹏

首页> 中文期刊>成都信息工程学院学报 >基于最优路径策略方法快速计算字符串编辑距离

基于最优路径策略方法快速计算字符串编辑距离

开具论文收录证明 >>

期刊封面封底目录下载 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

传统编辑距离算法采用动态规划方法用一个维度大小分别为源字符串长度和目标字符串长度的二维数组保存计算过程中求得编辑距离值.这种传统求解方式在时间效率和空间效率上开销较大,限制了编辑距离算法在长字符串中地应用.针对传统方法存在的问题,经深入研究编辑距离的求解过程,发现在某个关键区域内存在一条最优路径,通过确定最优路径所在关键区域可以快速地求解两字符串之间的编辑距离值.实验表明,方法在计算两字符串之间的编辑距离与传统方法相比可以降低问题的求解规模,提高算法的时间效率和空间效率.所描述的方法同样适用于图论中使用动态规划方法求解一般问题地应用,比如最优分配问题和背包问题等.

著录项

来源
《成都信息工程学院学报》|2014年第6期|616-624|共9页
作者
王远超; 安俊秀; 程芃森; 王鹏;
展开▼
作者单位

成都信息工程学院软件工程学院,四川成都610225;

成都信息工程学院软件工程学院,四川成都610225;

成都信息工程学院软件工程学院,四川成都610225;

成都信息工程学院软件工程学院,四川成都610225;

展开▼
原文格式 PDF
正文语种 chi
中图分类算法理论;
关键词
计算机软件与理论; 大数据技术; 编辑距离; 相似度; 最优路径; 关键区域; 动态规划;
入库时间 2023-07-25 19:48:16

相似文献

中文文献
外文文献
专利

1. 基于编辑距离和相似度改进的汉字字符串匹配 [J] . 邵清 ,叶琨 . 电子科技 . 2016,第009期
2. 基于字符串编辑距离的图像检索算法 [J] . 郑一露 . 信息通信 . 2015,第007期
3. 基于改进编辑距离的字符串相似度求解算法 [J] . 姜华 ,韩安琪 ,王美佳 . 计算机工程 . 2014,第001期
4. 用字符串编辑距离算法筛选相似试题 [J] . 王禄 . 电脑编程技巧与维护 . 2017,第001期
5. 字符串编辑距离算法在网络竞赛试题筛选中的应用 [J] . 王禄 ,吴洋 ,王振光 . 山东冶金 . 2015,第005期
6. 基于性能的混凝土桥梁全寿命养护策略方法研究 [C] . 项贻强 ,吴强强 . 中国公路学会桥梁和结构工程分会2013年全国桥梁学术会议 . 2013
7. 基于编辑距离字符串Top-k相似性搜索算法的研究 [A] . 杨健 . 2015

基于最优路径策略方法快速计算字符串编辑距离

摘要

著录项

相似文献

相关主题

期刊订阅