JPH07111699B2 - データ転送符号化方法およびその装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データ転送装置におけ
る符号化方法およびその装置に関するものである。

【０００２】

【従来の技術】近年、通信網を介したデータ通信によっ
て、計算機のメモリ上のデータをポインタによる参照関
係を保ちながら転送することが行なわれるようになって
きた。このとき、転送されるデータ列の生成方法は、例
えば文献１「抽象データ型のための値転送方式」、ハー
リィ，リスコフ著、エーシーエム・トランザクションズ
・オン・プログラミング・ランゲージズ・アンド・シス
テム、第４巻、第４冊、１９８２年、ｐｐ５２７−５５
１（M.Herlihy,B.Liskov, “A Value Transmission Met
hod for Abstract Data Types ”,ACM Transactions on
Programming Languages and Systems,Vol.4,No.4,Octo
ber 1982,pp527-551) に記載された例が知られている。

【０００３】図４は上記方式におけるデータ転送装置の
データを符号化する部分の構成を示すものである。図４
において、４０１は転送するデータを記憶する記憶部、
４０２は転送されるデータ、４０３はデータ４０２の中
にあるポインタによって指されているデータ、４０４は
データ４０２およびデータ４０３の中にあるポインタに
よって指されているデータ、４０５はデータを符号化す
る符号化部、４０６は符号化部４０５がデータを符号化
する際に必要な情報を記憶しておくための符号化情報
表、４０７は符号化済みのデータを記憶しておくための
記憶部である。

【０００４】転送データを記憶する記憶部４０１は、通
常の計算機における主記憶装置に相当する。主記憶装置
上でのデータの位置は、通常、アドレスとして示され
る。符号化済みデータを記憶する記憶部４０７の中に記
憶されたデータはデータ通信部によって他の計算機に転
送され、転送されたデータは、復号化部によって復号化
され、主記憶装置上のデータとなる。

【０００５】このように記憶部４０７上のデータは、デ
ータ通信部によって他の計算機に転送されるので、記憶
部４０７上での絶対位置によってデータ間の参照関係を
表現しても、その参照関係は、データを受け取った計算
機では、解釈することが不可能になる。したがって、記
憶部４０７上では、データの参照を示すためには、絶対
位置を表わすアドレスではなく、記憶部４０７の記憶空
間の先頭からの相対位置を示す値を使用する。この相対
位置を示す値をオフセットと呼ぶ。

【０００６】以上のように構成されたデータ転送装置に
ついて、以下その動作について説明する。なお、図４の
データ４０２、データ４０３、データ４０４において、
矢印が出ている領域は、ポインタが入っていることを表
わす。また斜めの線が書いてある領域は、ポインタを入
れることのできる領域であるが、そこにはなにもデータ
が入っていないことを示す。

【０００７】符号化部４０５に対して、データ４０２の
符号化の要求があったとする。このとき、最初に符号化
部４０５は、符号化情報表４０６を検索し、それ以前に
データ４０２が符号化されていないことを確認する。次
に、符号化部４０５は、データ４０２の記憶部４０１の
中での位置を示すアドレスと、記憶部４０７上での相対
位置を示す値すなわちオフセットを符号化情報表４０６
に格納する。

【０００８】次に符号化部４０５は、データ４０２の中
にポインタが含まれているので、そのポインタを符号化
する。この場合、ポインタはデータ４０４を指している
ので、このポインタの符号化の際にも、符号化部４０５
は符号化情報表４０６を検索し、データ４０４がすでに
符号化されていないことを確認する。

【０００９】その後、符号化部４０５は、データ４０４
を符号化し、符号化されたデータ４０４を記憶部４０７
に記憶する。

