您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 字串相似度演算法：Levenshtein Distance 完整實作解析

編輯：Java 相關知識

字串相似度比對在拼字檢查、DNA 序列分析、自然語言處理等場景極為常見。本文深入解析 Levenshtein Distance（編輯距離）演算法，並提供可直接用於生產環境的 Java 完整實作碼。

核心原理

Levenshtein Distance 定義為將字串 A 轉換為字串 B 所需的最少單字元編輯操作數（插入、刪除、替換）。演算法採用動態規劃，建立 (n+1) × (m+1) 矩陣 d，其中 d[i][j] 代表 str[0..i-1] 轉換至 target[0..j-1] 的最小編輯距離。

遞推關係

初始化：d[i][0] = i（刪除所有字元），d[0][j] = j（插入所有字元）
狀態轉移：d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+cost)
其中 cost = 0 若字元相同，否則 1

完整 Java 實作

public class Levenshtein {
    /**
     * 計算兩字串的編輯距離
     */
    private int compare(String str, String target) {
        int n = str.length();
        int m = target.length();
        if (n == 0) return m;
        if (m == 0) return n;

        int[][] d = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) d[i][0] = i;
        for (int j = 0; j <= m; j++) d[0][j] = j;

        for (int i = 1; i <= n; i++) {
            char ch1 = str.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                char ch2 = target.charAt(j - 1);
                int cost = (ch1 == ch2) ? 0 : 1;
                d[i][j] = Math.min(Math.min(d[i-1][j] + 1, d[i][j-1] + 1), d[i-1][j-1] + cost);
            }
        }
        return d[n][m];
    }

    /**
     * 取得相似度比率 (0.0 ~ 1.0)，1.0 代表完全相同
     */
    public float getSimilarityRatio(String str, String target) {
        int distance = compare(str, target);
        int maxLen = Math.max(str.length(), target.length());
        return maxLen == 0 ? 1.0f : 1 - (float) distance / maxLen;
    }

    public static void main(String[] args) {
        Levenshtein lt = new Levenshtein();
        System.out.println("similarityRatio(ab, ac) = " + lt.getSimilarityRatio("ab", "ac")); // 0.5
        System.out.println("similarityRatio(hello, hallo) = " + lt.getSimilarityRatio("hello", "hallo")); // 0.8
    }
}