科研之友
微信
新浪微博
Facebook
分享链接
摘要
最小编辑距离以其良好的抗噪性成为机器学习算法特征比对的重要手段。但是最小编辑距离经典算法时空复杂度均为O(n×m),较高的时空复杂度限制了最小编辑距离在大规模数据集及复杂特征计算中的运用。为了降低经典算法的时空复杂度,重点分析了经典算法的数学特性,论证了经典算法矩阵中相邻元素间的相互限制,说明了经典算法具有一定的自动纠错性,并以此为基础优化了经典算法,得到对任意序列时空复杂度都比经典算法(n/2)+1)2 (其中n为序列中较短者长度)的优化算法,并在实验部分的数据集中验证了本文算法的有效性。
- 单位