【００１０】次に符号化部４０５は、データ４０２の中
に、もう一つのポインタが含まれていることを確認し、
そのポインタを符号化しようとする。この例では、その
ポインタはデータ４０３を指している。このポインタを
符号化する際にも、符号化部４０５は符号化情報表４０
６を検索し、データ４０３がすでに符号化されていない
ことを確認する。次に、符号化部４０５は、符号化情報
表４０６にデータ４０３のアドレスと、記憶部４０７上
での位置を格納する。さらに、符号化部４０５は、デー
タ４０３の中にポインタが含まれていることを確認し、
そのポインタの符号化を開始する。この例では、そのポ
インタはデータ４０４を指している。

【００１１】符号化部４０５は、そのポインタが指すデ
ータ４０４がすでに符号化されているかどうかを符号化
情報表４０６を検索して調べる。この例では、すでにデ
ータ４０４は符号化情報表４０６に格納されているの
で、データ４０４はすでに符号化済みであることがわか
る。そこで、符号化部４０５は、データ４０４を符号化
し、記憶部４０７に格納する。

【００１２】その後、符号化部４０５は、データ４０３
の残りの部分を符号化し、記憶部４０７に格納する。次
に、符号化部４０５は、データ４０２の残りの部分を符
号化し、記憶部４０７に格納し、全データの符号化を終
了する。

【００１３】記憶部４０７に格納された符号化済みのデ
ータは、データ通信部によって他の計算機に転送され
て、その計算機上で復号化される。

【００１４】このように、従来のデータ転送装置におい
ても、１つのデータを参照するポインタが複数個あった
場合でも、その参照関係を保持したままデータ群を符号
化し、転送し、復号化することができる。

【００１５】

【発明が解決しようとする課題】しかしながら、上記の
従来の装置では、１つのデータを符号化するたびに符号
化情報表を検索しなければならず、また、検索の結果、
まだ符号化されていないデータであった場合には、符号
化情報表にその位置情報を格納する必要があり、符号化
するデータの数が大きくなったとき、符号化情報表の検
索、符号化情報表への情報の格納に時間がかかり、符号
化のオーバーヘッドが大きいという問題を有していた。

【００１６】本発明は、このような従来の問題を解決す
るものであり、符号化情報表の検索および符号化情報表
への情報の格納の動作を省き、ポインタでつながれたデ
ータ構造を高速に符号化することのできるデータ転送符
号化方法およびその装置を提供することを目的とする。

【００１７】

【課題を解決するための手段】上記目的を達成するため
に、本発明によるデータ転送符号化方法は、ユーザから
与えられたデータ構造に、データの符号化の際に使用す
る符号化済み情報と、符号化されたときの記憶部の未使
用空間の先頭のからの相対位置情報とを格納する領域を
設け、これらの情報を利用して符号化するようにしたも
のである。

【００１８】また、本発明によるデータ転送符号化装置
は、符号化データされたデータを記憶空間の先頭から格
納し、未使用空間の先頭の位置を問い合わせられたとき
にはその位置を答えとして返す記憶部と、ユーザから与
えられたデータ構造に対して符号化の際に使用する符号
化情報記憶領域を付加したデータ構造を生成するデータ
構造生成部と、その付加した領域の情報を利用してデー
タ符号化する符号化部とを備えたものである。

【００１９】

【作用】本発明は、上記構成によって、ポインタによっ
て参照関係が表わされている複数のデータを、その参照
関係を保ったまま符号化し転送する場合、符号化するデ
ータごとに符号化情報表の検索や符号化情報表への格納
をすることなく、高速に符号化を行なうことができると
いう効果を有する。

【００２０】

