Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

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

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

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

参考