データ構造及びアルゴリズム

はじめに

基本情報技術者試験 午後問題の「データ構造及びアルゴリズム」について解説する。

• 令和元年度 秋季「Bitap 法による文字列検索」
• 平成31年度 春季「ハフマン符号化を用いた文字列圧縮」
• 平成30年度 秋季「整数式の解析と計算」
• 平成30年度 春季「ヒープの性質を利用したデータの整列」
• 平成29年度 秋季「文字列の誤りの検出」
• 平成29年度 春季「最短経路の探索」
• 平成28年度 秋季「数値の編集」
• 平成28年度 春季「簡易メモ帳のメモリ管理」
• 平成27年度 秋季「Boyer-Moore-Horspool 法を用いた文字列検索」
• 平成27年度 春季「クイックソートを応用した選択アルゴリズム」
• 平成26年度 秋季「編集距離の算出」
• 平成26年度 春季「空き領域の管理」
• 平成25年度 秋季「文字列の圧縮」
• 平成25年度 春季「食料品店の値引き処理」
• 平成21年度 秋季「ニュートン法」

うかる！ 基本情報技術者 [午後・アルゴリズム編] 2021年版 福嶋先生の集中ゼミ【電子書籍】[ 福嶋宏訓 ] 価格：1980円 (2021/5/23時点) 楽天で購入

令和元年度 秋季 Bitap 法による文字列検索

関数 BitapMatch は，Bitap 法を使って文字列検索を行うプログラムである。

Bitap 法は，検索対象の文字列（以下，対象文字列という）と検索文字列の照合に，個別の文字ごとに定義されるビット列を用いるという特長をもつ。

なお，本問では，例えば 2 進数の 16 ビット論理型の定数 0000 0000 0001 0101 は，上位の 0 を省略して “10101” B と表記する。

平成31年度 春季 ハフマン符号化を用いた文字列圧縮

“A” ～ “D” の 4 種類の文字から成る文字列をハフマン符号化によって圧縮する。ハフマン符号化では，出現回数の多い文字には短いビット列を，出現回数の少ない文字には長いビット列を割り当てる。ハフマン符号化による文字列の圧縮手順は，次の (1) ～ (4) の通りである。

(1) 文字列中の文字の出現回数を求め，出現回数表を作成する。例えば，文字列 "AAAABBCDCDDACCAAAAA" （以下，文字列 α という）中の文字の出現回数表は，表 1 のとおりになる。

(2) 文字の出現回数表に基づいてハフマン木を作成する。ハフマン木の定義は，次のとおりである。

• 節と枝で構成する二分木である。
• 親である節は，子である節を常に二つもち，子の節の値の和を値としてもつ。
• 子をもたない節（以下，葉という）は文字に対応し，出現回数を値としてもつ。
• 親をもたない節（以下，根という）は，文字列の文字数を値としてもつ。

文字列 α に対応するハフマン木の例を，図 1 に示す。

注記　丸のなかの数値は各節がもつ値を表す。"A" ～ "D" は葉に対応する文字を表す。

ハフマン木は，次の手順で配列によって実現する。

1. 節の値を格納する 1 次元配列を用意する。
2. 文字の出現回数表に基づいて，各文字に対応する葉の値を，配列の先頭の要素から順に格納する。
3. 親が作成されていない節を二つ選択し，選択した順に左側の子，右側の子とする親の節を一つ作成する。この節の値を，配列中で値が格納されている最後の要素の次の要素に格納する。節の選択は節の値の小さい順に行い，同じ値をもつ節が二つ以上ある場合は，配列の先頭に近い要素に値が格納されている節を選択する。
4. 親が作成されていない節が一つになるまで c. を繰り返す。

(3) ハフマン木から文字のビット列（以下，ビット表現という）を次の手順で作成する。

1. 親と左側の子をつなぐ枝に 0，右側の子をつなぐ枝に 1 の値をもつビットを割り当てる。
2. 文字ごとに根から対応する葉までたどったとき，枝のビット値を順に左から並べたものを各文字のビット表現とする。

図 2 に示すとおり，根から矢印のようにたどると，文字列 α の文字 "B" のビット表現は 010 となる。

注記　線分は枝を表し，枝の上の数値は各枝のビット値を表す。