【実施例】以下、本発明の実施例について、図面を参照
しながら説明する。図１は本発明の一実施例におけるデ
ータ転送符号化装置の構成を示すブロック図である。図
１において、１０１はユーザが設定したデータ構造表
現、１０２はデータ構造生成部、１０３はデータ構造生
成部１０２によって生成されたデータ構造表現、１０４
は転送するデータを記憶する記憶部、１０５は転送され
るデータ、１０６はデータ１０５の中にあるポインタに
よって指されているデータ、１０７はデータ１０５およ
びデータ１０６の中にあるポインタによって指されてい
るデータ、１０８はデータを符号化する符号化部、１０
９は符号化されたデータを記憶しておくための記憶部で
ある。データ構造生成部１０２によって生成されたデー
タ構造表現１０３の中のＡは、そのデータがすでに符号
化済みか否かを示す値を格納するための記憶領域、Ｂは
そのデータが記憶部１０９に格納されているときの記憶
部１０９上での先頭からの相対位置すなわちオフセット
を格納する記憶領域である。

【００２１】本実施例における重要な構成要素は、デー
タ構造生成部１０２と、符号化部１０８に分けられる。
まず最初に、図２に示すブロック図を用いて、データ構
造生成部１０２の内部構成と、データ構造表現１０１と
データ構造表現１０３の内容例について説明する。

【００２２】図２において、２０１はデータ構造表現１
０１を読み込み、表現されているデータ構造を解析する
データ構造表現解析手段、２０２はデータ構造表現解析
手段２０１が解析した結果を記憶しておくためのデータ
構造記憶手段、２０３はデータ構造記憶手段２０２に記
憶されているデータ構造に対して、符号化のときに用い
る符号化情報記憶領域Ａ，Ｂを付け加えるための符号化
用記憶領域追加手段、２０４は符号化用記憶領域追加手
段２０３によって符号化情報記憶領域を追加されたデー
タ構造を記憶しておくためのデータ構造記憶手段、２０
５はデータ構造記憶手段２０４に記憶されているデータ
構造を読み取り、プログラミング言語によるデータ構造
の表現を生成するデータ構造表現生成手段である。２０
６はデータ構造表現１０１を読み込んだときに、データ
構造記憶手段２０２上に記憶されるデータ構造、２０７
はデータ構造表現１０１に符号化情報記憶領域を追加し
たときに、データ構造記憶手段２０４上に記憶されるデ
ータ構造である。

【００２３】次に、データ構造生成部１０２の動作につ
いて説明する。まず、データ構造表現解析手段２０１
は、ユーザによって作成されたデータ構造表現１０１を
読み込み解析する。図２に示した例では、データ構造表
現１０１はＣ言語を用いて表現されている。これは、他
のプログラミング言語、例えばパスカル言語などを用い
てもよい。データ構造表現１０１を読み込んだデータ構
造表現解析手段２０１は、表現されているデータ構造を
解析して、計算機の主記憶上で使用しやすいデータ構造
２０６にして、データ構造記憶手段２０２に格納する。
なお、プログラミング言語で記述されたプログラムを読
み込み、それを主記憶上のデータ構造、たとえばツリー
構造などに変換する方法は、一般的なコンパイラの技術
と同様である。また、プログラミング言語で記述された
プログラムの解析方法および解析した結果の主記憶上で
の表現方法については、たとえば文献２「プログラミン
グ言語処理系」、佐々政孝著、岩波書店、１９８９年、
に詳しく説明されている。

【００２４】データ構造記憶手段２０２上に格納された
データ構造２０６は、ここでは説明を簡単にするため
に、データ構造表現１０１によって示されたデータ構造
の名前と、そのデータ構造の各要素を表わすリストを用
いて表わすこととする。この場合、データ構造表現１０
１に示したデータ構造は、２つのポインタと１つの整数
から成るので、データ構造を示すリストも３つの要素を
持つ。

【００２５】次に、符号化用記憶領域追加手段２０３
は、データ構造記憶手段２０２上にあるデータ構造２０
６に対して、データの符号化の際に、そのデータがすで
に符号化されているか否かを示すフラグを格納する領域
Ａと、すでに格納されている場合には、記憶部１０９上
で符号化されたデータがどの位置に置かれるかを示す値
であるオフセットを格納する領域Ｂの２つの領域をつけ
加えたデータ構造２０７を作り、データ構造記憶手段２
０４に格納する。

