(57)【要約】【課題】変換後のデータ部分系列の個数の増大を抑制して、効率的にデータ系列の変換をすることができるようにする。【解決手段】部分列探索部１３によって、入力されたデータ系列のうちの未分解系列の先頭からの部分系列である語頭との距離が、予め定められた０より大きい閾値以下である、語頭の長さと一致する長さの既に切り出された前記データ系列の部分列のうち、長さが最も長い部分列を探索する。部分列生成部１４によって、未分解系列の先頭から、探索した部分列と対応する部分系列と後続する所定個のデータとを連結した部分列を切り出す。部分列符号化部１６によって、部分列探索部１３による探索及び切り出しを繰り返したときに、切り出された部分列の各々を、データ部分系列に変換し、変換されたデータ部分系列の各々を連結して、変換後のデータ系列として出力する。【選択図】図３
2014229926.tif 000002
【特許請求の範囲】
【請求項１】
部分列探索手段及びデータ変換手段を含み、入力されたデータ系列を、異なるデータ系列に変換するデータ変換装置におけるデータ変換方法であって、
前記部分列探索手段によって、前記入力されたデータ系列のうちの未分解系列の先頭からの部分系列である語頭との距離が、予め定められた０より大きい閾値以下である、前記語頭の長さと一致する長さの既に切り出された前記データ系列の部分列のうち、長さが最も長い部分列を探索し、前記未分解系列の先頭から、前記探索した部分列と対応する部分系列と後続する所定個のデータとを連結した部分列を切り出すステップと、
前記データ変換手段によって、前記部分列探索手段による探索及び切り出しを繰り返したときに、切り出された前記部分列の各々を、データ部分系列に変換し、前記変換された前記データ部分系列の各々を連結して、変換後のデータ系列として出力するステップと、
を含むデータ変換方法。
【請求項２】
前記閾値は、前記閾値が用いられるときの前記未分解系列の先頭位置が、前記入力されたデータ系列の先頭から遠いほど、大きくなるように定められている請求項１記載のデータ変換方法。
【請求項３】
前記データ変換手段によって変換後のデータ系列を出力するステップは、前記部分列探索手段による探索及び切り出しを繰り返したときに、切り出された前記部分列の各々を、圧縮データ部分系列に符号化し、前記符号化された圧縮データ部分系列の各々を連結して、圧縮データとして出力する請求項１又は２記載のデータ変換方法。
【請求項４】
入力されたデータ系列を、異なるデータ系列に変換するデータ変換装置であって、
前記入力されたデータ系列のうちの未分解系列の先頭からの部分系列である語頭との距離が、予め定められた０より大きい閾値以下である、前記語頭の長さと一致する長さの既に切り出された前記データ系列の部分列のうち、長さが最も長い部分列を探索し、前記未分解系列の先頭から、前記探索した部分列と対応する部分系列と後続する所定個のデータとを連結した部分列を切り出すことを繰り返す部分列探索手段と、
前記部分列探索手段による探索及び切り出しを繰り返したときに、切り出された前記部分列の各々を、データ部分系列に変換し、前記変換された前記データ部分系列の各々を連結して、変換後のデータ系列として出力するデータ変換手段と、
を含むデータ変換装置。
【請求項５】
データ部分系列切り出し手段及びデータ逆変換手段を含むデータ逆変換装置におけるデータ逆変換方法であって、
前記データ部分系列切り出し手段によって、請求項１〜請求項３の何れか１項記載のデータ変換方法によって変換された前記変換後のデータ系列から、前記データ部分系列の各々を切り出すステップと、
前記データ逆変換手段によって、前記切り出された前記データ部分系列の各々を逆変換して前記部分列の各々を取得すると共に、前記取得された部分列の各々を連結したデータ系列を出力するステップと、
を含むデータ逆変換方法。
【請求項６】
請求項４記載のデータ変換装置によって変換された前記変換後のデータ系列から、前記データ部分系列の各々を切り出すデータ部分系列切り出し手段と、
前記切り出された前記データ部分系列の各々を逆変換して前記部分列の各々を取得すると共に、前記取得された部分列の各々を連結したデータ系列を出力するデータ逆変換手段と、
を含むデータ逆変換装置。
【請求項７】
請求項１〜請求項３の何れか１項記載のデータ変換方法、あるいは請求項５記載のデータ逆変換方法を構成する各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを変換するデータ変換方法、データ逆変換方法、装置、及びプログラムに関する。
【背景技術】
【０００２】
任意の離散データを入力し、規則性があるか否かを識別し、識別結果に基づき縮約する技術が過去に提案されている（例えば、非特許文献１を参照）。
【０００３】
また、ＪＰＥＧ（画像）やＭＰＥＧ（動画）などの不可逆データ圧縮技術は、あらかじめ記録するフォーマットが決まっていて、データに特徴的な規則性の種類などが事前に明確な用途でのみ効果的な使い分けが可能である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】J. Ziv and A. Lempel、「Compression of individual sequences via variable-rate coding」、IEEE Transactions on Information Theory、vol.IT-24、no.5、1987、ｐ530-536
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、非特許文献１に記載されているような技術では、元々文書ファイルなどのテキストの符号化などを想定した可逆データ圧縮技術であり、完全なデータの再現を必ずしも必要としない計測データの縮約には不向きである。
【０００６】
また、ＪＰＥＧ（画像）やＭＰＥＧ（動画）などの不可逆データ圧縮技術においては、逆にどのような規則性のあるデータが入力されるのか不明な状況では、それを適応的に縮約することは難しかった。
【０００７】
つまり、従来の可逆データ圧縮技術は、汎用的ではあるが圧縮の性能に原理的に顕著な限界があり、個別の不可逆データ圧縮技術では、データの構造や規則性などに詳細な事前知識を要求されるために、予測できないパターンを記録する用途には不向きである、という問題点があった。
【０００８】
本発明は、上記の事情を鑑みてなされたもので、変換後のデータ部分系列の個数の増大を抑制して、効率的にデータ系列の変換をすることができるデータ変換方法、データ逆変換方法、装置、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明に係るデータ変換方法は、部分列探索手段及びデータ変換手段を含み、入力されたデータ系列を、異なるデータ系列に変換するデータ変換装置におけるデータ変換方法であって、前記部分列探索手段によって、前記入力されたデータ系列のうちの未分解系列の先頭からの部分系列である語頭との距離が、予め定められた０より大きい閾値以下である、前記語頭の長さと一致する長さの既に切り出された前記データ系列の部分列のうち、長さが最も長い部分列を探索し、前記未分解系列の先頭から、前記探索した部分列と対応する部分系列と後続する所定個のデータとを連結した部分列を切り出すステップと、前記データ変換手段によって、前記部分列探索手段による探索及び切り出しを繰り返したときに、切り出された前記部分列の各々を、データ部分系列に変換し、前記変換された前記データ部分系列の各々を連結して、変換後のデータ系列として出力するステップと、を含んでいる。
【００１０】
本発明に係るデータ変換装置は、入力されたデータ系列を、異なるデータ系列に変換するデータ変換装置であって、前記入力されたデータ系列のうちの未分解系列の先頭からの部分系列である語頭との距離が、予め定められた０より大きい閾値以下である、前記語頭の長さと一致する長さの既に切り出された前記データ系列の部分列のうち、長さが最も長い部分列を探索し、前記未分解系列の先頭から、前記探索した部分列と対応する部分系列と後続する所定個のデータとを連結した部分列を切り出すことを繰り返す部分列探索手段と、前記部分列探索手段による探索及び切り出しを繰り返したときに、切り出された前記部分列の各々を、データ部分系列に変換し、前記変換された前記データ部分系列の各々を連結して、変換後のデータ系列として出力するデータ変換手段と、を含んで構成されている。
【００１１】
また、本発明に係る閾値は、前記閾値が用いられるときの前記未分解系列の先頭位置が、前記入力されたデータ系列の先頭から遠いほど、大きくなるように定められているようにすることができる。
【００１２】
また、本発明に係るデータ変換手段は、前記部分列探索手段による探索及び切り出しを繰り返したときに、切り出された前記部分列の各々を、圧縮データ部分系列に符号化し、前記符号化された圧縮データ部分系列の各々を連結して、圧縮データとして出力するようにすることができる。
【００１３】
本発明に係るデータ逆変換方法は、データ部分系列切り出し手段及びデータ逆変換手段を含むデータ逆変換装置におけるデータ逆変換方法であって、前記データ部分系列切り出し手段によって、上記のデータ変換方法によって変換された前記変換後のデータ系列から、前記データ部分系列の各々を切り出すステップと、前記データ逆変換手段によって、前記切り出された前記データ部分系列の各々を逆変換して前記部分列の各々を取得すると共に、前記取得された部分列の各々を連結したデータ系列を出力するステップと、を含んでいる。
【００１４】
本発明に係るデータ逆変換装置は、上記のデータ変換装置によって変換された前記変換後のデータ系列から、前記データ部分系列の各々を切り出すデータ部分系列切り出し手段と、前記切り出された前記データ部分系列の各々を逆変換して前記部分列の各々を取得すると共に、前記取得された部分列の各々を連結したデータ系列を出力するデータ逆変換手段と、を含んで構成されている。
【００１５】
本発明に係るプログラムは、コンピュータを、上記データ変換方法、あるいは上記データ逆変換方法を構成する各ステップをコンピュータに実行させるためのプログラムである。
【発明の効果】
【００１６】
以上説明したように、本発明に係るデータ変換方法、データ逆変換方法、装置、及びプログラムよれば、入力されたデータ系列のうちの未分解系列の語頭との距離が、予め定められた０より大きい閾値以下である部分列のうち、長さが最も長い部分列を探索し、未分解系列の先頭から、探索した部分列と対応する部分系列と後続する所定個のデータとを連結した部分列を切り出すことを繰り返し、切り出された部分列の各々を、データ部分系列に変換することにより、変換後のデータ部分系列の個数の増大を抑制して、効率的にデータ系列の変換をすることができる、という効果が得られる。
【図面の簡単な説明】
【００１７】
【図１】従来の増分分解法の処理内容を模式的に示した説明図である。
【図２】本実施の形態における増分分解法の処理内容を模式的に示した説明図である。
【図３】本実施の形態に係るデータ圧縮装置の機能的な構成を示す図である。
【図４】本実施の形態における閾値の適応的な変化を模式的に示した概念図である。
【図５】本実施の形態に係るデータ再生装置の機能的な構成を示す図である。
【図６】データ圧縮装置及びデータ再生装置として機能するコンピュータの概略ブロック図である。
【図７】本実施の形態に係るデータ圧縮装置が実行するデータ圧縮処理ルーチンの前半部分の内容を示すフローチャートである。
【図８】本実施の形態に係るデータ圧縮装置が実行するデータ圧縮処理ルーチンの後半部分の内容を示すフローチャートである。
【図９】本実施の形態に係るデータ圧縮装置が実行する符号化処理ルーチンの内容を示すフローチャートである。
【図１０】本実施の形態に係るデータ再生装置が実行するデータ再生処理ルーチンの内容を示すフローチャートである。
【図１１】本実施の形態の実験結果を示す図である。
【発明を実施するための形態】
【００１８】
以下、図面を参照して、本発明の実施の形態を詳細に説明する。なお、本実施の形態では、本発明を、入力されたデータ系列を圧縮して圧縮データ系列に変換するデータ圧縮装置と、データ圧縮装置によって変換された圧縮データ系列を逆変換して、データ系列を再生するデータ再生装置とに適用した場合を例に説明する。
【００１９】
まず、データ系列を圧縮して圧縮データ系列に変換する原理について説明する。
【００２０】
＜データ圧縮の原理＞
本実施の形態におけるデータ系列とは、例えば、センサーから送られてくる時系列信号を、離散的な２値アルファベット（例えば０と１）で表現したものである。データ系列は、離散的なアルファベットで表現されるものであれば何でも良い。
【００２１】
データ系列として、例えば、時刻１から時刻ｎまでの入力データとして、データ系列
【００２２】
【数１】
2014229926.tif 000003
【００２３】
が得られたとする。ただし、上記の例の場合、アルファベットｘｉは、
【００２４】
【数２】
2014229926.tif 000004
【００２５】
となる。このデータ系列が
【００２６】
【数３】
2014229926.tif 000005
【００２７】
のように、空でない部分列に分解できたとする（以下では、データ系列内の分解済みの系列を部分列と称し、データ系列内の未分解の系列の一部分を部分系列と称する）。ただし、ここでは表記を簡単にするために、
【００２８】
【数４】
2014229926.tif 000006
【００２９】
という記法によって略記している。このデータ系列は、各部分列
【００３０】
【数５】
2014229926.tif 000007
【００３１】
に対する符号語を、全体として効率的に与えることで、全体のデータ系列が縮約される。以下、参考文献（Te Sun Han and Kingo Kobayashi、「Mathematics of Information and Coding」、Translations of Mathematical monographs、vol．203、1994、ｐ193-195）の記載に従い、増分分解（incremental parsing）の基本的な考え方を最初に解説し、その後、多くの計算機に実装されている従来法（ＬＺ７８法）と本実施の形態とを比較して説明する。
【００３２】
一般に、増分分解では、データ系列の部分列への分解
【００３３】
【数６】
2014229926.tif 000008
【００３４】
が、次の２つの条件を満足するように実行される。
【００３５】
（条件１）最後の部分列
【００３６】
【数７】
2014229926.tif 000009
【００３７】
を除いて、はじめのｐ個の部分列
【００３８】
【数８】
2014229926.tif 000010
【００３９】
はすべて相異なる。
【００４０】
（条件２）不等式
【００４１】
【数９】
2014229926.tif 000011
【００４２】
を満足するすべてのｊに対して、
【００４３】
【数１０】
2014229926.tif 000012
【００４４】
となる正整数ｉ（＜ｊ）が存在する。
上記の条件１、２を満足するような部分列への分解は一意的であることが知られており、増分分解と呼ばれる。従来法（ＬＺ７８法）は、与えられた任意のデータ系列に対して、この増分分解を再帰的に計算する手法である。これに対して、本実施の形態では、この再帰的な計算を意図的に「不正確」に実行することによって、その圧縮効率を改善する。
【００４５】
従来法（ＬＺ７８法）では、増分分解の表現は再帰的に計算される。より具体的には、第ｊ番目の部分列
【００４６】
【数１１】
2014229926.tif 000013
【００４７】
は、第ｊ−１番目までの分解の表現
【００４８】
【数１２】
2014229926.tif 000014
【００４９】
を用いて、次の３つの手順で計算される。ただし、以下の説明では便宜上、長さ０の空系列をλと表記し、
【００５０】
【数１３】
2014229926.tif 000015
【００５１】
と設定する。また、語頭（prefix）とは、ある系列の先頭部分に位置する任意の部分系列のことを指す。例えば、系列１２３の語頭は、１、１２、１２３となる。
【００５２】
（手順１）未分解の系列（以下、未分解系列と称する。）
【００５３】
【数１４】
2014229926.tif 000016
【００５４】
の語頭のどれかに一致する最長の系列を、データ系列から既に切り出された部分列と空系列λとをまとめた部分列の集合
【００５５】
【数１５】
2014229926.tif 000017
【００５６】
の中から探し出し、その部分列（第ｋｊ番目と仮定）を
【００５７】
【数１６】
2014229926.tif 000018
【００５８】
と書く。
【００５９】
（手順２）仮に、最長の語頭が未分解系列の全体と一致して、
【００６０】
【数１７】
2014229926.tif 000019
【００６１】
となるときは、
【００６２】
【数１８】
2014229926.tif 000020
【００６３】
となるようにｋｊを選び直し、さらにｎｊ＝ｎとする。この手順は例外的で、再帰計算の終了時に適用される。
【００６４】
（手順３）一般に、再帰計算の途中では、
【００６５】
【数１９】
2014229926.tif 000021
【００６６】
と置いて、第ｊ番目の部分列
【００６７】
【数２０】
2014229926.tif 000022
【００６８】
を定める。これは
【００６９】
【数２１】
2014229926.tif 000023
【００７０】
より１文字多い部分列になっていることがわかる。
【００７１】
つまり、（手順１）から（手順３）までを繰り返すことによって、結果的に、増分分解
【００７２】
【数２２】
2014229926.tif 000024
【００７３】
に表れる各部分列が求められる。全体のデータ系列は、各部分列をそれぞれ符号化することによって、圧縮される。従来の増分分解法の概念を図１に示す。ここで重要なことは、このような圧縮の方法では、その圧縮効率が増分分解の部分列の個数によって事実上決定されることである。実際、増分分解に基づく従来法（ＬＺ７８法）の圧縮率は、切り出された部分列の個数が小さい程小さくなり（高圧縮）、大きい程大きくなる（低圧縮）傾向があることが数学的に証明されている。
【００７４】
そこで、本実施の形態では、元のデータ系列のうちの部分系列と「似た」系列を適応的に定義し、いわば身代わりに増分分解することで、切り出される部分列の個数を小さくする。ここでは、当然、元のデータ系列を完全に再現することはあきらめることになる（不可逆圧縮）。しかし、部分列と部分系列との間に適当な距離測度（ハミング距離等）を導入することによって、データ系列の再現性と圧縮率のトレードオフを柔軟にコントロールすることができる。具体的な再帰計算の一例としては、次のような実施の形態がある。本実施の形態では、従来法（ＬＺ７８法）の手順１を下記の手順１Ａに置き換えれば良い。手順２と手順３は変更しない。
【００７５】
（手順１Ａ）未分解系列
【００７６】
【数２３】
2014229926.tif 000025
【００７７】
の語頭のどれかと一定の距離内にある最長の系列を、データ系列から既に切り出された部分列と空系列λをまとめた部分列の集合
【００７８】
【数２４】
2014229926.tif 000026
【００７９】
の中から探し出し、その部分列（第ｋｊ番目と仮定）を
【００８０】
【数２５】
2014229926.tif 000027
【００８１】
と書く。
【００８２】
手順１Ａで言及されている系列間の「距離」とは、ハミング距離のような数学的に定義された距離測度を意味している。ただし、本実施の形態の説明で使用する距離とは、アルファベット当たりに規格化されていると仮定する。本実施の形態で利用する緩和された増分分解（緩和増分分解）の概念を図２に示す。
【００８３】
次に符号化の処理を行う。ひとたび増分分解の表現が求められてしまえば、各部分列の符号化の方法に、従来法（ＬＺ７８法）と本実施の形態で区別はないので、これは両者に共通の計算手順になる。手順１（あるいは手順１Ａ）で定義したｋｊと手順３で定義したｎｊの組を利用して、第ｊ番目の部分列
【００８４】
【数２６】
2014229926.tif 000028
【００８５】
に対する符号語（ラベルとして使う整数）を
【００８６】
【数２７】
2014229926.tif 000029
【００８７】
と決定する。これは
【００８８】
【数２８】
2014229926.tif 000030
【００８９】
という部分列の番号ｊだけで指定できる桁数Ｌjの２進列で表現できることが証明できる。以下、この２進列を
【００９０】
【数２９】
2014229926.tif 000031
【００９１】
と書くことにする（以下、データ部分系列と称する）。すると、全体のデータ系列
【００９２】
【数３０】
2014229926.tif 000032
【００９３】
に対する変換後のデータ系列は、これらを番号順に連結した
【００９４】
【数３１】
2014229926.tif 000033
【００９５】
にすればよい。
【００９６】
＜データ再生の原理＞
次に、変換された圧縮データ系列を逆変換する原理について説明する。データ再生では、次のように復号化の処理を行う。元のデータ系列の復号の方法に、従来法（ＬＺ７８法）と本実施の形態で区別はないので、これは両者に共通の計算手順になる。
復号化の処理では、最初に、上記の２進列を先頭から、上記（２８）式に従ってＬ１桁、Ｌ２桁、と順番に切り出して
【００９７】
【数３２】
2014229926.tif 000034
【００９８】
を各々求め、それぞれから符号語
【００９９】
【数３３】
2014229926.tif 000035
【０１００】
を計算する。計算された符号語から、上記（２７）式に従って、（ｋｊ、ｎｊ）の組が一意に指定できるので、この結果、符号語から、各部分列
【０１０１】
【数３４】
2014229926.tif 000036
【０１０２】
を復元できる。後は、復元された各部分列を連結することにより、再生したデータ系列が得られる。
【０１０３】
＜データ圧縮装置のシステム構成＞
【０１０４】
次に、本発明を、入力されたデータ系列を符号化して圧縮データ系列に変換するデータ圧縮装置に適用した場合を例に説明する。
【０１０５】
図３は、本発明の実施の形態におけるデータ圧縮装置１０の機能的な構成を示す図である。
【０１０６】
図３に示すデータ圧縮装置１０は、入力されたデータ系列を符号化して圧縮データ系列に変換して出力する装置であって、符号化入力部１１と、距離指標算出部１２と、部分列探索部１３と、部分列生成部１４と、反復判定部１５と、部分列符号化部１６と、符号化出力部１７とを備えている。なお、距離指標算出部１２及び部分列探索部１３が、部分列探索手段の一例であり、部分列生成部１４、反復判定部１５、部分列符号化部１６、及び符号化出力部１７が、データ変換手段の一例である。
【０１０７】
符号化入力部１１は、データ系列の入力を受け付ける。
【０１０８】
距離指標算出部１２は、符号化入力部１１によって入力を受け付けたデータ系列の未分解系列の先頭からの部分系列である語頭の各々と、データ系列から既に切り出された部分列の各々との距離を算出する。
具体的には、距離指標算出部１２は、入力されたデータ系列に対して、未分解系列を設定する。そして、距離指標算出部１２は、未分解系列の先頭からの部分系列である語頭（例えば、データ系列１２３の語頭は、１、１２、１２３である）の各々について、当該語頭と、当該語頭の長さと一致する長さの、既に切り出されたデータ系列の部分列との距離を算出する。
【０１０９】
部分列探索部１３は、距離指標算出部１２によって算出された距離の各々と、予め定められた閾値とに基づいて、既に切り出された部分列の集合から、語頭との距離が閾値以下である最長の部分列を探索する。ここで、閾値は０より大きい値である。また、閾値は、図４に示すように、未分解系列の先頭位置が、入力されたデータ系列の先頭から遠いほど、大きくなるように定められている。すなわち、類似度の判定が実施される未分解系列の位置によって、判定基準を適応的に変化させる。また、語頭との距離が閾値以下である最長の部分列が２つ以上探索された場合には、そのうちの１つをランダムに決定する。なお、未分解系列の先頭位置に関わらず、一定の閾値を用いるようにしてもよい。
【０１１０】
部分列生成部１４は、未分解系列の先頭から、部分列探索部１３によって探索された、語頭との距離が閾値以下である最長の部分列と対応する部分系列と、後続する１個のアルファベットとを連結した部分列を切り出す。
具体的には、部分列生成部１４は、部分列探索部１３によって探索された部分列（第ｋｊ番目と仮定）
【０１１１】
【数３５】
2014229926.tif 000037
【０１１２】
に基づいて、上記（１９）式に従って、新たに生成するｊ番目の部分列の末尾のアルファベットの添え字ｎｊを計算する。そして、未分解系列の先頭から、添え字ｎｊのアルファベットまでの部分列
【０１１３】
【数３６】
2014229926.tif 000038
を新たなｊ番目の部分列として決定し、切り出す。
【０１１４】
反復判定部１５は、未分解系列全体と一致する、既に切り出された部分列が存在するか否かを繰り返し終了条件として設定し、繰り返し終了条件を満足したか否かを判定する。未分解系列全体と一致する、既に切り出された部分列が存在するまで、距離指標算出部１２による算出、部分列探索部１３による探索、及び部分列生成部１４による切り出し処理が繰り返される。
また、反復判定部１５によって、未分解系列全体と一致する、既に切り出された部分列が存在すると判定された場合には、上記（１８）式となるようにｋｊを選び直し、さらにｎｊ＝ｎとする。
【０１１５】
部分列符号化部１６は、部分列生成部１４によって切り出された部分列の各々を符号化して、符号語を２進数で表現した圧縮データ部分系列に変換し、変換された圧縮データ部分系列の各々を連結して、圧縮データ系列を生成する。
具体的には、部分列符号化部１６は、部分列生成部１４によって切り出された部分列の各々について、当該部分列の（ｋｊ、ｎｊ）の組に基づいて、上記（２７）式を用いて、当該部分列を符号語に変換する。次に、部分列の各々について変換された符号語の各々について、当該符号語を２進数で表現したデータ部分系列
【０１１６】
【数３７】
2014229926.tif 000039
【０１１７】
へ変換する。そして、上記（３１）式に示すように、変換されたデータ部分系列の各々を連結して、圧縮データ系列φ2（ｘ1ｎ）を生成する。
【０１１８】
符号化出力部１７は、部分列符号化部１６によって生成された圧縮データ系列を結果として出力し、ネットワークを介して、圧縮データ系列を後述するデータ再生装置２０へ送信する。
【０１１９】
＜データ再生装置のシステム構成＞
次に、本発明を、データ圧縮装置によって変換された圧縮データ系列を逆変換して、データ系列を再生するデータ再生装置に適用した場合を例に説明する。
【０１２０】
図５は、本発明の実施の形態におけるデータ再生装置２０の機能的な構成を示す図である。
【０１２１】
図５に示すデータ再生装置２０は、データ圧縮装置１０によって変換された圧縮データ系列を逆変換して出力する装置であって、復号化入力部２１と、部分列取得部２２と、部分列復号化部２３と、復号化出力部２４とを備えている。なお、部分列取得部２２が、データ部分系列切り出し手段の一例であり、部分列復号化部２３がデータ逆変換手段の一例である。
【０１２２】
復号化入力部２１は、データ圧縮装置１０によって変換された圧縮データ系列の入力を受け付ける。
【０１２３】
部分列取得部２２は、復号化入力部２１によって入力を受け付けた圧縮データ系列について、１番目〜ｊ番目の部分列に対応する２進列の桁数Ｌｊを、上記（２８）式に従って算出する。次に、部分列取得部２２は、算出されたｊ番目の２進列の桁数Ｌｊに基づいて、圧縮データ系列の先頭から、２進列
【０１２４】
【数３８】
2014229926.tif 000040
【０１２５】
の各々を切り出す。
【０１２６】
部分列復号化部２３は、切り出された２進列の各々について、符号語
【０１２７】
【数３９】
2014229926.tif 000041
【０１２８】
を算出する。部分列復号化部２３は、算出された符号語の各々について、上記（２７）式を用いて、ｊ番目の符号語の（ｋｊ、ｎｊ）の組を算出して、部分列
【０１２９】
【数４０】
2014229926.tif 000042
【０１３０】
を復元する。そして、部分列復号化部２３は、復元された部分列の各々を連結して、再生されたデータ系列を算出する。
【０１３１】
復号化出力部２４は、部分列復号化部２３によって算出されたデータ系列を結果として出力する。
【０１３２】
また、データ圧縮装置１０及びデータ再生装置２０は、図６に示すように、ＣＰＵ（Central Processing Unit）２０１と、ＣＰＵが後述する各処理ルーチンを実行するためのプログラム等を記憶したＲＯＭ（Read Only Memory）２０２と、ＲＡＭ（Random Access Memory）２０３と、を備えたコンピュータ２００で構成することができる。また、このコンピュータ２００は、通信インタフェース（ＩＦ）２０４、入出力ＩＦ２０５、及びハードディスクドライブ２０６も備えている。通信ＩＦ２０４はネットワーク２１０に接続するためのインタフェースである。入出力ＩＦ２０５は、ディスプレイ２０８及びキーボード２０９に接続される。
【０１３３】
ＣＰＵ２０１がＲＯＭ２０２やハードディスク等の記録媒体に記憶されているプログラムを読み出して実行することにより、上記ハードウェアとプログラムとを協働させて上述した機能が実現される。
【０１３４】
＜データ圧縮装置の作用＞
次に、本実施の形態に係るデータ圧縮装置１０の作用について説明する。圧縮対象のデータ系列が、データ圧縮装置１０に入力されると、データ圧縮装置１０によって、図７及び図８に示すデータ圧縮処理ルーチンが実行される。
【０１３５】
まず、ステップＳ１００において、データ系列の入力を受け付ける。
【０１３６】
ステップＳ１０２において、データ系列内のアルファベットの位置を示す添え字ｊに１を代入する。
【０１３７】
ステップＳ１０４において、後述するステップＳ１１８において切り出された部分列に基づいて、上記ステップＳ１００で入力を受け付けたデータ系列に対して、未分解系列
【０１３８】
【数４１】
2014229926.tif 000043
【０１３９】
を設定する。
【０１４０】
ステップＳ１０６において、ステップＳ１１８において切り出された部分列の集合に基づいて、反復判定部１５によって、上記ステップＳ１０４で設定された未分解系列全体と一致する、既に切り出された部分列が存在するか否かを判定する。そして、未分解系列全体と一致する、既に切り出された部分列が存在する場合には、ステップＳ１２２へ進む。一方、未分解系列全体と一致する、既に切り出された部分列が存在しない場合には、ステップＳ１０８へ進む。
【０１４１】
ステップＳ１０８において、距離指標算出部１２によって、上記ステップＳ１０４で設定された未分解系列に対して、全ての語頭を設定する（例えば、未分解系列が「１２３」の場合には、語頭として、１、１２、１２３の全てを設定する。）。
【０１４２】
ステップＳ１１０において、距離指標算出部１２によって、上記ステップＳ１０８で設定された各語頭について、ステップＳ１１８において切り出された部分列の集合から、当該語頭の長さと一致する部分列を選出する。
【０１４３】
ステップＳ１１２において、距離指標算出部１２によって、上記ステップＳ１０８で設定された各語頭について、当該語頭と、上記ステップＳ１１０で選出された各部分列との距離を算出する。
【０１４４】
ステップＳ１１４において、部分列探索部１３によって、上記ステップＳ１１２で算出された距離の各々と、予め定められた閾値とに基づいて、上記ステップＳ１１０で選出された各部分列から、語頭との距離が閾値以下である最長の部分列を探索する。
【０１４５】
ステップＳ１１６において、部分列生成部１４によって、ステップＳ１１４で探索された部分列（第ｋｊ番目）に基づいて、上記（１９）式に従って、新たに生成するｊ番目の部分列の末尾のアルファベットの添え字ｎｊを計算する。
【０１４６】
ステップＳ１１８において、部分列生成部１４によって、上記ステップＳ１１６で計算された新たに生成するｊ番目の部分列の末尾のアルファベットの添え字ｎｊに基づいて、未分解系列の先頭から、添え字ｎｊのアルファベットまでの部分列
【０１４７】
【数４２】
2014229926.tif 000044
【０１４８】
を新たなｊ番目の部分列として決定し、切り出す。
【０１４９】
ステップＳ１２０において、添え字ｊをインクリメントして、ステップＳ１０４へ進む。
【０１５０】
ステップＳ１２２において、部分列生成部１４によって、上記ステップＳ１０４で設定された未分解系列に対して、上記（１８）式となるようにｋｊを設定する。
【０１５１】
ステップＳ１２４において、部分列生成部１４によって、ｎｊ＝ｎとし、未分解系列の先頭から、最後のアルファベットまでの部分列
【０１５２】
【数４３】
2014229926.tif 000045
【０１５３】
を新たなｊ番目の部分列として決定し、切り出す。
【０１５４】
ステップＳ１２６において、上記ステップＳ１１８及びステップＳ１２４で切り出された各部分列を出力する。
【０１５５】
ステップＳ１２８において、部分列符号化部１６によって、符号化処理が行われる。ステップＳ１２８は、図９に示す符号化処理ルーチンによって実現される。
【０１５６】
＜符号化処理ルーチン＞
【０１５７】
まず、ステップＳ２００において、ステップＳ１２８で出力された各部分系列の入力を受け付ける。
【０１５８】
ステップＳ２０２において、部分列を識別する変数ｊに１を代入する。
【０１５９】
ステップＳ２０４において、部分列の（ｋｊ、ｎｊ）の組に基づいて、上記（２７）式に従って、当該部分列を符号語に変換する。
【０１６０】
ステップＳ２０６において、上記ステップＳ２０４で変換された符号語について、当該符号語を２進数で表現したデータ部分系列
【０１６１】
【数４４】
2014229926.tif 000046
【０１６２】
へ変換する。
【０１６３】
ステップＳ２０８において、上記ステップＳ２００で入力を受け付けた全ての部分列について、上記ステップＳ２０４及びステップＳ２０６の変換処理が実行されたか否かを判定する。そして、上記ステップＳ２０４及びステップＳ２０６の変換処理を全ての部分列について実行していない場合には、ステップＳ２１０において、変数ｊをインクリメントして、上記ステップＳ２０４へ戻り、上記ステップＳ２０４及びステップＳ２０６の処理を実行する。一方、上記ステップＳ２０４及びステップＳ２０６の変換処理を全ての部分列について実行した場合には、ステップＳ２１２へ進む。
【０１６４】
ステップＳ２１２において、上記ステップＳ２０６変換されたデータ部分系列の各々を連結して、上記（３１）式に示すように、圧縮データ系列φ2（ｘ1ｎ）を生成する。
【０１６５】
ステップＳ２１４において、上記ステップＳ２１２で連結した圧縮データ系列φ2（ｘ1ｎ）を出力して符号化処理ルーチンを終了する。
【０１６６】
次に、データ圧縮処理ルーチンに戻り、ステップＳ１３０において、符号化出力部１７によって、上記ステップＳ１２８で生成された圧縮データ系列φ2（ｘ1ｎ）を、ネットワークを介してデータ再生装置２０へ送信して、データ圧縮処理ルーチンを終了する。
＜データ再生装置の作用＞
次に、本実施の形態に係るデータ再生装置２０の作用について説明する。まず、データ圧縮装置１０からネットワークを介して送信された圧縮データ系列φ2（ｘ1ｎ）が、復号化入力部２１に入力されると、データ再生装置２０によって、図１０に示すデータ再生処理ルーチンが実行される。
【０１６７】
まず、ステップＳ３００において、復号化入力部２１によって、データ圧縮装置１０によって変換された圧縮データ系列φ2（ｘ1ｎ）の入力を受け付ける。
【０１６８】
ステップＳ３０２において、部分列を識別するための変数ｊに１を代入する。
【０１６９】
ステップＳ３０４において、部分列取得部２２によって、上記ステップＳ３００で入力を受け付けた圧縮データ系列φ2（ｘ1ｎ）について、ｊ番目の部分列に対応する２進列の桁数Ｌｊを、上記（２８）式に従って算出する。
【０１７０】
ステップＳ３０６において、部分列復号化部２３によって、上記ステップＳ３０４で算出されたｊ番目の２進列の桁数Ｌｊに基づいて、残りの圧縮データ系列の先頭から、２進列
【０１７１】
【数４５】
2014229926.tif 000047
【０１７２】
を切り出す。
【０１７３】
ステップＳ３０８において、部分列復号化部２３によって、上記ステップＳ３０６で切り出された２進列
【０１７４】
【数４６】
2014229926.tif 000048
【０１７５】
について、符号語
【０１７６】
【数４７】
2014229926.tif 000049
【０１７７】
を算出する。
【０１７８】
ステップＳ３１０において、部分列復号化部２３によって、上記ステップＳ３０８で算出された符号語
【０１７９】
【数４８】
2014229926.tif 000050
【０１８０】
について、上記（２７）式を用いて、ｊ番目の符号語の（ｋｊ、ｎｊ）の組を算出し、（ｋｊ、ｎｊ）の組に基づいて、部分列
【０１８１】
【数４９】
2014229926.tif 000051
【０１８２】
を復元する。
【０１８３】
ステップＳ３１２において、全ての部分列について、上記ステップＳ３０４〜ステップＳ３１０の処理が実行されたか否かを判定する。そして、上記ステップＳ３０４〜ステップＳ３１０の処理を全ての部分列について実行していない場合には、ステップＳ３１４において、部分列の添え字ｊをインクリメントして、上記ステップＳ３０４へ戻り、上記ステップＳ３０４〜ステップＳ３１０の処理を実行する。一方、上記ステップＳ３０４〜ステップＳ３１０の処理を全ての部分列について実行した場合には、ステップＳ３１６へ進む。
【０１８４】
ステップＳ３１６において、部分列復号化部２３によって、上記ステップＳ３１０で復元された部分列の各々を連結して、再生されたデータ系列を算出する。
【０１８５】
ステップＳ３１８において、上記ステップＳ３１６で算出された再生されたデータ系列を出力して、データ再生処理ルーチンを終了する。
【０１８６】
＜本実施の形態の性能評価＞
本実施の形態の動作確認及び性能評価の結果を図１１に示す。図１１では、データ系列の一例として、ベルヌーイ情報源からのランダムな出力系列をベンチマークとして利用している。ただし、ベルヌーイ情報源とは、独立同分布（Independently and Identically Distributed,略してIID）な確率変数をデータとして出力する情報源で、今回の評価実験では、各アルファベット（０か１）について、確率０．１で１の値をとるように設定した。今回の評価実験では、再帰計算における未分解系列の語頭と既に切り出された部分列との類似度を判定する距離測度として、ハミング距離（ビット当たり）を採用した。このとき、上記図４に示すように、類似度の判定を実施している未分解系列の先頭の位置によって、閾値（判定基準）を適応的に変化させている。プロット（○）は、１０００ビットのデータ系列を１００回圧縮・復元した平均値である。実線は、代表的な時分割（タイムシェアリング）符号化によるトレードオフを表しており、本実施の形態は、これを凌駕する性能であることが確認できる。
【０１８７】
以上説明したように、本実施の形態によれば、入力されたデータ系列のうちの未分解系列の語頭との距離が、予め定められた０より大きい閾値以下である部分列のうち、長さが最も長い部分列を探索し、未分解系列の先頭から、探索した部分列と対応する部分系列と後続する１個のデータとを連結した部分列を切り出すことを繰り返し、切り出された部分列の各々を符号化して、符号語に変換することにより、符号語の個数の増大を抑制して、効率的に圧縮データ系列の変換をすることができる。
【０１８８】
また、入力されたデータ系列の中に予期することができない規則性が含まれている場合であっても、それを最大限抽出して効率的にデータ圧縮・再生することができる。
【０１８９】
また、データ系列の構造や規則性などの詳細な事前知識がなくとも、データ系列を効率的に不可逆圧縮することができる。
【０１９０】
また、大量のデータ系列を効率的に記録・保存する必要がある様々な場面（例えば、バイオインフォマティクス分野における遺伝子発現パターンの分析、あるいは深宇宙探査での周波数解析等）で通信・計算・記憶資源等を効率的に運用することができる。
【０１９１】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１９２】
例えば、本実施の形態は、本発明を、データ系列を符号化して圧縮データ系列に変換するデータ圧縮装置に適用した場合を例に説明したが、これに限定されるものではなく、データ圧縮以外を目的として、データ系列を異なるデータ系列に変換するようにしてもよい。
【０１９３】
また、部分列生成部１４では、未分解系列の先頭から、語頭との距離が閾値以下である最長の部分列と対応する部分系列と、後続する１個のアルファベットとを連結した部分列を切り出す場合を例に説明したが、これに限定されるものではなく、未分解系列の先頭から、語頭との距離が閾値以下である最長の部分列と対応する部分系列と、後続する所定個（２個以上）のアルファベットとを連結した部分列を切り出すようにしてもよい。
【０１９４】
上述のデータ圧縮装置及びデータ再生装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする
【０１９５】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。例えば、当該プログラムを、上述したＲＯＭやハードディスクのみならず、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。また、ネットワーク上の他の記憶装置に当該プログラムを記憶しておき、ネットワークを介して当該プログラムをダウンロードして実行するようにしてもよい。
【０１９６】
また、上述のデータ圧縮装置及びデータ再生装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【符号の説明】
【０１９７】
１０   データ圧縮装置
１１   符号化入力部
１２   距離指標算出部
１３   部分列探索部
１４   部分列生成部
１５   反復判定部
１６   部分列符号化部
１７   符号化出力部
２０   データ再生装置
２１   復号化入力部
２２   部分列取得部
２３   部分列復号化部
２４   復号化出力部
【図３】
2014229926.tif 000052
【図５】
2014229926.tif 000053
【図６】
2014229926.tif 000054
【図７】
2014229926.tif 000055
【図８】
2014229926.tif 000056
【図９】
2014229926.tif 000057
【図１０】
2014229926.tif 000058
【図１】
2014229926.tif 000059
【図２】
2014229926.tif 000060
【図４】
2014229926.tif 000061
【図１１】
2014229926.tif 000062