基本情報技術者 2015年 秋期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問1～3に答えよ。
〔プログラムの説明〕
関数BMMatchは、Boyer-Moore-Horspool法（以下、BM法という）を用いて、文字列検索を行うプログラムである。BM法は、検索文字列の末尾の文字から先頭に向かって、検索対象の文字列（以下、対象文字列）と1文字ずつ順に比較していくことで照合を行う。比較した文字が一致せず、照合が失敗した際には、検索文字列中の文字の情報を利用して、次に照合を開始する対象文字列の位置を決定する。このようにして明らかに不一致となる照合を省き、高速に検索できる特徴がある。
(1) 対象文字列をText[]、検索文字列をPat[]とする。ここで、配列の添字は1から始まり、文字列Text[]のi番目の文字はText[i]と表記される。Pat[]についても同様にi番目の文字はPat[i]と表記される。また、対象文字列と検索文字列は、英大文字から構成される。
例えば、対象文字列Text[]が“ACBBMACABABC”、検索文字列Pat[]が“ACAB”の場合の例を図1に示す。
(2) 関数BMMatchでは、照合が失敗すると、次に照合を開始する位置まで検索文字列を移動するが、その移動量を格納した要素数26の配列Skip[]をあらかじめ作成しておく。Skip[1]に文字“A”に対応する移動量を、Skip[2]に文字“B”に対応する移動量を格納する。このように、Skip[1]～Skip[26]に文字“A”～“Z”に対応する移動量を格納する。ここで、検索文字列の長さをPatLenとすると、移動量は次のようになる。
① 検索文字列の末尾の文字Pat[PatLen]にだけ現れる文字と、検索文字列に現れない文字に対応する移動量は、PatLenである。
② 検索文字列のPat[1]からPat[PatLen − 1]に現れる文字に対応する移動量は、その文字が、検索文字列の末尾から何文字目に現れるかを数えた文字数から1を引いた値とする。ただし、複数回現れる場合は、最も末尾に近い文字に対応する移動量とする。
(3) 図1で示したPat[]の例の場合、次の①〜④に示すように、Skip[]は図2のとおりになる。
① 文字“A”は検索文字列の末尾から2文字目(Pat[3])と4文字目(Pat[1])に現れるので、末尾に近いPat[3]に対応する移動量の1 (=2−1)となる。
② 文字“B”は検索文字列の末尾の文字にだけ現れるので、移動量はPatLen (=4)となる。
③ 文字“C”は検索文字列の末尾から3文字目(Pat[2])に現れるので、移動量は2 (=3−1)となる。
④ “A”、“B”及び“C”以外の文字については検索文字列に現れないので、移動量はPatLen (=4)となる。
(4) 図1の例で照合する場合の手順は、次の①～⑨となり、その流れを図3に示す。
この例では、PatLen=4なので、検索文字列の末尾の文字はPat[4]である。
① Text[4]とPat[4]を比較する。Text[4]とPat[4]は同じ文字“B”である。
② Text[3]とPat[3]を比較する。Text[3]の“B”とPat[3]の“A”は異なる文字である。
③ ①で検索文字列の末尾の文字Pat[4]と比較したText[4]を基準に、Text[4]の文字“B”に対応する移動量であるSkip[2]の値4だけPat[]を右側に移動し、Text[8]とPat[4]の比較に移る。
④ Text[8]とPat[4]を比較する。Text[8]の“A”とPat[4]の“B”は異なる文字である。
⑤ ④で検索文字列の末尾の文字Pat[4]と比較したText[8]を基準に、Text[8]の文字“A”に対応する移動量であるSkip[1]の値1だけPat[]を右側に移動し、Text[9]とPat[4]の比較に移る。
⑥ Text[9]とPat[4]を比較する。Text[9]とPat[4]は同じ文字“B”である。
⑦ Text[8]とPat[3]を比較する。Text[8]とPat[3]は同じ文字“A”である。
⑧ Text[7]とPat[2]を比較する。Text[7]とPat[2]は同じ文字“C”である。
⑨ Text[6]とPat[1]を比較する。Text[6]とPat[1]は同じ文字“A”である。
⑥～⑨の比較で、対象文字列Text[]の連続した一部分が検索文字列Pat[]に完全に一致したので、検索は終了する。
〔関数BMMatchの引数と返却値〕
関数BMMatchの引数と返却値の仕様は、次のとおりである。
関数BMMatchでは、次の関数Indexを使用する。
〔関数Indexの仕様〕
引数にアルファベット順でn番目の英大文字を与えると、整数n(1 ≦ n ≦ 26)を返却値とする。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
a, bに関する解答群
ア：0
イ：1
ウ：I − PatLen
エ：PatLen
オ：PatLen − 1
カ：PatLen − I
模範解答
a：エ、b：カ
解説
解答の導き方
この設問では、Skip[]の初期値を決めるaと、検索文字列の各文字に対応する移動量を設定するbを求めます。
まず、プログラムの最初のループでは、Iを1から26まで動かして、Skip[I]に同じ値を入れます。Skip[1]～Skip[26]は英大文字“A”～“Z”に対応するので、すべての文字の初期値を設定している処理です。
問題文には、検索文字列に現れない文字や、末尾にだけ現れる文字の移動量はPatLenとあります。初期値をPatLenにしておけば、個別に移動量を設定しない文字にも、この値を使えます。したがって、aにはPatLenが入り、解答群ではエです。
次に、2番目のループでは、Pat[1]からPat[PatLen − 1]までを調べます。検索文字列の末尾Pat[PatLen]は調べません。各文字について、検索文字列の末尾からの距離を計算し、そこから1を引いた値をSkip[]に設定します。
Pat[I]は、末尾から数えると文字目にあります。ここから1を引くため、設定する移動量はです。よって、bにはPatLen − Iが入り、解答群ではカです。
同じ文字がPat[]の途中に複数回現れる場合も、この式で正しく処理できます。ループはIを小さい方から大きい方へ進めるため、同じ文字への設定は、末尾に近い位置ほど後に行われます。最後に残る値は、その文字が末尾以外で最も末尾に近く現れる位置に対応する値です。
例えば、Pat[]が“ACAB”でPatLenが4の場合、Pat[1]の“A”には、Pat[2]の“C”には、Pat[3]の“A”にはを設定します。“A”は2回設定されますが、後から設定される1が残ります。一方、“B”はPat[4]にしか現れないので、最初に設定されたPatLenの4のままです。
誤りやすいポイント
- bをとしてしまう誤りです。これは文字が末尾から何文字目かを数えた値です。問題文では、そこから1を引くため、になります。
- 初期値を0や1にしてしまう誤りです。検索文字列にない文字などの移動量はPatLenなので、まずSkip[]全体をPatLenで初期化します。
- 同じ文字が複数回現れるとき、最初に設定した値が使われると思い込む誤りです。ループは左から右へ進むため、後から設定される末尾に近い位置の値が残ります。
- IとIndex(Pat[I])を混同する誤りです。IはPat[]の位置を表し、Index(Pat[I])は文字に対応するSkip[]の添字を求めます。
FAQ
Q: なぜPat[PatLen]は2番目のループで調べないのですか？
A: Skip[]をPatLenで初期化しているためです。末尾にだけ現れる文字は、その初期値のままになります。末尾より前にも現れる文字は、2番目のループで移動量が設定されます。
A: Skip[]をPatLenで初期化しているためです。末尾にだけ現れる文字は、その初期値のままになります。末尾より前にも現れる文字は、2番目のループで移動量が設定されます。
Q: 同じ文字に何度も値を設定してよいのですか？
A: はい。ループがIの小さい順に進むため、最後の設定がその文字の最も末尾に近い出現位置に対応します。これは問題文にある「最も末尾に近い文字」による移動量と一致します。
A: はい。ループがIの小さい順に進むため、最後の設定がその文字の最も末尾に近い出現位置に対応します。これは問題文にある「最も末尾に近い文字」による移動量と一致します。
Q: Indexは何をする関数ですか？
A: 英大文字を、Skip[]の添字である1～26の整数に変換します。例えば“A”なら1、“B”なら2です。
A: 英大文字を、Skip[]の添字である1～26の整数に変換します。例えば“A”なら1、“B”なら2です。
関連キーワード: Boyer-Moore-Horspool法、文字列検索、配列、添字、パターン照合
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
図4のように、Text[]に“ABCXBBACABACADEC”、TextLenに16、Pat[]に“ABAC”、PatLenに4を格納し、BMMatch(Text[], TextLen, Pat[], PatLen)を呼び出した。プログラムが終了するまでにαはc回実行され、βはd回実行される。またこの場合、関数BMMatchの返却値はeである。
c〜eに関する解答群
ア：3
イ：4
ウ：5
エ：6
オ：7
カ：8
キ：9
ク：10
ケ：11
コ：12
模範解答
c：ア、d：オ、e：キ
解説
解答の導き方
まず、Skip[]の値を作ります。Skip[]は最初、検索文字列の長さであるで埋められます。続いて、Pat[1]からPat[PatLen − 1]までの文字について、移動量を設定します。
検索文字列は「ABAC」です。Pat[I]の位置から末尾までの文字数からを引くと、移動量はになります。
Aは2回設定されますが、最後に設定されるPat[3]に対応した移動量が残ります。そのため、Skip[A]はです。Bはです。Cは検索文字列の末尾にしか現れないので、初期値ののままです。Xも検索文字列に現れないため、のままです。
次に、検索文字列を対象文字列に重ねる位置ごとに、プログラムの動きを追います。PLastは、検索文字列を重ねたときの右端の位置です。αの「PText ← PLast」は、この位置ごとに実行されます。
1回目は、Text[4]とPat[4]が一致しません。照合した対象文字列の右端はText[4]のXなので、Xに対応する移動量だけ右にずらします。次のPLastはです。
2回目は、右端のText[8]とPat[4]が一致します。その後、右から順にText[7]とPat[3]、Text[6]とPat[2]も一致します。しかし、Text[5]とPat[1]は一致しません。この位置では、文字が一致するたびにβの条件「PPat = 1」が確認されるため、βは回実行されます。右端のText[8]はCで、Skip[C]はです。したがって次のPLastはです。
3回目は、Text[12]とPat[4]から比較を始めます。右から順に4文字すべてが一致します。βは一致した文字ごとに確認されるので、この位置では回実行されます。最後の比較ではPTextが、PPatがとなり、βの条件が真になります。そのため、関数はPTextであるを返します。
以上から、αは照合を始めた位置ごとに1回実行され、全部で回です。βは一致した文字ごとに実行され、回です。検索文字列が見つかった位置はです。
誤りやすいポイント
-
αの回数を比較した文字数と混同すること
αは、照合を始めるたびに実行されます。1回目、2回目、3回目の照合開始時に実行されるため、比較した文字の合計数ではありません。 -
不一致でもβが実行されると考えること
βの条件を確認するのは、Text[PText]とPat[PPat]が一致した後です。不一致になった比較では、βは実行されません。 -
PatLenから末尾までの距離をそのまま移動量にすること
移動量は「末尾から何文字目か」からを引いた値です。そのため、Pat[3]のAの移動量はではなくです。 -
返却値を検索文字列の右端の位置と考えること
完全一致が分かったとき、PTextは検索文字列の先頭文字に対応する位置です。この問題ではを返します。
FAQ
Q: なぜ検索文字列の末尾から比較するのですか？
A: 末尾側で不一致になったとき、照合した対象文字列の文字に応じて、検索文字列を何文字ずらせるか判断できるからです。明らかに一致しない位置での比較を減らせます。
A: 末尾側で不一致になったとき、照合した対象文字列の文字に応じて、検索文字列を何文字ずらせるか判断できるからです。明らかに一致しない位置での比較を減らせます。
Q: 2回目の照合で、Cに対応する移動量がなのはなぜですか？
A: Cは検索文字列の末尾であるPat[4]にしか現れません。Pat[1]からPat[PatLen − 1]には現れないため、初期値のPatLenであるがそのまま使われます。
A: Cは検索文字列の末尾であるPat[4]にしか現れません。Pat[1]からPat[PatLen − 1]には現れないため、初期値のPatLenであるがそのまま使われます。
Q: なぜ一致したときにPTextを返すのですか？
A: 照合は検索文字列の末尾から始まり、一致するたびにPTextを1ずつ減らします。最後にPat[1]と一致した時点でのPTextが、検索文字列の先頭が見つかった位置です。
A: 照合は検索文字列の末尾から始まり、一致するたびにPTextを1ずつ減らします。最後にPat[1]と一致した時点でのPTextが、検索文字列の先頭が見つかった位置です。
関連キーワード: Boyer-Moore-Horspool法、文字列検索、照合、スキップテーブル、配列
設問3：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。ここで、プログラム中のaとbには正しい答えが入っているものとする。
関数BMMatch中のγの処理を
I: PatLen − 1, I ≧ 1, −1
に変更した場合、関数BMMatchはf。
fに関する解答群
ア：対象文字列中に、検索文字列が含まれていないのに、1以上の値を返す場合がある
イ：対象文字列中に、検索文字列が含まれているのに、−1を返す場合がある
ウ：正しい値を返す
模範解答
f：イ
解説
解答の導き方
この設問は、Skip[]を作るループγの向きを逆にしたとき、検索結果にどのような影響が出るかを考えます。
Skip[]は、照合に失敗したときに検索文字列を何文字ずらすかを記録した表です。Boyer-Moore-Horspool法では、検索文字列の末尾から比べ、不一致なら対象文字列の文字に対応する移動量だけ検索文字列をずらします。
まず、検索文字列Pat[]を「ABAC」とした場合を考えます。PatLenは4です。プログラムでは、Skip[]の各要素を最初にPatLen、つまり4に設定します。その後、γの処理でPat[1]からPat[PatLen − 1]までを調べます。
移動量は、Pat[I]の文字について、PatLen − Iです。γを問題文のとおり逆向きにすると、次の順でSkip[]が更新されます。
AはPat[3]とPat[1]にあります。逆向きに処理すると、先にPat[3]に対応する移動量1が設定されますが、後からPat[1]に対応する3で上書きされます。その結果、Aの移動量は3になります。
しかし、正しい移動量は1です。検索文字列の末尾に近いPat[3]のAを使う必要があるためです。元のようにIを1から増やす順で処理すれば、Pat[1]に対応する3を設定した後、Pat[3]に対応する1で上書きされます。
この移動量の誤りによって、検索文字列が対象文字列に含まれているのに、見つけられない場合があります。例として、Text[]を「AABAC」、Pat[]を「ABAC」とします。
最初の照合では、Pat[]の末尾はText[4]に合います。ところが、Text[4]のAとPat[4]のCが一致しません。このとき、逆向きの処理で作られたSkip[]ではAの移動量が3なので、検索文字列を3文字ずらします。次の照合位置はTextLenを超えてしまい、プログラムは検索文字列が見つからなかったとして −1を返します。
実際には、Text[2]からText[5]までの「ABAC」がPat[]と一致しています。正しいAの移動量1なら、次の照合位置に進んでこの一致を見つけられます。つまり、移動量を大きくしすぎると、一致する位置を飛び越えてしまうことがあります。
一方、プログラムが1以上の値を返すのは、検索文字列の各文字がすべて一致したときです。移動量が誤っていても、一致していない文字列を一致したと誤判定することはありません。したがって、起こり得るのは「含まれているのに −1を返す」場合です。
誤りやすいポイント
- ループを逆向きにしても、同じ文字の移動量は変わらないと思い込まないようにします。同じ文字がPat[]内に複数あると、Skip[]への上書き順が変わります。
- 移動量を大きくすれば検索が速くなる、とだけ考えないようにします。大きくずらしすぎると、一致する位置を飛び越すことがあります。
- 返却値が1以上になる条件は、検索文字列の文字がすべて一致することです。移動量の誤りによる問題は、主に一致位置を見落とすことです。
FAQ
Q: Pat[]内で同じ文字が1回しか現れない場合も、逆向きにすると移動量が変わりますか？
A: その文字については、上書きが起きないため変わりません。問題になるのは、同じ文字が複数回現れる場合です。
A: その文字については、上書きが起きないため変わりません。問題になるのは、同じ文字が複数回現れる場合です。
Q: なぜ末尾に近い文字の位置を使うのですか？
A: 末尾に近い同じ文字があるのに、それを考慮せず大きくずらすと、その文字に続く一致の可能性を飛び越してしまうからです。
A: 末尾に近い同じ文字があるのに、それを考慮せず大きくずらすと、その文字に続く一致の可能性を飛び越してしまうからです。
Q: 移動量が誤っていると、検索文字列が含まれていないのに見つかったと返すこともありますか？
A: ありません。見つかったと返す前に、検索文字列の文字がすべて一致していることを確認するためです。
A: ありません。見つかったと返す前に、検索文字列の文字がすべて一致していることを確認するためです。
関連キーワード: Boyer-Moore-Horspool法、文字列検索、照合、シフト量
