Board 版 (精华区)

发信人: WeskitKeeper (马甲守护神), 信区: Board
标  题: [范文]最小编辑矩离学习笔记
发信站: 哈工大紫丁香 (Sat Nov 12 10:27:17 2005), 转信

论文阅读

谢欣 10208105

论文

Allison, L. “Dynamic programming algorithm (DPA) for editdistance.”

In Algorithms and Data Structures Research & Reference Material. School of Computer Science and Software Engineering, Monash University, Australia 3168. 1999

 

时间

2004年3月9日

 

笔记
1.      基本概念

编辑距离是指两个字符串通过插入字符、删除字符、改写字符而变为相同字符串所需要的操作次数。

比如：

d(“abc”,”abd”) = 1

d(“abc”,”ab”) = 1

d(“abc”, “abcdf”) = 2

d(“serverU”,” ser-u”)=4

显而易见，利用递规能够实现这个算法，但其时间和空间复杂度都不理想，为指数量级。本文作者就是要提出一个算法使计算更有效。
2.      算法

1）本文讨论了利用动态算法计算编辑距离的方法。

2）本方法的时间复杂性可以达到O(n2)，空间复杂性为O（n2）

3）如果更精确的表示，对于字符串s1和s2，时间复杂性为O(|s1|*|s2|)；对于空间复杂性，如果仅仅用于计算最终距离，利用垃圾回收策略，空间复杂性可以降至O(n)
3.      变形

1）计算最大共同子串
4.      相关研究

Ukkonen(1983)曾经给了一个算法，其最差时间复杂度为O(n*d)，平均时间复杂度为O(n+d2)。其中n是字符串的长度，d是他们的编辑距离。对于很小的字符串来说，当d<<n时，这个算法是很快的。
5.      应用

原文列出了很多应用，从生物学到语音识别等各个方面，可见作者射猎之广。
6.      体会

本文的算法讲解非常清晰易懂，文章也不长，但被很多其它文章所引用，还有很多后来人在研究对它的优化，可见本文章是很有价值的。

我这里附加的不是pdf格式的文章，而是一篇html格式的文件，作者可以用Javascript实现了这个算法，非常精炼，可以在页面直接运行。很有意思。
7.      和我们的实际关系

在文件搜索中，经常出现用户的查询词和实际文件名略有不同的情况，比如上面提到的serverU和serv-U等。如果应用此算法，则能够提高查全率。

--

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.236.206]