(57)【要約】【課題】対話型データ検索に使用する場合においても検索効率のよいデータ検索技術を提供する。【解決手段】木構造型データから所望のデータの検索を行うデータ検索装置１において、木構造型データの各節点間のリンク情報を格納する原始リンク情報格納手段３と、原始リンク情報格納手段３に記憶された各節点のリンク情報のうち、終端節点のリンク情報については、兄弟節点に対する新たなリンク情報を追加するリンク設定手段４とを備えた構成とした。これにより、終端節点から兄弟節点に遷移する場合に親節点を通らず直接遷移できる。そのため、木構造データの検索の効率が向上する。【選択図】          図１
2004348602.tif 000002
【特許請求の範囲】
【請求項１】
木構造型データから所望のデータの検索を行うデータ検索装置において、
前記木構造型データの各節点間のリンク情報を格納する原始リンク情報格納手段と、
前記原始リンク情報格納手段に記憶された各節点のリンク情報のうち、終端節点のリンク情報については、兄弟節点に対する新たなリンク情報を追加するリンク設定手段と、
を備えていることを特徴とするデータ検索装置。
【請求項２】
前記リンク設定手段は、前記原始リンク情報格納手段に記憶された各節点のリンク情報のうち、根節点以外の節点のリンク情報に対しては、その親節点に対する新たなリンク情報を追加することを特徴とする請求項１記載のデータ検索装置。
【請求項３】
前記リンク設定手段は、前記原始リンク情報格納手段に記憶された各節点のリンク情報のうち、根節点以外の節点のリンク情報に対しては、根節点に対する新たなリンク情報を追加することを特徴とする請求項１又は２記載のデータ検索装置。
【請求項４】
前記リンク設定手段は、非終端節点のリンク情報において、子節点の数ｎが所定の閾値ｎｍａｘに１を加えた値ｎｍａｘ＋１を超えている場合、当該非終端節点の子節点の集合をｎｍａｘ個の節点の集合Ａとｎ−ｎｍａｘ個の節点の集合Ｂに分割し、前記集合Ｂに属する節点を子節点とする新たな節点を生成すると共に、当該非終端節点の子節点を前記集合Ａに属する節点及び前記新たな節点とすることを特徴とする請求項１乃至３の何れか一に記載のデータ検索装置。
【請求項５】
木構造型データから所望のデータの検索を行うデータ検索方法において、
原始リンク情報格納手段に格納された前記木構造型データの各節点間のリンク情報のうち、終端節点のリンク情報については、兄弟節点に対する新たなリンク情報を追加して修正リンク情報を生成し、
前記修正リンク情報に従って各節点間を遷移することにより、所望のデータの検索を行うことを特徴とするデータ検索方法。
【請求項６】
前記原始リンク情報格納手段に記憶された各節点のリンク情報のうち、根節点以外の節点のリンク情報に対しては、その親節点に対する新たなリンク情報を追加することを特徴とする請求項５記載のデータ検索方法。
【請求項７】
前記原始リンク情報格納手段に記憶された各節点のリンク情報のうち、根節点以外の節点のリンク情報に対しては、根節点に対する新たなリンク情報を追加することを特徴とする請求項５又は６記載のデータ検索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、木構造型データの検索を行うためのデータ検索技術に関し、特に、木構造データの各節点においてユーザにより検索方向を指定することにより検索方向を指定する対話型データ検索に使用するのに適したデータ検索技術に関する。
【０００２】
【従来の技術】
多分木で表現される木構造型データの検索を行う検索技術としては、従来より多くのものが考案されている（例えば、特許文献１，２，３参照）。
【０００３】
特許文献１の木構造型データ検索方式では、木構造型データの節点間の関係を関係データベースに格納する。すなわち、関係データベースの各レコードに、木構造型データの各節点にあたるデータを格納する。また、各レコードには、レコードの格納位置を表すＩＤを設ける。そして、各節点Ｎを始節点とする節点｛Ｎ０，Ｎ１，…｝のＩＤを、その節点Ｎに対応するレコードのカラムに格納する。そして、木構造における１つの親節点とその親節点に対する複数の子節点との間の枝を、複数の子節点の中の有限個の子節点との間の枝に限定する。
【０００４】
このとき、親節点の枝数を限定したことにより非連結となった子節点は、他の兄弟節点との間に新たなリンク（枝）を形成させ、これにより親節点との連結性を保つようにしている。
【０００５】
このように、１つの親節点から出る枝を、複数の子節点の中の有限個の子節点との間の枝に限定することにより、関係データベースのカラム数の上限が決まる。そのため、関係データベースをメモリ内に効率よく格納できる。
【０００６】
また、特許文献２には、木構造型データベースの検索時間の短縮化を図るため、根節点以外の節点に格納された特定の目的データを検索する際に、ルートノードから検索することなく直接アクセスすることが可能な直接アクセスノードを決定して、目的データに最も近い直接アクセスノードから目的の目的データまでの検索を行う方式が記載されている。
【０００７】
また、特許文献３には、表示装置に階層メニューをグラフィック木構造で表示して、ユーザが表示されたグラフィック木構造からメニューを指定して、指定されたメニューに対応する動作を実行する対話型の検索方式が記載されている。
【０００８】
【特許文献１】
特開平１０−２４０７４１号公報
【特許文献２】
特開平７−２１０５６３号公報
【特許文献３】
特開平１−１４４１１７号公報
【０００９】
【発明が解決しようとする課題】
しかしながら、木構造データの各節点においてユーザにより検索方向を指定することにより検索方向を決定する対話型データ検索においては、目的データの検索は、ユーザがディスプレイ等の表示装置に表示されたメニューを見ながら節点間の遷移方向を決定する。この場合、木構造データの節点数が多くなると、ユーザが目的データにアクセスするまでの節点間の遷移回数が多くなる。
【００１０】
特許文献１のデータ検索方式によれば、同じ親節点を有する兄弟節点間でリンクを形成することにより、ある時点で、一つの子節点が表示状態にある場合に、他の兄弟節点に１回の遷移で移行することが可能となる。そのため、目的データにたどり着くまでの遷移回数を減少させることが可能である。
【００１１】
しかし、木構造における１つの親節点とその親節点に対する複数の子節点との間の枝を、複数の子節点の中の有限個の子節点との間の枝に限定したことによって、同じ親節点を有する兄弟節点間においても、リンクされた兄弟節点とリンクされない兄弟節点とが生じる。これにより、ユーザは、ある一つの子節点が表示状態にある場合に、その子節点に連結された兄弟節点の存在を認識することはできるが、その子節点に非連結な兄弟節点の存在を認識することはできない。従って、目的データの存在がわかりにくくなり、かえって検索効率が低下するという欠点がある。
【００１２】
また、親節点と枝で結ばれている子節点と親節点との間に直接の枝が存在しない子節点とが生じる。そのため、目的データが親節点に非連結な子節点に存在した場合、ユーザが親節点からその子節点にたどり着くことが困難である。
【００１３】
また、特許文献２に記載のデータ検索方式では、直接アクセスノードを設定することにより、目的データの存在する節点への距離を短縮し、遷移回数の減少を図っている。
【００１４】
しかしながら、この場合、最短距離で目的データにたどり着こうとすると、直接アクセスノードが設定された節点にたどり着く必要がある。一方、対話型データ検索においては、ユーザが表示画面を見ながら節点間の遷移を決定していくため、直接アクセスノードが設定された節点に必然的にたどり着くことはできない。従って、対話型データ検索においては、この方式は必ずしも検索能率の向上にはつながらない。
【００１５】
また、木構造型データに新たにデータを追加して、新たな節点が追加された場合、直接アクセスノードの組み替えを人手で行う必要がある。従って、頻繁に更新が行われるデータベースにおいて使用するのには適さない。
【００１６】
更に、一つの親節点に対する子節点の数が多くなると、子節点にアクセスするためのメニューが煩雑となり、メニューの中から所望の項目を選び出す効率が悪くなる。特に、音声入力によってメニューを選択する検索装置に適用する場合、メニューの項目数が増えると、音声認識の認識率が低下し、誤った選択がされやすくなるため、検索効率がかえって低下する。
【００１７】
また、特許文献３に記載のデータ検索方式では、階層メニューをグラフィック木構造で表示するため、ユーザは目的データの存在場所を迅速に探し出すことが可能となる。しかしながら、節点数が多くなると、グラフィック木構造が巨大化し、限られた表示画面中に表示することが困難となる。そのため、小規模なデータベースにしか適用することができない。
【００１８】
そこで、本発明の目的は、対話型データ検索に使用する場合においても検索効率のよいデータ検索技術を提供することにある。
【００１９】
【課題を解決するための手段】
本発明は、木構造型データから所望のデータの検索を行うデータ検索装置において、前記木構造型データの各節点間のリンク情報を格納する原始リンク情報格納手段と、前記原始リンク情報格納手段に記憶された各節点のリンク情報のうち、終端節点のリンク情報については、兄弟節点に対する新たなリンク情報を追加するリンク設定手段と、を備えていることを特徴とする。
【００２０】
この構成により、原始リンク情報格納手段が、終端節点に対しては、その兄弟節点へのリンクを追加することにより、終端節点から兄弟節点に遷移する場合に親節点を通らず直接遷移できる。そのため、木構造データの検索の効率が向上する。
【００２１】
また、終端節点からは、その終端節点と兄弟関係にある総ての節点を見ることができ、また、非終端節点からは、その非終端節点と親子関係にある総ての子節点を見ることができる。従って、対話型データ検索においても、データの見落としがなく、効率的な検索が可能となる。
【００２２】
また、原始リンク情報における終端節点は子節点がないため、これに新たに兄弟節点へのリンクを追加したとしても、一般には、当該節点の出次数が極端に多くなることはない。従って、特定の節点において分岐枝数が極端に多くなり、検索効率が低下することを防止できる。
【００２３】
また、原始リンク情報格納手段に格納されたリンク情報（以下、「原始リンク情報」という。）に基づき、兄弟節点へのリンクを自動的に設定することにより、大規模なＷｅｂページや、追加修正が頻繁に行われるＷｅｂページの場合であっても、検索効率のよい木構造データを効率よく再構築できる。
【００２４】
また、前記リンク設定手段は、前記原始リンク情報格納手段に記憶された各節点のリンク情報のうち、根節点以外の節点のリンク情報に対しては、その親節点に対する新たなリンク情報を追加するような構成とすることができる。
【００２５】
これにより、原始リンク情報の根節点以外の節点のリンク情報に対して、その親節点に対するリンクを追加することで、子節点から親節点への遷移が可能となる。従って、検索時の利便性が向上する。
【００２６】
また、前記リンク設定手段は、前記原始リンク情報格納手段に記憶された各節点のリンク情報のうち、根節点以外の節点のリンク情報に対しては、根節点に対する新たなリンク情報を追加するように構成することができる。
【００２７】
この構成により、原始リンク情報の根節点以外の節点のリンク情報に対して、その根節点に対するリンクを追加することで、下位節点から根節点への直接の遷移が可能となる。従って、特に検索木の階層が多い場合、深層の節点から根節点に直接遷移可能なため、検索時の利便性が向上する。
【００２８】
また、本発明においては、前記リンク設定手段は、非終端節点のリンク情報において、子節点の数ｎが所定の閾値ｎｍａｘに１を加えた値ｎｍａｘ＋１を超えている場合、当該非終端節点の子節点の集合をｎｍａｘ個の節点の集合Ａとｎ−ｎｍａｘ個の節点の集合Ｂに分割し、前記集合Ｂに属する節点を子節点とする新たな節点を生成すると共に、当該非終端節点の子節点を前記集合Ａに属する節点及び前記新たな節点とする処理を行うように構成することができる。
【００２９】
これにより、もとの木構造型データに、多数の子節点を有する節点が含まれていたとしても、修正されたリンク情報においては、各節点の子節点の数を所定の数以下とすることができる。従って、一つの節点において選択枝として生じる節点数を所定数以下に制限することが可能であり、ユーザの検索効率が向上する。また、音声入力による選択を行う場合には、認識率が向上する。
【００３０】
また、本発明は、木構造型データから所望のデータの検索を行うデータ検索方法において、原始リンク情報格納手段に格納された前記木構造型データの各節点間のリンク情報のうち、終端節点のリンク情報については、兄弟節点に対する新たなリンク情報を追加して修正リンク情報を生成し、前記修正リンク情報に従って各節点間を遷移することにより、所望のデータの検索を行うことを特徴とする。
【００３１】
【発明の実施の形態】
以下、本発明の一実施形態について、図面を参照しながら説明する。
（実施形態１）
図１は本発明の実施形態１に係るデータ検索装置の機能構成を表すブロック図である。
【００３２】
本発明のデータ検索装置１は、データ記憶手段２、原始リンク情報記憶手段３、リンク設定手段４、修正リンク情報記憶手段５、検索手段６、表示手段７、及び入力手段８を有する。
【００３３】
データ記憶手段２には、木構造データベースの各節点に対応するデータが格納されている。また、原始リンク情報記憶手段３には、データ記憶手段２に格納された各データ間の連結関係に関する情報（以下、「原始リンク情報」という。）が格納されている。リンク設定手段４は、原始リンク情報記憶手段３に記憶された原始リンク情報に新たなリンク情報を付加して新たなリンク情報（以下、「修正リンク情報」という。）を生成する。修正リンク情報記憶手段５には、リンク設定手段４が生成する修正リンク情報が格納される。
【００３４】
検索手段６は、修正リンク情報記憶手段５に格納された修正リンク情報に基づいて、現節点（現在選択状態にある節点をいう。）に結合された子節点やデータ記憶手段２から読み出した親節点に対応するデータ等を表示手段７に表示するとともに、入力手段８から入力されるユーザからの指示に基づいて現節点の切換を行う。
【００３５】
データ記憶手段２、原始リンク情報記憶手段３、及び修正リンク情報記憶手段５は、ＲＡＭ、磁気ディスク、ＣＤ−ＲＯＭ、メモリカード等の記憶装置によって構成される。検索手段６及びリンク設定手段４は、マイコン、中央演算装置（ＣＰＵ）等によって構成される。表示手段７は、ブラウン管、液晶ディスプレイ等の表示装置によって構成される。また、入力手段８は、キーボード、音声入力装置、ポインティング・デバイス等によって構成される。
【００３６】
図２は原始リンク情報のデータ構造の一例を木グラフで表した図、図３は図２の原始リンク情報リストの構造を表す図である。
【００３７】
図２において、符号Ａ〜Ｘは、原始リンク情報記憶手段３内における、各節点のデータが格納されたアドレスを表す。以下、例えば、アドレスＡに対応する節点を節点Ａ、アドレスＢに対応する節点を節点Ｂのように呼ぶことにする。
【００３８】
図２では、節点Ａは根節点である。また、枝で連結された２つの節点のうち、上側の節点（有向辺の始節点）が親節点、下側の節点（有向辺の終節点）が子節点である。例えば、節点Ｂに対しては、節点Ａが親節点であり、節点Ｅ，Ｆ，Ｇ，Ｈ，Ｉが子節点である。親節点が同じ子節点同士を兄弟節点という。例えば、節点Ｂを親節点とする子節点Ｅ，Ｆ，Ｇ，Ｈ，Ｉは兄弟節点である。
【００３９】
ある一つの節点を始節点とする枝の数を出次数、当該節点を終節点とする枝の数を入次数という。原始リンク情報を木グラフで表現したときに、出次数が０となる節点を終端節点、出次数が０ではない節点を非終端節点という。図２においては、節点Ｆ，Ｈ，Ｉ等は終端節点である。
【００４０】
原始リンク情報記憶手段３には、図２で表される木構造型データの原始リンク情報が図３のようなリスト形式で格納されている。各アドレスに格納された各節点の原始リンク情報は、｛データへのポインタ，子節点数，｛子節点ポインタ｝｝の組（以下、この組を「リンク情報」という。）により構成されている。
【００４１】
ここで、「データへのポインタ」とは、その節点ｘに対応するデータが格納されているデータ記憶手段２内のアドレスＤｐ（ｘ）をいう。「子節点数」とは、その節点ｘを親節点とする子節点の数ｎｃ（ｘ）をいう。「子節点ポインタ」とは、その節点ｘを親節点とする子節点の原始リンク情報記憶手段３内のアドレスをいう。なお、節点ｘに対応するリンク情報には、ｎｃ（ｘ）個の子節点ポインタが格納されている。但し、ｎｃ（ｘ）＝０のときには、子節点はないので、この子節点ポインタは格納されない。
【００４２】
以上のように構成された本実施形態に係るデータ検索装置について、以下その動作を説明する。
【００４３】
図４〜図６は本発明の実施形態１に係るリンク設定手段の動作を表すフローチャートである。
【００４４】
まず、リンク設定手段４は、原始リンク情報記憶手段３から原始リンク情報リストＴを読み出して、修正リンク情報リストＴ’に格納する（Ｓ１）。ここで、「修正リンク情報リスト」とは、リンク情報を要素とするリストである。修正リンク情報リストＴ’は、修正リンク情報記憶手段５に格納される。
【００４５】
次に、リンク設定手段４は、処理を行う節点の階層数ｋを０に設定する（Ｓ２）。そして、リンク設定手段４は、修正リンク情報記憶手段５内において根節点のリンク情報が格納されているアドレスを、リンク情報ポインタｐ（０，０）に格納する（Ｓ３）。
【００４６】
そして、リンク設定サブルーチンを引数（ｋ，ｐ（０，０），ｐ（０，０））として呼び出す（Ｓ４）。
【００４７】
図５はリンク設定サブルーチンの処理を表している。リンク設定サブルーチンの引数は、変数（ｋ，ｐｉｎ，ｐｐ）に引き継がれる。このリンク設定サブルーチンは再帰処理を行うサブルーチンである。
【００４８】
まず、リンク設定手段４は、修正リンク情報記憶手段５において、リンク情報ポインタｐｉｎで指定されるアドレスに格納されているリンク情報｛Ｄｐｉｎ，  ｎ，  ｛ｐ（ｋ＋１，０），…，ｐ（ｋ＋１，ｎ−１）｝｝を読み出す（Ｓ１１）。ここで、上述の通り、変数Ｄｐにはデータへのポインタ、変数ｎには子節点数、変数ｐ（ｋ＋１，０），…，ｐ（ｋ＋１，ｎ−１）には、それぞれ子節点ポインタが格納される。
【００４９】
ここで、ｎ≠０の場合（Ｓ１２）、すなわち、読み込んだリンク情報に対応する節点が非終端節点である場合、節点ｐ（ｋ＋１，ｉ）（ｉ＝０，…，ｎ−１）に対して、順次、親節点及び根節点へのリンクを追加し、リンク設定サブルーチンを再帰的に呼び出す処理を行う（Ｓ１４〜Ｓ１７）。各節点ｐ（ｋ＋１，ｉ）に対してリンク設定サブルーチンを呼び出す際には、引数を（ｋ＋１，ｐ（ｋ＋１，ｉ），ｐｐ）として呼び出す。これにより、各枝に対して終端節点に至るまで再帰処理が行われる。
【００５０】
なお、ステップＳ１５においては、リンク情報｛Ｄｐｉｎ，  ｎ，  ｛ｐ（ｋ＋１，０），…，ｐ（ｋ＋１，ｎ−１）｝｝の子節点ポインタに、親節点へのポインタｐｐと根節点へのポインタｐ０とを追加する処理を行い、修正されたリンク情報｛Ｄｐｉｎ，  ｎ，  ｛ｐ０，  ｐｐ，  ｐ（ｋ＋１，０），…，ｐ（ｋ＋１，ｎ−１）｝｝を修正リンク情報記憶手段に格納する。この処理によって、非終端節点のリンク情報の子節点ポインタには、親節点、及び根節点に対応するポインタが追加される。
【００５１】
ステップＳ１２において、ｎ＝０の場合、すなわち、読み込んだリンク情報に対応する節点が終端節点である場合、ｋ≠０（根節点ではない）ならば（Ｓ１８）、この節点についてリンク追加設定処理を行った後（Ｓ１９）、リンク設定サブルーチンの処理を終了する。
【００５２】
ステップＳ１８において、ｋ≠０（根節点）ならば、根節点には枝がないので、リンク設定サブルーチンの処理を終了する。
ここで、図６はリンク追加設定処理を表す。リンク追加設定処理では、まず、リンク設定手段４は、リンク情報ポインタｐｐで指定されるアドレスに格納された親節点のリンク情報Ｐ＝｛Ｄｐｐ，ｍ，  ｛ｐ（ｋ，０），…，ｐ（ｋ，ｍ−１）｝｝を取得する（Ｓ２１）。次に、リンク情報Ｐの子節点ポインタのうち、現在の節点に対応するポインタｐｉｎを除き、親節点へのポインタｐｐと根節点へのポインタｐ０とを追加して、現在の節点に対する修正リンク情報Ｐ’＝｛Ｄｐｉｎ，ｍ＋１，  ｛ｐ０，ｐｐ，ｐ（ｋ，０），…，ｐ（ｋ，ｍ−１）｝（但し、ｐｉｎを除く）｝を生成する（Ｓ２２）。そして、生成した修正リンク情報Ｐ’を、修正リンク情報記憶手段５内のポインタｐｉｎで指定されるアドレスに格納し（Ｓ２３）、リンク追加設定処理を終了する。
【００５３】
以上の処理によって、終端節点のリンク情報の子節点ポインタには、兄弟節点、親節点、及び根節点に対応するポインタが追加される。
【００５４】
図７は図３に例示した原始リンク情報リストに対して上述のリンク設定処理を行った後に修正リンク情報記憶手段に格納されている修正リンク情報リストの構造を表す図である。
【００５５】
図７に示したように、根節点Ａに対しては、リンク情報の修正（リンクの追加）は行われない。非終端節点に対しては、親節点及び根節点に対するリンクが追加される。例えば、節点Ｅに対しては、親節点Ｂと根節点Ａに対するリンクが追加されている。なお、根節点の子節点に当たる節点は、親節点の根節点が同一であるため、重複したリンクを避ける意味から、１つのリンクのみが追加されている。例えば、節点Ｂの親節点は根節点Ａであるため、節点Ｂのリンク情報に対しては節点Ａのポインタが１つだけ追加されている。
【００５６】
一方、終端節点に対しては、兄弟節点、親節点及び根節点に対するリンクが追加される。例えば、終端節点Ｆのリンク情報に対しては、兄弟節点Ｅ，Ｇ，Ｈ，Ｉ、親節点Ｂ、及び根節点Ａのポインタが追加されている。
【００５７】
このようにして、原始リンク情報記憶手段３に記憶された原始リンク情報から、自動的に修正リンク情報が生成され、修正リンク情報格納手段５に格納される。
【００５８】
最後に、検索手段６の動作について説明する。
ここでは、木構造型データの一例として、国立公園案内用のデータを用いて説明を行う。まず、国立公園案内用の木構造型データは、図８に示したような構造を有する。この木構造データに基づき、リンク設定手段４により修正リンク情報を生成する。そして、この修正リンク情報を修正リンク情報格納手段５に格納する。ここまでの処理動作は、上述した通りである。
【００５９】
そして、まず最初に検索手段６は、根節点である「国立公園」が選択された状態となる。検索手段６は、修正リンク情報記憶手段５から、節点「国立公園」に対応するリンク情報を読み込む。そして、リンク情報の中のデータへのポインタを参照して、データ記憶手段２の中の当該ポインタで指定されるアドレスに格納された、節点「国立公園」に対応するデータを読み込む。そして、この読み込んだデータを表示手段７の画面に表示する。
【００６０】
このとき、検索手段６は、節点「国立公園」の子節点へのリンク「北海道」，「本州」，「四国」，「九州・沖縄」をメニューとして表示する（図９（ａ）参照）。そして、検索手段６は、ユーザからの入力を待つ。
【００６１】
ここで、例えば、ユーザが入力手段８により、節点「北海道」を選択したとする。検索手段６は、修正リンク情報記憶手段５から、節点「北海道」に対応するリンク情報を読み込む。そして、リンク情報の中のデータへのポインタを参照して、データ記憶手段２の中の当該ポインタで指定されるアドレスに格納された、節点「北海道」に対応するデータを読み込む。そして、この読み込んだデータを表示手段７の画面に表示する。
【００６２】
このとき、検索手段６は、節点「北海道」の子節点へのリンク「利尻礼文サロベツ」，「知床」，「阿寒」，「釧路湿原」，「大雪山」，「知床洞爺」及び根節点へのリンク「ホームに戻る」をメニューとして表示する（図９（ｂ）参照）。そして、検索手段６は、ユーザからの入力を待つ。
【００６３】
ここで、例えば、ユーザが入力手段８により、節点「利尻礼文サロベツ」を選択したとする。検索手段６は、修正リンク情報記憶手段５から、節点「利尻礼文サロベツ」に対応するリンク情報を読み込む。そして、リンク情報の中のデータへのポインタを参照して、データ記憶手段２の中の当該ポインタで指定されるアドレスに格納された、節点「利尻礼文サロベツ」に対応するデータを読み込む。そして、この読み込んだデータを表示手段７の画面に表示する。
【００６４】
このとき、検索手段６は、節点「利尻礼文サロベツ」の兄弟節点へのリンク「「知床」，「阿寒」，「釧路湿原」，「大雪山」，「知床洞爺」及び親節点へのリンク「上に戻る」及び根節点へのリンク「ホームに戻る」をメニューとして表示する（図９（ｃ）参照）。そして、検索手段６は、ユーザからの入力を待つ。
【００６５】
このように、終端節点が選択状態にあるときでも、兄弟節点に対してリンクが張られているため、ユーザは兄弟節点のリンクを参照しながら目的のデータを検索することが可能となる。従って、目的データに達するまでの節点間の遷移回数が減少し、検索能率が向上する。
【００６６】
また、終端節点に対してのみ兄弟節点へのリンクを新たに設定し、非終端節点に対しては兄弟節点へのリンクは設定しないことで、選択メニューが煩雑となることが避けられる。そのため、ユーザがメニュー中のキーワードを認識する時間が早く、検索能率が高い。
【００６７】
また、入力手段８に音声入力装置を利用した場合、メニューのキーワード数が多いと誤認識率が増加するとともに、システムが認識に要する時間も増加するという問題がある。しかし、上記の如く、終端節点に対してのみ兄弟節点へのリンクを新たに設定することで、一つの節点に対するリンクが少なくメニューが簡単化されるため、上記のような問題は生じにくくなる。
【００６８】
（実施形態２）
本実施形態においては、各節点において、子節点が所定の数を越えたときに、新たな部分木を生成して、子節点を分割する例について説明する。
【００６９】
なお、データ検索装置の構成と動作に関して、図１〜図４、図６〜図９までは実施形態１と同様である。
【００７０】
図１０は本発明の実施形態２に係るリンク設定手段の動作を表すフローチャートである。図１０において、ステップＳ１１〜Ｓ１９は、図５と同様の処理を表している。
【００７１】
本実施形態においては、ステップＳ１２において、ｎ≠０の場合、すなわち、読み込んだリンク情報に対応する節点が非終端節点である場合において、子節点数が多い場合には、以下に説明するステップＳ３２〜Ｓ３５の節点分割処理を行うことを特徴としている。すなわち、ステップＳ１２においてｎ≠０の場合、リンク設定手段４は、子節点数ｎを参照して、節点ｐｉｎの子節点数ｎが所定の閾値ｎｍａｘに１を加えた値よりも大きいか否かを判定する（Ｓ３１）。そして、ｎ＞ｎｍａｘ＋１の場合には、節点分割処理を行い、前述のステップＳ１４に移行する。一方、ｎ≦ｎｍａｘ＋１の場合には、節点分割処理は行わずに、前述のステップＳ１４に移行する。
【００７２】
節点分割処理は以下のように行われる。まず、リンク設定手段４は、修正リンク情報記憶手段５に記憶されている修正リンク情報リストの最後の格納データの欄の後に、節点ｐｉｎ＿ｎｅｗのリンク情報が格納される新たな欄を追加する。そして、節点ｐｉｎ＿ｎｅｗのリンク情報として、「子節点数」にはｎ−ｎｍａｘ、「子節点ポインタ」には、｛ｐ（ｋ＋１，ｎｍａｘ），  ｐ（ｋ＋１，ｎｍａｘ＋１），…，ｐ（ｋ＋１，ｎ−１）｝を格納する。なお、新たに追加された節点ｐｉｎ＿ｎｅｗに対応するデータは、データ記憶手段２内には格納されていないので、「データへのポインタ」には、次ページが存在することを表す符号ＮＥＸＴ（データ記憶手段２のアドレス指定に使用される符号以外の符号）を格納しておく（Ｓ３２）。これにより、検索手段６は、データへのポインタがＮＥＸＴであった場合には、その節点が節点分割処理に追加された節点であることを識別することができる。
【００７３】
次に、リンク設定手段４は、節点ｐｉｎの子節点ポインタ｛ｐ（ｋ＋１，０），…，ｐ（ｋ＋１，ｎ−１）｝のうちから、｛ｐ（ｋ＋１，ｎｍａｘ），  …，  ｐ（ｋ＋１，ｎ−１）｝を削除するとともに、新たに追加された節点へのポインタｐｉｎ＿ｎｅｗを追加する（Ｓ３３）。また、子節点数ｎをｎｍａｘ＋１に設定する（Ｓ３４）。
【００７４】
そして、リンク設定手段４は、修正リンク情報記憶手段５内の修正リンク情報リストの節点ｐｉｎのリンク情報が格納されている欄のリンク情報として、「子節点数」にはｎｍａｘ＋１、「子節点ポインタ」には、｛ｐ（ｋ＋１，０），  ｐ（ｋ＋１，  １），…，ｐ（ｋ＋１，ｎｍａｘ−１），  ｐｉｎ＿ｎｅｗ｝を格納する（Ｓ３５）。
【００７５】
以上の動作により、子節点の数がｎｍａｘ＋１以上の節点のリンク情報は分割される。例えば、原始リンク情報記憶手段３に格納されているリンク情報が、図８のようなものであった場合には、子節点数の閾値をｎｍａｘ＝４として上記節点分割処理を行うと、節点間のリンクは図１１のようになる。なお、図１１においては、図面を見やすくするために、兄弟節点間のリンク、親節点へのリンク、及び根節点へのリンクは省略している。
【００７６】
図８において、節点「北海道」の子節点数は６であり、ｎｍａｘ＋１＝５を超えているために子節点が分割される。そして、新たに「次のページ」の節点が追加される。新たに追加された節点「次のページ」の子節点には、分割処理によって節点「北海道」の子節点から削除された節点「大雪山」、「支笏湖」が設定される。
【００７７】
以上のような節点分割処理によって、最初の木構造型データにおいて、多数の子節点を有する節点が含まれていたとしても、自動的に各節点の子節点の数を所定の数以下にすることができる。
【００７８】
なお、本実施形態において、ステップＳ３１において、節点分割の条件として子節点数ｎが閾値ｎｍａｘを超えたこと（ｎ＞ｎｍａｘ）を条件とするのではなく、子節点数ｎが閾値ｎｍａｘに１を加えた値を超えたこと（ｎ＞ｎｍａｘ＋１）としたのは、以下のような理由による。
【００７９】
節点分割処理の結果、子節点が分割された親節点の子節点は、ｎｍａｘ個の節点と、新たに追加された節点ｐｉｎ＿ｎｅｗとなるため、親節点の子節点数は合計ｎｍａｘ＋１個となる。従って、子節点数がｎｍａｘ＋１個の親節点に対して分割処理を行ったとしても、当該親節点の子節点数は減少せず、かえって木構造が複雑化する結果となる。例えば、図８のような木構造型データに対してｎｍａｘ＝４として節点分割処理を行う場合、仮にステップＳ３１において分割の条件をｎ＞ｎｍａｘとすると、分割後の木構造は図１２のようになる。
【００８０】
図１２では、子節点数が１の節点が新たに３個追加されている。しかし、このような節点分割がされると、ユーザが目的の情報まで行き着くまでの遷移数が増加する。例えば、図１１において「大山隠岐」を検索する場合には、ユーザは３回の遷移によって目的のデータに行き着けるのに対して、図１２のような木構造型データでは４回の遷移が必要である。従って、検索効率が低下することとなるため好ましくない。
【００８１】
（実施形態３）
本実施形態のデータ検索装置の構成は、実施形態１で説明した図１と同様である。また、リンク設定手段４の動作についても、図２〜図７に基づいて説明した通りである。本実施形態のデータ検索装置では、検索手段６の動作に特徴がある。
【００８２】
図１３は本発明の実施形態３に係るデータ検索装置の検索手段の動作を表すフローチャートである。
【００８３】
まず、検索手段６は、内部変数として有するカレント節点ポインタｐに、根節点ポインタｐ０を設定する（Ｓ４１）。ここで、「カレント節点」とは、現在選択されている節点をいう。「カレント節点ポインタ」とは、カレント節点のリンク情報が格納されている修正リンク情報記憶手段５内のアドレスをいう。また、「根節点ポインタ」とは、根節点のリンク情報が格納されている修正リンク情報記憶手段５内のアドレスをいう。
【００８４】
次に、検索手段６は、内部変数として有する親節点ポインタｐｐ（０）にｐ０に設定する。そして、カレント節点の深さｓｃを０に設定する（Ｓ４２）。ここで、「節点の深さ」とは、根節点からその節点に至る順路の長さをいう。
【００８５】
次に、検索手段６は、修正リンク情報記憶手段５から、カレント節点ポインタｐのリンク情報｛Ｄｐ，ｎ，｛ｐｃ（０），…，ｐｃ（ｎ−１）｝｝を取得する（Ｓ４３、図７参照）。ここで、変数Ｄｐにはデータへのポインタ、変数ｎには子節点数、変数ｐｃ（０），…，ｐｃ（ｎ−１）には、リンク先ポインタ（根節点ポインタ、親節点ポインタ、又は子節点ポインタ）が格納される。そして、子節点の先頭の位置を表すインデックスｉ０を０に初期化する（Ｓ４４）。ここで、図７から分かるように、修正リンク情報リストのリンク先ポインタには、子節点ポインタ以外にも、根節点ポインタや親節点ポインタが含まれている。リンク先ポインタに根節点ポインタが含まれている場合には、先頭位置に格納される。また、リンク先ポインタに親節点ポインタが含まれる場合には、根節点ポインタが含まれていればその後に、含まれていなければ先頭位置に格納される。子節点ポインタ（兄弟節点のポインタを含む。）は、根節点ポインタや親節点ポインタの後に格納されている。そこで、「子節点の先頭の位置を表すインデックス」とは、リンク先ポインタの中において子節点ポインタが格納されている先頭位置を表すインデックスをいう。
【００８６】
次に、検索手段６は、リンク先ポインタの先頭のポインタｐｃ（０）と根ポインタｐ０とを比較し（Ｓ４５）、両者が同一であれば、表示手段７に表示する選択メニューに「ホームに戻る」を追加する（Ｓ４６）。そして、インデックスｉ０の値を１だけ繰り上げると共に、子節点数ｎを１だけ減少させる（Ｓ４７）。
【００８７】
次に、検索手段６は、カレント節点の深さｓｃが０でない場合には、リンク先ポインタｐｃ（ｉ０）とカレント節点の親節点ポインタｐｐ（ｓｃ−１）とを比較し（Ｓ４８）、両者が同一であれば、表示手段７に表示する選択メニューに「上に戻る」を追加する（Ｓ４９）。そして、インデックスｉ０の値を１だけ繰り上げると共に、子節点数ｎを１だけ減少させる（Ｓ５０）。
【００８８】
次に、検索手段６は、データへのポインタＤｐで指定されるデータ記憶手段２のアドレスから、表示データを読み出して、表示手段７に表示する（Ｓ５１）。
【００８９】
次に、検索手段６は、子節点数ｎが表示制限個数ｎｍａｘを超えているか否かを判断する（Ｓ５２）。
【００９０】
ステップＳ５２において、子節点数ｎが表示制限個数ｎｍａｘを超えていない場合には、検索手段６は、表示手段７に表示する選択メニューに、表示ポインタ｛ｐｃ（ｉ０），…，ｐｃ（ｉ０＋ｎ−１）｝に対応する節点のリンクを表示する（Ｓ５３）。そして、ユーザが入力手段８により選択メニューを選択するまで待機する（Ｓ５４）。
【００９１】
ユーザが入力手段８により選択メニューを選択した場合、検索手段６は、まず、何れかの子節点ポインタｐｃ（ｎ）に対応する子節点が選択されたか否かを判断する（Ｓ７０）。ここで、何れかの子節点ポインタｐｃ（ｎ）に対応する子節点が選択された場合、検索手段６は、ます、親節点ポインタｐｐ（ｓｃ）にカレント節点ポインタｐの値を設定する。そして、カレント節点ポインタｐに、選択された子節点の子節点ポインタｐｃ（ｎ）を設定し、カレント節点の深さｓｃを１だけ増加させる（Ｓ７１）。
【００９２】
ユーザが入力手段８により「ホームに戻る」を選択した場合（Ｓ７２）、検索手段６は、カレント節点ポインタｐを０に設定し、カレント節点の深さｓｃを０とする（Ｓ７３）。
【００９３】
ユーザが入力手段８により「上に戻る」を選択した場合（Ｓ７４）、検索手段６は、カレント節点ポインタｐに、親節点ポインタｐｐ（ｓｃ−１）を設定するとともに、カレント節点の深さｓｃを１だけ減少させる（Ｓ７５）。
以上の動作の後に、再びステップＳ４３に戻る。
【００９４】
一方、ステップＳ５２において、子節点数ｎが表示制限個数ｎｍａｘを超えていた場合には、検索手段６は、内部変数として有する表示する子節点の先頭位置を表すインデックスｉの値を、子節点の先頭の位置を表すインデックスｉ０に設定する（Ｓ５５）。
【００９５】
次に、検索手段６は、表示ポインタ｛ｐｄ（０），…，ｐｄ（ｎｍａｘ−１）｝に節点ポインタ｛ｐｃ（ｉ），…，ｐｃ（ｉ＋ｎｍａｘ−１）｝を設定する（Ｓ５６）。ここで、「表示ポインタ」とは、選択メニューに表示するｎｍａｘ個の節点に対応するポインタをいい、検索手段６が内部変数として保有しているものとする。次に、検索手段６は、表示手段７に表示する選択メニューに、表示ポインタ｛ｐｄ（０），…，ｐｄ（ｎｍａｘ−１）｝に対応する節点を追加する（Ｓ５７）。そして、ｉ−ｉ０＜ｎ−ｎｍａｘ−１の場合には、検索手段６は、表示手段７に表示する選択メニューに、「下へ」の選択メニューを追加する（Ｓ５８）。更に、ｉ＞ｉ０のときは、検索手段６は、表示手段７に表示する選択メニューに、「上へ」の選択メニューを追加する（Ｓ５９）。そして、検索手段６は、ユーザが入力手段８により選択メニューを選択するまで待機する（Ｓ６０）。
【００９６】
ここで、ユーザが入力手段８により「下へ」を選択した場合（Ｓ６１）、検索手段６は、表示する子節点の先頭位置を表すインデックスｉの値を１だけ増加させた後（Ｓ６２）、ステップＳ５６に戻る。
【００９７】
また、ユーザが入力手段８により「上へ」を選択した場合（Ｓ６３）、検索手段６は、表示する子節点の先頭位置を表すインデックスｉの値を１だけ減少させた後（Ｓ６４）、ステップＳ５６に戻る。
【００９８】
一方、ユーザが入力手段８によりそれ以外のメニューを選択した場合には、上述のステップＳ７０の動作に移行する。
【００９９】
図１４は表示手段に表示される画像の一例を示したものである。図１４は、図８に示した木構造型データの節点「北海道」を表示している状態を表す。ここでは、子節点の表示制限個数ｎｍａｘは４としている。
【０１００】
図１４（ａ）において、画面の右側には表示データ１０が表示されており、画面の左側に選択メニュー１１が表示されている。選択メニュー１１の最上部には、カレント節点の名称「北海道」が表示されており、ユーザが現在どのこ節点にいるのかを認識できるようになっている。カレント節点の名称の下には、カレント節点の子節点の名称「利尻礼文サロベツ」、「知床」、「阿寒」、「釧路湿原」が表示されている。ここで、節点「北海道」の子節点は、他にも「大雪山」、「支笏洞爺」があり、全部で６個である。しかし、子節点の表示制限個数ｎｍａｘが４なので、画面には、このうちの先頭から４個だけが表示される。４個の子節点の名称の下には、メニュー「下へ」、「上に戻る」、「ホームに戻る」がそれぞれ表示されている。
【０１０１】
ユーザが他の子節点を見たい場合には、選択メニュー１１から「下へ」を選択する。これにより、図１４（ｂ）のように、子節点が１個だけずれて、選択メニューには「知床」、「阿寒」、「釧路湿原」、「大雪山」が表示される。また、子節点の名称の上には、新たに「上へ」のメニューが表示される。
【０１０２】
以上のように、本実施形態によれば、実施形態１でリンク設定手段４が作成した修正された木構造型データをそのまま用いた場合であっても、検索手段６が表示手段に表示する子節点の数を制限することにより、子節点の数が多くてもユーザは画面上から目的の子節点を容易に見つけ出すことができる。また、入力手段８として、音声認識装置を使用する場合には、選択メニューの個数が少ないため、認識率を上げることができる。
【０１０３】
【発明の効果】
以上のように、本発明によれば、原始リンク情報における終端節点から兄弟節点に直接遷移できるため、平均的にデータの検索時のパス長が短くなる。また、終端節点に対して新たに兄弟節点へのリンクを追加するので、特定の節点が極端に枝数が多くなることが防止できる。従って、検索効率の高い木構造型データベースのデータ検索技術を提供できる。
【０１０４】
また、原始リンク情報の根節点以外の節点のリンク情報に対して、その親節点に対するリンクを追加することで、検索時の利便性に優れたデータ検索装置を提供することができる。
【０１０５】
更に、原始リンク情報の根節点以外の節点のリンク情報に対して、その根節点に対するリンクを追加することで、検索時の利便性に優れたデータ検索装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の実施形態１に係るデータ検索装置の機能構成を表すブロック図である。
【図２】原始リンク情報のデータ構造の一例を木グラフで表した図である。
【図３】図２の原始リンク情報リストの構造を表す図である。
【図４】本発明の実施形態１に係るリンク設定手段の動作を表すフローチャートである。
【図５】本発明の実施形態１に係るリンク設定手段の動作を表すフローチャートである。
【図６】本発明の実施形態１に係るリンク設定手段の動作を表すフローチャートである。
【図７】図３に例示した原始リンク情報リストに対して上述のリンク設定処理を行った後に修正リンク情報記憶手段に格納されている修正リンク情報リストの構造を表す図である。
【図８】国立公園案内用の木構造型データの構成を表す図である。
【図９】国立公園案内用の木構造型データの検索時の表示画面を表す図である。
【図１０】本発明の実施形態２に係るリンク設定手段の動作を表すフローチャートである。
【図１１】節点分割処理により分割された木構造型データを表す図である。
【図１２】分割条件をｎ＞ｎｍａｘとした場合の節点分割処理により分割された木構造型データを表す図である。
【図１３】本発明の実施形態３に係るデータ検索装置の検索手段の動作を表すフローチャートである。
【図１４】表示手段に表示される画像の一例を示したものである。
【符号の説明】
１  データ検索装置
２  データ記憶手段
３  原始リンク情報記憶手段
４  リンク設定手段
５  修正リンク情報記憶手段
６  検索手段
７  表示手段
８  入力手段
１０  表示データ
１１  選択メニュー
【図１】
2004348602.tif 000003
【図２】
2004348602.tif 000004
【図３】
2004348602.tif 000005
【図４】
2004348602.tif 000006
【図５】
2004348602.tif 000007
【図６】
2004348602.tif 000008
【図７】
2004348602.tif 000009
【図８】
2004348602.tif 000010
【図９】
2004348602.tif 000011
【図１０】
2004348602.tif 000012
【図１１】
2004348602.tif 000013
【図１２】
2004348602.tif 000014
【図１３】
2004348602.tif 000015
【図１４】
2004348602.tif 000016