Levenshtein 算法小记

我就是我 2022-09-30 04:54 123阅读 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 条评论，123人围观）

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

相关阅读

相关算法小记（一）

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

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

相关 Levenshtein 算法小记

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

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

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

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

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

相关 GeoHash算法小记

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

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

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

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

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

相关 SIFT算法学习小记

SIFT算法学习小记转载自：[http://www.cnblogs.com/saintbird/archive/2008/08/20/1271943.html][htt

刺骨的言语ヽ痛彻心扉/ 2022年05月20日 06:14/ 0 赞/ 157 阅读

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

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

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

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

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

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

相关算法小记：快速排序

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

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

相关 Levenshtein distance算法:计算两个字符串的差异

LEVENSHTEIN DISTANCE(LD)-计算两字符串相似度算法两字符串相似度计算方法有好多，现对基于编距的算法的相似度计算自己总结下。简单介

阳光穿透心脏的1/2处/ 2021年11月09日 10:18/ 0 赞/ 170 阅读