Java中使用Levenshtein距離實現(xiàn)字符串相似度匹配方式

更新時間：2025年06月07日 15:09:39 作者：一勺菠蘿丶

這篇文章主要介紹了Java中使用Levenshtein距離實現(xiàn)字符串相似度匹配方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

Levenshtein距離簡介

Levenshtein距離是由俄羅斯科學(xué)家Vladimir Levenshtein在1965年提出的，用以量化兩個字符串之間的差異。

這種度量方式計算將一個字符串轉(zhuǎn)換成另一個字符串所需要的最少編輯操作次數(shù)，包括插入、刪除和替換字符。

計算原理

Levenshtein距離的計算可以通過建立一個矩陣來完成：

初始化矩陣：創(chuàng)建一個(m+1)x(n+1)的矩陣，其中m和n是兩個字符串的長度。矩陣的第一行和第一列分別初始化為從0到m和0到n的序列，表示從空字符串到該長度的轉(zhuǎn)換所需的步驟。
填充矩陣：遍歷字符串，比較每個字符。如果字符相同，該位置的值為左上角的值；如果不同，取左（插入）、上（刪除）、左上（替換）三個方向的最小值加一。
獲取距離值：矩陣的最右下角的值即為兩字符串之間的Levenshtein距離。

相似度計算

通過Levenshtein距離，我們可以計算出兩個字符串的相似度，公式為：[ \text{相似度} = 1 - \frac{\text{Levenshtein距離}}{\max(\text{字符串A的長度}, \text{字符串B的長度})} ]這樣，相似度越接近1表示兩個字符串越相似。

在Java中的實現(xiàn)

首先，我們需要在Java項目中引入Apache Commons Lang庫，這個庫提供了計算Levenshtein距離的實用方法。

如果你的項目使用Maven進行依賴管理，可以在pom.xml文件中添加以下依賴：

<!-- 在 Maven 的 pom.xml 文件中添加 Apache Commons Lang 依賴 -->
<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-lang3</artifactId>
    <version>3.12.0</version>
</dependency>

接下來，我們將編寫一個Java類，其中包含一個方法來計算兩個字符串之間的相似度。

這個相似度是基于Levenshtein距離來計算的。

import org.apache.commons.lang3.StringUtils;

public class QuestionMatcher {
    // 計算兩個字符串之間的相似度的方法
    public static double calculateSimilarity(String input, String target) {
        // 計算兩個字符串的最大長度
        int maxLength = Math.max(input.length(), target.length());
        // 使用StringUtils工具類計算Levenshtein距離
        int editDistance = StringUtils.getLevenshteinDistance(input, target);
        // 根據(jù)Levenshtein距離計算相似度
        return 1.0 - (double) editDistance / maxLength;
    }
    
    public static void main(String[] args) {
        // 用戶輸入的問題
        String userQuestion = "如何煮雞蛋?";
        // 已知的問題數(shù)組
        String[] knownQuestions = {"如何煮沸雞蛋?", "如何煎雞蛋?", "如何剝雞蛋皮?"};
        
        // 初始化最高相似度和最佳匹配問題
        double highestSimilarity = 0;
        String bestMatch = null;
        
        // 遍歷已知問題，找到與用戶問題最相似的一個
        for (String question : knownQuestions) {
            double similarity = calculateSimilarity(userQuestion, question);
            if (similarity > highestSimilarity) {
                highestSimilarity = similarity;
                bestMatch = question;
            }
        }
        
        // 輸出最佳匹配的問題和其相似度
        System.out.println("最佳匹配問題: " + bestMatch + "，相似度: " + highestSimilarity);
    }
}

輸出結(jié)果

解釋代碼

calculateSimilarity方法：該方法接收兩個字符串參數(shù)，計算它們之間的Levenshtein距離，并轉(zhuǎn)換成相似度。相似度計算公式是 1 - (編輯距離 / 最大字符串長度)。這樣得到的相似度越接近1，表示兩個字符串越相似。
main方法：這是程序的入口。我們定義了一個用戶輸入的問題和一組已知問題。程序遍歷這些已知問題，計算每一個問題與用戶輸入問題之間的相似度，并找出相似度最高的問題作為最佳匹配。