Levenshtein Distance（編輯距離）算法與使用場景

• 2020 年 3 月 9 日
• 筆記

前提

已經很久沒深入研究過算法相關的東西，畢竟日常少用，就算死記硬背也是沒有實施場景導致容易淡忘。最近在做一個脫敏數據和明文數據匹配的需求的時候，用到了一個算法叫Levenshtein Distance Algorithm，本文對此算法原理做簡單的分析，並且用此算法解決幾個常見的場景。

什麼是Levenshtein Distance

Levenshtein Distance，一般稱為編輯距離（Edit Distance，Levenshtein Distance只是編輯距離的其中一種）或者萊文斯坦距離，算法概念是俄羅斯科學家弗拉基米爾·萊文斯坦（Levenshtein · Vladimir I）在1965年提出。此算法的概念很簡單：Levenshtein Distance指兩個字串之間，由一個轉換成另一個所需的最少編輯操作次數，允許的編輯操作包括：

• 將其中一個字符替換成另一個字符（Substitutions）。
• 插入一個字符（Insertions）。
• 刪除一個字符（Deletions）。

下文開始簡稱Levenshtein Distance為LD

Levenshtein Distance公式定義

這個數學公式最終得出的數值就是LD的值。舉個例子：

將kitten這個單詞轉成sitting的LD值為3：

1. kitten → sitten （k→s）
2. sitten → sittin （e→i）
3. sittin → sitting （insert a ‘g’）

Levenshtein Distance動態規劃方法

可以使用動態規劃的方法去測量LD的值，步驟大致如下：

• 初始化一個LD矩陣(M,N)，M和N分別是兩個輸入字符串的長度。
• 矩陣可以從左上角到右下角進行填充，每個水平或垂直跳轉分別對應於一個插入或一個刪除。
• 通過定義每個操作的成本為1，如果兩個字符串不匹配，則對角跳轉的代價為1，否則為0，簡單來說就是：
  • 如果[i][j]位置的兩個字符串相等，則從[i][j]位置左加1，上加1，左上加0，然後從這三個數中取出最小的值填充到[i][j]。
  • 如果[i][j]位置的兩個字符串不相等，則從[i][j]位置左、左上、上三個位置的值中取最小值，這個最小值加1（或者說這三個值都加1然後取最小值），然後填充到[i][j]。
• 按照上面規則LD矩陣(M,N)填充完畢後，最終矩陣右下角的數字就是兩個字符串的LD值。

這裡不打算證明上面動態規劃的結論（也就是默認這個動態規劃的結果是正確的），直接舉兩個例子說明這個問題：

• 例子一（兩個等長字符串）：son和sun。
• 例子二（兩個非等長字符串）：doge和dog。

例子一：

初始化LD矩陣(3,3)：

計算[0][0]的位置的值，因為's' = 's'，所以[0][0]的值 = min(1+1, 1+1, 0+0) = 0。

