(57)【特許請求の範囲】
【請求項１】
相関する複数のデータの相対的な重要度を判断する重要度判断手段と、
前記重要度判断手段の判断に基づき前記複数のデータのうち重要度の高いものほど強度の強い誤り訂正を行えるように階層的疎グラフ符号を用いて前記複数のデータを符号化する符号化手段と、
前記符号化後の複数のデータを複数の格納先に、同じ重要度のデータをそれぞれ分散して格納するように、前記重要度の高い前記データほど優先して当該複数の格納先にそれぞれ送信する送信手段と、
前記格納先に格納されている前記相関する複数のデータの送信要求を受けたときに、前記重要度の高い前記データほど優先して前記格納先から収集する収集手段と、
を備えていることを特徴とするデータ処理装置。
【請求項２】
前記重要度判断手段は、前記複数のデータを、テキストデータ、静止画像データ、動画像データの順に重要と判断することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記重要度判断手段は、前記複数のデータを、参照回数が多いほど重要と判断することを特徴とする請求項１に記載のデータ処理装置。
【請求項４】
前記重要度判断手段は、前記複数のデータを、データ間のリンク回数が多いほど重要と判断することを特徴とする請求項１に記載のデータ処理装置。
【請求項５】
請求項１〜４の何れかの一項に記載のデータ処理装置と、
前記データ処理装置と通信可能で、前記送信手段から送信された前記符号化後のデータをそれぞれ受信して記憶する複数台の記憶装置と、
を備えているデータ処理システム。
【請求項６】
データの誤り訂正を行うデータ処理装置が、
相関する複数のデータの相対的な重要度を判断する第１のステップと、
前記第１のステップの後、当該第１のステップの判断に基づき前記複数のデータのうち重要度の高いものほど強度の強い誤り訂正を行えるように階層的疎グラフ符号を用いて前記複数のデータを符号化する第２のステップと、
前記第２のステップの後、前記符号化後の複数のデータを複数の格納先に、同じ重要度のデータをそれぞれ分散して格納するように、前記重要度の高い前記データほど優先して当該複数の格納先にそれぞれ送信する第３のステップと、
前記第３のステップの後、前記格納先に格納されている前記相関する複数のデータの送信要求を受けたときに、前記重要度の高い前記データほど優先して前記格納先から収集する第４のステップと、
を実行することを特徴とするデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理システム及びデータ処理方法に関する。
【背景技術】
【０００２】
ＲＡＩＤ（Redundant Arrays of Inexpensive Disks）は、複数台のハードディスクを組み合わせることで仮想的な１台のハードディスク装置として運用し、データに冗長性を持たせることでエラー回復を可能としたロバスト保存技術として幅広く利用されている（非特許文献１参照）。具体的には、ミラーリングやシンプルな誤り訂正符号により冗長性を持たせ、誤り耐性を向上させているが、冗長度の割合に対してエラー回復の度合いは低い。
【０００３】
また、エラー回復特性が高い誤り訂正符号としては、リードソロモン（ＲＳ:Reed-Solomon）符号などのＭＤＳ（Maximum Distance Separable）符号が知られている（非特許文献２参照）。ＲＳ符号は、ディジタル放送などで広く用いられているが、日本のディジタル放送においては符号長２０４バイトと定義されており、元データ１８８バイトに対しておよそ１０％のパリティバイトを付加することで、誤りに対して耐性を持たせている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Patterson, David; Garth A. Gibson, Randy Katz (1988). "A Case for Redundant Arrays of Inexpensive Disks (RAID)". SIGMOD Conference. pp. pp  109-116
【非特許文献２】笠原正雄、"リードソロモンの半世紀",IEICE Fundamentals Review Vol.5, No.1
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、一般に誤り訂正符号として符号長の長い符号を利用すれば性能がよくなることが知られているが、符号長が長くなると復号が複雑になり計算量が膨大になる弊害も知られている。そのため、ＲＳ符号では、大抵、最大符号長を２５５バイトとして扱うことが前提とされている。そして、ストレージに格納するデータに対し、このようなＲＳ符号を適用した場合、通信コスト（エラー回復に必要な通信量）が高くなり、かつ、多地点へのデータの分散数を増やした場合には、ロバスト性能を向上しようとすると演算量が大幅に増加してしまうことになる。
【０００６】
一方、現在、利用が拡大しているクラウドサービスにおいては、高価で信頼性の高いストレージを使ってシステム全体の信頼性を高めるよりも、個々のストレージの信頼性は多少低くても、それらの故障を前提としてシステム全体として信頼性を高める工夫がなされている。この際には、データの修復／更新の頻度に伴う通信コストはできるだけ抑制することが好ましい。
特に、震災、事故など外的要因等により「ストレージの破損」や「ネットワークノードの故障」の頻度が高い状況下においては、データの修復／更新の頻度も高くなると予想される。このような状況では、可能な限り、通信コストや演算量を抑制して誤り耐性を向上させる必要がある。
【０００７】
ところで、保存および伝送の対象となるデータには、重要度に違いがあることが多い。特に、震災、事故など外的要因等により「ストレージの破損」や「ネットワークノードの故障」の頻度が高い状況下においては、重要なデータを優先的に保護して伝送できるようにすることが望ましい。
そこで、本発明は、通信回線容量および演算コストをできるだけ抑制しつつ、重要なデータは高いロバスト性能で分散して送信し、保存することができるデータ処理装置、データ処理システム及びデータ処理方法を提供することを課題とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するため、本発明の一形態は、相関する複数のデータの相対的な重要度を判断する重要度判断手段と、前記重要度判断手段の判断に基づき前記複数のデータのうち重要度の高いものほど強度の強い誤り訂正を行えるように階層的疎グラフ符号を用いて前記複数のデータを符号化する符号化手段と、前記符号化後の複数のデータを複数の格納先に、同じ重要度のデータをそれぞれ分散して格納するように、前記重要度の高い前記データほど優先して当該複数の格納先にそれぞれ送信する送信手段と、前記格納先に格納されている前記相関する複数のデータの送信要求を受けたときに、前記重要度の高い前記データほど優先して前記格納先から収集する収集手段と、を備えていることを特徴とするデータ処理装置である。
本発明によれば、重要度の高いデータは高いロバスト性能で分散して送信し、保存する一方、重要度の低いデータは通信回線容量および演算コストを抑制して分散して送信し、保存することができる。また、通信回線容量が限定された状況でも、冗長度が低い条件（復号するために必要な情報量が少ない条件）で、データを保護する強度を高めることができる。さらに、重要度の高いデータを優先的に分散して送信し、保存することや、優先的に収集することができる。
【００１１】
前記の場合に、前記重要度判断手段は、前記複数のデータを、テキストデータ、静止画像データ、動画像データの順に重要と判断するようにしてもよい。
また、前記重要度判断手段は、前記複数のデータを、参照回数が多いほど重要と判断するようにしてもよい。
さらに、前記重要度判断手段は、前記複数のデータを、データ間のリンク回数が多いほど重要と判断するようにしてもよい。
【００１２】
本発明の別の一形態は、前記の何れかのデータ処理装置と、前記データ処理装置と通信可能で、前記送信手段から送信された前記符号化後のデータをそれぞれ受信して記憶する複数台の記憶装置と、を備えているデータ処理システムである。
本発明によれば、重要度の高いデータは高いロバスト性能で分散して送信し、保存する一方、重要度の低いデータは通信回線容量および演算コストを抑制して分散して送信し、保存することができる。
【００１３】
本発明の別の一形態は、データの誤り訂正を行うデータ処理装置が、相関する複数のデータの相対的な重要度を判断する第１のステップと、前記第１のステップの後、当該第１のステップの判断に基づき前記複数のデータのうち重要度の高いものほど強度の強い誤り訂正を行えるように階層的疎グラフ符号を用いて前記複数のデータを符号化する第２のステップと、前記第２のステップの後、前記符号化後の複数のデータを複数の格納先に、同じ重要度のデータをそれぞれ分散して格納するように、前記重要度の高い前記データほど優先して当該複数の格納先にそれぞれ送信する第３のステップと、前記第３のステップの後、前記格納先に格納されている前記相関する複数のデータの送信要求を受けたときに、前記重要度の高い前記データほど優先して前記格納先から収集する第４のステップと、を実行することを特徴とするデータ処理方法である。
本発明によれば、重要度の高いデータは高いロバスト性能で分散して送信し、保存する一方、重要度の低いデータは通信回線容量および演算コストを抑制して分散して送信し、保存することができる。また、通信回線容量が限定された状況でも、冗長度が低い条件（復号するために必要な情報量が少ない条件）で、データを保護する強度を高めることができる。さらに、重要度の高いデータを優先的に分散して送信し、保存することや、優先的に収集することができる。
【発明の効果】
【００１４】
本発明によれば、重要度の高いデータは高いロバスト性能で分散して送信し、保存する一方、重要度の低いデータは通信回線容量および演算コストを抑制して分散して送信し、保存することができるデータ処理装置、データ処理システム及びデータ処理方法を提供することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施の形態に係るデータ処理システムのシステム構成例を示す説明図である。
【図２】本発明の一実施の形態に係るデータ処理システムで管理プログラムに基づいてｗｅｂサーバが実行する処理を示す機能ブロック図である。
【図３】本発明の一実施の形態に係るデータ処理システムにおける疎グラフ符号に基づく処理について説明する説明図である。
【図４】本発明の一実施の形態に係るデータ処理システムにおける階層的疎グラフ符号化手段が実行する処理を説明する説明図である。
【図５】本発明の一実施の形態に係るデータ処理システムにおける分散配置手段が実行する処理を説明する説明図である。
【図６】本発明の一実施の形態に係るデータ処理システムにおける優先順位付け収集手段が実行する処理を説明する説明図である。
【図７】本発明の一実施の形態に係るデータ処理システムにおける優先順位付け手段の機能ブロック図である。
【図８】本発明の一実施の形態に係るデータ処理システムにおける優先順位付け手段の他の例の機能ブロック図である。
【図９】本発明の一実施の形態に係るデータ処理システムにおける優先順位付け手段の他の例の機能ブロック図である。
【図１０】本発明の一実施の形態に係るデータ処理方法を説明するフローチャートである。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について図面を用いて説明する。
［システム構成の概要］
図１は、本発明の一実施形態に係るデータ処理システム１のシステム構成例を示す説明図である。このデータ処理システム１は、インターネット２に接続され、各地に分散配置されているｗｅｂサーバ３ａ〜３ｅから構成されている。ｗｅｂサーバ３ｅは、ｗｅｂサーバ３ａ〜３ｄを管理する管理サーバであり、管理プログラム４に基づいて動作し、様々な処理を実行する。
【００１７】
インターネット２には、クライアントコンピュータ５も接続されている。クライアントコンピュータ５がデータをアップロードすると、管理サーバであるｗｅｂサーバ３ｅ（データ処理装置）が、当該データを、誤り訂正符号で符号化して、当該符号化後のデータをｗｅｂサーバ３ａ〜３ｄ（記憶装置）に分散配置する。なお、データの分散配置の対象となるｗｅｂサーバは、この例では、ｗｅｂサーバ３ａ〜３ｄの４台であるが、様々な台数に設定することができる。また、クライアントコンピュータ５がデータをダウンロードしようとするときは、管理サーバであるｗｅｂサーバ３ｅは、ｗｅｂサーバ３ａ〜３ｄに分散配置されているデータを収集して、復号し、クライアントコンピュータ５に送信する。すなわち、図１のシステムでは、ｗｅｂサーバ３ａ〜３ｄは異なる場所に分散して配置される。
【００１８】
図１のシステム構成例はクラウドシステムの例であるが、データ処理システム１を、例えばＲＡＩＤを適用したハードディスクシステムとして構成してもよい。すなわち、ｗｅｂサーバ３ｅの代わりにＲＡＩＤコントローラを用い、ｗｅｂサーバ３ａ〜３ｄの代わりにそれぞれハードディスク装置を用いて、ＲＡＩＤを用いたハードディスクシステムとしてもよい。この場合は、ｗｅｂサーバ３ａ〜３ｄの代わりに設けられる各ハードディスク装置は同じ設置場所に集中して配置されていてもよい。
【００１９】
図２は、管理プログラム４に基づいて、管理サーバであるｗｅｂサーバ３ｅが実行する処理を示す機能ブロック図である。優先順位付け手段１１は、クライアントコンピュータ５がアップロードした、相関する複数のデータ間の相対的な重要度を判断して、優先順位を付ける（重要度判断手段）。階層的疎グラブ符号化手段１２は、優先順位付け手段１１で優先順位が付けられたデータを、階層的疎グラフ符号を誤り訂正符号として符号化する。この際に、複数のデータのうち重要度の高いものほど強度の強い誤り訂正が可能となるように符号化する（符号化手段）。分散配置手段１３は、疎グラブ符号化手段１２で符号化されたデータをｗｅｂサーバ３ａ〜３ｅに前記の優先順に分散して送信し、当該データをｗｅｂサーバ３ａ〜３ｅに分散して格納配置するようにする（送信手段）。
優先順位付け収集手段１４は、クライアントコンピュータ５のダウンロード要求に応じて、ｗｅｂサーバ３ａ〜３ｅに分散配置されているデータを、前記の優先順に収集する（収集手段）。階層的疎グラフ復号手段１５は、優先順位付け収集手段１４で収集したデータを復号して、クライアントコンピュータ５に送信する。
【００２０】
［ｗｅｂサーバ３ｅで実行する処理の内容］
（疎グラフ符号について）
まず、階層的疎グラブ符号化手段１２及び階層的疎グラフ復号手段１５による符号化及び復号の前提となる、疎グラフ符号に基づく符号化及びその復号について、その概要を説明する。
【００２１】
代表的な疎グラフ符号化の手段としては、ＬＤＰＣ（Low Density Parity Check）符号（参照文献：R.G.Gallager, "Low density parity check codes," in Research Monograph series.Cambridge, MIT Press, 1963）、Ｒａｐｔｏｒ符号（参照文献：Shokrollahi, A, "Raptor codes," Information Theory, IEEE Transactions on Volume 52, Issue 6, 2006）、ＬＤＧＭ（Low Density Generator Matrix）符号（参照文献：David J. C. MacKay, "Good error-correcting codes based on very sparse matrices," IEEE Trans. Inform. Theory, vol.45, no.2, pp.399-431, 1999.  "Asynchronou layered coding protocol instantiation," IETF RFC 3450, Dec. 2002.）などが知られており、これらのどの方式も本実施形態における誤り訂正符号として適用可能である。以下では、ＬＤＧＭ符号の例を中心に説明する。
【００２２】
図３は、疎グラフ符号に基づく処理について説明する説明図である。ここで、処理対象となるデータとしては、テキストデータａと、画像データｂとを例示している。これらのデータを疎グラフ符号で処理することで、当該データはソースシンボル単位に分割され、符号語が生成される。図３の例では、疎グラフ符号として組織符号を仮定しており、符号語はソースシンボルとパリティシンボルにより構成されている。
【００２３】
具体的には、この例では、テキストデータａのＡ，Ｂ，Ｃのソースシンボルに対して、パリティシンボルＰＡＢＣが生成される。また、画像データｂのＤ，Ｅ，Ｆのソースシンボルに対して、パリティシンボルＰＤＥＦが生成される。さらに、画像データｂのＧ，Ｈ，Ｉのソースシンボルに対して、パリティシンボルＰＧＨＩが生成される。生成されたソースシンボルとパリティシンボルは、図３に例示するように、ノード０、ノード１、ノード２、ノード３（例えば、前記のｗｅｂサーバ３ａ〜３ｄ）に分散配置される。
【００２４】
次に、疎グラフ符号としてＬＤＧＭ符号を利用して符号化、復号を行う例を説明する。ＬＤＧＭ符号は、ＬＤＰＣ符号の一種であり、検査行列Ｈおよび生成行列Ｇが、非常に疎な行列により構成された誤り訂正符号である。ＬＤＧＭ符号は、次式（１）〜（３）で定義される線形符号であり、検査行列Ｈ中に三角行列Ｔを含むものをいう。ただし、式（１）中、Ｈｍ×ｎは、縦ｍ行、横ｎ列（以下、（ｍ，ｎ）のように表記）の検査行列であり、（ｍ，ｋ）の疎行列Ｐｍ×ｋ、および、（ｍ，ｍ）の下三角行列Ｔｍ×ｍ(staircase)から構成され、Ｗｎはｋ個のソースシンボルＳｋ＝［ｓ１，…，ｓｋ］、および、ｍ個のパリティシンボルＣｍ＝［ｃ１，…，ｃｍ］から構成される。
【数１】
0005603972.tif 000002
【００２５】
符号化においてはＬＤＧＭ符号を定義する式（１）より、
【数２】
0005603972.tif 000003
となり、式（４）を展開することで、次式によりパリティシンボルＣｍが作成される。
【数３】
0005603972.tif 000004
また、式（５）中の下三角行列Ｔｍ×ｍの逆行列は同じく下三角行列となる。そのため、下三角行列Ｔｍが式（２）に示されるように階段状に１が配置された行列（dual diagonal 行列）の場合は、式（５）は次式（６）〜（８）として書き換えられる。但し、Ｐ（ｍ）は疎行列Ｐｍ×ｋのｍ行目の１が立っているインデックスを示している。
【００２６】
【数４】
0005603972.tif 000005
式（６）より、ＬＤＧＭ符号では、エンコード処理を疎な行列を用いて少ないＸＯＲ（eXclusive OR）演算のみで実行できることから、復号処理を極めて高速に実行できる。
【００２７】
復号処理は、ＬＤＰＣ符号と同様に、定義式となる式（１）をＢＰ（Belief Propagation）復号法で解くことにより行なうことができる。ＢＰ復号法は、タナーグラフ上でのメッセージノードとチェックノードのMessage-Passingとして捉えることができ、式（１）は、タナーグラフ（図示は省略）として示される。今、あるメッセージノードの次数をｄｍとし、その隣接するノードから来るメッセージをｌｉとすると、あるチェックノードに送られるメッセージｍは次式で与えられる。
【数５】
0005603972.tif 000006
チェックノードでは、メッセージとしてβを送ってきたメッセージノードはノードを削除し、０を送ってきたノードに対して次式で計算されるメッセージｍを返信する。ただし、ｄｃはあるチェックノードの次数である。
【数６】
0005603972.tif 000007
復号処理は、式（９）および式（１０）を繰り返し行うことで実行され、最終的に誤りが全て訂正されるか、メッセージの伝搬が行われなくなる状態となって、復号処理は終了となる。なお、最大反復回数はチェックノード数と等しくなる。
【００２８】
ＬＤＧＭ符号の復号処理は、疎行列を用いて式（９）および式（１０）を繰り返すことにより行われる。しかし、復号での繰り返し反復数はシンボルの消失数であり、データの修復に必要な最大反復回数はチェックノード数と等しくなるため、非常に高速に処理することができる。なお、ＬＤＧＭ符号をストレージへのデータ格納に応用した際のデータの修復や更新に関わるコスト評価は、「外村喜秀、仲地孝之、藤井竜也、“疎グラフ符号の超分散ストレージへの応用”、第２７回信号処理シンポジウム、A7-29、2012年11月」に記載されている。
【００２９】
（階層的疎グラフ符号に基づく符号化及び復号について）
次に、階層的疎グラブ符号化手段１２及び階層的疎グラフ復号手段１５で実行する具体的な処理について説明する。
【００３０】
階層的に符号化されたデータに対して誤り訂正符号を付す技術については公知である（特開２００９−４９８９６号公報参照）。すなわち、同文献には、乱数に基づき生成した複数の疎行列からなる階層的疎行列を生成し、対象となるデータを分割して生成した階層データと階層的疎行列との間でＸＯＲ（eXclusive OR）演算を行うことにより、パリティシンボルを求める技術が開示されている。以下では、同技術を適用し、階層的疎グラフ符号を用いる例について説明する。
ここで処理対象とするデータは互いに相関のある複数のデータである。ここで、相関のある複数のデータとしては、以下のような例が挙げられる。
まず、インターネット２上で公開されているニュース素材のテキストデータと、それに関連する画像データとには相関がある。
【００３１】
また、被災地の被災者等が、デジタルカメラやスマートフォンで撮影した静止画像データ、動画像データを、インターネットにアップロードする場合に、被災地の同じ場所に関連する静止画像データ、動画像データは互いに相関がある複数のデータとなる。デジタルカメラやスマートフォンには、ＧＰＳ（Global Positioning System）機能が搭載され、静止画像データ、動画像データに対して自動的に位置情報がメタ情報として添付される場合があり、これらのメタ情報に基づいて、これらデータに相関があると判断することができる。
さらに、同じ定点監視カメラから撮影した静止画像データ、動画像データは、相関があると判断することができる。
【００３２】
また、震災の際には、被災者リストを作成し、テキストデータとして持つ場合もあるが、掲示板などに張り出されたものを写真で撮影して画像データとして共有する場合もある。これらの被災者リストの情報は、まず、震災発生の際に最初にアクセスする重要な情報となる。ほとんどの被災者が安否情報を確認するのに、被災者リストの情報にアクセスして、その後に個々の情報にアクセスすると考えられる。この場合に、最も重要度が高い情報は、被災者リストの情報になる。こうした同じ被災地の被災者リストとなるテキストデータ、画像データも相関があると判断することができる。
【００３３】
図４は、階層的疎グラフ符号化手段１２が実行する処理を説明する説明図である。図４には、このような相関がある複数のデータとして、テキストデータａ、画像データｂの例を示している。この互いに相関しているテキストデータａと画像データｂとの間には相対的な重要度に違いがある。本例では、テキストデータの方が画像データより重要であると規定している。よって、テキストデータａの方が画像データｂより重要であると判断される。
【００３４】
階層的疎グラブ符号化手段１２においては、テキストデータａ、画像データｂは、それぞれソースシンボル単位に分割され、符号語が生成される。疎グラフ符号として組織符号を仮定しており、符号語はソースシンボルとパリティシンボルにより構成されているが、図４の例が前記した図３の例と違うのは、パリティシンボルの生成手段にある。具体的には、テキストデータａのＡ，Ｂ，Ｃのソースシンボルに対して、パリティシンボルＰＡＢＣ，ＰＤＥＦ，ＰＧＨＩが生成される。また、画像データｂのＤ，Ｅ，Ｆのソースシンボルに対して、パリティシンボルＰＤＥＦが生成される。さらに、画像データｂのＧ，Ｈ，Ｉのソースシンボルに対して、パリティシンボルＰＧＨＩが生成される。すなわち、パリティシンボルＰＤＥＦ，ＰＧＨＩは自身のソースシンボルＤ〜Ｉのみならず、テキストデータａのＡ，Ｂ，Ｃのソースシンボルに対しても、保護する構成としている。
【００３５】
これにより、テキストデータａのＡ，Ｂ，Ｃのソースシンボルについては、画像データｂのＤ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉのソースシンボルと比較して、データを保護する強度を高めることができる。すなわち、テキストデータａのＡ，Ｂ，Ｃのソースシンボルについては、一部のソースシンボルが破損した場合にも、データを復号できる可能性を高めることができる。これにより、テキストデータａ、画像データｂのうち、重要度の高いテキストデータａについては、画像データｂに比べて強度の強い誤り訂正を行なえるように符号化することができる。
【００３６】
なお、これと同じ目的のために、階層的な手段は用いず、パリティシンボルの数をＰＡＢＣ以外にも増やすことで、Ａ，Ｂ，Ｃのソースシンボルを保護する強度を高めることも可能である。しかし、この場合は、前記のように階層的疎グラフ符号を利用した場合と比較して、データの冗長度が高くなる。
このように、階層的疎グラフ符号を用いれば、通信回線容量が限定された状況でも、冗長度ができるだけ低い条件（すなわち、復号するために必要な情報量ができるだけ少ない条件）で、データを保護する強度を高めることができる。
このようにして生成されたソースシンボルＡ〜ＩとパリティシンボルＰＡＢＣ，ＰＤＥＦ，ＰＧＨＩは、図４に示すように、分散配置手段１３によりｗｅｂサーバ３ａ〜３ｄに分散配置される。
【００３７】
次に、階層的疎グラフ符号化手段１２において、ＬＤＧＭ符号を利用して処理を行う例を説明する。階層的疎グラフ符号化手段１２では、疎行列を用いて１つの階層および任意の階層に対して任意の誤り訂正符号を付加する（前記の特開２００９−４９８９６号公報参照）。今、保護したい階層データは（ｕｋ１，ｕｋ２）であり、前記のような相関があり、かつ、重要度に“ｕｋ１＞ｕｋ２”の関係があるとする。本実施形態では、このような場合に階層データの関係に基づいて誤り訂正符号を統一的に付加することができるように疎行列を生成する。すなわち、上記の例であれば、生成疎行列Ｇを、
【数７】
0005603972.tif 000008
として生成する。これにより、階層的疎グラフ符号化手段１２では、次式の演算でパリティシンボル（ｃｍ１，ｃｍ２）が生成できる。
【数８】
0005603972.tif 000009
なお、ｃｍ１は階層データｕｋ１に対するパリティシンボルであり、ｃｍ２は階層データｕｋ１および階層データｕｋ２に対するパリティシンボルである。また、式（１２）はＧが疎行列であることと、ＸＯＲ（eXclusive OR）演算であることから、高速かつ少ない演算量でパリティシンボルを作成することができる。
【００３８】
このようにして符号化したデータは疎グラフ復号手段１５により復号される。この復号の手順は、一般的なＬＤＰＣの消失訂正符号の復号と同じ動作で実行でき、行ごとに１次連立方程式を解いていく動作を繰り返し行うことで実行することができる。ただし、例えば、ネットワークの回線容量が限定された状況で、階層データｕｋ１のみを復号したい場合は、次式を１次連立方程式として解いて復号を実施する等の例も考えられる。
【数９】
0005603972.tif 000010
なお、この機能により、階層符号化データの選択的誤り訂正復号が可能となり、部分的な復号機能を保持しつつ、誤り訂正符号を付加することが可能となる。
【００３９】
また、ここでは階層が２階層の場合を例に説明を行ったが、階層が３階層以上の場合についても容易に拡張することができる。例えば、階層データが（ｕｋ１、ｕｋ２、ｕｋ３）であり、それぞれ、階層データｕｋ１と、階層データｕｋ２および階層データｕｋ３との関係が強く、階層データｕｋ２と階層データｕｋ３とに関連性が無い場合等は、下記の疎行列を用いて符号化および復号を行なうことができる。
【数１０】
0005603972.tif 000011
【００４０】
このように、本実施形態の疎行列は、階層データにより様々なバリエーションを持ち、その疎行列の作成手段としては、ＬＤＰＣ符号等の手法（参照文献：R.G.Gallager, "Low density parity check codes," in Research Monograph series.Cambridge, MIT Press, 1963）で作成される疎行列を用いることができる。
復号は、前記した非階層的な疎グラフ符号の場合と同様に、ＢＰ（Belief Propagation）復号法で解くことにより行うことができる。階層的疎グラフ符号のＢＰ復号法は、タナーグラフとして示すことができる（図示省略）。
【００４１】
（データの分散配置について）
図５は、分散配置手段１３が実行する処理の説明図である。前記のとおり、ソースシンボル、パリティシンボルは、階層的疎グラフ符号で生成され、本例では、テキストデータａは画像データｂより重要度が高いと規定している。
震災発生時等、通信回線容量が限定されてしまう場合は、できるだけ重要なシンボルから先に分散配置する方が望ましい。
【００４２】
そこで、分散配置手段１３は、相対的に重要度が高いテキストデータａに関するソースシンボルＡ〜Ｃ、および、パリティシンボルＰＡＢＣ，ＰＤＥＦ，ＰＧＨＩについては、送信順位第１位として、優先的にＷｅｂサーバ３ａ〜３ｄに分散配置する。そして、相対的に重要度が低い画像データｂに関するソースシンボルＤ〜Ｉについては（パリティシンボルＰＤＥＦ，ＰＧＨＩは画像データｂに関するが、テキストデータａに関するパリティシンボルでもあるため、送信順位第１位としている）、送信順位第２位として、前記の送信順位第１位のデータを分散配置後にＷｅｂサーバ３ａ〜３ｄに分散配置する。このような送信順位に関する優先順位付けは優先順位付け手段１１により行う（後述する）。
【００４３】
これら、各データをＷｅｂサーバ３ａ〜３ｄに分散配置するに際しては、送信する各データをＷｅｂサーバ３ａ〜３ｄのいずれに送信したかを示す各データと関連付けられた識別情報（データ識別情報）と、当該各データが送信順位第１位なのか第２位なのかを示す識別情報（順位識別情報）とを、Ｗｅｂサーバ３ｅにおいて記憶する。なお、本例では、送信順位第１位、第２位の２段階の重要度の順にデータ送信を行う例を示しているが、３段階以上の重要度を設定し、その順にデータ送信を行うようにしてもよい。
【００４４】
（データの収集について）
図６は、優先順位付け収集手段１４が実行する処理を説明する説明図である。前記のようにＷｅｂサーバ３ａ〜３ｄに分散配置された互いに相関のある複数のデータ（前記の例では、テキストデータａ、画像データｂ）について、クライアントコンピュータ５からのダウンロード要求をＷｅｂサーバ３ｅが受信したときは、Ｗｅｂサーバ３ａ〜３ｄに分散配置されている当該データをＷｅｂサーバ３ｅが収集して、クライアントコンピュータ５に送信する。
この場合に、震災などで、通信回線容量が限定されている場合は、できるだけ重要なシンボルから先に収集して復号し、送信することが望ましい。
【００４５】
そこで、図６に示すように、優先順位付け収集手段１４は、Ｗｅｂサーバ３ｅに記憶されている前記の順位識別情報に基づいて、送信順位第１位であるデータを、前記のデータ識別情報の示す格納先（Ｗｅｂサーバ３ａ〜３ｄのいずれか）から優先的に収集する。このデータは、階層的疎グラフ復号手段１５で復号してクライアントコンピュータ５に送信する。しかる後、優先順位付け収集手段１４は、順位識別情報に基づいて、送信順位第２位であるデータを、データ識別情報の示す格納先から収集する。そして、このデータも階層的疎グラフ復号手段１５で復号してクライアントコンピュータ５に送信する。
【００４６】
すなわち、前記の例では、送信順位第１位であるテキストデータａに関するソースシンボルＡ〜Ｃ、および、パリティシンボルＰＡＢＣ，ＰＤＥＦ，ＰＧＨＩについて、優先的にデータを収集する。そして、その後に、送信順位第２位である画像データｂに関するソースシンボルＤ〜Ｉについて（パリティシンボルＰＤＥＦ，ＰＧＨＩは画像データｂに関するが、テキストデータａに関するパリティシンボルでもあるため、送信順位第１位としている）、データを収集する。
【００４７】
（優先順位付けについて）
前記のとおり、Ｗｅｂサーバ３ａ〜３ｄにデータを分散配置する際、これらＷｅｂサーバ３ａ〜３ｄからデータを収集する際の優先順位（送信順位）は、優先順位付け手段１１が行う。具体的には、互いに相関のある複数データの中での優先順位（送信順位）を予め定められた基準に基づいて決定し、その優先順位（送信順位）の高い順にデータを階層的疎グラフ復号手段１２に出力する。よって、階層的疎グラフ復号手段１２は、そのデータを受けた順番に当該データについて前記した処理を実行する。以下では、優先順位付け手段１１の処理例について３例説明する。
【００４８】
１．データ種類に基づく優先順位付け
図７は、処理対象となるデータの種類により優先順位を判断する例を説明する優先順位付け手段１１の機能ブロック図である。この優先順位付け手段１１は、データ種類判定手段２１と、並び替え手段２２とを備えている。データ種類判定手段２１は、入力された互いに相関のある複数データ１，２，…，ｎについて、データ種類を判定し、そのデータ種類に応じて優先順位を判断する。並び替え手段２２は、データ種類判定手段２１が判定した優先順位に応じてデータの並び替えを行う。
【００４９】
一例をあげると、本例では、データ種類を、テキストデータ、静止画像データ、動画像データの順に重要であると判断する。例えば、互いに相関のある複数データ１，２，…，ｎがインターネット２上のニュース素材のデータである場合、そのニュース素材中に含まれるデータを、テキストデータ、静止画像データ、動画像データの順に重要であると判断する。そして、並び替え手段２２は、その判断に基づき、重要と判断されたデータの順に階層的疎グラフ符号化手段１２にデータを出力する（出力データＰ１〜Ｐｎの順に重要度が高い）。
【００５０】
２．参照回数に基づく優先順位付け
図８は、処理対象となるデータの参照回数により優先順位を判断する例を説明する優先順位付け手段１１の機能ブロック図である。この優先順位付け手段１１は、参照回数判定手段２３と、並び替え手段２２とを備えている。参照回数判定手段２３は、入力された互いに相関のある複数データ１，２，…，ｎについて、インターネット２上での過去の参照回数を判定して、その参照回数に応じて優先順位を判断する。並び替え手段２２は、参照回数判定手段２３が判定した参照回数に応じてデータの並び替えを行う。すなわち、参照回数が多い程、優先順位が高いと判断し、優先順位が高い順にデータを階層的疎グラフ符号化手段１２に出力する（出力データＰ１〜Ｐｎの順に重要度が高い）。参照回数判定手段２３は、公知のロボット型の検索エンジン等が備えているインターネット２上のコンテンツの参照回数を判定する手段と同様の手段により、参照回数の判断を行うことができる。なお、このような参照回数のデータを他のＷｅｂサーバ等から取得するようにしてもよい。
【００５１】
この場合の情報の単位や参照回数を計算する時間の単位は、一意ではなく、様々に設定することが可能である。例えば、情報の単位は、前記のソースシンボルＡ〜Ｉ単位に設定も可能であり、複数のソースシンボルの集まりの単位（例えば、ソースシンボルＡＢＣ，ＤＥＦ，ＧＨＩの各単位）に設定することも可能である。また、参照回数を計算する時間の単位も、１時間、１日など、様々に設定できる。
【００５２】
３．リンク回数に基づく優先順位付け
図９は、処理対象となるデータのリンク回数により優先順位を判断する例を説明する優先順位付け手段１１の機能ブロック図である。この優先順位付け手段１１は、リンク回数判定手段２４と、並び替え手段２２とを備えている。リンク回数判定手段２４は、入力された互いに相関のある複数データ１，２，…，ｎについて、インターネット２上で過去にハイパーリンクを用いて他のコンテンツからリンクされた回数を判定して、そのリンク回数に応じて優先順位を判断する。並び替え手段２２は、リンク回数判定手段２４が判定したリンク回数に応じてデータの並び替えを行う。すなわち、リンク回数が多い程、優先順位が高いと判断し、優先順位が高い順にデータを階層的疎グラフ符号化手段１２に出力する（出力データＰ１〜Ｐｎの順に重要度が高い）。リンク回数判定手段２４は、公知のロボット型の検索エンジン等が備えているインターネット２上のコンテンツのリンクされた回数を判定する手段と同様の手段により、リンク回数の判断を行うことができる。なお、このようなリンク回数のデータを他のＷｅｂサーバ等から取得するようにしてもよい。
【００５３】
この場合の情報の単位やリンク回数を計算する時間の単位も、一意ではなく、様々に設定することが可能である。例えば、情報の単位は、前記のソースシンボルＡ〜Ｉ単位に設定も可能であり、複数のソースシンボルの集まりの単位（例えば、ソースシンボルＡＢＣ，ＤＥＦ，ＧＨＩの各単位）に設定することも可能である。また、参照回数を計算する時間の単位も、１時間、１日など、様々に設定できる。
【００５４】
［データ処理方法］
次に、データ処理システム１が実行するデータ処理方法について説明する。図１０は、データ処理システム１が実行するデータ処理方法について説明するフローチャートである（図１、図２も参照）。
まず、優先順位付け手段１１は、クライアントコンピュータ５が相関する複数のデータアップロードしたときは（ステップＳ１のＹｅｓ）、相関する複数のデータの相対的な重要度を判断して、優先順位を付ける（ステップＳ２）（第１のステップ）。ステップＳ１の後、階層的疎グラブ符号化手段１２は、優先順位付け手段１１で優先順位が付けられたデータを、階層的疎グラフ符号を誤り訂正符号として符号化する。この際に、複数のデータのうち重要度の高いものほど強度の強い誤り訂正が可能となるように符号化する（ステップＳ３）（第２のステップ）。ステップＳ３の後、分散配置手段１３は、疎グラブ符号化手段１２で符号化されたデータを前記の優先順にｗｅｂサーバ３ａ〜３ｄに分散して送信し、当該データをｗｅｂサーバ３ａ〜３ｄに分散して格納配置するようにする（ステップＳ４）（第３のステップ）。
【００５５】
一方、優先順位付け収集手段１４は、クライアントコンピュータ５のダウンロード要求があったときは（ステップＳ５のＹｅｓ）、当該ダウンロード要求に応じて、ｗｅｂサーバ３ａ〜３ｄに分散配置されているデータを、前記の優先順に収集する（ステップＳ６）。そして、階層的疎グラフ復号手段１５は、優先順位付け収集手段１４で収集したデータを復号して（ステップＳ７）、クライアントコンピュータ５に送信する（ステップＳ８）。なお、クライアントコンピュータ５のダウンロード要求がないときは（ステップＳ５のＮｏ）、ステップＳ１に戻る。
前記ステップＳ１〜Ｓ８の各ステップの更に詳細な処理内容については、前記のデータ処理システム１の構成と作用の説明から明らかである。
【００５６】
以上説明した本実施形態のデータ処理システム１、Ｗｅｂサーバ３ｅ、データ処理方法によれば、図４を参照して前記した内容から明らかなように、重要度の高いデータは高いロバスト性能でＷｅｂサーバ３ａ〜３ｄに分散して送信し、保存する一方、重要度の低いデータは通信回線容量および演算コストを抑制してＷｅｂサーバ３ａ〜３ｄに分散して送信し、保存することができる。
この場合に、前記のとおり階層的疎グラフ符号を用いているので、通信回線容量が限定された状況でも、冗長度が低い条件（復号するために必要な情報量が少ない条件）で、データを保護する強度を高めることができる。
さらに、図７〜図９を参照して前記したように、優先順位付け手段１１を備えたことにより、重要度の高いデータを優先的にＷｅｂサーバ３ａ〜３ｄに分散して送信し、保存することや、優先的にＷｅｂサーバ３ａ〜３ｄから収集することができる。
【符号の説明】
【００５７】
１      データ処理システム
３ａ〜３ｄ  Ｗｅｂサーバ（記憶装置）
３ｅ    Ｗｅｂサーバ（データ処理装置）
１１    優先順位付け手段（重要度判断手段）
１２    階層的疎グラフ符号化手段（符号化手段）
１３    分散配置手段（送信手段）
１４    優先順位付け収集手段（収集手段）
Ｓ２    （第１のステップ）
Ｓ３    （第２のステップ）
Ｓ４    （第３のステップ）
【要約】
【課題】通信回線容量および演算コストをできるだけ抑制しつつ、重要なデータは高いロバスト性能で分散して送信し、保存する。
【解決手段】優先順位付け手段１１は、クライアントコンピュータがアップロードした、相関する複数のデータ間の相対的な重要度を判断して、優先順位を付ける。階層的疎グラブ符号化手段１２は、優先順位付け手段１１で優先順位が付けられたデータを、階層的疎グラフ符号を誤り訂正符号として符号化する。この際に、複数のデータのうち重要度の高いものほど強度の強い誤り訂正が可能となるように符号化する。分散配置手段１３は、疎グラブ符号化手段１２で符号化されたデータをｗｅｂサーバに前記の優先順に分散して送信し、当該データをｗｅｂサーバに分散して格納配置するようにする。
【選択図】図２【図１】
0005603972.tif 000012
【図２】
0005603972.tif 000013
【図３】
0005603972.tif 000014
【図４】
0005603972.tif 000015
【図５】
0005603972.tif 000016
【図６】
0005603972.tif 000017
【図７】
0005603972.tif 000018
【図８】
0005603972.tif 000019
【図９】
0005603972.tif 000020
【図１０】
0005603972.tif 000021