(57)【要約】【課題】数値の組で表されるデータの記憶する際の高いデータ圧縮率を達成する。【解決手段】数値の組で表されるデータを、要素が０と１で表されるｎ次元配列のデータで表現する。その際、複数の要素をブロックごとにまとめ、そのブロックを数値の代わりに覚える。ブロックは、特定の要素の位置、パターン、ブロックに含まれる１あるいは０の個数の３つにより覚える。パターンは、例えば２次元配列データであれば、縦や横に並ぶ１の列を、縦パターンや横パターンのように与える。パターン、および特定の位置は、データに合わせ自由に決めることができる。更にブロックを覚える際には、特定の要素の位置の情報が同じものをまとめて覚えるのが効果的である。【選択図】図１
2008199565.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個の数値（ｘ１，ｘ２，  …  ，ｘｎ）で表されるデータを、（ｘ１，ｘ２，  …  ，ｘｎ）というデータが存在すれば（ｘ１，ｘ２，  …  ，ｘｎ）＝１、存在しなければ（ｘ１，ｘ２，  …  ，ｘｎ）＝０とする配列で表現し、全ての１あるいは０をいくつかのブロックに分け、全てのブロックを、ブロックの特定の要素の位置、ブロックのパターン、ブロックに含まれる１あるいは０の個数の３つにより覚えることで、全てのデータを覚えるデータ圧縮法である。
【請求項２】
２組の数値（ｘ，ｙ）で表されるデータを覚える際、（ｘ，ｙ）というデータが存在すればｘ行ｙ列の要素を１、存在しなければ０とする行列で表現し、全ての１あるいは０を、行列で見て単独、縦、横、斜め、四角の組み合わせによるパターンのどれかに属す複数のブロックに分け、全てのブロックを、行列で見てブロックの左上の１あるいは０の位置、ブロックのパターン、ブロックに含まれる１あるいは０の個数の３つにより覚えることで、全てのデータを覚えることによるデータ圧縮法
【請求項３】
画像のような３個の数値の組（ｘ，ｙ，ｚ）で表すことのできるデータを覚える際、（ｘ，ｙ，ｚ）というデータが存在すれば（ｘ，ｙ，ｚ）＝１、存在しなければ（ｘ，ｙ，ｚ）＝０と表現し、全ての１あるいは０を、３次元で見て単独、縦、横、奥、斜め、直方体の組み合わせによるパターンのどれかに属すブロックに分け、全てのブロックを、各ブロックの特定の要素の位置、ブロックのパターン、ブロックに含まれる１あるいは０の個数の３つにより覚えることで、全てのデータを覚えることによるデータ圧縮法
【請求項４】
ｎ個の数値で表されるデータを、数値の値に応じて覚える数値１つにかかるビット数が変化する可変長方式で覚える際に、現れる数値の個数ｎを覚えた後にｎ個分の数値を覚えるのではなく、ある特定の数値が数値の終端を表すと定め、ｎ個の数値を覚えた後に終端として定めた数値を覚えることを特徴とするデータ圧縮法
【発明の詳細な説明】
【技術分野】
【０００１】この発明は、数値の対や配列で表現される電子データの圧縮法に関する。
【背景技術】
【０００２】従来は、頻繁に現れる数値や、頻繁に現れる数値の並びに対し、頻繁に現れる数値には小さい符号を、頻繁に現れない数値には大きな符号を割り当て、数値の代わりにその符号を覚えていた。
【発明の開示】
【発明が解決しようとする課題】
【０００３】しかしながら、以上の技術によれば、符号の割当を余計に覚える必要があり、データのサイズがあまり小さくならなかった。
【課題を解決するための手段】
【０００４】以上の課題を解決するために、第一発明は、ｎ個の数値（ｘ１，ｘ２，  …  ，ｘｎ）で表されるデータを、（ｘ１，ｘ２，  …  ，ｘｎ）というデータが存在すれば（ｘ１，ｘ２，  …  ，ｘｎ）＝１、存在しなければ（ｘ１，ｘ２，  …  ，ｘｎ）＝０とする配列で表現し、全ての１あるいは０をいくつかのブロックに分け、全てのブロックを、ブロックの特定の要素の位置、ブロックのパターン、ブロックに含まれる１あるいは０の個数の３つにより覚えることで、全てのデータを覚えることを特徴とするデータ圧縮法である。
ブロックを覚える際には、要素の位置として覚える数値が小さい順に覚え、更に前のブロックに現れた数値との差分を覚えるなどの工夫を行い、含まれる１あるいは０の個数も、少なくとも２つは含まれるとわかっている場合には２減じた値を覚えるなどの工夫も行える。【０００５】また、第二発明は、要素が０と１であるｎ行ｍ列の行列で表されるデータを覚える際、全ての１あるいは０を、行列で見て単独、縦、横、斜め、四角の組み合わせによるパターンのどれかに属す複数のブロックに分け、全てのブロックを、行列で見てブロックの左上の１あるいは０の位置、ブロックのパターン、ブロックに含まれる１あるいは０の個数の３つにより覚えることで、全てのデータを覚えることを特徴とするデータの圧縮法である。
ブロックを覚える際には、要素の位置として覚える数値が小さい順に覚え、更に前のブロックに現れた数値との差分を覚えるなどの工夫を行い、含まれる１あるいは０の個数も、少なくとも２つは含まれるとわかっている場合には２減じた値を覚えるなどの工夫も行える。
また、２組の数値（ｘ，ｙ）で表されるデータを覚える際、（ｘ，ｙ）というデータが存在すればｘ行ｙ列の要素を１、存在しなければ０とする行列で表現することで、この圧縮法を適用できる。【０００６】また、第三発明は、画像のような３個の数値の組（ｘ，ｙ，ｚ）で表すことのできるデータを覚える際、（ｘ，ｙ，ｚ）というデータが存在すれば（ｘ，ｙ，ｚ）＝１、存在しなければ（ｘ，ｙ，ｚ）＝０と表現し、全ての１あるいは０を、３次元で見て単独、縦、横、奥、斜め、直方体の組み合わせによるパターンのどれかに属すブロックに分け、全てのブロックを、各ブロックの特定の要素の位置、ブロックのパターン、ブロックに含まれる１あるいは０の個数の３つにより覚えることで、全てのデータを覚えることを特徴とするデータの圧縮法である。
ブロックを覚える際には、要素の位置として覚える数値が小さい順に覚え、更に前のブロックに現れた数値との差分を覚えるなどの工夫を行い、含まれる１あるいは０の個数も、少なくとも２つは含まれるとわかっている場合には２減じた値を覚えるなどの工夫も行える。【０００７】また、第四発明は、覚える数値の数ｎが変化する場合に、ｎの値を覚えず、ｎ個の数値を覚えた後に、終端を表すと定めた値を覚えることで覚える数値の個数を得ることを特徴とする圧縮法である。
【発明の効果】
【０００８】第一発明、または、第二発明、第三発明によれば、配列や行列の要素である数値、および１あるいは０の要素は、ブロックでまとめて覚えることができるので、データ全体のサイズが小さくなる。【０００９】第四発明によれば、終端と定める数値を小さくすることで、いくつか続く数値の個数を覚えるよりも、覚える数値の値が小さくなる。
数値を覚え方を可変長方式とすることでデータ全体のサイズが小さくなる。
【発明を実施するための最良の形態】
【００１０】この第一発明および第二発明、第三発明の一実施形態を、図１、図２、図３、図４に示す。この図１では、配列の要素は１あるいは０であり、この場合は要素１の位置を覚えることで、行列全体のデータを覚えている。
網掛けされている１のまとまり１つ１つが、ブロックである。【００１１】図２は、ブロックの覚え方を示している。ブロックの特定の要素の位置、パターン、含まれる１あるいは０の数の順で、覚える数値が並んでいる。
ブロックの特定の要素の位置として、行列で見たブロックの要素の左上の位置を覚えている。【００１２】図３は、ブロックの特定の要素の位置を覚える際に現れる同じ数値をまとめている例である。同じ行要素が現れた場合、同じ行要素を持つブロックをまとめて、ブロックの最後尾に、終端を表す０を付加している。２つ目以降の列要素として０が現れることはないので、復元する際には、列要素として読み出す数値に０が現れるまでが、同じ行要素を持つブロックであるとわかる。【００１３】図４は、ブロックを効率良く覚えるために、ブロックを表現している数値をできるだけ小さくしている例である。例えば、１あるいは０が複数並ぶ場合にしか与えられないパターンが割り当てられたブロックであれば、含まれる１あるいは０の数として覚える各数値の値は２以上になるが、これらの値は２減じた値を覚えた方が、覚える数値が小さくなって圧縮には効果的である。更に、同じ行要素を持つものをまとめたものを新たなブロックと考え、そのブロックを行要素の番号で昇順に並べれば、各ブロックの行要素は、前に現れる行要素より必ず１大きくなり、覚える値を前に現れる行要素の番号との差分から１減じた値とすることで、覚える数値を小さくする。
また、同じ行要素を持つものをまとめた新しいブロック内に現れる列要素は、左に現れる列要素よりも必ず１大きいので、覚える値は左に現れる列要素の番号との差分とし、覚える数値を小さくする。ただし、終端として０を付加したので、覚える数値として０が現れないよう１減じることはしない。
図３、図４で表される操作は、用いるデータにより行うかどうかを決める。【００１４】第四発明の一実施形態を図３に示す。複数ブロックをまとめて新たなブロックを作る場合に、まとめたブロックの個数を覚える代わりに、終端を表す０を付加する。
この値は０でなくともよい。終端を表す数値は、ブロックに表れない数値とする。
ブロックの数値を終端の値が出現するまで順に読むことで、ブロックを復元できる。
これはブロックに限らず、複数の数値をまとめて覚える際に実施できる。【００１５】「実施形態の効果」
この実態形態によれば、要素がブロックでまとめられている分、データとして覚える量が減る。したがって、データの容量が小さくなり、データの圧縮がなされる。【００１６】「他の実施形態」
この圧縮法は、隣接リストや行列で表されるデータ、例えばＷｅｂ上のリンクデータや画像のデータを覚える際に活用できる。更に、パターンを覚える際には、１が単独パターンを表し、０１が縦パターンを表すなど、各パターンに各パターンを表す符号を割り当てるか、ある特定の数値が各パターンを表すと決めることでパターンを判別できる。
更に、縦パターンを持つブロックを複数連続で覚えるなどの工夫も行える。これは、含まれる１あるいは０の値を複数覚えることで行える。
【産業上の利用可能性】
【０００＊】
【図面の簡単な説明】
【００１７】
【図１】この発明の一実施形態を示す、要素が１あるいは０である行列のデータの例である。
【図２】この発明の一実施形態を示す、図１のブロックを覚える際の、数値の表現の例である。
【符号の説明】
【００１８】      １  要素が１または０である行列のデータ
２  ブロック
３  パターン
４  行要素
５  列要素
６  含まれる１あるいは０の数
【図１】
2008199565.tif 000003
【図２】
2008199565.tif 000004
【図３】
2008199565.tif 000005
【図４】
2008199565.tif 000006
【手続補正書】
【提出日】平成19年4月20日(2007.4.20)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
【図１】この発明の一実施形態を示す、要素が１あるいは０である行列のデータの例である。
【図２】この発明の一実施形態を示す、図１のブロックを覚える際の、数値の表現の例である。
【図３】この発明の一実施形態を示す、始点番号が同じ複数のブロックをまとめて覚えた例である。複数のブロックをまとめた場合，先頭以外のブロックの始点番号は覚える必要がないので省略し、代わりに、まとめられた複数のブロックの最後尾に０を付加する。
【図４】この発明の一実施形態を示す、まとめられたブロックを覚える際の数値を小さくした例である。始点番号は、前に現れる始点番号との差をとった値となり、終点番号は、前に現れる終点番号との差をとった値となる。始点番号、終点番号共に、前に現れる番号がない先頭の番号は、その番号をそのまま覚える。