You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
生物领域中DNA分析:比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列,那么这些两个序列很可能是同源的。在比对两个序列时,不仅要考虑完全匹配的字符,还要考虑一个序列中的空格或间隙(或者,相反地,要考虑另一个序列中的插入部分)和不匹配,这两个方面都可能意味着突变(mutation)。在序列比对中,需要找到最优的比对(最优比对大致是指要将匹配的数量最大化,将空格和不匹配的数量最小化)。
编辑距离
我们都用过在线字典,应该会有这样一个体验:在输入我们想要单词的前几个字母时,输入框下的提示框会给我们推荐若干个字母相近的单词。或者另一种用户体验:拼写检查。那么这些单词推荐是怎么实现的呢?程序是怎么知道我们想要的单词的呢?这里就需要引入编辑距离(Edit distance)的概念了。
简单来讲,两个单词的编辑距离就是单词 a 通过增加字母、删减字母和替换字母等操作变成单词 b ,在这个过程中总共进行了多少次操作便是这两个单词的编辑距离。
比如 snowy 和 sunny 两个单词,我们可以这样来进行编辑:
上下表格字符一一对齐来看:增加U、将O改为N、删除W,共3步,所以编辑距离是3。
上下表格字符一一对齐来看:增加S、将S改为U、删除O、删除W、增加N,共5步,所以编辑距离是5。
最小编辑距离(Levenshtein Distance)
题目描述:https://leetcode.com/problems/edit-distance/description/
莱文斯坦距离,又称Levenshtein距离,是编辑距离的一种。指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
即针对三种编辑操作,那么最优子结构应该是对这三种操作所得到的编辑距离进行求最小值。
最后对这三个操作的结果进行求最小值即可。
例如:
两个单词分别为 EXPONENTIAL 和 POLYNOMIAL。
并让第一行和列的值从0开始增长。矩阵的最后一个值d[n][m]即是它们的距离。
其中,子结构 E[4][3] 表示 EXPO 与 POL 的最小编辑距离。
一道题目:英文单词拼写纠错推荐
题目描述:
英文单词拼写的时候可能会出现拼写错误的情况(typo)。下面的题目,我们尝试实现拼写纠错推荐的功能。
字串编辑距离是衡量字串间相似度的常见手段。
①字串编辑距离:是指利用字符操作,把字符串A转换成字符串B所需要的最少操作数。
②字串操作包括:删除字符(removal)、插入字符(insertion)、修改字符(substitution)。
③使用以下规则对推荐纠错选项进行相似度排序。得分越高,认为相似度越低
只涉及到26个英文字符、不区分大小写。
删除(removal) 3分
插入(insertion) 3分
修改(substitution) :
(q w e r t a s d f g z x c v ) (y u i o p h j k l b n m)
以上两个分组内的字符修改 1 分,两个分组间字符修改 2 分。
输入:
每行一个输入。空格分割参数。 第一个参数是目标单词(可能存在 typo ) ,后面若干空格分割参数(个数不定)是字典单词,作为候选纠错项(也可能和第一个参数重复)。
输出:
按照上面的纠错规则字串相似度最小编辑距离进行排序,给出3个(如有)对应的纠错候选。 如得分相同,则按照输入顺序进行排序。
样例输入:
slep slap sleep step shoe shop snap slep
样例输出:
slep slap step
应用
最小编辑距离通常作为一种相似度计算函数被用于多种实际应用中,详细如下:(特别的,对于中文自然语言处理,一般以词为基本处理单元)
Reference
斯坦福课件
Levenshtein Distance
The text was updated successfully, but these errors were encountered: