基于基本操作序列的编辑距离顺序验证

• 作者: 张润梁 牛之贤
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 近似串搜索 编辑距离 顺序验证 基本操作序列
• 年，卷（期）: 2016,（z1）
• 所属期刊栏目: 智能计算
• 页码范围: 51-54
• 页数: 4页
• 分类号: TP391
• 字数: 4487字
• 语种: 中文

摘要

两字符串的编辑距离是从一个串转换到另一个串所需要的最少基本操作数.编辑距离广泛应用于字符串近似匹配、字符串相似连接等领域.动态规划法利用编辑距离矩阵来计算两个串的编辑距离,需要计算矩阵中的所有元素,时间效率低.改进的方法改变了矩阵中元素的计算次序,减少了需要比对的元素,但仍需要比对一半以上的元素,时间效率还有待提高.提出基于基本操作序列的编辑距离顺序验证方法.首先,分析了基本操作序列的可列性,给出了列举基本操作序列的方法.然后依次顺序验证基本操作数从小到大的基本操作序列直到某一序列通过验证,得到其编辑距离.在阈值为2的字符串近似搜索实验中发现,所提方法比动态规划类方法具有更高的效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	牛之贤	太原理工大学计算机科学与技术学院	14	74	4.0	8.0
2	张润梁	太原理工大学计算机科学与技术学院	1	3	1.0	1.0