Go 字符串匹配及 Rabin-Karp 算法回顧

About Author

• CuiShuang

• 嗶哩嗶哩 Go 服務端開發

• 個人博客 https://dashen.tech

• 個人郵箱 i@dashen.tech

• GitHub：https://github.com/cuishuang

簡介

字符串匹配是一項基礎且重要的算法，是計算機科學中最古老、研究最廣泛的問題之一。在生物信息學、信息檢索、拼寫檢查、語言翻譯、數據壓縮、網絡入侵檢測等方面有廣泛使用。

字符串匹配就是在一個大的字符串 T 中搜索某個字符串 P 所出現的位置（首次匹配到的位置，或全部位置）。其中，T 一般被稱爲文本串，P 稱爲模式串。

你可能聽過著名的 KMP 算法（考研 / 面試常客），BM 算法（Boyer-Moore）和 Horspool 算法（Python 的字符串匹配採用了這兩種算法）。

幾乎所有語言都內置字符串匹配功能，但不同語言對其實現有所差異。在 Go 語言中，根據文本串 T 和模式串 P 的長度，有不同的處理策略（其中最重要的是 Rabin-Karp 算法）。各種處理策略是何？Rabin-Karp 算法又是用什麼思路來降低算法時間複雜度的呢？深入源碼，一探究竟。

函數只有簽名，沒有函數體一般有兩種情況：

• 如 time.Sleep(d Duration)，其方法體在 src/time/sleep.go，其實現在 src/runtime/time.go

通過 go:linkname 指令告訴編譯器，爲當前源文件中的私有函數或者變量在編譯時鏈接到指定的方法或變量。（該指令破壞了類型系統和包的模塊化, 因此在使用時必須導入 unsafe 包）

• 另一種則是函數簽名使用 Go ，然後通過該包中的彙編文件來實現它，這兩種都廣泛存在於 Go 源碼中。

對於第二種方式，彙編文件 .s 與 .go 在一個文件夾下即可，文件名稱不需要一定相同.(方法名需相同) 使用 go build 即可構建出來。

Rabin-Karp 算法

Michael Rabin

1976 年圖靈獎得主

貢獻領域：非確定性自動機，拉賓 - 卡普算法

中文一般譯作 “邁克爾 · 拉賓”，1931 年出生於德國佈雷斯勞（二戰後成爲波蘭弗羅茨瓦夫)。以色列計算機科學家，猶太人。

1956 年，獲普林斯頓大學博士學位。

1959 年，拉賓和達納 · 斯科特共同發表了 “有限自動機與其判定性問題”（Finite Automata and Their Decision Problems）的論文，提出非確定自動機的觀點。他們也因此獲得了 1976 年的圖靈獎，並做 “計算機複雜性”（Complexity of Computations）的演講。

1969 年，證明 N successors 的二階邏輯是可判定的，證明的關鍵部分暗示了奇偶遊戲的確定性。

1975 年，發明米勒 - 拉賓檢驗。這是一個相當快速的隨機化算法（有較小的可能性錯誤），用於判斷一個大數是否是素數。快速素數檢驗是目前大部分公鑰密碼體系的關鍵。

1979 年，發明第一個非對稱密碼系統——拉賓密碼系統，它的安全性被證明和整數因式分解的複雜度相同。

1981 年，提出不經意傳輸技術。

1987 年，和理查德 · 卡普提出了著名的字符串搜索算法——拉賓 - 卡普算法。

Richard Karp

1985 年圖靈獎得主

貢獻領域：算法理論 (尤其是 NP - 完全性理論)，拉賓 - 卡普算法

中文一般譯作” 理查德 · 卡普”，1935 年出生于波士頓。

1955 年先獲得哈佛大學文學學士學位, 第二年又獲得理科碩士學位。之後進入哈佛大學的計算機實驗室攻讀博士，畢業後進入 IBM。

主要研究領域：路徑問題、揹包問題、覆蓋問題、匹配問題、分區問題、調度問題，並取得了許多成果。

在解決 “旅行推銷商” 問題時，提出“分支限界法”，是一種構造性的探索法，可在整個允許的解空間中進行最優搜索。（該方法的要點是：對解集合反覆進行分支，每次分支時，都對所得的子集計算最優解的界。如果對某個子集求得的界不優於已知的允許解，則拋棄此子集不再進行分支；否則繼續分支以探索更好的解，直到所得到的子集僅含有一個解爲止）

儘可能多的利用上一次的結果

擴展爲英文字符串

ASCII：英語字符與二進制位之間的關係 （其他語言？？）

Unicode：將世界上所有的符號都納入其中， 每個符號都對應一個獨一無二的編碼，最多可以容納 1114112 個字符，現在用了 14 萬個 （有個問題是浪費空間。。）

UTF-8：使用最廣的一種 Unicode 的實現方式 （最大特點是變長的編碼方式。Plan 9 的遺產之一）

其他資料

• Rabin-Karp 算法（字符串快速查找）[4]

• Rabin–Karp on coursera[5]

• 9.2 Rabin-Karp String Matching Algorithm[6]

• Go 夜讀第 5 期 strings 包源碼閱讀 [7]

鏈接地址

[1]

力扣 28. 實現 strStr() : https://leetcode-cn.com/problems/implement-strstr/

[2]

力扣 187. 重複的 DNA 序列: https://leetcode-cn.com/problems/repeated-dna-sequences/

[3]

力扣 686. 重複疊加字符串匹配: https://leetcode-cn.com/problems/repeated-string-match/

[4]

Rabin-Karp 算法（字符串快速查找）: https://www.cnblogs.com/golove/p/3234673.html

[5]

Rabin–Karp on coursera: https://www.coursera.org/lecture/algorithms-part2/rabin-karp-3KiqT

[6]

9.2 Rabin-Karp String Matching Algorithm: https://youtu.be/qQ8vS2btsxI

[7]

Go 夜讀第 5 期 strings 包源碼閱讀: https://talkgo.org/t/topic/24

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/PV_QJzTjZYdMVOJmUckCMQ