专栏首页WebJ2EE算法:编辑距离(Levenshtein Distance)

算法:编辑距离(Levenshtein Distance)

1. 什么是“编辑距离” ?

“编辑距离”又称 Leveinshtein 距离,是由俄罗斯科学家 Vladimir Levenshtein 在 1965 年提出。

“编辑距离”是计算两个文本相似度的算法之一,字符串 X 和字符串 Y 的编辑距离是将 X 转换成 Y 的最小操作次数,这里的操作包括三种:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

例如:

kitten 和 sitting 的编辑距离是3。

  1. kitten -> sitten (k替换为s)
  2. sitten -> sittin (e替换为i)
  3. sittin -> sitting (插入g)

至少要做3次操作。

图文无关:从入门到放弃

2. 基本策略 ?

... 当然还是传说中的 ...

线性规划

图文无关

递推公式如下

3. 程序代码 ?

4. 特性分析

  • 时间复杂度:O(m*n)

本文分享自微信公众号 - WebJ2EE(WebJ2EE),作者:WEBJ2EE

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【前端】闭包(closure)

    计算机科学中,闭包(Closure)是引用了自由变量的函数。即使自由变量原来所属的内存空间不存在了,该自由变量也依然对该函数有效。闭包是函数和其相关的“环境”组...

    WEBJ2EE
  • JSP:自定义标签技术

    JSP 标签是 JavaServer Pages 技术中的特殊语法,它看起来就像普通的 HTML 或者 XML 标签一样。

    WEBJ2EE
  • 【前端笔试系列】:0x02

    WEBJ2EE
  • PPT模板图片怎么替换?这两种方法可以帮到你

    我们在制作PPT演示文稿的时候,都会选择套用别人的PPT模板。这样不仅可以减轻工作负担,还能让PPT更高大上。如果我们想要替换模板中的图片该怎么办呢?PPT模板...

    高效办公
  • 2.2Virtualbox高级应用构建本地大数据集群服务器

    版权声明:本文为王小雷原创文章,未经博主允许不得转载 https://blog.csdn.n...

    王小雷
  • 数组函数 array_column

    array_column 函数简介传入一个参数,返回二维数组中指定列传入一个参数,指定列不一定存在的情况传入两个参数,且两个参数对应的列都存在且不重复如果第二个...

    写PHP的老王
  • 经典笔试题-数据库及SQL篇

    106、有3 个表(15 分钟):【基础】 Student 学生表(学号,姓名,性别,年龄,组织部门) Course 课程表(编号,课程名称) Sc 选课...

    cwl_java
  • 业界 | 季维智院士:干细胞和基因编辑的优势与挑战

    “金刚狼”、“蜘蛛侠”,这些好莱坞大片里的超级英雄,都有一个共同特点,那就是他们都通过基因编辑技术改造了生殖细胞。

    大数据文摘
  • JavaScript 易错知识点整理

    本文是我学习JavaScript过程中收集与整理的一些易错知识点,将分别从变量作用域,类型比较,this指向,函数参数,闭包问题及对象拷贝与赋值这6个方面进行由...

    哲洛不闹
  • 初接触 Sass 与Compass 遇到的几个坑

    最近开始接触传说中高大上的CSS 预处理器之一Sass 以及Compass ,本文不会对Sass 与Compass 技术层面做过多介绍,只是记录自己折腾过程中遇...

    Jeff

扫码关注云+社区

领取腾讯云代金券