アルゴリズムとデータ構造 第9回演習解答

第9回演習解答(1/5) [問] 次の１３１文字のテキストストリング(英語の部分。数字は位置を示す。）からパターン``retiring''が最初に現れる位置を求めたいとする。素朴なアルゴリズム、 Knuth-Morris-Pratt法とBoyer-Moore法ではそれぞれ何回文字比較を行うことになるか？ (1)素朴なアルゴリズム 01234567890123456789012345678901234567890123456789012345678901234567890 Fans crowded in front of Futagoyama stable, Monday morning, waiting for * * * * 123456789012345678901234567890123456789012345678901234567890 the word they expected yet dreaded-Takanohana was retiring. * ** ******** 122文字目から一致する。先頭からの122文字にパターンの先頭を位置づけた場合、 何文字目(先頭は0文字目)で失敗するか調べると 1文字目　5回 2文字目　1回 0文字目　122－6=116回 したがって、 比較回数は 　　　　　116×1　+　5×2　+　1×3　+　8　=　137 (回) である。

第9回演習解答(2/5) (2)Knuth-Morris-Pratt法 失敗関数f: パターンのi文字目(i≧1, 先頭は0文字目）で失敗した場合、次はパターン 　　　　　　　のf(i)文字目から照合を続ければ漏れなく照合できるような関数 ...ra... ...ra... ...retire... ...retire... retiring retiring retiring retiring i=1 i=0 i=5 i=1 ...rea... ...rea... ...retirir... ...retirir... retiring retiring retiring retiring i=2 i=0 i=6 i=0 ...retu... ...retu... ...retirink... ...retirink... retiring retiring retiring retiring i=3 i=0 i=7 i=0 ...retic.. ...retic... retiring retiring i 1 2 3 4 5 6 7 f i=4 i=0 0文字目、1文字目の失敗は素朴なアルゴリズムと同じ動きとなる。2文字目以降の失敗 はちょうど２文字目で失敗する場合が１度だけ（100文字目からの“rea”)あり、この場合は 0文字目で失敗する場合をスキップできるので、１回比較が減る。よって比較回数は136回。

第9回演習解答(3/5) Boyer-Moore法 関数d: テキストtのj文字目で失敗した場合、次はテキストのj+d(t[j])文字目、 パターンの最後の文字から照合を続ければ漏れなく照合できるような関数 j 文字g j j+0 j+5 文字t ...gg... ...gg... ...tiring... ...tiring... retiring retiring retiring retiring j j+1 j j+6 文字n 文字e ...ng... ...ng... ...etiring... ...etiring... retiring retiring retiring retiring j j+2 文字i j 文字a j+8 ...ing... ...ing... retiring retiring ...atiringng... ...atiringng retiring retiring j j+3 文字r ...ring... ...ring... retiring retiring 文字 r e t i n g その他 d 3 6 5 2 1 8

第9回演習解答(4/5) ..angr.. ...angrabcdefg... ...rg... ...rg... retiring 関数dd: テキスト文字列のj文字目、パターン文字列のi文字目で失敗した場合 テキスト文字列の j+dd(i)文字目、パターン文字列の最後の文字から照合を続ければ漏れなく照合できるような関数 j j+10 j j+1 ..angr.. ...angrabcdefg... ...rg... ...rg... retiring retiring retiring retiring i=5 j i=7 j+9 i 1 2 3 4 5 6 7 dd 15 14 13 12 11 10 9 ...rgr.. ...rgrabcdefg... retiring retiring i=6

第9回演習解答(4/5) 文字 r e t i n g その他 d 3 6 5 2 1 8 i 1 2 3 4 5 6 7 dd 15 14 関数d: テキストtのj文字目で失敗した場合、次はテキストのj+d(t[j])文字目、 パターンの最後の文字から照合を続ければ漏れなく照合できるような関数 文字 r e t i n g その他 d 3 6 5 2 1 8 関数dd: テキスト文字列のj文字目、パターン文字列のi文字目で失敗した場合 テキスト文字列の j+dd(i)文字目、パターン文字列の最後の文字から照合を続ければ漏れなく照合できるような関数 i 1 2 3 4 5 6 7 dd 15 14 13 12 11 10 9 01234567890123456789012345678901234567890123456789012345678901234567890 Fans crowded in front of Futagoyama stable, Monday morning, waiting for d 8 8 8 8 8 8 2 * 1* dd 1 1 1 1 1 1 1 * 1* d 1** 5** dd b** b** 123456789012345678901234567890123456789012345678901234567890 the word they expected yet dreaded-Takanohana was retiring. d 6 8 8 6 8 8 8 3 * dd 1 1 1 1 1 1 1 1 * d ******* dd ******* 11のつもり 比較回数は ３２回