这里是黄永亮的博客

2021年04月的存档

文章存档

20210424 Levenshtein距离解析

0.前言 距离上一次分析算法已经过去好几年了- -以我的算法水平其实是很讨厌分析算法的,一个是想写明白耗时很长,一个是说人话很啰嗦。但是写代码或公式又大部分人很难理解。今天要分析的算法是字符串相似度,Levenshtein距离 形式化描述:给定字符串strA,strB,求解dist(strA,strB)的值,dist为Levenshtein距离 说人话:两个字符串,编辑几次能变得完全一样,编辑允许的操作(插入,删除,替换字符) 0.定理/公理,人人都能看懂的情况 字符串基本操作: 连接 下文用+代表 删除字符 下文用 删除strA[0]表示 增加字符 下文用 str[x]=’ ...