基本情報技術者 2019年 秋期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
〔プログラムの説明〕
関数BitapMatchは、Bitap法を使って文字列検索を行うプログラムである。
Bitap法は、検索対象の文字列（以下、対象文字列という）と検索文字列の照合に、個別の文字ごとに定義されるビット列を用いるという特徴をもつ。
なお、本問では、例えば2進数の16ビット論理型の定数0000000000010101は、上位の0を省略して“10101”Bと表記する。
(1) 関数BitapMatchは、対象文字列をText[]に、検索文字列をPat[]に格納して呼び出す。配列の要素番号は1から始まり、Text[]のi番目の文字はText[i]と表記する。Pat[]についても同様にi番目の文字はPat[i]と表記する。対象文字列と検索文字列は、英大文字で構成され、いずれも最長16文字とする。
対象文字列Text[]が“AACBBAACABABAB”、検索文字列Pat[]が“ACABAB”の場合の格納例を、図1に示す。
(2) 関数BitapMatchは、関数GenerateBitMaskを呼び出す。
関数GenerateBitMaskは、文字“A”〜“Z”の文字ごとに、検索文字列に応じたビット列（以下、ビットマスクという）を生成し、要素数26の16ビット論理型配列Mask[]に格納する。Mask[1]には文字“A”に対するビットマスクを、Mask[2]には文字“B”に対するビットマスクを格納する。このようにMask[1]～Mask[26]に文字“A”～“Z”に対応するビットマスクを格納する。
関数GenerateBitMaskは、Mask[]の全ての要素を“0”Bに初期化した後、1以上でPat[]の文字数以下の全てのiに対して、Pat[i]の文字に対応するMask[]の要素であるMask[Index(Pat[i])]に格納されている値の、下位から数えてi番目のビットの値を1にする。
関数Indexは、引数にアルファベット順でn番目の英大文字を設定して呼び出すと、整数n（1 ≦ n ≦ 26）を返す。
(3) 図1で示した、Pat[]が“ACABAB”の例の場合、関数GenerateBitMaskを実行すると、Mask[]は図2のとおりになる。
(4) 関数GenerateBitMaskの引数と返却値の仕様は、表1のとおりである。
設問1：
問題文を見る プログラムの説明及びプログラム1中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：0000000000000101
イ：0000000000101000
ウ：0001010000000000
エ：1010000000000000
bに関する解答群
ア：“0”B
イ：“1”B
ウ：“1”BをPatLenビットだけ論理左シフトした値
エ：“1”Bを(PatLen − 1)ビットだけ論理左シフトした値
オ：“1111111111111111”B
cに関する解答群
ア：“1”Bを(i − 1)ビットだけ論理左シフトした値
イ：“1”Bをiビットだけ論理左シフトした値
ウ：“1”Bを(PatLen − 1)ビットだけ論理左シフトした値
エ：“1”BをPatLenビットだけ論理左シフトした値
オ：“1”B
模範解答
a：イ、b：ア、c：ア
解説
解答の導き方
この問題では、検索文字列の各位置をビットで表し、同じ文字が現れる位置をまとめた「ビットマスク」を作ります。ビットは、2進数の各桁にある「0」または「1」です。
検索文字列は「ACABAB」です。各文字の位置と、その位置を表すビットは次のようになります。
問題文には、各文字について「下位から数えて番目のビットの値を1にする」とあります。下位から1番目のビットを立てるには、値「1」を左に動かす必要はありません。下位から2番目なら1ビット、3番目なら2ビット左へ動かします。したがって、位置のビットを立てる値は、「1」をビットだけ論理左シフトした値です。よって、cはアです。
次に、同じ文字が複数の位置にある場合、その位置をすべてビットマスクに残します。そのため、すでにある値と新しい位置のビットを「ビットごとの論理和」で組み合わせます。どちらか一方でもその桁が1なら、結果も1になります。
「A」は位置1、3、5にあるので、下位から1、3、5番目のビットを立てます。問題文の図2にある“A”のマスク「0000000000010101」とも一致します。
「B」は位置4、6にあります。位置4のビットは「0000000000001000」、位置6のビットは「0000000000100000」です。この2つを論理和で組み合わせると、「0000000000101000」になります。したがって、aはイです。
「C」は位置2にだけあります。位置2のビットは「0000000000000010」なので、図2に示された“C”のマスクとも一致します。
最後に、Mask[]の初期化を考えます。問題文には、Mask[]の全ての要素を「0」Bに初期化するとあります。ビットマスクを作る前は、どの位置もまだ該当しないため、全て0にします。したがって、bはアです。
誤りやすいポイント
- 位置に対応するビットを立てるとき、左シフトする回数を回と考えないようにします。下位から1番目のビットは、シフトしなくても値「1」で表せるため、シフト回数はです。
- ビットマスクは、同じ文字が最初に現れた位置だけを記録するものではありません。「A」のように複数回現れる文字は、その全ての位置を記録します。
- 初期化では、まだ文字の位置を追加していないため、全要素を「0」Bにします。「1」Bなどで初期化すると、関係のない位置まで1になってしまいます。
- ビット列を左から読んで位置を数えないようにします。この問題では、下位から数えたビットの位置と検索文字列の位置を対応させています。
FAQ
Q: なぜ同じ文字の位置を論理和でまとめるのですか？
A: その文字が検索文字列のどの位置にあるかを、1つのビットマスクで表すためです。論理和なら、すでに1になっている位置を保ったまま、新しい位置も1にできます。
A: その文字が検索文字列のどの位置にあるかを、1つのビットマスクで表すためです。論理和なら、すでに1になっている位置を保ったまま、新しい位置も1にできます。
Q: 左シフトすると、ビット列はどちらへ動きますか？
A: 数値を大きくする方向、つまり左へ動きます。値「1」を1ビット左へ動かすと、下位から2番目のビットが1になります。
A: 数値を大きくする方向、つまり左へ動きます。値「1」を1ビット左へ動かすと、下位から2番目のビットが1になります。
Q: 先頭の0は省略してもよいのですか？
A: 問題文では、上位の0を省略して表記できると説明しています。固定長の16ビットで表示するときは、上位の0も含めて表します。
A: 問題文では、上位の0を省略して表記できると説明しています。固定長の16ビットで表示するときは、上位の0も含めて表します。
関連キーワード: Bitap法、ビットマスク、ビットシフト、ビットごとの論理和、2進数
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
〔関数BitapMatchの説明〕
(1) Text[]とPat[]を受け取り、Text[]の要素番号の小さい方からPat[]と一致する文字列を検索し、見つかった場合は、一致した文字列の先頭の文字に対応するText[]の要素の要素番号を返し、見つからなかった場合は、−1を返す。
(2) 図1の例では、Text[7]～Text[12]の文字列がPat[]と一致するので、7を返す。
(3) 関数BitapMatchの引数と返却値の仕様は、表2のとおりである。
図1で示したとおりに、Text[]とPat[]に値を格納し、関数BitapMatchを実行した。プログラム2の行βを実行した直後の変数iと配列要素Mask[Index(Text[i])]と変数Statusの値の遷移は、表3のとおりである。
例えば、iが1のときに行βを実行した直後のStatusの値は“1”Bであることから、iが2のときに行αを実行した直後のStatusの値は、“1”Bを1ビットだけ論理左シフトした“10”Bと“1”Bとのビットごとの論理和を取った“11”Bとなる。次に、iが2のときに行βを実行した直後のStatusの値は、Mask[Index(Text[2])]の値が“10101”Bであることを考慮すると、dとなる。
同様に、iが8のときに行βを実行した直後のStatusの値が“10”Bであるということに留意すると、iが9のときに行αを実行した直後の行βで参照するMask[Index(Text[9])]の値はeであるので、行βを実行した直後のStatusの値はfとなる。
d〜fに関する解答群
ア：“0”B
イ：“1”B
ウ：“10”B
エ：“11”B
オ：“100”B
カ：“101”B
キ：“10101”B
模範解答
d：イ、e：キ、f：カ
解説
解答の導き方
この設問では、行βを実行した直後のStatusの値を求めます。文字ごとのビットマスクを確認してから、行α、行βの順に処理を追います。
1. 文字ごとのビットマスクを確認します
ビットマスクとは、検索文字列の中で特定の文字が現れる位置を、ビット列の1で表したものです。位置は右端から数えます。関数GenerateBitMaskの説明にも、「下位から数えてi番目のビット」の値を1にするとあります。
検索文字列「ACABAB」の文字と位置は、次のとおりです。
文字Aは位置1、3、5にあるので、Aのビットマスクは「10101」Bです。文字Cは位置2にあるので、Cのビットマスクは「10」Bです。
2. iが2のときの値を求めます
行αでは、Statusを1ビット左にシフトし、その結果と「1」Bとのビットごとの論理和を取ります。論理和では、どちらかの桁が1なら結果が1になります。
問題文によると、iが1のとき、行βの処理後のStatusは「1」Bです。これを基に、iが2の行αを計算します。
続く行βでは、Statusと、Text[2]の文字Aに対応するビットマスク「10101」Bとのビットごとの論理積を取ります。論理積では、両方の桁が1のときだけ結果が1になります。
「11」Bを「10101」Bと桁をそろえて考えると、「00011」Bです。「00011」Bと「10101」Bの論理積は「00001」Bとなるため、結果は「1」Bです。したがって、dに入るのは「1」Bです。
3. iが9のときの値を求めます
問題文では、iが8の行βの処理後のStatusは「10」Bです。また、図1ではText[9]がAなので、iが9の行βではAのビットマスク「10101」Bを使います。したがって、eは「10101」Bです。
まず、行αの処理をします。「10」Bを左に1ビットシフトすると「100」Bです。これと「1」Bとの論理和は「101」Bになります。
次に、行βで「101」Bと「10101」Bとの論理積を取ります。桁をそろえると「101」Bは「00101」Bです。「00101」Bと「10101」Bの論理積は「00101」Bなので、結果は「101」Bです。したがって、fに入るのは「101」Bです。
Statusは、対象文字列を左から調べながら、検索文字列の先頭から何文字分一致しているかをビットで表します。行αで新しい一致候補を加え、行βで現在の文字に合わない候補を取り除くため、文字列の一致を順に調べられます。
誤りやすいポイント
- ビットの位置は右端から数えます。文字Aが検索文字列の位置1、3、5にある場合、そのビットマスクは「10101」Bです。
- 行αでは、Statusを左にシフトした後、「1」Bとの論理和を取ります。シフトだけではありません。
- 行βの論理積では、Statusとビットマスクの桁をそろえて計算します。左側に省略された0を補うと、各桁を比べやすくなります。
- eに入るのは、iが9のときにText[9]の文字Aに対応するビットマスクです。Statusの値ではありません。
FAQ
Q: 「10」Bは10進数の10ですか？
A: いいえ。「B」は2進数を表します。「10」Bは2進数の「10」で、右端から2番目のビットが1です。
A: いいえ。「B」は2進数を表します。「10」Bは2進数の「10」で、右端から2番目のビットが1です。
Q: 行αで「1」Bとの論理和を取るのはなぜですか？
A: 対象文字列の現在の位置から、検索文字列との一致が始まる候補を加えるためです。
A: 対象文字列の現在の位置から、検索文字列との一致が始まる候補を加えるためです。
Q: 行βでビットごとの論理積を取るのはなぜですか？
A: 現在の文字に対応するビットマスクと共通するビットだけを残し、一致が続かない候補を取り除くためです。
A: 現在の文字に対応するビットマスクと共通するビットだけを残し、一致が続かない候補を取り除くためです。
関連キーワード: ビットマスク、ビットシフト、ビットごとの論理和、ビットごとの論理積、文字列検索
設問3：
問題文を見る 関数GenerateBitMaskの拡張に関する、次の記述中のに入れる正しい答えを、解答群の中から選べ。ここで、プログラム3中のbには、設問1のbの正しい答えが入っているものとする。
表4に示すような正規表現を検索文字列に指定できるように、関数GenerateBitMaskを拡張し、関数GenerateBitMaskRegexを作成した。
Pat[]に“AC[BA]A[ABC]A”を格納して、関数GenerateBitMaskRegexを呼び出した場合を考える。この場合、文字“A”に対応するビットマスクであるMask[1]はgとなり、関数GenerateBitMaskRegexの返却値はhとなる。また、Pat[]に格納する文字列中において[]を入れ子にすることはできないが、誤ってPat[]に“AC[B[AB]AC]A”を格納して関数GenerateBitMaskRegexを呼び出した場合、Mask[1]はiとなる。
g, iに関する解答群
ア：“1001101”B
イ：“1010100001”B
ウ：“1011001”B
エ：“101111”B
オ：“110011”B
カ：“111101”B
hに関する解答群
ア：4
イ：6
ウ：9
エ：13
模範解答
g：カ、h：イ、i：ウ
解説
解答の導き方
この設問では、検索文字列に含まれる「[]」を、指定した文字のどれか1文字に一致する表現として扱います。たとえば「[BA]」は、検索文字列の1文字分の位置を使い、その位置には「B」または「A」が入ります。
ビットマスク（文字ごとに、その文字が検索文字列のどの位置に現れるかを0と1で表す値）では、検索文字列の位置ごとに対応するビットを1にします。ビットごとの論理和（どちらかの値が1なら結果を1にする処理）を使うので、同じ文字が複数の位置にある場合も、その位置をすべて記録できます。
プログラムでは、PatLenが「検索文字列の有効な位置」を数えます。Modeは、文字が「[]」の中にあるかどうかを表します。
- 「[」が現れると、Modeを1にしてPatLenを1増やします。これは、文字の候補を並べる位置を1つ確保するためです。
- 「[]」の中の文字は、PatLenを増やさず、現在の位置に対応するビットを各文字のMaskに設定します。
- 「]」が現れると、Modeを0に戻します。
- 「[]」の外にある文字は、PatLenを1増やして、その位置に対応するビットを設定します。
「1」をPatLenから1を引いた数だけ論理左シフトすると、その位置に対応するビットだけが1になります。たとえばPatLenが3なら、下位から3番目のビットが1になります。
gとhを求めます。
Pat[]の「AC[BA]A[ABC]A」を、検索位置ごとに分けると次のようになります。
検索位置は6つなので、PatLenは6です。関数の返却値はPatLenなので、hは6です。
次に、文字「A」に対応するMask[1]を考えます。「A」が現れる検索位置は1、3、4、5、6です。ビット列は、左から検索位置6、5、4、3、2、1の順に並ぶので、検索位置6～1について、1、1、1、1、0、1となります。
したがって、Mask[1]は「111101」Bとなり、gはカです。
iを求めます。
Pat[]が「AC[B[AB]AC]A」の場合を、文字ごとに追います。Modeは、入れ子の深さではなく、0か1だけで状態を管理しています。
内側の「]」が現れた時点でModeが0になります。そのため、本来は外側の「[]」の中にある「A」と「C」も、「[]」の外にある文字として扱われ、PatLenが増えます。
Mask[1]で1になる位置は1、4、5、7です。検索位置7から1までを並べると、1、0、1、1、0、0、1となるため、Mask[1]は「1011001」Bです。したがって、iはウです。
誤りやすいポイント
- Pat[]に書かれた文字数と、PatLenが数える位置数は同じとは限りません。「[]」内の候補文字は、複数あっても検索位置を1つだけ使います。
- ビット列は、下位から数えた位置が検索位置に対応します。表示するときは、検索位置の大きい側が左になります。
- 入れ子になった「[]」を正しく扱うには、入れ子の深さを数える必要があります。このプログラムのModeは0か1だけなので、内側の「]」でModeが0になると、外側の「[]」の途中でも外側にいるものとして処理されます。
- ビットごとの論理和は、既に1になっているビットを0に戻しません。同じ文字が複数の位置に現れる場合は、それぞれの位置のビットが残ります。
FAQ
Q: 「[BA]」の「B」と「A」は、なぜ同じ位置に対応するのですか？
A: 「[BA]」は、その位置に「B」または「A」のどちらか1文字が入る表現だからです。どちらの場合も、検索文字列全体では同じ1文字分の位置を使います。
A: 「[BA]」は、その位置に「B」または「A」のどちらか1文字が入る表現だからです。どちらの場合も、検索文字列全体では同じ1文字分の位置を使います。
Q: PatLenは、何を数えていますか？
A: 「[]」の候補文字を1つの位置として数えた、検索文字列の有効な位置数です。その値が関数の返却値になります。
A: 「[]」の候補文字を1つの位置として数えた、検索文字列の有効な位置数です。その値が関数の返却値になります。
Q: 入れ子の「[]」を正しく扱うには、何が必要ですか？
A: 「[]」の内側にいる深さを数える仕組みが必要です。このプログラムはModeの0と1だけで判定するため、入れ子には対応できません。
A: 「[]」の内側にいる深さを数える仕組みが必要です。このプログラムはModeの0と1だけで判定するため、入れ子には対応できません。
関連キーワード: 正規表現、ビットマスク、論理左シフト、ビットごとの論理和、状態変数