【００２６】データ構造２０７は、データ構造２０６に
これらの２つの記憶領域Ａ，Ｂを付加したデータ構造で
あるので、データ構造２０６では、データ構造を示すた
めのリストは３つの要素を持っているのに対し、データ
構造２０７では、記憶領域Ａ，Ｂが符号化用記憶領域追
加手段２０３によって加えられて、リストの要素が５つ
になっている。

【００２７】その後、データ構造表現生成手段２０５
は、データ構造２０７を読み込み、データ構造表現１０
３を生成する。この場合は、最初にＣ言語の構造体を示
す予約後「ｓｔｒｕｃｔ」を出力し、その次にデータ構
造名「ｎｏｄｅ」を出力し、その次にデータ構造を示す
部分の始まりを示す「｛」を出力し、さらにデータ構造
２０７の中のデータ構造を示すリストに格納されている
文字列を先頭から順に出力する。次いでデータ構造を示
す部分の終わりを示す「｝；」を出力する。

【００２８】以上のようにして、データ構造表現１０１
からデータ構造表現１０３を生成することができる。

【００２９】このデータ転送装置を使うユーザは、デー
タ構造表現１０３を含んだプログラムを作成する。ユー
ザが必要とする領域は、記憶領域ＡおよびＢを除く３つ
の領域であり、記憶領域ＡおよびＢはユーザは使用しな
い。ユーザが作成したプログラムが生成したデータは、
記憶部１０４に格納される。

【００３０】次に、記憶部１０４に格納されたデータを
転送するために、符号化部１０８におけるデータの符号
化について説明する。ここでは、転送するデータは、す
べてデータ構造表現１０３によって表現されたデータ構
造を持つものとし、図１の例ではデータ１０５を転送す
る場合について説明する。データ１０５の中には、デー
タ１０６とデータ１０７を指すポインタが含まれてお
り、データ１０６の中にもデータ１０７を指すポインタ
が含まれている。このデータ転送装置では、これらの、
ポインタによって参照されているデータを、参照関係を
保ったまま転送する。また、符号化を開始する前に、転
送されるデータの中の記憶領域Ａには、すべて０を入れ
て初期化しておき、そのデータが、まだ符号化されてい
ないことを示しておく。

【００３１】次に、図３に示すフローチャートを用い
て、符号化部１０８が、符号化の要求を受けて符号化を
開始する動作について説明する。符号化の要求を受ける
ときには、同時に符号化を行なうデータを指すポインタ
も受け取る。まず、符号化部１０８は、符号化の要求を
受けたときに与えられたポインタの指すデータの中の符
号化済みか否かを示す領域である記憶領域Ａを調べる
（ステップ３０１）。ここでは、すでに符号化されてい
るデータの場合は記憶領域Ａに１が、まだ符号化されて
いない場合には０が入れられているものとする。もし、
すでに符号化が行なわれていれば、ポインタの指すデー
タのオフセットを格納する領域である記憶領域Ｂからオ
フセットを取り出し、その値を符号化して記憶部１０９
に書き込み、実行を終了する（ステップ３０２）。

【００３２】記憶部１０９は、有限かつ１次元の記憶空
間を持っており、データ転送装置が転送するデータの符
号化を開始する前に初期化され、記憶空間全体が使用さ
れていない状態になる。この記憶部１０９は、データの
格納を要求されたときには、そのデータを使用されてい
ない記憶空間の中の先頭に入れ、データを格納した時に
は、格納したデータの大きさ分だけ使用されていない空
間が小さくなる。したがって、記憶部１０９の使用され
ていない空間の先頭の位置は、そのデータの大きさ分だ
け記憶空間の先頭から最後の方向へ移動する。また、記
憶部１０９は、通常の単純な記憶部と違って、使用され
ていない記憶空間の先頭の位置への問い合わせを受けた
ときには、使用されていない空間の先頭の位置を、記憶
空間の先頭からのオフセットとして表わす値を返す機能
を持つ。

