(57)【特許請求の範囲】
【請求項１】
木構造に基づいて格納されたデータに対して、該木構造の根から幅優先順序で走査し、該木構造の各節点について、スコアを親節点のスコアを利用して再帰的に計算する処理を高速化するための木構造を対象とした演算高速化装置であって、
木構造に対応する、節点ＩＤ，子節点ＩＤのリスト及びコストを含むデータを取得するデータ入力手段と、
入力された前記データから木構造を配列として構築し、該木構造の各節点の子節点が０個または、１個の場合と、２個以上の場合に分けて記憶手段に格納する木構造構築手段と、
子節点が０個または、１個の場合と、２個以上の場合に分けて、節点のスコア計算の繰り返し処理を制御するスコア計算手段と、
を有することを特徴とする木構造を対象とした演算高速化装置。
【請求項２】
前記木構造構築手段は、
各節点毎に、子節点の個数が０個または１個である場合は子節点を一つの節点ＩＤとし、２個以上の場合は節点ＩＤの配列として記憶手段に格納する手段を含み、
前記スコア計算手段は、
前記記憶手段から読み出した配列について、前記子節点の個数が２個以上の場合のみ繰り返し処理を行う手段を含む
請求項１記載の木構造を対象とした演算高速化装置。
【請求項３】
木構造に基づいて格納されたデータに対して、該木構造の根から幅優先順序で走査し、該木構造の各節点について、スコアを親節点のスコアを利用して再帰的に計算する処理を高速化するための木構造を対象とした演算高速化方法であって、
データ入力手段が、木構造に対応するデータを取得するデータ入力ステップと、
木構造構築手段が、入力された前記データから木構造を配列として構築し、該木構造の各節点の子節点が０個または、１個の場合と、２個以上の場合に分けて記憶手段に格納する木構造構築ステップと、
スコア計算手段が、子節点が０個または、１個の場合と、２個以上の場合に分けて、節点のスコア計算の繰り返し処理を制御するスコア計算ステップと、
を行うことを特徴とする木構造を対象とした演算高速化方法。
【請求項４】
前記木構造構築ステップにおいて、
各節点毎に、子節点の個数が０個または１個である場合は子節点を一つの節点ＩＤとし、２個以上の場合は節点ＩＤの配列として記憶手段に格納し、
前記スコア計算ステップにおいて、
前記記憶手段から読み出した配列について、前記子節点の個数が２個以上の場合のみ繰り返し処理を行う
請求項３記載の木構造を対象とした演算高速化方法。
【請求項５】
コンピュータを、
請求項１または２記載の木構造を対象とした演算高速化装置の各手段として機能させるための木構造を対象とした演算高速化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造データの演算高速化方法及び装置及びプログラムに係り、特に、典型的なデータ構造である木構造を利用して格納されたデータに対して、その構造を根から幅優先順序で走査し、木構造中の各節点について、そのスコアを親節点のスコアを利用して再帰的に計算する場面において、処理時間を削減するための木構造データの演算高速化方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
木構造は典型的なデータ構造として様々な場面で幅広く利用される。また、木構造に基づいて格納されたデータに対する典型的な処理として、図１に示すように、木構造の各節点に対するスコアを、その親節点のスコアを利用して再帰的に計算する手法がある。なお、図１において、丸内の数字は節点ＩＤであり、"0.8"等の数字はコストを示す。例えば、木構造の根から各節点への距離は、各節点に対応付けられたコスト[0]と、根節点から親節点までの距離とを用いて再帰的に計算される。図２は、番号"１"が書かれた節点を根とする木構造において、各節点に対する根からの距離を計算した例である。
【０００３】
上記のようなスコア計算を可能とする木構造は、計算機上では各節点に対応するエントリを節点数個格納した配列（以下では、Ｌとする）として表現される。各節点は、当該節点の節点ＩＤと子節点のＩＤの配列を要素として持つ構造体として表現される。図２（Ｂ）の表は、木構造を表現する配列である。なお、配列中では節点は節点ＩＤの順序で格納されているとし、かつ子節点のＩＤは常に節点ＩＤよりも大きいものとする。木構造に対して幅優先探索順序でスコアを計算する一般的な処理は、例えば、非特許文献１のようなアルゴリズムの教科書に記載されている。
【０００４】
図３に幅優先探索順序でスコアを計算する処理の概要を示す。
【０００５】
要素数Ｌのカウンタｉ（ｉ＝１，…，ｌ）を１に初期化し（ステップ１）、ｐを配列Ｌのｉ番目の節点とする（ステップ２）。ｐの子節点の数が０であり（ステップ３、Yes）、ｉが配列Ｌの要素数より小さい場合は（ステップ７,Yes）、ｉ＝ｉ＋１として（ステップ９）、ステップ２の処理に戻り、次の節点の処理を行う。ｉ≧配列Ｌの要素数であれば（ステップ７,No）、当該処理を終了する。
【０００６】
一方、ｐの子節点の数≠０である場合は（ステップ３,No）、子節点のカウンタをｊ＝１とし（ステップ４）、ｐのｊ番目の子節点のスコアを計算し（ステップ５）、ｊ＜ｐの子節点数の場合は（ステップ６,No）、ｊ＝ｊ＋１として（ステップ８）、ステップ５に戻る。ｊ≧ｐの子節点数の場合は、ｉ≧配列Ｌの要素数ｌであれば（ステップ７,No）、当該処理を終了し、ｉ＜配列Ｌの要素数ｌであればｉ＝ｉ＋１として（ステップ９）、ステップ２に戻る。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introduction to Algorithms, third edition", The MIT Press, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、各節点の平均的な子節点の個数が１個ないし０個の場合、小節点を配列として保持してアクセスする上記の従来の手法では、図４に示すように、殆どのノードの子ノードが０個または１個のとき、子ノードを全て配列として保持すると、節点毎に不必要な繰り返し処理における条件分岐が発生するため、処理時間が長くなるという問題がある。
【０００９】
本発明は、上記の点に鑑みなされたもので、繰り返し処理の有無を制御し、演算時間を短縮することが可能な木構造データの演算高速化方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するため、本発明（請求項１）は、木構造に基づいて格納されたデータに対して、該木構造の根から幅優先順序で走査し、該木構造の各節点について、スコアを親節点のスコアを利用して再帰的に計算する処理を高速化するための木構造を対象とした演算高速化装置であって、
木構造に対応するデータを取得するデータ入力手段と、
入力された前記データから木構造を配列として構築し、該木構造の各節点の子節点が０個または、１個の場合と、２個以上の場合に分けて記憶手段に格納する木構造構築手段と、
子節点が０個または、１個の場合と、２個以上の場合に分けて、節点のスコア計算の繰り返し処理を制御するスコア計算手段と、を有する。
【００１１】
また、本発明（請求項２）は、前記木構造構築手段において、
各節点毎に、子節点の個数が０個または１個である場合は子節点を一つの節点ＩＤとし、２個以上の場合は節点ＩＤの配列として記憶手段に格納する手段を含み、
前記スコア計算手段において、
前記記憶手段から読み出した配列について、前記子節点の個数が２個以上の場合のみ繰り返し処理を行う手段を含む。
【発明の効果】
【００１２】
本発明によれば、殆どの節点の子節点が１個ないし０個のときに、それに特化した処理を行うことによって余計な繰り返し分の実行回数を削減できる。
【００１３】
また、ダミーの記憶領域を一つ用意して、子節点が０個のときにその記憶領域に対する計算を行うことにより、条件分岐の回数を減らし、実行時間を削減できる。
【００１４】
これにより、多くの節点において子節点の個数が０個ないし１個である場合は、その根節点から葉節点へ、親節点のスコアを用いて再帰的にスコアを計算する際に、必要となる処理時間を削減することができる。
【図面の簡単な説明】
【００１５】
【図１】木構造における再帰的にスコアを更新する例である。
【図２】構造に基づいたスコア計算の例である。
【図３】従来の幅優先探索順序でスコアを計算する処理のフローチャートである。
【図４】本従来の問題点を示す図である。
【図５】本発明の概要を示す図である。
【図６】本発明の一実施の形態における木構造データの演算高速化装置の構成図である。
【図７】本発明の一実施の形態における動作のフローチャートである。
【図８】本発明の一実施の形態における入力データの例である。
【図９】本発明の一実施の形態における木構造をメモリに保持した例である。
【図１０】本発明の一実施の形態におけるスコア計算処理部のフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面と共に本発明の実施の形態を説明する。
【００１７】
図５は、本発明の概要を示す図である。
【００１８】
本発明は、演算時間の短縮を目的として、木構造の各節点について、その子節点が０個または１個の場合と、それ以上の個数の場合とで、構造体に記憶する内容を変化させ、かつ、スコア計算時の処理も変化させる。具体的には、同図（Ａ）に示す各ノードについて、同図（Ｂ）に示すように、子ノードの配列ではなく、唯一の子ノード（子節点が０または１個のノード）を記憶しておく。なお、２つ以上の子ノードをもつノードについては事前にチェックしておき、処理を分けるものとする。節点の個数が０個または１個のときには、各節点の構造体中で子節点を一つの節点ＩＤとして保持する。２個以上のときには節点ＩＤの配列（図５（Ｂ）の例では、子節点ＩＤの配列{2,3}，{4,5}）として保持する。そして、計算においては子節点の個数に応じて処理内容を変化させる。
【００１９】
以下に詳細に説明する。
【００２０】
図６は、本発明の一実施の形態における木構造データの演算高速化装置の構成を示す。
【００２１】
同図に示す装置は、データ入力部１、木構造構築処理部２、スコア計算処理部３、計算結果出力部４、メモリ５から構成される。
【００２２】
データ入力部１は、外部から木構造を構築するために必要となる情報を受け取る。すなわち、各節点について、節点ＩＤ、全ての小節点の節点ＩＤ、及び、実数で与えられるコストを受け取る。受け取ったデータは木構造構築処理部２に渡す。
【００２３】
木構造構築処理部２は、受け取ったデータを元に木構造を配列として構築し、メモリ５に格納する。
【００２４】
スコア計算処理部３は、メモリ５から木構造の配列を読み込み、スコア計算処理を実行し、結果を計算結果出力部４に渡す。
【００２５】
計算結果出力部４は、各節点に対するスコアを外部に出力する。
【００２６】
図７は、本発明の一実施の形態における動作のフローチャートである。
【００２７】
ステップ１０１）  データ入力部１は、入力されたデータを取得する。入力データの例を図８に示す。同図（Ａ）は、木構造に対応する入力データであり、同図（Ｂ）は、同図（Ａ）のデータをテーブルで表現したものであり、各節点に対し、当該節点ＩＤと子節点ＩＤのリスト、及びコストが与えられる。
【００２８】
ステップ１０２）  木構造構築部２は、入力されたデータをメモリ５上に保持する。メモリ５に保持されるデータの例を図８に示す。同図（Ｂ）は、図８のデータ計算機上での表現方法となる。各節点につき、一つの構造体を準備し、そこに節点ＩＤ、第１子節点の節点ＩＤまたは子節点の数と小節点ＩＤを格納した配列を構築し、そして、各節点ＩＤ毎にコストを格納する。子節点の数が１個または０個のときには、第一子節点の節点ＩＤを保持し、そうでなければ、子節点ＩＤを格納した配列と子節点の個数とを保持する。子節点が2個以上ある節点のIDを格納した配列をＭとする。図9(C) は配列Mの例である。なお、Ｍ中の節点ＩＤは昇順で格納されているものとする。
【００２９】
ステップ１０３）  スコア計算処理部３は、ステップ１０２でメモリ５に格納されたデータを読み出し、木構造に対して各コストからスコアの計算処理を行う。当該処理を図１０のフローチャートを用いて説明する。
【００３０】
ステップ２０１）  配列Ｍ（図９（Ｃ）の添え字（カウンタｉ）をｉ＝１に初期化する。
【００３１】
ステップ２０２）  配列Ｌ（全節点ＩＤ）の添え字（カウンタｊ）をｊ＝１に初期化する。
【００３２】
ステップ２０３）  配列Ｍのｉ番目の値（Ｍ[i]と記す）をlとする。
【００３３】
ステップ２０４）  以下、ステップ２０５〜２０７の処理をｊ＜lの間繰り返す。
【００３４】
ステップ２０５）  ｐ＝Ｌ[ｊ]として節点ｐをメモリ５から取り出す。
【００３５】
ステップ２０６）  ｐの第１子節点についてスコアを計算する。当該節点のスコア計算とは、メモリ５の親節点のスコアと各節点に割り当てられたコストを入力として、節点のスコアを返す演算のことであり、当該条件を満たすならば、演算の種類及びスコア形式（ベクトルまたはスカラー）は任意である。
【００３６】
ステップ２０７）  ｊを１増加させる。
【００３７】
ステップ２０８）  ｐ＝Ｌ[j]として、メモリ５から節点ｐを取り出す。
【００３８】
ステップ２０９）  添え字ｋをｋ＝１とする（ｋ＝１，…，ｐの子節点数）。
【００３９】
ステップ２１０）  ｐのｋ番目の子節点についてスコアを計算する。スコア計算については、上記のステップ２０６と同様である。
【００４０】
ステップ２１１）  ｉ＝ｉ＋１とする。
【００４１】
ステップ２１２）  ｊ＝ｊ＋１とする。
【００４２】
ステップ２１３）  iが配列Ｌの要素数より大きいか、すなわち、配列Ｍの全ての要素について処理が完了したかを判定し、処理が完了しているならばカウンタjをインクリメントしながらステップ２０５とステップ２０６と同様の処理を配列Lの最後まで行い終了する。そうでなければ、ステップ２０３に移行する。
【００４３】
ステップ１０４）  計算結果出力部４は、上記の処理により求められた各節点におけるスコアを表示装置や記憶手段に出力する。
【００４４】
上記のように、木構造の演算処理において、子ノードが複数あるときは繰り返し処理が必要となるが、子ノードが１個あるいは０個であれば繰り返し処理は不要であるので、子ノードが２個以上か否かによってデータ構造を分けて図９（Ｂ）に示すように記憶し、繰り返しの処理の有無を制御する。これにより、演算時間を短縮することができる。
【００４５】
上記の図６に示す装置の各構成要素の動作をプログラムとして構築し、木構造データの演算高速化装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００４６】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００４７】
１  データ入力部
２  木構造構築処理部
３  スコア計算処理部
４  計算結果出力部
５  メモリ
【図１】
0005670931.tif 000002
【図２】
0005670931.tif 000003
【図３】
0005670931.tif 000004
【図４】
0005670931.tif 000005
【図５】
0005670931.tif 000006
【図６】
0005670931.tif 000007
【図７】
0005670931.tif 000008
【図８】
0005670931.tif 000009
【図９】
0005670931.tif 000010
【図１０】
0005670931.tif 000011