(4) 文字列の全ての文字を (3) で得られたビット表現に置き換えて，ビット列を作成する。

平成30年度 秋季 整数式の解析と計算

整数式を受け取って，その値を返すプログラムである。例えば，例 1 に示す整数式を受け取ると，その値 50 を返す。

平成30年度 春季 ヒープの性質を利用したデータの整列

ヒープの性質を利用して，データを昇順に整列するアルゴリズムを考える。ヒープは二分木であり，本問では，親は一つ又は二つの子をもち，親の値は子の値よりも常に大きいか等しいという性質をもつものとする。

平成29年度 秋季 文字列の誤りの検出

文字列の誤りを検出するために，N 種類の文字に 0, 1, ... , N-1 の整数値を重複なく割り当て，検査文字を生成するプログラムと，元となる文字列の末尾に検査文字を追加した検査文字付文字列を検証するプログラムである。

平成29年度 春季 最短経路の探索

副プログラム ShortestPath は，N 個（N > 1）の地点と，地点間を直接結ぶ経路及び距離が与えられたとき，出発地から目的地に至る最短経路とその距離を求めるプログラムである。最短経路とは，ある地点から別の地点へ最短経路で移動する際の経由地を結んだ経路である。副プログラム ShortestPath では，出発地の隣接地点から開始して，目的地に向かって最短距離を順次確定する。ある地点の隣接地点とは，その地点から他の地点を経由せずに直接移動できる地点のことである。

平成28年度 秋季 数値の編集

事務計算においては，数値を見やすく表示（印字）するために，例えば 3 桁ごとに区切りの “,” を挿入するなどの編集処理がよく行われる。

平成28年度 春季 簡易メモ帳のメモリ管理

携帯端末上で稼働する簡易メモ帳の機能のうち，メモの編集処理（メモの追加・削除・変更・移動）を行うプログラムである。

平成27年度 秋季 Boyer-Moore-Horspool 法を用いた文字列検索

Boyer-Moore-Horspool 法（以下，BM 法という）を用いて，文字列検索を行うプログラムである。BM 法は，検索文字列の末尾の文字から先頭に向かって，検索対象の文字列（以下，制御文字列）と 1 文字ずつ順に比較していくことで照合を行う。比較した文字が一致せず，照合が失敗した際には，検索文字列中の文字の情報を利用して，次に照合を開始する対象文字列を決定する。このようにして明らかに不一致となる照合を省き，高速に検索できる特徴がある。

平成27年度 春季 クイックソートを応用した選択アルゴリズム

与えられた n 個のデータの中から k 番目に小さい値を選択する方法として，クイックソートを応用したアルゴリズムを考える。クイックソートとは，n 個のデータをある基準値以下の値のグループと基準値以上の値のグループに分割し（基準値はどちらのグループに入れても構わらない），更にそれぞれのグループで基準値を選んで二つのグループに分割するという処理を繰り返してデータを整列するアルゴリズムである。クイックソートを応用して k 番目に小さい値を選択するアルゴリズムでは，データを二つのグループに分割した時点で，求める値はどちらのグループに含まれるかが確定するので，そのグループだけに，更に分割する処理を繰り返し適用する。グループの分割ができなくなった時点で，k 番目に小さい値が選択されている。

MATLAB でクイックソートを応用した選択アルゴリズムを作成してみた。

x=[3 5 1 4 2 7 6];
n=7;
k=3;

Top=1;
Last=n;

while Top < Last
  Pivot=x(1,k);
  i=Top;
  j=Last;
  while x(1,i) < Pivot
    i=i+1;
  endwhile
  while Pivot < x(1,j)
    j=j-1;
  endwhile
  if i >= j
    break
  endif
  work=x(1,i);
  x(1,i)=x(1,j);
  x(1,j)=work;
  i=i+1;
  j=j+1;
  if i <= k
    Top=j+1;
  endif
  if k <= j
    Last=i-1;
  endif
endwhile

x(1,k)

クイックソート

クイックソート（quicksort）は，1960 年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。

$n$ 個のデータをソートする際の最良計算量及び平均計算量は， $O(n\log{n})$ である。他のソート法と比べて，一般的に最も高速だといわれているが対象のデータの並びやデータ数によっては必ずしも速いわけではなく，最悪の計算量は $O(n^2)$ である。

