アルゴリズムとデータ構造
第5週 文字列照合（BM法）、木の構造
2013年10月24日 金岡 晃
授業計画
第1週 (9/26)
データ構造とアルゴリズムの基 礎
第2週 (10/3)
アルゴリズムの効率、線形構造 第3週
(10/10)
スタックと待ち行列 第4週
(10/17)
文字列照合（KMP法、BM法）
第5週 (10/24)
木構造、木の走査
→文字列照合（BM法）、木構 造
第6週 (10/31)
二分木、決定木 第7週
(11/14)
中間試験
第8週 (11/21)
休講 第9週
(11/28)
グラフ構造と最短路問題 第10週
(12/5)
解の探索：Aアルゴリズム 第11週
(12/12)
データ整列：ヒープソート 法
第12週 (12/19)
データ整列：クイックソー ト法
第13週 (1/9)
データ探索：ハッシュ法 第14週
(1/16)
データ探索：木構造探索法 1/22-2/8 期末試験
【復習】第 4 週
文字列照合（ KMP 法）
アルゴリズムとデータ構造
文字列照合問題
…… …… ……
1 s s+m-1 n
文字列 text
パターン pat ……
入力済みの文章（文字列、テキスト）から、変更した い単語（パターン）を探し出す処理
文字列照合（文字列パターンマッチング）
文字列中の各文字を text[1], text[2],…,text[n]
パターン中の各文字をpat[1], pat[2],…,pat[m]と表す
1 m
単純照合法
text pat
１．テキストの先頭にパターンの先頭を合わせる ２．パターンの先頭から文字を比較していく
４．パターンの先頭から文字を比較していく
３．異なる文字が現れた場合、パターンを1文 字文後ろへシフトする
計算の効率
𝑂(𝑚𝑛)
KMP 法
Knuth-Morris-Pratt法（KMP法）
先頭から照合をしていく場合、照合失敗後のシフト量と 照合開始位置をあらかじめパターンから計算をしておき、
照合を行っていく
アルゴリズムの流れ
パターンpat[1..n]より
シフト量と照合開始位置を決める量 であるfail[1..n]を計算
failの計算
単純照合法と同様にパターンの先頭 から照合していくが、シフト量と照 合開始位置はfail[1..n]に従う
照合
注意
教科書P.83 のfail[i]の定 義式は見ないこと。記載 に矛盾があり混乱を招く。
パターンの先頭 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
• i番目で照合が失敗した場合、i-fail[i]だけ右にシフト
• 照合はpat[fail[i]]から開始する
KMP 法： fail の導出と利用
failの導出
（アルゴリズム）
failの利用
演習１： KMP 法における fail 導出
パターン “ACAABACABC”の場合の
failの導出を、図解とアルゴリズムを用いて示せ
第 5 週
文字列照合（ BM 法）、木の構造
アルゴリズムとデータ構造
本日の到達目標と概要
• 到達目標
– 文字列照合の代表的なアルゴリズムを理解する – データ構造で代表的な木構造の概要を理解する
• 概要
– 文字列照合アルゴリズム： BM 法 – 木の構造
– ポーランド記法（後置記法）
BM 法
Boyer-Moore法（BM法）
末尾から照合をしていく場合の照合失敗後のシフト量を
あらかじめパターンから計算をしておき、照合を行っていく
アルゴリズムの流れ
パターンpat[1..m]より シフト量を決める量 shift[1..m]を計算
shiftの計算
パターンの末尾から照合して いくが、照合失敗後のシフト 量はshift[1..m]とλ[1..Σ]に従う
照合
各文字がpat上で 最も右に現れる 位置λ[1..Σ]の計算
λの計算
BM 法： λ の導出
λの導出
（アルゴリズム）
Σはアルファベット全種類の集合
BM 法： shift の導出
shiftの導出（図解）
パターンを用いて、パターン同士の照合を 行い、シフト量を求める
pat B A B B A B
パターンの末尾 i 文字目を見て ここが照合失敗した場合に
何文字シフトするべきかを数える shift[6] 1文字 shift[6]=1
shift[5] 2文字 shift[5]=2 shift[4] 5文字 shift[4]=5 shift[3] 3文字 shift[3]=3 shift[2] 3文字 shift[2]=3 shift[1] 3文字 shift[1]=3
B A B B A B B A B B A B B A B B A B B A B B A B B A B B A B B A B B A B
BM 法： shift の導出
shiftの導出
（アルゴリズム）
BM 法： λ と shift の利用
アルゴリズムの流れ
パターンpat[1..m]より シフト量を決める量 shift[1..m]を計算
shiftの計算
パターンの末尾から照合していくが 照合失敗後のシフト量は
照合を失敗したテキスト場所kの文字text[k]
パターンの場所をiとした場合、
shift[i]と(i- λ[text[k]) の大きい方の分だけシフトする
照合
各文字がpat上で 最も右に現れる 位置λ[1..Σ]の計算
λの計算
演習 1 ： BM 法における λ と Shift 導出
パターン “BACBABA”の場合の λとshiftの導出を行え。
λはアルゴリズムを用い、
shiftは図解とアルゴリズムを用いて示せ
ただし、
アルファベットは A,B,Cの3文字とする
2 項演算子と、算術式の木構造
d=a*(b+c)
=
d *
a +
b c
z=y+1/(x-1)
=
z +
y /
1 -
x 1
2項演算子 2つの項を用いて演算を行う演算子
木構造
算術式の基本構造
演算子
第 1 被演算子 第 2 被演算子
中置記法と後置記法
• 中置記法
– 演算子が中央に置かれている
A+B
• 前置記法
– 演算子が前に置かれている
+AB
• 後置記法（ポーランド記法）
– 演算子が後ろに置かれている
AB+
人が通常使う記法
コンパイラが通常使う記法
後置記法の表記例
• 中置記法
A+B*C-D
• 後置記法
ABC*+D-
• 中置記法
E*F+G/H
• 後置記法
EF*GH/+
演習 2 ：木構造とポーランド記法
以下の中置記法で記述された算術式を、木構造と後 置記法（ポーランド記法）でそれぞれ示せ
