(57)【特許請求の範囲】
【請求項１】
ソートキーに基づいてソート対象データを並べ替えるソート装置であって、
ソートキーを所定の範囲に分割したソート区間ごとのソート対象データの出現頻度を求め、分布を分析する分布分析手段と、
前記分布分析手段による分析の結果、ソート区間ごとのソート対象データの分布の偏りが予め設定されたしきい値よりも大きい場合には、ソート対象データを一括してソートする方式を選択し、前記偏りが前記しきい値よりも小さい場合には、ソート対象データをソート区間ごとにソートする方式を選択するソート方式選択手段と、
前記ソート方式選択手段により選択された方式に従ってデータを並べ替えるソート実行手段と
を備えたことを特徴とするソート装置。
【請求項２】
前記ソート方式選択手段は、ソート対象データをソート区間ごとにソートする方式を選択した場合に、前記分布分析手段が求めたソート区間ごとのソート対象データの出現頻度に基づいて、各ソート区間に適用するソート手法を選択することを特徴とする請求項１に記載のソート装置。
【請求項３】
前記ソート方式選択手段は、ソート対象データの出現頻度が予め設定されたしきい値よりも大きいソート区間にはソート手法としてクイックソートを選択し、ソート対象データの出現頻度が前記しきい値よりも小さいソート区間にはソート手法としてラディックソートを選択することを特徴とする請求項２に記載のソート装置。
【請求項４】
ソートキーに基づいてソート対象データを並べ替えるソート方法であって、
ソートキーを所定の範囲に分割したソート区間ごとのソート対象データの出現頻度を求め、分布を分析する分布分析工程と、
前記分布分析工程による分析の結果、ソート区間ごとのソート対象データの分布の偏りが予め設定されたしきい値よりも大きい場合には、ソート対象データを一括してソートする方式を選択し、前記偏りが前記しきい値よりも小さい場合には、ソート対象データをソート区間ごとにソートする方式を選択するソート方式選択工程と、
前記ソート方式選択工程により選択された方式に従ってデータを並べ替えるソート実行工程と
を含んだことを特徴とするソート方法。
【請求項５】
前記ソート方式選択工程は、ソート対象データをソート区間ごとにソートする方式を選択した場合に、前記分布分析工程が求めたソート区間ごとのソート対象データの出現頻度に基づいて、各ソート区間に適用するソート手法を選択することを特徴とする請求項４に記載のソート方法。
【請求項６】
前記ソート方式選択工程は、ソート対象データの出現頻度が予め設定されたしきい値よりも大きいソート区間にはソート手法としてクイックソートを選択し、ソート対象データの出現頻度が前記しきい値よりも小さいソート区間にはソート手法としてラディックソートを選択することを特徴とする請求項５に記載のソート方法。
【請求項７】
ソートキーに基づいてソート対象データを並べ替えるソートプログラムであって、
ソートキーを所定の範囲に分割したソート区間ごとのソート対象データの出現頻度を求め、分布を分析する分布分析手順と、
前記分布分析手順による分析の結果、ソート区間ごとのソート対象データの分布の偏りが予め設定されたしきい値よりも大きい場合には、ソート対象データを一括してソートする方式を選択し、前記偏りが前記しきい値よりも小さい場合には、ソート対象データをソート区間ごとにソートする方式を選択するソート方式選択手順と、
前記ソート方式選択手順により選択された方式に従ってデータを並べ替えるソート実行手順と
をコンピュータに実行させることを特徴とするソートプログラム。
【請求項８】
前記ソート方式選択手順は、ソート対象データをソート区間ごとにソートする方式を選択した場合に、前記分布分析手順が求めたソート区間ごとのソート対象データの出現頻度に基づいて、各ソート区間に適用するソート手法を選択することを特徴とする請求項７に記載のソートプログラム。
【請求項９】
前記ソート方式選択手順は、ソート対象データの出現頻度が予め設定されたしきい値よりも大きいソート区間にはソート手法としてクイックソートを選択し、ソート対象データの出現頻度が前記しきい値よりも小さいソート区間にはソート手法としてラディックソートを選択することを特徴とする請求項８に記載のソートプログラム。
【請求項１０】
ソートキーに基づいてソート対象データを並べ替えるソートプログラムであって、
ソートキーを所定の範囲に分割したソート区間ごとのソート対象データの出現頻度を求め、分布を分析する分布分析手順と、
前記分布分析手順による分析の結果、ソート区間ごとのソート対象データの分布の偏りが予め設定されたしきい値よりも大きい場合には、ソート対象データを一括してソートする方式を選択し、前記偏りが前記しきい値よりも小さい場合には、ソート対象データをソート区間ごとにソートする方式を選択するソート方式選択手順と、
前記ソート方式選択手順により選択された方式に従ってデータを並べ替えるソート実行手順と
をコンピュータに実行させることを特徴とするソートプログラムを記憶したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、数値データ、テキストデータ等のソート対象データのソートに用いられるソート装置、ソート方法およびソートプログラム、並びにソートプログラムを記録したコンピュータ読み取り可能な記録媒体に関し、特に、ソート速度の高速化を図ることができるソート装置、ソート方法およびソートプログラム、並びにソートプログラムを記録したコンピュータ読み取り可能な記録媒体に関するものである。
【０００２】
従来より、ソート対象データに対してソートをかける方式として、様々なソート方式が考案されている。ソート方式としては、周知のクイックソート（quick sort）、ラディックソート（radic sort）、多重分割ソート等が挙げられる。しかしながら、これらのソート方式は、ソート対象データの量、性質に応じて一長一短があり、万能ではない。従って、ソート方式を選択する場合には、ソート対象データ、ソート方式に精通した高度な知識を有する者が関わる必要がある。このことから、従来より、ソートに関する高度な知識を有しない者であっても、最適なソートを実行することができる手段、方法が切望されている。
【０００３】
【従来の技術】
従来より、ソート方式として、上述したクイックソート、ラディックソート、多重分割ソート等が各分野で用いられている。クイックソートは、ソート対象データを細かなグループに分割していくことによって、高速にソートを実行するための方式である。ここで、ソート対象データをクイックソートによりソートする場合の手順についてつぎの（ａ−１）項〜（ｅ−１）項を参照して説明する。
【０００４】
0003765998.tif 000002
【０００５】
まず、（ａ−１）項に示した数列のソート対象データが与えられた場合、基準値として、例えば、最前列の「５」（＊印）が選択される。つぎに、（ｂ−１）項に示したように、基準値「５」（＊印）よりも小さな値（「３」、「２」、「４」、「１」）は、基準値「５」よりも前に配置される。一方、基準値「５」よりも大きい値（「６」、「８」、「７」）は、基準値「５」よりも後に配置される。これにより、（ｂ−１）項においては、括弧で示したように、基準値「５」より前に配置されたグループ（「３」、「２」、「４」、「１」）と、基準値「５」よりも後に配置されたグループ（「６」、「８」、「７」）という具合に未ソートの二つのグループに分けられる。
【０００６】
つぎに、（ｃ−１）項においては、括弧で示した二つのグループのそれぞれの先頭にある「３」（＊印）および「６」（＊印）が基準値とされる。つぎに、（ｄ−１）項に示したように、一方のグループにおいては、基準値「３」よりも小さな値（「２」、「１」）が基準値「３」よりも前に配置されるとともに、基準値「３」よりも大きな値（「４」）が基準値「３」よりも後に配置される。また、他方のグループにおいては、基準値「６」よりも大きな値（「８」、「７」）が基準値「６」よりも後に配置される。なお、この場合には、基準値「６」よりも小さい値は存在しない。
【０００７】
これにより、（ｄ−１）項においては、括弧で示したように、基準値「３」より前に配置されたグループ（「２」、「１」）と、基準値「６」よりも後に配置されたグループ（「８」、「７」）という具合に未ソートの二つのグループに分けられる。つぎに、（ｄ−１）項においては、括弧で示した二つのグループのそれぞれの先頭にある「２」（＊印）および「８」（＊印）が基準値とされる。
【０００８】
つぎに、（ｅ−１）項に示したように、一方のグループにおいては、基準値「２」よりも小さな値（「１」）が基準値「２」よりも前に配置される。なお、この場合には、基準値「２」よりも大きな値は存在しない。また、他方のグループにおいては、基準値「８」よりも小さな値（「７」）が基準値「８」よりも前に配置される。なお、この場合には、基準値「８」よりも大きな値は存在しない。以上説明したクイックソートの手順を経て、（ａ−１）項に示したソート対象データが、（ｅ−１）項に示したように昇順にソートされる。
【０００９】
上述したクイックソートは、ソート（ソート対象データの分割）が進むにつれて、ソート対象データが格納されているメモリのアクセスが局所的となるため、ソート速度が速いという特徴を備えている。ここでクイックソートのソート速度Ｏq は、ソート対象データの数をｎとすると、つぎの（１）式で表される。
Ｏq ＝ｎ・ｌｏｇ2ｎ  ・・・・・・・・・・（１）
【００１０】
また、前述したラディックソートは、ソート対象データを桁に分け、桁毎にソートを実行するための方式である。ここで、ソート対象データをラディックソートによりソートする場合の手順についてつぎの（ａ−２）項〜（ｃ−２）項を参照して説明する。
【００１１】
（ａ−２）  １７  ２０  ３０  ４５  ４６
（ｂ−２）  ２０  ３０  ４５  ４６  １７（１桁目をキーにソート）
（ｃ−２）  １７  ２０  ３０  ４５  ４６（２桁目をキーにソート）
【００１２】
ラディックソートを実行する場合には、二つのバッファ（バッファＡおよびバッファＢと称する）が用いられる。すなわち、（ａ−２）項のソート対象データ（２桁の数値）は、（ｂ−２）項に示したように、１桁目をキーにして昇順にソートされ、このソート結果は、バッファＡに格納される。つぎに、（ｃ−２）項に示したように、バッファＡに格納されているソート結果に対して、２桁目をキーに昇順にソートされる。このソート結果は、バッファＢに格納される。このように、ラディックソートにおいては、ソート対象データの桁数分だけ、バッファへのアクセスが必要とされる。
【００１３】
上述したラディックソートのソート速度Ｏr は、ソート対象データの桁数をｍ、ソート対象データの数をｎとするとつぎの（２）式で表される。
Ｏr ＝ｍ・ｎ       ・・・・・・・・・・（２）
【００１４】
また、多重分割ソートは、前述したクイックソートをより高速化するために考案された方式である。この多重分割ソートにおいては、ソート対象データが予め区間分割され、それぞれの区間単位でクイックソートが実行される。ここで、多重分割ソートのソート速度Ｏm は、区間数をＬ、ソート対象データの数をｎとするとつぎの（３）式で表され、理論的には（１）式のクイックソートのソート速度Ｏq よりもｎ／Ｌの分だけ高速化が期待される。
Ｏm ＝Ｌ・（ｎ／Ｌ）・ｌｏｇ2（ｎ／Ｌ）  ・・・・・・・・（３）
【００１５】
【発明が解決しようとする課題】
ところで、前述したように、クイックソートは、ソートが進むにつれて、メモリアクセスが局所的になるため、一般的にソート速度が速いという利点を備えている。しかしながら、ソート対象データの量が少ない場合は、（１）式および（２）式からわかるように、クイックソートのソート速度は、ラディックソートのソート速度に比して遅いという欠点があった。
【００１６】
一方、ラディックソートは、ソート対象データの量が少ない場合、ソート速度が速いという利点を備えている。しかしながら、実際には、ラディックソートでは、ソート対象データの量に対してバッファ容量が足りない場合、アクセスが遅い主記憶領域にソート用の領域を確保しなければならない。従って、このような場合には、主記憶領域のアクセス時間がソート速度に悪影響を及ぼすため、結果的にソート速度が遅くなるという欠点があった。
【００１７】
また、多重分割ソートは、理論的には最適な区間分割が行われた場合、クイックソートよりも高速にソートを実行することができるという利点を備えている。しかしながら、実際には、ソート対象データの分布状況を考慮して区間分割を行わない場合、区間分割に失敗することが多いため、何度も区間分割をし直さなければならず、その時間分だけクイックソートよりもソート速度が遅くなってしまうという問題があった。
【００１８】
このように、クイックソート、ラディックソートおよび多重分割ソートは、ソート対象データの量、性質に応じて一長一短があり、万能ではない。従って、ソート速度が速いソート方式を選択する場合には、ソート対象データ、ソート方式に精通した高度な知識を有する者が関わる必要がある。
【００１９】
本発明は、上記に鑑みてなされたもので、ソート対象データの性質、量に対応させてソート方式を自動選択することができるとともに、ソート速度を高速化することができるソート装置、ソート方法およびソートプログラム、並びにソートプログラムを記録したコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【００２０】
【課題を解決するための手段】
上記目的を達成するために、本発明は、ソートキーを所定の範囲に分割したソート区間ごとのソート対象データの出現頻度を求め、分布を分析する分布分析手段と、前記分布分析手段による分析の結果、ソート区間ごとのソート対象データの分布の偏りが予め設定されたしきい値よりも大きい場合には、ソート対象データを一括してソートする方式を選択し、前記偏りが前記しきい値よりも小さい場合には、ソート対象データをソート区間ごとにソートする方式を選択するソート方式選択手段と、前記ソート方式選択手段により選択された方式に従ってデータを並べ替えるソート実行手段とを備えたことを特徴とする。
【００２１】
この発明によれば、ソート区間ごとのデータの分布の偏りを分析し、偏りがしきい値よりも大きい場合はソートデータ全体を一括してソートし、偏りがしきい値よりも小さい場合はソート区間ごとにソートするように構成したので、高速なソートが可能であるがソート区間の分割状況にソート速度が依存する多重分割ソートの適用の可否をソート方式選択手段に自動的に判断させ、もって、ソート速度の高速化を実現することができる。
【００２２】
また、本発明は、前記ソート方式選択手段は、ソート対象データをソート区間ごとにソートする方式を選択した場合に、前記分布分析手段が求めたソート区間ごとのソート対象データの出現頻度に基づいて、各ソート区間に適用するソート手法を選択することを特徴とする。
【００２３】
この発明によれば、ソート区間ごとのソート対象データの出現頻度に応じて各ソート区間に適用するソート手法を選択するように構成したので、各ソート区間ごとにデータ量に応じた最適なソート手法を自動選択することができ、もって、ソート速度の高速化を実現することができる。
【００２４】
【発明の実施の形態】
以下、図面を参照して本発明にかかるソート装置、ソート方法およびソートプログラム、並びにソートプログラムを記録したコンピュータ読み取り可能な記録媒体の一実施の形態について詳細に説明する。
【００２５】
図１は、本発明にかかる一実施の形態の構成を示すブロック図である。この図において、ソート対象データ入力部１０は、例えば、ソート対象データを入力する機能を備えている。ここでソート対象データは、後述するクイックソート、ラディックソート等のソート手法に基づいてソートされるデータ（データサイズ８バイト）である。以下では、文書に含まれる単語をソート対象データとした場合を一例にして説明する。具体的には、文書／文書番号対応テーブル８０（図２（ａ）参照）および単語／単語番号対応テーブル８１（図２（ｂ）参照）からソート対象データが生成される。
【００２６】
図２（ａ）に示した文書／文書番号対応テーブル８０は、複数の文書（This is a book,That is a book,・・・）と、これらの文書にそれぞれ付与された文書番号（１〜Ｎ）との対応関係を表すテーブルであり、記憶部２０に格納されている。一方、図２（ｂ）に示した単語／単語番号対応テーブル８１は、文書／文書番号対応テーブル８０の複数の文書に含まれる複数の単語（This,is,a,book,that,・・・）と、これらの単語にそれぞれ付与された単語番号（１、２、３、・・・、２５０００、・・・）との対応関係を表すテーブルであり、記憶部２０に格納されている。
【００２７】
一実施の形態では、図３（ａ）に示したように上記単語を文書番号と単語番号とを対応づけたものをソート対象データＤ1 、Ｄ2 〜Ｄm 、・・・（総称してソート対象データ群９０と称する）としている。例えば、ソート対象データＤ1 は、図２（ｂ）に示した単語番号１の単語（This）に対応しており、［１，１］で表現される。この［１，１］における右側の数字は、図２（ａ）に示した文書番号１に対応しており、左側の数字は、図２（ｂ）に示した単語番号１に対応している。同様にして、ソート対象データＤ2 は、図２（ｂ）に示した単語番号２の単語（is）に対応しており、［２，１］で表現される。この［２，１］における右側の数字は、図２（ａ）に示した文書番号１に対応しており、左側の数字は、図２（ｂ）に示した単語番号２に対応している。
【００２８】
図１に戻り、記憶部２０には、上述した文書／文書番号対応テーブル８０、単語／単語番号対応テーブル８１、ソート対象データ群９０、ソート結果データ９１（図３（ｂ）参照）、分布測定セル９２（図４（ａ）参照）や、各種データが格納される。分布測定セル９２は、ソート対象データ群９０の分布の測定や、ソート方式決定等の際に用いられるワークシートである。
【００２９】
具体的には、分布測定セル９２は、セル番号０〜１０、・・・が付与されたセル９２0 〜９２10 、・・・を有している。これらのセル９２0 〜９２10 、・・・は、図２（ｂ）に示した単語番号の範囲（ソート区間）に対応付けられている。例えば、セル９２0 は、単語番号が１、２の範囲に対応付けられており、セル９２1 は、単語番号が３、４の範囲に対応付けられている。
【００３０】
また、分布測定セル９２においては、「単語番号の範囲」、「出現頻度」、「データ開始位置」および「ソート方式」というレコードがある。「単語番号の範囲」は、図２（ｂ）に示した単語／単語番号対応テーブル８１の単語番号の範囲（ソート区間）を表すレコードである。「出現頻度」は、「単語番号の範囲」内におけるソート対象データ（単語）の出現頻度（出現回数）を表すレコードである。「データ開始位置」は、それぞれのソート区間の始点に位置するソート対象データの位置を表すレコードである。ソート方式は、それぞれのソート区間で採用されるソート方式（クイックソートまたはラディックソート）を表すレコードである。
【００３１】
図１に戻り、分布集計部３０は、ソート対象データ群９０（図３（ａ）参照）の分布を集計する。この分布集計結果は、分布測定セル９２（図４（ａ）参照）の「出現頻度」に格納される。ソート方式選択部４０は、分布集計部３０の分布集計結果に基づいて、ソート区間毎に最適なソート方式を選択する。
【００３２】
具体的には、「出現頻度」が３２７６８以上である場合、ソート方式選択部４０は、当該ソート区間のソート方式としてクイックソートを選択する。一方、「出現頻度」が３２７６８未満である場合、ソート方式選択部４０は、当該ソート区間のソート方式としてラディックソートを選択する。ソート区間設定部５０は、ソート区間を設定する。ソート実行部６０は、ソート方式選択部４０により選択されたソート方式により、ソート区間毎にソートを実行する。表示部７０は、ソート実行部６０のソート結果を表示する。
【００３３】
つぎに、上述した一実施の形態の動作について、図５〜図８を参照しつつ説明する。図５および図６は、一実施の形態の動作を説明するフローチャートである。図７は、図５に示した分布集計処理を説明するフローチャートである。図８は、一実施の形態におけるソート対象データの区間振り分け処理を説明する図である。
【００３４】
図５に示したステップＳＡ１では、ソート対象データ入力部１０は、ソート対象データ群９０（図３（ａ）参照）を入力し、これらを記憶部２０に格納する。ステップＳＡ２では、分布集計部３０は、ソート対象データ群９０の分布測定方式を指定する。この場合、ソート対象データ群９０がｌｏｇ分布に従って分布しているものとすると、分布集計部３０は、分布測定方式としてｌｏｇ分布に基づく方式を指定する。
【００３５】
ステップＳＡ３では、分布集計部３０は、図３（ａ）に示したソート対象データ群９０の先頭（ソート対象データＤ1 ）にデータ用ポインタＰd をセットする。ステップＳＡ４では、分布集計部３０は、データ用ポインタＰd に対応するソート対象データＤ1 の単語番号１をキーとして、ソート対象データＤ1 が図４（ａ）に示した分布測定セル９２のセル９２0 〜９２10 、・・・のうち該当するセルを求める。この場合、ソート対象データＤ1 の単語番号が１であるため、分布集計部３０は、セル９２0 （単語番号の範囲＝１、２）を求める。
【００３６】
ステップＳＡ５では、分布集計部３０は、ステップＳＡ４で求めたセル９２0 の「出現頻度」を１インクリメントする。ステップＳＡ６では、分布集計部３０は、図３（ａ）に示したデータ用ポインタＰd がソート対象データ群９０の終端を指しているか否かを判断し、この場合、判断結果を「Ｎｏ」とする。ステップＳＡ７では、分布集計部３０は、図３（ａ）に示したデータ用ポインタＰd を一つ進める。これにより、データ用ポインタＰd は、つぎのソート対象データＤ2 にセットされる。以後、ステップＳＡ４〜ステップＳＡ７が繰り返されることにより、図４（ａ）に示したセル９２0 〜９２10 、・・・のそれぞれの「出現頻度」が１インクリメントされる。
【００３７】
そして、ステップＳＡ６の判断結果が「Ｙｅｓ」になると、分布集計部３０は、ステップＳＡ８の分布集計処理を実行する。この時点では、図４（ｂ）に示したように分布測定セル９２のそれぞれのセルの「出現頻度」には、ソート対象データ群９０の分布を表す数値が格納されている。例えば、セル９２0 （単語番号１、２）の「出現頻度」は、６５０００とされている。これは、ソート対象データ群９０の中に単語番号１、２のソート対象データが６５０００個含まれていることを意味している。
【００３８】
以下、図７を参照して、分布集計処理について詳述する。同図に示したステップＳＢ１では、分布集計部３０は、内部変数ＣＮＴおよび内部変数ＭＡＸのそれぞれに０を代入する。ステップＳＢ２では、分布集計部３０は、図４（ｂ）に示した分布測定セル９２の先頭のセル（セル９２0 ）にセル用ポインタＰc をセットする。ステップＳＢ３では、分布集計部３０は、セル用ポインタＰc が分布測定セル９２の終端のセルを指しているか否かを判断し、この場合、判断結果を「Ｎｏ」とする。
【００３９】
ステップＳＢ４では、分布集計部３０は、セル用ポインタＰc が指しているセル（セル９２0 ）に要素（「出現頻度」の値）が存在するか否かを判断する。この場合、要素として「出現頻度」＝６５０００が存在するため、分布集計部３０は、ステップＳＢ４の判断結果を「Ｙｅｓ」とする。一方、ステップＳＢ４の判断結果が「Ｎｏ」である場合、分布集計部３０は、ステップＳＢ６の判断を行う。この場合、ステップＳＢ５では、分布集計部３０は、内部変数ＣＮＴを１インクリメントする。
【００４０】
ステップＳＢ６では、分布集計部３０は、当該セルの要素数（「出現頻度」の値）が、内部変数ＭＡＸ（この場合、０）以上であるか否かを判断し、この判断結果を「Ｙｅｓ」とする。一方、ステップＳＢ６の判断結果が「Ｎｏ」である場合、分布集計部３０は、ステップＳＢ８の処理を実行する。この場合、ステップＳＢ７では、分布集計部３０は、内部変数ＭＡＸに要素数（この場合、「出現頻度」＝６５０００）を代入する。ステップＳＢ８では、分布集計部３０は、図４（ｂ）に示したセル用ポインタＰc を一つ進める。これにより、セル用ポインタＰc は、つぎのセル９２1 にセットされる。以後、ステップＳＢ３〜ステップＳＢ８が繰り返される。
【００４１】
そして、ステップＳＢ３の判断結果が「Ｙｅｓ」になると、ステップＳＢ９では、分布集計部３０は、図４（ｂ）に示したセル９２0 〜９２10 、・・・のそれぞれの「出現頻度」の合計値を、内部変数ＣＮＴで除算した結果を平均値ＡＶとして算出した後、図５に示したメインルーチンへ戻る。ステップＳＡ９では、分布集計部３０は、内部変数ＭＡＸと平均値ＡＶとの差が、予め設定されたしきい値Ｃ１以上である場合、ソート対象データ群９０の分布が偏っているものとし、判断結果を「Ｙｅｓ」とする。
【００４２】
ステップＳＡ１０では、ソート方式選択部４０は、ステップＳＡ９の判断結果を受けて、ソート方式としてクイックソートを選択する。このクイックソートは、ソート対象データ群９０の分布が偏っている場合にソート速度の高速化に有効なソート手法である。ステップＳＡ１１では、ソート区間設定部５０は、図４（ｂ）に示した分布測定セル９２のソート区間を設定する。
【００４３】
具体的には、ソート区間設定部５０は、分布測定セル９２のセル数を１とする。これにより、ソート対象データ群９０の全てに対してクイックソートが適用される。ステップＳＡ１２では、ソート実行部６０は、ソート対象データ群９０に対してクイックソートを実行する。ステップＳＡ１３では、ソート実行部６０は、クイックソートによるソート結果をソート結果データ９１（図３（ｂ）参照）として表示部７０に表示させる。
【００４４】
一方、ステップＳＡ９の判断結果が「Ｎｏ」である場合、ステップＳＡ１４では、ソート方式選択部４０は、図４（ｃ）に示した分布測定セル９２の先頭のセル９２0 にセル用ポインタＰc をセットする。ステップＳＡ１５では、ソート方式選択部４０は、セル用ポインタＰc に対応するセル（この場合、セル９２0 ）の出現頻度（＝６５０００）が、予め設定されたしきい値Ｃ２（＝３２７６８）以上であるか否かを判断する。この場合、ソート方式選択部４０は、ステップＳＡ１５の判断結果を「Ｙｅｓ」とする。
【００４５】
ステップＳＡ１６では、ソート方式選択部４０は、ステップＳＡ１５の判断結果を受けて、ソート方式としてクイックソート（同図では「quick」と表記）を、セル用ポインタＰc に対応するセル（セル９２0 ）の「ソート方式」に設定する。一方、ステップＳＡ１５の判断結果が「Ｎｏ」である場合、ステップＳＡ１７では、ソート方式選択部４０は、ソート方式としてラディックソート（同図では「radic」と表記）を、セル用ポインタＰc に対応するセルの「ソート方式」に設定する。ステップＳＡ１８では、ソート方式選択部４０は、セル用ポインタＰc が分布測定セル９２の終端のセルを示しているか否か判断し、この場合、判断結果を「Ｎｏ」とする。
【００４６】
ステップＳＡ１９では、ソート方式選択部４０は、図４（ｃ）に示したセル用ポインタＰc を一つ進める。これにより、セル用ポインタＰc は、つぎのセル９２1 ににセットされる。以後、ステップＳＡ１５〜ステップＳＡ１９が繰り返されることにより、図４（ｃ）に示したセル９２1 〜９２10 、・・・のそれぞれの「ソート方式」にクイックソートまたはラディックソートが設定される。
【００４７】
そして、ステップＳＡ１８の判断結果が「Ｙｅｓ」になると、ソート区間設定部５０は、図６に示したステップＳＡ２０以降の処理を実行する。このステップＳＡ２０以降の処理では、図４（ｄ）に示したように、ソート対象データ群９０（図３（ａ）参照）がセル９２0 〜９２10 、・・・のそれぞれに振り分けられる。具体的には、ステップＳＡ２０では、ソート区間設定部５０は、内部変数ＳＵＭに０を代入する。ステップＳＡ２１では、ソート区間設定部５０は、図４（ｄ）に示した分布測定セル９２の先頭のセル（セル９２0 ）にセル用ポインタＰc をセットする。
【００４８】
ステップＳＡ２２では、ソート区間設定部５０は、セル用ポインタＰc が、分布測定セル９２の終端のセルを指しているか否かを判断し、この場合、判断結果を「Ｎｏ」とする。ステップＳＡ２３では、ソート区間設定部５０は、図８（ａ）に示したソート対象データＤ１ 〜Ｄ１１１００２、・・・（図３（ａ）に示したソート対象データ群９０）の先頭（ソート対象データＤ１）から内部変数ＳＵＭ（この場合、０）右側にずれた位置のデータ（この場合、ソート対象データＤ１）にデータ用ポインタＰd をセットする。
【００４９】
ステップＳＡ２４では、ソート区間設定部５０は、上記データ用ポインタＰd の位置に交換データポインタＰa0 をセットする。ステップＳＡ２５では、ソート区間設定部５０は、現在の内部変数ＳＵＭ（＝０）に、分布測定セル９２（図４（ｄ）参照）のセル用ポインタＰc に対応するセル（この場合、セル９２0 ）の「出現頻度」（この場合、６５０００）を加算し、加算結果を変数ＳＵＭ（この場合、６５０００）とする。ステップＳＡ２６では、ソート区間設定部５０は、分布測定セル９２（図４（ｄ）参照）のセル用ポインタＰc を一つ進める。
【００５０】
これにより、セル用ポインタＰc は、つぎのセル９２1 に位置する。以後、ステップＳＡ２２〜ステップＳＡ２６の処理が繰り返されることにより、図８（ａ）に示したように、交換データポインタＰa1 〜Ｐa3 、・・・がそれぞれソート区間Ｋ０〜Ｋ３、・・・の先頭のソート対象データにそれぞれセットされる。これらのソート区間Ｋ０〜Ｋ３、・・・は、分布測定セル９２（図４（ｄ）参照）のセル番号０〜３、・・・に対応している。また、ソート区間Ｋ０〜Ｋ３、・・・のそれぞれに存在するソート対象データの数（６５０００個、３１０００個、１５０００個、・・・）は、分布測定セル９２（図４（ｄ）参照）の「出現頻度」に対応している。
【００５１】
そして、ステップＳＡ２２の判断結果が「Ｙｅｓ」になると、ステップＳＡ２７では、ソート区間設定部５０は、図８（ａ）に示したように、交換データポインタＰa0 、Ｐa1 、Ｐa2 、Ｐa3 、・・・に対応するソート対象データＤ１、Ｄ６５００１、Ｄ９６００１、Ｄ１１０００１、・・・をスタック９３に格納する。このスタック９３は、記憶部２０に確保された領域である。
【００５２】
ステップＳＡ２８では、ソート区間設定部５０は、全ての交換データポインタＰa0 、Ｐa1 、Ｐa2 、Ｐa3 、・・・を一つ進める。ステップＳＡ２９では、ソート区間設定部５０は、図８（ｂ）に示したようにスタック９３から一つのソート対象データ（同図ではソート対象データＤ１）を取り出す。ステップＳＡ３０では、ソート区間設定部５０は、ステップＳＡ４の場合と同様にして、ソート対象データＤ１に対応するソート区間（この場合、ソート区間Ｋ１）を求める。
【００５３】
ステップＳＡ３１では、ソート区間設定部５０は、ステップＳＡ３０で求めたソート区間（この場合、ソート区間Ｋ１）の交換データポインタ（この場合、交換データポインタＰa1 ）が指すソート対象データ（この場合、ソート対象データＤ６５００２）を取り出す。ステップＳＡ３２では、ソート区間設定部５０は、ステップＳＡ２９でスタック９３から取り出されたソート対象データ（この場合、ソート対象データＤ１）を、ステップＳＡ３１における交換データポインタ（この場合、交換データポインタＰa1 ）が指すデータ位置（６５００１）に格納する。
【００５４】
ステップＳＡ３３では、ソート区間設定部５０は、当該ソート区間の終端に交換データポインタ（この場合、交換データポインタＰa1 ）が位置しているか否かを判断し、この場合、判断結果を「Ｎｏ」とする。ステップＳＡ３４では、ソート区間設定部５０は、当該交換データポインタ（この場合、交換データポインタＰa1 ）を一つ進める。一方、ステップＳＡ３３の判断結果が「Ｙｅｓ」である場合、ステップＳＡ３５では、ソート区間設定部５０は、当該交換データポインタを削除する。
【００５５】
ステップＳＡ３６では、ソート区間設定部５０は、ステップＳＡ３１で取り出したソート対象データ（この場合、ソート対象データＤ６５００２）をスタック９３に格納する。すなわち、ソート対象データＤ１とソート対象データＤ６５００２とが交換されたのである。ステップＳＡ３７では、ソート区間設定部５０は、交換データポインタが存在するか否かを判断し、この場合、判断結果を「Ｙｅｓ」とする。以後、ステップＳＡ２９〜ステップＳＡ３７の処理が繰り返されることにより、ソート対象データの振り分けが行われる。
【００５６】
そして、ステップＳＡ３７の判断結果が「Ｎｏ」になると、ステップＳＡ３８では、スタック９３内のソート対象データを対応するソート区間に格納する。これにより、図８（ａ）に示したソート対象データＤ１ 〜Ｄ１１１００２、・・・がソート区間Ｋ０〜Ｋ３、・・・にそれぞれ振り分けられたのである。図４（ｄ）には、複数のソート対象データ（［１，１］、［１，５］、・・・）が振り分けられた状態が図示されている。
【００５７】
ステップＳＡ３９では、ソート実行部６０は、ソート区間単位に振り分けられたソート対象データに対して、分布測定セル９２の「ソート方式」に基づいて、ソートをそれぞれ実行する。具体的には、ソート区間Ｋ１（図８（ｂ）参照）内のソート対象データには、クイックソート（図４（ｄ）：セル９２0 の「quick」参照）が適用される。
【００５８】
また、ソート区間Ｋ２内のソート対象データには、ラディックソート（図４（ｄ）：セル９２1 の「radic」参照）が適用される。ソート区間Ｋ３以降のソート対象データについても同様である。ステップＳＡ４０では、ソート実行部６０は、クイックソートによるソート結果をソート結果データ９１（図３（ｂ）参照）として表示部７０に表示させる。
【００５９】
ここで、同一のソート対象データに対して、従来のクイックソートを適用した場合のソート速度と、一実施の形態を適用した場合のソート速度との比較例を以下に示す。このように、一実施の形態によれば、従来に比して大幅にソート速度の高速化を図ることができる。
【００６０】
0003765998.tif 000003
【００６１】
以上説明したように、一実施の形態によれば、ソート対象データ群９０の分布を分析した結果に基づいて、ソート区間を設定し、さらにソート区間毎にソート対象データの出現頻度を求め、出現頻度としきい値との比較結果により、クイックソートまたはラディックソートをソート区間単位で選択するようにしたので、ソート対象データ群の分布（性質、量）に対応させてソート方式を自動選択することができ、従来に比べてソート速度を高速化することができる。
【００６２】
以上本発明にかかる一実施の形態について図面を参照して詳述してきたが、具体的な構成例はこの一実施の形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等があっても本発明に含まれる。たとえば、前述した一実施の形態においては、ソート装置の機能を実現するためのソートプログラムを図９に示したコンピュータ読み取り可能な記録媒体２００に記録して、この記録媒体２００に記録されたソートプログラムを同図に示したコンピュータ１００に読み込ませ、実行することによりソートを行うようにしてもよい。
【００６３】
図９に示したコンピュータ１００は、上記ソートプログラムを実行するＣＰＵ１０１と、キーボード、マウス等の入力装置１０２と、各種データを記憶するＲＯＭ（Read Only Memory）１０３と、演算パラメータ等を記憶するＲＡＭ（Random Access Memory）１０４と、記録媒体２００からソートプログラムを読み取る読取装置１０５と、ディスプレイ、プリンタ等の出力装置１０６と、装置各部を接続するバスＢＵとから構成されている。
【００６４】
ＣＰＵ１０１は、読取装置１０５を経由して記録媒体２００に記録されているソートプログラムを読み込んだ後、ソートプログラムを実行することにより、前述したソートを行う。なお、記録媒体２００には、光ディスク、フロッピーディスク、ハードディスク等の可搬型の記録媒体が含まれることはもとより、ネットワークのようにデータを一時的に記録保持するような伝送媒体も含まれる。
【００６５】
【発明の効果】
以上説明したように、本発明によれば、ソート区間ごとのデータの分布の偏りを分析し、偏りがしきい値よりも大きい場合はソートデータ全体を一括してソートし、偏りがしきい値よりも小さい場合はソート区間ごとにソートするように構成したので、高速なソートが可能であるがソート区間の分割状況にソート速度が依存する多重分割ソートの適用の可否をソート方式選択手段に自動的に判断させ、もって、ソート速度の高速化を実現することができるという効果を奏する。
【００６６】
前述したように、多重分割ソートは、データの分布に偏りがないようにソート分割されている場合において他のソート手法よりも高速なソートを実現することができるが、ソート分割が適切におこなわれるまで区間分割を何度も繰り返したのでは結果としてソート処理に要する時間が長くなってしまう。そこで、本発明では、区間分割の結果、各ソート区間のデータ分布に偏りが生じた場合は多重分割ソートを適用しないこととし、ソート区間の再設定に要する時間を省略してソート処理に要する時間を短縮している。
【００６７】
また、本発明によれば、ソート区間ごとのソート対象データの出現頻度に応じて各ソート区間に適用するソート手法を選択するように構成したので、各ソート区間ごとにデータ量に応じた最適なソート手法を自動選択することができ、もって、ソート速度の高速化を実現することができるという効果を奏する。
【００６８】
また、本発明によれば、クイックソートまたはラディックソートを選択し、選択結果をそれぞれのソート区間に適用するようにしたので、クイックソート、ラディックソートの特長を生かすことができ、ソート速度の高速化を図ることができるという効果を奏する。
【図面の簡単な説明】
【図１】本発明にかかる一実施の形態の構成を示すブロック図である。
【図２】同一実施の形態で用いられる文書／文書番号対応テーブル８０および単語／単語番号対応テーブル８１を示す図である。
【図３】同一実施の形態におけるソート対象データ群９０およびソート結果データ９１を示す図である。
【図４】同一実施の形態で用いられる分布測定セル９２を示す図である。
【図５】同一実施の形態の動作を説明するフローチャートである。
【図６】同一実施の形態の動作を説明するフローチャートである。
【図７】図５に示した分布集計処理を説明するフローチャートである。
【図８】同一実施の形態におけるソート対象データの区間振り分け処理を説明する図である。
【図９】同一実施の形態の変形例を示すブロック図である。
【符号の説明】
３０  分布集計部
４０  ソート方式選択部
５０  ソート区間設定部
６０  ソート実行部
１００  コンピュータ
１０１  ＣＰＵ
２００  記録媒体
【図１】
0003765998.tif 000004
【図２】
0003765998.tif 000005
【図３】
0003765998.tif 000006
【図４】
0003765998.tif 000007
【図５】
0003765998.tif 000008
【図６】
0003765998.tif 000009
【図７】
0003765998.tif 000010
【図８】
0003765998.tif 000011
【図９】
0003765998.tif 000012