平成26年度 秋季 編集距離の算出

二つの文字列の差異を測る指標に編集距離がある。編集距離の概念は，文書比較や検索キーワードの候補の提示などに用いられている。編集距離とは，1 文字の追加操作又は削除操作を繰り返し適用し，ある文字列を別の文字列に変換するのに必要な最小の操作回数である。例えば，文字列 “abcabba” を文字列 “cbabac” に変換する場合，下表に示す操作 1 ～ 5 によって変換が完了する。下表は，最小の操作回数で変換する一例を示しており，編集距離は 5 となる。

二つの文字列間の編集距離を返す関数を MATLAB で作成した。引数の仕様は，次のとおりである。疑似言語において，各配列の添字は，0 から始まっているが，MATLAB では，各配列の添字は，1 から始めている（MATLAB では配列の添字を 0 とすることはできないため）。

Str1=["abcabba"];
Str1Len=length(Str1);
Str2=["cbabac"];
Str2Len=length(Str2);
D=zeros(Str1Len+1,Str2Len+1);
alpha=0;
beta=0;
for X=1:1:Str1Len+1;
  D(X,1)=X-1;
endfor
for Y=1:1:Str2Len+1;
  D(1,Y)=Y-1;
endfor

for X=2:1:Str1Len+1
  for Y=2:1:Str2Len+1
    if Str1(1,X-1)==Str2(1,Y-1)
      D(X,Y)=min([D(X-1,Y-1),D(X,Y-1)+1,D(X-1,Y)+1]);
      alpha=alpha+1;
    else
      D(X,Y)=min([D(X,Y-1)+1,D(X-1,Y)+1]);
      beta=beta+1;
    endif
  endfor
endfor

D(Str1Len+1,Str2Len+1)
alpha
beta

平成26年度 春季 空き領域の管理

セルを 1 列に連続して並べた領域がある。この領域中のセルについて，割当てと解放の処理を行う。

各セルには，セル位置を指定するための連続する整数が対応している。領域のセル数や，対応する整数の範囲には，特に制限がない。

関数 Alloc(始点, 終点) は，引数で指定した始点から終点までの連続した “空き” セルを “割当済み” として，空きリストから取り除く。関数 Free(始点, 終点) は，引数で指定した始点から終点までの連続した “割当済み” セルを “空き” として，空きリストに戻す。

平成25年度 秋季 文字列の圧縮

プログラムの説明

英字 A ～ Z から構成される文字列を圧縮する副プログラム Compress，及び圧縮された文字列を復元する副プログラム Decompress である。

圧縮処理の説明

副プログラム Compress では，配列 Plaindata に格納されている圧縮前の文字列を受け取り，圧縮後の文字列を配列 Compressedata に格納する。

副プログラム Compress の引数の仕様

Compress の引数の仕様は，次のとおりである。

