アルゴリズムとデータ構造

(1)

アルゴリズムとデータ構造

第4週文字列照合（KMP法、BM法）

2014年10月16日金岡晃

(2)

授業計画

第1週 (9/25)

データ構造とアルゴリズムの基礎

第2週 (10/2)

アルゴリズムの効率、線型構造、

スタックと待ち行列第3週

(10/9)

＜演習＞アルゴリズムの効率、

線型構造、スタックと待ち行列第4週

(10/16)

文字列照合（KMP法、BM法）

＋＜演習＞

第5週 (10/23)

休講第6週

(10/30)

木の構造、木の走査、二分木、

決定木 第7週

(11/13)

＜演習＞木の構造、木の走査、

二分木、決定木 第8週中間試験

第9週 (11/27)

休講第10週

(12/4)

グラフ構造と最短路問題＋

＜演習＞

第11週 (12/11)

データ整列：ヒープソート法、クイックソート法

第12週 (12/18)

＜演習＞データ整列：ヒープソート法、クイックソート法

第13週 (1/8)

データ探索：ハッシュ法、

木構造探索法第14週

(1/15)

＜演習＞データ探索：ハッシュ法、木構造探索法

1/21-2/6 期末試験

(3)

第 1 回課題の解説

2014/10/16 アルゴリズムとデータ構造

2

(4)

演習（その１）

平方数を判定する平方数を判定する

※平方数：ある整数の2乗で表される整数（例：1, 4, 9, 16, 25)

目的：入力された値が平方数であるか否かを判定する入力：自然数 𝑛

出力： 0 （平方数でない）または 1（平方数である）

手法A

1,2, … , 𝑛 を順に2乗し、𝑛と等しいか確認する。確認する数：最大𝑛回

制約：利用できる算術演算は加算（＋）、減算（－）、積（×）のみ

演習：手法Aよりも高速（確認する数が少ない）アルゴリズムを考え、実装して

(5)

演習（その 1 ）：回答例

4

for文の終了条件を変更 for文の終了条件を変更

＜省略＞

int flag = 0;

for(int i=0;i<n;i++){

if(i*i == n) flag = 1;

}

return flag;

＜省略＞

手法Aの実装例手法Aの実装例

int flag = 0;

for(int i=0;i*i<n;i++){

if(i*i == n) flag = 1;

}

return flag;

発見したらfor文のループを外れる発見したらfor文のループを外れる

int flag = 0;

for(int i=0;i<n;i++){

if(i*i == n){

flag = 1;

break;

} }

return flag;

(6)

演習（その 2 ）

積木の塔を解く積木の塔を解く

演習：積木の塔を解くアルゴリズムを考え、実装してみよう

入力：初期状態。（T,T,T,A）のようなベクトル。

※ベクトルの入力方法は任意

出力：目的の状態（B,C,D,T）に至るまでの状態と動作（moveとremove）

の内容の列挙

注：現段階では実現は難しいかもしれないので、

できなかった場合は、どういう考えでやろうとして（アルゴリズムのイメージ）、どう失敗したかを示せるように

注：現段階では実現は難しいかもしれないので、

できなかった場合は、どういう考えでやろうとして（アルゴリズムのイメージ）、どう失敗したかを示せるように

(7)

回答事例：プログラムが作れなかったケース

6

良いパターン良いパターン

「わかりませんでした」

「難しくて完成できませんでした」

「書けませんでした」

悪いパターン悪いパターン

「机の上にあるものから順に数字をつけて積み上げたいと思ったが、途中で混乱した。特に**を**することができなかった。」

「ベクトルのプログラム上での表現方法でつまづき、できなかった」

再帰を使わないプログラムの例を

http://www.klab.is.sci.toho-u.ac.jp/classes/

の授業ページに載せました

(8)

演習（その 3 ）

• 計算量が 𝑂 𝑛 、 𝑂 𝑛

²

の例をそれぞれ 1 つずつ考え、実装してみる

– 例：「九九の表を作る」

–

「＊＊という状況で＊＊＊という問題を解く」というまず状況設定と解かれるべき問題をプログラムのソースコードにコメント文として書くこと

–

同じく、コメント文に問題の解き方を書き、それがなぜそのオーダになるかを示すこと

計算量を考える計算量を考える

この例をそのまま使うのはやめてください

(9)

演習（その 3 ）：回答例

8

𝑂 𝑛 𝑂 𝑛

𝑂 𝑛² 𝑂 𝑛²

・1～nまでの和の計算（for文と+=で実現）

・

・1～nまでの和の計算（for文と+=で実現）

・n×n行列の表示（2次元配列とfor文で実現）

厳密には違う例厳密には違う例

・サイコロ2つの出た目の積の表

→ サイコロは6面で固定とも取れるので

「n面体の各面に1から順に数値を振ったサイコロ」とすると完璧