【００３３】もし、符号化部１０８が受け取ったポイン
タが指すデータが、まだ符号化されていない０の場合
は、記憶領域Ａに１を入れ、その時点で記憶部１０９に
データを格納した場合に、そのデータ格納される場所の
オフセットを記憶部１０９に尋ね、その答えを記憶領域
Ｂに格納する（ステップ３０３）。

【００３４】次に、符号化部１０８は、そのデータのす
べての要素を符号化したか否かを調べる（ステップ３０
４）。否の場合は、ポインタが指すデータの要素すべて
を１つずつ取り出して（ステップ３０５）、それぞれの
要素に対しての処理を行なう。すべての要素についての
処理が終わっている場合は、符号化部１０８全体の処理
を終了する。

【００３５】それぞれの要素に対する処理は、次のよう
なことを行なう。まず、その要素はポインタか否かを調
べる（ステップ３０６）。ポインタでなければ、その要
素を符号化して記憶部１０９に格納する（ステップ３０
７）。ポインタであれば、符号化部１０８を再帰的に呼
び出して、そのポインタの指すデータを符号化し、記憶
部１０９に格納する（ステップ３０８）。

【００３６】記憶部１０９に格納された符号化済みのデ
ータは、他の計算機に転送され、復号化されて、記憶部
１０４上での参照関係と同じ参照関係を保ったまま使用
することができる。このときの復号化方式は、前記した
文献１に記載された方法と同じでよい。

【００３７】以上のように、本実施例によれば、符号化
されたデータを記憶空間の先頭から格納し、未使用空間
の先頭の位置を問い合わせられたときには、その位置を
答えとして返す記憶部１０９と、ユーザからの与えられ
たデータ構造１０１に対して、符号化の際に使用する符
号化情報記憶領域ＡおよびＢを付加したデータ構造を生
成するデータ構造生成部１０２と、その付加した領域の
符号化済み情報およびオフセット情報を利用してデータ
を符号化する符号化部１０８を設けることにより、符号
化を行なう際に、符号化に必要なこれらの情報を、表な
どの符号化されるデータ以外のデータ構造を用いて管理
したり、符号化に必要な情報を表に格納したり、その表
から検索して取り出すような操作をすることなく、必要
な情報をすべて符号化するデータ自体に持たせることが
でき、符号化するデータの中への書き込みおよび符号化
するデータからの情報の読み出しだけで、すべてのデー
タ要素の符号化を行なうことができるので、符号化を高
速化することができる。

【００３８】なお、本実施例では、復号化には従来と同
じ方法を用いたが、復号化に際しても、受信したデータ
を格納する記憶部の中のデータ構造に対して、復号化に
必要な情報を格納する領域を追加し、復号化に際して
は、復号に必要な情報をその領域に記憶させることによ
って、復号化を高速化することも可能である。

【００３９】また、本実施例では、記憶領域Ａを用い
て、そのデータが符号化済みか否かを表現しているが、
符号化済みでない場合には記憶領域Ｂは使われていない
ので、符号化済みでない場合には記憶領域Ｂにオフセッ
トとしては絶対使われない値、たとえば負の値などを入
れて符号化済みでないことを示すこととし、記憶領域Ｂ
のみで符号化済みか否かの判断ができるようにして、記
憶領域Ａを不必要とすることも可能である。

【００４０】

【発明の効果】以上のように、本発明は、符号化された
データを記憶空間の先頭から格納し、未使用空間の先頭
の位置を問い合わせられたときは、その位置を答えとし
て返す記憶部を備え、ユーザから与えられたデータ構造
に対して、符号化の際に使用する符号化情報記憶領域を
付加したデータ構造を生成するとともに、その付加した
領域の情報を利用してデータを符号化するようにしたの
で、ポインタによって結ばれたデータ構造を、その参照
関係を保ったままより高速に符号化することができると
いう効果を有する。

