Levenshtein 算法小记

我就是我 2022-09-30 04:54 141阅读 0赞

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Levenshtein \{ public class SimilarityCompare \{ public int GetDistance(char\[\] src,char\[\] target) \{ //第一步，创建一个矩阵，列数为 src 长度+1，行数为 target 长度t+1 int\[,\] d;//矩阵 if (src.Length == 0) \{ return target.Length; \} if (target.Length == 0) \{ return src.Length; \} d = new int\[src.Length + 1, target.Length + 1\]; //第一步结束 //第二步，初始化矩阵 for (int x = 0; x <= src.Length; x++) \{ d\[x, 0\] = x;//设置第一行的初始值 \} for (int y = 0; y <= target.Length; y++) \{ d\[0, y\] = y;//设置第一列的初始值 \} //第二步结束 //第三步，计算距离 int cost=0; int above = 0; int left = 0; int diag = 0; for (int x = 1; x <= src.Length; x++) \{ for (int y = 1; y <= target.Length; y++) \{ if (src\[x - 1\] != target\[y - 1\]) \{ cost = 1; \} else \{ cost = 0; \} above = d\[x, y - 1\] + 1; left = d\[x - 1, y\] + 1; diag = d\[x - 1, y - 1\] + cost; d\[x, y\] = Math.Min(Math.Min(above, left), diag); \} \} //第三步结束 return d\[src.Length, target.Length\]; \} \} \}

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关算法小记（一）

1、生成指定个数的随机数组 C++实现： include <iostream> include <ctime> include <cassert>

冷不防/ 2024年01月20日 07:46/ 0 赞/ 38 阅读

相关 R语言文本比较算法：Levenshtein Distance（LD算法）

R语言文本比较算法：Levenshtein Distance（LD算法） Levenshtein Distance（编辑距离）是一种常用的文本比较算法，用于度量两个字符串之间

素颜马尾好姑娘i/ 2023年10月15日 11:34/ 0 赞/ 25 阅读

相关字符串相似度算法（编辑距离算法 Levenshtein Distance）

[字符串相似度算法（编辑距离算法 Levenshtein Distance）][Levenshtein Distance] 在搞验证码识别的时候需要比较字符代码的相似度用

小咪咪/ 2023年06月07日 08:08/ 0 赞/ 4 阅读

相关 Levenshtein 算法小记

using System; using System.Collections.Generic; using System.Linq; using System.Text;

我就是我/ 2022年09月30日 04:54/ 0 赞/ 142 阅读

相关 Levenshtein 相似度算法——Levenshtein(编辑距离)

[https://www.iteye.com/blog/wdhdmx-1343856][https_www.iteye.com_blog_wdhdmx-1343856] 原文

谁借莪１个温暖的怀抱￠/ 2022年08月28日 07:43/ 0 赞/ 189 阅读

相关 GeoHash算法小记

昨天被问到一道题目，感觉挺有意思，这里记录一下: 题目:给定一个m\m的矩形区域，已知一点的(x,y)坐标,如何找到离周围xkm的所有店家? 这里需要用到一个叫做

本是古典何须时尚/ 2022年06月07日 12:47/ 0 赞/ 212 阅读

相关 Levenshtein 算法：相似度--模糊查询，数据匹配

1.百度百科介绍： Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一

待我称王封你为后i/ 2022年05月31日 00:43/ 0 赞/ 252 阅读

相关 Levenshtein Distance （LD算法）编辑距离算法原理

莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括：将一个字符替换成另一个字符，插入一个

向右看齐/ 2022年02月22日 15:08/ 0 赞/ 336 阅读

相关数据对齐-编辑距离算法详解（Levenshtein distance）

总结一句话：编辑距离就是从一个字符串变到另外一个字符串所需要最小的步骤一：简介在信息论、语言学和计算机科学中，Levenshtein distance是用于测量两个

我会带着你远行/ 2022年01月19日 03:21/ 0 赞/ 307 阅读

相关算法小记：快速排序

一、思想快速排序是一种分治排序算法，将一个数组分成两个子数组，将两部分独立排序，当两个子数组都有序时整个数组就自然有顺序了。该方法的关键在与切分，这个过程

我不是女神ヾ/ 2021年12月01日 16:16/ 0 赞/ 241 阅读