列に変換し , c2 に保存します。 16 , 17 行目 では処理開始前の時刻と処理完了後の時刻 を変数 cl , c2 から表示しています。しかし , こではどんなに長い時間処理を行っても , 同じ時刻しか表示されません。 このような現象は , 関数 ctime が内部に 持つ static 変数のアドレスを戻り値として いるために発生します。つまり ctime から の戻り値であるアドレスは , 1 つのプログ ラム内では常に同じ値が返されるのです。 そのため , 変数 cl と c2 は同じアドレスを指 し示すことになります。その結果 , 9 行目 で c ⅱ me が呼ばれ , 引数で指定された秒を 文字列に変換した内部の static 変数は , 14 行目の呼び出し時に上書きされることにな ります。 このような関数の 2 度目の呼び出しを自 分では注意して行わないようにしているつ もりでも , 別の関数を呼び出してその中か ら 2 度目の呼び出しが行われていたなどと いうこともあります。 ④の場合も , なにげなく引数に指定した 変数を変更すると , 関数から戻されたアド レスで指し示される先の内容が変わってし まうことになります ( 後に出てくる List 3 を よく見てください ) 。⑤は呼び出し元なり , 何らかの方法で戻されたアドレスの領域を 解放 ( free 関数の呼び出し ) しなければなり ません。いずれにしても一長一短がありま す。 以上をまとめるとポインタを使いこなす ためのコッとは , どれだけ実際のメモリを イメージできるかということではないでし ようか。ポインタ変数と , ポインタにより 指し示される先の変数は別物であり , 記憶 クラスなどの特性により有効期間がまちま ちであったり , 内容も変化します。ポイン タ変数により , どのクラスに属する変数の アドレスを管理しているかを常に心がける ようにしましよう。 こで , Fig. 4 ~ 6 に今回の内容をまとめ データ型変換のまとめ Fig. 4 データ型変換のまとめ 自動型変換 ・自動型変換は「代入時」「演算時」「関数の引数引き渡し時」に発生する ・データ型には優先順位が存在する ・下位のデータ型変数へ上位のテータ型変数を代入する場合 , 有効範囲が失われる可能性がある ・演算時には使用されているデータ型の中でもっとも上位のデータ型へ変換される ・関数の引数引き渡し時には , 引き渡したデータ ( 実引数 ) は , 関数内で受け取った引数 ( 仮引数 ) のテータ型へ変換される 強制型変換 ( キャスト ) ・プログラマが任意で型変換を行いたい場合 , キャスト処理を行う ・書式は , 「 ( テータ型 ) 式」 Fig. 5 typedef のまとめ typedef : データ型を再定義する ・ typedef の機能はあるテータ型名に新しく別の名前 ( 同義語 ) を付けることができること 書式は , 「 typedef 既存のテータ型新しいデータ型名 ( 同義語 ) 」 #define と typedef ・ typedef のほかにデータ型名を再定義するために # define を使用することができるが , 基本的 に機能は異なる ・ # define は文字列を置き換える機能を持つマクロ ・ typedef はテータ型に新しい名前を再定義する命令 Fig. 6 変数のスコープと記憶クラスのまとめ 広域変数 ( グローバル変数 ) と局所変数 ( ローカル変数 ) ・広域変数 ( グローバル変数 ) は関数の外で宣言され . 宣言より下のすべての関数から参照が可能 ・局所変数 ( ローカル変数 ) は関数の中で宣言され , 宣言された関数内のみ参照が可能 記憶クラス 4 : void main( ) 3 : oa し fncgetcirclearea(float *r); #include <stdio. h> 1 : / * 円の面積を求めるプログラム * / Ex. 4.2 の解答 ・ extern ( 外部変数 ) は他ファイルで定義されたグローバル変数を参照するための指定子 ・ static ( 静的変数 ) はプログラムが起動されてから , 終了するまで値を保持し続ける ・ auto ( 自動変数 ) は関数内でのみ有効 ・変数の記憶クラスの書式は「記憶クラスデータ型変数名」 st 2 : 9 : 10 : 11 : 12 : } 13 : 14 : 15 : ( 16 : 17 : 18 : 19 : 20 : 21 : 22 : 23 : } 日 oa し f-hankei , f-area; pr 土 n し f ( ”円の半径を入力してください。” scanf( "%f", &f-hankei); f—area = fncgetcircl earea ( &f—hankei ); p て土 n セ f ( ”円の面積は %f 跏 % f-area); 日 oa ヒ fncgetcircl earea ( f 1 oa セ * て ) oa し f—a; if()r ぐ 0.0 ) て et n 0. / * 半径が 0 以下の時は 0.0 とする * / f—a = * て * * て * 3.1415 return f—a ー 52 C MAGAZINE 2 1 9

