使用Go語言計算字符串編輯距離的代碼實現(xiàn)
更新時間：2025年07月29日 08:30:26 作者：程序員愛釣魚
在自然語言處理、拼寫糾錯、模糊搜索等場景中,我們經常需要衡量兩個字符串之間的相似度,編輯距離（Edit Distance） 就是一個經典的衡量方式,它描述了將一個字符串轉換為另一個字符串所需的最少操作次數(shù),本文給大家介紹了如何使用Go語言計算字符串編輯距離
一、問題定義：什么是編輯距離？
編輯距離，也稱為 Levenshtein Distance，指的是將字符串 A 轉換成字符串 B 所需的最少操作次數(shù)。操作允許：
- • 插入一個字符（Insert）
- • 刪除一個字符（Delete）
- • 替換一個字符（Replace）
示例：
A?=?"kitten" B?=?"sitting" 編輯距離?=?3 解釋： kitten?→?sitten（k?→?s）?→?sittin（e?→?i）→?sitting（插入?g）
二、應用場景
編輯距離廣泛應用于：
- • 搜索引擎模糊匹配（例如：“gooogle” 應該匹配 “google”）
- • 拼寫檢查和自動糾正
- • 語音識別、OCR糾錯
- • DNA序列比對
三、解決思路：動態(tài)規(guī)劃（DP）
1. 狀態(tài)定義
設 dp[i][j] 表示將字符串 A 的前 i 個字符轉換成字符串 B 的前 j 個字符所需的最小操作數(shù)。
2. 狀態(tài)轉移方程
我們可以從三個方向轉移過來：
- 插入：
dp[i][j-1] + 1（B 多了個字符） - 刪除：
dp[i-1][j] + 1（A 多了個字符） - 替換或匹配：
dp[i-1][j-1] + cost - 如果
A[i-1] == B[j-1]，cost = 0 - 否則
cost = 1
- 如果
最終狀態(tài)轉移為：
dp[i][j]?=?min( ????dp[i-1][j]?+?1,??????????//?刪除 ????dp[i][j-1]?+?1,??????????//?插入 ????dp[i-1][j-1]?+?cost??????//?替換/匹配 )
3. 初始化
dp[0][j] = j：將空串變成 B 前 j 個字符需要插入 j 次；dp[i][0] = i：將 A 前 i 個字符變成空串需要刪除 i 次。
四、Go語言實現(xiàn)
動態(tài)規(guī)劃二維實現(xiàn)：
package?main
import?(
????"fmt"
????"math"
)
func?MinDistance(a,?b?string)?int?{
????m,?n?:=?len(a),?len(b)
????dp?:=?make([][]int,?m+1)
????//?初始化二維數(shù)組
????for?i?:=?range?dp?{
????????dp[i]?=?make([]int,?n+1)
????}
????//?初始化第一列和第一行
????for?i?:=?0;?i?<=?m;?i++?{
????????dp[i][0]?=?i
????}
????for?j?:=?0;?j?<=?n;?j++?{
????????dp[0][j]?=?j
????}
????//?狀態(tài)轉移
????for?i?:=?1;?i?<=?m;?i++?{
????????for?j?:=?1;?j?<=?n;?j++?{
????????????cost?:=?0
????????????if?a[i-1]?!=?b[j-1]?{
????????????????cost?=?1
????????????}
????????????dp[i][j]?=?min(
????????????????dp[i-1][j]+1,???//?刪除
????????????????dp[i][j-1]+1,???//?插入
????????????????dp[i-1][j-1]+cost,?//?替換/匹配
????????????)
????????}
????}
????return?dp[m][n]
}
func?min(a,?b,?c?int)?int?{
????return?int(math.Min(float64(a),?math.Min(float64(b),?float64(c))))
}
func?main()?{
????a?:=?"kitten"
????b?:=?"sitting"
????fmt.Printf("編輯距離?between?'%s'?and?'%s'?is:?%d\n",?a,?b,?MinDistance(a,?b))
}
五、運行示例
輸入： a?=?"kitten" b?=?"sitting" 輸出： 編輯距離?between?'kitten'?and?'sitting'?is:?3
六、時間與空間復雜度分析
- 時間復雜度：O(m * n)
因為我們遍歷了大小為 m x n 的二維數(shù)組； - 空間復雜度：O(m * n)
用于存儲狀態(tài)的二維數(shù)組。
七、空間優(yōu)化版本（滾動數(shù)組）
可以優(yōu)化為一維數(shù)組來降低空間：
func?MinDistanceOptimized(a,?b?string)?int?{
????m,?n?:=?len(a),?len(b)
????prev?:=?make([]int,?n+1)
????curr?:=?make([]int,?n+1)
????//?初始化第一行
????for?j?:=?0;?j?<=?n;?j++?{
????????prev[j]?=?j
????}
????for?i?:=?1;?i?<=?m;?i++?{
????????curr[0]?=?i
????????for?j?:=?1;?j?<=?n;?j++?{
????????????cost?:=?0
????????????if?a[i-1]?!=?b[j-1]?{
????????????????cost?=?1
????????????}
????????????curr[j]?=?min(
????????????????curr[j-1]+1,??????//?插入
????????????????prev[j]+1,????????//?刪除
????????????????prev[j-1]+cost,???//?替換
????????????)
????????}
????????prev,?curr?=?curr,?prev
????}
????return?prev[n]
}
八、拓展：支持更多操作的變種編輯距離
- Damerau-Levenshtein 距離：除了插入、刪除、替換，還支持交換相鄰字符；
- 帶權重的編輯距離：不同操作賦予不同代價；
- 相似度計算：將編輯距離轉為百分比相似度，比如：
similarity?:=?1?-?float64(distance)?/?float64(max(len(a),?len(b)))
九、實戰(zhàn)應用場景舉例
| 場景 | 作用描述 |
|---|---|
| 搜索引擎 | 用戶輸入有誤時自動推薦相似關鍵詞 |
| 拼寫檢查 | IDE、文本編輯器糾正英文單詞 |
| 語音/圖像識別后處理 | 自動修正識別錯誤的單詞序列 |
| 文件比對工具 | 如 Git diff、文本比較器 |
| 生物信息學 | DNA/RNA 序列比對、蛋白質比對 |
十、總結
| 點位 | 內容 |
|---|---|
| 算法思想 | 動態(tài)規(guī)劃 |
| 實現(xiàn)結構 | dp[i][j] 表示 A 的前 i 個字符轉換為 B 的前 j 個字符的最小編輯距離 |
| 時間復雜度 | O(m * n) |
| 空間優(yōu)化 | 支持優(yōu)化為滾動數(shù)組，空間降為 O(n) |
| 實戰(zhàn)價值 | 應用場景極廣，從 NLP 到搜索再到生物信息學 |
以上就是使用Go語言計算字符串編輯距離的代碼實現(xiàn)的詳細內容，更多關于Go計算字符串編輯距離的資料請關注腳本之家其它相關文章！
相關文章
本文主要介紹了Golang的鎖機制與使用技巧小結，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-06-06
這篇文章主要介紹了GO語言基本類型,較為詳細的分析了整形、浮點型、字符串、指針等類型的具體用法,是深入學習GO語言所必須掌握的重要基礎,需要的朋友可以參考下2014-12-12
golang高并發(fā)限流操作 ping / telnet
這篇文章主要介紹了golang高并發(fā)限流操作 ping / telnet，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
本文詳細講解了Golang中Interface接口的三個特性，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
本文主要介紹了Go語言JSON文件的讀寫操作，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-04-04
這篇文章主要為大家介紹了一文初探?Goroutine?與?channel基本用法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-02-02
傳統(tǒng)的并發(fā)編程模型是基于線程和共享內存的同步訪問控制的，共享數(shù)據(jù)受鎖的保護，使用線程安全的數(shù)據(jù)結構會使得這更加容易。本文將詳細介紹Golang并發(fā)編程中的Channel，,需要的朋友可以參考下2023-05-05
在?Go?語言中,并發(fā)是最重要的特性之一,sync?是?Go?標準庫中用于?并發(fā)控制與同步?的核心工具,下面小編就和大家詳細介紹一下它的具體使用吧2026-03-03
歸并排序采用的也是分治的策略，把原本的問題先分解成一些小問題進行求解，再把這些小問題各自的答案修整到一起得到原本問題的答案，從而達到分而治之的目的，對Go歸并排序算法相關知識感興趣的朋友一起看看吧2022-04-04
這篇文章主要介紹了一文讀懂go中semaphore(信號量)源碼的相關知識，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-04-04