ABC=("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
%圧縮前の文字列が格納されている１次元の配列
Plaindata=["ABCDEFABCDABCDEF"];
%圧縮前の文字列の長さ
Plength=length(Plaindata);
%制御記号の設定
Esym="$";

Pindex=1;
Cindex=1;

while and(Pindex < Plength+1,Pindex < 5)
  Compresseddata(1,Cindex)=Plaindata(1,Pindex);
  Cindex=Cindex+1;
  Pindex=Pindex+1;
endwhile

while Pindex < Plength+1
  Maxfitnum=-1;
  Maxdistance=-1;
  Distance=4;
  while and(Distance<=26,Pindex-1-Distance>=0)
    Fitnum=0;
    %同じ文字並びの文字数を調べる
    while and(Fitnum < Distance,(Pindex-1+Fitnum) < Plength);
      %文字が一致するかどうかを調べる
      if Plaindata(1,Pindex+Fitnum)!=Plaindata(Pindex-Distance+Fitnum);
        break;
      endif
      Fitnum=Fitnum+1;
    endwhile
    %文字列が4以上，かつ，最も多いかどうかを調べる
    if and(Fitnum>=4,Maxfitnum<Fitnum);
      Maxfitnum=Fitnum;
      Maxdistance=Distance
    endif
    Distance=Distance+1;
  endwhile
  
  if Maxfitnum==-1;
    Compresseddata(1,Cindex)=Plaindata(1,Pindex);
    Cindex=Cindex+1;
    Pindex=Pindex+1;
  elseif
    Compresseddata(1,Cindex)=Esym;
    Compresseddata(1,Cindex+1)=ABC(1,Maxdistance);
    Compresseddata(1,Cindex+2)=ABC(1,Maxfitnum);
    Cindex=Cindex+3;
    Pindex=Pindex+Maxfitnum;
  endif
endwhile
Clength=Cindex-1;

上記の Compresseddata を出力すると，次のとおり。

ABCDEF$FD$JF

復元処理の説明

副プログラム Decompress では，配列 Compresseddata に格納されている圧縮された文字列を受け取り，復元後の文字列を配列 Plaindata に格納する。復元処理の内容を次に示す。

1. 配列 Compresseddata の先頭から圧縮された文字列を順に調べる。
2. 文字が制御記号でなければ，その文字をそのまま配列 Plaindata に格納する。
3. 文字列が制御記号ならば，圧縮列の距離，文字数から，圧縮前の文字並びを復元して Plaindata に格納する。

副プログラム Decompress の引数の仕様

Decompress の引数の仕様は，次のとおりである。

平成23年度 春季 食料品店の値引き処理

ある食料品店では，従来の特売方法に加えて，新たに選択型特売を始めることになった。選択型特売とは，例えば 3 種類の商品中から合計 3 個（3 商品を各 1 個，同一商品を 3 個など）を選択して購入すれば値引きをするという特売方法である。

このプログラムは，レジ用プログラムの一部として，選択型特売の値引き処理をする。プログラムの実行は，顧客がレジに持ち込んだ商品のバーコードを全て読み込んで，購入する商品が確定した時点で行う者とする。

平成21年度 秋季 ニュートン法

方程式の解の一つを求めるアルゴリズムである。任意に定めた解の予測値から始めて，計算を繰り返しながらその値を真の値に近づけていく。この方法は，ニュートン法と呼ばれる。

アルゴリズム 1 の説明

3 次方程式 $a_3 x^3 + a_2 x^2 +a_1 x + a_0 = 0$ の解の一つを，次の手順で求める。

1. 解の予測値 $x$，係数 $a_3$，$a_2$，$a_1$，$a_0$ を読み込む。
2. $3 \times a_3$ を $b_2$ に，$2 \times a_2$ の値を $b_1$ に，$1 \times a_1$ の値を $b_0$ に，それぞれ求める。
3. 次の a. ～ d. の処理を一定の回数繰り返す。
   1. $a_3 x^3 + a_2 x^2 +a_1 x + a_0$ の値を求め，これを $f$ とする。
   2. $b_2 x^2 + b_1 x + b_0$ の値を求め，これを $d$ とする。
   3. $x$，$f$，$d$ の値を印字する。
   4. $x-f/d$ の値（解の一つにより近い値となる）を求め，これを新たな $x$ とする。

プログラム 1 は，このアルゴリズム 1 を MATLAB で実装したものである。

a=[3,-1,-3,1];
x=2.5;

b=zeros(1,3);
b(1,3)=3*a(1,4);
b(1,2)=2*a(1,3);
b(1,1)=  a(1,2);

for n1=2:9
  f=((a(1,4)*x+a(1,3))*x+a(1,2))*x+a(1,1);
  d=(b(1,3)*x+b(1,2))*x+b(1,1);
  printf("%f, %f, %f\n",x,f,d);
  x=x-f/d;
endfor

プログラム 1 を MATLAB で実行した結果，次に示す通り解の一つである $x=3$ が近似的に得られた。

2.500000, -2.625000, 2.750000
3.454545, 4.969947, 14.074380
3.101425, 0.874168, 9.247965
3.006900, 0.055485, 8.082941
3.000035, 0.000283, 8.000425
3.000000, 0.000000, 8.000000
3.000000, 0.000000, 8.000000
3.000000, 0.000000, 8.000000

プログラム 1 で与えた 3 次関数（$f=x^3-3x^2-x+3$）をグラフにすると次図となる。