0 第 6 回 C 言語入門講座 0 0 データ型変換と変数の スコープ・記憶クラス 小薗三典 / 中井信ム した。今回も関数の呼び出しに関連して , データの型変換と変数のスコー 前回 , 関数間の引数の引き渡し方とアドレス , ポインタについて解説しま プ , 記憶クラスについて説明します。 始めに ( 適用範囲 ) についての説明を進めていきま その後関数の説明に戻り , 関数のスコープ でぜひしつかりと覚えてください。さらに ますが , とても役に立つ , 重要な機能なの することが重要となります。単純ではあり よびアドレスは複合的に理解し , また利用 りと単純な決まりごとなのですが , 関数お あわせて紹介します。これらの 1 つ 1 つはわ するために必要となるほかの重要な機能も 進めるため , あるいはよりアドレスを理解 アドレスを中心に解説しますが , 今後話を ついて説明を行いました。今回も引き続き て , また関数間での引数の引き渡し方法に 得の 1 つの山場ともいえるアドレスについ みなさん , こんにちは。前回は C 言語習 データ型変換 す。 って型変換される場合 ( 演算や代入時など ) ータ型の変換には自動的にあるルールに従 データ型の変換を行うことができます。デ 場合もあります。こうした場合のために データ型の変数間で演算することが必要な 使用していました。しかし実際には異なる では , 基本的に同じデータ型同士の変数を これまで演算や関数への引数の引き渡し と , 任意で型変換を行う場合があります。 こではこれらについてまとめていきます。 自動型変換 自動的に型変換が行われる場合には , あ るルールが適用されます。 char く int < unsigned int く long int く unsignedlong int く float く double く long double このような表現範囲の順位付け ( 左にい くほど下位のデータ型 ) が , 暗黙のルール としてあります。では上記の順序を元に自 動型変換が行われるケースを確認していき ます。 ◆代入時 例として次のように変数が宣言されてい るとします。 char ch—a 土 n セ 創 oa し f—a ではそれぞれの場合について考えていき ます。 ・上位のテータ型変数 = 下位のデータ型変数 ( 代入 ) たとえば , i —a = Ch—a ー というような代入を行った場合 , 代入され るほうが上位のデータ型であるため , 問題 なくすべての情報が格納されます。 ・下位のデータ型変数 = 上位のデータ型変数 ( 代入 ) 逆に i—a = f—a; というような代入を行った場合 , 代入され るほうが下位のデータ型であるため , 次の ような問題が発生する場合があることを覚 えておいてください。 ( 1 ) 小数点以下の切り捨て 少数部が切り捨てられます。このため , 元のデータはより簡潔な形で格納される ことになります。 ( 2 ) オーパフロー int 型で表現できる範囲は一 2147483648 ~ + 2147483 7 でしたね ( 第 1 回参照 ) 。と ころが float 型では精度が落ちるものの , 1015 といった大きな数値も表現できます。 このようにⅲ t 型で格納しきれない大きな 数が代入された場合の結果は , ANSI では 未定義であり , 使用している処理系に委 ねられます。 一般的には下位のデータ型よりも上位デ ータ型のほうが表現できる範囲が広くなっ ています ( 少数部や , より大きな数値 ) 。下 位データ型を上位データ型に代入する場合 はさほど問題は発生しませんが , 上位デー タ型を下位データ型に代入する場合は , 少 数部の欠落やオーパフローといった , さま ざまな問題が発生します。また符号付きの 変数を符号なしの変数に代入する場合に も , 同じような問題が発生します。このよ Getlnto C world ! ! イ /

カリ 画像処理を極める Fig. 3 E ⅱ as 符号化で得られた 1 / 4 という値から復合する様子 (P ( 0 ) = 1 / 3 , P ( 1 ) = 2 / 3 の場合 ) (a) データの出現頻度に従って全体を 1 : 2 に分割し 0 く 1 / 4 く 1 / 3 で 0 の区間に含まれるのでデータ値 1 , Fig. 4 0 P(O) 4 値のテータ列を扱う区間 0 を出力 0 1 P ( 1 ) P(2) 1 P ( 3 ) 1 3 (b) (a) の領域をさらに 1 . 2 に分割し , 1 / 9 く 1 / 4 く 1 / 3 で 1 の区間に含まれるのでデータ値 1 " を出力 1 3 1 の区間 2 1 1 1 9 0 0 の区間 1 の区 2 (c) (b) の領域をさらに 1 : 2 に分割し , 5 / 27 く 1 / 4 く 1 / 3 で 1 の区間に含まれるのでデータ値 -1 " を出力 0 Fig. 5 1 9 5 27 1 0 区間 1 3 2 ※ (a) ~ (c) の処理の結果 , データ列 ( 0 , N 値データを扱う区間 1 ) が復号される P ( 1 ) 1 の区間 P(N—2) N ー 2 の区間 P (N ー 1 ) N ー 1 の区間 1 1 P ( 0 ) 0 の区間 0 P ( 0 ) P(2) 2 の区間 P ( 0 ) + P ( 1 ) P ( 0 ) + P ( 1 ) + P ( 2 ) Fig. 6 E ⅱ as 符号化で利用する式 ±p(i) く , く )p(i) んん一ん肥 ぉーんル ん / 砒 + ( ん g ん一 / 砒 ) p (i) いい + ( ん g ん一い ) p(i) ・ ( 式 1 ) ・ ( 式 2 ) ・ ( 式 3 ) ・ ( 式 4 ) んⅣ , ん方を更新していけば , データ列が なくなった時点でデータ列を表す区間が求 められます。 以上をまとめると , EIias 符号化の計算手 順は次のようになります。 ① / 0 ル = 0 , わ / わ = 1 とする ②データ列を読み , その値に従って Fig. 6- ( 式 3 ) を計算し , 新しい / 0 Ⅳとわ / わを 求める ③データ列がなくなるまで②を繰り返す ④最終的な / 0 Ⅳ , わ / g わがデータ列全体を 表現する区間となる この方法により , 純粋な計算だけでデー タ列を表す区間が求められます。 次に復号処理のための計算方法を考えて みます。前述のように , 復号処理は符号化 のときと同様に出現確率に合わせて区間を 分け , 符号化で得られた値が入る区間を求 めることで元のデータ列を求めていきま す。このとき , 選択された区間のわ w , ん方 を Fig. 7 に示すようにそれぞれ 0 , 1 になる ように補正すれば , 区間の中の境界を今ま での区間の境界と一致させることができま す。この性質を利用して , 符号化の数値 val を Fig. 6- ( 式 4 ) という式により修正するこ 画像処理を極めるアルゴリズムラボ 97 ④ Fig. 6- ( 式 3 ) により , / 0 Ⅳ , わ / g わを更新 間に対応するデータ値を出力する ③ v 引が入っている区間を求め , その区 より修正し , 新たな val& する ②符号化された数値 va 陸 Fig. 6- ( 式 4 ) に ものとする Fig. 6- ( 式 1 ) のように分けられている ① / 0 ル = 0 , わ / わ = 1 とする。また , 区間は 順になります。 以上を元に復号処理を考えると , 次の手 じ区間を継続して利用できます。 とで , 新たな区間分けをすることなく , 同

