(57)【要約】【課題】  容易に記憶領域を少なくすること。【解決手段】  データ列バッファ装置であって、データ列を所定単位で入力するデータ入力部２と、入力されたデータ列を、より前に入力された所定単位のデータ列と比較して、同一部分を検出するデータ列比較部３と、検出された同一部分を、より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するインデックスデータ生成手段と、入力されたデータ列のうち同一部分を除く非同一部分をインデックスデータと関連付けて記憶するデータ列記憶部１と、入力されたデータ列を入力された順に復元する復元手段と、復元されたデータ列を出力する出力部４とを備える。【選択図】        図１
2005208910.tif 000002
【特許請求の範囲】
【請求項１】
データ列を所定単位で入力するデータ入力手段と、
前記入力されたデータ列を、より前に入力された前記所定単位のデータ列と比較して、同一部分を検出するデータ列比較手段と、
前記検出された同一部分を、前記より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するインデックスデータ生成手段と、
前記入力されたデータ列のうち前記同一部分を除く非同一部分を前記インデックスデータと関連付けて記憶するデータ列記憶手段と、
前記入力されたデータ列を入力された順に復元する復元手段と、
前記復元されたデータ列を出力する出力手段とを備え、
前記復元手段は、前記非同一部分と、前記インデックスデータで関連付けられた同一部分とを前記データ列記憶手段から読出す読出手段を含む、データ列バッファ装置。
【請求項２】
前記データ列記憶手段は、前記復元されたデータ列を前記所定単位で記憶する復元データ記憶領域を含む、請求項１に記載のデータ列バッファ装置。
【請求項３】
データ列を所定単位で入力するデータ入力手段と、
前記入力されたデータ列を、より前に入力された前記所定単位のデータ列と比較して、同一部分を検出するデータ列比較手段と、
前記検出された同一部分を、前記より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するインデックスデータ生成手段と、
前記入力されたデータ列のうち前記同一部分を除く非同一部分を前記インデックスデータと関連付けて記憶するデータ列記憶手段と、
前記入力されたデータ列を入力された順に復元する復元手段と、
前記復元されたデータ列を前記所定単位で記憶する復元データ記憶手段と、
前記復元されたデータ列を出力する出力手段とを備え、
前記復元手段は、前記非同一部分および前記インデックスデータを前記データ列記憶手段から読出し、前記読出したインデックスデータで関連付けられた同一部分を前記復元データ記憶手段から読出す読出手段を含む、データ列バッファ装置。
【請求項４】
データ列を所定単位で入力するデータ入力手段と、
前記入力されたデータ列を、より前に入力された前記所定単位のデータ列と比較して、同一部分を検出するデータ列比較手段と、
前記検出された同一部分を、前記より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するインデックスデータ生成手段と、
前記入力されたデータ列のうち前記同一部分を除く非同一部分を前記インデックスデータと関連付けて記憶するデータ列記憶手段と、
前記入力されたデータ列の前記非同一部分と、前記インデックスデータで関連付けられた同一部分とを入力された順とは逆の順で前記データ列記憶手段から読出して復元する復元手段と、
前記復元されたデータ列を出力する出力手段とを備えた、データ列バッファ装置。
【請求項５】
前記復元手段により前記入力データが復元されたことを条件に、前記入力データに対応する前記非同一部分および前記インデックスデータを前記データ列記憶手段から削除する削除手段をさらに含む、請求項１〜４のいずれかに記載のデータ列バッファ装置。
【請求項６】
前記データ列比較手段は、前記入力されたデータ列を、前記データ列記憶手段に記憶された前記同一部分と比較する、請求項１〜４のいずれかに記載のデータ列バッファ装置。
【請求項７】
前記データ列比較手段は、前記入力されたデータ列を、前記復元データ記憶手段に記憶されている前記復元されたデータ列と比較する、請求項３に記載のデータ列バッファ装置。
【請求項８】
前記データ列比較手段は、前記データ列記憶手段に前記同一部分が記憶されていない場合には、前記入力されたデータ列を前記復元データ記憶手段に記憶された前記復元されたデータ列と比較する、請求項７に記載のデータ列バッファ装置。
【請求項９】
前記データ入力手段に入力されたデータ列を前記所定単位のみ記憶する入力データ列記憶手段をさらに備え、
前記データ列比較手段は、前記入力されたデータ列を、前記入力データ列記憶手段に記憶されている直前に入力されたデータ列と比較する、請求項１〜４のいずれかに記載のデータ列バッファ装置。
【請求項１０】
前記所定単位のデータ列は、描画用コマンドとパラメータとを含む、請求項１〜４のいずれかに記載のデータ列バッファ装置。
【請求項１１】
前記復元データ記憶領域は、前記データ列比較手段で前記入力されたデータ列と比較されるより前に入力された前記所定単位のデータ列の数と少なくとも同じ数のデータ列を記憶可能である、請求項２に記載のデータ列バッファ装置。
【請求項１２】
前記復元データ記憶手段は、前記データ列比較手段で前記入力されたデータ列と比較されるより前に入力された前記所定単位のデータ列の数と少なくとも同じ数のデータ列を記憶可能である、請求項３に記載のデータ列バッファ装置。
【請求項１３】
データ列を所定単位で入力するステップと、
前記入力されたデータ列を、より前に入力された前記所定単位のデータ列と比較して、同一部分を検出するステップと、
前記検出された同一部分を、前記より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するステップと、
前記入力されたデータ列のうち前記同一部分を除く非同一部分を前記インデックスデータと関連付けて記憶するステップと、
前記非同一部分と、前記インデックスデータで関連付けられた同一部分とを読出して、前記入力されたデータ列を入力された順に復元するステップと、
前記復元されたデータ列を前記所定単位のみ記憶するステップと、
前記復元されたデータ列を出力するステップとをコンピュータに実行させる、データ列バッファプログラム。
【請求項１４】
データ列を所定単位で入力するステップと、
前記入力されたデータ列を、より前に入力された前記所定単位のデータ列と比較して、同一部分を検出するステップと、
前記検出された同一部分を、前記より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するステップと、
前記入力されたデータ列のうち前記同一部分を除く非同一部分を前記インデックスデータと関連付けて記憶するステップと、
前記非同一部分と、前記インデックスデータで関連付けられた同一部分とを読出して、前記入力されたデータ列を入力された順とは逆の順で復元するステップと、
前記復元されたデータ列を出力するステップとをコンピュータに実行させる、データ列バッファプログラム。
【請求項１５】
データ列を所定単位で入力するステップと、
前記入力されたデータ列を、より前に入力された前記所定単位のデータ列と比較して、同一部分を検出するステップと、
前記検出された同一部分を、前記より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するステップと、
前記入力されたデータ列のうち前記同一部分を除く非同一部分を前記インデックスデータと関連付けて記憶するステップと、
前記非同一部分と、前記インデックスデータで関連付けられた同一部分とを読出して、前記入力されたデータ列を入力された順に復元するステップと、
前記復元されたデータ列を前記所定単位のみ記憶するステップと、
前記復元されたデータ列を出力するステップとを含む、データ列バッファ方法。
【請求項１６】
データ列を所定単位で入力するステップと、
前記入力されたデータ列を、より前に入力された前記所定単位のデータ列と比較して、同一部分を検出するステップと、
前記検出された同一部分を、前記より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するステップと、
前記入力されたデータ列のうち前記同一部分を除く非同一部分を前記インデックスデータと関連付けて記憶するステップと、
前記非同一部分と、前記インデックスデータで関連付けられた同一部分とを読出して、前記入力されたデータ列を入力された順とは逆の順で復元するステップと、
前記復元されたデータ列を出力するステップとを含む、データ列バッファ方法。
【発明の詳細な説明】
【技術分野】
【０００１】
情報処理装置にかかるデータ列バッファ装置、データ列バッファプログラムおよびデータ列バッファ方法に関する。
【背景技術】
【０００２】
従来、一定の記憶領域を持つデータバッファとしては、ＦＩＦＯ(First In First Out)型やＬＩＦＯ(Last In First Out)型が知られている。従来のＦＩＦＯ型やＬＩＦＯ型データバッファは、入力されたデータをそのまま記憶するため、あらかじめ用意した記憶領域のサイズ以上のデータを記憶することができない。このため、データバッファからの読出しがない限り記憶領域以上のデータを入力することができない。
【０００３】
特開平２−２０１５３６号公報（特許文献１）には、予めレジスタに記憶したデータと同じデータが連続して入力された場合にバッファに記憶しないようにして、入力されるデータ量よりも多くの量のデータを記憶可能としたデータバッファ装置が記載されている。このデータバッファ装置は、レジスタに記憶したデータと同じデータが連続して入力された回数をカウンタでカウントし、カウント数だけレジスタから出力するようにしたものである。
【特許文献１】特開平２−２０１５３６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、特開平２−２０１５３６号公報記載のデータバッファ装置では、入力データ中で連続することが予測されるデータをレジスタに予め記憶しておかなければならない。また、予め記憶したデータと、完全に一致するデータが連続して入力されなければ、圧縮の効果が得られない。
【０００５】
本発明は、上述した問題点を解決するためになされたもので、この発明の目的の１つは、記憶領域を少なくしたデータ列バッファ装置、データ列バッファプログラムおよびデータ列バッファ方法を提供することである。
【０００６】
この発明の他の目的は、データ列の出現頻度を事前に知ることなく、かつ圧縮用の辞書データを用意することなく、容易にデータ量を少なくすることが可能なデータ列バッファ装置、データ列バッファプログラムおよびデータ列バッファ方法を提供することである。
【課題を解決するための手段】
【０００７】
上記目的を達成するために本発明のある局面に従うと、データ列バッファ装置は、データ列を所定単位で入力するデータ入力手段と、入力されたデータ列を、より前に入力された所定単位のデータ列と比較して、同一部分を検出するデータ列比較手段と、検出された同一部分を、より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するインデックスデータ生成手段と、入力されたデータ列のうち同一部分を除く非同一部分をインデックスデータと関連付けて記憶するデータ列記憶手段と、入力されたデータ列を入力された順に復元する復元手段と、復元されたデータ列を出力する出力手段とを備え、復元手段は、非同一部分と、インデックスデータで関連付けられた同一部分とをデータ列記憶手段から読出す読出手段を含む。
【０００８】
この発明に従えば、所定単位で入力されたデータ列が、より前に入力された所定単位のデータ列と比較されて、同一部分をより前に入力されたデータ列の対応する部分と関連付けたインデックスデータが生成され、非同一部分がインデックスデータと関連付けて記憶される。そして、非同一部分と、インデックスデータで関連付けられた同一部分とが読出されて、入力されたデータ列が入力された順に復元されて出力される。このため、データ列のうちより前に入力されたデータ列と同一の部分がインデックスデータに変換されて記憶されるので、データ列のデータ量を少なくすることができる。また、入力されたデータ列を比較するため、データ列の出現頻度を知る必要も、圧縮用の辞書データを用意する必要もない。その結果、容易に記憶領域を少なくすることが可能なデータ列バッファ装置を提供することができる。
【０００９】
好ましくは、データ列記憶手段は、復元されたデータ列を所定単位で記憶する復元データ記憶領域を含む。
【００１０】
この発明の別の局面に従うと、データ列バッファ装置は、データ列を所定単位で入力するデータ入力手段と、入力されたデータ列を、より前に入力された所定単位のデータ列と比較して、同一部分を検出するデータ列比較手段と、検出された同一部分を、より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するインデックスデータ生成手段と、入力されたデータ列のうち同一部分を除く非同一部分をインデックスデータと関連付けて記憶するデータ列記憶手段と、入力されたデータ列を入力された順に復元する復元手段と、復元されたデータ列を所定単位で記憶する復元データ記憶手段と、復元されたデータ列を出力する出力手段とを備え、復元手段は、非同一部分およびインデックスデータをデータ列記憶手段から読出し、読出したインデックスデータで関連付けられた同一部分を復元データ記憶手段から読出す読出手段を含む。
【００１１】
この発明に従えば、記憶領域を容易に少なくすることが可能なデータ列バッファを提供することができる。
【００１２】
この発明のさらに別の局面に従うと、データ列バッファ装置は、データ列を所定単位で入力するデータ入力手段と、入力されたデータ列を、より前に入力された所定単位のデータ列と比較して、同一部分を検出するデータ列比較手段と、検出された同一部分を、より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するインデックスデータ生成手段と、入力されたデータ列のうち同一部分を除く非同一部分をインデックスデータと関連付けて記憶するデータ列記憶手段と、入力されたデータ列の非同一部分と、インデックスデータで関連付けられた同一部分とを入力された順とは逆の順でデータ列記憶手段から読出して復元する復元手段と、復元されたデータ列を出力する出力手段とを備える。
【００１３】
この発明に従えば、所定単位で入力されたデータ列が、より前に入力された所定単位のデータ列と比較されて、同一部分をより前に入力されたデータ列の対応する部分と関連付けたインデックスデータが生成され、非同一部分がインデックスデータと関連付けて記憶される。そして、非同一部分と、インデックスデータで関連付けられた同一部分とが読出されて、入力されたデータ列が入力された順と逆の順に復元されて出力される。このため、データ列のうちより前に入力されたデータ列と同一の部分がインデックスデータに変換されて記憶されるので、データ列のデータ量を少なくすることができる。また、入力されたデータ列を比較するため、データ列の出現頻度を知る必要も、圧縮用の辞書データを用意する必要もない。その結果、容易に記憶領域を少なくすることが可能なデータ列バッファを提供することができる。
【００１４】
好ましくは、復元手段により入力データが復元されたことを条件に、入力データに対応する非同一部分およびインデックスデータをデータ列記憶手段から削除する削除手段をさらに含む。
【００１５】
この発明に従えば、入力データが復元されたことを条件に、該入力データに対応する非同一部分およびインデックスデータが削除される。このため、次の入力データを入力することができ、記憶領域を有効に利用することができる。
【００１６】
好ましくは、データ列比較手段は、入力されたデータ列を、データ列記憶手段に記憶された同一部分と比較する。
【００１７】
この発明に従えば、入力されたデータ列が、記憶されている同一部分と比較される。
【００１８】
好ましくは、データ列比較手段は、入力されたデータ列を、復元データ記憶手段に記憶されている復元されたデータ列と比較する。
【００１９】
好ましくは、データ列比較手段は、入力されたデータ列を、データ列記憶手段に同一部分が記憶されていない場合には、復元データ記憶手段に記憶された復元されたデータ列と比較する。
【００２０】
この発明に従えば、データ列記憶手段に同一部分が記憶されていない場合には、入力されたデータ列が、復元データ記憶手段に記憶された復元されたデータ列と比較される。このため、直前に入力されたデータ列が出力された後に入力されるデータ列のデータ量を少なくして記憶することができる。
【００２１】
好ましくは、データ入力手段に入力されたデータ列を所定単位のみ記憶する入力データ列記憶手段をさらに備え、データ列比較手段は、入力されたデータ列を、入力データ列記憶手段に記憶されている直前に入力されたデータ列と比較する。
【００２２】
この発明に従えば、入力されたデータ列が所定単位のみ記憶され、入力されたデータ列が、直前に入力されたデータ列と比較される。このため、インデックスデータを容易に生成することができる。また、入力されたデータ列が所定単位のみ記憶されるので、直前に入力されたデータが復元されて出力された後でも、直前に入力されたデータは記憶される。その結果、直前に入力されたデータ列が出力された後に入力されるデータ列のデータ量を少なくして記憶することができる。
【００２３】
好ましくは、所定単位のデータ列は、描画用コマンドとパラメータとを含む。
【００２４】
この発明に従えば、所定単位のデータ列は、描画用コマンドとパラメータとを含む。
【００２５】
好ましくは、復元データ記憶領域は、データ列比較手段で入力されたデータ列と比較される、より前に入力された所定単位のデータ列の数と少なくとも同じ数のデータ列を記憶可能である。
【００２６】
この発明に従えば、入力されたデータ列と比較されるより前に入力された所定単位のデータ列の数と少なくとも同じ数の復元されたデータ列が記憶される。このため、データ列を確実に復元することができる。
【００２７】
好ましくは、復元データ記憶手段は、データ列比較手段で入力されたデータ列と比較される、より前に入力された所定単位のデータ列の数と少なくとも同じ数のデータ列を記憶可能である。
【００２８】
この発明に従えば、入力されたデータ列と比較されるより前に入力された所定単位のデータ列の数と少なくとも同じ数の復元されたデータ列が記憶される。
【００２９】
この発明のさらに他の局面によれば、データ列バッファプログラムは、データ列を所定単位で入力するステップと、入力されたデータ列を、より前に入力された所定単位のデータ列と比較して、同一部分を検出するステップと、検出された同一部分を、より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するステップと、入力されたデータ列のうち同一部分を除く非同一部分をインデックスデータと関連付けて記憶するステップと、非同一部分と、インデックスデータで関連付けられた同一部分とを読出して、入力されたデータ列を入力された順に復元するステップと、復元されたデータ列を所定単位のみ記憶するステップと、復元されたデータ列を出力するステップとをコンピュータに実行させる。
【００３０】
この発明に従えば、記憶領域を容易に少なくすることが可能なデータ列バッファプログラムを提供することができる。
【００３１】
この発明のさらに他の局面によれば、データ列バッファプログラムは、データ列を所定単位で入力するステップと、入力されたデータ列を、より前に入力された所定単位のデータ列と比較して、同一部分を検出するステップと、検出された同一部分を、より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するステップと、入力されたデータ列のうち同一部分を除く非同一部分をインデックスデータと関連付けて記憶するステップと、非同一部分と、インデックスデータで関連付けられた同一部分とを読出して、入力されたデータ列を入力された順とは逆の順で復元するステップと、復元されたデータ列を出力するステップとをコンピュータに実行させる。
【００３２】
この発明に従えば、記憶領域を容易に少なくすることが可能なデータ列バッファプログラムを提供することができる。
【００３３】
この発明のさらに他の局面に従えば、データ列バッファ方法は、データ列を所定単位で入力するステップと、入力されたデータ列を、より前に入力された所定単位のデータ列と比較して、同一部分を検出するステップと、検出された同一部分を、より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するステップと、入力されたデータ列のうち同一部分を除く非同一部分をインデックスデータと関連付けて記憶するステップと、非同一部分と、インデックスデータで関連付けられた同一部分とを読出して、入力されたデータ列を入力された順に復元するステップと、復元されたデータ列を所定単位のみ記憶するステップと、復元されたデータ列を出力するステップとを含む。
【００３４】
この発明に従えば、記憶領域を容易に少なくすることが可能なデータ列バッファ方法を提供することができる。
【００３５】
この発明のさらに他の局面に従えば、データ列バッファ方法は、データ列を所定単位で入力するステップと、入力されたデータ列を、より前に入力された所定単位のデータ列と比較して、同一部分を検出するステップと、検出された同一部分を、より前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するステップと、入力されたデータ列のうち同一部分を除く非同一部分をインデックスデータと関連付けて記憶するステップと、非同一部分と、インデックスデータで関連付けられた同一部分とを読出して、入力されたデータ列を入力された順とは逆の順で復元するステップと、復元されたデータ列を出力するステップとを含む。
【００３６】
この発明に従えば、記憶領域を容易に少なくすることが可能なデータ列バッファ方法を提供することができる。
【発明を実施するための最良の形態】
【００３７】
以下、本発明の実施の形態について図面を参照しながら説明する。なお、図中同一符号は同一または相当する部材を示し、重複する説明は繰り返さない。
【００３８】
＜第１の実施の形態＞
図１は、第１の実施の形態におけるデータ列バッファ装置の概略構成を示すブロック図である。図１を参照して、データ列バッファ装置１００は、データ列を所定単位で入力する入力部２と、入力されたデータ列をより前に入力された所定単位のデータ列と比較して同一部分を検出するデータ列比較部３と、検出された同一部分をより前に入力されたデータ列の対応する部分と関連付けたインデックスデータを生成するインデックスデータ生成手段と、入力されたデータ列のうち同一部分を除く非同一部分をインデックスデータと関連付けて記憶するデータ列記憶部１と、データ列を入力された順に復元して出力する出力部４とを備える。
【００３９】
本実施の形態におけるデータ列バッファ装置１００には、所定単位のデータ列が入力される。所定単位のデータ列は、複数のメンバから構成される。各メンバは、予め定められた固定の長さである。あるデータ列中で、すべてのメンバは同じ長さである必要はないが、メンバ間では対応するメンバは同じ長さである。
【００４０】
本実施の形態においては、所定単位のデータ列Ｄが４つのメンバＭ（１），Ｍ（２），Ｍ（３），Ｍ（４）で構成される例を説明する。入力部２には、データ列Ｄが一度に入力される。
【００４１】
データ列比較部３は、入力されたデータ列ＤのメンバＭ（１）〜Ｍ（４）を、より前に入力されたデータ列ＤのメンバＭ（１）〜Ｍ（４）とそれぞれ比較して、同一か否かを判断する。つまり、入力されたデータ列ＤのメンバＭ（１）〜Ｍ（４）のうち、より前に入力されたデータ列ＤのメンバＭ（１）〜Ｍ（４）と同一のメンバが同一部分であり、同一でないメンバが非同一部分である。
【００４２】
データ列比較部３は、入力されたデータ列Ｄについて、そのデータ列Ｄに対応するインデックスデータを作成する。インデックスデータは、入力データを特定するためのカウンタと、メンバごとに同一部分か非同一部分かを示すメンバ要素を含む。
【００４３】
データ列記憶部１は、入力されたデータ列のうち非同一部分とされたメンバの値と、インデックスデータとを関連付けて記憶する。
【００４４】
出力部４は、データ列記憶部１に記憶された情報に基づいて、入力されたデータ列Ｄを復元する。出力部４は、復元の対象となるデータ列より前に入力されたデータ列を復元したデータを記憶するための復元データ記憶領域を含む。出力部４は、復元の対象となるデータ列を、データ列記憶部１に記憶された非同一部分と、それに関連付けて記憶されたインデックスデータと、復元データ記憶領域に記憶されたより前に入力されたデータ列とを読出して、入力されたデータ列を復元する。
【００４５】
図２は、データ列バッファ装置に入力されるデータ列の一例を示す図である。データ列は、メンバ数を４とし、各メンバは４バイト（Ｂｙｔｅ）の固定長である。なお、図２において「メンバ１」、「メンバ２」、「メンバ３」、「メンバ４」と記されている部分は、データ列のメンバＭ（１）〜Ｍ（４）を表記上区別するために示したものであり、実際のデータではない。
【００４６】
図２（Ａ）は、第１番目に入力されるデータ列Ｄ１を示し、メンバＭ（１）〜Ｍ（４）は、「１００」、「５００」、「３００」、「４００」で構成される。図２（Ｂ）は、第２番目に入力されるデータ列Ｄ２を示し、メンバＭ（１）〜Ｍ（４）は、「１００」、「５００」、「３５０」、「２０」で構成される。図２（Ｃ）は、第３番目に入力されるデータ列Ｄ３を示し、メンバＭ（１）〜Ｍ（４）は、「１５０」、「５００」、「３５０」、「４００」で構成される。
【００４７】
図３は、インデックスデータの構成の一例を示す図である。インデックスデータは、入力されたデータ列を特定するためのカウントの要素と、４つのメンバごとにその直前に入力されたデータ列の対応するメンバと同一か非同一かを示すメンバ要素とを含む。カウントの要素は、データ列記憶部１に記憶されているデータ列の入力順を示す。このため、カウントの要素により、そのインデックスデータと関連するデータ列を入力順で特定することができる。
【００４８】
図４は、図２に示したデータ列が入力された場合に生成されるインデックスデータの一例を示す図である。図４（Ａ）は、第１番目に入力されたデータ列Ｄ１に関連付けられるインデックスデータＩ１を示す。図４（Ａ）を参照して、カウントの要素は、第１番目に入力されたデータ列Ｄ１を特定するために「１」とされる。第１番目に入力されたデータ列Ｄ１は、直前に入力されたデータ列が存在しないため、メンバ要素はすべて「非同一」とされる。
【００４９】
図４（Ｂ）は、第２番目に入力されたデータ列Ｄ２に関連付けられるインデックスデータＩ２を示す。図４（Ｂ）を参照して、カウントの要素は、第２番目に入力されたデータ列Ｄ２を特定するために「２」とされる。ここで、図２（Ａ）および図２（Ｂ）を参照して、第１番目に入力されたデータ列Ｄ１のメンバＭ（１）は「１００」であり、第２番目に入力されたデータ列Ｄ２のメンバＭ（１）は「１００」であるため、同一である。このため、図４（Ｂ）に示すインデックスデータＩ２のメンバＭ（１）に対応するメンバ要素は、「同一」とされている。同様に、図２（Ａ）および図２（Ｂ）を参照して、第１番目に入力されたデータ列Ｄ１と第２番目に入力されたデータ列Ｄ２のメンバＭ（２）は「５００」で同一であり、図４（Ｂ）に示すインデックスデータのメンバＭ（２）に対応するメンバ要素は「同一」とされている。さらに、図２（Ａ）および図２（Ｂ）を参照して、第１番目に入力されたデータ列Ｄ１のメンバＭ（３）は「３００」であり、第２番目に入力されたデータ列Ｄ２のメンバＭ（３）は「３５０」であるため、同一でない。このため、図４（Ｂ）に示すインデックスデータのメンバＭ（３）に対応するメンバ要素は、「非同一」とされている。同様に、図２（Ａ）および図２（Ｂ）を参照して、第１番目に入力されたデータ列Ｄ１のメンバＭ（４）は「４００」であり、第２番目に入力されたデータ列Ｄ２のメンバＭ（４）は「２０」であるため、同一でない。このため、図４（Ｂ）に示すインデックスデータのメンバＭ（４）に対応するメンバ要素は、「非同一」とされている。
【００５０】
図４（Ｃ）は、第３番目に入力されたデータ列Ｄ３に関連付けられるインデックスデータＩ３を示す。図４（Ｃ）を参照して、カウントの要素は、第３番目に入力されたデータ列Ｄ３を特定するために「３」とされる。ここで、図２（Ｂ）および図２（Ｃ）を参照して、第２番目に入力されたデータ列Ｄ２のメンバＭ（１）は「１００」であり、第３番目に入力されたデータ列Ｄ３のメンバＭ（１）は「１５０」であるため、同一でない。このため、図４（Ｃ）に示すインデックスデータのメンバＭ（１）に対応するメンバ要素は、「非同一」とされている。図２（Ｂ）および図２（Ｃ）を参照して、第２番目に入力されたデータ列Ｄ２と第３番目に入力されたデータ列Ｄ３のメンバＭ（２）は「５００」で同一であり、図４（Ｃ）に示すインデックスデータのメンバＭ（２）に対応するメンバ要素は「同一」とされている。また、第２番目に入力されたデータ列Ｄ２と第３番目に入力されたデータ列Ｄ３のメンバＭ（３）は「３５０」で同一であり、図４（Ｃ）に示すインデックスデータのメンバＭ（３）に対応するメンバ要素は「同一」とされている。さらに、図２（Ｂ）および図２（Ｃ）を参照して、第２番目に入力されたデータ列Ｄ２のメンバＭ（４）は「２０」であり、第３番目に入力されたデータ列Ｄ３のメンバＭ（４）は「４００」であるため、同一でない。このため、図４（Ｃ）に示すインデックスデータのメンバＭ（４）に対応するメンバ要素は、「非同一」とされている。
【００５１】
図５は、データ列記憶部１に記憶されるデータの構造を示す図である。図５を参照して、データ列記憶部１は、入力されたデータ列の非同一部分Ｄ’１〜Ｄ’３を記憶する領域と、インデックスデータＩ１〜Ｉ３を記憶する領域と、復元された入力データを記憶する復元データ記憶領域５とを含む。非同一部分Ｄ’１とインデックスデータＩ１は、入力データ列Ｄ１に対応し、それぞれが関連付けられて記憶される。非同一部分Ｄ’１は、メンバＭ（１）〜Ｍ（４）のすべてを含む。非同一部分Ｄ’１は、メンバＭ（１）〜Ｍ（４）の順に記憶される。非同一部分Ｄ’２とインデックスデータＩ２は、入力データ列Ｄ２に対応する。非同一部分Ｄ’２は、メンバＭ（３）の「３５０」とメンバＭ（４）の「２０」とを含む。非同一部分Ｄ’３とインデックスデータＩ３は、入力データ列Ｄ３に対応する。非同一部分は、メンバＭ（１）の「１５０」とメンバＭ（４）の「４００」とを含む。各データ列Ｄ１〜Ｄ３の非同一部分Ｄ’１〜Ｄ’３と、インデックスデータＩ１〜Ｉ３との関連付けは、記憶される順である。データ列のメンバのすべてが、直前のデータ列の対応するメンバと同一の場合には、非同一部分は記憶されない。図５では、入力されたデータ列が復元されていない場合を示しており、復元データ記憶領域５は何も記憶されていない。
【００５２】
図６は、第１の実施の形態におけるデータ列バッファ装置が実行するデータ列を記憶する処理の流れを示すフローチャートである。図６を参照して、ステップＳ０１では、入力部２より所定単位のデータ列を取り込む。ステップＳ０２ではデータ列記憶部１が空かどうかが判別される。空であれば、ステップＳ０４へ進み、空でなければステップＳ０３へ進む。この実施例においてデータ列記憶部１が空の場合とは、ステップＳ０１で第１番目のデータ列Ｄ１が入力された場合である。したがって、第１番目のデータ列が入力された場合に、ステップＳ０４に進み、そうでない場合に、ステップＳ０３に進む。もちろん、ｎ番目のデータ列が入力された際に、ｎ−１番目のデータ列がすでに読み出されている場合も含む。
【００５３】
ステップＳ０４では、第１番目に入力されたデータ列Ｄ１に対応するインデックスデータＩ１が生成される。ステップＳ０３では、ステップＳ０１で入力されたデータ列のうち、２番目以降に入力されたデータ列に対応するインデックスデータＩ２、Ｉ３が生成される。
【００５４】
ステップＳ０５では、非同一部分とステップＳ０３またはステップＳ０４で生成されたインデックスデータとがデータ列記憶部１に関連付けられて保存される。
【００５５】
まず、第１番目にデータ列Ｄ１が入力された場合について説明する。データ列Ｄ１が入力される（ステップＳ０１）と、データ列記憶部１が空であるとされ（ステップＳ０２でＹＥＳ）、図４（Ａ）に示したインデックスデータＩ１が生成されて（ステップＳ０４）、非同一部分Ｄ’１とインデックスデータＩ１とが関連付けられてデータ列記憶部１へ保存される。
【００５６】
２番目のデータ列Ｄ２が入力される（ステップＳ０１）と、データ列記憶部１にデータ列Ｄ１に対応する非同一部分Ｄ’１とインデックスデータＩ１が記憶されているので、データ列記憶部１が空でないとされ（ステップＳ０２でＮＯ）、図４（Ｂ）に示したインデックスデータＩ２が生成されて（ステップＳ０３）、非同一部分Ｄ２とインデックスデータＩ２とが関連付けられてデータ列記憶部１へ保存される（ステップＳ０５）。
【００５７】
３番目のデータ列Ｄ３が入力される（ステップＳ０１）と、データ列記憶部１にデータ列Ｄ２に対応する非同一部分Ｄ’２とインデックスデータＩ２が記憶されているので、データ列記憶部１が空でないとされ（ステップＳ０２でＮＯ）、図４（Ｃ）に示したインデックスデータＩ３が生成されて（ステップＳ０３）、非同一部分Ｄ３とインデックスデータＩ３とが関連付けられてデータ列記憶部１へ保存される（ステップＳ０５）。
【００５８】
図７は、図６におけるステップＳ０３で実行されるインデックスデータ生成処理の流れを示すフローチャートである。ここで、説明のためにデータ列を記号Ｄｉまたは配列Ｄ（ｉ，ｊ）で表す。変数ｉは、入力されたデータ列の入力順を示し、入力されたデータ列を特定するための変数である。例えば２番目に入力されたデータ列はＤ２、３番目に入力されたデータ列はＤ３と表される。変数ｊは、データ列に含まれるメンバを特定するための変数である。
【００５９】
図７を参照して、ステップＳ１１では、メンバを特定するための変数ｊを０にリセットする。ステップＳ１２では変数ｊを１進める。この処理は入力されたデータ列のメンバをメンバＭ（１）〜Ｍ（４）の順に比較してゆくためである。
【００６０】
ステップＳ１３では、メンバＭ（ｊ）に対応する、直前のデータ列Ｄ（ｉ−１）のメンバＭ（ｊ）を求めるため、データ列記憶部１に記憶されているインデックスデータのうち直前に記憶されたインデックスデータから順に、メンバＭ（ｊ）に対応するメンバ要素に「非同一」が設定されているインデックスデータを求める。たとえば、２番目のデータ列Ｄ２のメンバＭ（ｊ）との比較対象は、データ列Ｄ１に対応するメンバＭ（ｊ）である。これを求めるため、インデックスデータＩ１が読出される。インデックスデータＩ１のメンバＭ（ｊ）に対応するメンバ要素は「非同一」であるので、インデックスデータＩ１が求められる。また、３番目のデータ列Ｄ３のメンバＭ（２）との比較対象は、データ列Ｄ２のメンバＭ（２）である。これを求めるため、まず、インデックスデータＩ２が読出されるが、メンバＭ（２）に対応するメンバ要素が「同一」であるため、より前のインデックスデータＩ１が読出される。インデックスデータＩ１のメンバＭ（２）に対応するメンバ要素が「非同一」であるため、インデックスデータＩ１が求められる。また、３番目のデータ列Ｄ３のメンバＭ（３）との比較対象は、データ列Ｄ２のメンバＭ（３）である。これを求めるため、まず、インデックスデータＩ２が読出され、メンバＭ（３）に対応するメンバ要素が「非同一」であるため、インデックスデータＩ２が求められる。
【００６１】
ステップＳ１４ではステップＳ１３で求めたインデックスデータのメンバ要素のうちメンバＭ（１）〜メンバＭ（ｊ）に対応する「非同一」のメンバ要素の数がカウントされ、変数Ｃに代入される。たとえば、２番目のデータ列Ｄ２のメンバＭ（ｊ）については、インデックスデータＩ１の「非同一」のメンバ要素の数は、ｊであるので、変数Ｃにはｊが設定される。また、３番目のデータ列Ｄ３のメンバＭ（２）については、インデックスデータＩ１の「非同一」のメンバ要素の数は２であるので、変数Ｃには２が設定される。３番目のデータ列Ｄ３のメンバＭ（３）については、インデックスデータＩ２の「非同一」のメンバ要素の数は１であるので、変数Ｃには１が設定される。
【００６２】
ここで、ステップＳ１４で、変数Ｃを求める理由を説明する。あるデータ列のメンバがそれ以前のデータ列のメンバと同一となると、そのメンバは、データ列記憶装置１には記憶されない。このため、対応するインデックスの非同一のデータ数を数えていくことで、データ列記憶装置１の対応するデータを求めることができる。
【００６３】
ステップＳ１５では、ステップＳ１４で求めたインデックスデータに関連付けてデータ列記憶部１にＣ番目に記憶されている非同一部分を読出す。たとえば、２番目のデータ列Ｄ２のメンバＭ（ｊ）については、インデックスデータＩ１に関連して非同一部分Ｄ’１にＣ番目（ｊ番目）に記憶されている非同一部分が読出される。また、３番目のデータ列Ｄ３のメンバＭ（２）については、インデックスデータＩ１に関連して非同一部分Ｄ’１に２番目に記憶されている非同一部分「５００」が読出される。３番目のデータ列Ｄ３のメンバＭ（３）については、インデックスデータＩ２に関連付けて非同一部分Ｄ’２に１番目に記憶されている非同一部分「３５０」が読出される。
【００６４】
ステップＳ１６では入力データ列のメンバＭ（ｊ）と、ステップＳ１５で求めた直前のデータ列のメンバＭ（ｊ）とが比較される。
【００６５】
ステップＳ１７では、データ列Ｄｉの全てのメンバＭ（ｊ）について、直前のデータ列Ｄ（ｉ−１）の対応するメンバＭ（ｊ）との比較が終了したかが判断される。比較が終了した場合には処理を終了し、終了していない場合には次のメンバＭ（ｊ＋１）について上述した処理が繰り返し実行される。
【００６６】
これにより、図４（Ｂ）または図４（Ｃ）に示したインデックスデータＩ２，Ｉ３が生成される。
【００６７】
次に、本実施の形態におけるデータ列バッファ装置１００で実行されるデータ列復元処理について説明する。図８は、データ列記憶部１の記憶状態を示す図である。図８では、データ列記憶部１に記憶された非同一データＤ’１とインデックスデータＩ１とから入力されたデータ列Ｄ１が復元されて出力された後のデータ列記憶部１の状態を示している。図８を参照して、データ列記憶部１には、データ列Ｄ２に対応する非同一部分Ｄ’２およびインデックスデータＩ２と、データ列Ｄ３に対応する非同一部分Ｄ’３およびインデックスデータＩ３と、復元されたデータ列Ｄ１とが記憶される。復元されたデータ列Ｄ１は、復元データ記憶領域５に記憶される。図５に示したデータ列記憶部１の状態と異なる点は、データ列Ｄ’１とインデックスＩ１が削除されており、復元データ記憶領域５に出力データが保存されている点である。
【００６８】
図９は、第１の実施の形態におけるデータ列バッファ装置１００で実行される復元処理の流れを示すフローチャートである。図９を参照して、ステップＳ２１では、メンバ数をカウントするメンバカウンタｊを０にリセットする。ステップＳ２２ではメンバカウンタｊを１進める。この処理は、復元するデータ列をメンバ１からメンバ４まで順に復元するためである。
【００６９】
ステップＳ２３ではインデックスデータを解析する。ここで解析されるインデックスデータは、復元対象とされているデータ列に対応するインデックスデータである。復元対象となるデータ列が、ｉ番目に入力されたデータ列Ｄｉの場合は、インデックスデータＩｉが解析される。
【００７０】
ステップＳ２４では、データが圧縮されているか否かが判定される。圧縮されていない場合にはステップＳ２５に進み、圧縮されている場合にはステップＳ２５をスキップしてステップＳ２６に進む。圧縮されているか否かは、インデックスデータＩｉのメンバ要素が「非同一」の場合に圧縮されていないと判断し、「同一」の場合に圧縮されていると判断する。ここでデータＤ（ｉ，ｊ）は復元すべきデータ列Ｄｉのｊ番目のメンバを示す。
【００７１】
ステップＳ２５では、非同一部分Ｄ’ｉに記憶されている非同一部分が順に読出され、復元データ記憶領域５のｊ番目の領域Ｏ（ｊ）に記憶される。
【００７２】
ステップＳ２６では、メンバカウンタｊがメンバ数ｍ以上か否かが判断される。メンバカウンタｊがメンバ数ｍ以上の場合にはステップＳ２７に進み、そうでない場合にはステップＳ２２に戻る。ここではメンバ数ｍを「４」としている。
【００７３】
ステップＳ２７に進む場合には、データ列ＤｉのすべてのメンバＭ（１）〜Ｍ（４）が復元されて復元データ記憶領域５に記憶されることになる。ステップＳ２７では、データ列Ｄ’ｉとインデックスＩｉとをデータ列記憶部１から削除する。そして、復元データ記憶領域５に記憶されているＯ（１）〜Ｏ（４）を復元されたデータ列Ｄｉとして出力する（ステップＳ２８）。
【００７４】
図８に示したデータ列記憶部５の状態は、第１番目のデータ列Ｄ１が復元されて出力された後の状態であった。この状態から第２番目のデータ列Ｄ２を復元して出力する場合を説明する。ここでさらに図９を参照して，ステップＳ２１では、メンバ数をカウントするメンバカウンタｊが０にリセットされる。ステップＳ２２ではメンバカウンタｊを１進め、メンバカウンタｊが「１」に設定される。ステップＳ２３ではインデックスデータＩ２が解析される。図４に示したインデックスデータＩ２のメンバＭ（１）に対応するメンバ要素は「同一」であるため、Ｄ（２，１）は圧縮データと判断され（ステップＳ２４でＹＥＳ）、ステップＳ２６に進む。したがって、Ｄ（２，１）は、復元データ記憶領域５の１番目のデータＯ（１）がそのまま割当てられる。復元データ記憶領域５の１番目のデータＯ（１）には、直前のデータ列Ｄ１のメンバＭ（１）が記憶されているため、Ｄ（２，１）は、直前のデータ列Ｄ１のメンバＭ（１）とされる。
【００７５】
ステップＳ２６で、メンバカウンタｊが「１」でメンバ数ｍが４なので、偽と判断されてステップＳ２２に戻る。ステップＳ２２ではメンバカウンタｊを１進め、メンバカウンタｊが「２」に設定される。ステップＳ２３ではインデックスデータＩ２が解析される。図４に示したインデックスデータＩ２のメンバＭ（２）に対応するメンバ要素は「同一」であるため、Ｄ（２，２）は圧縮データと判断され（ステップＳ２４でＹＥＳ）、ステップＳ２６に進む。したがって、Ｄ（２，２）は、復元データ記憶領域５の２番目のデータＯ（２）がそのまま割当てられる。復元データ記憶領域５の２番目のデータＯ（２）には、直前のデータ列Ｄ１のメンバＭ（２）が記憶されているため、Ｄ（２，２）は、直前のデータ列Ｄ１のメンバＭ（２）とされる。
【００７６】
ステップＳ２６で、メンバカウンタｊが「２」でメンバ数ｍが４なので、偽と判断されてステップＳ２２に戻る。ステップＳ２２ではメンバカウンタｊを１進め、メンバカウンタｊが「３」に設定される。ステップＳ２３ではインデックスデータＩ２が解析される。図４に示したインデックスデータＩ２のメンバＭ（３）に対応するメンバ要素は「非同一」であるため、Ｄ（２，３）は圧縮データでないと判断され（ステップＳ２４でＮＯ）、ステップＳ２５に進む。ステップＳ２５では、Ｄ（２，３）は、非同一部分Ｄ’２の最初のデータが割当てられる。非同一部分Ｄ’２の最初のデータには「３５０」が割当てられている。復元データ記憶領域５の３番目のデータＯ（３）には、「３５０」が記憶される。
【００７７】
ステップＳ２６で、メンバカウンタｊが「３」でメンバ数ｍが４なので、偽と判断されてステップＳ２２に戻る。ステップＳ２２ではメンバカウンタｊを１進め、メンバカウンタｊが「４」に設定される。ステップＳ２３ではインデックスデータＩ２が解析される。図４に示したインデックスデータＩ２のメンバＭ（４）に対応するメンバ要素は「非同一」であるため、Ｄ（２，４）は圧縮データでないと判断され（ステップＳ２４でＮＯ）、ステップＳ２５に進む。ステップＳ２５では、Ｄ（２，４）は、非同一部分Ｄ’２の次のデータが割当てられる。非同一部分Ｄ’２の次のデータには「２０」が割当てられている。復元データ記憶領域５の３番目のデータＯ（４）には、「２０」が記憶される。
【００７８】
上記処理により、データ列Ｄ２｛１００、５００、３５０、２０｝が復元され、復元データ記憶領域５に保存される。この後、非同一部分Ｄ’２とインデックスデータＩ２とがデータ列記憶部１から削除され（ステップＳ２７）、復元データ記憶領域５に記憶された、復元されたデータ列Ｏ（ｊ）が出力される（ステップＳ２８）。
【００７９】
以上説明したように、本実施の形態のデータ列バッファ装置１００によると、入力されたデータ列のうち、より前に入力されたデータ列と同一の同一部分が記憶されないので、記憶するデータ量を少なくすることができる。また、入力されたデータ列を直前のデータ列と比較するため、データ列の出現頻度を事前に知る必要がない。さらに、圧縮用の辞書データを用意する必要もない。その結果、容易に記憶領域を少なくすることが可能なデータ列バッファ装置を提供することができる。
【００８０】
＜第１の実施の形態の変形例１＞
本実施の形態では，データ列記憶部１が備える復元データ記憶領域５は固定されたアドレスに割り当てた。ここでは復元データ記憶領域５を備えていない例について説明する。図１０はデータ列記憶部１の記憶状態の別の例を示す図である。データ列Ｄ１を読出す前の状態から、次のデータ列Ｄ２が読出し可能となる状態までの変化を、図１０（Ａ）、図１０（Ｂ）、図１０（Ｃ）の順に示す。
【００８１】
図１０（Ａ）はデータ列Ｄ１を読出す前の状態を示している。ここでは、データ列Ｄ１，Ｄ２，Ｄ３それぞれに対応して、非同一部分Ｄ’１，Ｄ’２，Ｄ’３と、インデックスデータＩ１，Ｉ２，Ｉ３とが記憶されている。この図では、データ列記憶部１に復元データ記憶領域５は存在しない。従って、図１０（Ａ）に示す状態は復元データ記憶領域５がないことを除いて図５と同じである。図１０（Ａ）の状態はデータ列Ｄ２を復元するまで継続する。
【００８２】
図１０（Ｂ）は復元されたデータ列Ｄ２がデータ列記憶部１に書込まれたれた後の状態を示している。図１０（Ｂ）を参照して、データ列Ｄ１が出力された後、データ列Ｄ１に対応する非同一部分Ｄ’１とデータ列Ｄ２に対応する非同一部分Ｄ’２とインデックスデータＩ２とを用いて、データ列Ｄ２を復元する。このとき復元したデータ列Ｄ２を、データ列記憶部１に上書きする。ここで上書きは非同一部分Ｄ’１が書き込まれていた領域に対して行なう。つまり、データ列Ｄ２が復元される段階で、非同一部分Ｄ’１が記憶されていた領域が復元のための作業領域となる。なお、データ列Ｄ２のデータのうちデータ列Ｄ１と異なるデータが非同一部分Ｄ’２に記憶されているため、復元したデータ列Ｄ２の全てをデータ列記憶部１に上書きするのではなく、非同一部分Ｄ’２をデータ列記憶部１に上書きするようにしてもよい。この後、インデックスデータＩ１を削除する。また、復元したデータ列Ｄ２を、データ列記憶部１に上書きした時点でデータ列Ｄ１が削除されたことになる。
【００８３】
図１０（Ｃ）はデータ列Ｄ２の読出しが可能となった状態を示している。図１０（Ｃ）を参照して、非同一部分Ｄ’２が記憶されていた領域分だけ、その領域を埋める方向に、非同一部分Ｄ’３以降のデータを移動（シフト）させる。この後インデックスデータＩ２の全てのメンバ要素を「非同一」と修正する。
【００８４】
このように、データ列Ｄ１の出力後に、最初のデータ列Ｄ１が記憶された領域が、復元されたデータ列Ｄ２の記憶領域となる。このため復元データ記憶領域５を用いずにデータ列を復元することができる。
【００８５】
＜第１の実施の形態の変形例２＞
図１０（Ａ）、図１０（Ｂ）、図１０（Ｄ）の順でデータ列記憶部１の状態が変化する、復元データ記憶領域５を備えていない別の変形例について説明する。図１０（Ａ）、図１０（Ｂ）については説明を繰り返さない。図１０（Ｄ）はデータ列Ｄ２の読出しが可能となった状態を示している。図１０（Ｄ）を参照して、非同一部分Ｄ’２が記憶されていた領域分だけ、その領域を埋める方向に、復元されたデータ列Ｄ２を移動させる。データの移動にともないデータの読出し位置も移動させる。
【００８６】
この後インデックスデータＩ２を削除する。これは、データ列Ｄ２が復元された時点でインデックスデータＩ２は不要となるからである。インデックスデータＩ２を削除することで、インデックスデータＩ２を修正し保存する場合よりも、処理の高速化、データ量削減が可能となる。
【００８７】
このように、データ列記憶部１は、データ列の読出しにともない順次アドレスを変更するため、固定されたアドレスの領域とはならない。なお、図１０（Ｄ）では復元したデータ列Ｄ２およびデータの読出し位置を移動させたが、移動させなくともよい。この場合には、変形例１と同様に、最初のデータ列Ｄ１の場所が読出し位置となる。
【００８８】
本実施の形態においては、入力されたデータ列を入力された順に復元して出力するようにしたが、データ列を入力された順とは逆の順で出力するようにしてもよい。この場合には、復元の対象となるデータ列より前に入力されたデータ列の同一部分およびインデックスデータは、ともにデータ列記憶部１に記憶されているので、データ列記憶部１に復元データ記憶領域５を備える必要はない。
【００８９】
また、本実施の形態においては、入力されたデータ列を直前に入力されたデータ列と比較するようにしたが、入力されたデータ列を比較する対象は、直前に入力されたデータ列に加えて、より前に入力されたデータ列と比較するようにしてもよい。たとえば、入力されたデータ列を、それより前に入力された５つのデータ列と比較するようにしてもよい。これにより、入力されたデータ列が５つ前に入力されたデータ列と比較されるので、同一部分となる確率が高くなり、記憶するデータ量をさらに削減することができる。この場合には、インデックスデータのメンバ要素には、「同一」または「非同一」のいずれかの情報と、比較対象となったデータ列を特定するための情報が含まれる。比較対象となったデータ列を特定するための情報とは、インデックスデータに含まれるカウンタの値、または、入力されたデータ列を基準にしてｎ個前のデータ列など相対的な位置とすることができる。また、復元データ記憶領域５は、比較対象とするデータ列のすべてを復元したデータ列を記憶することが可能な記憶容量を確保しておく必要がある。
【００９０】
＜第２の実施の形態＞
図１１は、第２の実施の形態におけるデータ列バッファ装置１００Ａの概略構成を示すブロック図である。第２の実施の形態におけるデータ列バッファ装置１００Ａは、第１の実施の形態におけるデータ列バッファ装置１００と異なる点は、出力部４から出力される復元されたデータ列を所定単位で記憶する出力一時記憶部６を備える点、および、データ列記憶部１に復元データ記憶領域５を備えていない点である。また、データ列比較部３は、出力一時記憶部６に接続されており、入力されたデータ列を、出力一時記憶部６に記憶されている復元されたデータ列と比較することが可能となっている。
【００９１】
第２の実施の形態におけるデータ列バッファ装置１００Ａで実行されるデータ記憶処理は、図６および図７に示した第１の実施の形態におけるデータ列バッファ装置１００で実行されるデータ記憶処理とステップＳ０４の処理を除いて同様の処理が実行される。データ列バッファ装置１００Ａは、ステップＳ０４において、入力されたデータ列を出力一時記憶部６に記憶されている復元されたデータ列と比較して、同一部分および非同一部分を抽出し、インデックスデータを生成する。これにより、第１番目に入力されるデータ列の非同一部分とインデックスデータとが関連付けて記憶されるため、同一部分をデータ列記憶部１に記憶しない。
【００９２】
図１２は、第２の実施の形態におけるデータ列バッファ装置１００Ａで実行されるデータ復元処理の流れを示すフローチャートである。図１２に示すデータ復元処理は、図９に示したデータ復元処理のステップＳ２５をステップＳ２５Ａとした点を除いて、同様の処理である。上述したように、データ列バッファ装置１００Ａは、復元したデータを出力一時記憶部６に記憶するようにしている。このため、第１の実施の形態におけるデータ列バッファ装置１００がデータ列記憶部１の復元データ記憶領域５に復元されたデータを記憶するのに代えて、復元したデータを出力一時記憶部６に記憶するようにしたものである。
【００９３】
第２の実施の形態におけるデータ列バッファ装置１００Ａでは、データ列記憶部１から全てのデータが読出された場合、データ列記憶部１は空になるが、出力一時記憶部６には最後に復元したデータ列が保持されている。この状態で、入力部２に新たなデータ列が入力されると、その入力されたデータ列を出力一時記憶部６に記憶されている直前に入力されたデータ列と比較される。
【００９４】
データ列比較部３は、新たに入力されたデータ列と比較対象となるデータ列が、データ列記憶部１に存在するか否かを判断し、存在しない場合には出力一時記憶部６に記憶されている復元されたデータ列を比較対象となるデータ列とする。このため、新たに入力されたデータ列の同一部分をデータ列記憶部１に記憶する必要がないので、記憶するデータ量を削減することができる。この場合、出力一時記憶部６に記憶されている復元されたデータ列は、入力されたデータ列の直前に入力されたデータ列である。
【００９５】
以上説明したように第２の実施の形態におけるデータ列バッファ装置１００Ａは、新たに入力されたデータ列を既に出力したデータ列と比較して、同一部分をデータ列記憶部１に記憶しないので、記憶するデータ量を削減することができる。
【００９６】
＜第３の実施の形態＞
図１３は、第３の実施の形態におけるデータ列バッファ装置の概略構成を示すブロック図である。第３の実施の形態におけるデータ列バッファ装置１００Ｂは、第１の実施の形態におけるデータ列バッファ装置１００の入力部２をレジスタ２Ａとし、レジスタ２Ａを、システムバスを介してＣＰＵ７と接続したものである。データ列記憶部１、データ列比較部３および出力部４の構成は、第１の実施の形態におけるデータ列バッファ装置１００と同様である。以下、第１の実施の形態におけるデータ列バッファ装置１００と異なる点を説明する。
【００９７】
レジスタ２Ａは、入力されたデータ列を記憶するための入力レジスタ２Ｂを備えている。この入力レジスタ２Ｂの記憶容量は、所定単位のデータ列のみを記憶可能であれば十分である。レジスタ２Ａは、ＣＰＵ７とシステムバスを介して接続されており、ＣＰＵ７から所定単位のデータ列が順に入力される。レジスタ２Ａは、ＣＰＵからデータ列Ｄｎが入力されると、入力されたデータ列Ｄｎをデータ列比較部３に出力する。この段階で、入力レジスタ２Ｂには、入力されたデータ列Ｄｎの直前に入力されたデータ列Ｄn-1が記憶されている。
【００９８】
データ列比較部３は、レジスタ２Ａより入力されたデータ列Ｄｎが入力されると、入力されたデータ列をレジスタ２Ａの入力レジスタ２Ｂに記憶されている直前に入力されたデータ列Ｄn-1と比較して、同一部分および非同一部分を抽出し、インデックスデータを生成する。そして、抽出した非同一部分と生成したインデックスデータとを関連付けてデータ列記憶部１に記憶する。さらに、入力されたデータ列Ｄｎを、レジスタ２Ａに出力する。
【００９９】
レジスタ２Ａでは、データ列比較部３より入力されるデータ列Ｄｎを直前に入力されたデータ列として入力レジスタ２Ｂに記憶する。
【０１００】
図１４は、第３の実施の形態におけるデータ列バッファ装置１００Ｂで実行されるデータ列記憶処理の流れを示すフローチャートである。図１４を参照して、まず、レジスタ２Ａにおいて、所定単位のデータ列Ｄｎが取り込まれる（ステップＳ４１）。これは、ＣＰＵ７から所定単位のデータ列が入力される場合が相当する。このステップＳ４１が実行される際に、レジスタ２Ａの入力レジスタ２Ｂには、ステップＳ４１で入力されたデータ列Ｄｎの直前に入力されたデータ列Ｄ（ｎ−１）が既に記憶されている。
【０１０１】
データ列比較部３では、レジスタ２Ａから入力されたデータ列を、レジスタ２Ａの入力レジスタ２Ｂに記憶されている直前に入力されたデータ列と比較する（ステップＳ４２）。これにより、入力されたデータ列の各メンバが、直前に入力されたデータ列の対応するメンバと同一か否かが判定される。そして、判定された結果から、入力されたデータ列に対応するインデックスデータが生成される。データ列比較部３は、インデックスデータの生成後、ステップＳ４１でレジスタ２Ａより入力されたデータ列を、レジスタ２Ａに出力する。レジスタ２Ａでは、データ列比較部３より受信したデータ列を直前に入力されたデータ列として入力レジスタ２Ｂに記憶する。
【０１０２】
次のステップＳ４４では、ステップＳ４２で非同一と判定されたメンバと、ステップＳ４３で生成されたインデックスデータとを関連付けてデータ列記憶部１に記憶する。
【０１０３】
第３の実施の形態におけるデータ列バッファ装置１００Ｂで実行されるデータ復元処理は、図９に示した第１の実施の形態における処理と同様であるので、ここでは説明を繰返さない。
【０１０４】
以上説明したように、第３の実施の形態におけるデータ列バッファ装置１００Ｂは、レジスタ２Ａに、直前に入力されたデータ列を記憶するための入力レジスタ２Ｂを備えるので、データ列比較部３における比較処理が単純化される。このため、入力されたデータ列から非同一部分を容易に抽出することができ、インデックスデータを容易に生成することができる。
【０１０５】
＜第４の実施の形態＞
図１５は、第４の実施の形態におけるデータ列バッファ装置の概略構成を示すブロック図である。第４の実施の形態におけるデータ列バッファ装置１００Ｃは、第３の実施の形態におけるデータ列バッファ装置１００Ｂに、第２の実施の形態におけるデータ列バッファ装置１００Ａが備える出力一時記憶部６を付加したものである。
【０１０６】
このため、入力されるデータ列を記憶する処理は、図１４に示した第３の実施の形態におけるデータ列バッファ装置１００Ｂで実行される処理となる。また、データ復元処理は、図１２に示した第２の実施の形態におけるデータ列バッファ装置１００Ｂで実行される処理となる。
【０１０７】
第４の実施の形態におけるデータ列バッファ装置１００Ｃによれば、レジスタ２Ａに、直前に入力されたデータ列を記憶するための入力レジスタ２Ｂを備えるので、データ列比較部３における比較処理が単純化される。このため、入力されたデータ列から非同一部分を容易に抽出することができ、インデックスデータを容易に生成することができる。さらに、データ列記憶部１から全てのデータが読出された場合、データ列記憶部１は空になるが、出力一時記憶部６には最後に復元したデータ列が保持されている。この状態で、入力部２に新たなデータ列が入力されると、その入力されたデータ列が出力一時記憶部６に記憶されている直前に入力されたデータ列と比較される。データ列比較部３は、新たに入力されたデータ列と比較対象となるデータ列が、データ列記憶部１に存在するか否かを判断し、存在しない場合には出力一時記憶部６に記憶されている復元されたデータ列を比較対象となるデータ列とする。このため、新たに入力されたデータ列の同一部分をデータ列記憶部１に記憶しないので、記憶するデータ量を削減することができる。
【０１０８】
なお、上述した第１〜第４の実施の形態におけるデータ列バッファ装置１００，１００Ａ，１００Ｂ，１００Ｃには、所定単位のデータ列が順に入力される場合を説明した。所定単位のデータ列には、メンバ数が同じ可変長のデータ列も含まれる。この場合、メンバを特定するためにデータ列には、各メンバの長さを特定するための情報を含めるようにすれば良い。
【０１０９】
＜実施例１＞
上述した第１〜第４の実施の形態におけるデータ列バッファ装置１００，１００Ａ，１００Ｂ，１００Ｃを、グラフィック描画装置の一部に組み込んだ場合を説明する。第１〜第４の実施の形態におけるデータ列バッファ装置１００，１００Ａ，１００Ｂ，１００Ｃには、グラフィック描画装置のコマンド入力部から所定単位のデータ列が順に入力され、コマンド処理部に対して入力された順にデータ列が出力される。
【０１１０】
図１６は、本実施例におけるデータ列の構成を示す図である。図１６を参照して、データ列は、メンバ１に「描画コマンド」が割当てられ、メンバ２〜４にそれぞれパラメータが割当てられる。このように、本実施例におけるデータ列は、描画コマンドと、そのコマンドに対する３つのパラメータを含む。コマンドは、直線描画コマンド、円描画コマンド、四角描画コマンド、および領域塗りつぶしコマンドを含む。
【０１１１】
図１７は、データ列の具体例を示す図である。図１７（Ａ）は、メンバ１に直線描画コマンドを含むデータ列の一例を示す。データ列Ｄ２１は、メンバ１に直線描画コマンドが割当てられ、メンバ２に始点座標（０，０）が割当てられ、メンバ３に終点座標（１００，１００）が割当てられ、メンバ４に色データ（２５５，２５５，２５５）が割当てられている。このデータ列がコマンド処理部に入力されると、始点座標（０，０）と終点座標（１００，１００）とを結ぶ直線が（２５５，２５５，２５５）で特定される色で描画される。
【０１１２】
図１７（Ｂ）は、メンバ１に直線描画マンドを含むデータ列の別の例を示す。データ列Ｄ２２は、メンバ１に直線描画コマンドが割当てられ、メンバ２に始点座標（０，０）が割当てられ、メンバ３に終点座標（９０，１００）が割当てられ、メンバ４に色データ（２５５，２５５，２５５）が割当てられている。このデータ列がコマンド処理部に入力されると、始点座標（０，０）と終点座標（９０，１００）とを結ぶ直線が（２５５，２５５，２５５）で特定される色で描画される。
【０１１３】
図１７（Ｃ）は、メンバ１に直線描画マンドを含むデータ列のさらに別の例を示す。データ列Ｄ２３は、メンバ１に直線描画コマンドが割当てられ、メンバ２に始点座標（０，０）が割当てられ、メンバ３に終点座標（８０，１００）が割当てられ、メンバ４に色データ（２５５，２５５，２５５）が割当てられている。このデータ列がコマンド処理部に入力されると、始点座標（０，０）と終点座標（８０，１００）とを結ぶ直線が（２５５，２５５，２５５）で特定される色で描画される。
【０１１４】
図１７（Ｄ）は、メンバ１に領域塗りつぶしマンドを含むデータ列の例を示す。データ列Ｄ２４は、メンバ１に領域塗りつぶしコマンドが割当てられ、メンバ２に始点座標（２００，３５０）が割当てられ、メンバ３に終点座標（８０，１００）が割当てられ、メンバ４に色データ（１０，１０，１０）が割当てられている。このデータ列がコマンド処理部に入力されると、始点座標（２００，３５０）と終点座標（８０，１００）とを結ぶ直線を対角線とする矩形領域が（１０，１０，１０）で特定される色で塗りつぶされる。
【０１１５】
図１７（Ｅ）は、メンバ１に四角描画コマンドを含むデータ列の例を示す。データ列Ｄ２５は、メンバ１に四角描画コマンドが割当てられ、メンバ２に始点座標（０，０）が割当てられ、メンバ３に終点座標（５０，５０）が割当てられ、メンバ４に色データ（１０，１０，１０）が割当てられている。このデータ列がコマンド処理部に入力されると、始点座標（０，０）と終点座標（５０，５０）とを結ぶ直線を対角線とする矩形の輪郭が（１０，１０，１０）で特定される色で描画される。
【０１１６】
第１〜第４の実施の形態におけるデータ列バッファ装置１００，１００Ａ，１００Ｂ，１００Ｃには、データ列Ｄ２１，Ｄ２２，Ｄ２３，Ｄ２４，Ｄ２５の順にデータ列が入力される。図１８は、図１７に示したデータ列が入力された場合のデータ列記憶部１の状態を示す図である。
【０１１７】
図１８を参照して、データ列記憶部１には、データ列Ｄ２１に対応する非同一部分Ｄ’２１およびインデックスデータＩ２１が関連付けて記憶される。データ列Ｄ２１が入力された時点において、データ列記憶部１には何も記憶されていない。また、第２または第４の実施の形態における出力データ一時記憶部６にも何も記憶されていない場合を想定している。インデックスデータＩ２１は、全てのメンバ要素が「非同一」とされ、非同一部分Ｄ’２１は、データ列Ｄ２１の全てのメンバがメンバ１「直線」、メンバ２「（０，０）」、メンバ３「（１００，１００）」、メンバ４「（２５５，２５５，２５５）」の順に記憶される。
【０１１８】
データ列記憶部１には、データ列Ｄ２１に対応する非同一部分Ｄ’２１の次にデータ列Ｄ２２に対応する非同一部分Ｄ’２２が記憶され、データ列Ｄ２１に対応するインデックスデータＩ２１の次にデータ列Ｄ２２に対応するインデックスデータＩ２２が記憶される。また、非同一部分Ｄ２２とインデックスデータＩ２２とは関連付けて記憶される。データ列Ｄ２２とデータ列Ｄ２１とは、メンバ３が異なるのみで、メンバ１，２，４が同じであるので、非同一部分Ｄ’２２はメンバ３「（９０，１００）」のみである。また、インデックスデータＩ２２は、メンバ３に対応するメンバ要素に「非同一」が設定され、他のメンバ１，２，４に対応するメンバ要素は「同一」が設定される。
【０１１９】
データ列記憶部１には、データ列Ｄ２２に対応する非同一部分Ｄ’２２の次に、データ列Ｄ２３に対応する非同一部分Ｄ’２３が記憶され、データ列Ｄ２２に対応するインデックスデータＩ２２の次にデータ列Ｄ２３に対応するインデックスデータＩ２３が記憶される。また、非同一部分Ｄ２３とインデックスデータＩ２３とは関連付けて記憶される。データ列Ｄ２３とデータ列Ｄ２２とは、メンバ３が異なるのみで、メンバ１，２，４が同じであるので、非同一部分Ｄ’２３はメンバ３「（８０，１００）」のみである。また、インデックスデータＩ２３は、メンバ３に対応するメンバ要素に「非同一」が設定され、他のメンバ１，２，４に対応するメンバ要素は「同一」が設定される。
【０１２０】
データ列記憶部１には、データ列Ｄ２３に対応する非同一部分Ｄ’２３の次にデータ列Ｄ２４に対応する非同一部分Ｄ’２４が記憶され、データ列Ｄ２３に対応するインデックスデータＩ２３の次にデータ列Ｄ２４に対応するインデックスデータＩ２４が記憶される。また、非同一部分Ｄ２４とインデックスデータＩ２４とは関連付けて記憶される。データ列Ｄ２４とデータ列Ｄ２３とは、メンバ１，２，４が異なり、メンバ３が同じであるので、非同一部分Ｄ’２４は、メンバ１「領域塗りつぶし」と、メンバ２「（２００，３５０）」と、メンバ４「（１０，１０，１０）」とを含む。また、インデックスデータＩ２４は、メンバ１，２，４に対応するメンバ要素に「非同一」が設定され、メンバ３に対応するメンバ要素は「同一」が設定される。
【０１２１】
データ列記憶部１には、データ列Ｄ２４に対応する非同一部分Ｄ’２４の次にデータ列Ｄ２５に対応する非同一部分Ｄ’２５が記憶され、データ列Ｄ２４に対応するインデックスデータＩ２４の次にデータ列Ｄ２５に対応するインデックスデータＩ２５が記憶される。また、非同一部分Ｄ２５とインデックスデータＩ２５とは関連付けて記憶される。データ列Ｄ２５とデータ列Ｄ２４とは、メンバ１，２，３が異なり、メンバ４が同じであるので、非同一部分Ｄ’２５は、メンバ１「四角」と、メンバ２「（０，０）」と、メンバ３「（５０，５０）」とを含む。また、インデックスデータＩ２５は、メンバ１，２，３に対応するメンバ要素に「非同一」が設定され、メンバ４に対応するメンバ要素は「同一」が設定される。
【０１２２】
以上説明したように、本実施の形態におけるデータ列バッファ装置１００，１００Ａ，１００Ｂ，１００Ｃは、グラフィック描画装置のコマンド入力部とコマンド処理部との間に設けられるので、コマンド処理部でコマンドを処理する前であっても、コマンド入力部に連続してコマンドを入力することができる。
【０１２３】
上述した第１〜第４の実施の形態においては、データ列バッファ装置１００，１００Ａ，１００Ｂ，１００Ｃについて説明したが、それらにより実行されるデータ列バッファ方法、または、その方法をコンピュータに実行させるためのデータ列バッファプログラムとしても実現可能である。データ列バッファプログラムは、コンピュータ読み取り可能なフレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ、磁気テープ、半導体メモリなどの記録媒体に記録しておき、この記録媒体からコンピュータにインストールすることにより実行させることができる。
【０１２４】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【０１２５】
【図１】第１の実施の形態におけるデータ列バッファ装置の概略構成を示すブロック図である。
【図２】データ列バッファ装置に入力されるデータ列の一例を示す図である。
【図３】インデックスデータの構成の一例を示す図である。
【図４】図２に示したデータ列が入力された場合に生成されるインデックスデータの一例を示す図である。
【図５】データ列記憶部１に記憶されるデータの構造を示す図である。
【図６】第１の実施の形態におけるデータ列バッファ装置が実行するデータ列を記憶する処理の流れを示すフローチャートである。
【図７】図６におけるステップＳ０３で実行されるインデックスデータ生成処理の流れを示すフローチャートである。
【図８】データ列記憶部１の記憶状態を示す図である。
【図９】第１の実施の形態におけるデータ列バッファ装置で実行される復元処理の流れを示すフローチャートである。
【図１０】データ列記憶部１の記憶状態の別の例を示す図である。
【図１１】第２の実施の形態におけるデータ列バッファ装置の概略構成を示すブロック図である。
【図１２】第２の実施の形態におけるデータ列バッファ装置１００Ａで実行されるデータ復元処理の流れを示すフローチャートである。
【図１３】第３の実施の形態におけるデータ列バッファ装置の概略構成を示すブロック図である。
【図１４】第３の実施の形態におけるデータ列バッファ装置１００Ｂで実行されるデータ列記憶処理の流れを示すフローチャートである。
【図１５】第４の実施の形態におけるデータ列バッファ装置の概略構成を示すブロック図である。
【図１６】本実施例におけるデータ列の構成を示す図である。
【図１７】データ列の具体例を示す図である。
【図１８】図１７に示したデータ列が入力された場合のデータ列記憶部１の状態を示す図である。
【符号の説明】
【０１２６】
１  データ列記憶部、２  入力部、２Ａ  レジスタ、２Ｂ  入力レジスタ、３  データ列比較部、４  出力部、５  復元データ記憶領域、６  出力一時記憶部、７  ＣＰＵ、１００, １００Ａ, １００Ｂ, １００Ｃ  データ列バッファ装置。
【図１】
2005208910.tif 000003
【図２】
2005208910.tif 000004
【図３】
2005208910.tif 000005
【図４】
2005208910.tif 000006
【図５】
2005208910.tif 000007
【図６】
2005208910.tif 000008
【図７】
2005208910.tif 000009
【図８】
2005208910.tif 000010
【図９】
2005208910.tif 000011
【図１０】
2005208910.tif 000012
【図１１】
2005208910.tif 000013
【図１２】
2005208910.tif 000014
【図１３】
2005208910.tif 000015
【図１４】
2005208910.tif 000016
【図１５】
2005208910.tif 000017
【図１６】
2005208910.tif 000018
【図１７】
2005208910.tif 000019
【図１８】
2005208910.tif 000020