Goでプログラミングの基礎を学ぶシリーズ
スクールでは教えてくれないプログラミングの基礎、データ構造とアルゴリズムをGoで学んでいくシリーズです。
そのデータ構造がどのようなものであるかは、理解を助けてくれるサイトを紹介しつつ、簡単な説明に留めさせていただきます。(ご自身でも調べてみてください！)
筆者自身、Exerciseに取り組みながら理解を深めていったので、コードの解説を中心に記事を書いていきたいと思います。
| タイトル | |
|---|---|
| #0 | はじめに (環境構築と勉強方法) |
| #1 | Pointer, Array, String (ポインタと配列と文字列と) |
| #2 | File operations (ファイル操作) |
| #3 | Linked List (連結リスト) |
| #4 | Stack & Queue (スタックとキュー) |
| #5 | Search algorithms (探索アルゴリズム) |
| #6 | Tree (木構造) |
| #7 | Sorting algorithms (ソートアルゴリズム) |
| #8 | String pattern matching algorithms (文字列探索アルゴリズム) ☜ here |
最終回となる今回は**#8 String pattern matching algorithms (文字列探索アルゴリズム)**です。
String pattern matching とは
文字列探索とは、ある文字列の中から、別のある文字列を探索することであり、さまざまなアルゴリズムがあります。
ここでは中でも代表的な文字列探索のアルゴリズムの Go での実装例をみていきます。
Naive algorithm (ナイーブ法)
ナイーブ法は、Brute Force algorithm (力まかせ探索) とも呼ばれます。
文字列( text )と探索文字列( pattern )を先頭から1文字ずつ探索し、不一致があった場合は探索文字列を1文字だけずらして、再度探索文字列の先頭から1文字ずつ探索していくアルゴリズムです。
文字列の長さを n, 探索文字列の長さを m としたときの時間計算量は $O(mn)$ ですが、これは文字列および探索文字列のなかで、同じ文字が何度も続く場合の計算量になりますので、実質はほぼ $O(n)$ となるようです。
func NaiveSearch(txt, pat string) {
if len(txt) <= len(pat) {
fmt.Println("text is shorter than pattern!")
}
patLastIndex := len(pat) - 1 // pattern の最後の index
var idx []int // pattern と一致した text 部分の先頭の index を格納する slice
for i := 0; i < len(txt)-patLastIndex; i++ {
for j := 0; j < len(pat); j++ {
if txt[i+j] != pat[j] {
break // 文字が一致しないとき、 i を一つ進める
}
if j == patLastIndex { // pattern がすべて一致したとき
idx = append(idx, i)
}
}
}
if len(idx) != 0 {
fmt.Printf("match index: %v\n", idx)
} else {
fmt.Println("no matching index!")
}
}
func main() {
NaiveSearch("xyzzxzyxyxyyzxzyyxyxyyz", "xyxyy")
}
☟ 出力結果
match index: [7 17]
Knuth-Morris-Pratt algorithm (KMP法)
KMP法 (クヌース・モリス・プラット法)は、探索文字列の先頭から探索していくのは ナイーブ法 と同様ですが、余計な探索を避けるための工夫がなされています。
文字列の長さを n, 探索文字列の長さを m としたときの時間計算量は $O(n)$ となりますが、実装は少々複雑になります。
詳細は以下サイトをご参考ください。
func KMPSearch(txt, pat string) {
if len(txt) < len(pat) {
fmt.Println("text is shorter than pattern!")
}
// スライドする文字数を決める ずらし表 を作成(pattern に対して pattern 自身を比較する)
table := make([]int, len(pat))
table[0] = 0
for i, j := 1, 0; i < len(pat); { // j は pattern 自身の比較で直前までに一致していた文字数
if pat[i] == pat[j] { // 一致している場合
j++
table[i] = j
i++
} else { // 一致しない場合
if j != 0 {
j = table[j-1]
} else {
table[i] = 0
i++
}
}
}
fmt.Printf("table: %v\n", table)
var idx []int // pattern と一致した text 部分の先頭の index を格納する slice
for i, j := 0, 0; i < len(txt); {
if txt[i] == pat[j] { // 文字が一致している場合
j++
i++
if j == len(pat) { // pattern がすべて一致したとき
idx = append(idx, i-j)
j = table[j-1]
}
} else { // 文字が一致しない場合
if j != 0 {
j = table[j-1]
} else {
i++
}
}
}
if len(idx) != 0 {
fmt.Printf("match index: %v\n", idx)
} else {
fmt.Println("no matching index!")
}
}
func main() {
KMPSearch("xyzzxzyxyxyyzxzyyxyxyyz", "xyxyy")
}
☟ 出力結果
table: [0 0 1 2 0]
match index: [7 17]
Boyer-Moore algorithm (BM法)
BM法 (ボイヤー・ムーア法)は、ナイーブ法やKMP法と異なり、探索文字列の後方から探索していくアルゴリズムです。
KMP法 と同様に、余計な探索を避けるために工夫されています。
文字列の長さを n, 探索文字列の長さを m としたときの時間計算量は、最良の場合で $O(n/m)$, 最悪の場合で $O(mn)$ となります。
しかし、 ナイーブ法 と同様に、最悪の場合というのは、これは文字列および探索文字列のなかで、同じ文字が何度も続く場合になりますので、実用する上では、ナイーブ法, KMP法 よりも高速なアルゴリズムのようです。
詳細は以下サイトをご参考ください。
func BMSearch(txt, pat string) {
if len(txt) < len(pat) {
fmt.Println("text is shorter than pattern!")
}
patLastIndex := len(pat) - 1 // pattern の最後の index
// スライドする文字数を決める ずらし表 を作成
table := make(map[byte]int)
for i, j := patLastIndex, 0; i >= 0; i, j = i-1, j+1 { // j は pattern の末尾からの文字数
if _, ok := table[pat[i]]; !ok { // pattern に含まれる文字でまだ table に存在しない場合
table[pat[i]] = j
}
}
fmt.Printf("table: %v\n", table)
for key, value := range table {
fmt.Printf("key: %s value: %v\n", string(key), value)
}
var idx []int // pattern と一致した text 部分の先頭の index を格納する slice
for i := patLastIndex; i < len(txt); {
// pattern の後方から探索を行う
for j := 0; j < len(pat); j++ { // j は pattern の末尾からの文字数
// 文字が一致している場合
if txt[i-j] == pat[patLastIndex-j] {
if j == patLastIndex { // pattern がすべて一致したとき
idx = append(idx, i-j)
} else {
continue
}
}
// 文字が一致しない場合 または pattern がすべて一致した場合、比較位置をずらす
slide, ok := table[txt[i-j]] // スライドする文字数を table から取得
if !ok { // 比較している text の文字が pattern の中にない場合
slide = len(pat)
}
// スライドする文字数を求める
if slide-j > 0 {
i += slide - j
} else { // 現在の位置より前にスライドしてしまう場合
i++ // 1 だけスライドする
}
break // j++ しても文字が一致することはないので break
}
}
if len(idx) != 0 {
fmt.Printf("match index: %v\n", idx)
} else {
fmt.Println("no matching index!")
}
}
func main() {
BMSearch("xyzzxzyxyxyyzxzyyxyxyyz", "xyxyy")
}
☟ 出力結果
table: map[120:2 121:0]
key: y value: 0
key: x value: 2
match index: [7 17]
おわりに
Exerciseの解答例はあくまで例なので、もっといい書き方あるよ！という方、ぜひコメントをお寄せください！
説明についても、筆者自身が初心者であるため、ご指摘や補足は大歓迎でございます。
株式会社Link Sportsでは、あらゆるスポーツを楽しむ人たちに送る、チームマネジメントアプリを開発しています。
未経験でも経験豊富なエンジニアの方でも、スポーツ好きなら活躍できる環境があります！
絶賛エンジニア募集中です！
Wantedly ▶︎ https://www.wantedly.com/projects/324177
Green ▶︎ https://www.green-japan.com/job/82003
データ構造とアルゴリズムを Go での実装例とともに学習してきましたが、いかがでしたか？
プログラミングスクールでは、全体像を掴むためにフレームワークを用いて簡単なアプリを作ったりすることと思いますが、いざ就職してみると、思うようにコードが書けない！なんてことになりませんでしたか？
筆者自身は、データ構造とアルゴリズムを学習してからのほうが、格段にコードが書きやすくなりました。
このシリーズがプログラミング初心者の方の助けになれば幸いです。