カリ私 画像処理を極める ことができます。また , 計算を固定小数点 いるものとして処理しました。このような ing) 」と呼ばれることもあります。 のビットの範囲で行うためには , 登場頻度 方法を「静的符号化」と呼ぶことがありま 適応型算術符号化でも算術符号化の基本 についても , 合計値がある値未満となるよ す。このような静的な符号化法には , 次の 的な処理方法 , つまり「各データ値の登場 うに正規化することが必要です。 ような問題があります。 頻度によって区間を分け , その区間によっ 今まで述べてきた中で , 算術符号化の処 ・各データ値の登場頻度の情報を出力デ てデータ列を表現する」という考え方は変 理が近似値を多く用いていることがわかり ータのどこかに格納しなければならず , わりません。違いは , 静的算術符号化では ます。符号化の際に正確な数値で区間分け これが圧縮結果データのサイスを大き 処理の始めにデータ列全体における各デー を行っていないことに疑問を持たれる方も くしてしまう タ値の登場頻度を求めて , 処理全体で同じ いるでしよう。しかし , 符号化・復号化で ・登場頻度を求める→符号化というよう 登場頻度情報を用いて処理するのに対し 同じ方法をとり , 同じように誤差を生じさ にデータ列を 2 度読みする必要があり , て , 適応型符号化では今までに処理したデ せる限りは , 元のデータが損なわれること オンラインテータなどシーケンシャル ータ列の登場頻度を用いて符号化処理を行 はありません。この場合 , 理論的最適値に に流れてくるデータをそのままで処理 う点です。 ならない可能性もありますが , 許容される できない それでは , 実際に適応型算術符号化の処 範囲を超えることはないでしよう。 とくに 1 つ目の問題は圧縮アルゴリズム 理方法を見ていくことにします。以下の説 としては深刻です。たとえば , 8 ビットの [ 注 2 ] ( ・・・・・・ ) 2 は 2 進数を表します 明では , 4 値のデータ列を処理することを データ列を処理し , 各データ値の登場頻度 想定していますが , N 値になった場合も , を 2 バイトで記録する場合 , それだけで 512 分割する区間を増やすだけです。 適応型算術符号化 バイトが必要になります。このような固定 適応型算術符号化では , データ列全体の こまで説明してきた算術符号化のアル 長データが圧縮後のデータに必ず付随する 登場頻度を求めないので , 初期状態ではす ゴリズムでは , データ列全体の中での各デ ことは , 圧縮率を低くする要因となります。 べてのデータ値の登場頻度が等しいと仮定 ータ値の登場頻度はあらかじめ求められて とくに短いデータ列を処理する場合には , します。たとえば , 各データ値が 1 回ずつ この固定長データのオーバヘッドにより , 登場している ( 登場回数 = 1 ) と仮定します。 Fig. 9 登場頻度の更新 かえってデータサイズを大きくしてしまう ですから , どんなデータ列が与えられたと (a) 初期の登場頻度 ことにもなりかねません。 しても , 始めの区間分割は Fig. & ( a ) のよ 登場回数 登場頻度 2 つ目の問題も , シーケンシャルなデー うに等間隔の区間で分割されます。そして , 1 タを処理する場合には問題となるでしよう。 データ列上の最初のデータ値によって , い 4 この場合 , データ列をすべて受け取るまで ずれかの区間を選択します。この点は静的 1 4 処理を開始できないため , 全データをいっ 算術符号化と同じです。次に , 処理したデ 1 たんバッフアなどに格納してから処理を行 ータ値の登場回数に 1 を加え , 登場頻度情 4 1 う必要があります。バッフアに格納するの 報を更新します。たとえば , 最初に登場し 4 も困難な非常に大規模なデータは , 静的符 たデータ値が '1' だった場合 , Fig. 9 のよう 号化では処理できないことになります ( 最 に 1 の登場回数を増やして登場頻度の更新 近のコンピュータ環境では , そのようなケ を行います。そして , 次のデータ値を処理 するときには , Fig. 8- (b) のように , 更新 ースは非常にまれでしようが , ストリー ング配信のようなデータ送信をする場合に された登場頻度を使用して区間分割を行い は問題になるかもしれません ) 。 これらの問題を解決するための方法とし このようにして , 登場頻度情報を更新し て , 「適応型」と呼ばれるものが考えられて ながら処理を続け , データ列をすべての処 います。算術符号化の場合は , 「適応型算 理が終了したときに選択されている区間が 術符号 (Adaptive ・ ithmetic encoding) 」と 元のデータ列を表す符号となります。適応 呼ばれる方法になります。なお , 適用型算 型算術符号化では , 処理が進むに従って区 術符号化は , 「静的算術符号」と対比して 間分割の割合が動的に変化します。いわば , 「動的算術符号 (Dynamic Arithmetic Encod 処理しているデータ列の登場頻度に「適応」 0 1 1 1 2 1 1 3 (b) ・ 1 ' を処理した後の登場頻度 登場回数 登場頻度 1 ー一 0 ワ」 LO 1 ー一 0 ー LO 0 1 2 1 2 1 3 1 画像処理を極めるアルゴリズムラボ 99

0 =. Ⅳ HEADLUNE ( 株 ) ユニバーサルオブジェクツ・ジャパン / Products ( 株 ) ユニバーサルオブジェクツ・ジャ パンは独自のレイアウト言語を装備した リポート開発 / 生成ツール「 UForms ( ユニ バーサルフォームズ ) 2.5 」を 23 , 880 円で 6 月 25 日よりダウンロード発売した。 のツールでは , テータベースなどから得 られたデータのレイアウトを ULL ( ユニ バーサルフォームズレイアウト言語 ) と 呼ばれる独自のプログラミング言語を用 いて定義し , HTML や XML, プリンタ , さまざまな画像フォーマットへ出力させ ることができる。 多彩な出力先 ほとんどのプログラムで「データを見 せる方法」がよく問題になる。ここ最近 の Web アプリケーションでは , i-mode な ど携帯端末の普及により , Web ページを 見る端末やソフトウェアの種類が多くな った。そのため , ある特定の端末ではレ イアウトが崩れたり , HTML の互換性が なく 1 つのファイルでは見られないとい ったことがよく起きる。それぞれの端末 に対応した Web ページを用意する方法で は , データ更新時に未更新の部分が残さ れるなどといった問題が発生しやすい。 どんな機器やソフトウェアからも表示 やドキュメント / 画像の位置が一定になっ たり , それに近くなるような工夫がほし くなるところだ。その 1 っとして中間言 語的なものを作り , そこにデータのレイ アウト情報を定義して自動的にデータを 出力するという考えは , 誰しも一度は思 い浮かぶはずだ。 U Forms ではそれを実 現してくれる。 UForms は ODBC/DAO/ADO に対応し , ◎ URL http:″www.universalobjects.co.jp/ UForms 2.5 を発売 これらの各データベースドライバを通じ てさまざまなテータベースからデータを 得ることができる。このときテータのや りとりには , ULL で記述したソースファ イル中に SQL 文を記述して行う。 出力データは , プリンタ , HTML/XML, GIF, JPEG, PDF, Micromedia Flash, CSV, バーコードなどに対応している。 Web ブラウザへは , UFo 「 ms の機能を 提供する CGI が用意されており , それを 通じてデータの表示が行える。 これらの定義を行う ULL は , 既存のプ ログラミング言語よりも柔軟性が高いと いわれる。 ULL を VisuaI C + + や VisuaI Ba sic などによって作られたプログラムから 呼び出すことができ , プログラムへ UFo 「 ms の機能を組み込むのも可能だ。 柔軟な出力方法と対応環境 UForms の特徴的な機能は , 出力イメ ージの , リサイズ , ズームイン / ズームア ウト / パン , 重ね合わせの各機能が装備 されているところだ。たとえば画面サイ ズが狭い端末で表示する場合 , UForms のほうで位置関係は保ったまま見やすく 自動的にコンテンツを再配置してくれ る。重ね合わせでは , べクトルデータと ビットマップテータを組み合わせること で , 拡大しても位置を示す線の太さは同 じなどといったことも簡単にできる。 UForms 自体は C + + で開発され , 特定 の OS に依存しないように作られている。 そのため , Windows/FreeBSD/Linux/Mac OS X / BeOS など非常に多くの環境で作 ったプログラムを動作させられる。今後 も多くの OS に対応することが可能だと UForms は同社の Web サイトのほか , http://www.vector.co.jp/soft/win95 /prog/sel 96352. htm ー より入手できる。この後 , 同社よりライ センスを購入することで正式に利用でき る。また , 8 月 1 7 日よりパッケージ版「 U Forms Designer 」が 39 , 800 円で一般店頭 でも販売される。 Web サイトでの動的な画像生成など , UForms が活躍する場面は多い。付録 CD- ROM には Windows で動作するデモ版が 収録されているので , ぜひ試してみてほ ( 霧島有香 ) 0 厂 rns ー Version2. 高パフォーマンスで低価 0 ◆異なる出からデタ取得ができる ◆多種な出力先へ同時に出力てきる ◆出力先に合わてリサイズできる リポート開発ツール 、パワフル 7 〃市川、 & リ E 加面、 .0 / 2 な 価格 UniversaI Objects 23 , 880 円 ( パッケージ版 : 39 , 800 問い合わせ先 MONTHLY HEADLINE 143 technical@universalobjects. CO. jp e-mail : FAX : 043-213-6735 TEL : 043-213-6703 ・ジャ / ヾン ( 株 ) ユニバーサルオブジェクツ

が悪くなってしまうことです。適応型算術 するように区間分割の方法を変えていくわ ほうが適しているケースがあるかもしれま 符号化で十分な圧縮効率を得るためには けです。 せん。 ある程度の量のデータ値を処理する必要カ : また , 算術符号化には特許が存在し , そ 復号する場合も考え方は同じです。符号 の使用には特許使用の許可 ( およびそれに 化のときと同様 , 初期状態では各データ値 あります。とはいえ , 静的算術符号化のよ 伴うパテント使用料 ) が必要だということ うに , 登場頻度情報など付加情報のための の登場頻度 ( 登場回数 ) がすべて等しいも にも注意が必要です。 のとして処理を開始します。したがって , オーバヘッドによって元のデータサイズよ ハフマン符号化にしても , 算術符号化に りも大きくなるようなリスクはないといっ 1 つ目のデータの復号処理では , 等間隔に しても , 画像圧縮という目的からすると , 区切られた区間の中で算術符号化されたデ ていいでしよう。 あまり圧縮率の高い方法とはいえません。 以上のように , 適応型算術符号化は , 計 ータがどこに位置するかを調べ , その区間 画像の場合 , 登場頻度以外にも統計的な偏 が示すデータ値を最初のデータ値として出 算量を静的算術符号化と同程度に抑えたま りが存在することが多いため , 登場頻度の 力します。そして , 求められたデータ値の まで圧縮後のデータに付加されるオーバへ みを利用しているこれらの符号化では , 圧 ッドをなくすことができるなど , 静的符号 登場回数を 1 増やし , この回数をもとに登 場頻度情報を更新します。次のデータを復 化の欠点を解消することができる有用なア 縮するにも限界があるのです。そのため , ハフマン符号化 , 算術符号化ともに単体で 合する際の区間分割は , この更新された登 ルゴリズムといえます。 利用されることは少なく , ほかの圧縮法と 場頻度情報に従って行います。以降 , 同様 組み合わせて利用されることが多くなりま に算術符号化されたデータが新たに分割さ まとめ す。こうすることにより , より高い圧縮率 れた区間の中でどこに位置するかを調べて , データの出力と登場頻度情報の更新をすべ 今回はハフマン符号化と同じく , データ を得ることができるのと , もともとこれら の符号化法がほかの圧縮法と組み合わせや の登場頻度を利用した圧縮アルゴリズムと てのデータ値が復号できるまで繰り返しま すいということからさまざまなところで利 して , 算術符号化を紹介しました。算術符 す。 号化は , ハフマン符号化と同様 , 可逆圧縮 用されています。 なお , 静的符号化と同様に適用型算術符 さて , 今回 , データの登場頻度に注目し の 1 つで画像データの圧縮だけではなく , 号化においても , 符号化されたデータだけ ほかのさまざまなデータの圧縮処理に適用 て符号化を行うアルゴリズムとして Elias では処理の終了地点を知ることができませ 符号化と算術符号化を紹介し , さらに算術 ん。したがって , 符号化したデータ列には できます。 符号化のパフォーマンスを高める手法とし また , 算術符号化は「データ列全体を 1 つ 必ず元のデータの大きさを示す情報を付随 て適応型算術符号化を解説しました。実は , の数値で表現する」という考え方で符号化 させておく必要があります。 最後に解説した適応型符号化は , 算術符号 を行うため , データ値 1 つ 1 つに符号を割り 以上のように適応型算術符号化では , 符 化にのみ適用できる特殊な手法ではなく , 当てるハフマン符号化に比べて , 最小符号 号化処理に際して , 最初にデータ列全体の 前回紹介したハフマン符号化についても適 登場頻度を求めるためにデータ列全体を走 化長に近づけやすくなるという特徴があり ます。実際 , 多くの場合 , 算術符号化のほ 応型は存在します。次回はこの適応型ハフ 査することも , 復号化用の登場頻度情報を うがハフマン符号よりも高い圧縮率を実現 マン符号化を取り上げたいと思います。 己録しておくことも不要です。つまり , 前 なお , 本連載で利用している Pmacs およ 述した静的符号化における 2 つの問題点を できます。 逆に , 算術符号化の欠点は , データ全体 び Pmacs プラグインに関する情報は , クリアしているといえます。また , 適応型 に符号を割り当てるようにしているため , 算術符号化処理は , 静的符号化と比べても http://www.asahi-net.0「.jprgv9k-setg 何らかの原因でデータが欠落してしまった 計算量の増加がわずかで済むことも重要で http://www.asahi-net.or.jprgv9k-setg/ 場合 , 元データの損失範囲が大きくなって す。増加する部分は登場頻度の更新ですが , mado. html などを参照してください。 実装上では足し算が 1 つ追加するだけで対 しまうことがあげられます。ハフマン符号 本連載に関するご意見 , ご質問は , 応できるので , 計算量の増加は無視できる 化ではデータの一部が損失しても , その損 失は局所的なものにとどまりますが , 算術 範囲でしよう。 gv9k-setg@asahi-net.0「.jp 適応型算術符号化の欠点は , 初期状態で 符号では最悪の場合元のデータ全体が損な までお願いします。また , 画像に関する M L を立ち上げました。興味のある方は上記 すべてのデータ値の登場頻度が等しいとい われてしまう可能性があるのです。ですか の Web サイトに案内があるので参照してく う本来の登場頻度とはかけ離れた状態から ら , 送受信工ラーなどが発生しやすいネッ 処理を始めるため , 始めのうちは圧縮効率 トワーク上での通信にはハフマン符号化の ださい。 1 三ロ、 100 C MAGMINE 2001 9

うな代入の結果は , ANSI においても未定 義な部分や , 事細かに定義されている部分 があり一言では説明しきれません。異なる 型の代入は , 2001 年 4 月号で解説した有効 範囲内で行われるように心がけましよう。 ◆演算時 演算時には演算式中で使用されているデ ータ型の中で , もっとも上位のデータ型へ すべての対象データが変換されます。また , 演算の結果が代入される際には代入時の自 動型変換のルールが適応されます。 ◆関数の引数引き渡し時 関数を呼び出し , 引数を引き渡す際にも 自動型変換が発生します。その際引き渡し たデータ ( 実引数 ) は , 関数内で受け取った 引数 ( 仮引数 ) のデータ型へ変換されます。 この場合 , プロトタイプ宣言があらかじめ 行われていることが前提となります。 強制型変換 ( キャスト ) 自動変換が行われるとき以外にも , プロ グラマが任意で型変換を行いたい場合があ ります。これを強制型変換 ( キャスト ) とい います。たとえば , 異なるデータ型同士で 値を比べたい場合 ( 値の評価 ) に , 一時的に データ型をそろえて行います。また , 整数 型変数同士の除算の結果が実数になること が考えられます。その結果を正しく変数に 代入したい場合にも , この方法を使用しま す。 ◆キャストの書式 ( データ型 ) 式 たとえば , 小数点以下の切り捨て処理を 行いたい場合 創 oat f—a, f-b; f—a = 1982.99 % f—b = ( int ) f—a; とすると , f ー b には 1982 という数値が代入 され , 小数点以下の値を切り捨てることが できます。この例では f. ー a は変数ですが , こ こに演算式などを指定することも可能です。 その場合 , 式の計算結果がキャストされて , 左項の変数に代入されます。 前回のコラム ( 8 月号豆 Column1 ) で void 型 の変数は存在できないが , void * 型のポイ 48 C MAGAZINE 2 1 9 ンタ変数なら存在できることを解説しまし た。 void * 型とは , とにかく型は問わない が何らかのアドレスであるといった定義に なります。この void * 型の変数は , アドレ スにより指し示される先のデータ長が決定 できないため , 代入や演算を行うことがで きません。そのためこのキャスト演算子に より , ほかの型に変換して利用します。 pedef : データ型の再定義 呼 pedef というデータ型を再定義する命 令を紹介します。この命令は , あるデータ 型名に新しく別の名前 ( 同義語 ) を付けるこ とができる機能を持ちます。この機能を使 用することにより , 変数の宣言でよりわか りやすい名前を付けることができ , より見 やすいプログラムを組むことができます。 ◆ typedef の書式 typedef 既存のデータ型 新しいデータ型名 [ 同義語 ] ; pedef の使用例を以下に示します。 typedef int FLAG ー FLAG il, 土 まずデータ型 int に FLAG という新しい名 前を付けます。そして実際の変数の宣言で は int 型を宣言する代わりに , FLAG という 型で宣言します。 typedef の宣言は , 実際 に変数を定義する前で行わなければなりま せん。このようにすることで , 変数 il , i2 がフラグとして利用されることが一目でわ かります。ほかにも Fig. 1 のような使用方 法があります。 pedef は配列や構造体 , および関数ポイ ンタと呼ばれる変数の再定義で力を発揮し ますが , 現段階では以上の内容をよく理解 しておくことがまずは大事です。 変数のスコープと記憶クラス では , 関数の説明に戻ります。今回は関 数間での変数の適応範囲について説明しま す。まず変数の適応範囲を大きく分類し , さらに詳細をまとめていきます。 Fig. 1 typedef の使用例 typedef unsigned char BYTE; BYTE bitdata; typedef long * PLONG; PLONG pLong, 〃 BYTE は unsigned char と同義語 ″ bitdata は unsigned char 型 ″ PLONG は long * と同義語 ″ pLong は long 型のポインタ変数 豆 COIumn 1 typedef と #define typedef と同様にデータ型に別の名前を 定義するために , # define というプリプロセ ッサの機能を利用することもできます。 ty pedef の例を , #define を使って書き換えて みると以下のようになります。 #inc lude く s し d 土 0. #define FLAG int void main ( ) 上記の例では . FLAG という文字列がす べて int に置き換えられた後にコンパイル され , typedef を利用した場合と同様の結果 FLAG il, 土 となります。ただ厳密に両者の間には次の ような違いがあります。 # deifne " ・コンバイルの前にプリプロ セッサにより , 文字列として単純 に置き換えられるだけ typedef ・ " コンバイラにより構文的に 解釈される # define は第 1 文字列を第 2 文字列に置き 換えるだけなので、 Fig. 1 で示したような u nsigned cha 「の場合にすでに unsigned cha 「で 2 つの文字列になるため , typedef のよ うに文字列 BYTE に置き換えたりすること はできず , コンパイルエラーとなります。 # define の詳細については , プリプロセッ サの回に解説します。

選択した区間をさらに P ( 0 ) , P ( 1 ) の割合 で分割し , 同様の作業を行います。 たとえば , 始めのデータ値が 0 であれば , 0 ~ P ( 0 ) の区間を選択しますが , 2 番目の データについては , この 0 ~ P ( 0 ) を同じよ うに 2 分割し , データ値によってどちらの 区間を選択するかを決めます。このように して , データ列上の値によって区間の分割 と選択を繰り返し , 最終的にデータ列がな くなったときに選択された区間がそのデー タ列全体を表す情報となります。 例として , データ列が ( 0 , 1 , 1 ) となる 場合の区間の求め方を Fig. 2 に示します。 このデータ列の場合 , P ( 0 ) = 1 / 3 , P ( 1 ) = 2 / 3 なので , これを用いて区間を分割して , 最 終的に 5 / 27 ~ 1 / 3 の区間がデータ列全体を 表現する区間となります。最終的に出力す る結果としては , 区間内に存在する値なら どの数値でもかまいませんが , 普通はデー タ量を少なくするために , もっとも桁数の 少ない数を選んで出力します。 この数値から元の符号列を復元する場合 にも , 符号化に使用した Fig. 1 の区間を考 えます。先ほどの Fig. 2 の結果を復号する 例として , 結果の区間に含まれる適当な値 である 1 / 4 という数字から元のデータ列を 復元してみます。なお , この 1 / 4 という数 値には , 5 / 27 ~ 1 / 3 に含まれるという以外 に特別な意味はありません。 まず , 元のデータ列のデータ登場頻度 P ( 0 ) = 1 / 3 , P ( 1 ) = 2 / 3 に従って区間を Fig. 3 の ように分割します。このとき , 数値 1 / 4 は 区間の左側にあるので , データ列の始めは 0 であることがわかります。次に , 左の区 間を同様に分割します。すると , 数値 1 / 4 は , 分割した区間の右側にあるので , 2 番 目のデータ値は 1 であることがわかります。 以下 , 同様の処理を繰り返していくと , 最 終的に元のデータ列 ( 0 , 1 , 1 ) が求められ ます。 多値データの場合 多値のデータ列を扱う場合も 2 値のデー 96 C MAGAZINE 2 冊 1 9 タ列の処理と考え方は同じです。この場合 は , 分割する区間が多くなるだけです。た とえば , 4 値 ( 0 , 1 , 2 , 3 ) のデータ列の場 合は , Fig. 4 のように区間を分割します。 こでは問題を一般化して , N 値データを 用いた場合の区間計算法を考えましよう。 こで , データ値 x の出現確率を P ( x ) と表 します。 まず , 初期状態では , 0 ~ 1 の区間を分割 することになりますが , この場合 , 各区間 の境界は Fig. 5 のように , それ以下のデー タ値の出現確率 P の総和となります。です Fig. 1 E ⅱ as 符号化で使用す区間 " ( a ) 元の区間 0 0 Fig. 2 0 ( b ) データの登場頻度による分割 P ( 0 ) データ列 ( 0 , 1 , 1 ) を E ⅱ as 符号化する様子 から , データ値 x が現れた場合 , 選択すべ き区間は Fig. 6- ( 式 1 ) のようになります ( な お , 式中の x には特別な意味はありません ) 。 以下 , この区間に対して分割を行っていく わけですが , この区間の最小値と最大値を それぞれんⅣ , 力な力とした場合 , この区間 を分割すると , Fig. 6- ( 式 2 ) のようになりま す。この式 2 より , 新たな区間が求められ ます。このときの最小値 , 最大値を新たな んⅣ , ん g 方として更新します。すなわち , Fig. 6- ( 式 3 ) のようになります。以下 , 現れ るデータ値に従って , この式 3 を適用して 1 1 P ( 1 ) (a) データの出現頻度に従って全体を 1 : 2 に分割し , 処理中のデータ値℃ " に該当する前半を選択 3 1 (c) 選択された領域をさらに 1 : 2 に分割し処理中のデータ値。ドに該当する後半を選択 3 1 (b) 選択された領域をさらに 1 : 2 に分割し , 処理中のデータ値 -1 " に該当する後半を選択 3 1 0 の 1 1 の区間 2 1 0 9 00 の区間 1 01 区尸 2 1 1 1 1 27 9 5 0 1 000 の区間 2 求めるデータ列 ( 0 , 1 , を表す区間 ※最終的に選択された領域内の値であれば , どの値を結果としてもかまわない ( 上記の例では 1 / 4 , 1 / 5 など )

000 最新システム開発技法 もありません。 1 件の検索なら問題ありま しておき , データを取得するときは , 複数 XML データベースエンジンでの せんが , 複数件の検索になるとその件数だ のデータベースに並列に接続してデータを 並列処理の必要性 け検索時間がかかり , 実際システムとして 取得します。データ量が増えて接続するマ 前述している XML データベースエンジン は , パフォーマンスの低いものとなってし シンの台数が増加したとき , これを逐次処 まいます。 YggdrasilI には , そのオプションツールとし 理していくと増加したマシンの台数に比例 て P a Ⅱ em001 ( パラレルツール ) があります そこでこうした問題を解決する方法とし して処理時間も増加します。しかし , 並列 ( 34 ページコラム参照 ) 。 ParallelTool は検索 処理を用いれば , マシンが何台増加しよう て , 並列処理があります。並列処理とは , が処理時間は変わらず , しかも安全に処理 プログラミングで処理を実行するとき , 1 を高速に行えるツールなのですが , 名前の つの CPU で行わず , 複数の CPU で並列に実 とおり並列に検索を行うものです。 することができます。 行することです。 Yggdrasill に ParallelT001 が用意されてい ではなぜ YggdrasiIl のような XML データ では並列処理を行うデータベース設計は , べースに並列処理が必要なのでしようか。 るのは , これが XML データベースエンジン どのようなシステムになるのでしよう。 Fig. RDB などでもそうですが , 大量のデータ だからです。前述のように XML は自由にタ 9 - ( a ) の例でいうと , 本社がサーバで各支店 を検索する場合 , データ量の増加に従って グを設定できます。 RDB で並列処理を行う がクライアントという概念が必要ありませ 処理時間は増加します。一般的にどのよう 場合 , 複数のデータベースからデータを取 得し , ワークテープルを作成してそのテー ん。 なシステムでも運用するのに従ってデータ 検索などを行う場合 , 並列に行うことに 量は増加していきます。そのため処理時間 プルにインサートするという処理が発生し よって処理時間が短縮でき , しかも整合性 ます。つまり RDB では検索結果の型を合わ もシステムの運用にともなって遅くなって のとれたデータが取得できます (Fig. 9-(b))0 せていなければなりません。取得したいデ いくのが通例です。 ータがバラバラの場合 , RDB では処理が不 たとえばサーバにトラブルが発生したとし Yggdrasill ではこれらを解消するために Pa ても , システム自体はストップせず処理を r e 001 が提供されています。データを登 可能なのです。しかし , Yggdrasill のような 行えます。 録する場合 , 複数のマシンに分散して登録 XML データベースエンジンは , たとえデー タがバラバラであっても検索結果をフラグ メントで取得し , 1 つにまとめることによ って簡単に並列処理を行えます。 並列処理 (parallel processing) について 並列処理は , プログラミングで処理を実 行するとき 1 つの CPU で行わず , 複数の CP U で並列に実行します。処理を分散して行 うことによって CPUI つあたりの処理が少 なくなり , そのぶん処理時間が短縮されま す。一般的には並列処理は , 難しい分野だ といわれていて , 逐次プログラムを組むほ うが簡単なケースも多くあります。 次に並列処理を構築するうえで必要にな るプログラミング上の概念を解説します。 スレッド (thread) マルチスレッド OS でプログラムを実行す るときの単位です。プログラムがデータを 読み書きしたり , メモリの値を参照するな ど実行していく過程 ( 道筋 ) をスレッドと呼 びます。 特集 2 最新システム開発技法 XML データベース + web アプリケーション Fig. 9 データの検索を行う例 ( a ) 本店にサーバを置くと各支店から検索要 ( b ) 並列処理を行うことでサーバとクライア 求が集まり , タイムラグなどにより別の ントの概念がなくなり , 問題が起きにく 支店のデータが正しく読み取れないこと くなる がある 本店 本店 支店 A 支店 C 支店 C 支店 B 支店 A 支店 B 31

刃リラボ 第 24 回 画像処理を極める 画像圧縮アルゴリズム③ E ⅱ as 符号化と算術符号化 昌達 K'z データの出現頻度に注目して符号化す によらず 1 ビットにまで圧縮可能にな ることで圧縮を試みる手法の 1 っとし ります。今回は , この E ⅱ as 符号化の て , E ⅱ as 符号化があります。これは , アルゴリズムを紹介するとともに , 日 データ列全体をまとめて符号化する考 ias 符号化を計算機上で処理可能な幵 え方で , 白紙の画像などはその大きさ 式に調整した算術符号化を解説します う際に各データ値の登場頻度が与えられて 計算機上では実現することが困難です [ 注 1 ] 。 いる場合は , 符号化によって圧縮できる最 しかし , E ⅱ as 符号化は理論的な考え方を元 はじめに 小値は理論的に求めることが可能で , それ にしたストレートな処理なので , どのよう 今回も前回に引き続き , 画像圧縮アルゴ を最小符号長といいます。しかし , ハフマ な方法で圧縮するのかを把握するためには , リズムを紹介します。画像に限らず , 可逆 ン符号化ではなかなか理論値としての最小 まずこちらから学ぶほうが近道だと思いま 的にデータ圧縮を行うためには , 元データ 符号長に近い結果を得ることはできませ す。 [ 注 1 ] 逆にいえば , 算術符号化は E ⅱ as 符号化 に何かしらの統計的特徴があることが必須 ん。それは , 理論的には各データ値に実数 をプログラムとして実装したものということ です。 ビット長の符号を割り当てなければならな もできます 前回は「データ中の各値の登場頻度に偏 いところを , ハフマン符号化を用いた実処 2 値データの場合 りがある」という統計的特徴のあるデータ 理では整数長のビットを割り当てなければ の圧縮アルゴリズムとして , シャノン・フ ならないからです。これを改善するために それではまず , データ値が 0 と 1 の 2 つし アノ符号化とハフマン符号化を紹介しまし 2 バイトごとに符号を割り当てるようにす かない 2 値データを扱う場合の Elias 符号化 た。ハフマン符号化は , 各データの登場頻 るなど , 元データをより大きい単位でまと を考えます。 度に応じて長さの違う符号を割り当てる方 めて符号化する方法が考えられますが まず , データ値 0 の登場頻度を P ( 0 ) , 1 法で , 登場頻度の高いデータ値には短い符 れにも限界があります。 の登場頻度を P ( 1 ) と表すことにします。 号を , 登場頻度の低いデータ値には長い符 これに対して , 算術符号化ではデータ全 これらの値は処理を始める前にあらかじめ 号を割り当てることにより , 全体としての 体に 1 つの符号を割り当てようとするので , 圧縮したいデータ列全体を調べて , 求めて データ量を少なくします。 ハフマン符号化よりも , 最小符号長に近づ おく必要があります。 今回紹介する「算術符号化 (Arithmetic en けることが期待できます。 EIias 符号化では , Fig. 1- ( a ) のような 0 ~ coding) 」もハフマン符号化と同じく , 「デ 以下 , 算術符号化の基本的な考え方と実 1 の区間を用います。この区間をまず , デ ータ列中の値の登場頻度に偏りがある」と ータ値の登場頻度 P ( 0 ) , P ( 1 ) の割合に合わ 装例を示します。 いう統計的特徴を利用する符号化法です。 せて Fig. 1- ( b ) に示すように分割します。 算術符号化がハフマン符号化と大きく異な そして , データ列上の値によって , どちら EIias 符号化 かの区間を選択します。データ列上のデー るのは , ハフマン符号化ではデータ値それ タ値が 0 であれば , 0 ~ P ( 0 ) の区間を採用 算術符号化の考え方を理解しやすくする ぞれに対して符号を割り当てるのに対し ために , まず " E ⅱ as 符号化 " と呼ばれている し , 1 であれば P ( 0 ) ~ 1 の区間を採用しま て , 算術符号化ではデータ全体を 1 つの符 号として表現する点です。 手法を紹介します。 Elias 符号化は , 方法的 す。 には算術符号化とまったく同じものですが , データ列上に次のデータ値がある場合は , データの登場頻度に注目して符号化を行 画像処理を極めるアルゴリズムラボ 95