Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

平成27年度春季応用情報午後問3

Ruby 情報処理技術者試験

平成27年度春季応用情報技術者試験(AP)の午後問題3はデータ圧縮の前処理として用いられるBlock-sorting(ブロックソート)に関する問題でした。学生時代(20年以上前)、データ圧縮について少し勉強したことがあるのですが、Block-sortingというアルゴリズムに接するのは今回が初めてです。Wikipedeiaで調べてみると、1994に開発されているようです。ちょうど自分が学生時代、データ圧縮について勉強しているときに開発されてたんですね。

2015h27h_ap_pm_qs.pdf

h27h_ap_pm3.rb

実行結果

$ ruby h27h_ap_pm3.rb
入力文字列: papaya
変換結果　: yppaaa, 3
復元処理後: papaya

入力文字列: kiseki
変換結果　: skkeii, 4
復元処理後: kiseki

思うこと

「図4 関数decodeのプログラム」ではエ、オ、カが空欄になっていますが、エとオをwhileループの外に出したということは、カは、「n != line」と答えさせようという意図があるのではないでしょうか。模範解答のカを想定するのであれば、エとオは不要で以下で良いのではと思います。ひょっとしたら勘違いをしているかもしれませんが。

  outputString = []
  n = line
  while outputString.length < blockSortString.length
    outputString << decodeArray[0][n]
    n = decodeArray[1][n]
  end

参考

ブロックソート - Wikipedia