(10)

演習（その 3 ）：回答例

オーダーの理解を誤っている例オーダーの理解を

誤っている例・公差数列の一般項を求める 𝐴_𝑛 = 𝐴₀ + 𝑛 − 1 × 𝑑

・𝑛を入力することで求まる関数なので𝑂 𝑛 という理解

𝑂 𝑛 は、計算の「量」が 𝑛に比例することを示すものであり、

計算の「値」が𝑛に比例することを示すものではない

一般項は𝑛を用いて求められる

一般項を求める計算は固定回（1回）の作業

このケースは𝑂 1

(11)

【復習】第 3 週

スタックと待ち行列

アルゴリズムとデータ構造

10 2014/10/16 アルゴリズムとデータ構造

(12)

スタック

スタック（Stack）

レコードの追加・削除ともに線形リストの先頭においてのみ行われる

追加をプッシュ（push）、削除をポップ（pop）と呼ぶ LIFO（Last-In First-Out）とも呼ばれる

例例

• 机の上に積んだ本

• スーパーやコンビニエンスストアの籠

(13)

レコードの追加は線型リストの末尾のみ、削除は先頭においてのみ行われる

キュー（待ち行列）

12

キュー（Queue) キュー（Queue)

追加をEnqueue、削除をDequeueと呼ぶ FIFO（First-In First-Out）とも呼ばれる

例例

• 有名店の行列

• コンビニエンスストアの飲料売り場

(14)

順配置表現

a[1]

a[n]

先頭の位置 t

a[1]

a[n]

末尾の位置 r 先頭の位置の1つ前 f スタック（Stack）

スタック（Stack）キュー（Queue)キュー（Queue)

(15)

再帰的手続きの例：ハノイの塔

14

ハノイの塔ハノイの塔

19世紀にEdouard Lucasにより発明されたゲーム。

・3本のピンがある

・穴の開いた大きさの異なる円盤が複数枚ある

・最初は左端のピンに小さいものが上になるように積み重ねられている

・すべての円盤を他のピンに移す

・ただし、1度の1枚の円盤しか動かせない

・小さな円盤の上に大きな円盤を載せることはできない

例例

円盤が3枚のときの初期状態

(16)

ハノイの塔：枚数 𝑛 枚のとき

操作に名称を付ける操作に名称を付ける

𝐻𝑎𝑛𝑜𝑖 𝑛, 𝑖, 𝑗 ： 𝑛枚の円盤をピン𝑖からピン𝑗に移す 𝑖, 𝑗 = 1,2,3 𝑖 ≠ 𝑗

1枚の時 𝐻𝑎𝑛𝑜𝑖 1, 𝑖, 𝑗 ∶ 𝑚𝑜𝑣𝑒(𝑖, 𝑗) 2枚の時

𝐻𝑎𝑛𝑜𝑖 2, 𝑖, 𝑗 ∶ 𝑚𝑜𝑣𝑒 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒 𝑖, 𝑗 , 𝑚𝑜𝑣𝑒(𝑘, 𝑗) 𝑘 = 6 − 𝑖 − 𝑗

𝑛枚の時

𝐻𝑎𝑛𝑜𝑖 𝑛, 𝑖, 𝑗 ∶ 𝐻𝑎𝑛𝑜𝑖 𝑛 − 1, 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒 𝑖, 𝑗 , 𝐻𝑎𝑛𝑜𝑖(𝑛 − 1, 𝑘, 𝑗) 𝑘 = 6 − 𝑖 − 𝑗

再帰的手続き

(17)

ハノイの塔： 𝑛 = 3 のときの操作分解

16

𝑘 = 6 − 𝑖 − 𝑗

𝐻𝑎𝑛𝑜𝑖 3, 𝑖, 𝑗 ∶ 𝐻𝑎𝑛𝑜𝑖 2, 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒 𝑖, 𝑗 , 𝐻𝑎𝑛𝑜𝑖(2, 𝑘, 𝑗)

𝐻𝑎𝑛𝑜𝑖 2, 𝑖, 𝑘 ∶ 𝐻𝑎𝑛𝑜𝑖 1, 𝑖, 𝑗 , 𝑚𝑜𝑣𝑒 𝑖, 𝑘 , 𝐻𝑎𝑛𝑜𝑖 1, 𝑗, 𝑘 𝐻𝑎𝑛𝑜𝑖 1, 𝑖, 𝑗 ∶ 𝑚𝑜𝑣𝑒 𝑖, 𝑗

𝐻𝑎𝑛𝑜𝑖 1, 𝑗, 𝑘 ∶ 𝑚𝑜𝑣𝑒 𝑗, 𝑘

𝐻𝑎𝑛𝑜𝑖 2, 𝑖, 𝑘 ∶ 𝑚𝑜𝑣𝑒(𝑖, 𝑗), 𝑚𝑜𝑣𝑒 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒(𝑗, 𝑘)

