程序员的自我修养
Home » Java语言, 算法拾遗 » Levenshtein距离

Levenshtein距离

0条评论1,960次浏览

Levenshtein距离,又称为编辑距离,或者成为字符串相似度,意思是一个字符串转换为另一个字符串所需要的最小编辑次数。编辑包含:插入、删除和替换三种操作。例如字符串:yurnom和yunum的编辑距离为2,因为需要插入一个r和将u替换为o两次操作。

Levenshtein算法由俄罗斯科学家Vladimir Levenshtein在1965年提出,该算法现在广泛用于DNA匹配、字符串纠错、实体共指等领域。

算法简介

将2个字符串转换为一个矩阵,为了简单起见,采用字符串heqi和hoi。转换后进行初始化,如下所示:

h e q i
0 1 2 3 4
h 1 A
o 2
i 3

其中数字部分为初始化的值,现计算绿色格子A处的值,其算法为:

  1. 若A所对应的两个字符相同,则左上角蓝色格子的值+0,否则+1,结果记为R1
  2. 选取上方和左方紫色格子中较小的值,并+1,结果记为R2
  3. 选取R1和R2中的较小值为绿色格子A处的值

经过计算可以得出A处的值为0,当A处计算完毕后,其右方和下方的值可以接着进行计算了,如此整个矩阵的值将可全部计算出来。最后矩阵右下方红色格子的值即为两个字符串的编辑距离。

至于为何左方和上方的值加1、左上角的值根据不同的情况加0或1的原因(也就是这么算的原理)比较简单,在此不再详述。

Java实现

运行结果:

不足之处与改造方法

原算法采用矩阵来记录中间的结果,矩阵的大小为str1.length()*str2.length()。当我们计算两个超长字符串的相似度时(例如计算两篇文章的相似度),所需要的空间则会非常的大,例如:str1、str2长度为1W,矩阵大小则为100M,若每个int为64字节,则该矩阵占用内存为8*100M=800MB。

然而实际计算过程中,该矩阵记录的绝大部分值都为中间值,这些中间值在完成后续的计算后就毫无用处了。通过观察Levenshtein算法的具体过程,可以发现,实际上只需要2“行”或者2“列”值来记录中间结果即可满足计算的要求。

算法过程

为了简单起见,现展示计算字符串heqi、hoi的过程:

  1. 初始化rowB,用rowB来计算rowA
    h e q i
    rowB 0 1 2 3 4
    rowA h 1 0 1 2 3
    o 2
    i 3
  2. rowA此时为历史数据,用于计算rowB
    h e q i
    0 1 2 3 4
    rowA h 1 0 1 2 3
    rowB o 2 1 1 2 3
    i 3
  3. 再次交换rowA和rowB的角色,利用rowB来计算rowA
    h e q i
    0 1 2 3 4
    h 1 0 1 2 3
    rowB o 2 1 1 2 3
    rowA i 3 2 2 2 2

代码实现:

最后

可以看到改进后的方法占用空间在数量级上下降了,时间复杂度保持不变,依然是O(mn),m和n为两个字符串的长度。对于此方法,可以进一步改进:将较长的字符串“竖着”放,较短的字符串横着放(参考上述算法过程中的三个表格理解),这样在时间复杂度不变的情况下,所占用的空间最小化了,只不过一般情况下该方法意义不大,只有当两个字符串长度相差悬殊的情况下有意义,例如一个字符串100W长度,一个字符串1W长度。

(转载本站文章请注明作者和出处 程序员的自我修养 – SelfUp.cn ,请勿用于任何商业用途)
标签:,
发表评论


profile
  • 文章总数:79篇
  • 评论总数:402条
  • 分类总数:31个
  • 标签总数:44个
  • 运行时间:1013天

大家好,欢迎来到selfup.cn。

这不是一个只谈技术的博客,这里记录我成长的点点滴滴,coding、riding and everthing!

最新评论
  • 晴子: 在主节点初始化CM5数据库的时候报错误:Verifying that we can write to /opt/cm-5.9.0/etc/cloudera-scm -server log4j:ERROR Could not...
  • zhangnew: 就4题 :?:
  • linxh: “ 但要是遇到预先并不知道数组的长度而又需要获取正确的(或者称之 为原始的)split长度时,该如何处理呢。。? ” 印象中可以split函数参数传-1?
  • linxh: 班门弄斧一下: ssh host cmd 和直接ssh上后cmd结果不一样是因为ssh直接运行远程命令 是非交互非登录模式与ssh上去得到一个登录交互式Shell二 者加载的环境变量不一样。
  • 匿名: 其实文本分类和数字分类是一样的,只是文本分类需要多一个步骤, 就是计算它的tf-idf值将其转换为double类型
  • yurnom: 可能苹果最近又改变了返回值吧,最近没做测试了。 BadDeviceToken一般测试环境和正式环境弄错的情况 下会出现。
  • Anonymous: :razz: 博主,良心贴啊, 最近也在弄apns推送。 有个问题想请教你一下啊。 你博客中写的 Unregistered 错误,有准确的说明吗, 我看你博客中写的:...
  • 一波清泉: 回复邮箱: 1004161699@qq.com 多谢
  • Anonymous: 17/02/09 01:15:02 WARN Utils: Service ‘SparkUI’ could not bind on port 4040. Attempting port...
  • pacificLee: :twisted:
  • 小码: 为什么没有后面的呢,只有前10个
  • Anonymous: :lol:
  • Anonymous: :razz: 楼主是属于会聊天的。 我想问,sqoop发了几个版本了,应该没这些问题了吧。
  • Anonymous: Config.kafkaConfig.kafkaGroupI d 这个是指自己配置的group id 还是从 import org.apache.kafka.common.config .Config 这个类...
  • Anonymous: ZkUtils.getPartitionsForTopics (zkClient, Config.kafkaConfig.topic) 那个方法是在 spark-streaming_2.10 中 kafka...
  • Anonymous: ZkUtils.getPartitionsForTopics (zkClient, Config.kafkaConfig.topic) 你确定 kafka 里面有这个类 ? 个人在kafka 最新 稳定版...
  • Anonymous: :roll:
  • Anonymous: 很不错,试问有java版的吗?
  • Anonymous: 赞
  • Anonymous: 哈哈 看楼主的吐槽乐死了 where子句是可以写的 同样找不到资料 一点点试出来的 select id from xxxx where ${CONDITIONS} and 1=1 and 2=2 limit 4