* 编辑距离算法,首先由俄国科学家Levenshtein提出的,又叫Levenshtein Distance
* 主要用来计算从原串(s)转换到目标串(t)所需要的最少的插入,删除和替换的数目,
* 在NLP中应用比较广泛,同时也常用来计算你对原文所作的改动数
*/
public class Levenshtein {
private int compare(String str, String target) {
int d[][]; // 矩阵
int n = str.length();
int m = target.length();
int i; // 遍历str的
int j; // 遍历target的
char ch1; // str的
char ch2; // target的
int temp; // 记录相同字符,在某个矩阵位置值的增量,不是0就是1
if (n == 0) {
return m;
}
if (m == 0) {
return n;
}
d = new int[n + 1][m + 1];
for (i = 0; i <= n; i++) { // 初始化第一列
d[i][0] = i;
}
for (j = 0; j <= m; j++) { // 初始化第一行
d[0][j] = j;
}
for (i = 1; i <= n; i++) { // 遍历str
ch1 = str.charAt(i - 1);
// 去匹配target
for (j = 1; j <= m; j++) {
ch2 = target.charAt(j - 1);
if (ch1 == ch2) {
temp = 0;
} else {
temp = 1;
}
// 左边+1,上边+1, 左上角+temp取最小
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1]
+ temp);
}
}
return d[n][m];
}
private int min(int one, int two, int three) {
return (one = one < two ? one : two) < three ? one : three;
}
/**
* 获取两字符串的相似度
*
* @param str
* @param target
* @return
*/
public float getSimilarityRatio(String str, String target) {
return 1 - (float) compare(str, target)
/ Math.max(str.length(), target.length());
}
public static void main(String[] args) {
Levenshtein lt = new Levenshtein();
String str = "ABCDEF";
String target = "FECDBA";
System.out.println("similarityRatio="
+ lt.getSimilarityRatio(str, target));
}
}
分享到:
相关推荐
Levenshtein Distance(简称LD),又称编辑距离,是衡量两个字符串相似度的一种方法。这个概念由俄国科学家Vladimir Levenshtein在1965年提出,因此得名。 编辑距离定义了将一个字符串转换成另一个字符串所需的最少...
字符串相似度算法是一种衡量两个字符串之间相似度的方法,广泛应用于自然语言处理、数据挖掘、机器学习等领域。在本文中,我们将讨论一种常用的字符串相似度算法:Levenshtein Distance。 什么是Levenshtein ...
在计算机科学领域,字符串相似度比较算法是一种用于评估两个字符串之间相似程度的技术。这些算法广泛应用于文本处理、信息检索、生物信息学等多个领域。当我们要判断两个字符串是否含有相同或相近的信息时,这类算法...
### MySQL 计算字符串相似度 #### 背景与需求 在许多应用场景中,我们需要对两个字符串进行相似度比较,比如搜索引擎中的关键词匹配、文本分析中的近义词识别等。MySQL 提供了多种方法来实现字符串相似度的计算,...
《使用Delphi实现Levenshtein算法:计算字符串相似度》 在信息技术领域,字符串处理是常见的任务之一,其中计算两个字符串的相似度是尤为重要的一个环节。Levenshtein算法,也称为编辑距离算法,就是用于衡量两个...
【作品名称】:基于 java计算两字符串相似度和最长公共子序列 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【项目介绍】:基于 ...
字符串相似度计算通常用于找出两个字符串之间的相似程度,这在许多场景下都非常有用,例如拼写检查、搜索引擎排名、推荐系统等。有多种算法可以用来衡量字符串的相似性,包括但不限于: 1. **Levenshtein距离**:也...
Levenshtein算法,也称为编辑距离算法,是由俄国数学家Vladimir Levenshtein在1965年提出的一种衡量两个字符串相似度的方法。这个算法基于动态规划原理,可以计算出将一个字符串转换成另一个字符串所需要的最少单...
本主题将深入探讨“两个字符串相似度匹配”的概念、方法及其实现。 字符串相似度匹配旨在量化两个字符串之间的相似程度,通常以百分比的形式表示。它考虑了字符的顺序、重复以及缺失等因素,旨在找出字符串间的共同...
本篇文章将深入探讨如何使用DELPHI编程语言实现LCS(最长公共子序列)算法来衡量两个字符串的相似度。LCS算法是一种找出两个序列中最长的相同子序列的算法,它不考虑子序列的顺序,对于字符串而言,就是找到最长的...
用途:可用于论文抄袭检测、DNA等。...算法实现思路:通过对一个字符串插入、删除、替换转变成另一个字符串所需要的步骤称为距离,计算两个字符串之间的距离,从而可以得到两个字符串之间的相似度。
在IT领域,字符串相似度算法是一种非常重要的工具,特别是在数据挖掘、信息检索、文本分类以及自然语言处理等应用中。这个小例子旨在介绍如何通过计算字符串间的相似度来进行模糊匹配。我们将探讨几种常见的字符串...
就是一个简单的字符串相似度比较的方法,暂时还不知道有没有更好的方法,大家先看看,有更好的希望分享一下
java 计算字符串相似度
字符串相似度比较旨在量化两个或多个字符串之间的相似程度,通常以百分比形式表示。这种比较不仅关注字符串是否完全相同,还关注它们的差异程度。在文本处理中,完全相同的字符串被视为100%相似,而完全不同则为0%...
在文本分析或信息检索中,字符串相似度是指两个字符串之间的相似程度,通常通过某种距离度量(如Levenshtein距离、Jaccard相似度等)或者比较它们的共同部分来衡量。在这个项目中,我们关注的是基于LCS的相似度计算...
本资料“字符串相似度比较T-2021-7-1.rar”显然聚焦于探讨如何衡量两个字符串之间的相似程度,以及在特定情境下,如站名对比,如何应用这些方法。 字符串相似度比较的目标是量化两个字符串之间的相似性,这通常通过...
关于字符串相似度检测的一个很好用的C代码
一个实现不同字符串相似度和距离度量的库。目前实现了十几种算法(包括 Levenshtein 编辑距离和兄弟、Jaro-Winkler、最长公共子序列、余弦相似度等)。查看下面的汇总表以获取完整列表... python字符串相似度 下载 ...
字符串相似度是评估两个字符串之间相似程度的一种度量。在很多情况下,我们不关心字符串是否完全相同,而是关注它们之间的相似性。例如,拼写检查、自动补全、模糊搜索等功能就利用了字符串相似度的计算。 最短编辑...