𝐻𝑎𝑛𝑜𝑖 2, 𝑘, 𝑗 ∶ 𝐻𝑎𝑛𝑜𝑖 1, 𝑘, 𝑖 , 𝑚𝑜𝑣𝑒 𝑘, 𝑗 , 𝐻𝑎𝑛𝑜𝑖 1, 𝑖, 𝑗 𝐻𝑎𝑛𝑜𝑖 1, 𝑘, 𝑖 ∶ 𝑚𝑜𝑣𝑒 𝑘, 𝑖

𝐻𝑎𝑛𝑜𝑖 1, 𝑖, 𝑗 ∶ 𝑚𝑜𝑣𝑒 𝑖, 𝑗

𝐻𝑎𝑛𝑜𝑖 2, 𝑘, 𝑗 ∶ 𝑚𝑜𝑣𝑒(𝑘, 𝑖), 𝑚𝑜𝑣𝑒 𝑘, 𝑗 , 𝑚𝑜𝑣𝑒(𝑖, 𝑗) 𝐻𝑎𝑛𝑜𝑖 3, 𝑖, 𝑗 ∶ 𝑚𝑜𝑣𝑒 𝑖, 𝑗 , 𝑚𝑜𝑣𝑒 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒 𝑗, 𝑘 , 𝑚𝑜𝑣𝑒 𝑖, 𝑗 ,

𝑚𝑜𝑣𝑒(𝑘, 𝑖), 𝑚𝑜𝑣𝑒 𝑘, 𝑗 , 𝑚𝑜𝑣𝑒(𝑖, 𝑗)

(18)

再帰的手続きの例：フィボナッチ数列

フィボナッチ数列フィボナッチ数列

Leonard Fibonacciにちなんで名づけられた数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

・次の数は、最後の数とその前の数を足した数になる 𝑓 0 = 1, 𝑓 1 = 1

𝑓 𝑖 = 𝑓 𝑖 − 1 + 𝑓(𝑖 − 2) 再帰的手続き

(19)

フィボナッチ数列： 𝑖 = 4 のとき

18

𝑓 4 = 𝑓 3 + 𝑓(2)

= 𝑓 2 + 𝑓(1) + 𝑓(2)

= 𝑓(1 + 𝑓 0 ) + 𝑓(1) + 𝑓 1 + 𝑓 0

= 1 + 1 + 1 + 1 + 1

= 2 + 1 + 1 + 1

= 3 + 2

= 5

(20)

演習（その 4 ）

ハノイの塔を解くハノイの塔を解く

演習：ハノイの塔を解くプログラムを実装してみよう

入力：積木の数, 最初のピンの位置（1, 2, 3のいずれか）, 最後のピンの位置（1, 2, 3のいずれか）

出力：目的の状態に至るまでの状態と動作（move）の内容の列挙

締切は本日16:10 締切は本日16:10

(21)

演習（その 5 ）

20

フィボナッチ数列フィボナッチ数列

演習：フィボナッチ数列を表示するプログラムを実装してみよう

入力：数列の長さ

出力：数列の長さまでのフィボナッチ数列の表示

締切は本日16:10 締切は本日16:10

(22)

第 4 週

文字列照合（ KMP 法）

アルゴリズムとデータ構造

(23)

本日の到達目標と概要

•

到達目標

–

文字列照合の代表的なアルゴリズムを理解する

•

概要

–

単純照合法

– KMP

法

(24)

文字列照合問題

…… …… ……

1 s s+m-1 n

文字列 text

パターン pat ……

入力済みの文章（文字列、テキスト）から、変更したい単語（パターン）を探し出す処理

文字列照合（文字列パターンマッチング）

文字列中の各文字を text[1], text[2],…,text[n]

パターン中の各文字をpat[1], pat[2],…,pat[m]と表す

1 m

(25)

単純照合法

24

text pat

１．テキストの先頭にパターンの先頭を合わせる２．パターンの先頭から文字を比較していく

４．パターンの先頭から文字を比較していく

３．異なる文字が現れた場合、パターンを1文字文後ろへシフトする

計算の効率

計算の効率 𝑂(𝑚𝑛)

(26)

効率化に向けて：照合回数を減らす

A B B C × text

pat A B B C B 1回目の照合はここで照合失敗

A B B C B

単純照合法での2回目の照合はここで照合失敗

これまでに照合した内容などを踏まえて、

効率的にシフトできないか？

これまでに照合した内容などを踏まえて、

効率的にシフトできないか？

A B B C B 本質的にはここから次の照合が始まったほうが良い

(27)

KMP 法

26

Knuth-Morris-Pratt法（KMP法）

先頭から照合をしていく場合、照合失敗後のシフト量と照合開始位置をあらかじめパターンから計算をしておき、

