(57)【特許請求の範囲】
【請求項１】
複数のデータを有するデータファイルに対し、ソート処理を行うデータソート処理プログラムにおいて、
コンピュータを、
データに一定回数以上出現する共通接頭文字列のみを一意な順序で格納した要約順序トライを作成する要約順序トライ作成手段、
前記要約順序トライの所定のノード間に分割境界を設定する分割境界決定手段、
前記分割境界に基づいて、前記データを複数のデータ集合に振り分けるデータ振り分け手段、
前記複数のデータ集合ごとにデータのソートを行い、該データのソートを行ったデータ集合のソートを行う振り分けデータソート手段、
として機能させることを特徴とするデータソート処理プログラム。
【請求項２】
前記要約順序トライ作成手段は、ルートを作成し、前記各データの各文字をそれぞれ順番に読み込み、前記ルートに接続される前記ノードを過去に通ったデータが所定数あったとき、かつ、前記所定のノードに関連づけられた文字の次の文字に対応する子ノードが作成されていないときに、前記所定のノードを共通にする前記各子ノードが所定の配列となるように、前記子ノードを作成することを特徴とする請求項１記載のデータソート処理プログラム。
【請求項３】
前記各ノードは、前記各ノードに対応してそれぞれ設けられ、前記各データが前記各ノードを通る毎にインクリメントするカウンタを備え、
前記要約順序トライ作成手段は、前記データの文字数Ｋ（Ｋ≧１）のデータを読み込んだとき、ルートから深さｋ（１≦ｋ≦Ｋ）のノードに設定されたカウンタが所定値以上のとき、かつ、深さ（ｋ＋１）の文字に対応するノードが存在しないときは、前記深さｋのノードに深さ（ｋ＋１）のノードを作成し、かつ、前記深さ（ｋ＋１）のノードを作成するときに、他の深さ（ｋ＋１）のノードが既に存在するときは、他の深さ（ｋ＋１）のノードに対して今回作成する前記深さ（ｋ＋１）のノードが、所定の配列となるように作成することを特徴とする請求項１記載のデータソート処理プログラム。
【請求項４】
複数のデータを有するデータファイルに対し、ソート処理を行うデータソート処理方法において、
要約順序トライ作成手段が、データに一定回数以上出現する共通接頭文字列のみを一意な順序で格納した要約順序トライを作成し、
分割境界決定手段が、前記要約順序トライの所定のノード間に分割境界を設定し、
データ振り分け手段が、前記分割境界に基づいて、前記データを複数のデータ集合に振り分け、
振り分けデータソート手段が、前記複数のデータ集合ごとにデータのソートを行い、該データのソートを行ったデータ集合のソートを行う、
ことを特徴とするデータソート処理方法。
【請求項５】
複数のデータを有するデータファイルに対し、ソート処理を行うデータソート処理装置において、
データに一定回数以上出現する共通接頭文字列のみを一意な順序で格納した要約順序トライを作成する要約順序トライ作成手段と、
前記要約順序トライの所定のノード間に分割境界を設定する分割境界決定手段と、
前記分割境界に基づいて、前記データを複数のデータ集合に振り分けるデータ振り分け手段と、
前記複数のデータ集合ごとにデータのソートを行い、該データのソートを行ったデータ集合のソートを行う振り分けデータソート手段と、
を有することを特徴とするデータソート処理装置。
【請求項６】
前記分割境界決定手段は、前記各データ集合が可及的に均等に振り分けられるように前記分割境界を決定することを特徴とする請求項１記載のデータソート処理プログラム。
【請求項７】
前記各ノードは、前記各ノードに対応してそれぞれ設けられ、前記各データが前記各ノードを通る毎にインクリメントするカウンタを備え、
前記要約順序トライ作成手段は、前記データの文字数Ｋ（Ｋ≧１）のデータを読み込んだとき、ルートから深さｋ（１≦ｋ≦Ｋ）のノードに設定されたカウンタが所定値以上のとき、かつ、深さ（ｋ＋１）の文字に対応するノードが存在しないときは、前記深さｋのノードに深さ（ｋ＋１）のノードを作成し、かつ、前記深さ（ｋ＋１）のノードを作成するときに、他の深さ（ｋ＋１）のノードが既に存在するときは、他の深さ（ｋ＋１）のノードに対して今回作成する前記深さ（ｋ＋１）のノードが、所定の配列となるように作成し、
前記分割境界決定手段は、前記カウンタ値と予め設定される分割数とに基づいて、前記分割境界を設定することを特徴とする請求項１記載のデータソート処理プログラム。
【請求項８】
前記分割境界決定手段は、ｉ番目の前記各ノードのカウンタ値の和が、（ｉ−１）番目の前記ノードのカウンタ値と異なるとき、前記ｉ番目の各ノードのカウンタ値の和が前記（ｉ−１）番目のノードのカウンタ値と等しくなるように、それぞれ前記ｉ番目の各ノードのカウンタ値を補正することを特徴とする請求項１記載のデータソート処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータソート処理プログラム、データソート処理方法およびデータソート処理装置に関し、特に大規模データのソートを行うデータソート処理プログラム、データソート処理方法およびデータソート処理装置に関する。
【背景技術】
【０００２】
与えられたデータを、予め定められた順序に並べ替えるデータソート方法が知られている。
従来のデータソート方法として、クイックソートやバブルソート、シェルソート等の方法がある。これらのデータソート方法は、データの件数に対して線形時間を超える計算時間が必要であるため、件数が非常に多いデータに適用された場合、計算時間が増大し、コンピュータの演算性能が急激に悪化するという問題がある。
【０００３】
この問題を解決するために、唯一の根（ルート）を持ち閉路を持たない（オープンループの）木構造（グラフ）を用いたデータソート方法が知られている（例えば、特許文献１参照）。
【０００４】
この木構造の１種として、与えられたデータの容量に対して線形時間（データのサイズに比例する時間）でソートすることができるトライ（ＴＲＩＥ）構造がある。
図１２は、複数の文字を有する文字列（データ）をトライ構造で示した図である。
【０００５】
なお、以下では、図１２中上下方向の長さを「深さ」、左右方向の長さを「幅」という。
トライ９０は１つ以上のノード（節）から構成され、特に最初のノードを「ルート」（根）という。また、ノードとノードとを結ぶ線を「ブランチ」（枝）という。また、所定のノードを「親ノード」というとき、親ノードに対して１つ下位のノードを「子ノード」といい、子ノードを持たないノードを「リーフ」（葉）という。
【０００６】
トライ９０を用いて文字を探索する場合は、ルートから開始する。ルートおよびノードは、トライ９０内の文字の種類と同じ数のブランチを有し、探索は文字に対応したブランチを選択するだけで進めることができる。トライ９０では、ルートは、Ｂ、ＣおよびＤの３本のブランチを有している。例えば、文字列が「ＢＡＣＫ」ならば、最初にＢのブランチを選択し、次にＡのブランチ、次にＣのブランチ、最後にＫのブランチを選んで進めていけば探索が完了する。
【０００７】
このようなトライ構造を用いた特許文献１に記載のデータソート方法によれば、巨大なサイズのデータ（文字列）に適用されても演算性能が急激に悪化することはない。
しかし、トライ構造は、相異なるデータ（ソートアイテム）のサイズに比例した計算領域（主記憶容量）を必要とする（メモリを大量に消費する）という欠点を持つ。このため、文字列の数や文字列の長さが増えると、メモリに収まらなくなってしまい、処理時間の遅延の原因となる。
【０００８】
従って、重複の少ない大規模データのソートや集計に適用されると、計算領域が不足して極端に演算性能が悪化する、または、計算が続けられなくなるという問題がある。
この問題を解決するために、与えられたデータを複数のデータの集合に分割し、それぞれのデータの集合に対して既存のソート方法を適用する方法が知られている（例えば、特許文献２参照）。
【特許文献１】特開２００３−４４２６７号公報
【特許文献２】特許第２９５９４９７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、データを単純に区分けしただけでは、分割して得られる各データ集合間のデータの順序が定かではないため、これらのデータ集合に対して、さらに、それぞれの処理結果を併合するためのデータ処理を行う必要があり、処理を効率良く行うことができない（データ処理のコストが高い）という問題がある。
【００１０】
本発明はこのような点に鑑みてなされたものであり、小容量のメモリを用いて、かつ高速にデータソート処理を行うことができるデータソート処理プログラム、データソート処理方法およびデータソート処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明では上記問題を解決するために、複数のデータを有するデータファイルに対し、ソート処理を行うデータソート処理プログラムにおいて、コンピュータを、データに一定回数以上出現する共通接頭文字列のみを一意な順序で格納した要約順序トライを作成する要約順序トライ作成手段、前記要約順序トライの所定のノード間に分割境界を設定する分割境界決定手段、前記分割境界に基づいて、前記データを複数のデータ集合に振り分けるデータ振り分け手段、前記複数のデータ集合ごとにデータのソートを行い、該データのソートを行ったデータ集合のソートを行う振り分けデータソート手段、として機能させることを特徴とするデータソート処理プログラムが提供される。
【００１２】
また、上記課題を解決するために、複数のデータを有するデータファイルに対し、ソート処理を行うデータソート処理方法において、要約順序トライ作成手段が、データに一定回数以上出現する共通接頭文字列のみを一意な順序で格納した要約順序トライを作成し、分割境界決定手段が、前記要約順序トライの所定のノード間に分割境界を設定し、データ振り分け手段が、前記分割境界に基づいて、前記データを複数のデータ集合に振り分け、振り分けデータソート手段が、前記複数のデータ集合ごとにデータのソートを行い、該データのソートを行ったデータ集合のソートを行う、ことを特徴とするデータソート処理方法が提供される。
【００１３】
また、上記課題を解決するために、複数のデータを有するデータファイルに対し、ソート処理を行うデータソート処理装置において、データに一定回数以上出現する共通接頭文字列のみを一意な順序で格納した要約順序トライを作成する要約順序トライ作成手段と、前記要約順序トライの所定のノード間に分割境界を設定する分割境界決定手段と、前記分割境界に基づいて、前記データを複数のデータ集合に振り分けるデータ振り分け手段と、前記複数のデータ集合ごとにデータのソートを行い、該データのソートを行ったデータ集合のソートを行う振り分けデータソート手段と、を有することを特徴とするデータソート処理装置が提供される。
【発明の効果】
【００１８】
本発明によれば、要約順序トライを作成してデータソート処理を行うことによって、一度振り分けたデータを再度併合することなくデータソート処理を完了させることができるため、データソート処理を簡易なものとすることができ、また、データソート処理の高速化を図ることができる。
【００１９】
また、データを複数のデータ集合に振り分け、このデータ集合をソートすることにより、データを直接ソートする場合に比べてメモリの省容量化を図ることができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の実施の形態を図面を参照して詳細に説明する。
まず、実施の形態に適用される発明の概念について説明し、その後、実施の形態の具体的な内容を説明する。
【００２１】
図１は、実施の形態に適用される発明の概念図である。
データ記憶手段１は、複数のデータＤ１、・・・、Ｄ（ｎ）を有するデータファイルＤを格納する。
【００２２】
要約順序トライ作成手段２は、データ記憶手段１からデータファイルＤが入力され、成長頻度パラメータ入力手段２１から成長頻度パラメータが入力されると、要約順序トライを作成する。
【００２３】
なお、成長頻度パラメータについては後に詳述する。
ところで「トライ」とは、入力された全てのデータＤ１、・・・、Ｄ（ｎ）の情報を格納して構築される木構造であり、「要約順序トライ」とは、トライの部分木構造になっており、トライと同一のルートを有し、データＤ１、・・・Ｄ（ｎ）のうち、所定回数以上出現するデータの接頭辞（共通接頭文字列）をすべて格納し、かつ、任意の親ノードの子ノードが、一意に、例えばアルファベットであれば、アルファベット順に例えば左から右へ順序付けられているものである。
【００２４】
例えば、文字列（データ）「ＢＡＤ」、「ＢＡＣＫ」、「ＢＡＤＹ」、・・・の要約順序トライは、文字「Ｂ」のノードを作成し、ルート所定回数（この例では３回）以上出現し共通する文字「Ａ」のノードが作成され、さらに全てのデータを格納したときに、文字「Ｂ」のノードに続く文字「Ａ」のノードを親ノードとし、それに続く子ノード（この例では「Ｃ」および「Ｄ」）が、所定回数以上出現したときに、「Ｃ」、「Ｄ」が、この順番に（一意な方向に順序付けられて）作成された木構造である。
【００２５】
この要約順序トライによれば、データが多い部分の構造が深くなり、データが少ない部分の構造が浅くなるため、データの重要な部分の情報を失うことなく構造が簡素化される。
【００２６】
分割境界決定手段３は、要約順序トライの所定のノード間を分割する分割境界を決定する。具体的には、分割境界決定手段３は、分割数入力手段３１から与えられるデータ集合分割数およびデータのデータ数ｎに基づいて、後述する各データ集合量が可及的に均等になるように要約順序トライの分割境界を決定する。
【００２７】
データ振り分け手段４は、分割境界決定手段３により決定された分割境界に基づいて、データＤ１、・・・、Ｄ（ｎ）を作成された要約順序トライに当てはめることにより、データＤ１、・・・、Ｄ（ｎ）を前述したデータ集合分割数のデータ集合に振り分ける。
【００２８】
振り分けデータソート手段５は、データ集合毎に、所定のソート方法を用いてソートを行う。
結合手段６は、振り分けデータソート手段５によってソートが行われた後のデータ集合を一意な順序で結合することにより、ソートが完了したデータを作成する。
【００２９】
これにより、データ記憶手段１からデータファイルＤが入力され、成長頻度パラメータ入力手段２１から成長頻度パラメータが入力されると、要約順序トライ作成手段２により、要約順序トライが作成される。そして、要約順序トライが分割境界決定手段３に渡され、分割数入力手段３１によりデータ集合分割数が入力されると、分割境界決定手段３により、各データ集合量が、可及的に均等になるように要約順序トライの分割境界が決定される。
【００３０】
決定された分割境界およびデータＤ１、・・・、Ｄ（ｎ）がデータ振り分け手段４に渡されると、データ振り分け手段４により、データＤ１、・・・、Ｄ（ｎ）が作成された要約順序トライに当てはめられる。そして、データＤ１、・・・、Ｄ（ｎ）が前述したデータ集合分割数のデータ集合に振り分けられる。
【００３１】
データ集合分割数のデータ集合が振り分けデータソート手段５に渡されると、振り分けデータソート手段５により、データ集合毎に、所定のソート方法を用いてソートが行われる。
【００３２】
このソートが行われた後のデータ集合が結合手段６に渡されると、結合手段６により、ソートが行われた後のデータ集合が一意な順序で結合されることにより、ソートが完了したデータが作成される。
【００３３】
以下、本発明の実施の形態を具体的に説明する。
図２は、本実施の形態のコンピュータのハードウェア構成例を示す図である。本発明の実施の形態のデータソートプログラムおよびデータソート方法は、コンピュータで構成されるデータソート処理装置１００により実現される。
【００３４】
データソート処理装置１００は、以下の様なハードウェア構成を有している。
データソート処理装置１００は、ＣＰＵ（Central Processing Unit）１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０１ａを介してＲＡＭ（Random Access Memory）１０２、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１０３、グラフィック処理装置１０４および入力インタフェース１０５が接続されている。
【００３５】
ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。また、ＨＤＤ１０３には、ＯＳやアプリケーションプログラム等が格納される。
【００３６】
グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号を、バス１０１ａを介してＣＰＵ１０１に送信する。
【００３７】
以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。
以下、図２に示す構成のデータソート処理装置１００における本実施の形態のデータソートの処理について詳細に説明する。
【００３８】
図３は、コンピュータの機能を示すブロック図である。
ＨＤＤ１０３には、ｎ個の文字列Ｘ１、Ｘ２・・・、Ｘ（ｎ）を有する文字列ファイルＸが格納されている。
【００３９】
データソート処理装置１００は、ソフトウェアによって実現される処理機能として、要約順序トライ構築部１１０、分割境界決定部１２０、文字列振り分け部１３０、振り分け文字列ソート部１４０および文字列結合部１５０を有している。
【００４０】
要約順序トライ構築部１１０は、作成中の要約順序トライを表す変数Ｔと、処理対象の文字を表す変数λと、制御対象のノードまたはルートを表す変数ｖとを有している。
また、要約順序トライ構築部１１０は、ｊ（１≦ｊ≦ｎ）番目の文字列Ｘ（ｊ）内の次の文字を取り出す関数ｎｅｘｔｃｈａｒ（）と、ノードｗからレコードａをたどる移動先のノードを返す関数ｇｏｔｏ（ｗ，ａ）と、関数ｇｏｔｏ（ｗ，ａ）＝ｚを満たし、さらにｚが要約順序トライＴ内で文字ａに対して一意な順番に位置するよう、要約順序トライＴにノードｚを追加する関数（戻り値なし）ｍａｋｅ（ｗ,ａ,ｚ）と、ノードｗのカウンタ値を返す関数ｃｏｕｎｔ（ｗ）とを有している。
【００４１】
例えば、ｊ番目の文字列Ｘ（ｊ）が「ＢＥ」であり、現在の文字が「Ｂ」であるとき、関数ｎｅｘｔｃｈａｒ（）が実行されると、次の文字「Ｅ」が取り出される。
要約順序トライ構築部１１０は、文字列Ｘ１、Ｘ２・・・、Ｘ（ｎ）を読み込み、キーボード１２やマウス１３等から入力される成長頻度パラメータαと、前述した変数および関数とを用いて要約順序トライＴを作成する。
【００４２】
分割境界決定部１２０は、各ノードｗに割り当てられたバケットＩＤを返す関数ｂｕｃｋｅｔ（ｗ）を有している。分割境界決定部１２０は、要約順序トライ構築部１１０から要約順序トライＴが送られると、文字列の個数ｎと、キーボード１２やマウス１３等から入力されるデータ集合分割数βとに基づいて、分割境界を決定する。具体的には、分割境界決定部１２０は、文字列の個数ｎが均等に分割されるように（文字列データ量が均等に分割されるように）要約順序トライＴを調整した要約順序トライＴ１を作成し、要約順序トライＴ１を所定のノード間で分割し、関数ｂｕｃｋｅｔ（ｗ）を用いて分割した各ノードにバケットＩＤを割り当てる。なお、このバケットＩＤの割り当て方法は、分割した各ノードを判別できるものであれば特に限定されない。
【００４３】
文字列振り分け部１３０は、現在の文字を表す変数λ１と、現在のノードまたはルートを表す変数ｖ１とを有している。
また、文字列振り分け部１３０は、前述した関数ｎｅｘｔｃｈａｒ（）と、前述した関数ｇｏｔｏ(ｗ,ａ)と、前述した関数ｂｕｃｋｅｔ（ｗ）とを有している。
【００４４】
文字列振り分け部１３０は、分割境界決定部１２０によって割り当てられたバケットＩＤの個数と等しいバケットＢ１、・・・、Ｂ（ｍ）を作成する。そして、文字列Ｘ１、Ｘ２、・・・、Ｘ（ｎ）を要約順序トライＴ１に当てはめることにより、文字列Ｘ１、Ｘ２、・・・、Ｘ（ｎ）をバケットＩＤに従って、それぞれ対応するバケットＢ１、・・・、Ｂ（ｍ）に格納する。
【００４５】
ここで、バケットＢ１、・・・、Ｂ（ｍ）内に格納される文字列をそれぞれ、文字列集合Ｕ１、・・・、Ｕ（ｍ）とすると、振り分け文字列ソート部１４０は、所定のソート方法を用いて、それぞれ文字列集合Ｕ１、・・・、Ｕ（ｍ）のソートを行う。
【００４６】
このソート方法としては特に限定されないが、例えば、特開２００３−４４２６７号公報に開示されているソート方法や、クイックソート方法等が挙げられる。
文字列結合部１５０は、ソートが完了した文字列集合Ｕ１ａ、・・・、Ｕ（ｍ）ａを、一意に結合して、その結合されたデータをソート結果としてモニタ１１に出力する。
【００４７】
以上のような構成のコンピュータによってデータソートが行われる。
次に、データソート処理装置１００を用いたデータソート処理を詳細に説明する。
図４は、データソート処理の手順を示すフローチャートである。以下、図４に示す処理をステップ番号に沿って説明する。
【００４８】
まず、要約順序トライ構築部１１０は、未読の文字列の読み込みを試みる（ステップＳ１１）。
次に、要約順序トライ構築部１１０は、全ての文字列Ｘ１、・・・、Ｘｎを読み込んだか否かを判断する（ステップＳ１２）。
【００４９】
全ての文字列を読み込んでいない場合は（ステップＳ１２のＹｅｓ）、要約順序トライ構築部１１０は、未読の文字列のうちの最先の文字列Ｘ（ｙ）（０≦ｙ＜ｎ）を取得し、読み込む。
【００５０】
次に、要約順序トライ構築部１１０は、変数ｋを０にセットする（ステップＳ１３）。
次に、要約順序トライ構築部１１０は、変数ｋをインクリメントする（ステップＳ１４）。
【００５１】
次に、要約順序トライ構築部１１０は、変数ｋが、読み込んだ文字列Ｘ（ｙ）の文字数Ｋより大きいか否かを判断する（ステップＳ１５）。
変数ｋが、文字数Ｋより大きい場合は（ステップＳ１５のＹｅｓ）、ステップＳ１１に移行する。
【００５２】
一方、変数ｋが文字数Ｋ以下のときは（ステップＳ１５のＮｏ）、要約順序トライＴの構築を行う（ステップＳ１６）。
なお、ステップＳ１６のサブルーチンについては後に詳述する。
【００５３】
ところで、ステップＳ１１で未読の文字列の読み込みに失敗した場合、すなわち要約順序トライ構築部１１０が全ての文字列Ｘ１、・・・、Ｘ（ｎ）を読み込んだ場合は（ステップＳ１２のＮｏ）、分割境界決定部１２０は、分割境界決定を行う（ステップＳ１７）。
【００５４】
なお、ステップＳ１７のサブルーチンについては後に詳述する。
次に、文字列振り分け部１３０は、未読の文字列の読み込みを試みる（ステップＳ１８）。
【００５５】
次に、文字列振り分け部１３０は、文字列ファイルＸ内の全ての文字列Ｘ１、・・・、Ｘ（ｎ）を読み込んだか否かを判断する（ステップＳ１９）。
全ての文字列Ｘ１、・・・、Ｘ（ｎ）を読み込んでいない場合は（ステップＳ１９のＹｅｓ）、文字列振り分け部１３０は、未読の文字列Ｘ１、・・・、Ｘ（ｎ）のうちの最先の文字列Ｘ（ｙ）を取得し、その文字列Ｘ（ｙ）の最初の文字を読み込む。
【００５６】
次に、文字列振り分け部１３０は、変数ｋを０にセットする（ステップＳ２０）。
次に、文字列振り分け部１３０は、変数ｋをインクリメントする（ステップＳ２１）。
次に、文字列振り分け部１３０は、変数ｋが、読み込んだ文字列Ｘ（ｙ）の文字数Ｋより大きいか否かを判断する（ステップＳ２２）。
【００５７】
変数ｋが、文字数Ｋより大きい場合は（ステップＳ２２のＹｅｓ）、ステップＳ１８に移行する。
一方、変数ｋが文字数Ｋ以下のときは（ステップＳ２２のＮｏ）、文字列の振り分けを行う（ステップＳ２３）。
【００５８】
なお、ステップＳ２３のサブルーチンについては後に詳述する。
ところで、ステップＳ１８で、未読の文字列の読み込みに失敗した場合、すなわち、全ての文字列Ｘ１、・・・、Ｘ（ｎ）を読み込んだ場合は（ステップＳ１９のＮｏ）、最終処理を行う（ステップＳ２４）。具体的には、前述したように、文字列集合Ｕ１、・・・、Ｕ（ｍ）を作成し、振り分け文字列ソート部１４０が、文字列集合Ｕ１、・・・、Ｕ（ｍ）のソートを行い、文字列結合部１５０が、ソートが完了した文字列集合Ｕ１ａ、・・・、Ｕ（ｍ）ａを、この順番に（一意に）結合して、その結合されたデータをソート結果としてモニタ１１に出力する。その後、データソート処理を終了する。
【００５９】
次に、要約順序トライルーチンについて説明する。
図５は、要約順序トライルーチンを示すフローチャートである。
以下、図５に示す処理をステップ番号に沿って説明する。
【００６０】
なお、要約順序トライルーチンの動作は、特に記載がない場合は、要約順序トライ構築部１１０で行われる。
まず、初期設定を行う（ステップＳ３１）。具体的には、変数ｖをルートに設定し、変数Ｔをルートｖのみのトライに設定し、変数λを文字列Ｘ１の先頭文字に設定し、関数ｃｏｕｎｔ（ｖ）＝０に設定する。
【００６１】
次に、変数ｖに設定されているルート（ノード）のカウンタ値をインクリメントする（ステップＳ３２）。
次に、変数ｖに設定されているルート（ノード）のカウンタ値が成長頻度パラメータα以上か否かを判断する（ステップＳ３３）。
【００６２】
カウンタ値が成長頻度パラメータα未満のときは（ステップＳ３３のＮｏ）、ステップＳ３９に移行する。
一方、カウンタ値が成長頻度パラメータα以上のときは（ステップＳ３３のＹｅｓ）、関数ｇｏｔｏ（ｖ，λ）が存在するか否か、すなわち、変数ｖに設定されているルート（親ノード）から現在のデータをたどる移動先のノード（子ノード）が存在するか否かを判断する（ステップＳ３４）。
【００６３】
関数ｇｏｔｏ（ｖ，λ）が存在するときは（ステップＳ３４のＹｅｓ）、ステップＳ３６に移行する。一方、関数ｇｏｔｏ（ｖ，λ）が存在しないときは（ステップＳ３４のＮｏ）、関数ｍａｋｅ（ｖ，λ，ｗ）を実行して新たなノードｗを作成し、関数ｃｏｕｎｔ（ｗ）＝０に設定する（ステップＳ３５）。
【００６４】
次に、ｖ＝ｇｏｔｏ（ｖ，λ）を実行し、実行対象（制御対象）のノードを移動先のノードとし、その移動先の変数ｖに設定されているノードのカウンタ値をインクリメントする（ステップＳ３６）。
【００６５】
次に、現在の文字列Ｘ（ｊ）の次の文字があるか否か、すなわち現在の文字列Ｘ（ｊ）の全ての文字に対して要約順序トライルーチンを実行したか否かを確認する（ステップＳ３７）。
【００６６】
次の文字がある場合は（ステップＳ３７のＹｅｓ）、現在の文字列Ｘ（ｊ）内の次の文字を取り出し（ステップＳ３８）、ステップＳ３２に移行する。
一方、次の文字がない場合は、（ステップＳ３７のＮｏ）、次の文字列Ｘ（ｊ＋１）があるか否かを判断する（ステップＳ３９）。
【００６７】
次の文字列Ｘ（ｊ＋１）がある場合は（ステップＳ３９のＹｅｓ）、変数λを次の文字列Ｘ（ｊ＋１）の先頭の文字に設定し、ステップＳ３２に移行する（ステップＳ４０）。
一方、次の文字列Ｘ（ｊ＋１）が存在しない場合は（ステップＳ３９のＮｏ）、要約順序トライルーチンを終了する。
【００６８】
次に、分割境界決定ルーチンについて説明する。
図６は、分割境界決定ルーチンを示すフローチャートである。
以下、図６に示す処理をステップ番号に沿って説明する。
【００６９】
なお、分割境界決定ルーチンの動作は、特に記載がない場合は、分割境界決定部１２０で行われる。
まず、各バケットＢ１、・・・、Ｂ（ｎ）に入れる平均データ数ＤＡＶＥを求める（ステップＳ４１）。具体的には、文字列Ｘ１、・・・、Ｘ（ｎ）の個数ｎを、与えられる文字集合分割数βで割った値を平均データ数ＤＡＶＥとする。
【００７０】
次に、要約順序トライＴの各子ノードのカウンタ値の和が、親ノードのカウンタ値と等しいか否かを確認し、各子ノードのカウンタ値の和が、親ノードのカウンタ値と等しくないときは、各子ノードのカウンタ値の比率に応じて、各子ノードのカウンタ値の和が、親ノードのカウンタ値と等しくなるように、各子ノードのカウンタ値を調整し、近似的な要約順序トライＴ１を作成する（ステップＳ４２）。
【００７１】
次に、要約順序トライＴ１の深さ毎または幅毎に各ノードのカウンタ値を足し合わせていき、その値が平均データ数ＤＡＶＥに略等しくなったノードを境界とする（ステップＳ４３）。
【００７２】
次に、要約順序トライＴ１を探索し、境界に設定されたノードの前後で値を変えたＩＤを、変数ｖに設定されているノードに対して与える関数ｂｕｃｋｅｔ（ｖ）を決定する（ステップＳ４４）。
【００７３】
その後、分割境界決定ルーチンを終了する。
なお、ステップＳ４２のカウンタ値の調整は、分割境界決定ルーチンの前の段階で行ってもよい。
【００７４】
次に、データの振り分けルーチンについて説明する。
図７は、データの振り分けルーチンを示すフローチャートである。
以下、図７に示す処理をステップ番号に沿って説明する。
【００７５】
なお、データの振り分けルーチンの動作は、特に記載がない場合は、文字列振り分け部１３０で行われる。
まず、初期設定を行う（ステップＳ５１）。具体的には、変数λ１を文字列Ｘ１の先頭文字に設定し、変数ｖ１を要約順序トライＴのルートに設定する。
【００７６】
次に、関数ｇｏｔｏ（ｖ１，λ１）が存在するか否かを判断する（ステップＳ５２）。
関数ｇｏｔｏ（ｖ１，λ１）が存在するときは（ステップＳ５２のＹｅｓ）、変数ｖ１に対して関数ｇｏｔｏ（ｖ１，λ１）を実行する（ステップＳ５３）。
【００７７】
次に、現在の文字列Ｘ（ｊ）内に次の文字があるか否かを判断する（ステップＳ５４）。
次の文字がある場合は（ステップＳ５４のＹｅｓ）、現在の文字列Ｘ（ｊ）内の次の文字を変数λ１に設定し（ステップＳ５５）、ステップＳ５２に移行する。
【００７８】
一方、次の文字がない場合は（ステップＳ５４のＮｏ）、ステップＳ５７に移行する。
また、ステップＳ５２で関数ｇｏｔｏ（ｖ１，λ１）が存在しないときは（ステップＳ５２のＮｏ）、変数ｖ１に設定されているノードがリーフノードか否かを判断する（ステップＳ５６）。
【００７９】
変数ｖ１に設定されているノードがリーフノードのとき（ステップＳ５６のＹｅｓ）、現在の文字列Ｘ（ｊ）に関数ｂｕｃｋｅｔ（ｖ１）を割り当てて（ステップＳ５７）ステップＳ５９に移行する。
【００８０】
一方、変数ｖ１に設定されているノードがリーフノードでないとき（ステップＳ５６のＮｏ）要約順序トライＴに現在の文字列Ｘ（ｊ）の、リーフノード側に一番近いノードｗに関するバケットｂｕｃｋｅｔ（ｗ）を割り当てて（ステップＳ５８）、ステップＳ５９に移行する。
【００８１】
次に、次の文字列Ｘ（ｊ＋１）があるか否かを判断する（ステップＳ５９）。
次の文字列Ｘ（ｊ＋１）がある場合は（ステップＳ５９のＹｅｓ）、変数λ１を次の文字列Ｘ（ｊ＋１）の先頭の文字に設定し、変数ｖ１をルートに設定し（ステップＳ６０）、ステップＳ５２に移行する。
【００８２】
一方、次の文字列Ｘ（ｊ＋１）がない場合は（ステップＳ５９のＮｏ）、データの振り分けルーチンを終了する。
図８〜図１１は、データソート処理を具体的に示す概念図である。
【００８３】
図８は、文字列ファイルを表す図である。
図８に示すように、文字列ファイルＸには、上から順番に１０個の文字列Ｘ１、・・・、Ｘ１０＝＜ＢＥＡＤＳ、ＣＡＴ、ＤＡＴＡ、ＢＡＤ、ＢＥＡ、ＢＡＣＫ、ＤＡＴ、ＢＡＤＹ、ＣＡＫＥ、ＢＥＡＲ＞が格納されている。
【００８４】
以下では、文字列ファイルＸのデータソート処理について説明する。
図９は、要約順序トライを構築する際の課程を示す概念図である。
なお、図９中の紙面上、右側を「右」、左側を「左」という。
【００８５】
また、成長頻度パラメータα＝３、文字集合分割数β＝３とする。
まず、要約順序トライ構築部１１０は、文字列ファイルＸの最初の文字列「ＢＥＡＤＳ」を取得する。
【００８６】
図９（ａ）に示すように、要約順序トライ構築部１１０は、要約順序トライＴのルートのカウンタを１にセットし、現時点ではルートのみのトライであるので、最初の文字「Ｂ」に対応するノードを新たに作成する。このノードのカウンタ値を１にセットする。次に、２番目の文字列「ＣＡＴ」を取得する。図９（ｂ）に示すように、ルートのカウンタ値をインクリメントし、文字「Ｃ」に対応するノードを作成して、そのノードのカウンタ値を１にセットする。３番目の文字列「ＤＡＴＡ」についても、同様の処理を行い文字「Ｄ」に対応するノードを作成する。ここで、最初の文字「Ｂ」に対して右側に「Ｃ」に対応するノードを作成したので、これらのアルファベットに一意な方向性（Ａ、Ｂ、・・・Ｙ、Ｚ）を持たせるため、文字「Ｄ」に対応するノードは、文字「Ｃ」の右側に作成する。
【００８７】
次に、４番目の文字列「ＢＡＤ」を読み込んだとき、前に文字列「ＢＥＡＤＳ」を読み込んだときに既に文字「Ｂ」に対するノードが作成されているため、この文字「Ｂ」のノードに移動して、この文字「Ｂ」のノード（現在のノード）のカウンタ値（以下ノード「Ｂ」のカウンタ値ともいう）をインクリメントする。この結果、ノード「Ｂ」のカウンタ値は２になる。
【００８８】
次に、５番目の文字列「ＢＥＡ」を読み込んだとき、ノード「Ｂ」のカウンタ値をインクリメントする。その結果、ノード「Ｂ」のカウンタ値は３となり、成長頻度パラメータαと等しくなるので、図９（ｃ）に示すように、現在の文字列「ＢＥＡ」の２番目の文字「Ｅ」に関するノードを新たに作成し、文字「Ｅ」のノードに移動して、このノード「Ｅ」のカウンタ値を１にセットする。
【００８９】
次に、６番目の文字列「ＢＡＣＫ」を読み込んだとき、ノード「Ｂ」のカウンタ値をインクリメントする。その結果、ノード「Ｂ」のカウンタ値は４になり、ノード「Ｂ」のカウンタ値が成長頻度パラメータα以上になるため、図９（ｄ）に示すように、現在の文字列「ＢＡＣＫ」の２番目の文字「Ａ」に関するノードを新たに作成し、文字「Ａ」のノードに移動して、このノード「Ａ」のカウンタ値を１にセットする。
【００９０】
以上の操作を、最後の文字列「ＢＥＡＲ」まで繰り返して行うことにより、図９（ｅ）に示すように、最終的な要約順序トライＴが完成する。
次に、完成した要約順序トライＴを用いて、入力データの分割境界を決定する。
【００９１】
図１０は、要約順序トライを用いたデータ分割境界を示す概要図である。
分割境界決定部１２０は、データ集合分割数β＝３と、入力データ件数Ｎ＝１０との演算、Ｎ／β＝３．３３３・・・を実行する。
【００９２】
次に、図１０（ａ）に示すように、文字「Ａ」のノードのカウンタ値２、文字「Ｅ」のノードのカウンタ値２と、文字「Ｂ」のノードのカウンタ値６との調整を行うため、文字「Ａ」のノードのカウンタ値および文字「Ｅ」のノードのカウンタ値の比率（１：１）に応じて、それぞれ文字「Ａ」のノードのカウンタ値および文字「Ｅ」のノードのカウンタ値に１を加算し、近似的な要約順序トライＴ１を作成する。
【００９３】
次に、分割境界決定部１２０は、演算結果により要約順序トライＴ１内の１つのノードまたは各ノードの合計値が３または４となるようにカウンタ値の組み合わせを調節することによって、分割境界を決定する。
【００９４】
なお、ここでは、要約順序トライＴ１の最下位の子ノードのカウンタ値、すなわち、文字「Ａ」、文字「Ｅ」、文字「Ｃ」、文字「Ｄ」のノードのカウンタ値の組み合わせを調節する。
【００９５】
具体的には、文字「Ｃ」のノードのカウンタ値および文字「Ｄ」のノードのカウンタ値の和が２＋２＝４であるため、文字「Ａ」のノードと文字「Ｅ」のノードとの間、文字「Ｂ」のノードと文字「Ｃ」および文字「Ｄ」のノードとの間で分割すると判断し、これらの間に境界線を引き、文字「Ａ」のノードにＩＤ＝１、文字「Ｅ」のノードにＩＤ＝２、文字「Ｃ」および文字「Ｄ」のノードにＩＤ＝３を割り当てる。
【００９６】
ここで、要約順序トライＴ１の、任意の親ノードに対する子ノードが、一意な方向性を有しているため、割り当てられるＩＤのナンバーも一意な方向性を有する。すなわち、ＩＤナンバーの増加する方向と、アルファベットの増加する方向（Ａ→Ｚの方向）とが一致する。
【００９７】
次に、文字列振り分け部１３０は、文字列Ｘ１、・・・、Ｘ１０をもう一度スキャンして要約順序トライＴ１へ当てはめることにより、文字列Ｘ１、・・・、Ｘ１０を対応する３個（β個）のバケットに振り分ける。
【００９８】
図１１は、要約順序トライを用いたデータ振り分けを示す概要図である。
まず、１番目のデータ「ＢＥＡＤＳ」を取得し、要約順序トライＴ１の上を移動させる。「ＢＥ」まで読んだところで移動先のノードがなくなるので、分割決定段階で割り振られたノード「Ｅ」のＩＤを参照する。その結果、ＩＤ＝２であることが分かるので、データ「ＢＥＡＤＳ」は２番目のバケットＢ２に格納される。次に２番目のデータ「ＣＡＴ」を取得する。同様にして要約順序トライＴの上を移動させると、１文字目「Ｃ」で移動先のノードが無くなる。このノードのＩＤ＝３であるので、データ「ＣＡＴ」は３番目のバケットＢ３に格納される。以下、同様の処理を続けることにより、１０個の文字列Ｘ１、・・・、Ｘ１０＝＜ＢＥＡＤＳ、ＣＡＴ、ＤＡＴＡ、ＢＡＤ、ＢＥＡ、ＢＡＣＫ、ＤＡＴ、ＢＡＤＹ、ＣＡＫＥ、ＢＥＡＲ＞は、次のように３分割される。バケットＢ１：文字列集合Ｕ１＝＜ＢＡＤ、ＢＡＣＫ、ＢＡＤＹ＞、バケットＢ２：文字列集合Ｕ２＝＜ＢＥＡＤＳ、ＢＥＡ、ＢＥＡＲ＞、バケットＢ３：文字列集合Ｕ３＝<ＣＡＴ、ＤＡＴＡ、ＤＡＴ、ＣＡＫＥ＞。
【００９９】
さらに、既存のソート方法を用いてバケットＢ１、バケットＢ２およびバケットＢ３毎に各バケット内の文字列集合Ｕ１、Ｕ２、Ｕ３を、それぞれソートする。ソート結果の文字列集合Ｕ１ａ、Ｕ２ａ、Ｕ３ａは、Ｕ１ａからＵ３ａに向かって一意な方向性をもつ３つの文字列集合Ｕ１ａ＝＜ＢＡＣＫ、ＢＡＤ、ＢＡＤＹ＞、文字列集合Ｕ２ａ＝＜ＢＥＡ、ＢＥＡＤＳ、ＢＥＡＲ＞、文字列集合Ｕ３ａ＝<ＣＡＫＥ，ＣＡＴ、ＤＡＴ、ＤＡＴＡ＞となる。
【０１００】
そして、文字列集合Ｕ１ａとＵ２ａとＵ３ａとをこの順番で積み重ねることにより、文字列Ｘ１、・・・、Ｘ１０＝＜ＢＥＡＤＳ、ＣＡＴ、ＤＡＴＡ、ＢＡＤ、ＢＥＡ、ＢＡＣＫ、ＤＡＴ、ＢＡＤＹ、ＣＡＫＥ、ＢＥＡＲ＞のソート結果であるＵ＝＜ＢＡＣＫ、ＢＡＤ、ＢＡＤＹ、ＢＥＡ、ＢＥＡＤＳ、ＢＥＡＲ、ＣＡＫＥ、ＣＡＴ、ＤＡＴ、ＤＡＴＡ＞が得られる。
【０１０１】
以上述べたように、データソート処理装置１００によれば、データの重要な部分の情報を失うことなく構造が簡素化された要約順序トライＴを作成することにより、メモリ（ＲＡＭ１０２）の省容量化が図れ、データソート処理を簡易なものにすることができる。
【０１０２】
また、バケットＢ１、Ｂ２、Ｂ３にそれぞれ該当する文字列集合Ｕ１、Ｕ２、Ｕ３を格納し、所定のソート方法を用いて各バケットのソートを行い、ソートが完了した文字列集合Ｕ１ａ、Ｕ２ａ、Ｕ３ａを、一意に結合することにより、一度振り分けた文字列集合Ｕ１ａ、Ｕ２ａ、Ｕ３ａを再度併合することなくデータソート処理を完了させることができるため、データソート処理をより簡易なものとすることができる。また、与えられたＲＡＭ１０２の容量に応じてバケットＢ１、・・・、Ｂ（ｍ）の個数を調整することにより、各バケットに格納されるデータの容量を調節することができる。特に、データの容量が均等になるように、バケットＢ１、・・・、Ｂ（ｍ）の個数を調整することにより、メモリの容量を超えるバケットの作成を容易に防止することができ、バケットＢ１、・・・、Ｂ（ｍ）のソート処理においては、処理する文字列Ｘ１、・・・、Ｘ（ｎ）の容量が大きなものであっても、再度ＨＤＤ１０３にアクセスすることなくデータソート処理を行うことができる。これによりデータソート処理の高速化を図ることができる。
【０１０３】
また、得られた要約順序トライＴから近似的な要約順序トライＴ１を作成することにより、さらに処理の高速化と、使用するメモリの少領域化を図ることができる。
以上本発明の好適な実施の形態について詳述したが、本発明は、その特定の実施の形態に限定されるものではない。
【０１０４】
例えば、上記の説明ではソート対象として文字列を用いたが、これに限らず、例えば、数列を用いることもできる。この場合、数列内の全ての数字が、最も桁数の多い数字と同じ桁数となるように、数字の先頭に、それぞれ、０をつけることで本実施の形態と同様にデータソート処理を行うことができる。例えば、最も桁数の多い数字が「１１１１」の場合、６１は「００６１」とする。
【０１０５】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、データソート処理装置１００が有すべき機能の処理内容を記述したデータソート処理プログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等がある。磁気記録装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープ等がある。光ディスクには、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等がある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）等がある。
【０１０６】
プログラムを流通させる場合には、たとえば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１０７】
プログラムを実行するコンピュータは、たとえば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１０８】
（付記１）  複数のデータを有するデータファイルに対し、ソート処理を行うデータソート処理プログラムにおいて、
コンピュータを、
データに一定回数以上出現する共通接頭文字列を一意な順序で格納した要約順序トライを作成する要約順序トライ作成手段、
所定の前記ノード間に分割境界を設定する分割境界決定手段、
前記分割境界に基づいて、前記データファイルを複数のデータ集合に振り分けるデータ振り分け手段、
として機能させることを特徴とするデータソート処理プログラム。
【０１０９】
（付記２）  前記要約順序トライ作成手段は、ルートを作成し、前記各データの各文字をそれぞれ順番に読み込み、前記ルートに接続される前記ノードを過去に通ったデータが所定数あったとき、かつ、前記所定のノードに関連づけられた文字の次の文字に対応する子ノードが作成されていないときに、前記所定のノードを共通にする前記各子ノードが所定の配列となるように、前記子ノードを作成することを特徴とする付記１記載のデータソート処理プログラム。
【０１１０】
（付記３）  前記分割境界決定手段は、前記各データ集合が可及的に均等に振り分けられるように前記分割境界を決定することを特徴とする付記１記載のデータソート処理プログラム。
【０１１１】
（付記４）  前記各ノードは、前記各ノードに対応してそれぞれ設けられ、前記各データが前記各ノードを通る毎にインクリメントするカウンタを備え、
前記データの文字数Ｋ（Ｋ≧１）のデータを読み込んだとき、前記ルートから深さｋ（１≦ｋ≦Ｋ）のノードに設定されたカウンタが所定値以上のとき、かつ、深さ（ｋ＋１）の文字に対応するノードが存在しないときは、前記深さｋのノードに深さ（ｋ＋１）のノードを作成し、かつ、前記深さ（ｋ＋１）のノードを作成するときに、他の深さ（ｋ＋１）のノードが既に存在するときは、他の深さ（ｋ＋１）のノードに対して今回作成する前記深さ（ｋ＋１）のノードが、所定の配列となるように作成することを特徴とする付記１記載のデータソート処理プログラム。
【０１１２】
（付記５）  前記分割境界決定手段は、前記カウンタ値と予め設定される分割数とに基づいて、前記分割境界を設定することを特徴とする付記４記載のデータソート処理プログラム。
【０１１３】
（付記６）  前記分割数は、前記各データ集合の容量が前記コンピュータの不揮発性メモリの容量より小さくなるように設定されることを特徴とする付記５記載のデータソート処理プログラム。
【０１１４】
（付記７）  前記各データ集合を所定の方法でソートするデータ集合ソート手段を有することを特徴とする付記１記載のデータソート処理プログラム。
（付記８）  前記所定の方法でソートされた各データ集合を一意な順序で結合する結合手段を有することを特徴とする付記７記載のデータソート処理プログラム。
【０１１５】
（付記９）  前記分割境界決定手段は、ｉ番目の前記各ノードのカウンタ値の和が、（ｉ−１）番目の前記ノードのカウンタ値と異なるとき、前記ｉ番目の各ノードのカウンタ値の和が前記（ｉ−１）番目のノードのカウンタ値と等しくなるように、それぞれ前記ｉ番目の各ノードのカウンタ値を補正することを特徴とする付記１記載のデータソート処理プログラム。
【０１１６】
（付記１０）  前記ｉ番目の各ノードは、前記各ノードのカウンタ値の比率に応じて前記各ノードのカウンタ値を補正することを特徴とする付記９記載のデータソート処理プログラム。
【０１１７】
（付記１１）  複数のデータを有するデータファイルに対し、ソート処理を行うデータソート処理方法において、
要約順序トライ作成手段が、データに一定回数以上出現する共通接頭文字列を格納した要約順序トライを作成し、
分割境界決定手段が、所定のノード間に分割境界を設定し、
データ振り分け手段が、前記分割境界に基づいて、前記データファイルを複数のデータ集合に振り分ける、
ことを特徴とするデータソート処理方法。
【０１１８】
（付記１２）  複数のデータを有するデータファイルに対し、ソート処理を行うデータソート処理装置において、
データに一定回数以上出現する共通接頭文字列を格納した要約順序トライを作成する要約順序トライ作成手段と、
所定の前記ノード間に分割境界を設定する分割境界決定手段と、
前記分割境界に基づいて、前記データファイルを複数のデータ集合に振り分けるデータ振り分け手段と、
を有することを特徴とするデータソート処理装置。
【図面の簡単な説明】
【０１１９】
【図１】実施の形態に適用される発明の概念図である。
【図２】本実施の形態のコンピュータのハードウェア構成例を示す図である。
【図３】コンピュータの機能を示すブロック図である。
【図４】データソート処理の手順を示すフローチャートである。
【図５】要約順序トライルーチンを示すフローチャートである。
【図６】分割境界決定ルーチンを示すフローチャートである。
【図７】データの振り分けルーチンを示すフローチャートである。
【図８】文字列ファイルを表す図である。
【図９】要約順序トライを構築する際の課程を示す概念図である。
【図１０】要約順序トライを用いたデータ分割境界を示す概要図である。
【図１１】要約順序トライを用いたデータ振り分けを示す概要図である。
【図１２】複数の文字を有する文字列（データ）をトライ構造で示した図である。
【符号の説明】
【０１２０】
１  データ記憶手段
２  要約順序トライ作成手段
３  分割境界決定手段
４  データ振り分け手段
５  振り分けデータソート手段
６  結合手段
１００  データソート処理装置
１１０  要約順序トライ構築部
１２０  分割境界決定部
１３０  文字列振り分け部
１４０  振り分け文字列ソート部
１５０  文字列結合部
Ｔ、Ｔ１  要約順序トライ
【図１】
0004479908.tif 000002
【図２】
0004479908.tif 000003
【図３】
0004479908.tif 000004
【図４】
0004479908.tif 000005
【図５】
0004479908.tif 000006
【図６】
0004479908.tif 000007
【図７】
0004479908.tif 000008
【図８】
0004479908.tif 000009
【図９】
0004479908.tif 000010
【図１０】
0004479908.tif 000011
【図１１】
0004479908.tif 000012
【図１２】
0004479908.tif 000013