(57)【特許請求の範囲】
【請求項１】
トライ木構造を有する第一のレコード群と第二のレコード群とをマージソートする装置のコンピュータで実行することが可能な方法において、
前記コンピュータが、
前記第一のレコード群及び第二のレコード群を取得する第一の工程と、
取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する第二の工程と、
前記キー情報よりも前記深さ情報を優先的に比較することにより、逐次的にマージソートする第三の工程と
を含む方法。
【請求項２】
前記深さ情報は、階層が深いほど大きい値に設定してあり、
前記コンピュータの前記第三の工程は、
取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する工程と、
一方の前記深さ情報の方が大きい場合には、前記深さ情報が大きい方の前記キー情報を出力する工程と、
前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する工程と、
前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する工程と
を含む請求項１に記載の方法。
【請求項３】
前記深さ情報は、階層が深いほど小さい値に設定してあり、
前記コンピュータの前記第三の工程は、
取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する工程と、
一方の前記深さ情報の方が小さい場合には、前記深さ情報が小さい方の前記キー情報を出力する工程と、
前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する工程と、
前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する工程と
を含む請求項１に記載の方法。
【請求項４】
トライ木構造を有する第一のレコード群と第二のレコード群とをマージソートする装置において、
前記第一のレコード群及び第二のレコード群を取得するレコード群取得手段と、
取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する深さ情報付与手段と、
前記キー情報よりも前記深さ情報を優先的に比較することにより、逐次的にマージソートするソート手段と
を備える装置。
【請求項５】
前記深さ情報は、階層が深いほど大きい値に設定してあり、
前記ソート手段は、
取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する比較手段と、
該比較手段での結果に基づいて前記キー情報を出力する出力手段と
を備え、
該出力手段は、
一方の前記深さ情報の方が大きい場合には、前記深さ情報が大きい方の前記キー情報を出力する第一の出力を、
前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する第二の出力を、
前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する第三の出力を、それぞれ実行する請求項４に記載の装置。
【請求項６】
前記深さ情報は、階層が深いほど小さい値に設定してあり、
前記ソート手段は、
取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する比較手段と、
該比較手段での結果に基づいて前記キー情報を出力する出力手段と
を備え、
該出力手段は、
一方の前記深さ情報の方が小さい場合には、前記深さ情報が小さい方の前記キー情報を出力する第一の出力を、
前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する第二の出力を、
前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する第三の出力を、それぞれ実行する請求項４に記載の装置。
【請求項７】
トライ木構造を有する第一のレコード群と第二のレコード群とをマージソートする装置で実行することが可能なコンピュータプログラムにおいて、
前記装置を、
前記第一のレコード群及び第二のレコード群を取得するレコード群取得手段、
取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する深さ情報付与手段、及び
前記キー情報よりも前記深さ情報を優先的に比較することにより、逐次的にマージソートするソート手段
として機能させるコンピュータプログラム。
【請求項８】
前記深さ情報は、階層が深いほど大きい値に設定してあり、
前記ソート手段を、
取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する比較手段、及び
該比較手段での結果に基づいて前記キー情報を出力する出力手段
として機能させ、
該出力手段を、
一方の前記深さ情報の方が大きい場合には、前記深さ情報が大きい方の前記キー情報を出力する第一の出力を、
前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する第二の出力を、
前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する第三の出力を、それぞれ実行する手段として機能させる請求項７に記載のコンピュータプログラム。
【請求項９】
前記深さ情報は、階層が深いほど小さい値に設定してあり、
前記ソート手段を、
取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する比較手段、及び
該比較手段での結果に基づいて前記キー情報を出力する出力手段
として機能させ、
該出力手段を、
一方の前記深さ情報の方が小さい場合には、前記深さ情報が小さい方の前記キー情報を出力する第一の出力を、
前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する第二の出力を、
前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する第三の出力を、それぞれ実行する手段として機能させる請求項７に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トライ木構造の階層の深さを示す深さ情報をメタデータとして付与することにより、トライ木構造を有するレコード群を高い効率でマージソートする方法、装置及びコンピュータプログラムに関する。
【背景技術】
【０００２】
トライ木構造を有するレコード群を降順又は昇順にマージソートする場合、順次１レコードずつ比較する必要があるため、演算処理負荷は比較的大きい。従来は、トライ木構造に着目して、ポインタを用いたトライ木構造に対する操作、あるいはメモリへのランダムアクセス等により、マージソートに要する時間を短縮するよう工夫していた。
【０００３】
例えば特許文献１には、異なるテーブルに含まれているレコードをマージソートする場合において、トライ木構造を有しているので、各トライ木へのリンク情報を活用することで演算処理効率を向上させるテーブル処理方法が開示されている。また、特許文献２には、トライ木を生成する場合に、１ノードに対して１個のタグキーを対応付けており、検索処理等を実行する場合に、比較対象となるノードの領域をタグキーにより絞り込むことで検索時間を短縮するトライ木生成装置が開示されている。
【０００４】
さらに特許文献３には、注目順位に対応する階層のノードを示す前回の探索経路情報を記憶しておき、前回の検索条件と前方一致する検索条件での検索を、探索木上の探索範囲を限定して行うことで検索をより高速化する検索装置が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１３−１４３０４０号公報
【特許文献２】国際公開第２０１０／１０６６８０号
【特許文献３】国際公開第２０１３／１０８３３３号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１乃至３では、トライ木構造を利用すること、及び検索条件を記憶することにより、全体として検索時間やマージソートに要する時間を短縮している。しかし、トライ木構造の階層が深い場合、あるいは階層構造が複雑である場合等においては、結局はポインタ等を用いてトライ木構造を指定する、あるいはメモリへランダムアクセスする必要が生じるので、結果として検索時間やマージソートに要する時間を短縮することができないおそれがあるという問題点があった。
【０００７】
また、例えばＦＰＧＡを用いた装置（ソータ）のように固定長のキー情報によるマージソートにしか対応していない場合、可変長のキー情報でマージソートするためには、両方に対応するようハードウェアを更新する必要が生じ、コストアップ要因となる。さらに、固定長のキー情報でマージソートするのに要する時間に比べて、可変長のキー情報でマージソートするのに要する時間の方が比較的長くなる。したがって、可変長のキー情報を用いてマージソートする場合には、マージソートするのに要する時間を短縮することが困難である。
【０００８】
本発明は斯かる事情に鑑みてなされたものであり、トライ木構造の階層の深さを示す深さ情報をメタデータとして付与することにより、トライ木構造を有するレコード群を高い効率でマージソートする方法、装置及びコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために第１発明に係る方法は、トライ木構造を有する第一のレコード群と第二のレコード群とをマージソートする装置のコンピュータで実行することが可能な方法において、前記コンピュータが、前記第一のレコード群及び第二のレコード群を取得する第一の工程と、取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する第二の工程と、前記キー情報よりも前記深さ情報を優先的に比較することにより、逐次的にマージソートする第三の工程とを含む。
【００１０】
また、第２発明に係る方法は、第１発明において、前記深さ情報は、階層が深いほど大きい値に設定してあり、前記コンピュータの前記第三の工程は、取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する工程と、一方の前記深さ情報の方が大きい場合には、前記深さ情報が大きい方の前記キー情報を出力する工程と、前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する工程と、前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する工程とを含む。
【００１１】
また、第３発明に係る方法は、第１発明において、前記深さ情報は、階層が深いほど小さい値に設定してあり、前記コンピュータの前記第三の工程は、取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する工程と、一方の前記深さ情報の方が小さい場合には、前記深さ情報が小さい方の前記キー情報を出力する工程と、前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する工程と、前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する工程とを含む。
【００１２】
次に、上記目的を達成するために第４発明に係る装置は、トライ木構造を有する第一のレコード群と第二のレコード群とをマージソートする装置において、前記第一のレコード群及び第二のレコード群を取得するレコード群取得手段と、取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する深さ情報付与手段と、前記キー情報よりも前記深さ情報を優先的に比較することにより、逐次的にマージソートするソート手段とを備える。
【００１３】
また、第５発明に係る装置は、第４発明において、前記深さ情報は、階層が深いほど大きい値に設定してあり、前記ソート手段は、取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する比較手段と、該比較手段での結果に基づいて前記キー情報を出力する出力手段とを備え、該出力手段は、一方の前記深さ情報の方が大きい場合には、前記深さ情報が大きい方の前記キー情報を出力する第一の出力を、前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する第二の出力を、前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する第三の出力を、それぞれ実行する。
【００１４】
また、第６発明に係る装置は、第４発明において、前記深さ情報は、階層が深いほど小さい値に設定してあり、前記ソート手段は、取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する比較手段と、該比較手段での結果に基づいて前記キー情報を出力する出力手段とを備え、該出力手段は、一方の前記深さ情報の方が小さい場合には、前記深さ情報が小さい方の前記キー情報を出力する第一の出力を、前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する第二の出力を、前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する第三の出力を、それぞれ実行する。
【００１５】
次に、上記目的を達成するために第７発明に係るコンピュータプログラムは、トライ木構造を有する第一のレコード群と第二のレコード群とをマージソートする装置で実行することが可能なコンピュータプログラムにおいて、前記装置を、前記第一のレコード群及び第二のレコード群を取得するレコード群取得手段、取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する深さ情報付与手段、及び前記キー情報よりも前記深さ情報を優先的に比較することにより、逐次的にマージソートするソート手段として機能させる。
【００１６】
また、第８発明に係るコンピュータプログラムは、第７発明において、前記深さ情報は、階層が深いほど大きい値に設定してあり、前記ソート手段を、取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する比較手段、及び該比較手段での結果に基づいて前記キー情報を出力する出力手段として機能させ、該出力手段を、一方の前記深さ情報の方が大きい場合には、前記深さ情報が大きい方の前記キー情報を出力する第一の出力を、前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する第二の出力を、前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する第三の出力を、それぞれ実行する手段として機能させる。
【００１７】
また、第９発明に係るコンピュータプログラムは、第７発明において、前記深さ情報は、階層が深いほど小さい値に設定してあり、前記ソート手段を、取得した前記第一のレコード群及び第二のレコード群に含まれる各レコードのノードごとに前記深さ情報及び前記キー情報を比較する比較手段、及び該比較手段での結果に基づいて前記キー情報を出力する出力手段として機能させ、該出力手段を、一方の前記深さ情報の方が小さい場合には、前記深さ情報が小さい方の前記キー情報を出力する第一の出力を、前記深さ情報が同一である場合には、小さい方の前記キー情報を出力する第二の出力を、前記深さ情報が同一であり、前記キー情報が同一である場合には、いずれか一方の前記キー情報を出力する第三の出力を、それぞれ実行する手段として機能させる。
【発明の効果】
【００１８】
本発明によれば、トライ木構造の階層が深い場合、あるいは階層構造が複雑である場合であっても、マージソートに要する時間を効果的に短縮することができるとともに、固定長のキー情報でのみマージソートすることが可能なハードウェアを用いたとしても、可変長のキー情報でもマージソートすることができるよう容易にインプリメンテーションすることが可能となる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施の形態１に係るソータの構成を模式的に示すブロック図である。
【図２】本発明の実施の形態１に係るソータの機能ブロック図である。
【図３】本発明の実施の形態１に係るソータのデータ構造の例示図である。
【図４】従来のＦＰＧＡを用いたソータのマージソート処理プログラムのソースコードの例示図である。
【図５】本発明の実施の形態１に係るソータのマージソート処理プログラムのソースコードの例示図である。
【図６】本発明の実施の形態１に係るソータのマージソート処理の最初の処理を示す模式図である。
【図７】本発明の実施の形態１に係るソータのマージソート処理の次の処理を示す模式図である。
【図８】本発明の実施の形態１に係るソータのマージソート処理の次の処理を示す模式図である。
【図９】本発明の実施の形態１に係るソータのマージソート処理の次の処理を示す模式図である。
【図１０】本発明の実施の形態１に係るソータのマージソート処理の次の処理を示す模式図である。
【図１１】本発明の実施の形態１に係るソータのマージソート処理の他の例を示す模式図である。
【図１２】本発明の実施の形態１に係るソータのＦＰＧＡの処理手順を示すフローチャートである。
【図１３】本発明の実施の形態２に係るソータのデータ構造の例示図である。
【図１４】本発明の実施の形態２に係るソータのマージソート処理の最初の処理を示す模式図である。
【図１５】本発明の実施の形態２に係るソータのマージソート処理の次の処理を示す模式図である。
【図１６】本発明の実施の形態２に係るソータのマージソート処理の次の処理を示す模式図である。
【図１７】本発明の実施の形態２に係るソータのマージソート処理の次の処理を示す模式図である。
【図１８】本発明の実施の形態２に係るソータのマージソート処理の次の処理を示す模式図である。
【図１９】本発明の実施の形態２に係るソータのマージソート処理の他の例を示す模式図である。
【図２０】本発明の実施の形態２に係るソータのＦＰＧＡの処理手順を示すフローチャートである。
【図２１】本発明の実施の形態２に係るソータのＦＰＧＡの他の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態に係る、トライ木構造の階層の深さを示す深さ情報をメタデータとして付与することにより、トライ木構造を有するレコード群を高い効率でマージソートする装置（ソータ）について、図面に基づいて具体的に説明する。以下の実施の形態は、特許請求の範囲に記載された発明を限定するものではなく、実施の形態の中で説明されている特徴的事項の組み合わせの全てが解決手段の必須事項であるとは限らないことは言うまでもない。
【００２１】
また、本発明は多くの異なる態様にて実施することが可能であり、実施の形態の記載内容に限定して解釈されるべきものではない。実施の形態を通じて同じ要素には同一の符号を付している。
【００２２】
以下の実施の形態では、コンピュータシステムにコンピュータプログラムを導入した装置について説明するが、当業者であれば明らかな通り、本発明はその一部をコンピュータで実行することが可能なコンピュータプログラムとして実施することができる。したがって、本発明は、トライ木構造の階層の深さを示す深さ情報をメタデータとして付与することにより、トライ木構造を有するレコード群を高い効率でマージソートするソータというハードウェアとしての実施の形態、ソフトウェアとしての実施の形態、又はソフトウェアとハードウェアとの組み合わせの実施の形態をとることができる。コンピュータプログラムは、ハードディスク、ＤＶＤ、ＣＤ、光記憶装置、磁気記憶装置等の任意のコンピュータで読み取ることが可能な記録媒体に記録することができる。
【００２３】
本発明の実施の形態によれば、トライ木構造の階層が深い場合、あるいは階層構造が複雑である場合であっても、マージソートに要する時間を効果的に短縮することができるとともに、固定長のキー情報でのみマージソートすることが可能なハードウェアを用いたとしても、可変長のキー情報でもマージソートすることができるよう容易にインプリメンテーションすることが可能となる。
【００２４】
（実施の形態１）
図１は、本発明の実施の形態１に係るソータの構成を模式的に示すブロック図である。本発明の実施の形態１に係るソータ１は、少なくともＦＰＧＡ１１、記憶装置１２、入出力インタフェース１３、通信インタフェース１４及び上述したハードウェアを接続する内部バス１５で構成されている。
【００２５】
ＦＰＧＡ１１は、内部バス１５を介してソータ１の上述したようなハードウェア各部と接続されており、上述したハードウェア各部の動作を制御するとともに、記憶装置１２に記憶されたコンピュータプログラムに従って、種々のソフトウェア的機能を実行する。コンピュータプログラムの実行時にはＦＰＧＡ１１に内蔵されているメモリにロードモジュールが展開され、コンピュータプログラムが実行される。
【００２６】
記憶装置１２は、内蔵される固定型記憶装置（ハードディスク）、ＲＡＭ等で構成されている。記憶装置１２に記憶されたコンピュータプログラムは、通信インタフェース１４を介して接続されている外部コンピュータからダウンロードされる。もちろん、可搬型ディスクドライブ等を搭載しておき、プログラム及びデータ等の情報を記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体からインストールしても良い。
【００２７】
記憶装置１２は、取得したレコード群（第一のレコード群及び第二のレコード群）を記憶するレコード群記憶部１２１を備えていても良い。レコード群記憶部１２１は、マージソートする２つのレコード群を記憶しておいても良いし、いずれか一方を記憶しておき、順次ＦＰＧＡ１１に内蔵されているメモリ、例えばキャッシュメモリへ展開するようにしても良い。
【００２８】
通信インタフェース１４は内部バス１５に接続されており、インターネット、ＬＡＮ、ＷＡＮ等の外部のネットワークに接続されることにより、外部コンピュータ等とデータ送受信を行うことが可能となっている。
【００２９】
入出力インタフェース１３は、キーボード、マウス等の入力装置、ＣＲＴディスプレイ、液晶ディスプレイ等の表示装置等の出力装置と接続され、例えばレコード群の入力の受付、マージソートされた結果の表示出力等を行う。
【００３０】
図２は、本発明の実施の形態１に係るソータ１の機能ブロック図である。図２において、ソータ１のレコード群取得部２０１は、マージソートの対象となる２つのレコード群を取得する。レコード群を取得する方法としては、入力装置からの入力を受け付けても良いし、外部のネットワークを介して受信しても良い。取得したレコード群は、記憶装置１２に記憶しても良いし、順次ＦＰＧＡ１１に内蔵されているメモリに展開しても良い。もちろん、記憶装置１２をバッファとして使用しても良いことは言うまでもない。
【００３１】
深さ情報付与部２０２は、取得したレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する。以下、各桁をノードと言い、各ノードの値をノード値と言う。ノード値が、マージソート実行時のキー情報となる。図３は、本発明の実施の形態１に係るソータ１のデータ構造の例示図である。本実施の形態１では、深さ情報をメタデータとして各ノードに付与する。
【００３２】
例えば図３（ａ）に示すような４つのレコードからなるレコード群を取得した場合、これを図３（ｂ）に示すように、桁ごとにブロック化することで階層化する。例えば第一レコードの第一ノード値は‘０’であるのに対して、第二乃至第四レコードの第一ノード値は‘１’であるので、第二乃至第四レコードの第一ノードをブロック化する。ブロック化されていない第一レコードについては、第二ノード値が‘０’、第三ノード値が‘０’、第四ノード値が‘１’となる。
【００３３】
次に、ブロック化されている第二乃至第四レコードの第二ノードについて、第一ノードと同様にブロック化を行う。図３の例では、第二レコードの第二ノード値は‘０’であるのに対して、第三及び第四レコードの第二ノード値は‘１’であるので、第三及び第四レコードの第二ノードをブロック化する。ブロック化されていない第二レコードについては、第三ノード以下にノード値が存在しないので、処理を終了する。
【００３４】
最後に、ブロック化されている第三及び第四レコードの第三ノードについて、第一及び第二ノードと同様にブロック化を行う。図３の例では、第三レコードの第三ノード値が‘０’であり、第四レコードの第三ノード値が‘１’である。第三レコードについては、第四ノード以下にノード値が存在しないので、処理を終了し、第四レコードについては、第四ノード値が‘１’となる。
【００３５】
そして、本実施の形態１では、深さ情報をメタデータとして各ノード値（キー情報）に付与する。付与する深さ情報は、ブロック化されたことにより階層化された図３（ｂ）に基づいて、上位階層から昇順に番号（ノード値の左側の数値）として付与する。
【００３６】
例えば図３（ｃ）に示すように、最初のレコードの最上位階層（第一ノード）には、深さ情報‘０’（左側の数値‘０’）をメタデータとしてノード値‘０’に付与する。次の階層（第二ノード）には、深さ情報‘１’（左側の数値‘１’）をメタデータとしてノード値‘０’に付与する。以下、階層を重ねる都度、深さ情報を‘１’ずつインクリメントしながらメタデータとして（ノード値の左側の数値として）ノード値に付与している。図３（ｃ）では、図３（ｂ）との対応関係を分かりやすくするため、これらのブロックを階層ごとにインデントして示しているが、深さ情報付与部２０２の実際の出力は、図３（ｄ）に示すように、単にこれらのブロックを連続して並べたものである。
【００３７】
ここで、深さ情報（メタデータ）とノード値（キー情報）との合計ビット数は固定（図３ではＰビット）であることが好ましい。これにより、例えばＦＰＧＡ１１のように固定長データに基づくマージソートにしか対応できない場合であっても、深さ情報（メタデータ）も含めた固定長データとして取り扱うことができ、可変長データであっても従来の処理アルゴリズムを活用してマージソートすることができる。
【００３８】
図４は、従来のＦＰＧＡ１１を用いたソータ１のマージソート処理プログラムのソースコードの例示図である。図４のソースコードは、Ｃ言語で記述されている。図４に示すように、キー情報が固定長であることから、５行目以降にレコード（エレメント）０のキー情報と、レコード（エレメント）１のキー情報とを比較してマージソートする処理が記述されている。
【００３９】
一方、図５は、本発明の実施の形態１に係るソータ１のマージソート処理プログラムのソースコードの例示図である。図５のソースコードも、Ｃ言語で記述されている。図５（ａ）に示すように、レコード（エレメント）‘０’の深さ情報と、レコード（エレメント）‘１’の深さ情報との比較、及びレコード（エレメント）‘０’のキー情報と、レコード（エレメント）‘１’のキー情報との両方の比較結果に基づいてマージソートする処理が記述されている。図５（ｂ）は、図５（ａ）のソースコードを整理して書き換えたソースコードである。
【００４０】
このように、深さ情報のビット数とキー情報のビット数との総和を一定長にしておくことにより、最小限のインプリメンテーションを行うことで、従来の固定長のキー情報を比較するマージソート処理プログラムを、可変長のキー情報を比較するマージソート処理プログラムとして機能させることが可能となる。
【００４１】
図２に戻って、ソート部２０３は、キー情報よりも深さ情報を優先的に比較することにより、逐次的にマージソートする。本実施の形態１では、深さ情報は、上述したように階層が深いほど大きい値になるよう設定してある。また、ソート部２０３は、比較部２０４、出力部２０５を備えている。
【００４２】
比較部２０４は、取得したレコード群に含まれる各レコードのノードごとに深さ情報及びキー情報（ノード値）を比較する。
【００４３】
出力部２０５は、比較部２０４での比較結果に基づいて３種類の出力のいずれかを実行する。まず、一方の深さ情報の方が大きい場合には、深さ情報が大きい方のレコードのノードのキー情報（ノード値）を出力する（第一の出力）。
【００４４】
また、深さ情報が同一である場合には、小さい方のキー情報（ノード値）を出力する（第二の出力）。そして、深さ情報が同一であり、キー情報（ノード値）が同一である場合には、いずれか一方のキー情報（ノード値）を出力する（第三の出力）。以下、図６乃至図１１により、実際のマージソート手順と結果について説明する。
【００４５】
図６は、本発明の実施の形態１に係るソータ１のマージソート処理の最初の処理を示す模式図である。図６（ａ）に示す第一のレコード群及び図６（ｃ）に示す第二のレコード群には、前述した方法により、キー情報（ノード値）ごとに深さ情報（ノード値の左側の数値）がメタデータとして付与されている。
【００４６】
図６（ａ）及び図６（ｃ）のブロック列は、それぞれ図６（ｂ）、図６（ｄ）に示されるトライ木構造のデータストリームを表現している。以降の図では、ブロック列と共にデータストリーム上の表現を記載しているが、動作の意味を解釈するために図示したものにすぎず、このトライ木構造のデータストリームはソータ１には入力されない。ソータ１が直接操作するデータ構造は、図６（ａ）及び図６（ｃ）に示されたブロック列である。マージソート処理開始時には、まず図６（ｂ）の‘０’（二重の四角で囲んであるノード値）と、図６（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較する。
【００４７】
本実施の形態１では、メタデータがノード値ごとに付与されており、実際には、図６（ａ）のブロック‘００’（二重の四角で囲んであるノード値）と、図６（ｃ）のブロック‘０１’（二重の四角で囲んであるノード値）とを比較する。ＦＰＧＡ１１は、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、どちらも深さ情報の値が‘０’であることから、次にキー情報であるノード値（右側の数値）を比較する。
【００４８】
図６の例では、図６（ａ）のキー情報（ノード値）の方が小さい値であることから、メタデータを含むブロック‘００’が出力される（図６（ｅ））。データストリームとしては、図６（ｆ）に示すように、最初の階層のノード値‘０’が出力される。
【００４９】
図７は、本発明の実施の形態１に係るソータ１のマージソート処理の次の処理を示す模式図である。本実施の形態１では、出力されたキー情報（ノード値）を含むブロックは順次削除していくので、図７（ａ）に示す第一のレコード群からは、出力されたブロック‘００’が削除されており、比較対象となるのは次に位置するブロック‘１０’（二重の四角で囲んであるブロック）となる。
【００５０】
これをデータストリームとして解釈したものは、それぞれ図７（ｂ）、（ｄ）に示されており、図７（ｂ）の‘０’（二重の四角で囲んであるノード値）と、図７（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較することに対応する。
【００５１】
ＦＰＧＡ１１は、図７（ａ）のブロック‘１０’（二重の四角で囲んであるノード値）と、図７（ｃ）のブロック‘０１’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、図７（ａ）の深さ情報の方が大きい値‘１’であることから、メタデータを含むブロック‘１０’が出力される（図７（ｅ））。データストリームとしては、図７（ｆ）に示すように、最初の階層のノード値‘０’の次に、次の階層のノード値‘０’が出力されることに対応する。
【００５２】
図８は、本発明の実施の形態１に係るソータ１のマージソート処理の次の処理を示す模式図である。本実施の形態１では、出力されたキー情報（ノード値）を含むブロックは順次削除していくので、図８（ａ）に示す第一のレコード群からは、出力されたブロック‘１０’が削除されており、比較対象となるのは次に位置するブロック‘２０’（二重の四角で囲んであるブロック）となる。
【００５３】
これをデータストリームとして解釈したものは、それぞれ図８（ｂ）、（ｄ）に示されており、図８（ｂ）の‘０’（二重の四角で囲んであるノード値）と、図８（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較することに対応する。
【００５４】
ＦＰＧＡ１１は、図８（ａ）のブロック‘２０’（二重の四角で囲んであるノード値）と、図８（ｃ）のブロック‘０１’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、図８（ａ）の深さ情報の方が大きい値‘２’であることから、メタデータを含むブロック‘２０’が出力される（図８（ｅ））。データストリームとしては、図８（ｆ）に示すように、最初の階層のノード値‘０’、次の階層のノード値‘０’の次に、その次の階層のノード値‘０’が出力されることに対応する。
【００５５】
図９は、本発明の実施の形態１に係るソータ１のマージソート処理の次の処理を示す模式図である。本実施の形態１では、出力されたキー情報（ノード値）を含むブロックは順次削除していくので、図９（ａ）に示す第一のレコード群からは、出力されたブロック‘２０’が削除されており、比較対象となるのは次に位置するブロック‘２１’（二重の四角で囲んであるブロック）となる。
【００５６】
これをデータストリームとして解釈したものは、それぞれ図９（ｂ）、（ｄ）に示されており、図９（ｂ）の‘１’（二重の四角で囲んであるノード値）と、図９（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較することに対応する。
【００５７】
ＦＰＧＡ１１は、図９（ａ）のブロック‘２１’（二重の四角で囲んであるノード値）と、図９（ｃ）のブロック‘０１’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、図９（ａ）の深さ情報の方が大きい値‘２’であることから、出力としてメタデータを含むブロック‘２１’が出力される（図９（ｅ））。データストリームとしては、図９（ｆ）に示すように、最初の階層のノード値‘０’、次の階層のノード値‘０’、その次の階層のノード値‘０’の下に、枝分かれしたノード値‘１’が出力されることに対応する。
【００５８】
図１０は、本発明の実施の形態１に係るソータ１のマージソート処理の次の処理を示す模式図である。本実施の形態１では、出力されたキー情報（ノード値）を含むブロックは順次削除していくので、図１０（ａ）に示す第一のレコード群からは、出力されたブロック‘２１’が削除されており、比較対象となるのは次に位置するブロック‘０２’（二重の四角で囲んであるブロック）となる。
【００５９】
これをデータストリームとして解釈したものは、それぞれ図１０（ｂ）、（ｄ）に示されており、図１０（ｂ）の‘２’（二重の四角で囲んであるノード値）と、図１０（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較することに対応する。
【００６０】
ＦＰＧＡ１１は、図１０（ａ）のブロック‘０２’（二重の四角で囲んであるノード値）と、図１０（ｃ）のブロック‘０１’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、どちらも深さ情報の値が‘０’であることから、次にキー情報であるノード値（右側の数値）を比較する。
【００６１】
図１０の例では、図１０（ｃ）のノード値の方が小さい値であることから、メタデータを含むブロック‘０１’が出力される（図１０（ｅ））。以降、同様に処理を継続する。
【００６２】
第一のブロック列又は第二のブロック列のいずれかが終端に達した場合、終端に達していない方のブロック列を出力する。両方のブロック列が終端に達した時点で処理を終了する。
【００６３】
また、深さ情報もキー情報（ノード値）も同一の場合には、同一であるブロック（深さ情報及びキー情報）を出力して、次の比較はそれぞれ次のブロック同士を比較すれば良い。図１１は、本発明の実施の形態１に係るソータ１のマージソート処理の他の例を示す模式図である。図６と同様、図１１（ａ）に示す第一のレコード群及び図１１（ｃ）に示す第二のレコード群には、前述した方法により、深さ情報がメタデータとしてキー情報（ノード値）に付与されている。
【００６４】
これをデータストリームとして解釈したものは、それぞれ図１１（ｂ）、（ｄ）に示されており、図１１（ｂ）の‘０’（二重の四角で囲んであるノード値）と、図１１（ｄ）の‘０’（二重の四角で囲んであるノード値）とを比較することに対応する。
【００６５】
ＦＰＧＡ１１は、図１１（ａ）のブロック‘００’（二重の四角で囲んであるノード値）と、図１１（ｃ）のブロック‘００’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、どちらも深さ情報の値が‘０’であることから、次にキー情報であるノード値（右側の数値）を比較する。
【００６６】
図１１の例では、図１１（ａ）と図１１（ｃ）とでノード値も同じ‘０’であることから、両者に共通であるブロック‘００’が出力される（図１１（ｅ））。データストリームとしては、図１１（ｆ）に示すように、最初の階層のノード値‘０’が出力されることに対応する。
【００６７】
つまり、メタデータが付与されたブロック単位で同一である場合には、両者に共通であるブロックのいずれか一方のブロックを出力して、両方のレコード群から対象としたブロック‘００’を削除する。
【００６８】
図１２は、本発明の実施の形態１に係るソータ１のＦＰＧＡ１１の処理手順を示すフローチャートである。図１２において、ソータ１のＦＰＧＡ１１は、マージソートの対象となる２つのレコード群を取得する（ステップＳ１２０１）。レコード群を取得する方法としては、入力装置からの入力を受け付けても良いし、ネットワークを介して受信しても良い。取得したレコード群は、記憶装置１２に記憶しても良いし、順次ＦＰＧＡ１１に内蔵されているメモリに展開しても良い。もちろん、データストリームとして取得して、記憶装置１２をバッファとして使用しても良いことは言うまでもない。
【００６９】
ＦＰＧＡ１１は、取得したレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する（ステップＳ１２０２）。ＦＰＧＡ１１は、比較対象となる第一のレコード群及び第二のレコード群の最初のノードを選択し（ステップＳ１２０３）、第一のレコード群及び第二のレコード群が終端に達したか否かを判断する（ステップＳ１２２０）。
【００７０】
ＦＰＧＡ１１が、第一のレコード群及び第二のレコード群の両方が終端に達したと判断した場合（ステップＳ１２２０：第一＝終端、第二＝終端）、ＦＰＧＡ１１は、処理を終了する。ＦＰＧＡ１１が、第二のレコード群のみが終端に達したと判断した場合（ステップＳ１２２０：第一≠終端、第二＝終端）、ＦＰＧＡ１１は、第一のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ１２２１）、処理をステップＳ１２１１へ進める。
【００７１】
ＦＰＧＡ１１が、第一のレコード群のみが終端に達したと判断した場合（ステップＳ１２２０：第一＝終端、第二≠終端）、ＦＰＧＡ１１は、第二のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ１２２２）、処理をステップＳ１２１３へ進める。ＦＰＧＡ１１が、第一のレコード群も第二のレコード群も終端に達していないと判断した場合（ステップＳ１２２０：第一≠終端、第二≠終端）、ＦＰＧＡ１１は、第一のレコード群のノードの深さ情報と、第二のレコード群のノードの深さ情報とを比較する（ステップＳ１２０４）。
【００７２】
ＦＰＧＡ１１が、第一のレコード群のノードの深さ情報の方が、第二のレコード群のノードの深さ情報より大きいと判断した場合（ステップＳ１２０４：第一＞第二）、ＦＰＧＡ１１は、第一のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ１２０５）、処理をステップＳ１２１１へ進める。ＦＰＧＡ１１が、第二のレコード群のノードの深さ情報の方が、第一のレコード群のノードの深さ情報より大きいと判断した場合（ステップＳ１２０４：第一＜第二）、ＦＰＧＡ１１は、第二のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ１２０６）、処理をステップＳ１２１３へ進める。
【００７３】
ＦＰＧＡ１１が、第一のレコード群のノードの深さ情報と、第二のレコード群のノードの深さ情報とが同じであると判断した場合（ステップＳ１２０４：第一＝第二）、ＦＰＧＡ１１は、各ノードのキー情報を比較する（ステップＳ１２０７）。
【００７４】
ＦＰＧＡ１１が、第一のレコード群のノードのキー情報の方が、第二のレコード群のノードのキー情報より小さいと判断した場合（ステップＳ１２０７：第一＜第二）、ＦＰＧＡ１１は、第一のレコード群のノードのキー情報（ノード値）を出力する（ステップＳ１２０８）。ＦＰＧＡ１１は、第一のレコード群の次のノードを選択して（ステップＳ１２１１）、処理をステップＳ１２２０へ戻して、上述した処理を繰り返す。
【００７５】
ＦＰＧＡ１１が、第二のレコード群のノードのキー情報の方が、第一のレコード群のノードのキー情報より小さいと判断した場合（ステップＳ１２０７：第一＞第二）、ＦＰＧＡ１１は、第二のレコード群のノードのキー情報（ノード値）を出力する（ステップＳ１２０９）。ＦＰＧＡ１１は、第二のレコード群の次のノードを選択して（ステップＳ１２１３）、処理をステップＳ１２２０へ戻して、上述した処理を繰り返す。
【００７６】
ＦＰＧＡ１１が、第一のレコード群のノードのキー情報と、第二のレコード群のノードのキー情報とが同じであると判断した場合（ステップＳ１２０７：第一＝第二）、ＦＰＧＡ１１は、いずれか一方のノードのキー情報を出力する（ステップＳ１２１０）。ＦＰＧＡ１１は、第一のレコード群及び第二のレコード群の次のノードを選択して（ステップＳ１２１２）、処理をステップＳ１２２０へ戻して、上述した処理を繰り返す。
【００７７】
以上のように本実施の形態１によれば、トライ木構造の階層が深い場合、あるいは階層構造が複雑である場合であっても、マージソートに要する時間を効果的に短縮することができるとともに、固定長のキー情報でのみマージソートすることが可能なハードウェアを用いたとしても、可変長のキー情報でもマージソートすることができるよう容易にインプリメンテーションすることが可能となる。
【００７８】
（実施の形態２）
本発明の実施の形態２に係るソータの構成及び機能ブロックは、実施の形態１と同様であることから、同一の符号を付することで詳細な説明を省略する、本実施の形態２は、深さ情報付与部２０２において、上位階層から降順になるように、深さ情報をメタデータとして各ノード値に付与する点で実施の形態１と相違する。
【００７９】
図１３は、本発明の実施の形態２に係るソータ１のデータ構造の例示図である。図１３（ａ）に示すような４つのレコードからなるレコード群を取得した場合、これを実施の形態１と同様、図１３（ｂ）に示すように、桁ごとにブロック化することで階層化する。
【００８０】
そして、本実施の形態２では、深さ情報をメタデータとして各ノード値（キー情報）に付与する。付与する深さ情報は、実施の形態１とは逆に、ブロック化されたことにより階層化された図１３（ｂ）に基づいて、上位階層から降順に番号（ノード値の左側の数値）として付与する。
【００８１】
例えば図１３（ｃ）に示すように、最初のレコードの最上位階層（第一ノード）には、深さ情報‘３’（左側の数値‘３’）をメタデータとしてノード値‘０’に付与する。次の階層（第二ノード）には、深さ情報‘２’（左側の数値‘２’）をメタデータとしてノード値‘０’に付与する。以下、階層を重ねる都度、深さ情報を‘１’ずつデクリメントしながらメタデータとして（ノード値の左側の数値として）ノード値に付与している。図１３（ｃ）では、図１３（ｂ）との対応関係を分かりやすくするため、これらのブロックを階層ごとにインデントして示しているが、深さ情報付与部２０２の実際の出力は、図１３（ｄ）に示すように、単にこれらのブロックを連続して並べたものである。
【００８２】
実施の形態１と同様、深さ情報（メタデータ）とノード値（キー情報）との合計ビット数は固定（図３と同様のＰビット）であることが好ましい。これにより、例えばＦＰＧＡ１１のように固定長データに基づくマージソートにしか対応できない場合であっても、深さ情報（メタデータ）も含めた固定長データとして取り扱うことができ、可変長データであっても従来の処理アルゴリズムを活用してマージソートすることができる。
【００８３】
そして、本実施の形態２では、図２の比較部２０４、出力部２０５の処理が実施の形態１と相違している。すなわち、比較部２０４は、取得したレコード群に含まれる各レコードのノードごとに深さ情報及びキー情報（ノード値）を比較する。
【００８４】
出力部２０５は、比較部２０４での結果に基づいて３種類の出力のいずれかを実行する。まず、一方の深さ情報の方が小さい場合には、深さ情報が小さい方のレコードのノードのキー情報（ノード値）を出力する（第一の出力）。
【００８５】
また、深さ情報が同一である場合には、小さい方のキー情報（ノード値）を出力する（第二の出力）。そして、深さ情報が同一であり、キー情報（ノード値）が同一である場合には、いずれか一方のキー情報（ノード値）を出力する（第三の出力）。以下、図１４乃至図１９により、実際のマージソート手順と結果について説明する。
【００８６】
図１４は、本発明の実施の形態２に係るソータ１のマージソート処理の最初の処理を示す模式図である。図１４（ａ）に示す第一のレコード群及び図１４（ｃ）に示す第二のレコード群には、前述した方法により、キー情報（ノード値）ごとに深さ情報（ノード値の左側の数値）がメタデータとして付与されている。
【００８７】
これをデータストリームとして解釈したものは、それぞれ図１４（ｂ）、（ｄ）に示されており、マージソート処理開始時には、まず図１４（ｂ）の‘０’（二重の四角で囲んであるノード値）と、図１４（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較することに対応する。
【００８８】
本実施の形態２では、メタデータがノード値ごとに付与されており、実際には、図１４（ａ）のブロック‘２０’（二重の四角で囲んであるノード値）と、図１４（ｃ）のブロック‘２１’（二重の四角で囲んであるノード値）とを比較する。ＦＰＧＡ１１は、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、どちらも深さ情報の値が‘２’であることから、次にキー情報であるノード値（右側の数値）を比較する。
【００８９】
図１４の例では、図１４（ａ）のキー情報（ノード値）の方が小さい値であることから、メタデータを含むブロック‘２０’が出力される（図１４（ｅ））。データストリームとしては、図１４（ｆ）に示すように、最初の階層のノード値‘０’が出力されることに対応する。
【００９０】
図１５は、本発明の実施の形態２に係るソータ１のマージソート処理の次の処理を示す模式図である。本実施の形態２では、出力されたキー情報（ノード値）を含むブロックは順次削除していくので、図１５（ａ）に示す第一のレコード群からは、出力されたブロック‘２０’が削除されており、比較対象となるのは次に位置するブロック‘１０’（二重の四角で囲んであるブロック）となる。
【００９１】
これをデータストリームとして解釈したものは、それぞれ図１５（ｂ）、（ｄ）に示されており、図１５（ｂ）の‘０’（二重の四角で囲んであるノード値）と、図１５（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較することに対応する。
【００９２】
ＦＰＧＡ１１は、図１５（ａ）のブロック‘１０’（二重の四角で囲んであるノード値）と、図１５（ｃ）のブロック‘２１’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、図１５（ａ）の深さ情報の方が小さい値‘１’であることから、メタデータを含むブロック‘１０’が出力される（図１５（ｅ））。データストリームとしては、図１５（ｆ）に示すように、最初のノード値‘０’の次に、その次の階層のノード値‘０’が出力されることに対応する。
【００９３】
図１６は、本発明の実施の形態２に係るソータ１のマージソート処理の次の処理を示す模式図である。本実施の形態２では、出力されたキー情報（ノード値）を含むブロックは順次削除していくので、図１６（ａ）に示す第一のレコード群からは、出力されたブロック‘１０’が削除されており、比較対象となるのは次に位置するブロック‘００’（二重の四角で囲んであるブロック）となる。
【００９４】
これをデータストリームとして解釈したものは、それぞれ図１６（ｂ）、（ｄ）に示されており、図１６（ｂ）の‘０’（二重の四角で囲んであるノード値）と、図１６（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較することに対応する。
【００９５】
ＦＰＧＡ１１は、図１６（ａ）のブロック‘００’（二重の四角で囲んであるノード値）と、図１６（ｃ）のブロック‘２１’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、図１６（ａ）の深さ情報の方が小さい値‘０’であることから、メタデータを含むブロック‘００’が出力される（図１６（ｅ））。データストリームとしては、図１６（ｆ）に示すように、最初の階層のノード値‘０’、次の階層のノード値‘０’の次に、その次の階層のノード値‘０’が出力されることに対応する。
【００９６】
図１７は、本発明の実施の形態２に係るソータ１のマージソート処理の次の処理を示す模式図である。本実施の形態２では、出力されたキー情報（ノード値）を含むブロックは順次削除していくので、図１７（ａ）に示す第一のレコード群からは、出力されたブロック‘００’が削除されており、比較対象となるのは次に位置するブロック‘０１’（二重の四角で囲んであるブロック）となる。
【００９７】
これをデータストリームとして解釈したものは、それぞれ図１７（ｂ）、（ｄ）に示されており、図１７（ｂ）の‘１’（二重の四角で囲んであるノード値）と、図１７（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較することに対応する。
【００９８】
ＦＰＧＡ１１は、図１７（ａ）のブロック‘０１’（二重の四角で囲んであるノード値）と、図１７（ｃ）のブロック‘２１’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、図１７（ａ）の深さ情報の方が小さい値‘０’であることから、メタデータを含むブロック‘０１’が出力される（図１７（ｅ））。データストリームとしては、図１７（ｆ）に示すように、最初の階層のノード値‘０’、次の階層のノード値‘０’、その次の階層のノード値‘０’の下に、枝分かれしたノード値‘１’が出力されることに対応する。
【００９９】
図１８は、本発明の実施の形態２に係るソータ１のマージソート処理の次の処理を示す模式図である。本実施の形態２では、出力されたキー情報（ノード値）を含むブロックは順次削除していくので、図１８（ａ）に示す第一のレコード群からは、出力されたブロック‘０１’が削除されており、比較対象となるのは次に位置するブロック‘２２’（二重の四角で囲んであるブロック）となる。
【０１００】
これをデータストリームとして解釈したものは、それぞれ図１８（ｂ）、（ｄ）に示されており、図１８（ｂ）の‘２’（二重の四角で囲んであるノード値）と、図１８（ｄ）の‘１’（二重の四角で囲んであるノード値）とを比較することに対応する。
【０１０１】
ＦＰＧＡ１１は、図１８（ａ）のブロック‘２２’（二重の四角で囲んであるノード値）と、図１８（ｃ）のブロック‘２１’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、どちらも深さ情報の値が‘２’であることから、次にキー情報であるノード値（右側の数値）を比較する。
【０１０２】
図１８の例では、図１８（ｃ）のノード値の方が小さい値であることから、メタデータを含むブロック‘２１’が出力される（図１８（ｅ））。以降、同様に処理を継続する。
【０１０３】
第一のブロック列又は第二のブロック列のいずれかが終端に達した場合、終端に達していない方のブロック列を出力する。両方のブロック列が終端に達した時点で処理を終了する。
【０１０４】
また、深さ情報もキー情報（ノード値）も同一の場合には、いずれか一方のブロック（深さ情報及びキー情報）を出力して、次の比較はそれぞれ次のブロック同士を比較すれば良い。図１９は、本発明の実施の形態２に係るソータ１のマージソート処理の他の例を示す模式図である。図１４と同様、図１９（ａ）に示す第一のレコード群及び図１９（ｃ）に示す第二のレコード群には、前述した方法により深さ情報がメタデータとしてキー情報（ノード値）に付与されている。
【０１０５】
これをデータストリームとして解釈したものは、それぞれ図１９（ｂ）、（ｄ）に示されており、図１９（ｂ）の‘０’（二重の四角で囲んであるノード値）と、図１９（ｄ）の‘０’（二重の四角で囲んであるノード値）とを比較することに対応する。
【０１０６】
ＦＰＧＡ１１は、図１９（ａ）のブロック‘２０’（二重の四角で囲んであるノード値）と、図１９（ｃ）のブロック‘２０’（二重の四角で囲んであるノード値）とを比較する。具体的には、まず深さ情報であるメタデータ、すなわち左側の数値を比較する。この例の場合は、どちらも深さ情報の値が‘２’であることから、次にキー情報であるノード値（右側の数値）を比較する。
【０１０７】
図１９の例では、図１９（ａ）と図１９（ｃ）とでノード値も同じ‘０’であることから、両者に共通であるブロック‘２０’が出力される（図１９（ｅ））。データストリームとしては、図１９（ｆ）に示すように、最初のノード値‘０’が出力されることに対応する。
【０１０８】
つまり、メタデータが付与されたブロック単位で同一である場合には、両者のレコード群からいずれか一方のブロックを出力して、両方のレコード群から対象としたブロック‘２０’を削除することになる。また、実施の形態１では、深さ情報とキー情報とを別個に比較する必要があったのに対して、実施の形態２では、深さ情報とキー情報との比較を、深さ情報を上位ビット、キー情報を下位ビットとする整数として比較情報を生成することで、一回の比較処理で行うこともできるので（図２１参照）、演算処理負荷を軽減することができる。
【０１０９】
図２０は、本発明の実施の形態２に係るソータ１のＦＰＧＡ１１の処理手順を示すフローチャートである。図２０において、ソータ１のＦＰＧＡ１１は、マージソートの対象となる２つのレコード群を取得する（ステップＳ２００１）。レコード群を取得する方法としては、入力装置からの入力を受け付けても良いし、外部のネットワークを介して受信しても良い。取得したレコード群は、記憶装置１２に記憶しても良いし、順次ＦＰＧＡ１１に内蔵されているメモリに展開しても良い。もちろん、データストリームとして取得して、記憶装置１２をバッファとして使用しても良いことは言うまでもない。
【０１１０】
ＦＰＧＡ１１は、取得したレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する（ステップＳ２００２）。ＦＰＧＡ１１は、比較対象となる第一のレコード群及び第二のレコード群の最初のノードを選択し（ステップＳ２００３）、第一のレコード群及び第二のレコード群が終端に達したか否かを判断する（ステップＳ２０２０）。
【０１１１】
ＦＰＧＡ１１が、第一のレコード群及び第二のレコード群の両方が終端に達したと判断した場合（ステップＳ２０２０：第一＝終端、第二＝終端）、ＦＰＧＡ１１は、処理を終了する。ＦＰＧＡ１１が、第二のレコード群のみが終端に達したと判断した場合（ステップＳ２０２０：第一≠終端、第二＝終端）、ＦＰＧＡ１１は、第一のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ２０２１）、処理をステップＳ２０１１へ進める。
【０１１２】
ＦＰＧＡ１１が、第一のレコード群のみが終端に達したと判断した場合（ステップＳ２０２０：第一＝終端、第二≠終端）、ＦＰＧＡ１１は、第二のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ２０２２）、処理をステップＳ２０１３へ進める。ＦＰＧＡ１１が、第一のレコード群も第二のレコード群も終端に達していないと判断した場合（ステップＳ２０２０：第一≠終端、第二≠終端）、ＦＰＧＡ１１は、第一のレコード群のノードの深さ情報と、第二のレコード群のノードの深さ情報とを比較する（ステップＳ２００４）
【０１１３】
ＦＰＧＡ１１が、第一のレコード群のノードの深さ情報の方が、第二のレコード群のノードの深さ情報より小さいと判断した場合（ステップＳ２００４：第一＜第二）、ＦＰＧＡ１１は、第一のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ２００５）、処理をステップＳ２０１１へ進める。ＦＰＧＡ１１が、第二のレコード群のノードの深さ情報の方が、第一のレコード群のノードの深さ情報より小さいと判断した場合（ステップＳ２００４：第一＞第二）、ＦＰＧＡ１１は、第二のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ２００６）、処理をステップＳ２０１３へ進める。
【０１１４】
ＦＰＧＡ１１が、第一のレコード群のノードの深さ情報と、第二のレコード群のノードの深さ情報とが同じであると判断した場合（ステップＳ２００４：第一＝第二）、ＦＰＧＡ１１は、各ノードのキー情報を比較する（ステップＳ２００７）。
【０１１５】
ＦＰＧＡ１１が、第一のレコード群のノードのキー情報の方が、第二のレコード群のノードのキー情報より小さいと判断した場合（ステップＳ２００７：第一＜第二）、ＦＰＧＡ１１は、第一のレコード群のノードのキー情報（ノード値）を出力する（ステップＳ２００８）。ＦＰＧＡ１１は、第一のレコード群の次のノードを選択して（ステップＳ２０１１）、処理をステップＳ２０２０へ戻して、上述した処理を繰り返す。
【０１１６】
ＦＰＧＡ１１が、第二のレコード群のノードのキー情報の方が、第一のレコード群のノードのキー情報より小さいと判断した場合（ステップＳ２００７：第一＞第二）、ＦＰＧＡ１１は、第二のレコード群のノードのキー情報（ノード値）を出力する（ステップＳ２００９）。ＦＰＧＡ１１は、第二のレコード群の次のノードを選択して（ステップＳ２０１３）、処理をステップＳ２０２０へ戻して、上述した処理を繰り返す。
【０１１７】
ＦＰＧＡ１１が、第一のレコード群のノードのキー情報と、第二のレコード群のノードのキー情報とが同じであると判断した場合（ステップＳ２００７：第一＝第二）、ＦＰＧＡ１１は、いずれか一方のノードのキー情報を出力する（ステップＳ２０１０）。ＦＰＧＡ１１は、第一のレコード群及び第二のレコード群の次のノードを選択して（ステップＳ２０１２）、処理をステップＳ２０２０へ戻して、上述した処理を繰り返す。
【０１１８】
以上のように本実施の形態２によれば、トライ木構造の階層が深い場合、あるいは階層構造が複雑である場合であっても、マージソートに要する時間を効果的に短縮することができるとともに、固定長のキー情報でのみマージソートすることが可能なハードウェアを用いたとしても、可変長のキー情報でもマージソートすることができるよう容易にインプリメンテーションすることが可能となる。また、比較情報を生成することで、比較処理を一回にすることが可能であることから、演算処理負荷を軽減することも可能となる。
【０１１９】
なお、深さ情報を上位ビット、キー情報を下位ビットとする整数として生成された比較情報を比較対象として、図２０に示す処理手順を簡略化することもできる。図２１は、本発明の実施の形態２に係るソータ１のＦＰＧＡ１１の他の処理手順を示すフローチャートである。図２１において、ソータ１のＦＰＧＡ１１は、マージソートの対象となる２つのレコード群を取得する（ステップＳ２１０１）。レコード群を取得する方法としては、入力装置からの入力を受け付けても良いし、外部のネットワークを介して受信しても良い。取得したレコード群は、記憶装置１２に記憶しても良いし、順次ＦＰＧＡ１１に内蔵されているメモリに展開しても良い。もちろん、データストリームとして取得して、記憶装置１２をバッファとして使用しても良いことは言うまでもない。
【０１２０】
ＦＰＧＡ１１は、取得したレコード群に含まれる各レコードのノードごとのキー情報に、トライ木構造における階層の深さを示す深さ情報をメタデータとして付与する（ステップＳ２１０２）。ＦＰＧＡ１１は、比較対象となる第一のレコード群及び第二のレコード群の最初のノードを選択し（ステップＳ２１０３）、第一のレコード群及び第二のレコード群が終端に達したか否かを判断する（ステップＳ２１２０）。
【０１２１】
ＦＰＧＡ１１が、第一のレコード群及び第二のレコード群の両方が終端に達したと判断した場合（ステップＳ２１２０：第一＝終端、第二＝終端）、ＦＰＧＡ１１は、処理を終了する。ＦＰＧＡ１１が、第二のレコード群のみが終端に達したと判断した場合（ステップＳ２１２０：第一≠終端、第二＝終端）、ＦＰＧＡ１１は、第一のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ２１２１）、処理をステップＳ２１１１へ進める。
【０１２２】
ＦＰＧＡ１１が、第一のレコード群のみが終端に達したと判断した場合（ステップＳ２１２０：第一＝終端、第二≠終端）、ＦＰＧＡ１１は、第二のレコード群のノードのキー情報（ノード値）を出力して（ステップＳ２１２２）、処理をステップＳ２１１３へ進める。ＦＰＧＡ１１が、第一のレコード群も第二のレコード群も終端に達していないと判断した場合（ステップＳ２１２０：第一≠終端、第二≠終端）、ＦＰＧＡ１１は、第一のレコード群のノードの比較情報（深さ情報＋キー情報）と、第二のレコード群のノードの比較情報（深さ情報＋キー情報）とを比較する（ステップＳ２１０４）
【０１２３】
ＦＰＧＡ１１が、第一のレコード群のノードの比較情報の方が、第二のレコード群のノードの比較情報より小さいと判断した場合（ステップＳ２１０４：第一＜第二）、ＦＰＧＡ１１は、第一のレコード群のノードのキー情報（ノード値）を出力し（ステップＳ２１０５）、第一のレコード群の次のノードを選択して（ステップＳ２１１１）、処理をステップＳ２１２０へ戻して、上述した処理を繰り返す。
【０１２４】
ＦＰＧＡ１１が、第二のレコード群のノードの比較情報の方が、第一のレコード群のノードの比較情報より小さいと判断した場合（ステップＳ２１０４：第一＞第二）、ＦＰＧＡ１１は、第二のレコード群のノードのキー情報（ノード値）を出力し（ステップＳ２１０６）、第二のレコード群の次のノードを選択して（ステップＳ２１１３）、処理をステップＳ２１２０へ戻して、上述した処理を繰り返す。
【０１２５】
ＦＰＧＡ１１が、第一のレコード群のノードの比較情報と、第二のレコード群のノードの比較情報とが同じであると判断した場合（ステップＳ２１０４：第一＝第二）、ＦＰＧＡ１１は、いずれか一方のノードのキー情報を出力し（ステップＳ２１０７）、第一のレコード群及び第二のレコード群の次のノードを選択して（ステップＳ２１１２）、処理をステップＳ２１２０へ戻して、上述した処理を繰り返す。
【０１２６】
なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨の範囲内であれば多種の変更、改良等が可能である。例えばＦＰＧＡ１１を用いることに限定されるものではなく、例えばＣＰＵ（中央演算処理装置）、ＧＰＵ等の演算処理装置を用いてマージソート処理を行っても良い。
【符号の説明】
【０１２７】
１  ソータ
１１  ＦＰＧＡ
１２  記憶装置
１３  入出力インタフェース
１４  通信インタフェース
１５  内部バス
【図１】
0006016215.tif 000002
【図２】
0006016215.tif 000003
【図３】
0006016215.tif 000004
【図６】
0006016215.tif 000005
【図７】
0006016215.tif 000006
【図８】
0006016215.tif 000007
【図９】
0006016215.tif 000008
【図１０】
0006016215.tif 000009
【図１１】
0006016215.tif 000010
【図１２】
0006016215.tif 000011
【図１３】
0006016215.tif 000012
【図１４】
0006016215.tif 000013
【図１５】
0006016215.tif 000014
【図１６】
0006016215.tif 000015
【図１７】
0006016215.tif 000016
【図１８】
0006016215.tif 000017
【図１９】
0006016215.tif 000018
【図２０】
0006016215.tif 000019
【図２１】
0006016215.tif 000020
【図４】
0006016215.tif 000021
【図５】
0006016215.tif 000022