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