(57)【要約】【課題】変換テーブルにデータ構造として形成されるパスカルの三角形の節点の値Ｃを、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ' にすることにより、圧縮対象データが大きくなり系列長ｇが長くなっても、計算の際に必要となる演算幅ｈを節約でき、当該装置の規模を抑え、計算負担も軽減することができるデータ圧縮方法，データ圧縮装置，コンピュータプログラム及びコンピュータプログラム記録媒体を提供する。【解決手段】変換テーブルにデータ構造として形成されるパスカルの三角形の節点の値Ｃを、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ' にし、当該変換テーブルに基づき、圧縮対象データを、データ量が圧縮された圧縮データへ変換する。【選択図】図５
2007312323.tif 000002
【特許請求の範囲】
【請求項１】
節点（ｉ，ｊ）（但し、ｉ及びｊは変数）の値Ｃを有するパスカルの三角形が形成されたデータ構造を備える変換テーブルに基づき、圧縮対象データを、データ量が圧縮された圧縮データへ変換するデータ圧縮方法において、
前記節点（ｉ，ｊ）の値Ｃは、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ' であることを特徴とするデータ圧縮方法。
【請求項２】
前記変換テーブルは、更に、前記三角形の各節点間を連結する有向グラフが形成されているデータ構造を備え、
前記圧縮対象データに基づき、前記三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定めるステップと、
前記圧縮対象データを表す２進系列に含まれた０又は１を下位桁（又は上位桁）から順次抽出するステップと、
０又は１のいずれを抽出したかを順次判断するステップと、
前記始点から終点まで、０を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動し、１を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動するステップと、
１を抽出したと判断した場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ’を順次抽出するステップと、
抽出した値Ｃ’を順次加算するステップと、
値Ｃ’の加算した総和を、前記圧縮データとして出力するステップとを含むことを特徴とする請求項１に記載のデータ圧縮方法。
【請求項３】
前記値Ｃ’は、下式により規定されることを特徴とする請求項１又は２に記載のデータ圧縮方法。
Ｌ＝１＋ｆｌｏｏｒ（ｌｏｇ2 Ｃ）
ｚ＝２L-d
ｑ＝ｆｌｏｏｒ（Ｃ／ｚ）
ｒ＝Ｃ−ｑ＊ｚ
Ｃ’ ＝ｑ＊ｚ＋ｍｉｎ（ｒ，１）＊ｚ
但し、式中、Ｃは節点（ｉ，ｊ）の値、ｄは１が含まれる前記所定の上位桁数、関数ｆｌｏｏｒ（Ｃ／ｚ）はＣ／ｚ以下のうち最大の整数を返す関数であり、関数ｍｉｎ（ｒ，１）はｒ及び１のうち小さい方を返し、ｒ＝０の場合はＣ’＝Ｃで返し、ｒ＞０の場合はＣ’＝ｑ＊ｚ＋ｚで返す関数である。
【請求項４】
節点（ｉ，ｊ）（但し、ｉ及びｊは変数）の値Ｃを有するパスカルの三角形が形成されたデータ構造を備える変換テーブルと、該変換テーブルに基づき、圧縮対象データをデータ量が圧縮された圧縮データへ変換する手段とを備えるデータ圧縮装置において、
前記変換テーブルは、前記節点（ｉ，ｊ）の値Ｃが、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ’であり、前記三角形の各節点間を連結する有向グラフが形成されているデータ構造を備え、
前記圧縮対象データに基づき、前記三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定める手段と、
前記圧縮対象データを表す２進系列に含まれた０又は１を下位桁（又は上位桁）から順次抽出する手段と、
０又は１のいずれを順次抽出したかを判断する手段と、
前記始点から終点まで、０を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動し、１を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動する手段と、
１を抽出したと判断した場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ’を順次抽出する手段と、
抽出した値Ｃ’を順次加算する手段と、
値Ｃ’の加算した総和を、前記圧縮データとして出力する手段とを備えることを特徴とするデータ圧縮装置。
【請求項５】
節点（ｉ，ｊ）（但し、ｉ及びｊは変数）の値Ｃを有するパスカルの三角形が形成されたデータ構造を備える変換テーブルに基づき、圧縮対象データをデータ量が圧縮された圧縮データへ変換させるコンピュータプログラムにおいて、
前記変換テーブルは、前記節点（ｉ，ｊ）の値Ｃが、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ’であり、前記三角形の各節点間を連結する有向グラフが形成されているデータ構造を備え、
コンピュータに、前記圧縮対象データに基づき、前記三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定めさせるステップと、
コンピュータに、前記圧縮対象データを表す２進系列に含まれた０又は１を下位桁（又は上位桁）から順次抽出させるステップと、
コンピュータに、０又は１のいずれを抽出したかを順次判断させるステップと、
コンピュータに、前記始点から終点まで、０を抽出したと判断させた場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動させ、１を抽出したと判断させた場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動させるステップと、
コンピュータに、１を抽出したと判断させた場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ’を順次抽出させるステップと、
コンピュータに、抽出した値Ｃ’を順次加算させるステップと、
コンピュータに、値Ｃ’の加算した総和を、前記圧縮データとして出力させるステップとを実行させることを特徴とするコンピュータプログラム。
【請求項６】
節点（ｉ，ｊ）（但し、ｉ及びｊは変数）の値Ｃを有するパスカルの三角形が形成されたデータ構造を備える変換テーブルに基づき、圧縮対象データをデータ量が圧縮された圧縮データへ変換させるコンピュータプログラムを記録してある、コンピュータでの読み取りが可能な記録媒体において、
前記変換テーブルは、前記節点（ｉ，ｊ）の値Ｃが、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ’であり、前記三角形の各節点間を連結する有向グラフが形成されているデータ構造を備え、
コンピュータに、前記圧縮対象データに基づき、前記三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定めさせるステップと、
コンピュータに、前記圧縮対象データを表す２進系列に含まれた０又は１を下位桁（又は上位桁）から順次抽出させるステップと、
コンピュータに、０又は１のいずれを抽出したかを順次判断させるステップと、
コンピュータに、前記始点から終点まで、０を抽出したと判断させた場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動させ、１を抽出したと判断させた場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動させるステップと、
コンピュータに、１を抽出したと判断させた場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ’を順次抽出させるステップと、
コンピュータに、抽出した値Ｃ’を順次加算させるステップと、
コンピュータに、値Ｃ’の加算した総和を、前記圧縮データとして出力させるステップとを実行させるコンピュータプログラムが記録されていることを特徴とするコンピュータでの読み取りが可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、圧縮対象データを、データ量が圧縮された圧縮データへ変換するデータ圧縮方法、該方法を実行するための装置、コンピュータを動作させ前記方法を実行させるためのコンピュータプログラム、及び該コンピュータプログラムを記録してある、コンピュータでの読み取りが可能な記録媒体に関する。
【背景技術】
【０００２】
従来、画像データ又は音声データなどの大容量データをコンピュータで扱う場合、大容量データのデータ量を符号化圧縮して必要な処理を行い、後に伸張することにより、処理の負荷軽減を行っている。
【０００３】
このようなデータの圧縮方法としては、パスカルの三角形を用いた数え上げ符号によるデータ圧縮方法が知られている。図１はパスカルの三角形の配列を示す概念図、図２はパスカルの三角形を用いた従来のデータ圧縮方法を説明する概念図である。
【０００４】
従来のデータ圧縮方法で用いるパスカルの三角形は、図１の如く、節点（ｉ，ｊ）が（ｉ＝０，１，２，…ｎ）（ｊ＝０，１，２，…，ｉ）（但し、ｎは自然数、ｉは頂点から底辺へ向かう距離，ｊは左辺を構成する節点から右辺へ向かう距離である。）に配置された三角形であり、図２の如く、頂点，左辺及び右辺を構成する節点の値が１であり、それ以外の節点の値が、節点（ｉ，ｊ）の値＝節点（ｉ−１，ｊ−１）の値＋節点（ｉ−１，ｊ）の値という二項係数の関係式により定まる。
【０００５】
そして、従来のデータ圧縮方法では、パスカルの三角形の頂点を始点とし、該三角形の底辺を構成するいずれかの節点を終点とし、圧縮対象データを表す２進系列に含まれた０又は１を順次抽出し、０を抽出した場合は、一の節点から底辺への一の方向を示す有向グラフにより連結された次節点へ移動し、１を抽出した場合は、一の節点から底辺への他の方向を示す有向グラフにより連結された次節点へ移動し、始点から終点までの有向グラフを移動する際、０を抽出した場合、一の節点の値と次節点の値との差分をとり、差分の総和を算出し、算出した総和から圧縮したデータを得ることができる。
【０００６】
例えば、圧縮対象データを表す２進系列「１０１００００」に基づき、変換テーブルの節点を、始点から終点まで移動すると、図２の如く、総和は（２−１）＋（６−３）＋（１０−６）＋（１５−１０）＋（２１−１５）＝１９（２進数表現で１００１１）となり、これを圧縮データとして出力する。
【０００７】
このように、従来のデータ圧縮方法は、圧縮対象データをデータ量が圧縮された圧縮データに符号圧縮することができる（例えば特許文献１）。
【特許文献１】特開２００３−１５８４５８
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかし、特許文献１に記載されたデータ圧縮方法において、節点の値の差分及び加算をするには、圧縮対象データを表す２進系列の系列長ｇと同程度の演算幅ｈを有する演算器を用いる必要があり、圧縮対象データが大きくなれば、系列長ｇも長くなるため、ｈ≧ｇを満たす演算幅ｈを有する演算器が必要になる。上述した例では、圧縮対象データを表す２進系列「１０１００００」を計算するために、７ビット程度の演算幅ｈが必要になる。
【０００９】
また、従来のデータ圧縮方法では、節点の値の２進系列のうち連続する１のみを計算することにより、演算器の演算幅ｈを節約しようとする方法も併用できるが、１が連続していない系列の場合は、演算幅ｈを節約することができない。
【００１０】
従って、従来のデータ圧縮方法は、系列長３２ビット以上の大容量データを圧縮する場合、３２ビットの演算器を実装するＣＰＵを備える個人向けコンピュータでは実行させることができず、別途、３２ビット以上の演算器を備えた専用の装置が必要になることから、実用に適さないという問題がある。
【００１１】
また、３２ビット以上の演算器を備えた装置であっても、圧縮対象データが大きくなり系列長ｇが長くなる場合、最大でｇビット程度の演算幅ｈを計算することになるので、当該装置の規模及び計算負担が大きくなり、結果を出力するまで長い時間を要するという問題もある。
【００１２】
本発明はかかる事情に鑑みてなされたものであり、その目的とするところは、変換テーブルにデータ構造として形成されるパスカルの三角形の節点の値Ｃを、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ' にすることにより、圧縮対象データが大きくなり系列長ｇが長くなっても、計算の際に必要となる演算幅ｈを節約でき、当該装置の規模を抑え、計算負担も軽減することができるデータ圧縮方法，データ圧縮装置，コンピュータプログラム及びコンピュータでの読み取りが可能な記録媒体を提供することにある。
【００１３】
また、本発明の他の目的は、変換テーブルにデータ構造として形成されるパスカルの三角形の節点の値Ｃ' を、所定の規則に基づき、順次加算していき、節点の値Ｃ' の加算した総和を圧縮データとして出力することにより、圧縮対象データが大きくなり系列長ｇが長くなっても、計算の際に必要となる演算幅ｈを節約でき、当該装置の規模を抑え、計算負担も軽減することができるデータ圧縮方法，データ圧縮装置，コンピュータプログラム及びコンピュータでの読み取りが可能な記録媒体を提供することにある。
【００１４】
また、本発明の他の目的は、変換テーブルにデータ構造として形成されるパスカルの三角形の節点の値Ｃ' を、所定の式により規定することができるデータ圧縮方法を提供することにある。
【課題を解決するための手段】
【００１５】
上記課題を解決するために第１発明に係るデータ圧縮方法は、節点（ｉ，ｊ）（但し、ｉ及びｊは変数）の値Ｃを有するパスカルの三角形が形成されたデータ構造を備える変換テーブルに基づき、圧縮対象データを、データ量が圧縮された圧縮データへ変換するデータ圧縮方法において、前記節点（ｉ，ｊ）の値Ｃは、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ' であることを特徴とする。
【００１６】
また、第２発明に係るデータ圧縮方法は、前記変換テーブルは、更に、前記三角形の各節点間を連結する有向グラフが形成されているデータ構造を備え、前記圧縮対象データに基づき、前記三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定めるステップと、前記圧縮対象データを表す２進系列に含まれた０又は１を下位桁（又は上位桁）から順次抽出するステップと、０又は１のいずれを抽出したかを順次判断するステップと、前記始点から終点まで、０を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動し、１を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動するステップと、１を抽出したと判断した場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ' を順次抽出するステップと、抽出した値Ｃ' を順次加算するステップと、値Ｃ' の加算した総和を、前記圧縮データとして出力するステップとを含むことを特徴とする。
【００１７】
また、第３発明に係るデータ圧縮方法は、前記値Ｃ' は、下式により規定されることを特徴とする。
Ｌ＝１＋ｆｌｏｏｒ（ｌｏｇ2 Ｃ）
ｚ＝２L-d
ｑ＝ｆｌｏｏｒ（Ｃ／ｚ）
ｒ＝Ｃ−ｑ＊ｚ
Ｃ’＝ｑ＊ｚ＋ｍｉｎ（ｒ，１）＊ｚ
但し、式中、Ｃは節点（ｉ，ｊ）の値、ｄは１が含まれる前記所定の上位桁数、関数ｆｌｏｏｒ（Ｃ／ｚ）はＣ／ｚ以下のうち最大の整数を返す関数であり、関数ｍｉｎ（ｒ，１）はｒ及び１のうち小さい方を返し、ｒ＝０の場合はＣ’ ＝Ｃで返し、ｒ＞０の場合はＣ’＝ｑ＊ｚ＋ｚで返す関数である。
【００１８】
また、第４発明に係るデータ圧縮装置は、節点（ｉ，ｊ）（但し、ｉ及びｊは変数）の値Ｃを有するパスカルの三角形が形成されたデータ構造を備える変換テーブルと、該変換テーブルに基づき、圧縮対象データをデータ量が圧縮された圧縮データへ変換する手段とを備えるデータ圧縮装置において、前記変換テーブルは、前記節点（ｉ，ｊ）の値Ｃが、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ' であり、前記三角形の各節点間を連結する有向グラフが形成されているデータ構造を備え、前記圧縮対象データに基づき、前記三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定める手段と、前記圧縮対象データを表す２進系列に含まれた０又は１を下位桁（又は上位桁）から順次抽出する手段と、０又は１のいずれを順次抽出したかを判断する手段と、前記始点から終点まで、０を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動し、１を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動する手段と、１を抽出したと判断した場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ’を順次抽出する手段と、抽出した値Ｃ’を順次加算する手段と、値Ｃ’の加算した総和を、前記圧縮データとして出力する手段とを備えることを特徴とする。
【００１９】
また、第５発明に係るコンピュータプログラムは、節点（ｉ，ｊ）（但し、ｉ及びｊは変数）の値Ｃを有するパスカルの三角形が形成されたデータ構造を備える変換テーブルに基づき、圧縮対象データをデータ量が圧縮された圧縮データへ変換させるコンピュータプログラムにおいて、前記変換テーブルは、前記節点（ｉ，ｊ）の値Ｃが、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ' であり、前記三角形の各節点間を連結する有向グラフが形成されているデータ構造を備え、コンピュータに、前記圧縮対象データに基づき、前記三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定めさせるステップと、コンピュータに、前記圧縮対象データを表す２進系列に含まれた０又は１を下位桁（又は上位桁）から順次抽出させるステップと、コンピュータに、０又は１のいずれを抽出したかを順次判断させるステップと、コンピュータに、前記始点から終点まで、０を抽出したと判断させた場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動させ、１を抽出したと判断させた場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動させるステップと、コンピュータに、１を抽出したと判断させた場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ’を順次抽出させるステップと、コンピュータに、抽出した値Ｃ’を順次加算させるステップと、コンピュータに、値Ｃ’の加算した総和を、前記圧縮データとして出力させるステップとを実行させることを特徴とする。
【００２０】
第６発明に係るコンピュータでの読み取りが可能な記録媒体は、節点（ｉ，ｊ）（但し、ｉ及びｊは変数）の値Ｃを有するパスカルの三角形が形成されたデータ構造を備える変換テーブルに基づき、圧縮対象データをデータ量が圧縮された圧縮データへ変換させるコンピュータプログラムを記録してある、コンピュータでの読み取りが可能な記録媒体において、前記変換テーブルは、前記節点（ｉ，ｊ）の値Ｃが、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ' であり、前記三角形の各節点間を連結する有向グラフが形成されているデータ構造を備え、コンピュータに、前記圧縮対象データに基づき、前記三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定めさせるステップと、コンピュータに、前記圧縮対象データを表す２進系列に含まれた０又は１を下位桁（又は上位桁）から順次抽出させるステップと、コンピュータに、０又は１のいずれを抽出したかを順次判断させるステップと、コンピュータに、前記始点から終点まで、０を抽出したと判断させた場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動させ、１を抽出したと判断させた場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動させるステップと、コンピュータに、１を抽出したと判断させた場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ’を順次抽出させるステップと、コンピュータに、抽出した値Ｃ’を順次加算させるステップと、コンピュータに、値Ｃ’の加算した総和を、前記圧縮データとして出力させるステップとを実行させるコンピュータプログラムが記録されていることを特徴とする。
【００２１】
第１発明にあっては、変換テーブルにデータ構造として形成されるパスカルの三角形の節点の値Ｃを、２進数表現で所定の上位桁のみに１が含まれる数で表される値Ｃ' にし、当該変換テーブルに基づき、圧縮対象データを、データ量が圧縮された圧縮データへ変換する。
【００２２】
また、第２発明，第４発明，第５発明及び第６発明にあっては、変換テーブルにデータ構造として形成されるパスカルの三角形の節点の値Ｃ' を、所定の規則に基づき、順次加算し、節点の値Ｃ’の加算した総和を圧縮データとして出力することにより、圧縮対象データを圧縮データへ変換する。
【００２３】
また、第３発明にあっては、変換テーブルにデータ構造として形成されるパスカルの三角形の節点の値Ｃ' を、所定の式により規定する。
【発明の効果】
【００２４】
本発明にあっては、圧縮対象データが大きくなり系列長ｇが長くなっても、計算の際に必要となる演算幅ｈを節約でき、当該装置の規模を抑え、計算負担も軽減することができる。
【発明を実施するための最良の形態】
【００２５】
実施の形態１．
以下、本発明をその実施の形態を示す図面に基づいて説明する。
まず、本発明に係るデータ圧縮装置の構成を説明する。図３は本発明に係るデータ圧縮装置を具現化するコンピュータのブロック図である。図３に示すように、本発明に係るデータ圧縮装置を具現化するコンピュータ１は、少なくとも、バス１０を介して以下のハードウェア各部が接続されており、記憶手段１２に格納されたプログラムに従って種々のソフトウェア的機能を実行するＣＰＵ（中央演算装置）１１、プログラム等を格納する記憶手段１２、ＳＲＡＭ・フラッシュメモリ等からなり、プログラム処理において一時的に発生したデータを一時記憶するＲＡＭ（メモリ）１３、マウス、キーボード等の入力手段１４、液晶表示装置・ＣＲＴディスプレイ等の表示装置、又はプリンタ等の印刷装置であり、演算結果を表示し、又は印刷して出力する出力手段１５、及びコンピュータ１で使用するプログラムを記録した可搬型記録媒体１７であり、ＤＶＤ、ＣＤ−ＲＯＭ等が該当する補助記憶手段１６で構成される。また、補助記憶手段１６は、コンピュータ１で使用する変換テーブルＴを記録する可搬型記録媒体１７等も含む。
【００２６】
入力手段１４は、外部から圧縮対象データ、及び１が含まれる上位桁数ｄを受け付け、ＲＡＭ１３へ出力する。ＲＭＡ１３は、受け付けた圧縮対象データ、及び１が含まれる上位桁数ｄを記憶する。
【００２７】
補助記憶手段１６は、可搬型記録媒体１７から、コンピュータ１で使用するプログラム及び変換テーブルＴを読み出し、記憶手段１２へ出力する。記憶手段１２は、受け付けたプログラム及び変換テーブルＴを格納する。
【００２８】
ＣＰＵ１１は、記憶手段１２に格納しているプログラム及び変換テーブルＴ、並びにＲＡＭ１３に記憶している圧縮対象データ及び１が含まれる上位桁数ｄを読み出す。
【００２９】
また、ＣＰＵ１１は、圧縮対象データを表す２進系列の系列長ｇ及び１の個数に基づき、読み出した変換テーブルＴがデータ構造として備える三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定める。
【００３０】
また、ＣＰＵ１１は、圧縮対象データを表す２進系列に含まれた０又は１を下位桁（又は上位桁）から順次抽出し、０又は１のいずれを抽出したかを順次判断し、始点から終点まで、０を抽出したと判断した場合、読み出した変換テーブルＴがデータ構造として備える三角形の、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動し、１を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動し、１を抽出したと判断した場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ’を順次抽出し、抽出した値Ｃ’を順次加算し、値Ｃ’の加算した総和を出力手段１５へ出力する。
【００３１】
出力手段１５は、ＣＰＵ１１から受け付けた総和を、前記圧縮データとして出力する。
【００３２】
次に、変換テーブルＴがデータ構造として備える三角形の概念について説明する。まず、節点（ｉ，ｊ）の値ＣをＣ’に、及びオフセット（ｊ）の値ＦをＦ’に桁上げをするために用いる関数Ｒｏｕｎｄｕｐ（ｘ，ｄ）について説明しておく。ここで、関数Ｒｏｕｎｄｕｐ（ｘ，ｄ）とは、値ｘ及び１が含まれる上位桁数ｄを入力した場合、２進数表現で上位ｄ桁にしか１を含まず、値ｘ以上のうち最小の整数を返す関数である。
【００３３】
Ｌ＝１＋ｆｌｏｏｒ（ｌｏｇ2 ｘ）
ｚ＝２L-d
ｑ＝ｆｌｏｏｒ（ｘ／ｚ）
ｒ＝ｘ−ｑ＊ｚ
ｘ’ ＝ｑ＊ｚ＋ｍｉｎ（ｒ，１）＊ｚ
Ｒｏｕｎｄｕｐ（ｘ，ｄ）＝ｘ’
【００３４】
但し、式中、ｄは１が含まれる上位桁数、関数ｆｌｏｏｒ（ｘ／ｚ）はｘ／ｚ以下のうち最大の整数を返す関数であり、関数ｍｉｎ（ｒ，１）はｒ及び１のいずれか小さい方を返し、ｒ＝０の場合はｘ’ ＝ｘで返し、ｒ＞０の場合はｘ’ ＝ｑ＊ｚ＋ｚで返す関数である。
【００３５】
次に、変換テーブルＴがデータ構造として備える三角形の生成手順について説明する。図４は本発明に用いる変換テーブルの生成処理の手順を説明するフローチャート、図５は本発明に用いる変換テーブルの一例を説明する概念図、図６は関数Ｒｏｕｎｄｕｐ（ｘ，ｄ）により切り上げられた値の一例を説明する概念図である。尚、本実施の形態では、変換テーブルＴは、外部装置（図示せず、以下同様）により生成され可搬型記録媒体１７に記録されているが、これに限らず、コンピュータ１が自ら生成するようにしても良い。
【００３６】
外部装置のＣＰＵは、生成の終了段数ａを受け付け（Ｓ１０１）、頂点（０，０）の値を１にする（Ｓ１０２）。変数ｉに１を加え（Ｓ１０３）、変数ｉが終了段数ａ−１より大であるか否かを判断し（Ｓ１０４）、大であると判断した場合（Ｓ１０４でＹＥＳ）、処理を終了する。
【００３７】
他方、ＣＰＵは、大ではないと判断した場合（Ｓ１０４でＮＯ）、変数ｊに１を加え（Ｓ１０５）、変数ｊが変数ｉより大であるか否かを判断し（Ｓ１０６）、大であると判断した場合（Ｓ１０６でＹＥＳ）、ステップＳ１０３へ戻り変数ｉに１を加える。
【００３８】
他方、ＣＰＵは、大ではないと判断した場合（Ｓ１０６でＮＯ）、変数ｊが０又は変数ｉと一致するか否かを判断し（Ｓ１０７）、一致すると判断した場合（Ｓ１０７でＹＥＳ）、節点（ｉ，ｊ）の値を１にして（Ｓ１０８）、ステップＳ１０５へ戻る。
【００３９】
他方、ＣＰＵは、一致しないと判断した場合（Ｓ１０７でＮＯ）、節点（ｉ，ｊ）の値Ｃ＝節点（ｉ−１，ｊ−１）の値Ｃ’＋節点（ｉ−１，ｊ）の値Ｃ’を計算する（Ｓ１０９）。
【００４０】
ＣＰＵは、更に、算出した値Ｃを引数にした関数Ｒｏｕｎｄｕｐ（Ｃ，ｄ）を用いて値Ｃ’を算出し（Ｓ１１０）、節点（ｉ，ｊ）の値を値Ｃ’にして（Ｓ１１１）、ステップＳ１０５へ戻る。
【００４１】
例えば、「２進数表現で上位桁３ビットのみに１が含まれる数で表される数」である節点（６，３）は以下のように規定される。
【００４２】
まず、節点（６，３）の値＝節点（５，２）の値＋節点（５，３）の値を計算し、次に、算出された節点（６，３）の値を上述した関数Ｒｏｕｎｄｕｐ（３５，３）により切り上げる。その結果、節点（６，３）の値Ｃ’「４０（２進数表現で１０１０００）」に規定される。 
【００４３】
また、節点（７，２）の値Ｃ’は、節点（６，１）の値「６（２進数表現で１１０）」＋節点（６，２）の値「１６（２進数表現で１００００）」を計算し、算出した値を関数Ｒｏｕｎｄｕｐ（２２，３）で切り上げることにより規定される。
【００４４】
その結果、図５に示す如く、点線で囲んだ節点の値が切り上げられ、本発明に用いる変換テーブルＴの節点の値Ｃ’は、図２に示すパスカルの三角形とは異なり、節点（ｉ，ｊ）の値≧節点（ｉ−１，ｊ−１）の値＋節点（ｉ−１，ｊ）の値という関係式を満たし、かつ「２進数表現で所定の上位桁ビットのみに１が含まれる数で表される数」に規定される。
【００４５】
具体的には、図６に示す如く、演算器が０を無視して１のみを用いてｄビットのみを加算するようにすれば、圧縮対象データの系列長ｇが長くなっても、演算幅を１＋２＊ｆｌｏｏｒ（ｌｏｇ2 ｇ）程度まで節約できる。
【００４６】
つまり、関数Ｒｏｕｎｄｕｐ（ｘ，ｄ）による切り上げでは、ｘに最大（１＋２1-d ）の係数が掛かり、切り上げを三角形の頂点から底辺までｇ回繰り返すと、その係数は最大（１＋２1-d ）g となるが、１が含まれる上位桁数ｄを１＋ｆｌｏｏｒ（ｌｏｇ2 ｇ）以上の整数とすれば、この係数は１に漸近するので、データ圧縮の効率は劣化しない。また、符号化を三角形の頂点から開始すれば、加算する数は減ってゆくことはないので、足される数（それまでの合計）の１／（ｇ−１）以上であり、生じ得る桁上げはｆｌｏｏｒ（ｌｏｇ2 ｇ）ビット以下に限定される。符号化に必要な演算幅ｈは１が含まれる上位桁数ｄと桁上げの合計であり、１＋２＊ｆｌｏｏｒ（ｌｏｇ2 ｇ）程度まで節約できる。
【００４７】
次に、コンピュータ１が、圧縮対象データに基づき、変換テーブルＴがデータ構造として備える三角形の始点及び終点を指定する手順、及び、同オフセット（ｊ）の値Ｆ’ を規定する手順を説明する。図７は始点及び終点の指定処理の手順を説明するフローチャート、図８はオフセット（ｊ）の値の規定処理の手順を説明するフローチャート、図９は本発明に用いる始点，終点及びオフセットの値を定めた変換テーブルの一例を説明する概念図である。
【００４８】
まず、入力手段１４は、外部から圧縮対象データを表す２進系列及び１が含まれる上位桁数ｄを受け付け、ＲＡＭ１３へ出力する。ＲＡＭ１３は、受け付けた圧縮対象データ、及び１が含まれる上位桁数ｄを記憶する。
【００４９】
ＣＰＵ１１は、記憶手段１２に格納している変換テーブルＴを読み出して、読み出した変換テーブルＴがデータ構造として備える三角形の頂点（０，０）を始点として指定する（Ｓ２０１）。
【００５０】
また、ＣＰＵ１１は、ＲＡＭ１３から読み出した圧縮対象データを表す２進系列の系列長ｇ及び１の個数を抽出し（Ｓ２０２）、頂点（０，０）から、抽出した系列長ｇだけ下位へ移動し（Ｓ２０３）、移動先の辺を底辺に定める。更に、底辺の左頂点（ｉ，０）から、抽出した１の個数だけ右へ移動し（Ｓ２０４）、移動先の節点（ｉ，ｊ）を終点として指定する。
【００５１】
このように、コンピュータ１は、変換テーブルＴがデータ構造として備える三角形の始点及び終点を指定する。
【００５２】
次に、ＣＰＵ１１は、オフセット（ｊ）の値Ｆ’を底辺から１段下に、底辺を構成する節点（ｉ，ｊ）（終点を含む）に対応して、以下のように規定する。尚、オフセット（ｊ）の値Ｆ’は、変換テーブルＴで用いるために生成された重みに対応する値であって、オフセット（０）は重み０，オフセット（１）は１の値，…夫々対応している。また、重みは、圧縮対象データを表す２進系列の１の個数であって、本発明に係るデータ圧縮方法により圧縮された圧縮データを伸張へ可逆するために用いるパラメータである。
【００５３】
ＣＰＵ１１は、圧縮対象データを表す２進系列及び変換テーブルＴから夫々、系列長ｇ，上位桁数ｄ，底辺の左頂点（ｉ，０）の値及び底辺の節点（ｉ，ｊ）の個数ｋを抽出し（Ｓ３０１）、オフセット（０）の値を０にし（Ｓ３０２）、変数ｊに１を加え（Ｓ３０３）、変数ｊが底辺の節点（ｉ，ｊ）の個数ｋ−１より大であるか否かを判断し（Ｓ３０４）、大であると判断した場合（Ｓ３０４でＹＥＳ）、処理を終了する。
【００５４】
他方、ＣＰＵ１１は、大ではないと判断した場合（Ｓ３０４でＮＯ）、オフセット（ｊ）の値Ｆ＝オフセット（ｊ−１）の値Ｆ’＋底辺の節点（ｉ，ｊ−１）の値Ｃ’を計算する（Ｓ３０５）。
【００５５】
ＣＰＵ１１は、更に、算出した値Ｆを引数にした関数Ｒｏｕｎｄｕｐ（Ｆ，ｄ）に基づき値Ｆ’を算出し（Ｓ３０６）、オフセット（ｊ）の値を値Ｆ’にして（Ｓ３０７）、ステップＳ３０３へ戻る。
【００５６】
このように、コンピュータ１は、変換テーブルＴがデータ構造として備える三角形のオフセット（ｊ）の値Ｆ’を規定する。
【００５７】
例えば、節点の値が「２進数表現で上位桁３ビットのみに１が含まれる数」であって、かつ圧縮対象データを表す２進系列が「１０１００００」である場合、系列長ｇは７ビットであり、配列されている１の個数ｋは２個であるから、図９の如く、頂点（０，０）から７だけ下位に移動した先、節点（７，０）〜節点（７，７）で構成される辺が底辺に定まる。また、底辺の左頂点（７，０）から、２だけ移動した先、節点（７，２）が終点に定まる。
【００５８】
また、オフセット（ｊ）は、上述定めた底辺から一段下に規定され、オフセット（０）の値Ｆ＝０，オフセット（１）の値Ｆ＝オフセット（０）の値Ｆ’＋節点（７，０）の値Ｃ’ ，オフセット（２）の値Ｆ＝オフセット（１）の値Ｆ’＋節点（７，１）の値Ｃ’，…と計算していき、更に関数Ｒｏｕｎｄｕｐ（Ｆ，ｄ）により値Ｆ’へ切り上げる。
【００５９】
その結果、図９の如く、オフセット（０）＝０，オフセット（１）＝１，オフセット（２）＝８，オフセット（３）＝３２，オフセット（４）＝８０，オフセット（５）＝１２８，オフセット（６）＝１６０，オフセット（７）＝１９２に定まる。
【００６０】
次に、コンピュータ１が、始点から終点まで、変換テーブルＴがデータ構造として備える三角形の節点（ｉ，ｊ）を順次移動し、節点（ｉ，ｊ）の値を順次加算し、加算した総和を圧縮データとして出力する手順を、上述した節点の値が「２進数表現で上位桁３ビットのみに１が含まれる数」であって、かつ圧縮対象データを表す２進系列が「１０１００００」である場合を例として説明する。図１０は実施の形態１に係るデータ圧縮方法を説明する概念図である。
【００６１】
まず、ＣＰＵ１１は、ＲＡＭ１３から読み出した圧縮対象データを表す２進系列「１０１００００」で含まれた０又は１を下位桁から上位へ順次抽出していく。
【００６２】
ＣＰＵ１１は、圧縮対象データを表す２進系列の最下位桁０を抽出し、０を抽出したと判断して、頂点（０，０）から底辺への一の方向である左下方向（以下、同様）を示す有向グラフにより連結された次節点（１，０）へ移動する。同様に下位桁から上位へ符号「０，０，０」を順次抽出し、同様に、節点（１，０）から節点（２，０）へ、節点（２，０）から節点（３，０）へ、節点（３，０）から節点（４，０）へ移動する。
【００６３】
ＣＰＵ１１は、次の上位桁１を抽出し、１を抽出したと判断して、節点（４，０）から底辺への他の方向である右下方向（以下、同様）を示す有向グラフにより連結された次節点（５，１）へ移動する。この場合、節点（４，０）の右隣に配置された節点（４，１）の値「４（２進数表現で１１）」を加算対象として抽出し、次へ進む。
【００６４】
ＣＰＵ１１は、次の上位桁０を抽出し、０を抽出したと判断して、頂点（５，１）から底辺への左下方向を示す有向グラフにより連結された次節点（６，１）へ移動する。
【００６５】
ＣＰＵ１１は、次の上位桁１を抽出し、１を抽出したと判断して、頂点（６，１）から底辺への右下方向を示す有向グラフにより連結された次節点（７，１）へ移動する。この場合、節点（７，１）の右隣に配置された節点（６，２）の値「１６（２進数表現で１００００）」を加算対象として抽出する。尚、節点（７，１）は上述のとおり、終点であるから、移動を終了し、加算対象「４（２進数表現で１１）」と「１６（２進数表現で１００００）」との和を算出する。
【００６６】
更に、ＣＰＵ１１は、節点（７，１）の一段下に配置されたオフセット（２）の値「８（２進数表現で１００）」を、上述の和に加算して総和「２８（２進数表現で１１１００）」を算出し、算出された総和を、圧縮データとして、出力手段１５を介して出力する。
【００６７】
このように、本発明に係るデータ圧縮方法で処理する値は２進数表現で上位桁３ビットのみに１が含まれる数のみであるから、ＣＰＵ１１が実装する演算器において０を無視して１のみを用いて加算するようにすれば、上述の如く、演算幅ｈを、従来に比しｈ＝ｌｏｇ2 ｇ程度に節約することができる。
【００６８】
実施の形態２．
実施の形態１では、変換テーブルの頂点（０，０）を始点に定め、底辺を構成するいずれかの節点（ｉ，ｊ）を終点に定め、頂点から底辺へ向かう移動を例とした。そこで、実施の形態２では、底辺を構成するいずれかの節点（ｉ，ｊ）を始点に定め、変換テーブルの頂点（０，０）を終点に定め、底辺から頂点へ向かう移動を、上述した節点の値が「２進数表現で上位桁３ビットのみに１が含まれる数」であって、かつ圧縮対象データを表す２進系列「１０１００００）」である場合を例として説明する。図１１は実施の形態２に係るデータ圧縮方法を説明する概念図である。
【００６９】
まず、入力手段１４が、外部から圧縮対象データを表す２進系列「１０１００００）」及び１が含まれる上位桁数「３ビット」を受け付け、ＲＡＭ１３へ出力する。ＲＡＭ１３は、受け付けた圧縮対象データ、及び１が含まれる上位桁数ｄを記憶しておく。
【００７０】
ＣＰＵ１１は、記憶手段１２から読み出した変換テーブルＴがデータ構造として備える三角形の頂点（０，０）を終点に指定し、ＲＡＭ１３から読み出した圧縮対象データを表す２進系列の系列長ｇ及び１の個数を抽出する。抽出した系列長ｇは７ビットであり、１の個数は２個であるから、ＣＰＵ１１は、頂点（０，０）から７だけ下位に移動した先、節点（７，０）〜節点（７，７）で構成される辺を底辺に定め、底辺の左頂点（７，０）から、２だけ移動した先、節点（７，２）を始点として指定する。
【００７１】
次に、ＣＰＵ１１は、始点（７，２）に対応するオフセット（２）の値「８（２進数表現で１００）」を加算対象として抽出する。
【００７２】
次に、ＣＰＵ１１は、ＲＡＭ１３から読み出した圧縮対象データを表す２進系列「１０１００００」で含まれた０又は１を上位桁から下位へ順次抽出していく。
【００７３】
ＣＰＵ１１は、受け付けた圧縮対象データを表す２進系列の最上位桁１を抽出し、１を抽出したと判断して、始点（７，２）から底辺への他の方向である左上方向（以下、同様）を示す有向グラフにより連結された次節点（６，１）へ移動する。この場合、次節点（６，１）の右隣に配置された節点（６，２）の値「１６（２進数表現で１００００）」を加算対象として抽出する。
【００７４】
ＣＰＵ１１は、次の下位桁０を抽出し、０を抽出したと判断して、節点（６，１）から頂点への一の方向である右上方向（以下、同様）を示す有向グラフにより連結された次節点（５，１）へ移動する。
【００７５】
ＣＰＵ１１は、次の下位桁１を抽出し、１を抽出したと判断して、節点（５，１）から頂点への左上方向を示す有向グラフにより連結された次節点（４，０）へ移動する。この場合、次節点（４，０）の右隣に配置された節点（４，１）の値「４（２進数表現で１１）」を加算対象として抽出する。
【００７６】
ＣＰＵ１１は、次以降の下位桁「０，０，０，０」を抽出し、０を抽出したと判断して、節点（４．０）から頂点への左上方向を示す有向グラフにより連結された次節点を移動し、終点である頂点まで移動する。そして加算対象である「８（２進数表現で１００）」「１６（２進数表現で１００００）」及び「４（２進数表現で１１）」の総和「２８（２進数表現で１１１００）」を算出する。
【００７７】
そして、ＣＰＵ１１は、加算対象として抽出した値の総和を、圧縮データとして、出力手段１５を介して出力する。
【００７８】
このように、実施の形態１とは反対方向から移動した場合でも、処理する値は２進数表現で上位桁３ビットのみに１が含まれる数のみであるから、ＣＰＵ１１が実装する演算器において０を無視して１のみを用いて加算するようにすれば、上述の如く、演算幅ｈを、従来に比しｈ＝ｌｏｇ2 ｇ程度に節約することができる。
【００７９】
本実施の形態２は以上の如き内容であり、その他の内容は、実施の形態１と同様であるので、対応する部分には同一の参照番号を対応してその詳細な説明は省略する。
【００８０】
尚、上述した実施の形態では、変換テーブルＴに基づき、圧縮対象データを圧縮データへ変換（圧縮）する例を示したが、本発明に係るデータ圧縮方法は、可逆性を有しており、以下、圧縮データを伸張（圧縮対象）データへ伸張する手順について説明しておく。図１２及び図１３は伸張処理の手順を説明するフローチャートである。
【００８１】
ＣＰＵ１１は、変数ｓに圧縮データを代入し（Ｓ４０１）、変数ｊに伸張データを表す２進系列の系列長ｇを代入し（Ｓ４０２）、変数ｓがオフセット（ｊ）の値Ｆ’以上であるか否かを判断し（Ｓ４０３）、変数ｓがオフセット（ｊ）の値Ｆ’以上ではないと判断した場合（Ｓ４０３でＮＯ）、変数ｊから１を引き（Ｓ４０４）、ステップＳ４０３に戻り、変数ｓがオフセット（ｊ）の値Ｆ’以上になるまで繰り返す。
【００８２】
他方、ＣＰＵ１１は、変数ｓがオフセット（ｊ）の値Ｆ’以上であると判断した場合（Ｓ４０３でＹＥＳ）、変数ｓ＝変数ｓ−オフセット（ｊ）の値Ｆ’を計算し（Ｓ４０５）、変数ｉに伸張データを表す２進系列の系列長ｇ−１を代入し（Ｓ４０６）、変数ｉが変数ｊ以上であるか否かを判断し（Ｓ４０７）、変数ｉが変数ｊ以上ではないと判断した場合（Ｓ４０７でＮＯ）、後述のステップＳ４１１へジャンプする。
【００８３】
他方、ＣＰＵ１１は、変数ｉが変数ｊ以上であると判断した場合（Ｓ４０７でＹＥＳ）、更に変数ｓが節点（ｉ，ｊ）の値Ｃ’以上であるか否かを判断し（Ｓ４０８）、変数ｓが節点（ｉ，ｊ）の値Ｃ’以上ではないと判断した場合（Ｓ４０８でＮＯ）、伸張データを表す２進系列の上位桁ｔg-1を０にする（Ｓ４０９）。
【００８４】
他方、ＣＰＵ１１は、変数ｓが節点（ｉ，ｊ）の値Ｃ’以上であると判断した場合（Ｓ４０８でＹＥＳ）、変数ｓ＝変数ｓ−節点（ｉ，ｊ）の値Ｃ’を計算し（Ｓ４１０）、伸張データを表す２進系列の上位桁ｔg-1を１にする（Ｓ４１１）。
【００８５】
更に、ＣＰＵ１１は、変数ｊから１を引き（Ｓ４１２）、変数ｉが０であるか否かを判断し（Ｓ４１３）、変数ｉが０ではないと判断した場合（Ｓ４１３でＮＯ）、変数ｉから１を引いて（Ｓ４１４）、ステップＳ４０７へ戻る。
【００８６】
他方、ＣＰＵ１１は、変数ｉが０であると判断した場合（Ｓ４１３でＹＥＳ）、伸張データを表す２進系列（ｔ1 ，ｔ2 ，ｔ3 ，…，ｔg ）を、出力手段１５を介して出力する（Ｓ４１５）。このように、圧縮データを伸張（圧縮対象）データへ伸張する。
【００８７】
尚、上述した実施の形態では、関数Ｒｏｕｎｄｕｐ（ｘ，ｄ）を求める具体的な式を示したが、これに限らず、他の式に基づいて求めるようにしてもよい。
【００８８】
また、上述した実施の形態では、出力手段１５から出力される圧縮データは、変換テーブルＴ上の節点（ｉ，ｊ）の値の和にオフセット（ｊ）の値を加算した総和としたが、これに限らず、変換テーブルＴ上の節点（ｉ，ｊ）の値の総和のみを用いてもよい。また、別の方法で規定されるオフセット（ｊ）を用いたり、重みを別の方法で符号化してもよい。例えば、重みを２進数で表して、桁数がｌｏｇ2 （ｇ＋１）以上の最小の整数となるように０を前置したものを、重みの符号化として、変換テーブルＴ上の節点(ｉ，ｊ)の和で求めた圧縮データに前置してもよい。
【００８９】
更にまた、上述した実施の形態では、本発明のデータ圧縮装置を具現化するものとして、コンピュータ１を用いたが、これに限らず符号変換器と加算器とを備える専用の装置であってもよい。この場合、符号変換器は、圧縮対象データに基づき、三角形の頂点（０，０）（又は底辺を構成するいずれかの節点（ｉ，ｊ））を始点に定め、該三角形の底辺を構成するいずれかの節点（ｉ，ｊ）（又は頂点（０，０））を終点に定め、圧縮対象データを表す２進系列で含まれた０又は１を下位桁（又は上位桁）から順次抽出し、０又は１のいずれを順次抽出したかを判断し、前記始点から終点まで、０を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への一の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動し、１を抽出したと判断した場合、一の節点（ｉ，ｊ）から底辺（又は頂点）への他の方向を示す有向グラフにより連結された次節点（ｉ，ｊ）へ順次移動し、１を抽出したと判断した場合、所定の規則に基づき、該一の節点（ｉ，ｊ）（又は次節点（ｉ，ｊ））の隣に配置されている節点（ｉ，ｊ）の値Ｃ’を順次抽出して、加算器へ出力し、加算器は、抽出した値Ｃ'を順次加算して、値Ｃ’の加算した総和を、前記圧縮データとして出力する。
【図面の簡単な説明】
【００９０】
【図１】パスカルの三角形の配列を示す概念図である。
【図２】パスカルの三角形を用いた従来のデータ圧縮方法を説明する概念図である。
【図３】本発明に係るデータ圧縮装置を具現化するコンピュータのブロック図である。
【図４】本発明に用いる変換テーブルの生成処理の手順を説明するフローチャートである。
【図５】本発明に用いる変換テーブルの一例を説明する概念図
【図６】関数Ｒｏｕｎｄｕｐ（ｘ，ｄ）により切り上げられた値の一例を説明する概念図である。
【図７】始点及び終点の指定処理の手順を説明するフローチャートである。
【図８】オフセットの値の規定処理の手順を説明するフローチャートである。
【図９】本発明に用いる始点，終点及びオフセットの値を定めた変換テーブルの一例を説明する概念図である。
【図１０】実施の形態１に係るデータ圧縮方法を説明する概念図である。
【図１１】実施の形態２に係るデータ圧縮方法を説明する概念図である。
【図１２】伸張処理の手順を説明するフローチャートである。
【図１３】伸張処理の手順を説明するフローチャートである。
【符号の説明】
【００９１】
１１  ＣＰＵ
１２  記憶手段
１３  ＲＡＭ
１４  入力手段
１５  出力手段
１６  補助記憶手段
１７  可搬型記録媒体
【図１】
2007312323.tif 000003
【図２】
2007312323.tif 000004
【図３】
2007312323.tif 000005
【図４】
2007312323.tif 000006
【図５】
2007312323.tif 000007
【図６】
2007312323.tif 000008
【図７】
2007312323.tif 000009
【図８】
2007312323.tif 000010
【図９】
2007312323.tif 000011
【図１０】
2007312323.tif 000012
【図１１】
2007312323.tif 000013
【図１２】
2007312323.tif 000014
【図１３】
2007312323.tif 000015