编辑距离求解的改进算法

摘要：

动态规划DP算法计算编辑距离的时间和空间开销均为0（m·n），它所用的编辑距离表可用于计算编辑操作的顺序。该文涉及的应用无须考虑编辑操作的顺序，为该文提出了一个空间开销为0（min (mn)）空间覆盖编辑距离求解算法。

关键词： 编辑距离 近似匹配 算法

作者: 马光志

作者单位: 理工大学(武汉)

会议类型: 国内会议

会议名称: 全国第十一次微计算机学术交流会

会议地点: 武昌

会议语种:中文

页码: 634～638

在线出版日期: 1998-11-01（万方平台首次上网日期，不代表论文的发表时间）