按照這個規則計算其他位置的值，填充完畢後的LD矩陣`如下：

那麼son和sun的LD值為1。

例子二：

初始化LD矩陣(4,3)：

接着填充矩陣：

那麼doge和dog的LD值為1。

Levenshtein Distance算法實現

依據前面提到的動態規劃方法，可以相對簡單地實現LD的算法，這裡選用Java語言進行實現：

public enum LevenshteinDistance {        // 單例      X;        /**       * 計算Levenshtein Distance       */      public int ld(String source, String target) {          Optional.ofNullable(source).orElseThrow(() -> new IllegalArgumentException("source"));          Optional.ofNullable(target).orElseThrow(() -> new IllegalArgumentException("target"));          int sl = source.length();          int tl = target.length();          // 定義矩陣,行列都要加1          int[][] matrix = new int[sl + 1][tl + 1];          // 首行首列賦值          for (int k = 0; k <= sl; k++) {              matrix[k][0] = k;          }          for (int k = 0; k <= tl; k++) {              matrix[0][k] = k;          }          // 定義臨時的編輯消耗          int cost;          for (int i = 1; i <= sl; i++) {              for (int j = 1; j <= tl; j++) {                  if (source.charAt(i - 1) == target.charAt(j - 1)) {                      cost = 0;                  } else {                      cost = 1;                  }                  matrix[i][j] = min(                          // 左上                          matrix[i - 1][j - 1] + cost,                          // 右上                          matrix[i][j - 1] + 1,                          // 左邊                          matrix[i - 1][j] + 1                  );              }          }          return matrix[sl][tl];      }        private int min(int x, int y, int z) {          return Math.min(x, Math.min(y, z));      }        /**       * 計算匹配度match rate       */      public BigDecimal mr(String source, String target) {          int ld = ld(source, target);          // 1 - ld / max(len1,len2)          return BigDecimal.ONE.subtract(BigDecimal.valueOf(ld)                  .divide(BigDecimal.valueOf(Math.max(source.length(), target.length())), 2, BigDecimal.ROUND_HALF_UP));      }  }

算法的複雜度為O(N * M)，其中N和M分別是兩個輸入字符串的長度。這裡的算法實現完全參照前面的動態規劃方法推論過程，實際上不一定需要定義二維數組（矩陣），使用兩個一維的數組即可，可以參看一下java-string-similarity中Levenshtein算法的實現。以前面的例子運行一下：

public static void main(String[] args) throws Exception {      String s = "doge";      String t = "dog";      System.out.println("Levenshtein Distance:" +LevenshteinDistance.X.ld(s, t));      System.out.println("Match Rate:" +LevenshteinDistance.X.mr(s, t));  }  // 輸出  Levenshtein Distance:1  Match Rate:0.75

Levenshtein Distance算法一些使用場景

LD算法主要的應用場景有：

• DNA分析。
• 拼寫檢查。
• 語音識別。
• 抄襲偵測。
• 等等……

其實主要就是"字符串"匹配場景，這裡基於實際遇到的場景舉例。

脫敏數據和明文數據匹配

最近有場景做脫敏數據和明文數據匹配，有時候第三方導出的文件是脫敏文件，格式如下：

己方有明文數據如下：

要把兩份數據進行匹配，得出上面兩條數據對應的是同一個人的數據，原理就是：當且僅當兩條數據中手機號的LD值為4，身份證的LD值為8，姓名的LD值為1，則兩條數據完全匹配。

使用前面寫過的算法：

public static void main(String[] args) throws Exception {      String sourceName = "張*狗";      String sourcePhone = "123****8910";      String sourceIdentityNo = "123456****8765****";      String targetName = "張大狗";      String targetPhone = "12345678910";      String targetIdentityNo = "123456789987654321";      boolean match = LevenshteinDistance.X.ld(sourceName, targetName) == 1 &&              LevenshteinDistance.X.ld(sourcePhone, targetPhone) == 4 &&              LevenshteinDistance.X.ld(sourceIdentityNo, targetIdentityNo) == 8;      System.out.println("是否匹配:" + match);      targetName = "張大doge";      match = LevenshteinDistance.X.ld(sourceName, targetName) == 1 &&              LevenshteinDistance.X.ld(sourcePhone, targetPhone) == 4 &&              LevenshteinDistance.X.ld(sourceIdentityNo, targetIdentityNo) == 8;      System.out.println("是否匹配:" + match);  }  // 輸出結果  是否匹配:true  是否匹配:false

拼寫檢查

這個場景看起來比較貼近生活，也就是詞典應用的拼寫提示，例如輸入了throwab，就能提示出throwable，筆者認為一個簡單實現就是遍歷t開頭的單詞庫，尋找匹配度比較高（LD值比較小）的單詞進行提示（實際上為了滿足效率有可能並不是這樣實現的）。舉個例子：

public static void main(String[] args) throws Exception {      String target = "throwab";      // 模擬一個單詞庫      List<String> words = Lists.newArrayList();      words.add("throwable");      words.add("their");      words.add("the");      Map<String, BigDecimal> result = Maps.newHashMap();      words.forEach(x -> result.put(x, LevenshteinDistance.X.mr(x, target)));      System.out.println("輸入值為:" + target);      result.forEach((k, v) -> System.out.println(String.format("候選值:%s,匹配度:%s", k, v)));  }  // 輸出結果  輸入值為:throwab  候選值:the,匹配度:0.29  候選值:throwable,匹配度:0.78  候選值:their,匹配度:0.29

這樣子就可以基於輸入的throwab選取匹配度最高的throwable。

抄襲偵測

抄襲偵測的本質也是字符串的匹配，可以簡單認為匹配度高於某一個閾值就是屬於抄襲。例如《我是一隻小小鳥》裏面的一句歌詞是：

我是一隻小小小小鳥，想要飛呀飛卻飛也飛不高

假設筆者創作了一句歌詞：

我是一條小小小小狗，想要睡呀睡卻睡也睡不夠

我們可以嘗試找出兩句詞的匹配度：

System.out.println(LevenshteinDistance.X.mr("我是一隻小小小小鳥，想要飛呀飛卻飛也飛不高", "我是一條小小小小狗，想要睡呀睡卻睡也睡不夠"));  // 輸出如下  0.67

可以認為筆者創作的歌詞是完全抄襲的。當然，對於大文本的抄襲偵測（如論文查重等等）需要考慮執行效率的問題，解決的思路應該是類似的，但是需要考慮如何分詞、大小寫等等各種的問題。

小結

本文僅僅對Levenshtein Distance做了一點皮毛上的分析並且列舉了一些簡單的場景，其實此算法在日常生活中是十分常見的，筆者猜測詞典應用的單詞拼寫檢查、論文查重（抄襲判別）都可能和此算法相關。算法雖然學習曲線比較陡峭，但是它確實是一把解決問題的利刃。

參考資料：

• 維基百科 – Levenshtein distance
• java-string-similarity
• The Levenshtein Algorithm