平成26年 秋期 基本情報技術者 午後 問08
問08 必須問題問8 次のプログラムの説明及びプログラムを読んで,設問1,2に答えよ。 二つの文字列の差異を測る指標に編集距離がある。編集距離の概念は,文書比較や 検索キーワードの候補の提示などに用いられている。編集距離とは,1文字の追加操作又は 削除操作を繰り返し適用し,ある文字列を別の文字列に変換するのに必要な最小の操作回数である。 例えば文字列 "abcabba" を文字列 "cbabac" に変換する場合,図1に示す操作1〜5によって変換が 完了する。図1は,最小の操作回数で変換する一例を示しており,編集距離は5となる。
図1 文字列 "abcabba" を文字列 "cbabac" に変換する場合の例 関数 CalcEditDistance は,二つの文字列間の編集距離を返す関数である。 (1) 変換元の文字列を Str1[],変換先の文字列を Str2[] とする。また, 配列の添字は0から始まり,文字列 Str1[] の i 番目の文字は Str1[i−1] と表記する。 したがって,Str1[] = "abcabba" の場合,1番目の文字 = Str1[Ø]= "a", 2番目の文字 = Str1[1] = "b" となる。Str2[] についても同様である。 (2) 関数 CalcEditDistance は,エディットグラフと呼ばれるグラフの最短距離取得問題の 考え方に基づいて,編集距離を求めている。編集距離の求め方は次のとおりである。 (b) Ø ≦ Y ≦ Str2Len を満たす全ての整数 Y に対して,点 (Ø,Y) から点 (Str1Len,Y) に線分を引く。 (C) Ø ≦ X < Str1Len,Ø ≦ Y < Str2Len を満たす全ての整数 X,Y の組に対して, Str1[X] と Str2[Y] が同一の文字の場合,点(X,Y)から点(X+1,Y+1)に線分を引く。
図2 Strl[]="abcabba",Str2[]="cbabac" の場合の (4) 関数 CalcEditDistance では,点(Ø,Ø)から点(X,Y)への最短移動距離を D[X,Y] に求めている。D[X,Y] は,既に算出されている D[X−1,Y−1], D[X,Y−1],D[X−1,Y] を用いて求めることができる。これによって編集距離を算出している。 〔関数 CalcEditDistance の引数と返却値〕 関数 CalcEditDistance の引数の仕様は,次のとおりである。各配列の添字は,0 から始まる。
関数 CalcEditDistance では,次の関数 Min を使用している。 〔関数 Min の仕様〕 引数として与えられた二つ以上の整数値の中で最も小さい値を返却値とする。 〔プログラム〕 設問1 プログラム中の に入れる正しい答えを, 解答群の中から選べ。 a に関する解答群 イ Str1[X−1] ≠ Str2[Y−1] ウ Str1[X] = Str2[Y] エ Str1[X] ≠ Str2[Y] オ Str1[X−1] = Str1[X] and Str2[Y−1] = Str2[Y] カ Str1[X−1] ≠ Strl[x] and Str2[Y−1] ≠ Str2[Y] b に関する解答群 イ D[Str1Len,0] ウ D[Str1Len,Str2Len] エ D[Str1Len,Str2Len]+1 オ D[Str1Len−1,Str2Len−1] カ D[Str1Len−1,Str2Len−1]+1
設問2 次の記述中の に入れる正しい答えを, 解答群の中から選べ。
Str1[]="peace",Str2[]="people" の場合のエディットグラフは となる。 c に関する解答群 d に関する解答群
オ 10 カ 12 キ 14 ク 16 e に関する解答群
オ 22 カ 24 キ 26 ク 28 f に関する解答群 オ 8 カ 9 キ 10 ク 11
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
©2004-2024 情報処理試験.jp
|
プライバシーポリシー・著作権・リンク
|
お問合わせ
|