【図面の簡単な説明】

【図１】本発明の一実施例におけるデータ転送符号化装
置の構成を示すブロック図

【図２】同装置におけるデータ構造生成部１０２の内部
構成と、データ構造表現１０１と１０３の内容の例を示
したブロック図

【図３】同装置における符号化部１０８の動作を示すフ
ローチャート

【図４】従来のデータ転送装置のデータを符号化する部
分の構成を示すブロック図

【符号の説明】

１０１ ユーザによって与えられたデータ構造表現 １０２ データ構造生成部 １０３ データ構造生成部によって生成されたデータ構
造表現 １０４ 転送するデータを記憶する記憶部 １０５ 転送されるデータ １０６ データ１０５の中のポインタによって指されて
いるデータ １０７ データ１０５と１０６の中にポインタによって
指されているデータ １０８ 符号化部 １０９ 符号化されたデータを記憶する記憶部 Ａ 符号化済み情報を格納する記憶領域 Ｂ 記憶部１０９上でのオフセット情報を格納する記憶
領域 ２０１ データ構造表現解析手段 ２０２ データ構造記憶手段 ２０３ 符号化用記憶領域追加手段 ２０４ データ構造記憶手段 ２０５ データ構造表現生成手段 ２０６ データ構造記憶手段２０２に記憶されるデータ
構造 ２０７ データ構造記憶手段２０４に記憶されるデータ
構造

Claims (4)

【特許請求の範囲】
1. 【請求項１】 ユーザから与えられたデータ構造に対し
   て、符号化要求のあったデータがすでに符号化済みであ
   るか否を示す情報を格納する符号化情報記憶領域を付加
   したデータ構造を生成し、この生成されたデータ構造を
   持つデータの符号化を行なう際に、前記符号化情報記憶
   領域中に符号化済であることを示す情報が含まれていな
   い場合には、その領域に符号化済みであることを示す情
   報を入れるとともに、符号化されたデータを格納する記
   憶部に対して未使用空間の先頭の位置を問い合わせ、そ
   の答えとして得られた値を符号化情報記憶領域中に入
   れ、符号化要求のあったデータのすべての要素を符号化
   して前記記憶部に格納する一方、符号化情報記憶領域中
   に符号化済みであることを示す情報が含まれている場合
   には、符号化情報記憶領域からそのデータが符号化され
   た時の前記記憶部の未使用空間の先頭の位置を示す値を
   取り出し、その値を符号化して前記記憶部に格納するデ
   ータ転送符号化方法。
2. 【請求項２】 有限かつ１次元の記憶空間を有し、符号
   化データの格納を要求されたときには未使用空間の先頭
   に格納し、未使用空間の先頭の位置を問い合わせられた
   ときにはその位置を示す値を答えとして返す記憶部と、
   ユーザから与えられたデータ構造に対して、符号化の際
   に使用する符号化情報記憶領域を付加したデータ構造を
   生成するデータ構造生成部と、前記データ構造生成部に
   よって生成されたデータ構造を持つデータを、前記符号
   化情報記録領域に格納された情報を利用して符号化する
   符号化部とを備えたデータ転送符号化装置。
3. 【請求項３】 符号化情報記憶領域は、符号化要求のあ
   ったデータがすでに符号化済みであるか否かを示す値を
   格納する領域と、そのデータが符号化されて記憶部に格
   納されている場合に、その先頭からの相対位置を示すオ
   フセットを格納する領域の二つの領域である請求項２記
   載のデータ転送符号化装置。
4. 【請求項４】 符号化情報記憶領域は、符号化要求のあ
   ったデータが符号化されて記憶部に格納されたときに、
   その先頭からの相対位置を示すオフセットを格納すると
   ともに、そのデータがまだ符号化されていない場合に
   は、オフセットとしては絶対に使用されない値を格納す
   ることにより符号化済みでないことを示す一つの領域で
   ある請求項２記載のデータ転送符号化装置。