(57)【要約】【課題】  階層型のメモリ構造において、分岐が多く横長でアンバランスな木構造の参照局所性を向上させる。【解決手段】  本発明は、集約起点ノードを取得して最初の処理対象ノードとする初回処理対象ノード設定手段と、処理対象ノードの子ノード集合を木構造記憶手段から参照確率と共に抽出しノード情報記憶手段に格納し、該ノード情報記憶手段のノード集合中で最も参照確率が高いノードを次の処理対象ノードとし、Ｊ個の葉方向にＫ個のノード列を該ノード情報記憶手段から抽出して、パス情報記憶手段に格納するパス情報取得手段と、パス情報記憶手段に格納されているパス集合を単体物理ノードに集約して最適化木構造記憶手段に格納し、該単体物理ノード以外のノードから構成される部分木を、該単体物理ノードの子ノードとして再配置する再配置手段と、を有する。【選択図】  図２
2014126882.tif 000002
【特許請求の範囲】
【請求項１】
長さＮの文字列の中から任意の部分文字列Ｍを探索する際に、入力された木構造が分岐の多い横長の構造であるとき、該木構造を再構成する木構造の再構成装置であって、
前記木構造の各ノードの識別子、接続関係、参照確率を含む入力木構造情報が入力されると、木構造記憶手段に格納する木構造最適化処理手段と、
集約起点ノード以下のノードを所定のルールに基づいて集約する部分木集約処理手段と、
を有し、
前記部分木集約処理手段は、
前記集約起点ノードを取得して最初の処理対象ノードとする初回処理対象ノード設定手段と、
処理対象ノードの子ノード集合を前記木構造記憶手段から参照確率と共に抽出しノード情報記憶手段に格納し、該ノード情報記憶手段のノード集合中で最も参照確率が高いノードを次の処理対象ノードとし、Ｊ個の葉方向にＫ個のノード列を該ノード情報記憶手段から抽出して、パス情報記憶手段に格納するパス情報取得手段と、
前記パス情報記憶手段に格納されているパス集合を単体物理ノードに集約して最適化木構造記憶手段に格納し、該単体物理ノード以外のノードから構成される部分木を、該単体物理ノードの子ノードとして再配置する再配置手段と、
を有することを特徴とする部分木集約による木構造の再構成装置。
【請求項２】
前記部分木集約処理手段は、
前記処理対象ノードとなったノードの情報を前記ノード情報記憶手段から削除し、次の処理対象ノードとなったノードの情報を該ノード情報記憶手段に格納する手段を含む
請求項１記載の部分木集約による木構造の再構成装置。
【請求項３】
長さＮの文字列の中から任意の部分文字列Ｍを探索する際に、入力された木構造が分岐の多い横長の構造であるとき、該木構造を再構成する木構造の再構成方法であって、
木構造最適化処理手段、部分木集約処理手段、木構造記憶手段、ノード情報記憶手段、パス情報記憶手段、最適化木構造記憶手段を有し、
前記木構造最適処理手段が、前記木構造の各ノードの識別子、接続関係、参照確率を含む入力木構造情報が入力されると、前記木構造記憶手段に格納する木構造最適化処理ステップを行い、
前記部分木集約処理手段が、
前記集約起点ノードを取得して最初の処理対象ノードとする初回処理対象ノード設定ステップと、
処理対象ノードの子ノード集合を前記木構造記憶手段から参照確率と共に抽出し、前記ノード情報記憶手段に格納し、該ノード情報記憶手段のノード集合中で最も参照確率が高いノードを次の処理対象ノードとし、Ｊ個の葉方向にＫ個のノード列を該ノード情報記憶手段から抽出して、前記パス情報記憶手段に格納するパス情報取得ステップと、
前記パス情報記憶手段に格納されているパス集合を単体物理ノードに集約して最適化木構造記憶手段に格納し、該単体物理ノード以外のノードから構成される部分木を、該単体物理ノードの子ノードとして再配置する再配置ステップと、
を行うことを特徴とする部分木集約による木構造の再構成方法。
【請求項４】
前記部分木集約処理ステップにおいて、
前記処理対象ノードとなったノードの情報を前記ノード情報記憶手段から削除し、次の処理対象ノードとなったノードの情報を該ノード情報記憶手段に格納する
請求項３記載の部分木集約による木構造の再構成方法。
【請求項５】
コンピュータを、
請求項１または２に記載の部分木集約による木構造の再構成装置の各手段として機能させるための部分木集約による木構造の再構成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、部分木集約による木構造の再構成装置及び方法及びプログラムに係り、特に、木構造を用いて文字列を探索する際に、探索対象の文字列から構成されたアンバランスな木構造（トライ木やパトリシア木）を再構成し、より探索の際に参照局所性を改善するための部分木集約による木構造の再構成装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
文字列探索の木の最適化方法として、文字列探索のための木構造における冗長的なポインタと探索を削減するために、部分的なノードをカップリングすることで、ポインタの数を削減し、参照局所性を限定的に改善する方法がある（例えば特許文献1参照）。
【０００３】
また、文字列探索の木構造において、根ノードから単一の葉ノードまでの全ノード集合を単体物理ノードに再帰的に集約することで参照局所性を改善する方法がある（例えば、非特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許４４０２１２０号公報
【非特許文献】
【０００５】
【非特許文献１】Roberto Gross and Giuseppe Ottaviano, 「Fast Compressed Tries through Path Decompositions」, ALENEX, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記従来の特許文献１の手法では、探索対象の文字列から構築した木構造の形や各ノードの参照確率によって、参照局所性が極端に悪くなり、探索速度が著しく悪化するケースがある。また、非特許文献１の手法では、特に、高さのある木構造では、参照確率が低いアクセスされないノードまで集約されるため非効率である。
【０００７】
本発明は、上記の点に鑑みなされたもので、階層型のメモリ構造において、分岐が多く横長でアンバランスな木構造の参照局所性を向上させることにより、探索速度を高速化可能な部分木集約による木構造の再構成装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明（請求項１）は、長さＮの文字列の中から任意の部分文字列Ｍを探索する際に、入力された木構造が分岐の多い横長の構造であるとき、該木構造を再構成する木構造の再構成装置であって、
前記木構造の各ノードの識別子、接続関係、参照確率を含む入力木構造情報が入力されると、木構造記憶手段に格納する木構造最適化処理手段と、
集約起点ノード以下のノードを所定のルールに基づいて集約する部分木集約処理手段と、
を有し、
前記部分木集約処理手段は、
前記集約起点ノードを取得して最初の処理対象ノードとする初回処理対象ノード設定手段と、
処理対象ノードの子ノード集合を前記木構造記憶手段から参照確率と共に抽出しノード情報記憶手段に格納し、該ノード情報記憶手段のノード集合中で最も参照確率が高いノードを次の処理対象ノードとし、Ｊ個の葉方向にＫ個のノード列を該ノード情報記憶手段から抽出して、パス情報記憶手段に格納するパス情報取得手段と、
前記パス情報記憶手段に格納されているパス集合を単体物理ノードに集約して最適化木構造記憶手段に格納し、該単体物理ノード以外のノードから構成される部分木を、該単体物理ノードの子ノードとして再配置する再配置手段と、を有する。
【０００９】
また、本発明（請求項２）は、前記部分木集約処理手段において、
前記処理対象ノードとなったノードの情報を前記ノード情報記憶手段から削除し、次の処理対象ノードとなったノードの情報を該ノード情報記憶手段に格納する手段を含む。
【発明の効果】
【００１０】
上記のように、本発明によれば、長さＮの文字列の中から任意の部分文字列Ｍ（N>>M前提）を効率的に探索するための木構造（トライ木）を構成した場合に起こるアンバランスな構造、特に分岐が多い横長な木構造のパスの中で、参照確率の高い根からＪ個の葉方向、Ｋ個のノード列を単体物理ノードにまとめてメモリ上の隣接領域に配置し、その他のノードから構成される部分木はその集約ノードの子として再配置するため、アンバランスだった木構造全体が平衡化して階層型メモリにおける参照局所性が向上し、結果として探索速度が改善される。
【図面の簡単な説明】
【００１１】
【図１】本発明の概要を示す図である。
【図２】本発明の一実施の形態における木構造再構成装置の構成例である。
【図３】本発明の一実施の形態における木構造入力装置から入力されるデータ例である。
【図４】本発明の一実施の形態におけるパス情報記憶部のデータフォーマットである。
【図５】本発明の一実施の形態における木構造最適化処理部のフローチャートである。
【図６】本発明の一実施の形態における部分木集約処理部のフローチャートである。
【図７】本発明の一実施の形態における入力の特徴と再構成の具体例である。
【図８】本発明の一実施の形態におけるパス情報記憶部の更新例である。
【図９】本発明の一実施の形態における集約されたノード内の探索の具体例である。
【発明を実施するための形態】
【００１２】
以下、図面と共に本発明の実施の形態を説明する。
【００１３】
図１は、本発明の概要を示す図である。
【００１４】
本発明は、文字列探索のためのアンバランスな木構造を最適化するものであり、具体的には、探索対象の文字列から構成されたアンバランスな木構造（トライ木／パトリシア木）を再構成することでより探索の際の参照局所性を改善した木構造を生成する。
【００１５】
同図（ａ）は横長の木構造の例である。本発明では、このように探索対象の文字列から当該入力文字列の特性に依存したアンバランスな木が入力されるものとする。同図（ａ）のような木構造から、アンバランス性を改善し、同図（ｂ）に示すように、全体的に均衡のとれた最適化された木構造を出力する。
【００１６】
図２は、本発明の一実施の形態における木構造再構成装置の構成例である。
【００１７】
同図に示す木構造再構成装置１０は、木構造最適化処理部１１、集約起点候補ノード記憶部１２、部分木集約処理部１３、ノード情報記憶部１４、最適化木構造記憶部１５、木構造記憶部１６、パス情報記憶部１７を有する。
【００１８】
木構造最適化処理部１１は、木構造入力装置１と結果出力装置２に接続されており、木構造入力装置１からの木構造データの入力を受け付け、木構造記憶部１６に格納すると共に、木構造の最適化が終了すると、最適化木構造記憶部１５に格納されている最適化結果を結果出力装置２に出力する。
【００１９】
集約起点候補ノード記憶部１２は、木構造最適化処理部１１から設定された根ノードと、集約起点候補ノードが格納される。
【００２０】
ノード情報記憶部１４は、単一パス集約処理部１３から指定された根のノードに対応するノード情報が格納される。なお、ノード情報記憶部１４は、後述する図６のフローチャートが終了した時点で消去される一時的な記憶部である。
【００２１】
最適化木構造記憶部１５は、木構造最適化処理部１１で最適化処理されたノード番号の集合が格納される。
【００２２】
木構造記憶部１６は、木構造最適化処理部１１から渡された、図３に示すような入力木構造（ノード番号、隣接ノード番号、参照確率）が格納され、単一パス集約処理部１３が、当該木構造記憶部１６から処理対象ノードとしたノード情報を読み込む。
【００２３】
パス情報記憶部１７は、部分木集約処理部１３で決定されたパス集合を格納する。パス情報記憶部１７は、図４に示すように、更新順序番号とパスを構成するノード番号を格納する。部分木集約処理部１３の実行前は何も格納されていない。
【００２４】
以下、上記の構成における処理を説明する。
【００２５】
図５は、本発明の一実施の形態における木構造最適化処理部のフローチャートである。
【００２６】
ステップ４００）  木構造最適化処理部１１は、木構造入力装置１から文字列探索のための入力木構造を受け取るまで待機する。
【００２７】
ステップ４０５）  木構造入力装置１から、図３に示すような入力木構造を取得する。入力されるデータは、ノード番号、隣接ノード番号、参照確率であり、同図（ｂ）に示すように横に長い木構造のイメージである。木構造最適化処理部１１は、入力された入力木構造を木構造記憶部１６に格納し、指定された根のノードを集約起点候補ノード記憶部１２に挿入する。また、木構造最適化処理部１１は、部分木集約処理部１３に集約起点ノードの情報を出力し、部分木集約処理部１３は木構造記憶部１６から当該集約起点ノードに対応する木構造を処理対象ノードとして抽出し、ノード情報記憶部１４に格納する。ノード情報記憶部１４には、ノード番号、隣接ノード番号、参照確率が格納される。
【００２８】
ステップ４１０）  集約回数用のカウンタｉを０で初期化する。
【００２９】
ステップ４１５）  集約起点候補ノード記憶部１２から集約起点となるノードを１つ取得する。最初の集約起点ノードは、ステップ４０５で得られた根のノードであり、次回以降は集約起点候補ノード記憶部１２の中で更新順序番号が最も小さいノードを集約起点ノードとして取得する。また、取得した当該ノードを当該集約起点候補ノード記憶部１２から削除する。これにより、集約起点候補ノード記憶部１２に残るのは未処理の候補ノードのみとなる。
【００３０】
ステップ４２０）  ステップ４１５で取得した集約起点ノードを部分木集約処理部１３に入力し、部分木集約処理部１３に、図６に示す処理を実行させる。
【００３１】
ステップ４２５）  木構造最適化処理部１１は、集約起点ノードノード記憶部１２内に存在する候補数Ｓを取得し、Ｓが０より大きければステップ４３０に移行し、そうでなければ、最適化完了通知を結果出力装置２に出力して当該木構造最適化処理部１１の処理を終了する。
【００３２】
ステップ４３０）  カウンタｉを１増加させ（ｉ=ｉ＋１）、ｉが、集約回数の入力パラメータであるNUM_COMPACTIONより小さい場合は、ステップ４１５に移行し、そうでない場合はステップ４３５に移行する。なお、NUM_COMPACTION（集約回数）は、ステップ４１５〜４３０を繰り返す回数であり、事前に決定され、入力手段（図示せず）から入力される、または、メモリ（図示せず）に格納されているものとする。
【００３３】
ステップ４３５）  集約起点候補ノード記憶部１２内に残された集約対象とならなかったノード集合を最適化構造記憶部１５に記録する。なお、NUM_COMPACTIONは、予め設定されているものとする。当該処理は、図６に示す部分木集約処理部１３の処理において集約対象とならなかった集約起点候補ノード記憶部１２内の残りのノード集合を最適化構造記憶部１５に格納することで、当該最適化構造記憶部１５に木全体の情報が記録されることになる。
【００３４】
次に、上記のステップ４２０で実行される部分木集約処理部１３の処理について説明する。
【００３５】
図６は、本発明の一実施の形態における部分木集約処理部のフローチャートであり、図７は、パス情報記憶部の更新例を示す。
【００３６】
ステップ５００）  部分木集約処理部１３は、木構造最適化部１１から入力された集約起点候補ノードを処理対象ノードとする。パス情報記憶部１７には、この時点ではまだ何も格納されていない。
【００３７】
ステップ５０５）  集約ノード数のためのカウンタｉを０で初期化する（ｉ＝０）。
【００３８】
ステップ５１０）  処理対象ノードの子ノード集合を木構造記憶部１６から読み出して、参照確率と組にしてノード情報記憶部１４に記録する。なお、子ノードは入力された木構造の隣接ノード番号を参照することにより抽出する。
【００３９】
ステップ５１５）  ノード情報記憶部１４に記録されているノード集合の中で最も参照確率の高いノードを探索し、該当ノードがある場合はステップ５２０に移行し、ない場合は当該処理を終了する。なお、参照確率が同値のノードがある場合は、ノード情報記憶部１４に先に記録されたノードを選択するものとする。
【００４０】
ステップ５２０）  ステップ５１５で該当したノードを取得し、当該ノードをノード情報記憶部１４から削除する。
【００４１】
ステップ５２５）  取り出したノードを次の処理対象ノードとする。
【００４２】
ステップ５２７）  上記の処理対象ノードに設定された以外の子ノードを全て集約起点候補ノード記憶部１２に挿入する。集約起点候補ノード記憶部１２は更新順序番号毎にノード番号が格納され、先頭から順に参照される。
【００４３】
ステップ５３０）  処理対象ノードと現在の集約起点ノードとの距離Ｓを求める。ここで、距離Ｓとは、処理対象ノードと現在の集約起点ノード間のノード数を指す。距離Ｓが所定の数Kより小さい場合はステップ５１０に戻り、距離ＳがＫ以上の場合はステップ５３５に移行する。
【００４４】
ステップ５３５）  処理対象ノードと集約起点ノード間のパスをパス情報記憶部１７に記録する。
【００４５】
ステップ５４０）  カウンタｉをインクリメントし（ｉ＝ｉ＋１）、ｉが所定の数Ｊより小さければステップ５１５に移行し、ｉがＪ以上である場合はステップ５４５に移行する。
【００４６】
ステップ５４５）  パス情報記憶部１７から決定したパス集合を取得する。
【００４７】
ステップ５５０）  パス集合から集約ノードとしてまとめた部分木ノードを構成し、その他のノードから構成される部分木は当該集約ノードの子ノードとして最適化木構造記憶部１５に格納する。[0]
【００４８】
以下、上記の部分木集約処理部１３の処理を具体的に説明する。
【００４９】
図７は、本発明の一実施の形態における入力の特徴と再構成の具体例を示し、図８は図７の例のおけるパス情報記憶部の更新例を示す。
【００５０】
木構造最適処理部１１が、木構造入力装置１から取得した木構造のデータを木構造記憶部１６に出力し、集約起点ノードを集約起点候補ノード記憶部１２及び部分木集約処理部１３に出力しているものとする。木構造記憶部１６に格納される木構造は図７（ａ）のように分岐が多く横長な木構造である。
【００５１】
部分木集約処理部１３は、入力された集約起点ノードを処理対象ノードする。また、当該処理対象ノードの子ノード集合を木構造記憶部１６から読み出して、参照確率と組にしてノード情報記憶部１４に格納する（ステップ５１０）。図７の例では、参照確率の高い根からＪ個の葉方向Ｋ個の（Ｊ＝３／Ｋ＝３とする）ノード列を単体物理ノードに集約する。なお、ノードの参照確率は、そのノードを根とした場合の木全体の合計参照確率とする。図８に示すように、１回目（ｊ＝１）では、ノード番号［１］［２］［４］でパス構成し、２回目（ｊ＝２）では、ノード番号［１］［７］［８］でパスを構成し、３回目（ｊ＝３）では、［１］［７］［９］でパスを構成し、これらのパスはパス情報記憶部１７に格納される（ステップ５３５）。図７の例では、Ｊ＝３，Ｋ＝３であるので、上記の１〜３回目までの処理でステップ５１０〜５４０の処理が終了する。
【００５２】
次に、部分木集約処理部１３は、パス情報記憶部１７に格納されたパス集合（図８（ｂ））を読み込み（ステップ５４５）、当該パス集合から集約部分木ノードを構成し最適化構造記憶部１５に格納し、パス情報記憶部１７の情報を削除する。（ステップ５５０）。
【００５３】
図７の例では、ノード［１］［２］［４］［７］［８］［９］が集約され、メモリ（図示せず）の隣接領域に配置される。次に、部分木（図７（ｂ）の点線の三角）に対して、集約されたノードの子ノードの参照確率が最も高いノードを次の処理対象ノード（図７（ｂ）のノード［１０］に対して上記の処理を行う。図７（ｂ）では、ノード［１０］を集約起点ノードとして集約したもので、ノード［１０］の子ノードが［１１］［１２］となった例である。このように、再構成された同様の集約を再帰的に実施する。
【００５４】
上記のようにして最適化木構造記憶部１５に格納された集約されたノード群をメモリ（図示せず）上の隣接領域に配置し、部分木を探索することにより次に探索すべき部分木を決定する。図９の例において、ノード［１１］を探索する際に、メモリ上の集約されたノード群のノード［１］⇒［７］から当該ノード［７］に対応する部分木［１０］にジャンプし、目的とするノード［１１］を探索することができる。
【００５５】
なお、上記の図２の木構造再構成装置の各構成要素の動作をプログラムとして構築し、木構造再構成装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５６】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５７】
１  木構造入力装置
２  結果出力装置
１０  木構造再構成装置
１１  木構造最適化処理部
１２  集約起点候補ノード記憶部
１３  部分木集約処理部
１４  ノード情報記憶部
１５  最適化木構造記憶部
１６  木構造記憶部
【図１】
2014126882.tif 000003
【図２】
2014126882.tif 000004
【図３】
2014126882.tif 000005
【図４】
2014126882.tif 000006
【図５】
2014126882.tif 000007
【図６】
2014126882.tif 000008
【図７】
2014126882.tif 000009
【図８】
2014126882.tif 000010
【図９】
2014126882.tif 000011