(57)【要約】【課題】  本発明は、選択型コンテンツの配信にあたり、帯域幅を抑えることができる配信順序計画装置、該方法、該方法のプログラム及び該プログラムを記録した記録媒体を提供する。【解決手段】  本発明に係る、複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける複数のコンテンツ要素を配信する順序を計画する配信順序計画装置は、複数のコンテンツ要素における視聴順序に基づいて選択型コンテンツが再生の開始後再生の終了まで途切れずに再生可能となるように複数のコンテンツ要素の配信順序を計画する配信順序計画処理部を備える。【選択図】      図１
2007067602.tif 000002
【特許請求の範囲】
【請求項１】
複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画する配信順序計画装置において、
前記複数のコンテンツ要素における視聴順序に基づいて前記選択型コンテンツが再生の開始後再生の終了まで途切れずに再生可能となるように前記複数のコンテンツ要素の配信順序を計画する配信順序計画処理部を備えること
を特徴とする配信順序計画装置。
【請求項２】
前記複数のコンテンツ要素は、互いに再生時間が同一であって、最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフで表記され、
前記配信順序計画処理部は、
根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択部と、
前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定部と、
前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定部と、
前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当部と、
前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当部と、
前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当部とを備えること
を特徴とする請求項１に記載の配信順序計画装置。
【請求項３】
複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画する配信順序計画方法において、
前記複数のコンテンツ要素は、互いに再生時間が同一であって、最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフで表記され、
根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択ステップと、
前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定ステップと、
前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定ステップと、
前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当ステップと、
前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当ステップと、
前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当ステップとを備えること
を特徴とする配信順序計画方法。
【請求項４】
複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画する配信順序計画方法において、
前記複数のコンテンツ要素が互いに再生時間が同一であって最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフとなるように、前記選択型コンテンツにおける、自己に戻る遷移を省略し、視聴順序の順番で過去に戻る遷移を省略し、分岐しないコンテンツ要素を視聴順序の順番で次のコンテンツ要素に結合し、最小の再生時間を単位にコンテンツ要素を分割するグラフ処理ステップと、
根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択ステップと、
前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定ステップと、
前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定ステップと、
前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当ステップと、
前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当ステップと、
前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当ステップとを備えること
を特徴とする配信順序計画方法。
【請求項５】
前記第２割当ステップは、
第１変数ｉに２を代入する第１ステップと、
第２変数ｊに２を代入すると共に第３変数ｋに０を代入する第２ステップと、
深さが等しいコンテンツ要素であって前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を要素とする集合を集合Ｒとした場合に、主順序に含まれるコンテンツ要素の個数から第３変数ｋを減算した値、第２変数ｊから第３変数ｋを減算した値、及び、第２変数ｊの深さの集合Ｒにおける要素の個数のうち最も小さい値の個数のコンテンツ要素を、第２変数ｊの深さの集合Ｒから選択して第１変数ｉ番目のチャネルに割り当てる第３ステップと、
第３ステップで割り当てたコンテンツ要素を第２変数ｊの深さの集合Ｒから削除する第４ステップと、
前記第３変数ｋに前記第３ステップで割り当てたコンテンツ要素の個数を加算する第５ステップと、
前記第２変数ｊが前記主順序に含まれるコンテンツ要素の個数より小さい場合には前記第２変数ｊに１を加算した後に前記第３ステップに戻すと共に、前記第２変数ｊが前記主順序に含まれるコンテンツ要素の個数以上である場合には前記第１変数ｉに１を加算する第６ステップと、
前記第１変数ｉが前記チャネル総数より小さい場合には前記第２ステップに戻すと共に、前記第１変数ｉが前記チャネル総数である場合には前記第３割当ステップを実行すること
を特徴とする請求項３又は請求項４に記載の配信順序計画方法。
【請求項６】
複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画するように、コンピュータを機能させるための配信順序計画プログラムにおいて、
前記複数のコンテンツ要素は、互いに再生時間が同一であって、最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフで表記され、
根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択ステップと、
前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定ステップと、
前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定ステップと、
前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当ステップと、
前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当ステップと、
前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当ステップとを備えること
を特徴とする配信順序計画プログラム。
【請求項７】
複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画するように、コンピュータを機能させるための配信順序計画プログラムを記録したコンピュータに読み取り可能な記録媒体において、
前記複数のコンテンツ要素は、互いに再生時間が同一であって、最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフで表記され、
前記配信順序計画プログラムは、
根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択ステップと、
前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定ステップと、
前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定ステップと、
前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当ステップと、
前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当ステップと、
前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当ステップとを備えること
を特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、選択型コンテンツを構成するコンテンツ要素を配信する順序を計画する配信順序計画装置に関する。そして、本発明は、このような配信順序計画装置に実装される配信順序計画方法、配信順序計画方法の配信順序計画プログラム及び該配信順序計画プログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
近年、従来の地上波アナログテレビ放送だけでなく、ＢＳ（broadcast satellite）やＣＳ（communication satellite）の衛星放送、ケーブルテレビ放送、地上波ディジタルテレビ放送、及び、インターネットの利用等のように、コンテンツの配信形態が多様化し、様々なコンテンツが配信可能になってきている。
【０００３】
コンテンツは、様々な基準によって分類可能であるが、コンテンツの中には、複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を上記複数のコンテンツ要素の中に少なくとも１つ含むコンテンツがある。このようなコンテンツを本明細書において、「選択型コンテンツ」と呼ぶこととする。
【０００４】
この選択型コンテンツを一例を挙げると、例えば、多枝択一クイズ番組のコンテンツがある。この多枝択一クイズ番組では、問題及び選択枝のコンテンツが提示され、その後、ユーザが回答を選択すると、このユーザの回答に応じたコンテンツが提示される。例えば、二者択一クイズ番組のコンテンツの場合では、問題及び選択枝のコンテンツが提示され、その後、ユーザが回答を選択する。そして、ユーザの回答が正解の場合には正解のコンテンツが提示され、ユーザの回答が不正解の場合には不正解のコンテンツが提示される。このように選択型コンテンツは、ユーザの選択によってコンテンツの展開が変わり、ユーザの嗜好に合わせたコンテンツを提供することができる。
【０００５】
ここで、このような多枝択一クイズ番組のコンテンツの場合、問題及び選択枝のコンテンツや回答に応じたコンテンツがコンテンツ要素に相当し、コンテンツ要素は、選択型コンテンツを構成する個々のコンテンツである。また、問題及び選択肢のコンテンツが２以上のコンテンツ要素へ分岐可能なコンテンツ要素に相当する。
【０００６】
このような選択型コンテンツを放送局やサーバが配信する場合、受信装置が再生の開始後再生の終了までコンテンツを途切れずに再生することができるようにしなければならないため、放送局やサーバは、複数の選択枝にそれぞれ対応する複数のコンテンツ要素を、これらコンテンツ要素が再生される可能性が生じる時までに配信する必要がある。
【０００７】
ここで、準オンデマンドにおいて、多数のユーザに対してチャネル数及び最大待ち時間を抑えつつ効率的に番組コンテンツを配信するために、番組コンテンツの配信順序をスケジューリング（計画）するコンテンツ配信方法が例えば特許文献１に開示されている。この特許文献１に開示の、番組サーバがユーザ端末に対して準オンデマンドで番組コンテンツを配信するコンテンツ配信方法は、前記番組サーバが、ｎ番目の情報グループのデータサイズがＤ×Ｒ（ｎ−１）（但し、Ｄは、番組コンテンツの先頭部に相当する１番目の情報グループのデータサイズ、Ｒは、番組コンテンツの再生速度に対する各チャネルの伝送速度の比）かつＲが１より大きい数であるように、前記番組コンテンツを先頭から順に分割して複数の情報グループを生成する第１のステップと、前記第１のステップで生成された前記情報グループのうち、ｎ番目の情報グループが、番組コンテンツの再生速度のＲ倍の伝送速度を有する複数のチャネルのうちのチャネル番号ｎのチャネルを介して周期的に連続的に放送されるよう、全ての情報グループに対してスケジューリングを行なう第２のステップと、前記第２のステップにおける前記スケジューリングの結果に従って、各情報グループを放送する第３のステップと、前記第３のステップで放送された前記情報グループのうち、チャネル番号１のチャネルで周期的に放送されている１番目の情報グループで、かつ、ユーザがダウンロード要求した時点以降に放送される最早の情報グループをグループ単位で前記ユーザ端末にダウンロードする第４のステップと、チャネル番号ｋ（ｋ＝１、２、３、・・・）のチャネルで放送されているｋ番目の情報グループのダウンロードが完了した直後に、チャネル番号ｋ＋１のチャネルで放送されているｋ＋１番目の情報グループが存在する場合には、前記ユーザ端末にダウンロードされているｋ番目の情報グループの再生を開始すると共に、チャネル番号ｋ＋１のチャネルで放送されているｋ＋１番目の情報グループのダウンロードを開始して、該ｋ番目の情報グループの再生が完了した時点で、該ｋ＋１番目の情報グループのユーザ端末へのダウンロードを終了し、チャネル番号ｋ＋１のチャネルで放送されているｋ＋１番目の情報グループが存在しない場合には、チャネル番号ｋのチャネルで放送されているｋ番目の情報グループのダウンロードが完了した直後に、該ユーザ端末にダウンロードされている該ｋ番目の情報グループの再生を開始する第５のステップからなるものである。
【特許文献１】特開２００３−０４６９７５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ところで、複数の選択枝にそれぞれ対応する複数のコンテンツ要素を単純に再生開始時刻と同時に配信を開始する場合では、これらコンテンツ要素の個数に応じた放送チャネル（帯域幅）が必要となる。このため、選択枝の枝数の増加に伴って、また、選択の機会の増加に伴って広い帯域幅が必要になるという不都合がある。
【０００９】
また、上記、特許文献１に開示のコンテンツ配信方法は、チャネル数を抑制することができるが、準オンデマンドの番組コンテンツを配信するための技術である。
【００１０】
本発明は、上記事情に鑑みて為されたものであり、選択型コンテンツの配信にあたり、帯域幅を抑えることができるコンテンツ要素の配信順序を計画する配信順序計画装置を提供することを目的とする。そして、本発明は、このような配信順序計画装置に実装される配信順序計画方法、配信順序計画方法の配信順序計画プログラム及び該配信順序計画プログラムを記録した記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明者は、種々検討した結果、上記目的は、以下の本発明により達成されることを見出した。即ち、本発明に係る一態様では、複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画する配信順序計画装置において、前記複数のコンテンツ要素における視聴順序に基づいて前記選択型コンテンツが再生の開始後再生の終了まで途切れずに再生可能となるように前記複数のコンテンツ要素の配信順序を計画する配信順序計画処理部を備えることを特徴とする。
【００１２】
図１は、本発明の原理を説明するための図である。図１（Ａ）は、選択型コンテンツの状態遷移グラフを示し、図１（Ｂ）は、本発明によって計画された配信順序を示し、そして、図１（Ｃ）は、単純手法によって計画された配信順序を示す。
【００１３】
例えば、図１（Ａ）に示すように、コンテンツ要素Ｓａ’、Ｓｃ及びＳｄの３個のコンテンツ要素から成り、コンテンツ要素Ｓａ’からコンテンツ要素Ｓｃ及びＳｄに分岐可能なコンテンツ要素Ｓａ’を含む選択型コンテンツでは、コンテンツ要素Ｓａ’、Ｓｃ及びＳｄの視聴順序を考慮すると、コンテンツ要素Ｓｃ及びＳｄは、コンテンツ要素Ｓａ’の後に視聴され得るので、コンテンツ要素Ｓａ’の配信中に配信可能である。そこで、本発明では、図１（Ｂ）に示すように、第１のチャネルでは、コンテンツ要素Ｓａ’及びＳｃ（又はＳｄ）を配信し、第２のチャネルでは、コンテンツ要素Ｓａ’の配信開始と同時にコンテンツ要素Ｓｄ（又はＳｃ）の配信を開始するように、各コンテンツ要素Ｓａ’、Ｓｃ及びＳｄの配信順序を計画する。このように配信順序を計画すると、例えば、各コンテンツ要素Ｓａ’、Ｓｃ及びＳｄの再生時間が同一であって、第１のチャネルの帯域幅をコンテンツ要素Ｓａ’及びＳｃ（又はＳｄ）の再生レートＢに一致させると、第２のチャネルの帯域幅は、第１のチャネルの帯域幅の半分にすることができる。よって、配信に必要な帯域幅は、１．５×Ｂとなる。
【００１４】
一方、比較例を挙げると、選択型コンテンツのコンテンツ要素を再生開始時刻と同時に配信を開始する単純な配信順序計画手法（単純手法）では、図１（Ｃ）に示すように、第１のチャネルでは、コンテンツ要素Ｓａ’及びＳｃ（又はＳｄ）を配信し、第２のチャネルでは、コンテンツ要素Ｓｃ（又はＳｄ）の配信開始と同時にコンテンツ要素Ｓｄ（又はＳｃ）の配信を開始するように、各コンテンツ要素Ｓａ’、Ｓｃ及びＳｄの配信順序を計画しなければならないため、第２のチャネルの帯域幅も第１のチャネルの帯域幅と等しくなければならない。よって、配信に必要な帯域幅は、２×Ｂとなる。
【００１５】
従って、選択型コンテンツを配信するにあたり、本発明に係る配信順序計画装置は、単純手法に較べて、２５パーセント削減することができ、配信に必要な帯域幅を狭くすることができる。
【００１６】
そして、上述の配信順序計画装置において、前記複数のコンテンツ要素は、互いに再生時間が同一であって、最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフで表記され、前記配信順序計画処理部は、根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択部と、前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定部と、前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定部と、前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当部と、前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当部と、前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当部とを備えることを特徴とする。
【００１７】
そして、本発明に係る他の一態様では、複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画する配信順序計画方法において、前記複数のコンテンツ要素は、互いに再生時間が同一であって、最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフで表記され、根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択ステップと、前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定ステップと、前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定ステップと、前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当ステップと、前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当ステップと、前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当ステップとを備えることを特徴とする。
【００１８】
また、本発明に係る他の一態様では、複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画する配信順序計画方法において、前記複数のコンテンツ要素が互いに再生時間が同一であって最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフとなるように、前記選択型コンテンツにおける、自己に戻る遷移を省略し、視聴順序の順番で過去に戻る遷移を省略し、分岐しないコンテンツ要素を視聴順序の順番で次のコンテンツ要素に結合し、最小の再生時間を単位にコンテンツ要素を分割するグラフ処理ステップと、根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択ステップと、前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定ステップと、前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定ステップと、前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当ステップと、前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当ステップと、前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当ステップとを備えることを特徴とする。
【００１９】
さらに、これら上述の配信順序計画方法において、前記第２割当ステップは、第１変数ｉに２を代入する第１ステップと、第２変数ｊに２を代入すると共に第３変数ｋに０を代入する第２ステップと、深さが等しいコンテンツ要素であって前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を要素とする集合を集合Ｒとした場合に、主順序に含まれるコンテンツ要素の個数から第３変数ｋを減算した値、第２変数ｊから第３変数ｋを減算した値、及び、第２変数ｊの深さの集合Ｒにおける要素の個数のうち最も小さい値の個数のコンテンツ要素を、第２変数ｊの深さの集合Ｒから選択して第１変数ｉ番目のチャネルに割り当てる第３ステップと、第３ステップで割り当てたコンテンツ要素を第２変数ｊの深さの集合Ｒから削除する第４ステップと、前記第３変数ｋに前記第３ステップで割り当てたコンテンツ要素の個数を加算する第５ステップと、前記第２変数ｊが前記主順序に含まれるコンテンツ要素の個数より小さい場合には前記第２変数ｊに１を加算した後に前記第３ステップに戻すと共に、前記第２変数ｊが前記主順序に含まれるコンテンツ要素の個数以上である場合には前記第１変数ｉに１を加算する第６ステップと、前記第１変数ｉが前記チャネル総数より小さい場合には前記第２ステップに戻すと共に、前記第１変数ｉが前記チャネル総数である場合には前記第３割当ステップを実行することを特徴とする。
【００２０】
そして、本発明に係る他の一態様では、複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画するように、コンピュータを機能させるための配信順序計画プログラムにおいて、前記複数のコンテンツ要素は、互いに再生時間が同一であって、最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフで表記され、根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択ステップと、前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定ステップと、前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定ステップと、前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当ステップと、前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当ステップと、前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当ステップとを備えることを特徴とする。
【００２１】
また、本発明に係る他の一態様では、複数のコンテンツ要素から成り２以上のコンテンツ要素へ分岐可能なコンテンツ要素を前記複数のコンテンツ要素の中に少なくとも１つ含む選択型コンテンツにおける前記複数のコンテンツ要素を配信する順序を計画するように、コンピュータを機能させるための配信順序計画プログラムを記録したコンピュータに読み取り可能な記録媒体において、前記複数のコンテンツ要素は、互いに再生時間が同一であって、最初に再生されるコンテンツ要素を根とする多分木の状態遷移グラフで表記され、前記配信順序計画プログラムは、根のコンテンツ要素から葉のコンテンツ要素に至る１つの視聴順序を主順序として選択する選択ステップと、前記選択型コンテンツのコンテンツ要素の総数を前記主順序に含まれるコンテンツ要素の個数で除算すると共に小数点以下を繰り上げた整数値をチャネル総数として演算し、演算した前記チャネル総数個のチャネルを前記選択型コンテンツ要素を配信するために使用する使用チャネルに設定する使用チャネル設定ステップと、前記使用チャネルのうちの１番目乃至（前記チャネル総数−１）番目のチャネルにおける帯域幅を前記コンテンツ要素の再生レートに一致するように設定する帯域幅設定ステップと、前記主順序に含まれるコンテンツ要素を視聴順序に従って前記使用チャネルのうちの１番目のチャネルに割り当てる第１割当ステップと、前記主順序に含まれるコンテンツ要素を除いたコンテンツ要素を、前記１番目のチャネルに割り当てられたコンテンツ要素を配信する時間帯に対応する２番目から（前記チャネル総数−１）番目までのチャネルにおける時間帯に、根のコンテンツ要素の深さを１とした場合に、当該時間帯に割り当てられるコンテンツ要素の深さが当該時間帯に対応する前記１番目のチャネルの時間帯に割り当てられているコンテンツ要素の深さ以上となるように、割り当てる第２割当ステップと、前記第１乃至（前記チャネル総数−１）番目のチャネルに割り当てたコンテンツ要素を除いたコンテンツ要素を視聴順序に従ってチャネル総数番目のチャネルに割り当てる第３割当ステップとを備えることを特徴とする。
【発明の効果】
【００２２】
このような構成の配信順序計画装置及び配信順序計画方法は、単純手法に較べて、選択型コンテンツの視聴順序を考慮してコンテンツ要素の配信順序を計画（スケジューリング）するので、配信に必要な帯域幅を狭くすることができる。
【００２３】
また、このような構成の配信順序計画プログラム及び配信順序計画プログラムを記録した記録媒体では、コンピュータに配信順序計画プログラムを実行させることによって、配信に必要な帯域幅が狭くなるように、選択型コンテンツの各コンテンツ要素の配信順序を計画する装置を提供することができる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明に係る実施形態を図面に基づいて説明する。なお、各図において同一の符号を付した構成は、同一の構成であることを示し、その説明を省略する。
（実施形態の構成）
図２は、実施形態に係る配信システムの構成を示す図である。図３は、放送局の構成を示すブロック図である。図４は、選択型コンテンツ情報テーブルの構成を示す図である。
【００２５】
図２において、本実施形態の配信システムは、選択型コンテンツを配信する放送局１と、選択型コンテンツを受信し視聴者に提示する受信装置２とを備え、放送局１と受信装置２とは、衛星放送３−Ｓ、地上波放送３−Ｂ、ケーブルテレビ放送３−Ｃ及びネットワーク配信３−Ｎ等の配信形態に応じた無線又は有線の伝送路（伝送媒体）によって通信可能に接続され、放送局１から選択型コンテンツが受信装置２に配信（放送）される。
【００２６】
放送局１は、本発明に係る配信順序計画装置及び配信順序計画方法が組み込まれており、後述の処理により選択型コンテンツを構成する各コンテンツ要素の配信順序をスケジューリング（計画）し、このスケジューリングしたスケジュールに従って、所定の配信形態によって受信装置２に選択型コンテンツを配信する装置である。放送局１は、例えば、図３に示すように、情報処理部１１と、記憶部１２と、送信データ生成部１３と、送信部１４とを備えて構成される。
【００２７】
情報処理部１１は、例えば、マイクロプロセッサ及びその周辺回路等を備えて構成され、機能的に、視聴順序グラフ処理部１１１と、配信順序計画処理部１１２と、配信処理部１１３とを備え、制御プログラムに従い記憶部１２、送信データ生成部１３及び送信部１４を当該機能に応じてそれぞれ制御する。
【００２８】
視聴順序グラフ処理部１１１は、選択型コンテンツを構成する各コンテンツ要素の配信順序をスケジューリングし易くするために、選択型コンテンツの視聴順序を表記する状態遷移グラフである視聴順序グラフを省略、結合及び分割する処理を実行する。配信順序計画処理部１１２は、選択型コンテンツを構成する各コンテンツ要素の視聴順序に基づいてこの選択型コンテンツが受信装置２で再生の開始後再生の終了まで途切れずに再生可能となるように各コンテンツ要素の配信順序をスケジューリングする。配信処理部１１３は、配信順序計画処理部１１２でスケジューリングされた各コンテンツ要素の配信順序に従って、記憶部１２に記憶されている各コンテンツ要素を送信データ生成部１３及び送信部１４を用いて、所定の伝送路によって配信する。
【００２９】
記憶部１２は、選択型コンテンツ情報を記憶する選択型コンテンツ情報記憶部１２１と、選択型コンテンツを記憶する選択型コンテンツ記憶部１２２とを備え、選択型コンテンツを構成する各コンテンツ要素の配信順序を後述のようにスケジューリングする配信順序計画プログラムや、記憶部１２、送信データ生成部１３及び送信部１４の制御プログラム等の各種プログラム、及び、各種プログラムの実行に必要なデータやその実行中に生じるデータ等の各種データを記憶する。記憶部１２は、例えば、情報処理部１１の所謂ワーキングメモリとなるＲＡＭ（Random Access Memory）等の揮発性の記憶素子、各種プログラムや各種データを格納しておく、ＲＯＭ（Read Only Memory）や書換え可能なＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）等の不揮発性の記憶素子、及び、比較的大容量の記憶装置であるハードディスク等を備えて構成される。
【００３０】
選択型コンテンツ情報は、選択型コンテンツを構成する各コンテンツ要素の配信順序をスケジューリングするために必要な情報であり、本実施形態では、例えば、当該コンテンツ要素を特定し識別するための識別子であるコンテンツ要素識別子、当該コンテンツ要素の再生時間、当該コンテンツ要素に続いて再生される可能性のあるコンテンツ要素（遷移先のコンテンツ要素）のコンテンツ要素識別子、及び、各コンテンツ要素の相互関係をその視聴順序に従って多分木（ツリー構造）の状態遷移グラフで表現した場合における根からの当該コンテンツ要素の深さ（Ｄｅｐｔｈ）である。
【００３１】
選択型コンテンツ情報は、本実施形態では、例えば、図４に示すようにテーブル形式で記憶部１２の選択型コンテンツ情報記憶部１２１に記憶される。図４に示す選択型コンテンツ情報テーブル６０は、当該コンテンツ要素識別子を登録するコンテンツ要素識別子フィールド６１、当該コンテンツ要素の再生時間を登録する再生時間フィールド６２、当該コンテンツ要素における遷移先のコンテンツ要素に対応するコンテンツ要素識別子を登録する遷移先コンテンツ要素識別子フィールド６３、及び、当該コンテンツ要素の深さを登録する深さフィールド６４の各フィールドを備え、コンテンツ要素に応じてレコードが作成される。なお、根のコンテンツ要素は、選択型コンテンツにおいて最初に再生され得るコンテンツ要素であり、本実施形態では、根のコンテンツ要素の深さを「１」としている。また、当該コンテンツ要素における遷移先のコンテンツ要素がない場合には、遷移先コンテンツ要素識別子フィールド６３には当該コンテンツ要素における遷移先のコンテンツ要素がない旨を示す符号、例えば、「ＥＮＤ」が登録される。あるいは、遷移先コンテンツ要素識別子フィールド６３は、空欄にされてもよい。
【００３２】
選択型コンテンツ記憶部１２２には、予め制作されたクイズ番組等の選択型コンテンツのデータが記憶されており、例えば、選択型コンテンツを構成するコンテンツ要素のデータと当該コンテンツ要素のコンテンツ要素識別子とを対応付けて記憶されている。
【００３３】
送信データ生成部１３は、記憶部１２の選択型コンテンツ記憶部１２２に記憶されている選択型コンテンツのデータを配信形態に応じた送信可能な形式に処理して送信データを生成する。送信データ生成部１３は、一例として、例えば放送局１と受信装置２との間で送受信される選択型コンテンツの映像及び音声のデータがＭＰＥＧ（Moving Picture Experts Group）規格に準拠し、放送用データがこのＭＰＥＧ形式に基づくＴＳ（Transport Stream）形式で放送されるディジタル放送システムの場合では、データ放送の番組をセクションデータを含むＴＳパケットに変換して多重化部１３３に出力するデータ放送生成部１３１と、選択型コンテンツのデータをＭＰＥＧ形式に変換してＴＳパケットに変換し多重化部１３３に出力する複数のＭＰＥＧエンコーダ部１３２（１３２−１、１３２−２、・・・、１３２−ｎ）と、データ放送生成部１３１からのＴＳパケット及びＭＰＥＧエンコーダ部１３２からのＴＳパケットを時分割で多重し変調部１３４に出力する多重化部１３３と、多重化部１３３で多重化されたデータを送信部１４で送信可能な形式に変調する変調部１３４とを備えて構成される。ＭＰＥＧエンコーダ部１３２の個数は、チャネル数に対応する。
【００３４】
送信部１４は、送信データ生成部１３で生成した選択型コンテンツの送信データを所定の配信形態に応じて配信する。例えば、衛星放送３−Ｓによって選択型コンテンツが配信される場合には、送信部１４は、衛星放送用送信アンテナを用いて衛星Ｓに送信データ生成部１３で生成した選択型コンテンツの送信データを送信する。衛星Ｓは、選択型コンテンツの送信データの電波を放射し、受信装置２は、衛星放送用受信アンテナでこの選択型コンテンツの送信データの電波を受信し、選択型コンテンツを再生する。また例えば、地上波放送３−Ｂによって選択型コンテンツが配信される場合には、送信部１４は、地上波送信用アンテナを用いて送信データ生成部１３で生成した選択型コンテンツの送信データの電波を放射する。受信装置２は、地上波受信アンテナでこの選択型コンテンツの送信データの電波を受信し、選択型コンテンツを再生する。また例えば、ケーブルテレビ放送３−Ｃによって選択型コンテンツが配信される場合には、送信部１４は、同軸ケーブルや光ファイバ等のケーブルを用いて送信データ生成部１３で生成した選択型コンテンツの送信データを受信装置２に送信する。受信装置２は、ケーブルを介して受信した選択型コンテンツを再生する。また例えば、ネットワーク配信３−Ｎによって選択型コンテンツが配信される場合には、送信部１４は、ネットワークＮを用いて送信データ生成部１３で生成した選択型コンテンツの送信データを受信装置２に送信する。受信装置２は、ネットワークＮを介して受信した選択型コンテンツを再生する。
【００３５】
ネットワークＮは、有線又は無線の伝送路によって構成される通信網であり、例えば、電話網、ディジタル通信網及び無線通信網等である。ネットワークＮには、所定の通信プロトコルが用いられてデータが伝送される。通信プロトコルには、例えば、ＨＴＴＰ（Hyper Text Transfer Protocol）、ＦＴＰ（File Transfer Protocol）、ＲＳＶＰ（Resource reSerVation Protocol）、ＳＭＴＰ（Simple Mail Transfer Protocol）、ＰＯＰ３（Post Office Protocol ver.3）及びＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol）等の所謂インターネットプロトコル群が用いられる。この場合、ネットワークＮは、インターネットを構成する。
【００３６】
ここで、インターネットを介して選択型コンテンツを送信する場合、放送局１は、いわゆるサーバコンピュータとなり、受信装置２は、いわゆるクライアントコンピュータとなって、放送局１は、選択型コンテンツを管理して受信装置２の要求に応じて選択型コンテンツを提供することで、選択型コンテンツを送信する。
【００３７】
受信装置２は、放送局１より番組の配信が開始されてから当該番組の選択型コンテンツの配信を受け、ユーザの選択に応じた展開の選択型コンテンツを番組の再生を開始すると最後まで再生する装置であり、複数のチャネルから同時に受信可能であって、受信したコンテンツ要素を蓄積することができる充分な記憶容量のバッファメモリを備えている。バッファメモリは、例えば、ＲＡＭ等の記憶素子やハードディスク等の記憶装置を備えて構成される。
【００３８】
次に、本実施形態の動作について説明する。
（実施形態の動作）
まず、視聴順序グラフの省略、結合及び分割の各処理について説明し、その後、選択型コンテンツの各コンテンツ要素に対する配信順序をスケジューリングする配信順序計画処理について説明する。
【００３９】
図５は、視聴順序グラフの省略及び結合の各処理を実行する際における視聴順序グラフ処理部の動作を示すフローチャートである。図６は、視聴順序グラフの省略及び結合の各処理を説明するための図である。図６（Ａ）、（Ｂ）及び（Ｃ）の各左側には、視聴順序グラフを示し、各右側には、左側の視聴順序グラフに対応する選択型コンテンツ情報テーブルを示す。
【００４０】
図５において、視聴順序グラフの省略及び結合の各処理を実行する際に、情報処理部１１の視聴順序グラフ処理部１１１は、まず、記憶部１２の選択型コンテンツ情報記憶部１２１に記憶されている選択型コンテンツ情報の中から省略処理の対象とするコンテンツ要素を選定する（＃１１）。例えば、視聴順序グラフ処理部１１１は、選択型コンテンツ情報テーブル６０の先頭のレコードから末尾のレコードへ順にレコードを選択することによって、処理の対象とする一のコンテンツ要素を選定する。
【００４１】
次に、視聴順序グラフ処理部１１１は、視聴順序が自己に戻る可能性があるか否か、又は、視聴順序が過去に戻る可能性があるか否かを判断する（＃１２）。
【００４２】
この視聴順序が自己に戻る可能性があるか否かの判断は、例えば、選定したコンテンツ要素における遷移先のコンテンツ要素に自己が含まれているか否かを判断することによって、即ち、処理＃１１で選択したレコードにおけるコンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子が、同レコードの遷移先コンテンツ要素識別子フィールド６３に含まれているか否かを判断することによって、実行することができる。コンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子が同レコードの遷移先コンテンツ要素識別子フィールド６３に含まれている場合には、視聴順序が自己に戻る可能性があると判断され、一方、コンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子が同レコードの遷移先コンテンツ要素識別子フィールド６３に含まれていない場合には、視聴順序が自己に戻る可能性がないと判断される。
【００４３】
一方、視聴順序が過去に戻る可能性があるか否かの判断は、例えば、選定したコンテンツ要素における遷移先のコンテンツ要素に過去のコンテンツ要素が含まれているか否かを判断することによって、即ち、処理＃１１で選択したレコードにおける深さフィールド６４に登録されている自己の深さが、処理＃１１で選択したレコードにおける遷移先コンテンツ要素識別子フィールド６３に登録されているコンテンツ要素識別子をコンテンツ要素識別子フィールド６１に登録するレコードにおける深さフィールド６４に登録されている遷移先の深さより、大きいか否かを判断することによって、実行することができる。自己の深さが遷移先の深さよりも大きい場合には、視聴順序が過去に戻る可能性があると判断され、一方、自己の深さが遷移先の深さよりも小さい場合には、視聴順序が過去に戻る可能性がないと判断される。
【００４４】
処理＃１２における判断の結果、視聴順序が自己に戻る可能性がなく、かつ、過去に戻る可能性がないと判断した場合（Ｎｏ）には、視聴順序グラフ処理部１１１は、処理＃１４を実行し、視聴順序が自己に戻る可能性があると判断した場合、及び／又は、視聴順序が過去に戻る可能性があると判断した場合（Ｙｅｓ）には、視聴順序グラフ処理部１１１は、自己及び／又は過去に戻る遷移を省略した後に（＃１３）、処理＃１４を実行する。
【００４５】
この処理＃１３における自己に戻る遷移の省略は、処理＃１１で選択したレコードにおけるコンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子を、同レコードの遷移先コンテンツ要素識別子フィールド６３から削除することによって実行される。そして、この処理＃１３における過去に戻る遷移の省略は、自己の深さよりも小さい深さを持つコンテンツ要素のコンテンツ要素識別子を、処理＃１１で選択したレコードの遷移先コンテンツ要素識別子フィールド６３から削除することによって実行される。
【００４６】
このように視聴順序が自己に戻る遷移や過去に戻る遷移を省略することができるのは、受信装置２は、放送局１から受信したコンテンツ要素をバッファメモリに記憶しておくので、一旦コンテンツ要素を受信すると、このコンテンツ要素を任意の時間に再生することができるからである。
【００４７】
このように視聴順序が自己に戻る遷移や過去に戻る遷移を省略することによって、視聴順序グラフを簡単化することができ、後述のコンテンツ要素の配信順序をスケジューリングする際に、処理が容易となる。
【００４８】
処理＃１４において、視聴順序グラフ処理部１１１は、選択型コンテンツ情報の中に、この省略の処理を実行していない未処理のコンテンツ要素があるか否かを判断する。この判断の結果、未処理のコンテンツ要素がある場合（Ｙｅｓ）には、視聴順序グラフ処理部１１１は、次の未処理のコンテンツ要素に対し省略の処理を実行すべく、処理を処理＃１１に戻し、一方、未処理のコンテンツ要素がない場合（Ｎｏ）には、視聴順序グラフ処理部１１１は、次の結合の処理を実行すべく、処理＃１５を実行する。
【００４９】
処理＃１５において、視聴順序グラフ処理部１１１は、処理＃１１と同様に、記憶部１２の選択型コンテンツ情報記憶部１２１に記憶されている選択型コンテンツ情報の中から結合処理の対象とするコンテンツ要素を選定する。
【００５０】
次に、視聴順序グラフ処理部１１１は、視聴順序が分岐しないか否かを判断する（＃１６）。この判断は、例えば、処理＃１５で選択したレコードにおける遷移先コンテンツ要素識別子フィールド６３に１個のコンテンツ要素識別子が登録されているか否かによって実行することができる。遷移先コンテンツ要素識別子フィールド６３に１個のコンテンツ要素識別子が登録されている場合には視聴順序が分岐しないと判断する。
【００５１】
処理＃１６における判断の結果、視聴順序が分岐しない場合ではない場合（Ｎｏ）には、視聴順序グラフ処理部１１１は、処理＃１８を実行し、一方、視聴順序が分岐しない場合（Ｙｅｓ）には、視聴順序グラフ処理部１１１は、コンテンツ要素を結合する結合処理（＃１７）を実行した後に、処理＃１８を実行する。
【００５２】
この結合処理では、例えば、視聴順序グラフ処理部１１１は、まず、処理＃１５で選択したレコードにおける遷移先コンテンツ要素識別子フィールド６３に登録されているコンテンツ要素識別子をコンテンツ要素識別子フィールド６１に登録しているレコードを検索し、この検索したレコードにおける遷移先コンテンツ要素識別子フィールド６３に登録されているコンテンツ要素識別子で、処理＃１５で選択したレコードにおける遷移先コンテンツ要素識別子フィールド６３に登録されているコンテンツ要素識別子を置き換える。次に、視聴順序グラフ処理部１１１は、処理＃１５で選択したレコードにおける再生時間フィールド６２に登録されている再生時間に、この検索したレコードにおける再生時間フィールド６２に登録されている再生時間を足し合わせると共に、処理＃１５で選択したレコードにおけるコンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子、及び、この検索したレコードにおけるコンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子にそれぞれ対応するコンテンツ要素のデータを記憶部１２の選択型コンテンツ記憶部１２２に記憶されているコンテンツ要素から検索し、これら検索したコンテンツ要素のデータを視聴順序に従って結合する。そして、視聴順序グラフ処理部１１１は、この検索したレコードを選択型コンテンツ情報テーブル６０から削除する。
【００５３】
このように結合処理を実行することによって、視聴順序が分岐しないコンテンツ要素が遷移先のコンテンツ要素と一体にされる。このため、視聴順序グラフが簡単になり、後述のコンテンツ要素の配信順序をスケジューリングする際に、処理が容易となる。
【００５４】
そして、処理＃１８において、視聴順序グラフ処理部１１１は、選択型コンテンツ情報の中に、この結合処理を実行していない未処理のコンテンツ要素があるか否かを判断する。この判断の結果、未処理のコンテンツ要素がある場合（Ｙｅｓ）には、視聴順序グラフ処理部１１１は、次の未処理のコンテンツ要素に対し結合処理を実行すべく、処理を処理＃１５に戻し、一方、未処理のコンテンツ要素がない場合（Ｎｏ）には、視聴順序グラフ処理部１１１は、この省略及び結合の各処理を終了する。
【００５５】
このように視聴順序グラフ処理部１１１が処理＃１１乃至処理＃１８を実行することによって、上記処理＃１２の条件を満たすコンテンツ要素の遷移が省略され、上記処理＃１６の条件を満たすコンテンツ要素が結合されることによって、視聴順序グラフが簡単化される。
【００５６】
より具体的に説明すると、例えば、図６（Ａ）の左側に示すように、クイズを提示するコンテンツ要素Ｓａと、回答者に回答を促す旨を提示するコンテンツ要素Ｓｂと、正解を提示するコンテンツ要素Ｓｃと、不正解を提示するコンテンツ要素Ｓｄとを備え、視聴順序がコンテンツ要素Ｓａからコンテンツ要素Ｓｂに遷移し、視聴順序がコンテンツ要素Ｓｂからコンテンツ要素Ｓｂ、Ｓｃ及びＳｄの何れか１つのコンテンツ要素に遷移し、コンテンツ要素Ｓｃ及びＳｄの遷移先がない二者択一クイズ番組の選択型コンテンツの場合、選択型コンテンツ情報テーブル６０−１は、図６（Ａ）の右側に示すように、コンテンツ要素識別子フィールド６１にＳａ；Ｓｂ；Ｓｃ；Ｓｄを登録する各レコードにおいて、再生時間フィールド６２には１分；１分；４分；４分がそれぞれ登録され、遷移先コンテンツ要素識別子フィールド６３にはＳｂ；Ｓｂ、Ｓｃ、Ｓｄ；ＥＮＤ；ＥＮＤがそれぞれ登録される。
【００５７】
図６（Ａ）に示す視聴順序グラフに対し、まず、図５に示す上記の省略処理を実行すると、処理＃１１で選択型コンテンツ情報テーブル６０−１の２番目のレコード（コンテンツ要素識別子フィールド６１にＳｂを登録するレコード）が選定された場合に、コンテンツ要素識別子フィールド６１に登録されているＳｂが遷移先コンテンツ要素識別子フィールド６３にも登録されているので、処理＃１２の判断で、視聴順序が自己に戻り得るコンテンツ要素であると判断され、処理＃１３でこのレコードにおける遷移先コンテンツ要素識別子フィールド６３からＳｂが削除される。
【００５８】
この遷移の省略処理が完了すると、図６（Ａ）に示す視聴順序グラフは、図６（Ｂ）に示すものとなる。即ち、視聴順序がコンテンツ要素Ｓａからコンテンツ要素Ｓｂに遷移し、視聴順序がコンテンツ要素Ｓｂからコンテンツ要素Ｓｃ又はＳｄに遷移し、コンテンツ要素Ｓｃ及びＳｄの遷移先がない二者択一クイズ番組の選択型コンテンツとなって、選択型コンテンツ情報テーブル６０−２は、図６（Ｂ）の右側に示すように、コンテンツ要素識別子フィールド６１にＳａ；Ｓｂ；Ｓｃ；Ｓｄを登録する各レコードにおいて、再生時間フィールド６２には１分；１分；４分；４分がそれぞれ登録され、遷移先コンテンツ要素識別子フィールド６３にはＳｂ；Ｓｃ、Ｓｄ；ＥＮＤ；ＥＮＤがそれぞれ登録される。
【００５９】
次に、図６（Ｂ）に示す視聴順序グラフに対し図５に示す上記の結合処理を実行すると、処理＃１５で選択型コンテンツ情報テーブル６０−２の１番目のレコード（コンテンツ要素識別子フィールド６１にＳａを登録するレコード）が選定された場合に、コンテンツ要素識別子フィールド６１にはＳｂのみ登録されているので、処理＃１６の判断で、視聴順序が分岐しないコンテンツ要素であると判断され、処理＃１７でコンテンツ要素の結合処理が為される。即ち、視聴順序グラフ処理部１１１は、まず、処理＃１５で選択したレコード（１番目のレコード）における遷移先コンテンツ要素識別子フィールド６３に登録されているＳｂをコンテンツ要素識別子フィールド６１に登録しているレコード（２番目のレコード）を検索し、この検索した２番目のレコードにおける遷移先コンテンツ要素識別子フィールド６３に登録されているＳｃ、Ｓｄで、処理＃１５で選択した１番目のレコードにおける遷移先コンテンツ要素識別子フィールド６３に登録されているＳｂを置き換える。次に、視聴順序グラフ処理部１１１は、処理＃１５で選択した１番目のレコードにおける再生時間フィールド６２に登録されている再生時間１分に、この検索した２番目のレコードにおける再生時間フィールド６２に登録されている再生時間１分を足し合わせて２分とすると共に、処理＃１５で選択した１番目のレコードにおけるコンテンツ要素識別子フィールド６１に登録されているＳａ、及び、この検索した２番目のレコードにおけるコンテンツ要素識別子フィールド６１に登録されているＳｂにそれぞれ対応するコンテンツ要素のデータを記憶部１２の選択型コンテンツ記憶部１２２に記憶されているコンテンツ要素から検索し、これら検索したコンテンツ要素のデータを視聴順序に従って結合する。そして、視聴順序グラフ処理部１１１は、この検索した２番目のレコードを選択型コンテンツ情報テーブル６０−２から削除し、処理＃１５で選択した１番目のレコードにおけるコンテンツ要素識別子フィールド６１に登録されているＳａをＳａ’に置き換える。コンテンツ要素識別子がＳａ’であるコンテンツ要素は、コンテンツ要素Ｓａのデータとコンテンツ要素Ｓｂのデータとを視聴順序に従って結合したものである。なお、この置き換えを行うことなく、Ｓａのままでもよい。
【００６０】
このコンテンツ要素の結合処理が完了すると、図６（Ｂ）に示す視聴順序グラフは、図６（Ｃ）に示すものとなる。即ち、視聴順序がコンテンツ要素Ｓａ’からコンテンツ要素Ｓｃ又はＳｄに遷移し、コンテンツ要素Ｓｃ及びＳｄの遷移先がない二者択一クイズ番組の選択型コンテンツとなって、選択型コンテンツ情報テーブル６０−３は、図６（Ｃ）の右側に示すように、コンテンツ要素識別子フィールド６１にＳａ’；Ｓｃ；Ｓｄを登録する各レコードにおいて、再生時間フィールド６２には２分；４分；４分がそれぞれ登録され、遷移先コンテンツ要素識別子フィールド６３にはＳｃ、Ｓｄ；ＥＮＤ；ＥＮＤがそれぞれ登録される。
【００６１】
このように図５に示す上記の省略及び結合の各処理を実行することにより、図６（Ａ）に示す視聴順序グラフは、図６（Ｃ）に示す視聴順序グラフに簡単化される。
【００６２】
次に、視聴順序グラフの分割の処理について説明する。図７は、視聴順序グラフの分割の処理を実行する際における視聴順序グラフ処理部の動作を示すフローチャートである。図８は、視聴順序グラフの分割の処理を説明するための図である。図８（Ａ）及び（Ｂ）の各左側には、視聴順序グラフを示し、各右側には、左側の視聴順序グラフに対応する選択型コンテンツ情報テーブルを示す。
【００６３】
図７において、視聴順序グラフの分割処理を実行する際に、情報処理部１１の視聴順序グラフ処理部１１１は、まず、記憶部１２の選択型コンテンツ情報記憶部１２１に記憶されている選択型コンテンツ情報に基づいてコンテンツ要素の最小再生時間を探索し、取得する（＃２１）。より具体的には、本実施形態では、例えば、視聴順序グラフ処理部１１１は、選択型コンテンツ情報テーブル６０の各レコードにおいて、再生時間フィールド６２に登録されている再生時間を相互に比較し、最小値を見つけ出し、取得する。
【００６４】
次に、視聴順序グラフ処理部１１１は、上述の処理＃１１と同様に、記憶部１２の選択型コンテンツ情報記憶部１２１に記憶されている選択型コンテンツ情報の中から分割処理の対象とするコンテンツ要素を選定する（＃２２）。
【００６５】
次に、視聴順序グラフ処理部１１１は、処理＃２２で選択したレコードにおける再生時間フィールド６２に登録されている再生時間と、処理＃２１で取得した最小再生時間とを比較することによって、この再生時間フィールド６２に登録されている再生時間が、この取得した最小再生時間を超えているか否かを判断する（＃２３）。
【００６６】
この処理＃２３における判断の結果、この再生時間フィールド６２に登録されている再生時間が、この取得した最小再生時間を超えていない場合（Ｎｏ）には、視聴順序グラフ処理部１１１は、処理＃２５を実行し、一方、この再生時間フィールド６２に登録されている再生時間が、この取得した最小再生時間を超えている場合（Ｙｅｓ）には、視聴順序グラフ処理部１１１は、コンテンツ要素を分割する分割処理（＃２４）を実行した後に、処理＃２５を実行する。
【００６７】
この分割処理では、例えば、視聴順序グラフ処理部１１１は、まず、処理＃２２で選択したレコードにおける再生時間フィールド６２に登録されている再生時間を最小再生時間で割って、その商の数から１だけ引いた個数のレコードを選択型コンテンツ情報テーブル６０に追加する。次に、視聴順序グラフ処理部１１１は、処理＃２２で選択したレコードのコンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子を一時的に保持し、処理＃２２で選択したレコード及びこの追加したレコードにおけるコンテンツ要素識別子フィールド６１にそれぞれ新たに生成したコンテンツ要素識別子を登録する。なお、処理＃２２で選択したレコードのコンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子は、そのままでもよく、この場合、上記の保持は必要としない。次に、視聴順序グラフ処理部１１１は、処理＃２２で選択したレコード及びこの追加したレコードにおける再生時間フィールド６２にそれぞれ最小再生時間を登録する。次に、視聴順序グラフ処理部１１１は、処理＃２２で選択したレコード及びこの追加したレコードにおける遷移先コンテンツ要素識別子フィールド６３にそれぞれ視聴順序に従って遷移先のコンテンツ要素識別子を登録する。そして、上記で保持している処理＃２２で選択したレコードにおけるコンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子に対応するコンテンツ要素のデータを記憶部１２の選択型コンテンツ記憶部１２２に記憶されているコンテンツ要素から検索し、これら検索したコンテンツ要素のデータを最小再生時間で分割し、これら分割したコンテンツ要素のデータに上記の新たに作成したコンテンツ要素識別子を視聴順序に従って対応付けて選択型コンテンツ記憶部１２２に記憶する。
【００６８】
そして、処理＃２５において、視聴順序グラフ処理部１１１は、選択型コンテンツ情報の中に、この分割処理を実行していない未処理のコンテンツ要素があるか否かを判断する。この判断の結果、未処理のコンテンツ要素がある場合（Ｙｅｓ）には、視聴順序グラフ処理部１１１は、次の未処理のコンテンツ要素に対し分割処理を実行すべく、処理を処理＃２２に戻し、一方、未処理のコンテンツ要素がない場合（Ｎｏ）には、視聴順序グラフ処理部１１１は、この分割処理を終了する。
【００６９】
このように視聴順序グラフ処理部１１１が処理＃２１乃至処理＃２５の分割処理を実行することによって、選択型コンテンツを構成する各コンテンツ要素の再生時間が同一とされ、後述の配信順序計画処理が簡単化される。
【００７０】
より具体的に説明すると、例えば、図８（Ａ）の左側に示すように、６個のコンテンツ要素Ｓｈ乃至Ｓｍを備え、視聴順序がコンテンツ要素Ｓｈからコンテンツ要素Ｓｉ又はＳｊに遷移し、視聴順序がコンテンツ要素Ｓｉからコンテンツ要素Ｓｋ又はＳｌに遷移し、コンテンツ要素Ｓｊからコンテンツ要素Ｓｍに遷移し、コンテンツ要素Ｓｋ、Ｓｌ及びＳｍの遷移先がない選択型コンテンツの場合、選択型コンテンツ情報テーブル６０−４は、図８（Ａ）の右側に示すように、コンテンツ要素識別子フィールド６１にＳｈ；Ｓｉ；Ｓｊ；Ｓｋ；Ｓｌ；Ｓｍを登録する各レコードにおいて、再生時間フィールド６２には２分；２分；４分；２分；２分；２分がそれぞれ登録され、遷移先コンテンツ要素識別子フィールド６３にはＳｉ、Ｓｊ；Ｓｋ、Ｓｌ；Ｓｍ；ＥＮＤ；ＥＮＤ；ＥＮＤがそれぞれ登録される。
【００７１】
図８（Ａ）に示す視聴順序グラフに対し、図７に示す上記の分割処理を実行すると、処理Ｓ２１で最小再生時間が２分と探索、取得され、選択型コンテンツ情報テーブル６０−４の３番目のレコード（コンテンツ要素識別子フィールド６１にＳｊを登録するレコード）が選定された場合に、再生時間フィールド６２に登録されている４分が最小再生時間を超えているので、処理＃２３の判断で、再生時間が最小再生時間を超えていると判断され、処理＃２４でこのレコードが分割処理される。
【００７２】
即ち、この分割処理では、図８（Ｂ）に示すように、例えば、視聴順序グラフ処理部１１１は、まず、処理＃２２で選択した３番目のレコードにおける再生時間フィールド６２に登録されている再生時間を最小再生時間で割って、その商である２から１を引いた１個のレコードを選択型コンテンツ情報テーブル６０−４に追加する。次に、視聴順序グラフ処理部１１１は、処理＃２２で選択したレコードのコンテンツ要素識別子フィールド６１に登録されているＳｊを一時的に保持し、処理＃２２で選択した３番目のレコード及びこの追加した４番目のレコードにおけるコンテンツ要素識別子フィールド６１にそれぞれ新たに生成したＳｊ１、Ｓｊ２を登録する。次に、視聴順序グラフ処理部１１１は、処理＃２２で選択した３番目のレコード及びこの追加した４番目のレコードにおける再生時間フィールド６２にそれぞれ最小再生時間２分を登録する。次に、視聴順序グラフ処理部１１１は、処理＃２２で選択したレコードにおける遷移先コンテンツ要素識別子フィールド６３に視聴順序に基づき遷移先のＳｊ２を登録し、この追加した４番目のレコードにおける遷移先コンテンツ要素識別子フィールド６３に視聴順序に基づき遷移先のＳｍを登録する。そして、上記で保持している処理＃２２で選択したレコードにおけるコンテンツ要素識別子フィールド６１に登録されているコンテンツ要素識別子に対応するコンテンツ要素のデータを記憶部１２の選択型コンテンツ記憶部１２２に記憶されているコンテンツ要素から検索し、これら検索したコンテンツ要素のデータを最小再生時間２分で分割し、これら分割したコンテンツ要素のデータに上記の新たに作成したＳｊ１及びＳｊ２を視聴順序に従って対応付けて選択型コンテンツ記憶部１２２に記憶する。
【００７３】
このコンテンツ要素の分割処理が完了すると、図８（Ａ）に示す視聴順序グラフは、図８（Ｂ）に示すものとなる。即ち、７個のコンテンツ要素Ｓｈ〜コンテンツ要素Ｓｍを備え、視聴順序がコンテンツ要素Ｓｈからコンテンツ要素Ｓｉ又はＳｊ１に遷移し、視聴順序がコンテンツ要素Ｓｉからコンテンツ要素Ｓｋ又はＳｌに遷移し、コンテンツ要素Ｓｊ１からコンテンツ要素Ｓｊ２に遷移し、コンテンツ要素Ｓｊ２からコンテンツ要素Ｓｍに遷移し、コンテンツ要素Ｓｋ、Ｓｌ及びＳｍの遷移先がない選択型コンテンツとなって、選択型コンテンツ情報テーブル６０−５は、図８（Ｂ）の右側に示すように、コンテンツ要素識別子フィールド６１にＳｈ；Ｓｉ；Ｓｊ１；Ｓｊ２；Ｓｋ；Ｓｌ；Ｓｍを登録する各レコードにおいて、再生時間フィールド６２には２分；２分；２分；２分；２分；２分；２分がそれぞれ登録され、遷移先コンテンツ要素識別子フィールド６３にはＳｉ、Ｓｊ１；Ｓｋ、Ｓｌ；Ｓｊ２；Ｓｍ；ＥＮＤ；ＥＮＤ；ＥＮＤがそれぞれ登録される。
【００７４】
次に、配信順序計画処理について説明する。図９は、配信順序計画処理部の動作を示すフローチャートである。図１０は、配信順序計画処理の初期処理を実行する際における配信順序計画処理部の動作を示すフローチャートである。図１１は、視聴順序グラフを示す図である。図１２は、配信順序計画処理を説明するための図である。図１２（Ａ）は、チャネルＣ１におけるコンテンツ要素のデータの配信順序を示し、図１２（Ｂ）は、途中のチャネルＣ１及びＣ２におけるコンテンツ要素のデータの配信順序を示し、図１２（Ｃ）は、チャネルＣ１及びＣ２におけるコンテンツ要素のデータの配信順序を示し、図１２（Ｄ）は、配信順序計画処理後における、チャネルＣ１乃至Ｃ３におけるコンテンツ要素のデータの配信順序を示す。そして、図１２（Ｅ）に放送時刻の到来に合わせて各コンテンツ要素を配信する場合の各チャネル及び各コンテンツ要素のデータの配信順序を示す。
【００７５】
図９において、情報処理部１１の配信順序計画処理部１１２は、周知の幅優先探索法や深さ優先探索法等によって、多分木（ツリー構造）で表現された選択型コンテンツの視聴順序グラフにおける根からの深さを各コンテンツ要素についてそれぞれ探索し、取得する（＃３１）。
【００７６】
次に、配信順序計画処理部１１２は、変数の初期処理を実行する（＃３２）。
【００７７】
この変数の初期処理について図１０を用いてより詳細に説明する。ここで、総数変数ｎは、選択型コンテンツを構成するコンテンツ要素の総数を表し、個数変数ｐＸは、視聴順序Ｘにおけるコンテンツ要素の個数を表し、コンテンツ要素集合ＰＸは、視聴順序Ｘにおけるコンテンツ要素の集合を表し、深さ変数ｊは、多分木の視聴順序グラフにおけるコンテンツ要素の深さを表し、等深度コンテンツ要素集合Ｒｙは、深さ変数ｊ＝ｙ（深さｙ）にあるコンテンツ要素の集合を表す。使用チャネル変数ｍは、選択型コンテンツを配信する際に使用するチャネル総数を表し、チャネル番号変数ｉは、チャネルの番号を表し、チャネルＣＸは、番号Ｘのチャネルを表す。割当て済みコンテンツ要素個数変数ｋは、スケジューリング中のチャネルにおける配信を割り当てられたコンテンツ要素の個数を表し、計画コンテンツ要素変数ｌは、等深度コンテンツ要素集合ＲＸからスケジューリングするコンテンツ要素の個数を表す。
【００７８】
図１０において、配信順序計画処理部１１２は、まず、視聴順序グラフの根から葉への一の視聴順序を主順序Ｍとして選定する（＃３２１）。このように配信順序計画処理部は、選択部としても機能し選択部の一例でもある。
【００７９】
次に、配信順序計画処理部１１２は、主順序Ｍのコンテンツ要素の集合をコンテンツ要素集合ＰＭに代入する（＃３２２）。次に、配信順序計画処理部１１２は、コンテンツ要素集合ＰＭにおけるコンテンツ要素の個数を個数変数ｐＭに代入する（＃３２２）。
【００８０】
次に、配信順序計画処理部１１２は、視聴順序グラフのコンテンツ要素の総数（選択型コンテンツを構成するコンテンツ要素の総数）を総数変数ｎに代入する（＃３２４）。次に、配信順序計画処理部１１２は、総数変数ｎを個数変数ｐＭで割って、求めた商の小数点以下を繰り上げ、この繰り上げた整数値を使用チャネル変数ｍに代入し、使用チャネル変数ｍ個のチャネルを選択型コンテンツ要素を配信するために使用する使用チャネルに設定する（＃３２５）。このように配信順序計画処理部は、使用チャネル設定部としても機能し使用チャネル設定部の一例でもある。
【００８１】
次に、配信順序計画処理部１１２は、チャネルＣ１、Ｃ２、・・・、Ｃｍ−１の帯域幅を再生レートと等しくする（＃３２６）。このように配信順序計画処理部は、帯域幅設定部としても機能し帯域幅設定部の一例でもある。次に、配信順序計画処理部１１２は、視聴順序グラフの深さｊにあるコンテンツ要素の集合を等深度コンテンツ要素集合Ｒｊに代入する（＃３２７）。このように配信順序計画処理部１１２が動作することによって変数の初期処理が実行される。
【００８２】
図９に戻って、配信順序計画処理部１１２は、主順序Ｍのコンテンツ要素集合ＰＭにおける各コンテンツ要素を根から葉へ順に、即ち、視聴順序に従って、チャネルＣ１に割り当てることによって、主順序Ｍのコンテンツ要素をスケジューリングする（＃３３）。このように配信順序計画処理部は、第１割当部としても機能し第１割当部の一例でもある。
【００８３】
次に、配信順序計画処理部１１２は、上記処理＃３３でスケジューリングしたコンテンツ要素を等深度コンテンツ要素集合Ｒｊから削除する（＃３４）。
【００８４】
次に、処理＃３３及び＃３４でチャネルＣ１の配信順序がスケジューリングされたので、次番号のチャネルＣ２の配信順序をスケジューリングすべく、配信順序計画処理部１１２は、チャネル番号変数ｉに２を代入し、チャネル番号変数ｉを更新する（＃３５）。次に、処理＃３３及び＃３４でチャネルＣ１に主順序Ｍがスケジューリングされ、深さ１のコンテンツ要素Ｓ１がスケジューリングされたので、次の深さ、即ち、深さ２のコンテンツ要素をスケジューリングすべく、配信順序計画処理部１１２は、チャネルＣｉへ割り当てる対象となるコンテンツ要素の深さを示す深さ変数ｊに２を代入すると共に、チャネルＣｉにおける割当て済みコンテンツ要素個数変数ｋに０を代入する（＃３６）。
【００８５】
次に、配信順序計画処理部１１２は、等深度コンテンツ要素集合Ｒｊからスケジューリングするコンテンツ要素の個数を示す計画コンテンツ要素変数ｌ＝ｍｉｎ（ｐＭ−ｋ、ｊ−ｋ、（等深度コンテンツ要素集合Ｒｊの要素数））個のコンテンツ要素をチャネルＣｉに割り当てることによって、スケジューリングする（＃３７）。ここで、関数ｍｉｎは、引数のうちの最小の引数を出力する関数であり、例えば、引数がｘ、ｙ、ｚでこれらのうちで最小がｘの場合では、ｍｉｎ（ｘ、ｙ、ｚ）＝ｘとなる。
【００８６】
次に、配信順序計画処理部１１２は、上記処理＃３７でスケジューリングしたコンテンツ要素を等深度コンテンツ要素集合Ｒｊから削除する（＃３８）。
【００８７】
次に、配信順序計画処理部１１２は、上記処理＃３７でスケジューリングしたコンテンツ要素の個数、即ち、計画コンテンツ要素変数ｌを割当て済みコンテンツ要素個数変数ｋに加算することによって、新たな割当て済みコンテンツ要素個数変数ｋの値とする（＃３９）。
【００８８】
次に、配信順序計画処理部１１２は、ｊ＜ｐＭであるか否かを判断する（＃４０）。この処理＃４０における判断の結果、ｊ＜ｐＭである場合（Ｙｅｓ）には、配信順序計画処理部１１２は、深さ変数ｊに１を加算することによって、新たな深さ変数ｊの値とした後に（＃４１）、処理を処理＃３７に戻す。一方、処理＃４０における判断の結果、ｊ＜ｐＭではない場合（Ｎｏ）には、配信順序計画処理部１１２は、チャネル番号変数ｉに１を加算することによって、新たなチャネル番号変数ｉの値とする（＃４２）。
【００８９】
次に、配信順序計画処理部１１２は、配信順序をスケジューリングしていないチャネルＣがあるか否かを判断すべく、ｉ≦ｍであるか否かを判断する（＃４３）。この処理＃４３における判断の結果、ｉ≦ｍである場合（Ｙｅｓ）には、配信順序をスケジューリングしていないチャネルＣがあると判断され、配信順序計画処理部１１２は、処理を処理＃３６に戻し、一方、ｉ≦ｍではない場合（Ｎｏ）には、配信順序をスケジューリングしていないチャネルＣがないと判断され、配信順序計画処理部１１２は、チャネルＣｍの帯域幅ｂｍを式１により算出し（＃４４）、配信順序計画処理を終了する。
【００９０】
【数１】
2007067602.tif 000003
【００９１】
ここで、関数ｍａｘは、引数のうちの最大の引数を出力する関数であり、例えば、引数がｘ、ｙ、ｚでこれらのうちで最大がｚの場合では、ｍａｘ（ｘ、ｙ、ｚ）＝ｚとなる。
【００９２】
これら処理＃３５乃至処理＃４３のように動作することによって、配信順序計画処理部は、第２及び第３割当部としても機能し第２及び第３割当部の一例でもある。特に、処理＃４３でｉ＝ｍと判断された場合における処理＃３５乃至処理＃４０のように動作する配信順序計画処理部は、第３割当部として機能している。
【００９３】
配信順序計画処理が終了すると、配信処理部１１３は、配信順序計画処理部１１２によってスケジューリングされた配信順序に従って選択型コンテンツの各コンテンツ要素を各チャネルから送信データ生成部１３及び送信部１４を用いて配信する。
【００９４】
このように配信順序計画処理部１１２が動作することによって、記憶部１２の選択型コンテンツ記憶部１２２に記憶されている選択型コンテンツの各コンテンツ要素に対する配信順序がスケジューリングされ、当該コンテンツ要素が視聴され得る時刻までに放送局１から受信装置２へ配信可能となると共に、配信に使用される帯域幅が抑制される。この帯域幅ＢＷは、再生レートをｒとすると、式２により与えられる。
【００９５】
【数２】
2007067602.tif 000004
【００９６】
より具体的に説明すると、例えば、図１１に示すように、１０個のコンテンツ要素Ｓ１〜Ｓ１０を備え、視聴順序がコンテンツ要素Ｓ１からコンテンツ要素Ｓ２、Ｓ３及びＳ４のうちの何れかに遷移し、視聴順序がコンテンツ要素Ｓ２からコンテンツ要素Ｓ５に遷移し、視聴順序がコンテンツ要素Ｓ３からコンテンツ要素Ｓ６又はＳ７に遷移し、視聴順序がコンテンツ要素Ｓ５からコンテンツ要素Ｓ８又はＳ９に遷移し、コンテンツ要素Ｓ７からコンテンツ要素Ｓ１０に遷移し、コンテンツ要素Ｓ４、Ｓ６、Ｓ８、Ｓ９及びＳ１０の遷移先がない選択型コンテンツの場合、選択型コンテンツ情報テーブル６０は、図４に示すように、コンテンツ要素識別子フィールド６１にＳ１；Ｓ２；Ｓ３；Ｓ４；Ｓ５；Ｓ６；Ｓ７；Ｓ８；Ｓ９；Ｓ１０を登録する各レコードにおいて、再生時間フィールド６２には３分；３分；３分；３分；３分；３分；３分；３分；３分；３分がそれぞれ登録され、遷移先コンテンツ要素識別子フィールド６３にはＳ１、Ｓ２、Ｓ３；Ｓ５；Ｓ６、Ｓ７；ＥＮＤ；Ｓ８、Ｓ９；ＥＮＤ；Ｓ１０；ＥＮＤ；ＥＮＤ；ＥＮＤがそれぞれ登録される。
【００９７】
図１１に示す視聴順序グラフに対し、図９及び図１０に示す上記の配信順序計画処理が実行されると、まず、処理＃３１で深さ探索が実行され、図１１に示す多分木で表現された視聴順序グラフの場合、根のコンテンツ要素Ｓ１が深さ１と判断され、コンテンツ要素Ｓ１の遷移先であるコンテンツ要素Ｓ２、Ｓ３及びＳ４が深さ２と判断され、コンテンツ要素Ｓ２の遷移先であるコンテンツ要素Ｓ５が深さ３と判断されると共に、コンテンツ要素Ｓ３の遷移先であるコンテンツ要素Ｓ６及びＳ７が深さ３と判断され、そして、コンテンツ要素Ｓ５の遷移先である葉のコンテンツ要素Ｓ８及びＳ９が深さ４と判断されると共に、コンテンツ要素Ｓ７の遷移先である葉のコンテンツ要素Ｓ１０が深さ４と判断される。
【００９８】
そして、各コンテンツ要素Ｓ１〜Ｓ１０におけるこれら各深さが選択型コンテンツ情報テーブル６０の深さフィールド６４にそれぞれ登録される。図１１及び図４に示す例では、選択型コンテンツ情報テーブル６０は、コンテンツ要素識別子フィールド６１にＳ１；Ｓ２；Ｓ３；Ｓ４；Ｓ５；Ｓ６；Ｓ７；Ｓ８；Ｓ９；Ｓ１０を登録する各レコードにおいて、深さフィールド６４には１；２；２；２；３；３；３；４；４；４がそれぞれ登録される。
【００９９】
次に、処理＃３２が実行される。即ち、まず、処理＃３２１が実行され、視聴順序グラフの根から葉への一の視聴順序、例えば、根のコンテンツ要素Ｓ１からコンテンツ要素Ｓ２及びコンテンツ要素Ｓ５を介して葉のコンテンツ要素Ｓ８に至る視聴順序Ｐ１が主順序Ｍとして選定される。
【０１００】
次に、処理＃３２２が実行され、主順序Ｍ（＝１）のコンテンツ要素の集合｛Ｓ１、Ｓ２、Ｓ５、Ｓ８｝がコンテンツ要素集合ＰＭに代入され、ＰＭ＝｛Ｓ１、Ｓ２、Ｓ５、Ｓ８｝となる。次に、処理＃３２３が実行され、順序変数ＰＭにおけるコンテンツ要素の個数４が個数変数ｐＭに代入され、ｐＭ＝４となる。
【０１０１】
次に、処理＃３２４が実行され、視聴順序グラフのコンテンツ要素の総数１０が総数変数ｎに代入され、ｎ＝１０となる。次に、処理＃３２５が実行され、総数変数ｎ＝１０が個数変数ｐＭ＝４で除算され、求めた商２．５の小数点以下が繰り上げられ、この繰り上げられた整数値３が使用チャネル変数ｍに代入され、ｍ＝３となる。
【０１０２】
次に、処理＃３２６が実行され、使用チャネルＣ１及びＣ２の帯域幅が再生レート、例えば５Ｍｂｐｓと等しくされる。次に、処理＃３２７が実行され、視聴順序グラフの深さｊにあるコンテンツ要素の集合が等深度コンテンツ要素集合Ｒｊに代入される。即ち、深さｊ＝１〜４であり、各コンテンツ要素Ｓ１〜Ｓ１０の深さは、処理＃３１で求めた上記の如くであるから、Ｒ１＝｛Ｓ１｝、Ｒ２＝｛Ｓ２、Ｓ３、Ｓ４｝、Ｒ３＝｛Ｓ５、Ｓ６、Ｓ７｝、Ｒ４＝｛Ｓ８、Ｓ９、Ｓ１０｝となる。このように各変数が初期処理される。
【０１０３】
そして、処理＃３３が実行され、ＰＭ＝｛Ｓ１、Ｓ２、Ｓ５、Ｓ８｝の根であるコンテンツ要素Ｓ１から葉であるコンテンツ要素Ｓ８まで視聴順序の順にチャネルＣ１に割り当てられ、図１２（Ａ）に示すように、ＰＭの配信順序がスケジューリングされる。なお、図１２（Ａ）乃至（Ｅ）のＤ（ｘ）は、コンテンツ要素ｘのデータであることを示す。
【０１０４】
次に、処理＃３４が実行され、処理＃３３でスケジューリングしたコンテンツ要素がＲ１〜Ｒ４から削除される。即ち、コンテンツ要素Ｓ１、Ｓ２、Ｓ５及びＳ８がチャネルＣ１にスケジューリングされたので、Ｒ１＝｛φ｝、Ｒ２＝｛Ｓ３、Ｓ４｝、Ｒ３＝｛Ｓ６、Ｓ７｝、Ｒ４＝｛Ｓ９、Ｓ１０｝となる。なお、｛φ｝は、空集合であることを表す。
【０１０５】
次に、処理＃３５が実行され、処理＃３３及び＃３４でチャネル番号変数ｉ＝１である場合のチャネルＣ１の配信順序がスケジューリングされたので、次番号のチャネルであるチャネルＣ２の配信順序をスケジューリングすべく、チャネル番号変数ｉに２が代入される。次に、処理＃３６が実行され、深さ変数ｊに２が代入され、割当て済みコンテンツ要素個数変数ｋに０が代入される。
【０１０６】
次に、処理＃３７が実行され、Ｒ２から計画コンテンツ要素変数ｌ＝ｍｉｎ（４−０、２−０、２）＝２個のコンテンツ要素、例えばコンテンツ要素Ｓ３及びＳ４がチャネルＣ２に割り当てられ、図１２（Ｂ）に示すように、コンテンツ要素Ｓ３及びＳ４がスケジューリングされる。このように深さ２のコンテンツ要素Ｓ２、Ｓ３及びＳ４は、当該コンテンツ要素Ｓ２、Ｓ３及びＳ４が視聴され得る時刻までに放送局１から受信装置２へ放送可能となるように、スケジューリングされる。
【０１０７】
次に、処理＃３８が実行され、スケジューリングされたコンテンツ要素Ｓ３及びＳ４がＲ１〜Ｒ４から削除され、Ｒ１＝｛φ｝、Ｒ２＝｛φ｝、Ｒ３＝｛Ｓ６、Ｓ７｝、Ｒ４＝｛Ｓ９、Ｓ１０｝となる。
【０１０８】
次に、処理＃３９が実行され、割当て済みコンテンツ要素個数変数ｋに処理＃３８でスケジューリングしたコンテンツ要素の個数、即ち、計画コンテンツ要素変数ｌ＝２が加算され、割当て済みコンテンツ要素個数変数ｋ＝０＋２＝２となる。次に、処理＃４０が実行され、ｊ＜ｐＭであるか否かが判断される。ここでは、ｊ＝２でｐＭ＝４であるから、ｊ＜ｐＭであると判断され、処理＃４１が実行されて、深さ変数ｊに１が加算され、深さ変数ｊ＝２＋１＝３となって、処理＃３７に戻される。
【０１０９】
処理＃３７乃至＃３９が同様に実行されることで、Ｒ３から計画コンテンツ要素変数ｌ＝ｍｉｎ（４−２、３−２、２）＝１個のコンテンツ要素、例えばコンテンツ要素Ｓ６が図１２（Ｂ）に示すようにチャネルＣ２にスケジューリングされ、Ｒ１＝｛φ｝、Ｒ２＝｛φ｝、Ｒ３＝｛Ｓ７｝、Ｒ４＝｛Ｓ９、Ｓ１０｝となって、割当て済みコンテンツ要素個数変数ｋ＝２＋１＝３となる。
【０１１０】
次に、処理＃４０が実行され、ｊ＜ｐＭであるか否かが判断される。ここでは、ｊ＝３でｐＭ＝４であるから、ｊ＜ｐＭであると判断され、処理＃４１が実行されて、深さ変数ｊに１が加算され、深さ変数ｊ＝３＋１＝４となって、処理＃３７に戻される。
【０１１１】
処理＃３７乃至＃３９が同様に実行されることで、Ｒ４から計画コンテンツ要素変数ｌ＝ｍｉｎ（４−３、４−３、２）＝１個のコンテンツ要素、例えばコンテンツ要素Ｓ９が図１２（Ｃ）に示すようにチャネルＣ２にスケジューリングされ、Ｒ１＝｛φ｝、Ｒ２＝｛φ｝、Ｒ３＝｛Ｓ７｝、Ｒ４＝｛Ｓ１０｝となって、割当て済みコンテンツ要素個数変数ｋ＝３＋１＝４となる。
【０１１２】
次に、処理＃４０が実行され、ｊ＜ｐＭであるか否かが判断される。ここでは、ｊ＝４でｐＭ＝４であるから、ｊ＜ｐＭではないと判断される。即ち、チャネルＣ２の配信順序が完了されたと判断される。このため、処理＃４２が実行されて、チャネル番号変数ｉに１が加算され、チャネル番号変数ｉ＝２＋１＝３となる。これによって、次番号のチャネルであるチャネルＣ３の配信順序をスケジューリングする処理が以下のように実行される。
【０１１３】
次に、処理＃４３が実行され、ｉ≦ｍであるか否かが判断される。ここでは、ｉ＝２でｍ＝３であるから、ｉ≦ｍであると判断され、処理が処理＃３６に戻され、処理＃３６が実行されて、深さ変数ｊに２が代入され、変数ｋに０が代入される。
【０１１４】
処理＃３７が実行され、Ｒ２から計画コンテンツ要素変数ｌ＝ｍｉｎ（４−０、２−０、０）＝０個のコンテンツ要素がチャネルＣ２にスケジューリングされるが、計画コンテンツ要素変数ｌ＝ｍｉｎ（４−０、２−０、０）＝０個であるから、実際には、コンテンツ要素は、スケジューリングされない。このため、処理＃３８及び処理＃３９が実行されても、Ｒ１〜Ｒ４に変化はなく、Ｒ１＝｛φ｝、Ｒ２＝｛φ｝、Ｒ３＝｛Ｓ７｝、Ｒ４＝｛Ｓ１０｝であり、変数ｋ＝０＋０＝０のままである。
【０１１５】
次に、処理＃４０が実行され、ｊ＜ｐＭであるか否かが判断される。ここでは、ｊ＝２でｐＭ＝４であるから、ｊ＜ｐＭであると判断され、処理＃４１が実行されて、深さ変数ｊに１が加算され、深さ変数ｊ＝２＋１＝３となって、処理＃３７に戻される。
【０１１６】
処理＃３７が実行され、Ｒ３から計画コンテンツ要素変数ｌ＝ｍｉｎ（４−０、３−０、１）＝１個のコンテンツ要素、例えばコンテンツ要素Ｓ７が図１２（Ｄ）に示すようにチャネルＣ３にスケジューリングされ、Ｒ１＝｛φ｝、Ｒ２＝｛φ｝、Ｒ３＝｛φ｝、Ｒ４＝｛Ｓ１０｝となって、割当て済みコンテンツ要素個数変数ｋ＝０＋１＝１となる。
【０１１７】
次に、処理＃４０が実行され、ｊ＜ｐＭであるか否かが判断される。ここでは、ｊ＝３でｐＭ＝４であるから、ｊ＜ｐＭであると判断され、処理＃４１が実行されて、深さ変数ｊに１が加算され、深さ変数ｊ＝３＋１＝４となって、処理＃３７に戻される。
【０１１８】
処理＃３７が実行され、Ｒ４から計画コンテンツ要素変数ｌ＝ｍｉｎ（４−１、４−１、１）＝１個のコンテンツ要素、例えばコンテンツ要素Ｓ１０が図１２（Ｄ）に示すようにチャネルＣ３にスケジューリングされ、Ｒ１＝｛φ｝、Ｒ２＝｛φ｝、Ｒ３＝｛φ｝、Ｒ４＝｛φ｝となって、割当て済みコンテンツ要素個数変数ｋ＝１＋１＝２となる。
【０１１９】
次に、処理＃４０が実行され、ｊ＜ｐＭであるか否かが判断される。ここでは、ｊ＝４でｐＭ＝４であるから、ｊ＜ｐＭではないと判断され、処理＃４２が実行されて、チャネル番号変数ｉに１が加算され、チャネル番号変数ｉ＝３＋１＝４となる。
【０１２０】
次に、処理＃４３が実行され、ｉ≦ｍであるか否かが判断される。ここでは、ｉ＝４でｍ＝３であるから、ｉ≦ｍではないと判断され、処理＃４４が実行され、チャネルＣ３の帯域幅が式１により算出され、配信順序計画処理が終了する。
【０１２１】
図１１に示す視聴順序グラフの選択型コンテンツを放送する場合、本実施形態では、上記のように動作した結果、図１２（Ｄ）に示すように、チャネルＣ１は、帯域幅が５Ｍｂｐｓで放送時間が１２分間であり、配信順序がコンテンツ要素のデータＤ（Ｓ１）、Ｄ（Ｓ２）、Ｄ（Ｓ５）及びＤ（Ｓ８）の順に計画され、チャネルＣ２は、帯域幅が５Ｍｂｐｓで放送時間が１２分間であり、配信順序がコンテンツ要素のデータＤ（Ｓ３）、Ｄ（Ｓ４）、Ｄ（Ｓ６）及びＤ（Ｓ９）の順に計画され、そして、チャネルＣ３は、帯域幅が２．５Ｍｂｐｓで放送時間が１２分間であり、配信順序がコンテンツ要素のデータＤ（Ｓ７）及びＤ（Ｓ１０）の順に計画される。従って、図１１に示す視聴順序グラフの選択型コンテンツは、１２．５Ｍｂｐｓの帯域幅で放送することができる。
【０１２２】
一方、単純に、各コンテンツ要素Ｓ１〜Ｓ１０の放送時刻に合わせて各コンテンツ要素Ｓ１〜Ｓ１０のデータＤ（Ｓ１）〜Ｄ（Ｓ１０）を放送する場合には、図１２（Ｅ）に示すように、１５Ｍｂｐｓの帯域幅が必要となり、本実施形態の方が狭い帯域幅で放送することができる。
【０１２３】
図１３は、本発明の配信順序計画法と単純手法とにおける必要な帯域幅を示す図である。図１３に示す比較にあたって、視聴順序グラフは、出線数ｅの多分木である。ただし、コンテンツ要素の総個数を任意に与えられるように、葉より１つ浅い深さにあるコンテンツ要素の出線数は、ｅ以下になる場合がある。図１３の横軸は、選択型コンテンツのコンテンツ要素の総個数であり、その縦軸は、必要な帯域幅である。必要な帯域幅は、再生レートに比例するため、再生レートで除算した値である。●は、出線数ｅ＝１の視聴順序グラフに対し本発明の配信順序計画法を適用した場合の必要な帯域幅であり、▲は、出線数ｅ＝２の視聴順序グラフに対し本発明の配信順序計画法を適用した場合の必要な帯域幅であり、■は、出線数ｅ＝３の視聴順序グラフに対し本発明の配信順序計画法を適用した場合の必要な帯域幅であり、△は、出線数ｅ＝２の視聴順序グラフに対し単純手法を適用した場合の必要な帯域幅であり、そして、□は、出線数ｅ＝３の視聴順序グラフに対し単純手法を適用した場合の必要な帯域幅である。なお、●は、出線数ｅ＝１の視聴順序グラフに対し単純手法を適用した場合の必要な帯域幅でもある。また、本発明の配信順序計画法では、ｐＭ＝ｂ（ｂは、最大深さである。）となるように、主順序Ｍを選択した。
【０１２４】
本発明の配信順序計画法では視聴順序を考慮して効率的にコンテンツ要素の配信順序をスケジューリングしているので、図１３から分かるように、選択型コンテンツを放送するために必要な帯域幅は、本発明の配信順序計画法の方が、単純に、各コンテンツ要素の放送時刻に合わせて各コンテンツ要素のデータを放送する単純手法の場合に較べて、狭い。
【０１２５】
ここで、上述の具体例では、処理＃３２の処理＃３２１で、主順序Ｍとして、根のコンテンツ要素Ｓ１からコンテンツ要素Ｓ２及びコンテンツ要素Ｓ５を介して葉のコンテンツ要素Ｓ８に至る視聴順序Ｐ１が選択されたが、他の視聴順序を選択してもよい。例えば、主順序Ｍとして、根のコンテンツ要素Ｓ１からコンテンツ要素Ｓ３を介して葉のコンテンツ要素Ｓ６に至る視聴順序Ｐ２が選択されてもよい。
【０１２６】
図１４は、図１１に示す視聴順序グラフで他の視聴順序Ｐ２を主順序Ｍとして選択した場合における配信順序計画処理を説明するための図である。図１４（Ａ）は、図１１に示す視聴順序グラフにおける視聴順序Ｐ２を示し、図１４（Ｂ）は、配信順序計画処理後における、チャネルＣ１乃至Ｃ４におけるコンテンツ要素のデータの配信順序を示す。
【０１２７】
主順序Ｍとして視聴順序Ｐ２が選択され、処理＃３１乃至処理＃４４の各処理が実行されると、図１４（Ｂ）に示すように、チャネルＣ１は、帯域幅が５Ｍｂｐｓで放送時間が９分間であり、配信順序がコンテンツ要素のデータＤ（Ｓ１）、Ｄ（Ｓ３）及びＤ（Ｓ６）の順に計画され、チャネルＣ２は、帯域幅が５Ｍｂｐｓで放送時間が９分間であり、配信順序がコンテンツ要素のデータＤ（Ｓ２）、Ｄ（Ｓ４）及びＤ（Ｓ５）の順に計画され、チャネルＣ３は、帯域幅が５Ｍｂｐｓで放送時間が９分間であり、配信順序がコンテンツ要素のデータＤ（Ｓ７）、Ｄ（Ｓ８）及びＤ（Ｓ９）の順に計画され、そして、チャネルＣ４は、帯域幅が５／３Ｍｂｐｓで放送時間が９分間であり、コンテンツ要素のデータＤ（Ｓ１０）が放送されるように計画される。従って、図１１に示す視聴順序の選択型コンテンツは、主順序Ｍを視聴順序Ｐ２とすると、９分間で（１５＋５／３）Ｍｂｐｓの帯域幅で放送することができる。
【０１２８】
このように主順序Ｍに採用する視聴順序ＰＭによって、放送に必要な帯域幅と放送時間とが依存する。そのため、主順序Ｍに採用し得る全ての視聴順序に対して、図９及び図１０を用いて説明した配信順序計画処理を実行することによって、最も狭い帯域幅で放送し得る配信順序を探索することができ、そのような配信順序を採用することによって、放送に使用可能な帯域幅をより効率的に利用することができる。
【０１２９】
なお、上述の実施形態では、選択型コンテンツの配信に伴って選択型コンテンツの各コンテンツ要素の配信順序を配信順序計画処理部１１２がスケジューリングしたが、例えば、図４に破線で示すように、コンテンツ要素の配信順序を登録する配信順序フィールド６５を選択型コンテンツ情報テーブル６０にさらに設け、配信順序計画処理部１１２は、上述した処理＃３１乃至処理＃４４で選択型コンテンツの各コンテンツ要素の配信順序をスケジューリングした後に、各コンテンツ要素の配信順序を各コンテンツ要素の配信順序フィールド６５にそれぞれ登録するように構成してもよい。このように構成することによって、選択型コンテンツの配信に先立って選択型コンテンツの各コンテンツ要素の配信順序を予めスケジューリングすることができ、また、放送局（サーバ）１を、選択型コンテンツの各コンテンツ要素の配信順序をスケジューリングする機能と、選択型コンテンツを配信する機能とを別体の装置でそれぞれ構成することができる。
【０１３０】
また、上述の実施形態では、選択型コンテンツとしてクイズ番組を挙げたが、これに限定されるものではない。例えば、他の例を挙げると、選択型コンテンツには、ダイジェスト−ソースのコンテンツがある。このダイジェスト−ソースでは、複数のダイジェスト（要約）のコンテンツが提示され、その後、ユーザが一のダイジェストを選択すると、このユーザが選択したダイジェストに対応する要約前の元のコンテンツ（ソースのコンテンツ）が提示される。例えば、ニュース番組の場合では、幾つかのニュースの概要のコンテンツが提示され、その後、詳細を視聴したいと考えて、ユーザが一のニュースを選択すると、このユーザが選択したニュースの概要に対応する元のニュースのコンテンツが提示される。あるいは、例えば、通信販売番組の場合では、複数の商品を示すコンテンツ又は複数のＣＭのコンテンツが提示され、その後、ユーザが一の商品又はＣＭを選択すると、このユーザが選択した商品又はＣＭに対応するより詳細に商品を説明するコンテンツが提示される。このようにユーザの選択によってコンテンツの内容の展開が変わるものである。
【０１３１】
また他の例を挙げると、選択型コンテンツには、選択型ドラマのコンテンツがある。この選択型ドラマでは、登場人物の複数の行動のコンテンツが提示され、その後、ユーザが一の行動を選択すると、このユーザが選択した行動に対応するストーリのコンテンツが提示される。このようにユーザの選択によってドラマのストーリ展開が変わり、エンディングが変わるものである。
【図面の簡単な説明】
【０１３２】
【図１】本発明の原理を説明するための図である。
【図２】実施形態に係る配信システムの構成を示す図である。
【図３】放送局の構成を示すブロック図である。
【図４】選択型コンテンツ情報テーブルの構成を示す図である。
【図５】視聴順序グラフの省略及び結合の各処理を実行する際における視聴順序グラフ処理部の動作を示すフローチャートである。
【図６】視聴順序グラフの省略及び結合の各処理を説明するための図である。
【図７】視聴順序グラフの分割の処理を実行する際における視聴順序グラフ処理部の動作を示すフローチャートである。
【図８】視聴順序グラフの分割の処理を説明するための図である。
【図９】配信順序計画処理部の動作を示すフローチャートである。
【図１０】配信順序計画処理の初期処理を実行する際における配信順序計画処理部の動作を示すフローチャートである。
【図１１】視聴順序グラフを示す図である。
【図１２】配信順序計画処理を説明するための図である。
【図１３】本発明の配信順序計画法と単純手法とにおける必要な帯域幅を示す図である。
【図１４】図１１に示す視聴順序グラフで他の視聴順序Ｐ２を主順序Ｍとして選択した場合における配信順序計画処理を説明するための図である。
【符号の説明】
【０１３３】
１  放送局（サーバ）
２  受信装置
１１  情報処理部
１２  記憶部
１３  送信データ生成部
１４  送信部
６０、６０−１〜６０−５  選択型コンテンツ情報テーブル
６１  コンテンツ要素識別子フィールド
６２  再生時間フィールド
６３  遷移先コンテンツ要素識別子フィールド
６４  深さフィールド
６５  配信順序フィールド
１１１  視聴順序グラフ処理部
１１２  配信順序計画処理部
１１３  配信処理部
１２１  選択型コンテンツ情報記憶部
１２２  選択型コンテンツ記憶部
【図１】
2007067602.tif 000005
【図２】
2007067602.tif 000006
【図３】
2007067602.tif 000007
【図４】
2007067602.tif 000008
【図５】
2007067602.tif 000009
【図６】
2007067602.tif 000010
【図７】
2007067602.tif 000011
【図８】
2007067602.tif 000012
【図９】
2007067602.tif 000013
【図１０】
2007067602.tif 000014
【図１１】
2007067602.tif 000015
【図１２】
2007067602.tif 000016
【図１３】
2007067602.tif 000017
【図１４】
2007067602.tif 000018