(57)【特許請求の範囲】
【請求項１】
マルチメディアのデータがノードの単位でまとめられ関連あるノード同士がリンクで結合された構造を有し、前記リンクを辿りながら前記ノードのデータを探索するハイパーメディアの探索方法において、
前記各ノードについてそのノードと結合する全ての宛先ノードに対してそれぞれ探索の対象となる確率である探索確率の初期値を式（１）によりそれぞれ設定する初期値設定処理と、
ある前記ノードからある前記宛先ノードへ探索された時、そのノードと結合する全ての前記宛先ノードの探索確率を式（２）、（３）により更新する探索時更新処理と、
ある前記ノードからある前記宛先ノードへのリンクが追加された時、そのノードからの全ての前記宛先ノードの探索確率を式（４）、（５）により更新する追加時更新処理と、
ある前記ノードからある前記宛先ノードへのリンクが削除された時、そのノードからの全ての前記宛先ノードの探索確率を式（６）、（７）により更新する削除時更新処理と、
ある前記ノードが探索された時、そのノードからの前記宛先ノードへの前記探索確率の大きい１つまたは複数の前記宛先ノードのデータをあらかじめメモリ内にロードする予測ロード処理と、
ある前記ノードからある前記宛先ノードへ探索した時に、その宛先ノードのデータが前記予測ロード処理によって前記メモリにロードされているかどうかを判別する判別処理と、
前記予測ロード処理によりロードされていればロードされたデータの提示を行い、ロードされていなければその宛先ノードのデータを前記メモリ内にロードしてその宛先ノードのデータの提示を行う提示処理とを、
実行することを特徴とするハイパーメディアの探索方法。
Ｐ1 ＝Ｐ2 ＝Ｐ3 ＝…＝Ｐn ＝１／ｎ                    ・・・（１）
ここで、Ｐi （1=1,2,…，n)は、ノードからの宛先ノードへの探索確率であり、ｎはノードからの宛先ノードの数を表す。
Ｐk ＝αＰk ＋１−α                                  ・・・（２）
Ｐi ＝αＰi (i=1,2,…,n  ただしi ≠k )  ・・・（３）
ここで、Ｐk はあるノードからある宛先ノードへ探索された時の、そのノードからその宛先のノードへの探索確率であり、Ｐk （i ≠k)はその宛先ノードを除く宛先ノードへの探索確率であり、ｎはそのあるノードからの宛先ノードの数を表し、αは０＜α＜１なる定数である。
Ｐi ＝Ｐi （１−１／ｎ）   (i=1,2,…,n-1)  ・・・（４）
Ｐn ＝１／ｎ                                          ・・・（５）
ここで、Ｐn は、あるノードにリンクが追加された宛先ノードへの探索確率であり、Ｐi はそのノードにリンクが追加された宛先ノード以外の宛先ノードへの探索確率であり、ｎは追加された宛先ノードを含む宛先ノードの数である。
Ｐk ≠１のとき
Ｐi ＝Ｐi ／（１−Ｐk ）  （i=1,2,…，n ただしi ≠k)  ・・・（６）
Ｐk ＝１のとき
Ｐi ＝１／（ｎ−１）      （i=1,2,…，n ただしi ≠k)  ・・・（７）
ここで、Ｐk は、あるノードからリンクが削除された宛先ノードへの探索確率であり、Ｐi はそのノードからのリンクが削除された宛先ノード以外の宛先ノードへの探索確率であり、ｎはリンクが削除された宛先ノードを含む宛先ノードの数である。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、ハイパーメディアの探索方法に関するものである。
【０００２】
【従来の技術】
従来、このような分野の技術としては、例えば、次のような文献に記載されるものがあった。
文献；ＩＥＥＥ  ＣＯＭＰＵＴＥＲ、１９８８−１、（米）、N.Yankelovic          h,B.J.Haan,N.K.Meyrowitz,and S.M.Drucker著、"Intermedia:The Co          ncept and the Construction of a Seamless Information Environme          nt" 、Ｐ８１−９６
ハイパーメディアは、マルチメディアのデータがノードと呼ばれる単位でまとめられ、関連あるノード同士がリンクで結合された構造をしており、利用者はその中を主としてリンクを辿ること（以下、ナビゲーションと呼ぶ）によりデータを探索する。ナビゲーションの内部処理としては、前記文献に代表されるように、利用者があるノードの任意のリンクを選択し、ナビゲートコマンドを入力した時点で、システムが宛先のノードに相当するファイルを開き、内容を利用者に提示するというハイパーメディアの探索方法が一般的である。
この場合、内容を利用者に提示するシステム提示処理を専門に行なう提示プロセスを起動してもよい。また、データの格納先は通常のファイルではなく、データベースでもよい。すなわちシステムは利用者のナビゲートコマンドの入力により、宛先ノードの内容を表示するためのデータ提示プロセスを起動する。提示プロセスは宛先ノードの内容となるデータをファイルまたはデータベースからメモリ上へロードし、出力装置へデータを提示する。
なお、ノードが持つデータは一般にテキストのみならず、画像、音声、グラフィクスなどを統合的に含むマルチメディアのデータである。
【０００３】
【発明が解決しようとする課題】
しかしながら、従来のハイパーメディアの探索方法においては、次のような課題があった。
ハイパーメディアをナビゲートする時にデータのデータベースからメモリへのローディングに時間がかかるといった問題点がある。そのため、利用者がリンクを辿って別のノードへ移ろうとするたびに、待ち時間が生じ、利用者にとって使いづらいシステムになる。特に、この問題はリアルタイム性が要求されるシステムでは切実である。
【０００４】
【課題を解決するための手段】
本発明は、前記課題を解決するために、マルチメディアのデータがノードの単位でまとめられ関連あるノード同士がリンクで結合された構造を有し、前記リンクを辿りながら前記ノードのデータを探索するハイパーメディアの探索方法において、以下の処理を実行するようにしている。
すなわち、前記各ノードについてそのノードと結合する全ての宛先ノードに対する探索確率（本発明では、例えば、ハイパーメディアにおいてノードＡからノードＢ，Ｃ，Ｄへインクが張られているとき、ノードＡを視聴している利用者が、次にノードＢを探索する確率を、ノードＡからノードＢへの探査確率と呼ぶ。）の初期値を式（８）により設定する初期値設定処理と、ある前記ノードからある前記宛先ノードへ探索された時、そのノードと結合する全ての前記宛先ノードの探索確率を式（９）、（１０）により更新する探索時更新処理と、ある前記ノードからある前記宛先ノードへのリンクが追加された時、そのノードからの全ての前記宛先ノードの探索確率を式（１１）、（１２）により更新する追加時更新処理と、ある前記ノードからある前記宛先ノードへのリンクが削除された時、そのノードからの全ての前記宛先ノードの探索確率を式（１３）、（１４）により更新する削除時更新処理とを実行する。
さらに、ある前記ノードが探索された時、そのノードからの前記宛先ノードへの前記探索確率の大きい１つまたは複数の前記宛先ノードのデータをあらかじめメモリ内にロードする予測ロード処理と、ある前記ノードからある前記宛先ノードへ探索した時に、その宛先ノードのデータが前記予測ロード処理によって前記メモリにロードされているかどうかを判別する判別処理と、前記予測ロード処理によりロードされていればロードされたデータの提示を行い、ロードされていなければその宛先ノードのデータを前記メモリ内にロードしてその宛先ノードのデータの提示を行う提示処理とを実行する。
【０００５】
前記式（８）〜（１４）は、下記の通りである。
Ｐ1 ＝Ｐ2 ＝Ｐ3 ＝…＝Ｐn ＝１／ｎ                   ・・・（８）
ここで、Ｐi （1=1,2,…，n)は、ノードからの宛先ノードへの探索確率であり、ｎはノードからの宛先ノードの数を表す。
Ｐk ＝αＰk ＋１−α                                 ・・・（９）
Ｐi ＝αＰi (i=1,2,…,n  ただしi ≠k )               ・・・（10）
ここで、Ｐk はあるノードからある宛先ノードへ探索された時の、そのノードからその宛先ノードへの探索確率であり、Ｐk （i ≠k)はその宛先ノードを除く宛先ノードへの探索確率であり、ｎはそのあるノードからの宛先ノードの数を表す。また、αは０＜α＜１なる定数であり、αが小さい程、更新量は大きいという性質をもつ更新のためのパラメータである。一般には、リンクを辿るたびに大きく探索確率を変動させないように、αには１に近い値を設定しておく。
【０００６】
Ｐi ＝Ｐi （１−１／ｎ）   (i=1,2,…,n-1)             ・・・（11）
Ｐn ＝１／ｎ                                          ・・・（12）
ここで、Ｐn は、あるノードにリンクが追加された宛先ノードへの探索確率であり、Ｐi はそのノードにリンクが追加された宛先ノード以外の宛先ノードへの探索確率であり、ｎは追加された宛先ノードを含む宛先ノードの数である。
Ｐk ≠１のとき
Ｐi ＝Ｐi ／（１−Ｐk ）  （i=1,2,…，n ただしi ≠k)  ・・・（13）
Ｐk ＝１のとき
Ｐi ＝１／（ｎ−１）      （i=1,2,…，n ただしi ≠k)  ・・・（14）
ここで、Ｐk は、あるノードからリンクが削除された宛先ノードへの探索確率であり、Ｐi はそのノードからのリンクが削除された宛先ノード以外の宛先ノードへの探索確率であり、ｎはリンクが削除された宛先ノードを含む宛先ノードの数である。
【０００７】
【作用】
本発明によれば、以上のようにハイパーメディアの探索方法を構成したので、初期値設定処理により前記各ノードについてそのノードと結合する全ての宛先ノードの探索確率の初期値を設定する。探索時更新処理により、あるノードからある宛先ノードへ探索された時、その探索された宛先ノードの探索確率を大きくし、それ以外の宛先ノードの探索確率を小さくするように更新して探索された宛先ノードがより予測探索されるようにする。追加時更新処理により、あるノードからある宛先ノードへのリンクが追加された時、そのノードからの全ての宛先ノードの探索確率を更新し、削除時更新処理により、あるノードからある宛先ノードへのリンクが削除された時、そのノードからの全ての宛先ノードの探索確率を更新する。
そして、あるノードが探索された時、予測ロード処理により、そのノードからの宛先ノードへの探索確率の大きい１つまたは複数の宛先ノードのデータをあらかじめメモリ内にロードして予測探索する。判別処理により、あるノードからある宛先ノードへ探索した時に、その宛先ノードのデータが前記予測ロード処理によってメモリにロードされているかどうかを判別する。提示処理により、ロードされていればロードされたデータの提示を行い、ロードされていなければその宛先ノードのデータをメモリ内にロードしてその宛先ノードのデータの提示を行う。従って、前記課題を解決できるのである。
【０００８】
【実施例】
図１は、本発明の実施例を示すハイパーメディアを探索方法を実施するためのハイパーメディアシステムの構成図である。
このハイパーメディアシステムでは、入力部１を有している。入力部１の出力側には、ユーザインタフェース管理部２が接続されている。ユーザインタフェース管理部２の出力側には、データ提示部３及びハイパーメディア制御部４が接続されている。ハイパメディア制御部４の出力側には、ユーザインタフェース管理部２及びデータベース部５が接続されている。データベース部５はノード情報管理部５−１、リンク情報管理部５−２、及びメディア情報管理部５−３などによって構成されている。
入力部１は利用者がキーボードやマウスを使用して入力したハイパーメディアでの探索やナビゲーションのためのコマンドをユーザインタフェース管理部２へ供給するものである。ユーザインタフェース管理部２は入力部１からのコマンドを受け付け、ノードの内容や探索結果などのデータの表示を行なうためのデータをデータ提示部３へ供給するものである。データ提示部３は利用者がナビケーションしたノードのデータを利用者に提示処理を行うものである。
【０００９】
ハイパーメディア制御部４はあるノードから宛先ノードへのナビゲーションの探索確率を設定し、あるノードが探索された時、このノードから宛先ノードへの探索確率の大きい１つまたは複数の宛先ノードのデータをあらかじめメモリ内にデータベースからロードする予測ロード処理をするものである。
データベース部５において、ノード情報管理部５−１はノードの情報を管理するものである。ノードの情報としては、ノード識別子、ノードが保持するデータの識別子、リンクの識別子などがある。リンク情報管理部５−２はノード間のリンクに関する情報を管理するものである。リンクの情報としては、リンク識別子、リンクの始点となるノードの識別子、リンクの終点となるノードの識別子、リンク探索確率などである。メディア情報管理部５−３はそれぞれのメディアに応じたデータを持ち、メディアの数だけメディア情報管理部５−３を持つ。たとえば、テキストデータ、グラフィクスデータ、動画像データ、静止画像データ、音声データの管理部などがある。
【００１０】
図２は本発明の実施例を示すハイパーメディアの探索方法のフローチャートである。
以下、これらの図を参照しつつ本実施例のハイパーメディアの探索方法を（１）〜（１８）に説明する。
（１）  ステップＳ１の処理
図１中の入力部１は、利用者からの起動コマンドが入力されると、ハイパーメディアシステムが起動した時点で、ハイパーメディア制御部４へ制御が渡されてハイパーメディア制御部４での処理が開始する。
（２）  ステップＳ２の処理（初期値設定処理）
ハイパーメディア制御部４は、ハイパーメディアネットワークを初期化する。このとき、ハイパーメディア制御部４はデータベース部５のノード情報管理部５−１とリンク情報管理部５−２を介してノード情報とリンク情報を参照し、各ノードの出力リンクに探索確率が設定されているか調べる。もし、設定されていないなら、探索確率の初期値を設定する。
図３は一般的なハイパメディア構造の一部分である。ノードＯからｎ個の宛先ノードＡ1 ，Ａ2 ，Ａ3 ，…，Ａn へ出力リンクＬ1 ，Ｌ2 ，Ｌ3 ，…，Ｌn で結合され、ｍ個のノードＢ1 ，Ｂ2 ，Ｂ3 ，…，Ｂm からノードＯへ入力リンクｌ1 ，ｌ2 ，ｌ3 ，…，ｌm で結合されている。
このようにノードの出力リンクの数（以下、出力次数と呼ぶ）がｎであるときに、ノードＯにおける宛先ノードＡi への各出力リンクの探索確率Ｐi （i=1,…，n)は等しいとして、初期値は１／ｎとおく。すなわち、探索確率Ｐi は式（８）のようになる。
この探索確率Ｐi はリンク情報管理部５−２に格納する。
【００１１】
（３）  ステップＳ３の処理
ハイパーメディア制御部４は、データベース部５を参照し、利用者が現在訪れているノード（以下、カレントノードと呼ぶ）として著者がハイパーメディアへの入り口として設定したノード（以下、ホームノードと呼ぶ）を設定する。そして、ハイパーメディア制御部４では、カレントノード用のデータ提示プロセスを起動する。
（４）  ステップＳ４の処理（提示処理）
ハイパーメディア制御部４は、ユーザインイタフェース部２を通してデータ提示部３のデータ提示プロセスにデータの提示を行なわせる。
（５）  ステップＳ５の処理（予測ロード処理）
ハイパーメディア制御部４は、カレントノードの各出力リンクの探索確率Ｐ1 ，Ｐ2 ，Ｐ3 ，…，Ｐn を調べ、探索確率が最大のリンクを見つける。探索確率が最大のリンクが複数あれば、その中からランダムに選択する。このリンクの宛先ノードのデータを予測ノードとして選択し、この予測ノードの提示プロセスを起動する。起動された提示プロセスは、そのノードのデータをメモリ空間へロードする。ただし、出力装置へのそのノードのデータの提示はまだしない。もし、メモリ空間に余裕がある場合には、２番目に探索確率の大きいリンクの宛先ノードも予測ノードとし、同様の処理を行なう。さらに、メモリ空間に余裕があるなら以下、メモリ空間が充溢するまで同様の処理を繰り返す。
【００１２】
（６）  ステップＳ６の処理
ハイパメディア制御部４は、ユーザインタフェース制御部２を通して利用者からの入力を受け付ける。そして、利用者からの入力がリンクの探索であれば、ステップＳ１０の処理へ進み、リンクの追加であれば、ステップＳ２０の処理へ進み、リンクの削除であれば、ステップＳ３０へ進み、終了であればステップＳ４０へ進む。
（７）  ステップＳ１０の処理（探索時更新処理）
入力コマンドがリンクの探索であれば、ハイパーメディア制御部４では、以下に述べる方法でカレントノードの出力リンクの探索確率を更新する。
利用者がある時点でノードＯからノードＡk へのリンクを辿ったとする。この時、ハイパーメディア制御部４は、式（９）、（１０）のように探索確率を更新する。また、式（９），（１０）より、更新前と更新後の探索確率の和はいずれも１となるように設定される。
（８）  ステップＳ１１の処理
ハイパーメディア制御部４は、データベース部５を参照して、利用者の要求したリンクの宛先ノードをカレントノードとする。
【００１３】
（９）  ステップＳ１２の処理（判別処理）
ハイパーメディア制御部４は、カレントノードに対応する提示プロセスが予測ロード処理によって既に起動されているかどうかを調べる。
（１０）  ステップＳ１３の処理
カレントノードに対応する提示プロセスが起動していないなら起動する。
（１１）  ステップＳ１４の処理
カレントノードに対応する提示プロセス以外のプロセスを強制終了し、ステップＳ４に戻る。
（１２）  ステップＳ２０の処理
入力コマンドがリンクの追加であれば、利用者の要求に従いリンクを追加し、データベース部５を書き換える。
（１３）  ステップＳ２１の処理（追加時更新処理）
ハイパーメディア制御部４は、以下に述べる方法でカレントノードの出力リンクの探索確率を更新し、ステップＳ５へ戻る。
ノードＯには出力リンクＬ1 ，Ｌ2 ，Ｌ3 ，…，Ｌn-1 が結合されており、対応する探索確率がＰ1 ，Ｐ2 ，…，Ｐn-1 で与えられているとする。この時、利用者がハイパーメディアの中で新規にノードＯからノードＯ´へのリンクＬn を追加したとする。この結果、各リンクに対応する探索確率を式（１１）、（１２）のように更新する。
【００１４】
（１４）  ステップＳ３０の処理
入力コマンドがリンクの削除であれば、利用者の要求に従いリンクを削除し、データベース部５を書き換える。
（１５）  ステップＳ３１の処理（削除時更新処理）
ハイパーメディア制御部４は、以下に述べる方法でカレントノードの出力リンクの探索確率を更新する。
ノードＯには出力リンクＬ1 ，Ｌ2 ，Ｌ3 ，…，Ｌn が結合されており、対応する探索確率がＰ1 ，Ｐ2 ，…，Ｐn で与えられているとする。この時、利用者がハイパーメディアの中でノードＯからノードＯ´へのリンクＬk を削除したとする。この結果、各リンクに対応する探索確率を式（１３）、（１４）のように更新する。
（１６）  ステップＳ３２の処理
ハイパメディア制御部４では削除したリンクの宛先ノードの提示プロセスが既に起動されているかどうかを調べる。起動されていなければ、ステップＳ６へ戻る。
【００１５】
（１７）  ステップＳ３３の処理
もし起動されていれば、その提示プロセスを強制終了し、ステップＳ５へ戻る。
（１８）  ステップＳ４０の処理
入力コマンドが終了であれば、終了処理を行う。
以上のように、本実施例では、ハイパーメディア利用者がリンクを辿った時に、すでに提示プロセスが起動されていれば、ローディング時間が短縮でき、提示処理だけで済むので利用者の目からは円滑に目的のノードへ移行できたように見えるという利点がある。通常、利用者は１つのノードに到着すればしばらくはそのノードに滞在しているので、その間を利用してシステムが別の処理を行うのは、利用者には害にはならない。また、起動をかける提示プロセスは過去の探索に基づき確率を推定して選択しているので、ランダムに選択するよりも予測の的中率が高いという利点がある。
【００１６】
【発明の効果】
以上詳細に説明したように、本発明によれば、ノードと結合する全ての宛先ノードへの探索確率を求め、あるノードが探索された時、このノードからの宛先ノードへの前記探索確率の大きい１つまたは複数の宛先ノードのデータをあらかじめメモリ内にロードする予測ロード処理を実行し、あるノードからある宛先ノードへ探索した時に、その宛先ノードのデータが前記予測ロード処理によってメモリにロードされているかどうかを判別し、ロードされていればロードされたデータの提示を行い、ロードされていなければその宛先ノードのデータをメモリ内にロードしてその宛先ノードのデータの提示を行う提示処理をする。これにより、ローディング時間が短縮できて円滑にナビゲーションできる。
【図面の簡単な説明】
【図１】本発明の実施例を示すハイパーメディアの探索方法を実施するためのハイパーメディアシステムの構成図である。
【図２】本発明の実施例を示すハイパーメディアの探索方法のフローチャートである。
【図３】一般的なハイパーメディアの部分構造を示す図である。
【符号の説明】
１                入力部
２                ユーザインタフェース管理部
３                データ提示部
４                ハイパーメディア制御部
５                データベース部
【図１】
0003692154.tif 000002
【図２】
0003692154.tif 000003
【図３】
0003692154.tif 000004