編輯距離算法其實(shí)就是，在規(guī)定的編輯操作(替換字符串、插入字符串、刪除字符串)中，經(jīng)過幾步可以把一個(gè)字符串變成另一個(gè)字符串，而這個(gè)所需的步數(shù)就是你的編輯距離。

測(cè)試樣例：

str1 = abc

str2 = yabd

表里的每一個(gè)值都代表著將str1轉(zhuǎn)換成str2所需要的步數(shù)，每個(gè)單元格的值都遵循這樣一個(gè)規(guī)律，第一行和第一列都是從0到n；其他的值要分情況計(jì)算，行索引和列索引對(duì)比大小，相同的話直接取左上方單元格的值，不同的話對(duì)比其左上方、左邊、上邊，找到三個(gè)單元格之中的最小值再加1即這個(gè)單元格的值。

str1		a	b	c
str2
	0	1	2	3
y	1	1	2	3
a	2	1	2	3
b	3	2	1	2
d	4	3	3	2

最后一個(gè)單元格的值就是兩個(gè)字符串間不同字符的個(gè)數(shù)，利用這個(gè)數(shù)與兩個(gè)字符串中最長(zhǎng)的長(zhǎng)度相除就得到了不相似的程度，再用1減去就是相似率。

public class FileCompared {public static void main(String[] args) {String str1 = "ABCDEFGZ";String str2 = "ABFDFEGXY";System.out.println("兩個(gè)字符串的相似率為：" + similarRates(str1,str2) +"%");}//定義一個(gè)similarRates方法獲取兩個(gè)字符串間不同字符的個(gè)數(shù)并求出兩個(gè)字符串的相似率public static int similarRates(String str1 , String str2){//確定二維距離表distance的維度int str1Len = str1.length();int str2Len = str2.length();//如果一個(gè)字符串的內(nèi)容為空就返回另一個(gè)字符串的長(zhǎng)度if (str1Len == 0) return str2Len;if (str2Len == 0) return str1Len;//定義一張二維距離表distanceint[][] distance = new int[str1Len + 1][str2Len + 1];//給二維數(shù)組的第一行第一列賦值int maxLen = str1Len > str2Len ? str1Len : str2Len;for (int num = 0; num < maxLen + 1; num++){if (num<str1Len + 1) distance[num][0] = num;if (num<str2Len + 1) distance[0][num] = num;}/*** 補(bǔ)全二維數(shù)組除第一行第一列的其他值* 行列索引進(jìn)行對(duì)比，相同的話直接取左上方值，不同的話采用最小距離算法*/for (int row = 1; row < str1Len+1; row++){char c1 = str1.charAt(row - 1);for (int col = 1; col < str2Len+1; col++){char c2 = str2.charAt(col - 1);if (c1 == c2) {distance[row][col] = distance[row - 1][col - 1];} else {// 最小距離算法就是，取該元素左上方值、左邊值、上邊值，找到三個(gè)之中的最小值再加1即最終距離distance[row][col] = mostMin(distance[row-1][col], distance[row][col-1], distance[row-1][col-1]) + 1;}}}//二維數(shù)組中的最后一個(gè)元素即是兩個(gè)字符串間不同字符的個(gè)數(shù)int notSimilarNum = distance[str1Len][str2Len];//求出相似率double similarRates = (1- (double)notSimilarNum / maxLen)*100;return (int)similarRates;}//取三個(gè)數(shù)中的最小值public static int mostMin(int up, int left, int upLeft){int min = up < left ? up : left;min = min < upLeft ? min : upLeft;return min;} }

如此便求出了兩個(gè)字符串的相似率，字符串換成讀取文件的話就可以得到兩個(gè)文件的相似度。

總結(jié)

以上是生活随笔為你收集整理的java实现编辑距离算法(levenshtein distance)，计算字符串或者是文本之间的相似度【附代码】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。