Standford NLP Course(2)

阅读: 评论:0

Standford NLP Course(2)

Standford NLP Course(2)

Minimum edit distance

How similar are two strings? letter scale / word scale
- Insertion
- Deletion
- Substitution

For two strings

X of length n
Y of length m
Define D(i,j)
the edit distance between X[1 … i] and Y[1 … j]
the edit distance between X and Y is D(n,m)

Dynamic Programming for Minimum edit distance动态规划计算最小编辑距离
Levenshtein 莱文斯顿距离
Bottom-up

1. 第一行 第一列加#,表示空字符
2. 空字符和任意x个字符距离都是x,因此第一行第一列直接填1 2 3…
3. 如果第i行第j列字母相同,比较左侧+1(insertion),下面+1(deletion),左下三个数字,取最小值
4. 如果第i行第j列字母不同,比较左侧+1,下面+1,左下+2三个数字(substitution),取最小值

Backtrace
得到距离,还需要知道它是怎么得来的
左侧:Insertion
下方:Deletion
左下:Substitution

Performance
Time: O(nm)
Space: O(mn)
Backtrace: O(m+n)

Weighted Minimum edit distance
Spell Correction: some letters are more likely to be mistyped than others
Biology: certain kinds of deletions or insertions are more likely than others

Minimum Edit Distance in Computational Biology
加了两种情况
所求的不是两者间的距离,而是两者的相似度
可以掐头去尾
但从视频里看更多地用于基因链条分析等等,算法也相对类似,就不仔细贴了

本文发布于:2024-02-01 20:43:19,感谢您对本站的认可!

本文链接:https://www.4u4v.net/it/170679140139307.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:Standford   NLP
留言与评论(共有 0 条评论)
   
验证码:

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23