(57)【要約】【課題】一人の送信者と複数の受信者とにおける信号伝送にて、各受信者に対し異なるマルチメディア信号を３つ以上を同時に送信する際、ネットワークのトラフィックを低減し、各受信者が受信する信号を効率的に圧縮復元する信号圧縮及び信号復元方法を提供する。【解決手段】本発明の信号圧縮及び信号復元方法は、伝送の対象となる信号系列である入力信号系列が複数存在し、それら入力信号系列の集合である入力信号系列集合を複数の受信者へ配送し、各受信者がそれぞれ保有する入力信号系列の集合である補助信号系列集合を用いて、補助信号系列集合に含まれない入力信号系列の集合である伝送信号系列集合を復元する信号伝送に用い、入力信号系列集合から、この入力信号系列集合を圧縮した圧縮信号系列を抽出する信号系列圧縮過程と、圧縮信号系列及び補助信号系列集合から伝送信号系列集合を復元する信号系列復元過程とを有する。【選択図】図２
2008311746.tif 000002
【特許請求の範囲】
【請求項１】
伝送の対象となる信号系列である入力信号系列を各要素とする集合である入力信号系列集合を、該入力信号系列集合に含まれる信号系列を有する複数の受信者へ伝送する信号伝送に用いる、入力信号系列集合を圧縮する信号圧縮方法であり、
圧縮信号系列グラフ作成部が、設定された一定の長さを有する任意の入力信号系列を有する前記入力信号系列集合に対し、該入力信号系列集合の経験的な確率分布である経験確率分布を用い、該入力信号系列集合に対応する圧縮信号系列を定め、該入力信号系列集合と圧縮信号系列との対応関係を示す圧縮信号系列グラフを作成する圧縮信号系列グラフ作成過程と、
信号系列分割部が、前記入力信号系列集合に含まれる各入力信号系列を、それぞれ圧縮信号系列グラフ作成過程にて定められた長さの信号系列に分割することで、分割された信号系列である分割信号系列を抽出し、該分割信号系列の集合である分割信号系列集合を出力する信号系列分割過程と、
分割信号系列集合経験分布導出部が、前記分割信号系列集合各々から、それぞれの分割信号系列集合の経験確率分布を求める分割信号系列集合経験分布導出過程と、 
圧縮信号部分系列決定部が、前記分割信号系列集合各々を、それぞれの分割信号系列集合に対応する前記経験確率分布及び前記圧縮信号系列グラフを用いて、その分割信号系列集合に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定過程と、
圧縮信号系列生成部が、前記圧縮信号部分系列の集合から、各該圧縮信号部分系列を統合し、前記入力信号系列集合に対応する圧縮信号系列を生成する圧縮信号系列生成過程と
から構成されることを特徴とする信号圧縮方法。
【請求項２】
前記圧縮信号系列グラフ作成過程は、
信号系列集合分類部が、あらかじめ設定された一定の長さを有する任意の入力信号系列の集合を、その入力信号系列集合の経験確率分布に対応させて分類する信号系列集合分類過程と、
経験分布別圧縮信号系列グラフ作成部が、該信号系列集合分類過程にて得られた分類各々に対し、該分類に含まれる入力信号系列集合各々に対応する圧縮信号系列を定め、該入力信号系列集合と圧縮信号系列との対応関係を示す経験分布別圧縮信号系列グラフを作成する経験分布別圧縮信号系列グラフ作成過程と
から構成されることを特徴とする請求項１に記載の信号圧縮方法。
【請求項３】
前記圧縮信号部分系列決定過程は、
圧縮信号部分系列先頭部決定部が、前記分割信号系列集合の各々の経験確率分布に対応する番号または該番号に対応する系列を、圧縮信号部分系列の先頭部分として決定する圧縮信号部分系列先頭部決定過程と、
圧縮信号部分系列後続部決定部が、前記分割信号系列集合の各々の経験確率分布に対応する経験分布別圧縮信号系列の集合から、該分割信号系列集合に対応する圧縮信号系列を導出し、該圧縮信号系列を圧縮信号部分系列の後続部分として決定する圧縮信号部分系列後続部決定過程と
から構成されることを特徴とする請求項１または請求項２に記載の信号圧縮方法。
【請求項４】
複数の受信者へ信号系列を伝送する際、各受信者への伝送の対象となる入力信号系列を各要素とする集合である入力信号系列集合を圧縮して作成した圧縮信号列と、各受信者があらかじめ保有する入力信号系列集合の部分集合である補助信号系列集合とからなる圧縮された圧縮信号系列から、前記補助信号系列集合に含まれない入力信号系列の集合である伝送信号系列集合を復元する信号復元方法であり、
圧縮信号系列分割部が、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割過程と、
圧縮信号系列グラフ固定部が、前記圧縮信号系列分割過程で得られた圧縮信号部分系列である復元圧縮信号部分系列の各々について、それぞれの復元圧縮信号部分系列に対応した、入力信号系列集合と圧縮信号部分系列との対応を示す圧縮信号系列グラフを、圧縮信号部分系列に対応して圧縮信号系列グラフが記憶されている記憶部から同定する圧縮信号系列グラフ固定過程と、
分割伝送信号系列集合復元部が、前記復元圧縮信号部分系列、及び補助信号系列集合を入力とし、各復元圧縮信号部分系列に対応して前記圧縮信号系列グラフ固定過程で得られた圧縮信号系列グラフである復元圧縮信号系列グラフから、前記伝送信号系列集合に対応する分割信号系列集合である分割伝送信号系列集合を復元して、復元分割伝送信号系列集合を得る分割伝送信号系列集合復元過程と、
復元伝送信号系列集合生成部が、該分割伝送信号系列集合復元過程で得られた復元分割伝送信号系列集合の集合から、それら復元分割伝送信号系列集合を統合することにより、伝送信号系列集合を復元する復元伝送信号系列集合生成過程と
から構成されることを特徴とする信号復元方法。
【請求項５】
前記圧縮信号系列グラフ同定過程において、
圧縮信号系列グラフ固定部が、前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列の各々について、該復元圧縮信号部分系列の先頭部分から、該圧縮信号部分系列を生成した経験分布別圧縮信号系列グラフを同定することを特徴とする請求項４に記載の信号復元方法。
【請求項６】
伝送の対象となる信号系列である入力信号系列を各要素とする集合である入力信号系列集合を、該入力信号系列集合に含まれる信号系列を有する複数の受信者へ伝送する信号伝送に用いる、入力信号系列集合を圧縮する信号圧縮装置であり、
設定された一定の長さを有する任意の入力信号系列を有する前記入力信号系列集合に対し、該入力信号系列集合の経験的な確率分布である経験確率分布を用い、該入力信号系列集合に対応する圧縮信号系列を定め、該入力信号系列集合と圧縮信号系列との対応関係を示す圧縮信号系列グラフを作成する圧縮信号系列グラフ作成部と、
前記入力信号系列集合に含まれる各入力信号系列を、それぞれ圧縮信号系列グラフ作成過程にて定められた長さの信号系列に分割することで、分割された信号系列である分割信号系列を抽出し、該分割信号系列の集合である分割信号系列集合を出力する信号系列分割部と、
前記分割信号系列集合各々から、それぞれの分割信号系列集合の経験確率分布を求める分割信号系列集合経験分布導出部と、 
前記分割信号系列集合各々を、それぞれの分割信号系列集合に対応する前記経験確率分布及び前記圧縮信号系列グラフを用いて、その分割信号系列集合に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定部と、
前記圧縮信号部分系列の集合から、各該圧縮信号部分系列を統合し、前記入力信号系列集合に対応する圧縮信号系列を生成する圧縮信号系列生成部と
から構成されることを特徴とする信号圧縮装置。
【請求項７】
複数の受信者へ信号系列を伝送する際、各受信者への伝送の対象となる入力信号系列を各要素とする集合である入力信号系列集合を圧縮して作成した圧縮信号列と、各受信者があらかじめ保有する入力信号系列集合の部分集合である補助信号系列集合とからなる圧縮された圧縮信号系列から、前記補助信号系列集合に含まれない入力信号系列の集合である伝送信号系列集合を復元する信号復元装置であり、
前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割部と、
前記圧縮信号系列分割過程で得られた圧縮信号部分系列である復元圧縮信号部分系列の各々について、それぞれの復元圧縮信号部分系列に対応した、信号系列集合及び圧縮信号部分系列の対応を示す圧縮信号系列グラフを、圧縮信号部分系列に対応して圧縮信号系列グラフが記憶されている記憶部から同定する圧縮信号系列グラフ固定部と、
前記復元圧縮信号部分系列、及び補助信号系列集合を入力とし、各復元圧縮信号部分系列に対応して前記圧縮信号系列グラフ固定過程で得られた圧縮信号系列グラフである復元圧縮信号系列グラフから、前記伝送信号系列集合に対応する分割信号系列集合である分割伝送信号系列集合を復元して、復元分割伝送信号系列集合を得る分割伝送信号系列集合復元部と、
該分割伝送信号系列集合復元部が生成した復元分割伝送信号系列集合の集合から、それら復元分割伝送信号系列集合を統合することにより、伝送信号系列集合を復元する復元伝送信号系列集合生成部と
から構成されることを特徴とする信号復元装置。
【請求項８】
伝送の対象となる信号系列である入力信号系列を各要素とする集合である入力信号系列集合を、該入力信号系列集合に含まれる信号系列を有する複数の受信者へ伝送する信号伝送に用いる、入力信号系列集合を圧縮する信号圧縮装置としてコンピュータを機能させるプログラムであり、
圧縮信号系列グラフ作成部が、設定された一定の長さを有する任意の入力信号系列を有する前記入力信号系列集合に対し、該入力信号系列集合の経験的な確率分布である経験確率分布を用い、該入力信号系列集合に対応する圧縮信号系列を定め、該入力信号系列集合と圧縮信号系列との対応関係を示す圧縮信号系列グラフを作成する圧縮信号系列グラフ作成ステップと、
信号系列分割部が、前記入力信号系列集合に含まれる各入力信号系列を、それぞれ圧縮信号系列グラフ作成過程にて定められた長さの信号系列に分割することで、分割された信号系列である分割信号系列を抽出し、該分割信号系列の集合である分割信号系列集合を出力する信号系列分割ステップと、
分割信号系列集合経験分布導出部が、前記分割信号系列集合各々から、それぞれの分割信号系列集合の経験確率分布を求める分割信号系列集合経験分布導出ステップと、 
圧縮信号部分系列決定部が、前記分割信号系列集合各々を、それぞれの分割信号系列集合に対応する前記経験確率分布及び前記圧縮信号系列グラフを用いて、その分割信号系列集合に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定ステップと、
圧縮信号系列生成部が、前記圧縮信号部分系列の集合から、各該圧縮信号部分系列を統合し、前記入力信号系列集合に対応する圧縮信号系列を生成する圧縮信号系列生成ステップと
を有するコンピュータ実行可能なプログラム。
【請求項９】
複数の受信者へ信号系列を伝送する際、各受信者への伝送の対象となる入力信号系列を各要素とする集合である入力信号系列集合を圧縮して作成した圧縮信号列と、各受信者があらかじめ保有する入力信号系列集合の部分集合である補助信号系列集合とからなる圧縮された圧縮信号系列から、前記補助信号系列集合に含まれない入力信号系列の集合である伝送信号系列集合を復元する信号復元装置としてコンピュータを機能させるプログラムであり、
圧縮信号系列分割部が、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割ステップと、
圧縮信号系列グラフ固定部が、前記圧縮信号系列分割部の生成した圧縮信号部分系列である復元圧縮信号部分系列の各々について、それぞれの復元圧縮信号部分系列に対応した、信号系列集合及び圧縮信号部分系列の対応を示す圧縮信号系列グラフを、圧縮信号部分系列に対応して圧縮信号系列グラフが記憶されている記憶部から同定する圧縮信号系列グラフ固定ステップと、
分割伝送信号系列集合復元部が、前記復元圧縮信号部分系列、及び補助信号系列集合を入力とし、各復元圧縮信号部分系列に対応して前記圧縮信号系列グラフ固定過程で得られた圧縮信号系列グラフである復元圧縮信号系列グラフから、前記伝送信号系列集合に対応する分割信号系列集合である分割伝送信号系列集合を復元して、復元分割伝送信号系列集合を得る分割伝送信号系列集合復元ステップと、
復元伝送信号系列集合生成部が、該分割伝送信号系列集合復元部で生成された復元分割伝送信号系列集合の集合から、それら復元分割伝送信号系列集合を統合することにより、伝送信号系列集合を復元する復元伝送信号系列集合生成ステップと
を有するコンピュータ実行可能なプログラム。
【請求項１０】
請求項８または請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音楽、静止画像、動画像及びテキストファイルなどのコンテンツを送受信する際の圧縮及び復元を行う信号圧縮方法、信号復元方法、それら装置、プログラム並びにそれらプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
近年、音楽・映像を取得あるいは生成するデバイスの普及、また大容量ネットワークの普及などにより、音楽・静止画像・動画像・テキストなどを含む多様なコンテンツのマルチメディア信号がネットワーク上を流通し、それらコンテンツを各個人のレベルにて蓄積する機会が増大している。
しかし、パーソナルコンピュータにおける記憶媒体の大容量化・低価格化、及びネットワークにおける伝送の大容量化に対し、それを上回る速度にて、取り扱う情報量が増大してきている。
【０００３】
このため、記憶媒体の容量不足やネットワークトラフィックの過度の増大を避けるための手段の一つとして、信号を再度復元可能な形にて圧縮する技術が必須となってきている。
特に、携帯端末や衛星を介した信号伝送において、通信容量の制限及びネットワーク構成の複雑性などの理由から、上記マルチメディア信号を圧縮して伝送する技術が求められている。
【０００４】
上述した携帯端末や衛星を介した信号伝送は、複数の信号提供者（＝送信者）と複数の信号被提供者（＝受信者）との存在を仮定している。
さらに、圧縮及び復元を行う実用上の観点から、伝送されるマルチメディア信号がどのような確率構造に基づいて発生するかの知識がなくても、それら知識を持っている場合と同等の効率にて圧縮が行えて伝送できることが望ましい。
【０００５】
このような信号伝送における信号圧縮技術として、図１０に示す信号伝送モデルに対しては、例えば、非特許文献１に記載された圧縮方法が知られている。
すなわち、図１０に示す信号伝送モデルとしては、１人の送信者と複数の受信者を想定し、送信者が送信する２つの信号のうち、いずれか１つの信号を各受信者が所有しているとき、各受信者が所有していない信号を受信できるように、送信者が上記２つの信号を圧縮して圧縮信号を生成し、この圧縮信号を全ての受信者に対して伝送する。
【非特許文献１】木村昭悟、植松友彦、葛岡成晃:”Universal source coding with complementary delivery,”、情報理論とその応用シンポジウム（SITA2006）予稿集, pp-803-806, 2006年11月
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１に記載の方法においては、送信者が伝送する信号が２つの場合に限られ、送信者が３つ以上の信号を送信する場合に原理的に適応することができない欠点がある。
衛星を介した信号伝送を考慮した場合、効率的な伝送を行う必要があり、伝送したい信号が多数となることが想定され、送信者が伝送する信号が３つ以上の場合にも、一人の送信者が複数の受信者に対して、それぞれ異なる情報を同時に行う信号伝送に対応する信号圧縮技術が確立されることが望まれている。
【０００７】
本発明は、このような事情に鑑みてなされたもので、一人の送信者と複数の受信者とにおける信号伝送において、各受信者に対してそれぞれ異なるマルチメディア信号を複数、特に３つ以上を同時に送信する場合、ネットワークにおけるトラフィックを低減し、各受信者が受信する信号を効率的に圧縮復元が可能な信号圧縮方法及び信号復元方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の信号圧縮方法は、伝送の対象となる信号系列である入力信号系列を各要素とする集合である入力信号系列集合を、該入力信号系列集合に含まれる信号系列を有する複数の受信者へ伝送する信号伝送に用いる、入力信号系列集合を圧縮する信号圧縮方法であり、  圧縮信号系列グラフ作成部が、設定された一定の長さを有する任意の入力信号系列を有する前記入力信号系列集合に対し、該入力信号系列集合の経験的な確率分布である経験確率分布を用い、該入力信号系列集合に対応する圧縮信号系列を定め、該入力信号系列集合と圧縮信号系列との対応関係を示す圧縮信号系列グラフを作成する圧縮信号系列グラフ作成過程と、信号系列分割部が、前記入力信号系列集合に含まれる各入力信号系列を、それぞれ圧縮信号系列グラフ作成過程にて定められた長さの信号系列に分割することで、分割された信号系列である分割信号系列を抽出し、該分割信号系列の集合である分割信号系列集合を出力する信号系列分割過程と、分割信号系列集合経験分布導出部が、前記分割信号系列集合各々から、それぞれの分割信号系列集合の経験確率分布を求める分割信号系列集合経験分布導出過程と、圧縮信号部分系列決定部が、前記分割信号系列集合各々を、それぞれの分割信号系列集合に対応する前記経験確率分布及び前記圧縮信号系列グラフを用いて、その分割信号系列集合に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定過程と、圧縮信号系列生成部が、前記圧縮信号部分系列の集合から、各該圧縮信号部分系列を統合し、前記入力信号系列集合に対応する圧縮信号系列を生成する圧縮信号系列生成過程とから構成されることを特徴とする。
【０００９】
本発明の信号圧縮方法は、前記圧縮信号系列グラフ作成過程は、信号系列集合分類部が、あらかじめ設定された一定の長さを有する任意の入力信号系列の集合を、その入力信号系列集合の経験確率分布に対応させて分類する信号系列集合分類過程と、経験分布別圧縮信号系列グラフ作成部が、該信号系列集合分類過程にて得られた分類各々に対し、該分類に含まれる入力信号系列集合各々に対応する圧縮信号系列を定め、該入力信号系列集合と圧縮信号系列との対応関係を示す経験分布別圧縮信号系列グラフを作成する経験分布別圧縮信号系列グラフ作成過程とから構成されることを特徴とする。
【００１０】
本発明の信号圧縮方法は、前記圧縮信号部分系列決定過程は、圧縮信号部分系列先頭部決定部が、前記分割信号系列集合の各々の経験確率分布に対応する番号または該番号に対応する系列を、圧縮信号部分系列の先頭部分として決定する圧縮信号部分系列先頭部決定過程と、圧縮信号部分系列後続部決定部が、前記分割信号系列集合の各々の経験確率分布に対応する経験分布別圧縮信号系列の集合から、該分割信号系列集合に対応する圧縮信号系列を導出し、該圧縮信号系列を圧縮信号部分系列の後続部分として決定する圧縮信号部分系列後続部決定過程とから構成されることを特徴とする。
【００１１】
本発明の信号復元方法は、複数の受信者へ信号系列を伝送する際、各受信者への伝送の対象となる入力信号系列を各要素とする集合である入力信号系列集合を圧縮して作成した圧縮信号列と、各受信者があらかじめ保有する入力信号系列集合の部分集合である補助信号系列集合とからなる圧縮された圧縮信号系列から、前記補助信号系列集合に含まれない入力信号系列の集合である伝送信号系列集合を復元する信号復元方法であり、圧縮信号系列分割部が、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割過程と、圧縮信号系列グラフ固定部が、前記圧縮信号系列分割過程で得られた圧縮信号部分系列である復元圧縮信号部分系列の各々について、それぞれの復元圧縮信号部分系列に対応した、入力信号系列集合と圧縮信号部分系列との対応を示す圧縮信号系列グラフを、圧縮信号部分系列に対応して圧縮信号系列グラフが記憶されている記憶部から同定する圧縮信号系列グラフ固定過程と、分割伝送信号系列集合復元部が、前記復元圧縮信号部分系列、及び補助信号系列集合を入力とし、各復元圧縮信号部分系列に対応して前記圧縮信号系列グラフ固定過程で得られた圧縮信号系列グラフである復元圧縮信号系列グラフから、前記伝送信号系列集合に対応する分割信号系列集合である分割伝送信号系列集合を復元して、復元分割伝送信号系列集合を得る分割伝送信号系列集合復元過程と、復元伝送信号系列集合生成部が、該分割伝送信号系列集合復元過程で得られた復元分割伝送信号系列集合の集合から、それら復元分割伝送信号系列集合を統合することにより、伝送信号系列集合を復元する復元伝送信号系列集合生成過程とから構成されることを特徴とする。
【００１２】
本発明の信号復元方法は、前記圧縮信号系列グラフ同定過程において、圧縮信号系列グラフ固定部が、前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列の各々について、該復元圧縮信号部分系列の先頭部分から、該圧縮信号部分系列を生成した経験分布別圧縮信号系列グラフを同定することを特徴とする。
【００１３】
本発明の信号圧縮装置は、伝送の対象となる信号系列である入力信号系列を各要素とする集合である入力信号系列集合を、該入力信号系列集合に含まれる信号系列を有する複数の受信者へ伝送する信号伝送に用いる、入力信号系列集合を圧縮する信号圧縮装置であり、設定された一定の長さを有する任意の入力信号系列を有する前記入力信号系列集合に対し、該入力信号系列集合の経験的な確率分布である経験確率分布を用い、該入力信号系列集合に対応する圧縮信号系列を定め、該入力信号系列集合と圧縮信号系列との対応関係を示す圧縮信号系列グラフを作成する圧縮信号系列グラフ作成部と、前記入力信号系列集合に含まれる各入力信号系列を、それぞれ圧縮信号系列グラフ作成過程にて定められた長さの信号系列に分割することで、分割された信号系列である分割信号系列を抽出し、該分割信号系列の集合である分割信号系列集合を出力する信号系列分割部と、前記分割信号系列集合各々から、それぞれの分割信号系列集合の経験確率分布を求める分割信号系列集合経験分布導出部と、前記分割信号系列集合各々を、それぞれの分割信号系列集合に対応する前記経験確率分布及び前記圧縮信号系列グラフを用いて、その分割信号系列集合に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定部と、前記圧縮信号部分系列の集合から、各該圧縮信号部分系列を統合し、前記入力信号系列集合に対応する圧縮信号系列を生成する圧縮信号系列生成部とから構成されることを特徴とする。
【００１４】
本発明の信号復元装置は、複数の受信者へ信号系列を伝送する際、各受信者への伝送の対象となる入力信号系列を各要素とする集合である入力信号系列集合を圧縮して作成した圧縮信号列と、各受信者があらかじめ保有する入力信号系列集合の部分集合である補助信号系列集合とからなる圧縮された圧縮信号系列から、前記補助信号系列集合に含まれない入力信号系列の集合である伝送信号系列集合を復元する信号復元装置であり、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割部と、前記圧縮信号系列分割過程で得られた圧縮信号部分系列である復元圧縮信号部分系列の各々について、それぞれの復元圧縮信号部分系列に対応した、入力信号系列集合と圧縮信号部分系列との対応を示す圧縮信号系列グラフを、圧縮信号部分系列に対応して圧縮信号系列グラフが記憶されている記憶部から同定する圧縮信号系列グラフ固定部と、前記復元圧縮信号部分系列、及び補助信号系列集合を入力とし、各復元圧縮信号部分系列に対応して前記圧縮信号系列グラフ固定過程で得られた圧縮信号系列グラフである復元圧縮信号系列グラフから、前記伝送信号系列集合に対応する分割信号系列集合である分割伝送信号系列集合を復元して、復元分割伝送信号系列集合を得る分割伝送信号系列集合復元部と、該分割伝送信号系列集合復元部が生成した復元分割伝送信号系列集合の集合から、それら復元分割伝送信号系列集合を統合することにより、伝送信号系列集合を復元する復元伝送信号系列集合生成部とから構成されることを特徴とする。
【００１５】
本発明のプログラムは、伝送の対象となる信号系列である入力信号系列を各要素とする集合である入力信号系列集合を、該入力信号系列集合に含まれる信号系列を有する複数の受信者へ伝送する信号伝送に用いる、入力信号系列集合を圧縮する信号圧縮装置としてコンピュータを機能させるプログラムであり、圧縮信号系列グラフ作成部が、設定された一定の長さを有する任意の入力信号系列を有する前記入力信号系列集合に対し、該入力信号系列集合の経験的な確率分布である経験確率分布を用い、該入力信号系列集合に対応する圧縮信号系列を定め、該入力信号系列集合と圧縮信号系列との対応関係を示す圧縮信号系列グラフを作成する圧縮信号系列グラフ作成ステップと、信号系列分割部が、前記入力信号系列集合に含まれる各入力信号系列を、それぞれ圧縮信号系列グラフ作成過程にて定められた長さの信号系列に分割することで、分割された信号系列である分割信号系列を抽出し、該分割信号系列の集合である分割信号系列集合を出力する信号系列分割ステップと、分割信号系列集合経験分布導出部が、前記分割信号系列集合各々から、それぞれの分割信号系列集合の経験確率分布を求める分割信号系列集合経験分布導出ステップと、圧縮信号部分系列決定部が、前記分割信号系列集合各々を、それぞれの分割信号系列集合に対応する前記経験確率分布及び前記圧縮信号系列グラフを用いて、その分割信号系列集合に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定ステップと、圧縮信号系列生成部が、前記圧縮信号部分系列の集合から、各該圧縮信号部分系列を統合し、前記入力信号系列集合に対応する圧縮信号系列を生成する圧縮信号系列生成ステップとを有するコンピュータ実行可能なプログラムである。
【００１６】
本発明のプログラムは、複数の受信者へ信号系列を伝送する際、各受信者への伝送の対象となる入力信号系列を各要素とする集合である入力信号系列集合を圧縮して作成した圧縮信号列と、各受信者があらかじめ保有する入力信号系列集合の部分集合である補助信号系列集合とからなる圧縮された圧縮信号系列から、前記補助信号系列集合に含まれない入力信号系列の集合である伝送信号系列集合を復元する信号復元装置としてコンピュータを機能させるプログラムであり、圧縮信号系列分割部が、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割ステップと、圧縮信号系列グラフ固定部が、前記圧縮信号系列分割部の生成した圧縮信号部分系列である復元圧縮信号部分系列の各々について、それぞれの復元圧縮信号部分系列に対応した、入力信号系列集合と圧縮信号部分系列との対応を示す圧縮信号系列グラフを、圧縮信号部分系列に対応して圧縮信号系列グラフが記憶されている記憶部から同定する圧縮信号系列グラフ固定ステップと、分割伝送信号系列集合復元部が、前記復元圧縮信号部分系列、及び補助信号系列集合を入力とし、各復元圧縮信号部分系列に対応して前記圧縮信号系列グラフ固定過程で得られた圧縮信号系列グラフである復元圧縮信号系列グラフから、前記伝送信号系列集合に対応する分割信号系列集合である分割伝送信号系列集合を復元して、復元分割伝送信号系列集合を得る分割伝送信号系列集合復元ステップと、復元伝送信号系列集合生成部が、該分割伝送信号系列集合復元部で生成された復元分割伝送信号系列集合の集合から、それら復元分割伝送信号系列集合を統合することにより、伝送信号系列集合を復元する復元伝送信号系列集合生成ステップとを有するコンピュータ実行可能なプログラムである。
【００１７】
本発明の記録媒体は、上記記載のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００１８】
本発明によれば、１人の送信者と複数の受信者を想定した場合、マルチメディア信号を各受信者の端末に送信する際、複数、特に３つ以上の信号系列を１つの圧縮信号系列として送信するため、ネットワークにおけるトラフィックを低減することができる。
また、本発明によれば、３以上の入力信号系列集合と圧縮系列信号との対応を示す圧縮信号系列グラフを、圧縮側と復元側とがそれぞれの記憶部に共通に記憶しているため、圧縮信号系列により、上記圧縮信号系列グラフから他方の信号系列を抽出することにより、効率的に伝送する入力信号系列の圧縮及び復元が可能である。
【発明を実施するための最良の形態】
【００１９】
本発明で言及する信号伝送の例として、図１に示すような、１人の送信者と、３人の受信者を想定し、かつ送信者が所有する３つの信号のうちいずれか１つの信号を各受信者が所有している場合、各受信者が所有していない信号を受信できるように、送信者が信号を圧縮し、全ての受信者に対して同一の圧縮信号を送信者から伝送する。図１は上記例の実施形態による伝送システムの構成を示す概念図である。
この図１において、送信者１００は信号Ｘ，Ｙ，Ｚを有しており、受信者２０１、２０２、２０３それぞれ信号Ｚ，Ｙ，Ｘを有している。この状態にて、送信者１００は、受信者２０１に対して信号Ｘ及びＹを、受信者２０２に対して信号Ｘ及びＺを、受信者２０３に対して信号Ｙ，Ｚを送信する。
【００２０】
そして、本発明の信号伝送においては、送信者が所有する信号を受信者が正しく受信できない確率が無視できる程度に小さくすることが要求される。
このとき、図１に示す信号モデルに対しては、信号の圧縮率をエントロピーを用いて表現したときの理論的限界値、及び圧縮率がその理論的限界値に漸近する信号圧縮方法の存在が、以下の非特許文献２に示されている。
（非特許文献2）A・ D. Wyner, J. K. Wolf, and F・ M. J. Willems“Communicating via a processing broadcast satellite,”IEEE Transactions on Information Theory, Vol・ 48, N0. 6, pp. 1243-1249, June 2002.
【００２１】
上述したように、本発明においては、伝送すべき信号が従う確率構造についての知識がなくても、圧縮率が上記非特許文献２に示される理論的限界値に漸近する信号圧縮方法を示すものである。
本発明においては、後に詳述するが、以下のａ及びｂの２点により、上記の理論的限界値に漸近する信号圧縮を行う信号伝送方法を実現している。
ａ．与えられた複数の信号系列のみから得られる経験的な確率分布（以下、同時経験分布）を用いることにより、信号系列がどのような確率構造に基づいて生成されたかについての知識がなくても、圧縮率が理論的限界値に漸近する信号圧縮を可能にする。
ｂ．与えられた複数の信号系列を圧縮する際に、信号系列の集合と圧縮信号との対応関係を上記非特許文献１とは異なる方法により表現することにより、受信者が所有している情報を基に、受信者が所有していない情報を復元する操作を容易に行う。
【００２２】
＜第１の実施形態＞
本実施形態における信号系列の伝送を行う伝送システムとしては、図２の概念図に示すように、信号系列を圧縮する信号系列圧縮部１が信号系列を送信する送信側端末１００に設けられ、圧縮された信号系列（圧縮信号系列）を復元する系列復元部２（あるいは３、４）が受信側端末２０１（あるいは２０２，２０３）に設けられている。
【００２３】
ここで、送信側端末１００は伝送の対象となる複数の入力信号系列を入力し、これら信号系列から圧縮信号系列を生成し、この生成した圧縮信号系列を、上記入力信号系列のうちいくつかの信号系列からなる集合である補助信号系列集合を所有する（各受信端末の記憶部に記憶されている）複数の受信側端末２０１、２０２、２０３…へ伝送する。
一方、受信側端末２０１、２０２、２０３…各々は、補助系列集合を用いて、上記圧縮信号系列から、自身の所有していない信号系列からなる集合である伝送信号系列集合を、それぞれの系列復元部により復元し、その復元した伝送信号系列集合である復元伝送信号系列集合を出力する。
【００２４】
以下の説明において、簡単化のため、全ての信号系列を文字系列であるとし、信号系列を単に系列と呼ぶ。入力信号系列と、復元信号系列及び補助信号系列とについても、同様に、それぞれ入力系列、復元系列及び補助系列と呼ぶ。
また、入力系列は、特に断らない限りにおいて、同一の長さｎを持つと仮定する。入力系列の数をＮsとして第ｊ番目（ｊ＝１，２，…，Ｎｓ）の各入力系列ｘ（ｊ）ｎの各文字ｘｉ（ｊ）（ｉ＝１，２，…，ｎ）は有限文字列χ（ｊ）の要素であるとする。この入力系列集合を以下の（１）式として表す。
【００２５】
【数１】
2008311746.tif 000003
【００２６】
上記（１）式において、ＩＮｓ＝｛１，２，…，Ｎｓ｝である。
また、受信者がＮｄ人存在すると、第ｋ番目（ｋ＝１，２，…，Ｎd）の受信者は、以下の（２）式により表される補助系列集合を有している。この補助系列集合は、受信者があらかじめ保有する入力信号系列の集合である。すなわち、送信者が送信する入力信号系列の集合からこの補助系列集合の信号系列を除いた残りが、その受信者が受信する入力信号系列となる。
【００２７】
【数２】
2008311746.tif 000004
【００２８】
このとき、第ｋ番目の受信者は、以下の（３）式に示す伝送系列集合を復元することを目的とする。
【００２９】
【数３】
2008311746.tif 000005
【００３０】
例えば、図１に示す信号伝送モデルにおいて、入力系列数はＮｓ＝３、入力系列集合はＸｎ＝｛ｘ（１）ｎ，ｘ（２）ｎ，ｘ（３）ｎ｝（ｘ（ｊ）ｎ∈χ（ｊ）、ｊ＝１，２，３）、受信者数はＮｄ＝３、各受信者の補助系列集合のインデックスはそれぞれＩＮｓ−Ｓ１＝｛１｝、ＩＮｓ−Ｓ２＝｛２｝、ＩＮｓ−Ｓ３＝｛３｝である。
よって、このとき、第ｋ番目の受信者は、補助系列集合Ｓ（〜Ｓｋ）ｎ＝｛ｘ（ｋ）ｎ｝を保有し、伝送系列集合Ｘ（Ｓｋ）ｎ＝｛ｘ（ｊ）ｎ｝ｊ≠ｋを復元する。
以下、簡単のため、まず、図１に示す信号伝送モデルについて、入力系列数はＮｓ＝３とした例にて実施形態を示す。その後、入力系列数Ｎｓを所定の複数の数値とする一般的な信号伝送モデルについての実施形態を示すこととする。
系列圧縮部１は、入力信号系列集合を入力し、入力信号系列集合を圧縮した圧縮系列を抽出し、その圧縮系列を出力する。
【００３１】
圧縮系列の抽出方法は特に限定されるものではないが、本実施形態において、図３に示すように、系列圧縮部１は、圧縮系列グラフ作成部１１と、系列分割部１２と、系列集合経験分布導出部１３と、圧縮部分系列決定部１４と、圧縮系列生成部１５とを有している。この系列圧縮部１により処理される圧縮系列の抽出方法について述べる。
圧縮系列グラフ作成部１１は、系列集合分類部１１１と、経験分布別圧縮系列グラフ作成部１１３とによって構成されている。圧縮系部分系列決定部１４は、圧縮部分系列先頭部決定部１４１と、圧縮部分系列後続部決定部１４２とから構成されている。
【００３２】
以下、図３及び図４を参照して、第１の実施形態による信号圧縮の処理を説明する。図４は本実施形態における信号圧縮の処理の流れを示すフローチャートである。
圧縮系列グラフ作成部１１は、予め設定されたある一定の長さを持つ任意の系列の集合について、その系列集合の経験的な確率分布である同時経験分布を用い、その系列集合に対応する圧縮系列を定める。
また、圧縮系列グラフ作成部１１は、求めた圧縮系列集合と、この圧縮系列集合との対応関係を示すグラフである圧縮系列グラフを作成し、その圧縮系列グラフを出力する。
【００３３】
ここで、圧縮系列グラフ作成部１１が行う圧縮系列グラフの作成方法は特に限定されるものではないが、本実施形態においては以下のように作成する。
以下、これらによる圧縮系列グラフの作成方法を説明する。
上記系列集合分類部１１１は、ある一定の長さを持つ任意の系列の集合を同時経験分布により分類し（ステップＳ１及びＳ２）、得られた分類である集合を経験分布共有系列集合族の集合として出力する（ステップＳ３）。
上記系列集合分類部１１１は、例えば、系列集合を、以下に示すようにして分類する。
まず、系列集合分類部１１１は、分類決定に用いる系列の長さ、すなわち系列長ｍを設定する。この系列長ｍは、ユーザが入力しても良いし、あるいは系列集合分類部１１１が入力系列の系列長と同一に設定しても良い、また、この系列長ｍは、各入力系列の系列長ｎと同一である必要はないが、ｍ≦ｎを満たす必要がある。
【００３４】
次に、系列集合分類部１１１は、内部にて系列長がｍである系列の集合を以下の（４）式にて表す。
【００３５】
【数４】
2008311746.tif 000006
【００３６】
また、系列集合分類部１１１は、任意の系列集合についてその経験的な確率分布である以下の（５）式に示す同時経験分布を、以下の（６）式を用いて求める（算出する）。
【００３７】
【数５】
2008311746.tif 000007
【００３８】
【数６】
2008311746.tif 000008
【００３９】
上記（６）式において、Ｎ（ａ１，ａ２，ａ３｜Ｘ〜ｍ）は系列集合Ｘ〜ｍの中で文字集合（ａ１，ａ２，ａ３）が生起する回数である。
また、Ｐｍ（χ（１）×χ（２）×χ（３））は直積文字集合χ（１）×χ（２）×χ（３）からなる系列長ｍの系列についての同時経験分布全体の集合である。
例として、以下の（７）式による系列長ｍ＝４の２元系列の集合を考える。
【００４０】
【数７】
2008311746.tif 000009
【００４１】
上記（７）式の系列集合についての以下の（８ａ）に示す同時経験分布は、以下の（８）式のように表せる。
【００４２】
【数８】
2008311746.tif 000010
【００４３】
そして、系列集合分類部１１１は、同一の同時経験分有Ｑを持つ系列長ｍの系列集合の集合ＴＱｍを以下の（９）式により作成し、この集合(経験分布共有系列集合族)を求める分類として出力する。また、系列集合分類部１１１は、この求めた経験分布共有系列集合族を内部の記憶部に記憶する。
【００４４】
【数９】
2008311746.tif 000011
【００４５】
ただし、｛χ（ｊ）ｍ｝はχ（ｊ）のｍ次直積集合である。
例として、上記（８）式の同時経験分布Ｑについて、その経験分布共有系列集合族は、以下の（１０）式に示すように、（０，０，０）の組、（０，０，１）の組、（０，１，０）の組、（１，０，０）の組がそれぞれ１回出現する、系列長ｍ＝４の系列の組の集合となる。
【００４６】
【数１０】
2008311746.tif 000012
【００４７】
次に、経験分布別圧縮系列グラフ作成部１１３は、上記系列集合分類過程１１１から出力された分類(経験分有共有系列集合族)の集合を入力し、各経験分布共有系列集合族に含まれる系列集合各々に圧縮系列を対応させ（ステップＳ４）、系列集合と圧縮系列との対応関係を示す圧縮系列グラフである経験分布別圧縮系列グラフを作成し、この経験分布別圧縮系列グラフの集合を出力する（ステップＳ５及びＳ６）。
【００４８】
本実施形態において、経験分布別圧縮系列グラフ作成部１１３は、以下のステップＳ４以降の処理において、経験分布別圧縮系列グラフを、例えば、以下のようにして作成する。この作成の過程を図５を用いて説明する。
この図５においては、（８）式に示す同時経験分布Ｑについての経験分布別圧縮系列グラフの作成過程を示している。
まず、経験分布別圧縮系列グラフ作成部１１３は、同時経験分布Ｑ各々について、その同時経験分布に対応する経験分有共有系列集合ＴＱｍに含まれる系列集合を抽出し、これら系列集合各々に頂点Ｃを割り当てる。
【００４９】
次に、経験分布別圧縮系列グラフ作成部１１３は、長さｍの補助系列ｘ（ｋ）ｍ（ｋ＝１，２，３）各々について、この系列集合を構成要素として持つ集合ＴＱｍ内の系列集合を取り出し（抽出し）、抽出した系列集合に対応する頂点の間に辺を配置する。
例えば、（８）式に示す同時経験分布Ｑにおいては、図５に示すような頂点と辺の配置によるグラフが作成される。
ただし、図５は、系列集合（１０００，０１００，００１０）に対応する頂点を中心として、その周辺のグラフ構造のみを示している。
【００５０】
ここで、周辺とは、系列集合の一つに注目して、その頂点（系列集合）の値（系列集合の有する構成要素）のうち少なくとも一つ（の構成要素）は同じとなる系列集合を示している。
本実施形態の場合、系列集合（１０００，０１００，００１０）の周辺のグラフ構造が図５及び図６に示されており、図５の下部における六角形においては第１要素である「１０００」が共通であり、左上の六角形においては第２要素である「０１００」が共通であり、右上の六角形においては第３要素である「００１０」が共通である。
【００５１】
そして、経験分布別圧縮系列グラフ作成部１１３は、上述したように作成されたグラフの各頂点に対して、後に圧縮系列に対応することとなる番号を割り当てる。
このとき、経験分布別圧縮系列グラフ作成部１１３は、辺で連結されている頂点同士において、全て相異なる番号が割り当てられるように、それぞれに番号を割り当てる。
また、図６は、図５にて説明した番号の割り当て方の１例を示す概念図である。具体的な番号の割り当て方法については、後述する。
【００５２】
上記のようにして作成されたグラフを、同時経験分布Ｑについての経験分有別圧縮系列グラフとする。作成された経験分布別圧縮系列グラフは、以下の性質を持つ。
ただし、集合ＴＱ；ｋｍ（ｘ（ｋ）ｍ）（ｋ＝１，２，３）に示す集合は、以下の（１１）、（１２）及び（１３）式に示すように、長さｍの補助系列ｘ（ｋ）ｍが与えられたときの、伝送系列集合に対応する経験分布共有系列集合族の構成要素の集合である。
【００５３】
【数１１】
2008311746.tif 000013
【００５４】
【数１２】
2008311746.tif 000014
【００５５】
【数１３】
2008311746.tif 000015
【００５６】
例えば、（８）式に示す同時経験分布Ｑにおいて、経験分布共有系列集合族の構成要素の集合ＴＱ；１ｍ（１０００）は以下の（１４）式のように表せる。
【００５７】
【数１４】
2008311746.tif 000016
【００５８】
図６に示すように、作成される経験分布別圧縮系列グラフは、以下の性質を有している。
１．各頂点は３個の完全部分グラフに含まれており、それら完全部分グラフに含まれない頂点との間には辺は存在しない。ただし、完全グラフとは、任意の頂点の間に辺が存在するグラフである。
２．各完全部分グラフは、長さｍの補助系列ｘ（ｋ）ｍが与えられたときの、経験分布共有伝送系列集合ＴＱ；ｋｍ（ｘ（ｋ）ｍ）に対応している。完全部分グラフの次数は、受信者のインデックスｋ及び同時経験分布Ｑのみに依存しており、長さｍの補助系列集合ｘ（ｋ）ｍには依存しない。以下、この次数をｍｋ（Ｑ）によって表す。
３．経験分布別圧縮系列グラフの次数はＱのみに依存しており、以下の（１５）式で与えられる。
【００５９】
【数１５】
2008311746.tif 000017
【００６０】
上述したグラフの各頂点への番号の割り当ては、一般にグラフの頂点彩色問題として知られている。グラフの頂点彩色の方法としては、例えば、以下の２つの方法がよく知られている。
１．貪欲アルゴリズム。すなわち、各頂点に順に割り当て可能な番号を割り当てる。この方法を用いると、グラフの次数よりも１つ多い数の番号を用意すれば、頂点彩色が可能となる。
２．ブルックスの定理の証明を利用した方法。この方法を用いると、グラフが完全グラフでも奇数頂点数の閉路でもなければ、グラフの次数だけ番号を用意すれば、頂点彩色が可能となる。経験分布別圧縮系列グラフは、完全グラフでも奇数頂点数の閉路でもない。
以下、頂点数ｎの完全グラフをＫｎで表現する。
【００６１】
以下、ブルックスの定理の証明を利用した方法について簡単に説明する。また、ブルックスの定理の証明を利用した方法の説明に用いた記号は、この説明のみ用いられるものである。
１．グラフＧの次数△(Ｇ）が２以下であるとき、
(ａ)△(Ｇ)＝０であれば、Ｇは完全グラフＫ１である．
(ｂ)△(Ｇ)＝１であれば、Ｇは完全グラフＫ２である．
(ｃ)△(Ｇ)＝２であれば、Ｇは単純パスか偶数頂点の閉路かのいずれかである。
Ｇが単純パスか偶数頂点数の閉路であれば、Ｇの辺を辿りながらＧの頂点に交互に      異なる色を割り当てることにより、△(Ｇ)＝２個の色で塗り分けることができる。
【００６２】
２．△(Ｇ)≧３であるとき、
（ａ）ある１つの頂点ｖについて、その頂点ｖをグラフＧから取り除くことによってＧが非連結になる場合、
ｉ．その非連結となる２つの部分グラフに頂点ｖをそれぞれ加えた部分グラフＧ１、Ｇ２について、再帰的に上記非特許文献３の方法を適用する。
ii．頂点ｕ割り当てられる色がＧ１とＧ２とで一致するように、Ｇ２の色を適切に取り替える（変更する）。
【００６３】
（ｂ）ある隣接していない２つの頂点ｕ，ｖについて、それら頂点ｕ，ｖをグラフＧから取り除くことによってＧが非連結になる場合、
ｉ．その非連結となる２つの部分グラフに頂点ｕ．ｖをそれぞれ加えた部分グラフＧ１，Ｇ２について、再帰的に非特許文献３の方法を適用する。
ii．頂点ｕとｖが、部分グラフＧ１及びＧ２のいずれにおいても異なる色で塗られている場合には、ｕ及びｕそれぞれに割り当てられる色がＧ１とＧ２で一致するように、Ｇ２の色を適切に取り替える。
iii．頂点ｕとｖが、部分グラフＧ1で同じ色に塗られている場合、
Ａ．部分グラフＧ１においては、頂点ｕとｖにはいずれも△（Ｇ）−１本の辺が連  結している。そうでなければ、頂点ｕ，ｖのいずれかの色を別の色に取り替えて、２（ｂ）iiの場合に変更することができる。
Ｂ．このとき、部分グラフＧ２においては、頂点ｕとｕはいずれも１本の辺しか連  結していない。部分グラフＧ２内で頂点ｖと隣接する唯一の頂点をｗとすると、頂点ｕとｗを取り除いてもＧが非連結になるので、このｗに読み替えて２ｂに戻る。
iv．頂点ｕとｖが、部分グラフＧ２で同じ色で塗られている場合、２（ｂ）iiiと同様である。
【００６４】
（ｃ）隣接しない２つの頂点をどのように選んでも、それら頂点をグラフＧから取り除        いたグラフが非連結にならない場合、
ｉ．△(Ｇ)本の辺が連結している頂点ｕに隣接し、かつ互いに隣接していない２つの頂点ｕ，ｗを検出する。このような頂点ｕ，ｗを検出できない場合、グラフＧは完全グラフである。
ii．グラフＧから頂点ｕ，ｗを取り除いた部分グラフＧから取り除いた部分グラフＧ−ｕ−ｗについて、頂点ｕを根とする全域木(グラフの全ての頂点を構成要素として含む木)を検出する。全域木の構築は、単純な貪欲法で実現できる。すなわち、初期構成要素を根の頂点として、既に構成要素となっている頂点に隣接する頂点を、閉路を形成しないように取り込んでいく。
iii．頂点ｕとｗを同じ色で塗る。
iv．上記全域木を葉から順に辿りながら、辿った順に頂点に色を塗る。このとき、  根ｖ以外の頂点は、より根に近い隣接頂点が全域木内に１つ以上存在することから、△(Ｇ)個の色のうちいずれかで塗ることが可能である。また、根ｕついては、グラフＧで隣接する頂点＊が同じ色で塗られていることから、同様に△(Ｇ)個の色のいずれかを選ぶことができる。
【００６５】
上述したように、経験分布別圧縮系列グラフ作成部１１３は、経験分布別圧縮系列グラフの各頂点に割り当てられた番号を、ｃ２＝ｃ２（Ｑ）桁の｜Ｚ｜進表現とすることにより、各頂点に対応する系列集合Ｘ〜ｍに割り当てられる圧縮系列ｚ〜ｃ２（Ｘ〜ｍ）が得られる。
ここで、上記Ｚは圧縮系列を構成する文字の集合であり、ｃ２（Ｑ）は以下の（１６）式にて与えられる。
【００６６】
【数１６】
2008311746.tif 000018
【００６７】
そして、上記ステップＳ５及びＳ６の説明の通り、圧縮系列グラフ作成部１１は、前記経験分布別圧縮系列グラフの集合を圧縮系列グラフとして出力するとともに内部の記憶部に記憶する。
【００６８】
次に、系列分割部１２は、入力系列集合を入力し、この入力系列各々を上記圧縮系列グラフ作成部１１にて設定された系列長の系列に分割することで、分割入力系列を抽出し（生成し）、それら分割入力系列の集合である分割入力系列集合について、その集合である分割入力系列集合族を出力する（ステップＳ７）。
本実施形態において、各入力系列ｘ（ｊ）ｎ∈｛χ（ｊ）｝ｎ（ｊ＝１，２，３）は、上記系列集合分類部１１１で定めた系列長ｍを用いて、以下の（１７）式に示すように分割される。
【００６９】
【数１７】
2008311746.tif 000019
【００７０】
上記（１７）式において、Ｌは以下の（１８）式により表せる。
【００７１】
【数１８】
2008311746.tif 000020
【００７２】
また、上記（１８）式において、ｘ（ｊ）ｋｉは系列ｘ（ｊ）ｎの第ｉ成分から第ｋ成分までを切り出した部分系列、すなわちｘ（ｊ）ｋｉ＝ｘ（ｊ）iｘ（ｊ）ｉ＋１・・・ｘ（ｊ）ｋである。
また、floor（ｘ）は実数ｘ以下の最大の整数である。上記の分割方法は、すなわち、系列の先頭から順に系列長ｍの部分系列を切り出し、系列長ｍの部分系列が切り出せなくなったところで系列分割を終了し、残りの部分系列をそのまま出力する方法である。
上述したように、系列分割部１２は、下記の（１９）式及び（２０）式に示す分割入力系列集合を抽出し（生成し）、これら分割入力系列集合の集合である分割入力系列集合族を出力するとともに記憶部に記憶する。ただし、ｍ’＝ｍｏｄ（ｎ，ｍ）＝ｎ−Ｌｍである。
【００７３】
【数１９】
2008311746.tif 000021
【００７４】
【数２０】
2008311746.tif 000022
【００７５】
次に、系列集合経験分布導出部（分割信号系列集合経験分布導出部）１３は、上記分割入力系列集合族を系列分割部１２から入力し、その分割入力系列集合族に含まれる分割系列集合の各々から、同時経験分布を導出し、その同時経験分布の集合を出力するとともに記憶部に記憶する（ステップＳ８）。
各分割系列集合分布Ｘｍ（ｌ）（ｌ＝１，２，…，Ｌ）についての同時経験分布ＱＸｍ（ｌ）ｍは、上記系列集合分類部１１１に示す方法と同様にして得られる。
ここで、系列集合経験分布導出部１３は、Ｌ＋１番目の分割系列集合Ｘｍ（Ｌ＋１）については、同時経験分布を抽出しない。すなわち、系列長ｍに満たない余りの分割系列集合については同時経験分布の抽出を行わない。
【００７６】
圧縮部分系列決定部１４は、経験分布別圧縮系列グラフの集合、分割入力系列集合族及び同時経験分布の集合各々を上記記憶部から入力し、この分割入力系列集合族に含まれる分割系列集合の各々について、対応する同時経験分布及び経験分布別圧縮系列グラフを用いて、その分割系列集合に対応する圧縮系列である圧縮部分系列を定め、その圧縮部分系列の集合を出力するとともに記憶部に記憶する（ステップＳ９）。
圧縮部分系列の決定方法は、特に限定されるものではないが、本実施形態においては、以下に示すように、圧縮部分系列先頭部決定部１４１と、圧縮部分系列後続部決定部１４２とによって作成される方法にて以下に説明する。
【００７７】
圧縮部分系列先頭部決定部１４１は、上記分割入力系列集合族及び同時経験分布の集合を上記記憶部から入力し、この分割入力系列集合族に含まれる分割入力系列集合の各々について、その分割入力系列集合の同時経験分布に対応する番号もしくはその番号に対応する系列を、圧縮部分系列の先頭部分とし、その圧縮部分系列の先頭部分の集合を出力する。
ここで、本実施形態において、圧縮部分系列の先頭部分は、圧縮部分系列先頭部決定部１４１により以下のようにして決定される。
同時経験分布全体の集合Ｐｍ（χ（１）×χ（２）×χ（３））の各要素に対して異なる番号があらかじめ与えられているとする。
このとき、上記同時経験分布全体の集合の要素数｜Ｐｍ（χ（１）×χ（２）×χ（３））｜は以下の（２１）式に示す範囲にある。
【００７８】
【数２１】
2008311746.tif 000023
【００７９】
同時経験分布全体の集合の要素数は上記（２１）式に示す範囲を有しているため、同時経験分布全体の集合Ｐｍ（χ（１）×χ（２）×χ（３））の各要素に対する番号の数を、高々、以下の（２２）式に示す数の種類を用意すれば良い。
【００８０】
【数２２】
2008311746.tif 000024
【００８１】
ここで、圧縮部分系列先頭部決定部１４１は、分割系列集合Ｘｍ（ｌ）（ｌ＝１，２，３）に対して、その同時経験分布ＱＸｍ（ｌ）ｍに対応する番号を割り当てる。
そして、圧縮部分系列先頭部決定部１４１は、各分割系列集合に割り当てられた番号を、以下の（２３）式に示すｃ１桁の｜Ｚ｜進表現に変換し、その｜Ｚ｜進表現を、分割系列集合Ｘｍ（ｌ）に対応する圧縮部分系列の先頭部分として、以下の（２４）式に示すように決定する。
【００８２】
【数２３】
2008311746.tif 000025
【００８３】
【数２４】
2008311746.tif 000026
【００８４】
圧縮部分系列後続部決定部１４２は、上記経験分布別圧縮系列グラフの集合、上記分割入力系列集合族、及び上記同時経験分布の集合を上記記憶部から入力する。
そして、圧縮部分系列後続部決定部１４２は、入力された分割入力系列集合の各々について、その分割入力系列集合の同時経験分布に対応する経験分布別圧縮系列グラフから、その分割入力系列集合に対応する圧縮系列を導出し、これを圧縮部分系列の後続部として決定し、その圧縮部分系列の後続部の集合を出力する（ステップＳ９）。
【００８５】
本実施形態において、上述した圧縮部分系列の後続部の決定は、以下のように圧縮部分系列後続部決定部１４２が処理する。
まず、圧縮部分系列後続部決定部１４２は、分割入力系列集合Ｘｍ（ｌ）（ｌ＝１，２，…，Ｌ）に対して、その同時経験分布ＱＸｍ（ｌ）ｍに対応する経験分布別圧縮系列グラフを記憶部から選択して読み出す。
次に、圧縮部分系列後続部決定部１４２は、記憶部から読み出した経験分布別圧縮系列グラフの中から、分割入力系列集合Ｘｍ（ｌ）対応する頂点を検出し、この検出された頂点に割り当てられた以下の（２５）式として表される圧縮系列を導出（抽出）する。
【００８６】
【数２５】
2008311746.tif 000027
【００８７】
上記（２８）式において、ｃ２（ｌ）は、ｌ番目の分割入力系列集合に対応する圧縮系列の系列長である。
上記経験分布別圧縮系列グラフ作成部１１３により、ｃ２（ｌ）は、ｌ番目の分割入力系列集合の同時経験分布Ｑｌ＝ＱＸｍ（ｌ）ｍによって決定され、圧縮部分系列後続部決定部１４２により以下の（２６）式により求められる。
【００８８】
【数２６】
2008311746.tif 000028
【００８９】
そして、圧縮部分系列後続部決定部１４２は、上記（２６）式により求められた圧縮系列ｚ〜ｃ２（ｌ）（ｌ；２）を、分割系列集合Ｘｍ（ｌ）に対応する圧縮部分系列の後続部として出力する。
上述したように、圧縮部分系列決定部１４は、上記の処理により抽出された圧縮部分系列の先頭部ｚ〜ｃ１（ｌ）（ｌ；１）と後続部ｚ〜ｃ２（ｌ）（ｌ；２）とを連結した系列ｚ〜ｃ（ｌ）を、下記に示す（２７）式にて表される圧縮部分系列として、この圧縮部分系列の集合を出力する。下記の（２７）式において、「＊」は系列の連接を表す演算子であり、ｃ（ｌ）＝ｃ１＋ｃ２（ｌ）はｌ番目の分割系列集合に対応する圧縮部分系列の長さである。
【００９０】
【数２７】
2008311746.tif 000029
【００９１】
次に、圧縮系列生成部１５は、上記圧縮部分系列決定部１４から出力される圧縮部分系列の集合から圧縮部分系列を連結して統合することにより、入力系列集合に対応する圧縮系列を生成し、その圧縮系列を出力する（ステップＳ１０）。
本実施形態において、圧縮系列生成部１５は、入力系列集合Ｘｎ＝（ｘ（１）ｎ，ｘ（２）ｎ，ｘ（３）ｎ）に対応する圧縮系列ｚｃ＊（Ｘｎ）を、以下の（２８）式に示す構成として決定する。
【００９２】
【数２８】
2008311746.tif 000030
【００９３】
上記（２８）式において、ｃ＊は、以下の（２９）式により表される入力系列集合Ｘｎに対応する圧縮系列の長さである。
【００９４】
【数２９】
2008311746.tif 000031
【００９５】
すなわち、上記（２８）式に示す圧縮系列の構成は、各圧縮部分系列を連結した後で、最後に上記系列分割部１２で余った部分系列を圧縮せずにそのまま連結して統合した構成である。
上述したように、系列圧縮部１は、各部の処理により、上記圧縮系列ｚｃ＊（Ｘｎ）を出力する。
【００９６】
次に、本実施形態における系列復元部２（または３及び４）による圧縮系列の復元処理について説明する。系列復元部２は、本実施形態の構成による復元伝送系列集合の復元方法として特に限定されるものではないが、図７に示すように、圧縮系列分割部２１と、圧縮系列グラフ同定部２２と、分割系列集合復元部２３と、復元系列集合生成部２４とから構成されている。
【００９７】
上述した図７の構成により、系列復元部２は、上記系列圧縮部１から出力された圧縮系列を入力し、かつ自身の補助系列集合記憶部から補助系列集合を読み出し、これら圧縮系列と補助系列集合とから伝送系列集合を復元し、復元された伝送系列集合である復元伝送系列集合を出力する。系列復元部２は、入力される圧縮系列及び補助系列集合を一端、補助系列集合記憶部に記憶し、必要に応じて読み出し、復元の処理を行う。
ここで、経験分布別圧縮系列グラフは、系列圧縮部１にて生成されたものと同一のものが予め各受信端末の補助系列集合記憶部に記憶されている。例えば、送信側端末１００が上記経験分布別圧縮系列グラフを作成し、この経験分布別圧縮系列グラフが設定された周期毎に、送信側端末１００から各受信側端末に対して送信されて同期が取られている。
以下、この系列復元部２により処理される復元伝送系列集合の復元方法について述べる。
【００９８】
圧縮系列分割部２１は、前記圧縮系列を入力し、圧縮系列を分割することで圧縮部分系列を復元し、復元した圧縮部分系列である復元圧縮部分系列についてその集合を出力する（ステップＳ２１及びＳ２２）。
本実施形態において、圧縮系列分割部２１は、圧縮部分系列を、以下のようにして復元する。
ここで、入力された圧縮系列ｚｃ＊から、すでにｌ−１番目までの以下の（３０）式に示す復元圧縮部分系列が復元されているものとする。以下の（３０）式において、ｃ＾（ｌ）はｌ番目の復元圧縮部分系列の系列長である。
【００９９】
【数３０】
2008311746.tif 000032
【０１００】
まず、圧縮系列分割部２１は、圧縮系列ｚｃ＊のσｌ＋１番目の文字を先頭としてｃｌ文字を切り出し、このｃｌ文字を１番目の復元圧縮部分系列の先頭部ｚ＾ｃ１（ｌ；１）とする。ここで、σｌは以下の（３１）式にて与えられる。
【０１０１】
【数３１】
2008311746.tif 000033
【０１０２】
また、ｃｌは入力系列集合に依存せず、
定数（＝（log｜ｚ｜（ｍ＋１））・｜χ（１）｜・｜χ（２）｜・｜χ（３）｜）
であることに注意する。
すでに説明した圧縮部分系列先頭部決定部１４１に示した処理を考慮すると、上記のようにして切り出した復元圧縮部分系列の先頭部ｚ＾ｃ１（ｌ）から、ｌ番目の分割系列集合の同時経験分布Ｑ＾ｌを復元できる。
【０１０３】
さらに、上記圧縮部分系列後続部決定部１４２に示した処理を考慮すると、圧縮系列分割部２１は、復元された同時経験分布である復元同時経験分布Ｑ＾ｌからｌ番目の圧縮部分系列の後続部の系列長ｃ＾２（ｌ）を同定できる．
上記の説明により、圧縮系列分割部２１は、圧縮系列ｚｃ＊のσｌ＋ｃｌ＋１番目の文字を先頭とするｃ＾２（ｌ）を切り出すことで、ｌ番目の復元圧縮部分系列の後続部ｚ＾ｃ＾２（ｌ）（ｌ；２）を生成する。
そして、圧縮系列分割部２１は、先頭部ｚ＾ｃ１（ｌ；１）と後続部ｚ＾ｃ＾２（ｌ）（ｌ；２）を連結することにより、ｌ番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ）（ｌ）を生成する。ここで、ｃ＾（ｌ）＝ｃ１＋ｃ＾２（ｌ）である。
【０１０４】
ここで、圧縮系列分割部２１は、上記の操作をｌ＝１，…，Ｌについて繰り返し実行することにより、Ｌ番目までの復元圧縮部分系列ｚ＾ｃ＾（ｌ）（ｌ）（ｌ＝１，…，Ｌ）を復元する。
また、圧縮系列分割部２１は、設定されている系列長以下であるために圧縮系列から切り出されなかった残りのｃ＊−σＬ文字を、Ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（Ｌ＋１）（Ｌ＋１）とする。ここで、ｃ＾（Ｌ＋１）＝ｃ＊−σＬである。
【０１０５】
次に、圧縮系列グラフ同定部２２は、上記復元圧縮部分系列の集合を入力し、その復元圧縮部分系列の各々について、その圧縮部分系列を生成した圧縮系列グラフを、補助系列集合記憶部に記憶されている圧縮系列グラフから同定し、上記復元圧縮部分系列の各々に対して同定された圧縮系列グラフである復元圧縮系列グラフの集合を出力する（ステップＳ２３）。
本実施形態において、圧縮系列グラフ同定部２２は、復元圧縮系列グラフを、以下のようにして同定する。
【０１０６】
まず、圧縮系列グラフ同定部２２は、ｌ番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ）（ｌ）の先頭ｃ１文字である先頭部ｚ＾ｃ１（ｌ）を切り出す。
そして、圧縮系列グラフ同定部２２は、この先頭部ｚ＾ｃ１（ｌ）からｌ番目の分割系列集合の復元同時経験分布Ｑ＾ｌを同定し、この復元同時経験分布Ｑ＾ｌに対応する経験分布別圧縮系列グラフを同定する。
圧縮系列グラフ同定部２２は、上記同定した経験分布別圧縮系列グラフを、ｌ番目の復元圧縮系列グラフとして出力する。
【０１０７】
また、圧縮系列グラフ同定部２２は、上記の操作を、ｌ＝１，２，…，Ｌについて繰り返して行い、Ｌ個のグラフからなる集合を出力する。この処理において、圧縮系列グラフ同定部２２は、Ｌ＋１番目の分割系列集合については、上記の操作を実行しない。
【０１０８】
次に、分割系列集合復元部２３は、上記復元圧縮部分系列の集合、上記復元圧縮系列グラフの集合、及び補助系列集合記憶部から補助系列集合を入力する。
そして、分割系列集合復元部２３は、復元圧縮部分系列の各々、及び各復元圧縮系列に対応して補助系列集合から得られる分割補助系列集合について、その復元圧縮部分系列に対応して得られた復元圧縮系列グラフから、伝送系列集合に対応する分割系列集合である分割伝送系列集合を復元して、この復元された分割系列集合である復元分割伝送系列集合の集合を出力する（ステップＳ２４）。
【０１０９】
本実施形態において、分割系列集合復元部２３は、復元分割伝送系列集合を、以下の処理により求める。
まず、分割系列集合復元部２３は、系列分割部１２と同様の処理により、補助系列ｘ（ｋ）ｎ（ｋ＝１，２，３）を分割補助系列ｘ（ｋ）ｍ（ｌ）（ｌ＝１，２，…Ｌ）に分割する。
次に、分割系列集合復元部２３は、ｌ番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ）（ｌ）の後続ｃ＾２（ｌ）文字であるｚ＾ｃ＾２（ｌ）（ｌ）を切り出す。
そして、分割系列集合復元部２３は、ｌ番目の復元圧縮系列グラフから、ｌ番目の分割補助系列ｘ（ｋ）ｍ（ｌ）に対応する完全部分グラフを検出する。
その完全部分グラフから、分割系列集合復元部２３は、復元圧縮部分系列の後続部ｚ＾ｃ＾２（ｌ）（ｌ）が存在する頂点を検出する。
次に、分割系列集合復元部２３は、検出された頂点に対応する分割入力系列集合Ｘ＾ｍ（ｌ）から分割伝送系列集合を抽出し、以下の（３２）式、（３３）式及び（３４）式に示されるｌ番目の復元分割伝送系列集合として出力する。
【０１１０】
【数３２】
2008311746.tif 000034
【０１１１】
【数３３】
2008311746.tif 000035
【０１１２】
【数３４】
2008311746.tif 000036
【０１１３】
そして、分割系列集合復元部２３は、上記の操作をｌ＝１，…，Ｌについて繰り返し実行することにより、Ｌ番目までの復元分割伝送系列集合Ｘ＾（Ｓｋ）ｍ（ｌ）（ｌ＝１，…，Ｌ）が復元される。
また、分割系列集合復元部２３は、Ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（Ｌ＋１）（Ｌ＋１）に対しては、その部分系列を３等分し、その第ｊ番目の部分ｚ＾ｊｃ＾（Ｌ＋１）／Ｎｓ（Ｌ＋１）を切り出し、その集合をＬ＋１番目の復元分割伝送系列集合Ｘ＾（Ｓｋ）ｍ’（Ｌ＋１）として出力する。
【０１１４】
次に、復元系列集合生成部２４は、分割系列集合復元部２３から上記復元分割伝送系列集合の集合を入力し、それら復元分割伝送系列集合を統合することにより、伝送系列集合を復元し、復元した系列集合である復元伝送系列集合を出力する（ステップＳ２５）。
本実施形態において、復元系列集合生成部２４は、復元伝送系列集合Ｘ＾（Ｓｋ）ｎ（ｋ＝１，２，３）を、以下の（３５）式から（３７）式に示すように、復元分割伝送系列集合の要素を連結することで求める。
【０１１５】
【数３５】
2008311746.tif 000037
【０１１６】
【数３６】
2008311746.tif 000038
【０１１７】
【数３７】
2008311746.tif 000039
【０１１８】
上述したように、系列復元部２は、各部の処理により、信号系列圧縮部１が圧縮した入力系列からなる上記復元伝送系列集合Ｘ＾（Ｓｋ）ｎを復元して出力する。
また、上記第１の実施形態例においては、どのような入力系列集合が入力として与えられたとしても、必ず同一の系列集合を復元することができる。
すなわち、信号系列圧縮部１が圧縮する入力系列からなる伝送系列集合と、系列復元部２が復元する復元伝送系列集合とは同一となる。このとき、ｃ＾（Ｌ＋１）＝ｃ＊−σＬは、３mod（ｎ，ｍ）と一致する。
以上が、図１に示す信号伝送モデルについての第１の実施形態の具体的な説明である。同様の方法を、３つ以上の複数の入力系列数に対応する一般の場合についても適用させることができる。以下、一般の場合についての第１の実施形態を示す。
【０１１９】
次に、上述した説明を一般化した場合においても、図２のシステム構成、図３の信号系列圧縮部１の構成、図７の系列復元部２（または３，４）については、Ｎｓ＝３として説明した際の構成と同様である。以下、信号系列圧縮部１における信号系列の圧縮処理と、系列復元部２の系列復元処理とを順番に説明する。
上記信号系列圧縮部１は、すでに述べたように、図４のフローチャートの処理の流れにより、入力信号系列集合を入力し、入力信号系列集合を圧縮した圧縮系列を抽出して、その圧縮系列を出力する。
信号系列圧縮部１は、圧縮系列の抽出方法を特に限定するものではないが、圧縮系列グラフ作成部１１と、系列分割部１２と、系列集合経験分布導出部１３と、圧縮部分系列決定部１４と、圧縮系列生成部１５とによって構成されている。
【０１２０】
上記圧縮系列グラフ作成部１１は、ある一定の長さを持つ任意の系列の集合について、その系列集合の経験的な確率分布である同時経験分布を用いてその系列集合に対応する圧縮系列を定め、系列集合と圧縮系列との対応関係を示すグラフである圧縮系列グラフを作成し、その圧縮系列グラフを出力する（ステップＳ１〜Ｓ６）。
ここで、圧縮系列グラフの作成方法は特に限定されるものではないが、本実施形態においては、系列集合分類部１１１と、経験分布別圧縮系列グラフ作成部１１３とによって構成される圧縮系列グラフ作成部１１による圧縮系列グラフの作成方法について述べる。
【０１２１】
系列集合分類部１１１は、予め設定されたある一定の長さを持つ任意の系列の集合を上記同時経験分布により分類し、その分類の集合を出力する（ステップＳ１及びＳ２）。
本実施形態において、系列集合分類部１１１は、以下のようにして、系列集合を分類する。
まず、系列集合分類部１１１は、分類決定に用いる系列の長さである系列長ｍを決定する。この系列長は、外部から与えてもよいし、予め内部に設定しておいても良い。また、この系列長ｍは、各入力系列の系列長ｎと同一である必要はないが、ｍ≦ｎを満たす必要がある。
【０１２２】
次に、系列集合分類部１１１は、系列長がｍである系列の集合Ｘ〜ｍ＝｛ｘ〜（ｊ）ｍ｝Ｊ＝１Ｎｓを基に、任意の系列集合についてその経験的な確率分布である下記の（３８）式に示す同時経験分布を、以下の（３９）式を用いて求める。
【０１２３】
【数３８】
2008311746.tif 000040
【０１２４】
【数３９】
2008311746.tif 000041
【０１２５】
そして、系列集合分類部１１１は、同一の同時経験分布Ｑを持つ系列長ｍの系列集合の集合ＴＱｍを作成し、この集合(経験分布共有系列集合族)を求める分類として、以下の（４０）式として出力する（ステップＳ３）。
【０１２６】
【数４０】
2008311746.tif 000042
【０１２７】
次に、経験分布別圧縮系列グラフ作成部１１３は、上記系列集合分類部１１１から出力された分類（経験分布共有系列集合族)の集合を入力し、各経験分布共有系列集合族に含まれる系列集合各々に圧縮系列を対応させ（ステップＳ４）、系列集合と圧縮系列との対応関係を示す圧縮系列グラフである経験分布別圧縮系列グラフを作成し、この経験分布別圧縮系列グラフの集合を出力する（ステップＳ５及びＳ６）。
【０１２８】
本実施形態において、経験分布別圧縮系列グラフ作成部１１３は、経験分布別圧縮系列グラフを、以下のようにして作成する。
まず、経験分布別圧縮系列グラフ作成部１１３は、同時経験分布Ｑ各々について、その同時経験分布に対応する経験分布共有系列集合族ＴＱｍに含まれる系列集合を抽出し、これら系列集合各々に頂点を割り当てる（図５参照）。
次に、経験分布別圧縮系列グラフ作成部１１３は、系列長ｍの補助系列集合Ｘ〜（〜Ｓｋ）ｍ各々について、この系列集合を構成要素として持つＴＱｍ内の系列集合を取り出し、それら系列集合に対応する頂点の間に辺を配置する。
【０１２９】
そして、経験分布別圧縮系列グラフ作成部１１３は、上述したように作成されたグラフの各頂点に対して、後に圧縮系列に対応することとなる番号を割り当てる（図６）。
このとき、経験分布別圧縮系列グラフ作成部１１３は、辺で連結されている頂点同士において、全て相互に異なる番号が割り当てられるように、番号を割り当てて付与する。
この番号の割り当て方法については、すでに述べたグラフ頂点彩色アルゴリズムを用いる。
経験分布別圧縮系列グラフ作成部１１３は、上記のようにして作成されたグラフを、同時経験分布Ｑについての経験分布別圧縮系列グラフとして出力するとともに内部記憶部に記憶する。
【０１３０】
また、経験分布別圧縮系列グラフ作成部１１３において求められた経験分布別圧縮系列グラフは、以下に述べる性質を有している。
ただし、ＴＱ；ｋｍ（Ｘ〜（ＩＮｓ−Ｓｋ）ｍ）は、長さｍの下記の（４１）式に示す系列長ｍの補助系列集合が与えられる際、
【０１３１】
【数４１】
2008311746.tif 000043
【０１３２】
伝送系列集合に対応する経験分布共有系列集合族の下記（４２）式に示す構成要素
【０１３３】
【数４２】
2008311746.tif 000044
【０１３４】
の下記（４３）式に示す集合である。
【０１３５】
【数４３】
2008311746.tif 000045
【０１３６】
上記経験分布別圧縮系列グラフの性質は、
１．各頂点はＮｄ個の完全部分グラフに含まれており、それら完全部分グラフに含まれない頂点との間には辺は存在しない。ただし、完全グラフとは、任意の頂点の間に辺が存在するグラフである。
２．各完全部分グラフは、系列長ｍの補助系列集合Ｘ〜（〜Ｓｋ）ｍが与えられたときの、経験  分布共有伝送系列集ＴＱ；ｋｍ（Ｘ〜（〜Ｓｋ）ｍ）に対応している。完全部分グラフの次数は、ｋ(直接的には集合Ｓｋ)及び同時経験分布Ｑのみに依存しており、系列長ｍの補助系列集合Ｘ〜（〜Ｓｋ）ｍ）には依存しない。以下、この次数をｍｋ（Ｑ）によって表現する。
３．経験分布別圧縮系列グラフの次数はＱのみに依存しており、以下の（４４）式で与えられる。
【０１３７】
【数４４】
2008311746.tif 000046
【０１３８】
そして、経験分布別圧縮系列グラフ作成部１１３は、経験分布別圧縮系列グラフの各頂点に割り当てられた番号を、ｃ２＝ｃ２（Ｑ）桁の｜Ｚ｜進表現をすることにより、各頂点に対応する系列集合Ｘ〜ｍに割り当てられる圧縮系列ｚ〜ｃ２（Ｘ〜ｍ）を求める。
ここで、Ｚは圧縮系列を構成する文字の集合であり、ｃ２（Ｑ）は以下の（４５）式により与えられる。
【０１３９】
【数４５】
2008311746.tif 000047
【０１４０】
上述した処理により、圧縮系列グラフ作成部１１は、上記経験分布別圧縮系列グラフの集合を圧縮系列グラフとして出力する。
【０１４１】
次に、系列分割部１２は、入力系列集合を入力し、入力系列各々を上記圧縮系列グラフ作成部１１にて定められた系列長の系列に分割して、分割入力系列を抽出し、これら分割入力系列の集合である分割入力系列集合について、その集合である分割入力系列集合族を出力する（ステップＳ７）。
本実施形態において、系列分割部１２は、各入力系列ｘ（ｊ）ｎ∈｛χ（ｊ）｝ｎを、上記系列集合分類部１１１にて定めた系列長ｍを用いて、以下の（４６）式に示すようにように分割する。
【０１４２】
【数４６】
2008311746.tif 000048
【０１４３】
上記（４９）式において、Ｌは以下の（４７）式に示すように求められる。
【０１４４】
【数４７】
2008311746.tif 000049
【０１４５】
上記（４９）式において、ｘ（ｊ）ｉｋは系列ｘ（ｊ）ｎの第ｉ成分から第ｋ成分までを切り出した部分系列、すなわちｘ（ｊ）ｉｋ＝ｘ（ｊ）ｉｘ（ｊ）ｉ＋１…ｘ（ｊ）ｋである。
また、（５０）式において、floor（ｘ）は実数ｘ以下の最大の整数である。
上記系列分割部１２における入力系列各々の分割方法は、すなわち、系列の先頭から順に系列長ｍの部分系列を切り出し、系列長ｍの部分系列が切り出せなくなったところで系列分割を終了し、残りの部分系列をそのまま出力する方法である。
上記の通り、系列分割部１２は、以下の（４８）式及び（４９）式の示す分割入力系列集合を抽出し、これら分割入力系列集合の集合である分割入力系列集合族を出力するとともに記憶部に記憶する（ステップＳ７）。ただし、（４９）式において、ｍ’＝mod（ｎ，ｍ）＝ｎ−Ｌｍである。
【０１４６】
【数４８】
2008311746.tif 000050
【０１４７】
【数４９】
2008311746.tif 000051
【０１４８】
次に、系列集合経験分布導出部１３は、上記分割入力系列集合族を入力し、その分割入力系列集合族に含まれる分割系列集合の各々から同時経験分布を導出し、その同時経験分布の集合を出力する（ステップＳ８）。
各分割系列集合Ｘｍ（ｌ）（ｌ＝１，２，…，Ｌ）についての同時経験分布ＱＸｍ（ｌ）ｍは、上記系列集合分類部１１１にて示した方法と同様に、系列集合経験分布導出部１３により求められる。
しかしながら、系列集合経験分布導出部１３は、Ｌ＋１番目の分割系列集合Ｘｍ（Ｌ＋１）については、系列長がｍに満たないため、同時経験分布を抽出しない。
【０１４９】
次に、圧縮部分系列決定部１４は、上記経験分布別圧縮系列グラフの集合、上記分割入力系列集合族及び上記同時経験分布の集合を入力し、この分割入力系列集合族に含まれる分割系列集合の各々について、対応する同時経験分布及び経験分布別圧縮系列グラフを用いて、その分割系列集合各々に対応する圧縮系列である圧縮部分系列をそれぞれ定め、その圧縮部分系列の集合を出力する（ステップＳ９）。
この圧縮部分系列決定部１４による圧縮部分系列の決定方法は、特に限定されるものではないが、本実施形態においては、圧縮部分系列先頭部決定部１４１及び圧縮部分系列後続部決定部１４２によって構成される作成方法について、以下に説明する。
【０１５０】
ここで、圧縮部分系列先頭決定部１４１は、上記分割入力系列集合族及び上記同時経験分有の集合を入力し、分割入力系列集合族に含まれる分割入力系列集合の各々について、その分割入力系列集合の同時経験分布に対応する番号もしくはその番号に対応する系列を、圧縮部分系列の先頭部分とし、その圧縮部分系列の先頭部分の集合を出力する。
本実施形態において、圧縮部分系列先頭決定部１４１は、圧縮部分系列の先頭部分を、以下のようにして決定する。
このとき、同時経験分布全体の集合Ｐｍ（χ（ＩＮｓ））の各要素に対して異なる番号が予め与えられているとする。
このとき、上記集合Ｐｍ（χ（ＩＮｓ））は、以下の（５０）式に示す範囲にある。
【０１５１】
【数５０】
2008311746.tif 000052
【０１５２】
上記集合Ｐｍ（χ（ＩＮｓ））は、（５０）式に示す数値範囲にあるので、高々（ｍ＋１）｜χ（ＩＮｓ）｜種類の番号を用意すればよい。
そして、圧縮部分系列先頭決定部１４１は、分割系列集合Ｘｍ（ｌ）（ｌ＝１，２，…，Ｌ）それぞれに対して、その同時経験分布ＱＸｍ（ｌ）ｍに対応する番号を割り当てる。
次に、圧縮部分系列先頭決定部１４１は、各分割系列集合に割り当てられた番号を、以下の（５１）式の示す桁の｜Ｚ｜進表現に変換する。
【０１５３】
【数５１】
2008311746.tif 000053
【０１５４】
また、圧縮部分系列先頭決定部１４１は、上記（５１）式から求めた桁の｜Ｚ｜進表現を、分割系列集合Ｘｍ（ｌ）に対応する圧縮部分系列の先頭部分を下記の（５２）式として設定する。
【０１５５】
【数５２】
2008311746.tif 000054
【０１５６】
次に、圧縮部分系列後続部決定部１４２は、上記経験分布別圧縮系列グラフの集合、上記分割系列集合族、及び上記同時経験分布の集合を入力し、入力された分割系列集合の各々について、その分割系列集合の同時経験分布に対応する経験分布別圧縮系列グラフから、その分割系列集合に対応する圧縮系列を導出する。
そして、圧縮部分系列後続部決定部１４２は、導出した圧縮系列を、圧縮部分系列の後続部として決定し、その圧縮部分系列の後続部の集合を出力する（ステップＳ９）。
【０１５７】
本実施形態において、圧縮部分系列後続部決定部１４２は、上述した圧縮部分系列の後続部を、以下のように決定する。
まず、圧縮部分系列後続部決定部１４２は、分割入力系列集合Ｘｍ（ｌ）（ｌ＝１，２，…，Ｌ）に対して、その同時経験分布ＱＸｍ（ｌ）ｍに対応する経験分布別圧縮系列グラフを、記憶部に記憶されている経験分布別圧縮系列グラフの中から選択して読み出す。
次に、圧縮部分系列後続部決定部１４２は、読み出された経験分布別圧縮系列グラフの中から、分割入力系列集合Ｘｍ（ｌ）に対応する頂点を検出し、その頂点に割り当てられた下記の（５３）式に示す圧縮系列を導出する。
【０１５８】
【数５３】
2008311746.tif 000055
【０１５９】
上記（５３）式において、ｃ２（ｌ）は、ｌ番目の分割入力系列集合に対応する圧縮系列の系列長である。
上記経験分布別圧縮系列グラフ作成部１１３は、ｃ２（ｌ）をｌ番目の分割入力系列集合の同時経験分布Ｑｌ＝ＱＸｍ（ｌ）ｍによって決定され、以下の（５４）式により求めて出力する。
【０１６０】
【数５４】
2008311746.tif 000056
【０１６１】
そして圧縮部分系列後続部決定部１４２は、上記の（５６）式により求めた圧縮系列ｚ〜ｃ（ｌ）（ｌ）を、分割系列集合Ｘｍ（ｌ）に対する圧縮部分系列の後続部として出力する。
圧縮部分系列決定部１４は、上述した処理により抽出された圧縮部分系列の先頭部ｚ〜ｃ１（ｌ；１）と、後続部ｚ〜ｃ２（ｌ）（ｌ；２）とを連結した系列ｚ〜ｃ（ｌ）（ｌ）を圧縮部分系列とし、この下記（５５）式に示す圧縮部分系列の集合を出力する。下記（５５）式において、「＊」は系列の連接を表す演算子であり、ｃ（ｌ）＝ｃ１＋ｃ２（ｌ）はｌ番目の分割系列集合に対応する圧縮部分系列の系列長である。
【０１６２】
【数５５】
2008311746.tif 000057
【０１６３】
次に、圧縮系列生成部１５は、上記圧縮部分系列決定部１４から出力される圧縮部分系列の集合を入力し、入力した圧縮部分系列を統合することにより、入力系列集合に対応する圧縮系列を生成し、その圧縮系列を出力する（ステップＳ１０）。
本実施形態において、圧縮系列生成部１５は、入力系列集合Ｘｎに対応する圧縮系列ｚｃ＊（Ｘｎ）を以下の（５６）式により求めて決定する。
【０１６４】
【数５６】
2008311746.tif 000058
【０１６５】
上記（５６）式において、ｃ＊は以下の（５７）式により設定される。
【０１６６】
【数５７】
2008311746.tif 000059
【０１６７】
上記（５７）式において、ｃ＊は入力系列集合Ｘｎに対応する圧縮系列の系列長となる。この圧縮系列の構成は、すなわち、各圧縮部分系列を連結した後で、最後に上記系列分割部１２で余った部分系列を圧縮せずにそのまま連結するものである。
上述したように、系列圧縮部１は、上記圧縮系列ｚｃ＊（Ｘｎ）を出力する。
【０１６８】
次に、本実施形態における系列復元部２（または３及び４）による圧縮系列の一般化した復元処理について説明する。系列復元部２は、すでに説明したように、本実施形態の構成による復元伝送系列集合の復元方法として特に限定されるものではないが、図７に示すように、圧縮系列分割部２１と、圧縮系列グラフ同定部２２と、分割系列集合復元部２３と、復元系列集合生成部２４とから構成されている。
【０１６９】
上述した図７の構成により、系列復元部２は、上記系列圧縮部１から出力された圧縮系列及び補助系列集合を入力し、これら圧縮系列と補助系列集合とから伝送系列集合を復元し、復元された伝送系列集合である復元伝送系列集合を出力する。系列復元部２は、入力される圧縮系列及び補助系列集合を一端、補助系列集合記憶部に記憶し、必要に応じて読み出し、復元の処理を行う。
以下、この系列復元部２により処理される復元伝送系列集合の一般化した復元方法について図８のフローチャートに従い説明する。
【０１７０】
圧縮系列分割部２１は、系列圧縮部１から出力された圧縮系列及び補助系列集合を入力し、圧縮系列を分割することにより圧縮部分系列を復元し、復元した圧縮部分系列である復元圧縮部分系列の集合を出力する（ステップＳ２１）。
本実施形態において、圧縮系列分割部２１は、圧縮部分系列を以下の様にして復元する。
このとき、圧縮系列分割部２１は、入力された圧縮系列ｚｃ＊から、すでに以下の（５８）式に示すようにｌ−１番目までの復元圧縮系列が復元しているとする。下記の（５８）式において、ｃ＾（ｌ）はｌ番目の復元圧縮部分系列の系列長である。
【０１７１】
【数５８】
2008311746.tif 000060
【０１７２】
まず、圧縮系列分割部２１は、圧縮系列ｚｃ＊のσｌ＋１番目の文字を先頭としてｃ１文字を切り出し、これをｌ番目の復元圧縮部分系列の先頭部ｚ＾ｃ１（ｌ；１）とする。
このσｌは以下の（５９）式により与えられる。
【０１７３】
【数５９】
2008311746.tif 000061
【０１７４】
また、切り出す文字数ｃ１は入力系列集合に依存せず、定数（＝（log｜Ｚ｜（ｍ＋１））Πｊ＝１Ｎｓ｜χ（ｊ）｜）であることに注意する。
上記圧縮部分系列先頭部決定部１４に示した処理を考慮すると、上述のように切り出した復元圧縮部分系列の先頭部ｚ＾ｃ１（ｌ）からｌ番目の分割系列集合の同時経験分布Ｑ＾ｌが復元できる。
さらに、上記圧縮部分系列後続決定部１４２に示した処理を考慮すると、復元された同時経験分布である復元同時経験分布Ｑ＾ｌからｌ番目の圧縮部分系列の後続部の系列長ｃ＾２（ｌ）を同定できる。
【０１７５】
上述した説明に基づき、圧縮系列分割部２１は、圧縮系列ｘｃ＊のσｌ＋ｃ１＋１番目の文字を先頭とするｃ＾２（ｌ）文字を切り出すことにより、ｌ番目の復元圧縮部分系列の後続部ｚ＾ｃ＾２（ｌ）（ｌ；２）を生成する。
そして、圧縮系列分割部２１は、先頭部ｚ＾ｃ１（ｌ）と後続部ｚ＾ｃ＾２（ｌ）（ｌ；２）とを連結することにより、ｌ番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ）（ｌ）を生成する。ここで、ｃ＾（ｌ）＝ｃ１＋ｃ＾２（ｌ）である。
【０１７６】
そして、圧縮系列分割部２１は、上記の処理を、ｌ＝１，２，…，Ｌについて繰り返し実行することにより、Ｌ番目までの復元圧縮部分系列ｚ＾ｃ＾（ｌ）（ｌ）（ｌ＝１，２，…，Ｌ）を復元する。
また、圧縮系列分割部２１は、圧縮系列から切り出されなかった残りのｃ＊−σｌ文字を、Ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（Ｌ＋１）（Ｌ＋１）として出力する。ここで、ｃ＾（Ｌ＋１）＝ｃ＊−σＬである。
【０１７７】
次に、圧縮系列グラフ同定部２２は、圧縮系列分割部２１から上記復元圧縮部分系列の集合を入力し、入力した復元圧縮部分系列の各々に対し、補助系列集合記憶部に記憶されている圧縮系列グラフのなかから、その圧縮部分系列を生成した圧縮系列グラフを同定して読み出し、その同定された圧縮系列グラフである復元圧縮系列グラフの集合を出力する（ステップＳ２３）。
本実施形態において、圧縮系列グラフ同定部２２は、圧縮系列グラフである各復元圧縮系列グラフを、以下のようにして同定する。
【０１７８】
まず、圧縮系列グラフ同定部２２は、ｌ番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ）（ｌ）の先頭ｃ１文字である先頭部ｚ＾ｃ１（ｌ）を切り出す。
そして、圧縮系列グラフ同定部２２は、上記先頭部ｚ＾ｃ１（ｌ）からｌ番目の分割系列集合の復元同時経験分布Ｑ＾ｌを同定し、補助系列集合記憶部に記憶されている経験分布別圧縮系列グラフのなかから、この同定された復元同時経験分布Ｑ＾ｌに対応する経験分布別圧縮系列グラフを検索して抽出する。
【０１７９】
圧縮系列グラフ同定部２２は、上記抽出された経験分布別圧縮系列グラフを、ｌ番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ）（ｌ）に対応する復元圧縮系列グラフとして出力する。
そして、圧縮系列グラフ同定部２２は、上記復元圧縮系列グラフの同定処理をｌ＝１，２，…，Ｌについて繰り返すことにより、Ｌ個からなる復元圧縮系列グラフの集合を生成して出力する。
また、圧縮系列グラフ同定部２２は、Ｌ＋１番目の分割系列集合に対しては、復元圧縮系列グラフの同定処理を行わない。
【０１８０】
次に、分割系列集合復元部２３は、上記復元圧縮部分系列の集合、上記復元圧縮系列グラフの集合、及び補助系列集合を入力する。
そして、分割系列集合復元部２３は、上記復元圧縮部分系列の各々、及び各復元圧縮系列に対応して補助系列集合から得られる分割補助系列集合に対し、その復元圧縮部分系列に対応して得られた復元圧縮系列グラフから、伝送系列集合に対応する分割系列集合である分割伝送系列集合を復元し、この復元された分割系列集合である復元分割伝送系列集合の集合を出力する（ステップＳ２４）。
【０１８１】
ここで、分割系列集合復元部２３は、本実施形態において、復元分割伝送系列集合を、以下のようにして求める。
まず、系列分割部１２と同様の処理により、補助系列集合Ｘ（〜Ｓｋ）を、以下の（６０）式に示す分割補助系列集合に分割する。
【０１８２】
【数６０】
2008311746.tif 000062
【０１８３】
次に、分割系列集合復元部２３は、ｌ番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ）（ｌ）の後続のｃ＾２（ｌ）文字であるｚ＾ｃ＾２（ｌ）（ｌ）を切り出す。
そして、分割系列集合復元部２３は、ｌ番目の復元圧縮系列グラフからｌ番目の分割補助系列集合Ｘ（−Ｓｋ）ｍ（ｌ）に対応する完全部分グラフを抽出する。
そして、分割系列集合復元部２３は、抽出した完全部分グラフから、復元圧縮部分系列の後続部ｚ＾ｃ＾２（ｌ）（ｌ）が存在する頂点の検出を行う。
対象とする頂点が検出されると、分割系列集合復元部２３は、この頂点に対応する分割入力系列集合Ｘ＾ｍ（ｌ）から、以下の（６１）式に示す分割伝送系列集合を抽出し、ｌ番目の復元分割伝送系列集合とする。
【０１８４】
【数６１】
2008311746.tif 000063
【０１８５】
そして、分割系列集合復元部２３は、上述した分割伝送系列集合を抽出処理を、ｌ＝１，２，…，Ｌの復元圧縮部分系列に対して繰り返して行い、１番目からＬ番目までのＬ個の復元分割伝送系列集合Ｘ＾（Ｓｋ）ｍ（ｌ）（ｌ＝１，２，…，Ｌ）を復元する。
このとき、分割系列集合復元部２３は、Ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（Ｌ＋１）（Ｌ＋１）に対して、その部分系列をＮｓ等分に分割し、そのｊ番目の部分ｚ＾ｊｃ＾（Ｌ＋１）／Ｎｓ（Ｌ＋１）を切り出して、その集合をＬ＋１番目の復元分割伝送系列集合Ｘ＾（Ｓｋ）ｍ’（Ｌ＋１）として出力する。
【０１８６】
次に、復元系列集合生成部２４は、上記復元分割伝送系列集合の集合を入力し、入力された各復元分割伝送系列集合を連結して統合することにより、伝送系列集合を復元し、復元した系列集合である復元伝送系列集合を出力する（ステップＳ２５）。
ここで、復元系列集合生成部２４は、本実施形態において、復元伝送系列集合Ｘ＾（ｓｋ）ｎを、復元分割伝送系列集合の要素を連結して、以下の（６２）式に示す入力系列として復元する。
【０１８７】
【数６２】
2008311746.tif 000064
【０１８８】
上述したように、系列復元部２は、系列圧縮部１が複数（特に３つ以上）の入力系列を圧縮した圧縮系列を、復元伝送系列集合Ｘ＾（ｓｋ）ｎとして復元する。
【０１８９】
また、上述した第１の実施形態においては、どのような入力系列集合が入力として与えられても、必ず同一の系列集合を復元することができる。すなわち、伝送系列集合と復元伝送系列集合とは同一となる。
このとき、ｃ＾（Ｌ＋１）＝ｃ＊−σＬはＮｓmod（ｎ、ｍ）と一致する。
しかしながら、後述する第２の実施形態においては、必ずしも同一の系列を復元できるとは限らないが、ｃ＾（Ｌ＋１）とＮｓmod（ｎ，ｍ）とは一致するように構成されるが、詳細は後述する。
【０１９０】
＜第２の実施形態＞
本第２実施形態における信号系列の伝送を行う伝送システムとしては、第１の実施形態と同様に図２の概念図に示すように、信号系列を圧縮する信号系列圧縮部１が信号系列を送信する送信側端末１００に設けられ、圧縮された信号系列（圧縮信号系列）を復元する系列復元部２（あるいは３、４）が受信側端末２０１（あるいは２０２，２０３）に設けられている。
【０１９１】
図９を用い、第２の実施形態の説明を行う。図９は、第２の実施形態による系列圧縮部１の構成例を示すブロック図である。第２の実施形態が第１の実施形態と異なる点は、圧縮系列グラフ作成部１１に系列集合分類選択部１１２が設けられていることである。
すなわち、本第２の実施形態による圧縮系列グラフ作成部１１は、系列集合分類部１１１と、系列集合分類選択部１１２と、経験分布別圧縮系列グラフ作成部１１３とから構成されている。
第２の実施形態において第１の実施形態と同様の構成については同一の符号を付して説明を省略する。以下、第２の実施形態が第１の実施形態と異なる部分及び動作のみを説明する。
【０１９２】
上記系列集合分類選択部１１２は、上記系列集合分類部１１１にて求められた分類の集合を入力し、入力した分類の集合のなかから、分類に所属する系列集合に対応する圧縮系列の系列長が予め設定された閾値である圧縮系列長閾値以下の（下回る）分類のみを選択し、選択した分類の集合を出力する。
ここで、系列集合分類選択部１１２は、第２の実施形態において上述した分類の選択処理を以下のように行う。
【０１９３】
すでに説明した圧縮部分系列決定部１４に示した処理を考慮すると、ある同時経験分布に対応する分類（すなわち、その同時経験分布を有する系列集合の集合）ＴＱｍに含まれる分割系列集合から得られる圧縮部分系列の系列長は同時経験分布Ｑのみに依存し、ｃ１＋ｃ２（Ｑ）で表されることがわかる。
したがって、本第２の実施形態においては、上記圧縮系列長閾値ｒを導入して予め設定し、以下の（６３）式を満たす同時経験分布Ｑ、及びその同時経験分布Ｑに対応する分類ＴＱｍを選択し、選択された分類の集合を出力する。
【０１９４】
【数６３】
2008311746.tif 000065
【０１９５】
次に、経験分布別圧縮系列グラフ作成部１１３は、上記系列集合分類選択部１１２から出力された分類ＴＱｍの集合を入力し、各分類に含まれる系列集合各々に対応する圧縮系列を定めて設定し、系列集合と圧縮系列との対応関係を示す圧縮系列グラフである経験分布別圧縮系列グラフを作成し、この経験分布別圧縮グラフの集合を出力する。
ここで、経験分布別圧縮系列グラフ作成部１１３は、上記圧縮系列グラフ作成の処理において、上記系列集合分類選択部１１２にて選択された分類に対しては、第１の実施形態と同様であるが、系列集合分類選択部１１２にて選択されなかった分類に対しては、経験分布別圧縮系列グラフの作成を行わない。
このため、第２の実施形態は、第１の実施形態と異なり、上記系列集合分類選択部１１２にて選択されなかった分類に含まれる系列集合に対しては、特定の圧縮系列が割り当たらないこととなる。
【０１９６】
次に、圧縮部分系列後続部決定部１４２は、上記圧縮系列グラフ作成部１１から出力される経験分布別圧縮系列グラフの集合と、上記系列分割部１２から出力された分割系列集合の集合と、及び上記系列経験分布導出部１３から出力された同時経験分布の集合と、を入力し、入力された分割系列集合の各々に対し、その分割系列集合の同時経験分布を導出する。
そして、圧縮部分系列後続部決定部１４２は、導出した同時経験分布に対応する経験分布別圧縮系列グラフを補助系列集合記憶部から抽出する。
これにより、圧縮部分系列後続部決定部１４２は、抽出した経験分布別圧縮系列グラフにおいて、その分割系列集合に対応する圧縮系列を導出し、これを圧縮部分系列の後続部として決定し、その圧縮部分系列の後続部の集合を出力する。
【０１９７】
ここで、圧縮部分系列後続部決定部１４２は、上記経験分布別圧縮系列グラフ作成部１１３で経験分布別圧縮系列グラフが作成されている同時経験分布を有する分割系列集合については、上述した第１の実施形態と同様処理を行う。
一方、圧縮部分系列後続部決定部１４２は、上記経験分布別圧縮系列グラフ作成部１１３で経験分布別圧縮系列グラフが作成されていい同時経験分布を有する分割系列に対しては、系列長ｃ２（ｊ）のランダムな系列を割り当て、これを圧縮部分系列の後続部として出力する。
【０１９８】
また、第２の実施形態における別の実施形態として、経験分布別圧縮系列グラフが作成されている同時分布を持つ分割系列集合について、圧縮系列長を全て一定にすることも可能である。
このとき、元々の圧縮系列長が圧縮系列長閾値ｒに満たないとき、圧縮系列に適切な数の文字を埋めることにより、系列長をｒに揃えることができ、処理を簡易とすることができる。
上述したことから、第２の実施形態においては、上記系列集合分類選択部１１２で選択されなかった分類に含まれる分割系列集合については、上記系列復元部２において、必ずしも伝送系列集合を完全に復元できるとは限らないが、第１の実施形態に比較して処理が容易となる。
【０１９９】
なお、図１における系列圧縮部１，系列復元部２，系列復元部３，系列復元部３それぞれの機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、それぞれのシステムにおいて圧縮または復元を行うプロセスとして実行することにより各機能の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【０２００】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【０２０１】
【図１】本発明の第１及び第２の実施形態による信号圧縮装置及び信号復元装置を用いた信号伝送システムの概念図である。
【図２】本発明の第１及びの実施形態による信号伝送システムの構成例を示すブロック図である。
【図３】本発明の第１の実施形態による系列圧縮部１の構成例を示すブロック図である。
【図４】図３における構成の信号圧縮装置における複数の入力系列の圧縮処理の動作例を説明するフローチャートである。
【図５】図３における経験分布別圧縮系列グラフ作成部１１３における経験分布別圧縮系列グラフの生成方法を説明する概念図である。
【図６】図３における経験分布別圧縮系列グラフ作成部１１３における経験分布別圧縮系列グラフの生成方法を説明する概念図である。
【図７】図３における系列復元部２（または３，４）の構成例を示すブロック図である。
【図８】図３における圧縮系列表作成部１１の圧縮系列を復元する処理の動作例を示すフローチャートである。
【図９】本発明の第２の実施形態による系列圧縮部１の構成例を示すブロック図である。
【図１０】従来の２つの入力系列を圧縮して送受信する信号圧縮装置及び信号復元装置を用いた信号伝送システムの概念図である。
【符号の説明】
【０２０２】
１…信号系列圧縮部
２，３，４…系列復元部
１１…圧縮系列グラフ作成部
１２…系列分割部
１３…系列集合経験分布導出部
１４…圧縮部分系列決定部
１５…圧縮系列生成部
２１…圧縮系列分割部
２２…圧縮系列グラフ同定部
２３…分割系列集合復元部
２４…復元系列集合生成部
１００…送信側端末
１１１…系列集合分類部
１１２…系列集合分類選択部
１１３…経験分布別圧縮系列グラフ作成部
１４１…圧縮部分系列先頭部決定部
１４２…圧縮部分系列後続部決定部
２０１，２０２…受信側端末
【図１】
2008311746.tif 000066
【図２】
2008311746.tif 000067
【図３】
2008311746.tif 000068
【図４】
2008311746.tif 000069
【図５】
2008311746.tif 000070
【図６】
2008311746.tif 000071
【図７】
2008311746.tif 000072
【図８】
2008311746.tif 000073
【図９】
2008311746.tif 000074
【図１０】
2008311746.tif 000075