照合を行っていく

アルゴリズムの流れ

パターンpat[1..n]より

シフト量と照合開始位置を決める量であるfail[1..n]を計算

failの計算

単純照合法と同様にパターンの先頭から照合していくが、シフト量と照合開始位置はfail[1..n]に従う

照合

注意

教科書P.83 のfail[i]の定義式は見ないこと。記載に矛盾があり混乱を招く。

(28)

パターンの先頭 i 文字を見てここが照合失敗した場合に

何文字シフトするべきかを数える

KMP 法： fail の導出と利用

failの導出（図解）

パターンを用いて、パターン同士の照合を行い、シフト量を求める

pat A B B C B

fail[1] A ^1文字

iからシフト量を引いた数がfail[i]

fail[1]=1-1=0

fail[2] A B 1文字 fail[2]=2-1=1 fail[3] A B B 2文字 fail[3]=3-2=1 fail[4] A B B C 3文字 fail[4]=4-3=1 fail[5] A B B C B 4文字 fail[5]=5-4=1

(29)

• i番目で照合が失敗した場合、i-fail[i]だけ右にシフト

• 照合はpat[fail[i]]から開始する

KMP 法： fail の導出と利用

28

failの導出

（アルゴリズム）failの導出

（アルゴリズム）

failの利用 failの利用

(30)

𝑂(𝑚)

KMP 法の計算量

failの導出 failの導出

failを利用した 𝑂(𝑛) 照合

failを利用した照合

𝑂(𝑚 + 𝑛) KMP法

KMP法

(31)

演習（その 6 ）

30

KMP法による文字列照合 KMP法による文字列照合

演習：KMP法によるfailの導出を行うプログラムを作成してみよう

入力：文字列

出力：文字列の長さに応じたfair

(32)

演習（その 6 ）：実行イメージ

> java KMPFail ABBCB fail: 0, 1, 1, 1, 1

(33)

本日の到達目標と概要

•

到達目標

–

文字列照合の代表的なアルゴリズムを理解する

•

概要

–

単純照合法

– KMP

法

(34)

締切と提出方法：演習その 6

• 締切

– 再来週（10月30日）の16:10まで

※次回のこの講義＋演習時間が終わるまで

• 提出方法

– 電子メール

• メールアドレス

– [email protected]

– メールのタイトルに「アルゴリズムとデータ構造第3回課題」と書いてください

– 作ったプログラムをメールに添付してください。

• 注意事項

– 必ず金岡から受領確認メールを返します。

• 必ず日本語で受領確認メールを返します

• 英語のメールはエラーメール（アドレスが間違っている）の可能性が高いです

– メールで提出がされていないものは未提出とみなします

アルゴリズムとデータ構造

アルゴリズムとデータ構造

授業計画

第 1 回課題の解説

演習（その１）

演習（その 1 ）：回答例

演習（その 2 ）

回答事例：プログラムが作れなかったケース

演習（その 3 ）

• 計算量が 𝑂 𝑛 、 𝑂 𝑛

の例をそれぞれ 1 つずつ考え、実装 してみる

– 例：「九九の表を作る」

「＊＊という状況で＊＊＊という問題を解く」というまず状況 設定と解かれるべき問題をプログラムのソースコードにコメン ト文として書くこと

同じく、コメント文に問題の解き方を書き、それがなぜその オーダになるかを示すこと

演習（その 3 ）：回答例

演習（その 3 ）：回答例

【復習】第 3 週

スタックと待ち行列

アルゴリズムとデータ構造

スタック

キュー（待ち行列）

順配置表現

再帰的手続きの例：ハノイの塔

ハノイの塔：枚数 𝑛 枚のとき

ハノイの塔： 𝑛 = 3 のときの操作分解

再帰的手続きの例：フィボナッチ数列

フィボナッチ数列： 𝑖 = 4 のとき

演習（その 4 ）

演習（その 5 ）

第 4 週

文字列照合（ KMP 法）

アルゴリズムとデータ構造

本日の到達目標と概要

到達目標

文字列照合の代表的なアルゴリズムを理解する

概要

単純照合法

法

文字列照合問題

単純照合法

効率化に向けて：照合回数を減らす

KMP 法

KMP 法： fail の導出と利用

KMP 法： fail の導出と利用

KMP 法の計算量

演習（その 6 ）

演習（その 6 ）：実行イメージ

本日の到達目標と概要

到達目標

文字列照合の代表的なアルゴリズムを理解する

概要

単純照合法

法

締切と提出方法：演習その 6

の例をそれぞれ 1 つずつ考え、実装してみる

「＊＊という状況で＊＊＊という問題を解く」というまず状況設定と解かれるべき問題をプログラムのソースコードにコメント文として書くこと

同じく、コメント文に問題の解き方を書き、それがなぜそのオーダになるかを示すこと