整列装置、その制御方法、ならびに、プログラム
【課題】 順序付けが可能なデータを昇順に整列させるのに好適な整列装置等を提供する。
【解決手段】 整列装置２０１の入力受付部２０２は、データの入力を受け付け、一時記憶部２０３は、受け付けられたデータを所定のデータ制限に至るまで記憶し、所定のデータ制限に至るかデータの入力が完了すると、マージ部２０４は、一時記憶部２０３に記憶されたデータを昇順に整列したものを不揮発記憶部２０５に記憶された昇順に整列済みのデータに昇順にマージして不揮発記憶部２０５を更新し、消去部２０６は、マージ部２０４によるマージが終わると一時記憶部２０３をクリアし、データ整列の結果が不揮発記憶部２０５に得られる。
【解決手段】 整列装置２０１の入力受付部２０２は、データの入力を受け付け、一時記憶部２０３は、受け付けられたデータを所定のデータ制限に至るまで記憶し、所定のデータ制限に至るかデータの入力が完了すると、マージ部２０４は、一時記憶部２０３に記憶されたデータを昇順に整列したものを不揮発記憶部２０５に記憶された昇順に整列済みのデータに昇順にマージして不揮発記憶部２０５を更新し、消去部２０６は、マージ部２０４によるマージが終わると一時記憶部２０３をクリアし、データ整列の結果が不揮発記憶部２０５に得られる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、順序付けが可能なデータを昇順に整列させるのに好適な整列装置、その制御方法、ならびに、これらをコンピュータにて実現するためのプログラムに関する。
【背景技術】
【０００２】
従来から、順序付けが可能なデータを昇順に整列させるためのソート技術については、これを高速に行うアルゴリズムが提案されている。たとえば、以下の文献に、このようなソート技術を利用したデータ検索の技術が開示されている。
【特許文献１】特開２００１−０３４６２９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
このようなソート技術は、たとえば大規模な転置ファイルを作る上で重要な技術となる。したがって、ソートを高速に行うための、様々な手法が強く求められている。
【０００４】
本発明は、上記の課題を解決するもので、順序付けが可能なデータを昇順に整列させるのに好適な整列装置、その制御方法、ならびに、これらをコンピュータにて実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００６】
本発明の第１の観点に係る整列装置は、所定の順序付けが可能な複数のデータを昇順に整列し、入力受付部、不揮発記憶部、一時記憶部、マージ部、消去部を備え、以下のように構成する。
【０００７】
ここで、入力受付部は、整列されるべきデータの入力を受け付ける。
【０００８】
一方、不揮発記憶部は、当該所定の順序付けにより既に昇順に整列されたデータを、不揮発に記憶する。
【０００９】
さらに、一時記憶部は、入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶する。
【００１０】
そして、マージ部は、一時記憶部が所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させる。
【００１１】
一方、消去部は、一時記憶部が所定のデータ量制限に至った場合、マージ部によるマージが行われた後に、一時記憶部に記憶されたデータを消去する。
【００１２】
また、本発明の整列装置において、一時記憶部に入力されたデータが記憶される毎に、一時記憶部に記憶されるデータは、当該所定の順序付けにより昇順に整列されるように構成することができる。
【００１３】
また、本発明の整列装置において、一時記憶部に記憶されるデータは、所定のデータ量制限に至った、もしくは、当該データの入力が終了した後、マージ部により取得される前に、当該所定の順序付けにより昇順に整列されるように構成することができる。
【００１４】
また、本発明の整列装置において、マージ部は、一時記憶部に記憶されるデータと、不揮発部に記憶されるデータと、をマージソートするように構成することができる。
【００１５】
また、本発明の整列装置において、一時記憶部は、ランダムアクセスメモリであり、不揮発記憶部は、ハードディスクであり、不揮発記憶部は、できるだけ連続したセクタに、当該所定の順序付けにより昇順に整列されたデータを記憶するように構成することができる。
【００１６】
本発明のその他の観点に係る制御方法は、所定の順序付けが可能な複数のデータを昇順に整列し、入力受付部、当該所定の順序付けにより既に昇順に整列されたデータが不揮発に記憶される不揮発記憶部、一時記憶部、マージ部、消去部を有する整列装置を制御し、入力受付工程、一時記憶工程、マージ工程、消去工程を備え、以下のように構成する。
【００１７】
すなわち、入力受付工程では、入力受付部が、整列されるべきデータの入力を受け付ける。
【００１８】
一方、一時記憶工程では、一時記憶部に、入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶させる。
【００１９】
さらに、マージ工程では、マージ部が、一時記憶工程にて所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させる。
【００２０】
そして、消去工程では、消去部が、一時記憶工程にて所定のデータ量制限に至った場合、マージ工程におけるマージが行われた後に、一時記憶部に記憶されたデータを消去する。
【００２１】
本発明のその他の観点に係るプログラムは、コンピュータを、上記整列装置の各部として機能させるように構成する。
【００２２】
上記のプログラムは、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＦＤ（Flexible Disk）などの各種の記録媒体に記録することができるほか、インターネットなどのコンピュータ通信網を介して配布することができる。
【発明の効果】
【００２３】
本発明によれば、順序付けが可能なデータを昇順に整列させるのに好適な整列装置、その制御方法、ならびに、これらをコンピュータにて実現するためのプログラムを提供することができるようになる。
【発明を実施するための最良の形態】
【００２４】
以下、添付図面を参照して、本発明の実施の形態について説明する。
【実施例１】
【００２５】
図１は、本発明の整列装置として機能しうる典型的な情報処理装置の概要構成を示す模式図である。以下、図１を参照して説明する。
【００２６】
情報処理装置１０１は、ＣＰＵ（Central Processing Unit；中央処理ユニット）１０２によって制御される。情報処理装置１０１に電源を投入すると、ＣＰＵ １０２は、ＲＯＭ １０３に記憶されたＩＰＬ（Initial Program Loader；初期プログラムローダ）を実行する。
【００２７】
ＩＰＬは、ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭなどの記録媒体に記憶されたＯＳ（Operating System；オペレーティング・システム）プログラムを読み出して実行するプログラムである。
【００２８】
ＯＳを起動した後、ＣＰＵ １０２は、キーボード１０５やマウス１０６などにより入力されたユーザの指示にしたがって、あるいは、ハードディスクなどにあらかじめ記述された設定ファイルの内容にしたがって、ハードディスクなどに記憶されたアプリケーションプログラムを実行する。
【００２９】
当該アプリケーションプログラムを実行することにより、情報処理装置１０１は、設計支援装置として機能することとなる。
【００３０】
ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭなどの記憶媒体に、各種の情報が記録されることになる。
【００３１】
ＣＰＵ １０２は、このプログラムの実行の際に、ＲＡＭ １０７を一時的な作業用記憶領域として用いる。このほか、一時的な作業用記憶領域として、ＣＰＵ １０２内に設けられたレジスタやキャッシュ（図示せず）が使われる。
【００３２】
プログラムの実行に伴ない、各種の情報をユーザに報告したり、途中経過を見せるため、ＣＰＵ １０２は、液晶ディスプレイやＣＲＴ（Cathode Ray Tube）などの表示装置１０８に当該情報を表示することができる。マウス１０６による指示操作では、マウス１０６を移動することにより、画面に表示されたカーソルが移動し、マウス１０６をクリックすることにより、カーソルが指すメニュー項目を選択することができる。
【００３３】
情報処理装置１０１は、ＮＩＣ（Network Interface Card）やモデムなどのインターフェース１０９を介してインターネットなどのコンピュータ通信網と通信を行うことができる。インターフェース１０９を介して受信した順序木を処理の対象としたり、抽出したパターンをインターフェース１０９を介して送信したり、インターフェース１０９を介して受信したプログラムを実行したり、などができる。
【００３４】
図２は、本発明の実施形態の一つに係る整列装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【００３５】
本実施形態に係る整列装置２０１は、所定の順序付けが可能な複数のデータを昇順に整列するものであり、入力受付部２０２、不揮発記憶部２０５、一時記憶部２０３、マージ部２０４、消去部２０６を備える。
【００３６】
ここで、入力受付部２０２は、整列されるべきデータの入力を受け付ける。データの入力は、ハードディスク等に記録されたデータを読み出すこととしても良いし、コンピュータ通信網を介してデータを取得することとしても良い。また、他の処理によって得られたデータがＲＡＭに記憶されている場合に、当該ＲＡＭ内のデータを利用することとしても良い。
【００３７】
したがって、ＣＰＵ １０２は、ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭ、インターフェース１０９を介して通信可能に接続された他のコンピュータ、あるいは、ＲＡＭ １０７と共働して、入力受付部として機能する。
【００３８】
図３、図４は、本実施形態の整列装置で処理するデータの例を示す説明図である。以下、本図を参照して説明する。本図に示すデータは、ある文書（ドキュメント）に出現する用語（ターム）の対応付けを記録するものである。各文書はドキュメントＩＤで識別され、各用語はタームＩＤで識別される。
【００３９】
図３には、ドキュメントＩＤがｄ１〜ｄ４の文書に、タームＩＤがｔ１〜ｔ１０のタームがそれぞれ出現する様子を表すデータが示されている。
【００４０】
図３では、ドキュメントＩＤが記憶される配列３０１は、ドキュメントの数と同じ４個のスロットを配列の要素３０２として持っており、各スロットの配列の要素３０２には、ドキュメントＩＤと、タームＩＤの配列３０３へのポインタが含まれている。
【００４１】
タームＩＤの配列３０３には、当該配列３０３を指すポインタを有するスロットの配列の要素３０２に記録されたドキュメントＩＤの文書に出現する用語のタームＩＤが記録されている。また、配列３０２、３０３には、それぞれ、当該配列に含まれる要素の要素の個数を記憶する領域３０５、３０６が用意されている。
【００４２】
図３に示す例は、以下のような情報を表すデータである。
（１）ドキュメントＩＤがｄ１の文書では、タームＩＤがｔ１〜ｔ４の用語が出現している。
（２）ドキュメントＩＤがｄ２の文書では、タームＩＤがｔ２、ｔ５〜ｔ７、ｔ３の用語が出現している。
（３）ドキュメントＩＤがｄ３の文書では、タームＩＤがｔ８〜ｔ１０の用語が出現している。
（４）ドキュメントＩＤがｄ４の文書では、タームＩＤがｔ８、ｔ９、ｔ３、ｔ４の用語が出現している。
【００４３】
一方、図４は、ドキュメントＩＤとタームＩＤの関係を逆にしたデータを示している。図４では、タームＩＤが記憶される配列３１１は、タームの数と同じ１０個のスロット３１２を持っており、各スロット３１２には、タームＩＤと、ドキュメントＩＤの配列３１３へのポインタが含まれている。
【００４４】
ドキュメントＩＤの配列３１３には、当該配列３１３を指すポインタを有するスロット３１２に記録されたタームＩＤの用語が出現する文書のドキュメントＩＤが記録されている。また、配列３１２、３１３に、それぞれ、当該配列に含まれる要素数を示す領域３１５、３１６があるのは、上記のものと同様である。
【００４５】
すなわち、図４に示す例は、以下のような情報を表すデータである。
（１）タームＩＤがｔ１の用語が出現する文書のドキュメントＩＤは、ｄ１である。
（２）タームＩＤがｔ２の用語が出現する文書のドキュメントＩＤは、ｄ１、ｄ２である。
（３）タームＩＤがｔ３の用語が出現する文書のドキュメントＩＤは、ｄ１、ｄ２、ｄ４である。
（４）タームＩＤがｔ４の用語が出現する文書のドキュメントＩＤは、ｄ１、ｄ４である。
（５）タームＩＤがｔ５の用語が出現する文書のドキュメントＩＤは、ｄ２である。
（６）タームＩＤがｔ６の用語が出現する文書のドキュメントＩＤは、ｄ２である。
（７）タームＩＤがｔ７の用語が出現する文書のドキュメントＩＤは、ｄ２である。
（８）タームＩＤがｔ８の用語が出現する文書のドキュメントＩＤは、ｄ３、ｄ４である。
（９）タームＩＤがｔ９の用語が出現する文書のドキュメントＩＤは、ｄ３、ｄ４である。
（１０）タームＩＤがｔ１０の用語が出現する文書のドキュメントＩＤは、ｄ３である。
【００４６】
さて、図４に示すデータ構造は、図３に示すデータ構造の「転置ファイル」と呼ばれる。
【００４７】
図３に示すデータ構造は、ドキュメントＩＤを鍵に当該ドキュメントＩＤに対応付けられるタームＩＤの群がソート（整列）されているのに対して、図４に示すデータ構造は、タームＩＤを鍵に当該タームＩＤに対応付けられるドキュメントＩＤの群がソートされているからである。
【００４８】
図５、図６は、図３、図４に示すものと等価なデータ構造を示す説明図である。すなわち、図３、図４に示されるデータ構造と図５、図６に示されるデータ構造とは、相互に変換が可能である。
【００４９】
図５では、配列内に１６個の要素が格納されており、各要素は、ドキュメントＩＤとタームＩＤがコロン「：」で結ばれた対からなっている。この対は、当該ドキュメントＩＤの文書に当該タームＩＤの用語が出現することを意味している。
【００５０】
図５は、配列内で各対がドキュメントＩＤを鍵にソートされた様子を示すものであり、図３に示される構造と等価である。
【００５１】
図６は、配列内で各対がタームＩＤを鍵にソートされた様子を示すものであり、図４に示される構造と等価である。
【００５２】
このように、転置ファイルを作成する、という作業は、対の一方の鍵でソートされている（実は、必ずしもソートされている必要はない。）データを、他方の鍵でソートし直すことに相当する。
【００５３】
ここでは、文書をドキュメントＩＤの順に走査して、用語が出現するごとに当該用語のタームＩＤを取得することで、図３や図５に相当するようなデータを入力受付部２０２が受け付ける場合を考える。特に、入力受付部２０２は、図５に示される配列４０１の要素３０２の対が個々に順に、いわゆるストリームデータとして入力される場合を考える。
【００５４】
一般に、ソートは、各レコードに含まれる要素を用いてどのような大小関係をつけるか、によって結果が定まる。上記のような文書に出現する用語の出現の様子を表す転置ファイルを作成する場合には、容易に得られる一方の要素の大小関係ではなく、他方の要素の大小関係でデータをソートすることに相当するのである。
【００５５】
以下では、理解を容易にするため、上記のような転置ファイルを作る作業に整列装置２０１を適用する場合を例にあげて説明するが、一般的な各種のソートに適用できることは明らかであり、そのような実施態様も本発明の範囲に含まれる。
【００５６】
また、本実施形態では、理解を容易にするため個々のデータを記憶するためのデータ構造として配列を採用するが、図３に示すような配列とリスト構造を併用したものを採用しても良いし、その他、配列と相互に変換可能な種々のデータ構造を採用しても良く、そのような場合も本発明の範囲に含まれる。
【００５７】
さて、不揮発記憶部２０５は、当該所定の順序付けにより既に昇順に整列されたデータを、不揮発に記憶する。
【００５８】
すなわち、不揮発記憶部２０５が記憶するのは、
（ａ）作業途中の転置ファイル。対のデータが途中までソートされたもの。
（ｂ）作業結果の転置ファイル。図６に相当するもの。
のいずれかである。したがって、初めて作業を開始する場合には、不揮発記憶部２０５に記憶されるデータは、空であり、入力受付部２０２がデータを受け付けると、適宜データが追加されて記憶されるが、記憶されている状態は、所定の順序で（本実施形態では、タームＩＤの順序で）ソートされたものである、ということになる。
【００５９】
したがって、不揮発記憶部２０５としては、ハードディスク等にデータを記録することとしても良いし、コンピュータ通信網を介して他の機器にデータを記録することとしても良い。すなわち、ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、インターフェース１０９を介して通信可能に接続された他のコンピュータ等は、不揮発記憶部２０５として機能する。
【００６０】
一方、一時記憶部２０３は、入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶する。
【００６１】
すなわち、一時記憶部２０３が記憶するのは、入力されたデータの一部、特に、最近入力された所定量（個数、バイト数等）を上限とするデータである。一時記憶部２０３は、入力されたデータを一時的にバッファリングするために機能する。
【００６２】
したがって、初めて作業を開始する場合には、一時記憶部２０３に記憶されるデータは、空であり、入力受付部２０２がデータを受け付けると、適宜データが追加されて記憶されるが、後述するように、適当なタイミングで一時記憶部２０３は消去される。典型的には、ＲＡＭ １０７が、一時記憶部２０３として機能する。
【００６３】
なお、本実施形態は、不揮発記憶部２０５と一時記憶部２０３とをうまく利用して、ソートを高速に行うためのものであり、そのためには、一時記憶部２０３に対するアクセス速度が、不揮発記憶部２０５に対するアクセス速度よりも高速であれば十分である。アクセス速度が高速な記憶媒体は、容量制限が厳しくなることが一般的である。
【００６４】
本実施形態も、アクセス速度が低速であるが記憶容量の大きいハードディスク１０４は不揮発記憶部２０５として、アクセス速度が高速であるが記憶容量の小さいＲＡＭ １０７は一時記憶部２０３として、それぞれ用いるのが好適である。
【００６５】
図７は、本実施形態の整列装置２０１で実行される整列処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００６６】
処理が開始されると、まず、ＣＰＵ １０２は、一時記憶部２０３をクリアする（ステップＳ５０１）。上記のように、一時記憶部２０３は配列として実装されており、記録できる要素の個数には上限がある。ここでは、仮に、その個数を５個とする。すなわち、記憶された対の数が５個に至ると、データ量制限に至ったこととなる。
【００６７】
なお、現在記憶されている要素の個数は、別途ＲＡＭ １０７内などに記憶するようにしておく。すると、当該個数を０にクリアすれば、ステップＳ５０１の処理が実行されることになる。
【００６８】
次に、ＣＰＵ １０２は、不揮発記憶部２０５をクリアする（ステップＳ５０２）。なお、上述したように、既存のソート済みデータに新たに要素を追加する場合は、ステップＳ５０２の処理は不要である。
【００６９】
図８から図３３は、不揮発記憶部２０５と一時記憶部２０３に用意されている配列の様子を示す説明図である。これらの図においては、ドキュメントＩＤとタームＩＤをコロン「：」で区切って各データを表記するものとする。
【００７０】
図８は、初めて実行されるステップＳ５０３の直前の様子を示すものであり、不揮発記憶部２０５、一時記憶部２０３とも、配列内にはデータが記憶されておらず、空となっている。
【００７１】
ついで、入力受付部２０２は、受け付けるデータがあるか否かを調べる（ステップＳ５０３）。データがある場合（ステップＳ５０３；Ｙｅｓ）、当該データを取得して（ステップＳ５０４）、一時記憶部２０３に追加して記憶する（ステップＳ５０５）。
【００７２】
上記のように、一時記憶部２０３は配列として構成されているため、現在記憶されている要素数を保持しておけば、追加は容易に行うことができる。
【００７３】
次に、現在一時記憶部２０３に記憶されているデータが所定のデータ量制限に至ったか否か、すなわち、本実施形態の場合には、一時記憶部２０３に記憶されたデータの個数が配列に記憶しうる個数に至ったか否かを調べ（ステップＳ５０６）、至っていなければ（ステップＳ５０６；Ｎｏ）、ステップＳ５０３に戻る。
【００７４】
上記のように、配列に記憶できる要素の上限は５個であるから、多くの場合（入力されるデータがそろそろ終了する頃以外の状況）は、５個になるまで順次データが追加されていくことになる（図９、図１０、図１１、図１２、図１３）。
【００７５】
一方、配列に記憶しうる個数に至った場合（ステップＳ５０６；Ｙｅｓ）、ステップＳ５０７に進む。図１３は、初めて実行されたステップＳ５０７に進む直前の不揮発記憶部２０５、一時記憶部２０３の様子が示されていることとなる。前者は空となっているが、後者には５個のデータが入力された順に記憶されている。
【００７６】
さてここで、マージ部２０４は、一時記憶部２０３に記憶されたデータを、所定の順序でソートする（ステップＳ５０７）。本実施形態の場合、所定の順序とは、データの対のうち、タームＩＤの順序、の意味である。したがって、図１４には、ステップＳ５０７の後の不揮発記憶部２０５、一時記憶部２０３の様子が示されており、前者は空となっているが、後者には５個のデータがタームＩＤの順に記憶されることとなる。
【００７７】
上記のように、一時記憶部２０３は、ＲＡＭ １０７などの比較的アクセスが高速な媒体を用いて実現されるため、ステップＳ５０７におけるソートも高速に行うことができる。
【００７８】
ついで、マージ部２０４は、不揮発記憶部２０５と、一時記憶部２０３に記憶されたデータを先頭から順に個別に読み出して、マージした、新たな配列を不揮発記憶部２０５に記憶させる（ステップＳ５０８）。
【００７９】
不揮発記憶部２０５と一時記憶部２０３は、いずれも配列として用意されているが、配列の先頭から要素を順に読み出す場合、これらはデータストリームとして考えることができる。
【００８０】
２つのデータストリームをマージする、とは、マージソートで用いられる手法であり、マージは、２つのソート済みのデータ列から、これらを併せたデータからなる１つのソート済みのデータ列を生成するための広く知られた手法であり、具体的には、以下のような処理を行う。
（１）一方のデータストリームの先頭と、他方のデータストリームの先頭を比較し、小さい方を出力する。
（２）両方の先頭が等しければ、どちらかを選択して出力する。
（３）出力された側のデータストリームを１つ進め、先頭を更新して、上記の処理を繰り返す。
（４）いずれかのデータストリームが終了したら、残りのデータストリームをそのまま出力する。
【００８１】
マージ（ステップＳ５０８）が終了したら、既存の配列を削除して、新たな配列を「不揮発記憶部２０５に記憶されるデータ」とする（ステップＳ５０９）。
【００８２】
典型的には、不揮発記憶部２０５に記憶されるデータは、ハードディスク１０４内でファイル名を用いて管理される。したがって、ソート済みのデータを記憶するファイル名をＸとした場合、マージ（ステップＳ５０８）されたデータを記憶する新たなファイル名としては一時的な名前Ｙを用いてハードディスク１０４に出力する。そして、ステップＳ５０９において、ファイル名Ｘのファイルを削除した後、ファイル名Ｙのファイルをファイル名Ｘにリネーム（rename）すれれば良い。
【００８３】
図１５には、初めて実行されたステップＳ５０９の後の不揮発記憶部２０５、一時記憶部２０３の様子が示されており、後者は空となっているが、前者には５個のデータがタームＩＤの順に記憶されることとなる。
【００８４】
さて、マージが終了したら、消去部２０６は、一時記憶部２０３をクリアして（ステップＳ５１０）、ステップＳ５０３に戻る。
【００８５】
一方、受け付けるデータがなくなった場合（ステップＳ５０３；Ｎｏ）の場合も、ステップＳ５１１に進む。ステップＳ５１１〜ステップＳ５１３で実行する処理は、ステップＳ５０７〜ステップＳ５０９と同じである。
【００８６】
すなわち、一時記憶部２０３に記憶されている（配列に記憶しうる個数未満の個数の）データを当該所定の順序でソートすることになる。
【００８７】
すると、最終的には、不揮発記憶部２０５に、入力を受け付けたデータ（と、もし既存のソート済みデータが不揮発記憶部２０５にあれば、それも含むデータ）をソートしたデータが、配列として記憶されることになる。
【００８８】
図８〜図３３には、このような処理によってどのように不揮発記憶部２０５と一時記憶部２０３にデータが記憶されていく様子を順に示している。
【００８９】
なお、上記の説明では、不揮発記憶部２０５と一時記憶部２０３に記憶されたデータをマージする直前に、一時記憶部２０３に記憶されたデータをソートすることとしており、データを一時記憶部２０３に追加する際には、単に有効な配列の末尾に追加するだけとしているが、データを追加する度に、大小関係を考慮して正しい順に挿入追加することとしても良い。これは、挿入ソートを行っていることに相当する。
【００９０】
上記のように、本実施形態では、一時記憶部２０３としてＲＡＭ １０７を採用し、不揮発記憶部２０５としてハードディスク１０４を採用しているが、マージ処理では、データが先頭から順に出力されるので、書き込みの際にもシークがあまり発生せず、できるだけ連続したセクタにデータが順に書き込まれることになる。したがって、ソート済データに対する以降のマージ処理でも高速なアクセスが期待できるとともに、ソート全体の所要時間の高速化を図ることもできる。
【産業上の利用可能性】
【００９１】
以上説明したように、順序付けが可能なデータを昇順に整列させるのに好適な整列装置、その制御方法、ならびに、これらをコンピュータにて実現するためのプログラムを提供することができるようになる。
【図面の簡単な説明】
【００９２】
【図１】情報処理装置の概要構成を示す模式図である。
【図２】本発明の実施形態に係る整列装置の概要構成を示す模式図である。
【図３】本実施形態の整列装置で処理するデータの例を示す説明図である。
【図４】本実施形態の整列装置で処理するデータの例を示す説明図である。
【図５】本実施形態の整列装置で処理するデータの例を示す説明図である。
【図６】本実施形態の整列装置で処理するデータの例を示す説明図である。
【図７】本発明の実施形態に係る整列装置にて実行される整列処理の制御の流れを示すフローチャートである。
【図８】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図９】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１０】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１１】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１２】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１３】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１４】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１５】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１６】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１７】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１８】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１９】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２０】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２１】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２２】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２３】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２４】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２５】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２６】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２７】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２８】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２９】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図３０】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図３１】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図３２】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図３３】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【符号の説明】
【００９３】
１０１ 情報処理装置
１０２ ＣＰＵ
１０３ ＲＯＭ
１０４ ＨＤ
１０５ キーボード
１０６ マウス
１０７ ＲＡＭ
１０８ 表示装置
１０９ インターフェース
１１０ ＦＤドライブ
１１１ ＣＤ−ＲＯＭドライブ
２０１ 整列装置
２０２ 入力受付部
２０３ 一時記憶部
２０４ マージ部
２０５ 不揮発記憶部
２０６ 消去部
３０１ 配列
３０２ 配列の要素
３０３ 配列
３０５ 配列の要素の個数
３０６ 配列の要素の個数
３１１ 配列
３１２ 配列の要素
３１３ 配列
３１５ 配列の要素の個数
３１６ 配列の要素の個数
【技術分野】
【０００１】
本発明は、順序付けが可能なデータを昇順に整列させるのに好適な整列装置、その制御方法、ならびに、これらをコンピュータにて実現するためのプログラムに関する。
【背景技術】
【０００２】
従来から、順序付けが可能なデータを昇順に整列させるためのソート技術については、これを高速に行うアルゴリズムが提案されている。たとえば、以下の文献に、このようなソート技術を利用したデータ検索の技術が開示されている。
【特許文献１】特開２００１−０３４６２９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
このようなソート技術は、たとえば大規模な転置ファイルを作る上で重要な技術となる。したがって、ソートを高速に行うための、様々な手法が強く求められている。
【０００４】
本発明は、上記の課題を解決するもので、順序付けが可能なデータを昇順に整列させるのに好適な整列装置、その制御方法、ならびに、これらをコンピュータにて実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００６】
本発明の第１の観点に係る整列装置は、所定の順序付けが可能な複数のデータを昇順に整列し、入力受付部、不揮発記憶部、一時記憶部、マージ部、消去部を備え、以下のように構成する。
【０００７】
ここで、入力受付部は、整列されるべきデータの入力を受け付ける。
【０００８】
一方、不揮発記憶部は、当該所定の順序付けにより既に昇順に整列されたデータを、不揮発に記憶する。
【０００９】
さらに、一時記憶部は、入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶する。
【００１０】
そして、マージ部は、一時記憶部が所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させる。
【００１１】
一方、消去部は、一時記憶部が所定のデータ量制限に至った場合、マージ部によるマージが行われた後に、一時記憶部に記憶されたデータを消去する。
【００１２】
また、本発明の整列装置において、一時記憶部に入力されたデータが記憶される毎に、一時記憶部に記憶されるデータは、当該所定の順序付けにより昇順に整列されるように構成することができる。
【００１３】
また、本発明の整列装置において、一時記憶部に記憶されるデータは、所定のデータ量制限に至った、もしくは、当該データの入力が終了した後、マージ部により取得される前に、当該所定の順序付けにより昇順に整列されるように構成することができる。
【００１４】
また、本発明の整列装置において、マージ部は、一時記憶部に記憶されるデータと、不揮発部に記憶されるデータと、をマージソートするように構成することができる。
【００１５】
また、本発明の整列装置において、一時記憶部は、ランダムアクセスメモリであり、不揮発記憶部は、ハードディスクであり、不揮発記憶部は、できるだけ連続したセクタに、当該所定の順序付けにより昇順に整列されたデータを記憶するように構成することができる。
【００１６】
本発明のその他の観点に係る制御方法は、所定の順序付けが可能な複数のデータを昇順に整列し、入力受付部、当該所定の順序付けにより既に昇順に整列されたデータが不揮発に記憶される不揮発記憶部、一時記憶部、マージ部、消去部を有する整列装置を制御し、入力受付工程、一時記憶工程、マージ工程、消去工程を備え、以下のように構成する。
【００１７】
すなわち、入力受付工程では、入力受付部が、整列されるべきデータの入力を受け付ける。
【００１８】
一方、一時記憶工程では、一時記憶部に、入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶させる。
【００１９】
さらに、マージ工程では、マージ部が、一時記憶工程にて所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させる。
【００２０】
そして、消去工程では、消去部が、一時記憶工程にて所定のデータ量制限に至った場合、マージ工程におけるマージが行われた後に、一時記憶部に記憶されたデータを消去する。
【００２１】
本発明のその他の観点に係るプログラムは、コンピュータを、上記整列装置の各部として機能させるように構成する。
【００２２】
上記のプログラムは、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＦＤ（Flexible Disk）などの各種の記録媒体に記録することができるほか、インターネットなどのコンピュータ通信網を介して配布することができる。
【発明の効果】
【００２３】
本発明によれば、順序付けが可能なデータを昇順に整列させるのに好適な整列装置、その制御方法、ならびに、これらをコンピュータにて実現するためのプログラムを提供することができるようになる。
【発明を実施するための最良の形態】
【００２４】
以下、添付図面を参照して、本発明の実施の形態について説明する。
【実施例１】
【００２５】
図１は、本発明の整列装置として機能しうる典型的な情報処理装置の概要構成を示す模式図である。以下、図１を参照して説明する。
【００２６】
情報処理装置１０１は、ＣＰＵ（Central Processing Unit；中央処理ユニット）１０２によって制御される。情報処理装置１０１に電源を投入すると、ＣＰＵ １０２は、ＲＯＭ １０３に記憶されたＩＰＬ（Initial Program Loader；初期プログラムローダ）を実行する。
【００２７】
ＩＰＬは、ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭなどの記録媒体に記憶されたＯＳ（Operating System；オペレーティング・システム）プログラムを読み出して実行するプログラムである。
【００２８】
ＯＳを起動した後、ＣＰＵ １０２は、キーボード１０５やマウス１０６などにより入力されたユーザの指示にしたがって、あるいは、ハードディスクなどにあらかじめ記述された設定ファイルの内容にしたがって、ハードディスクなどに記憶されたアプリケーションプログラムを実行する。
【００２９】
当該アプリケーションプログラムを実行することにより、情報処理装置１０１は、設計支援装置として機能することとなる。
【００３０】
ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭなどの記憶媒体に、各種の情報が記録されることになる。
【００３１】
ＣＰＵ １０２は、このプログラムの実行の際に、ＲＡＭ １０７を一時的な作業用記憶領域として用いる。このほか、一時的な作業用記憶領域として、ＣＰＵ １０２内に設けられたレジスタやキャッシュ（図示せず）が使われる。
【００３２】
プログラムの実行に伴ない、各種の情報をユーザに報告したり、途中経過を見せるため、ＣＰＵ １０２は、液晶ディスプレイやＣＲＴ（Cathode Ray Tube）などの表示装置１０８に当該情報を表示することができる。マウス１０６による指示操作では、マウス１０６を移動することにより、画面に表示されたカーソルが移動し、マウス１０６をクリックすることにより、カーソルが指すメニュー項目を選択することができる。
【００３３】
情報処理装置１０１は、ＮＩＣ（Network Interface Card）やモデムなどのインターフェース１０９を介してインターネットなどのコンピュータ通信網と通信を行うことができる。インターフェース１０９を介して受信した順序木を処理の対象としたり、抽出したパターンをインターフェース１０９を介して送信したり、インターフェース１０９を介して受信したプログラムを実行したり、などができる。
【００３４】
図２は、本発明の実施形態の一つに係る整列装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【００３５】
本実施形態に係る整列装置２０１は、所定の順序付けが可能な複数のデータを昇順に整列するものであり、入力受付部２０２、不揮発記憶部２０５、一時記憶部２０３、マージ部２０４、消去部２０６を備える。
【００３６】
ここで、入力受付部２０２は、整列されるべきデータの入力を受け付ける。データの入力は、ハードディスク等に記録されたデータを読み出すこととしても良いし、コンピュータ通信網を介してデータを取得することとしても良い。また、他の処理によって得られたデータがＲＡＭに記憶されている場合に、当該ＲＡＭ内のデータを利用することとしても良い。
【００３７】
したがって、ＣＰＵ １０２は、ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭ、インターフェース１０９を介して通信可能に接続された他のコンピュータ、あるいは、ＲＡＭ １０７と共働して、入力受付部として機能する。
【００３８】
図３、図４は、本実施形態の整列装置で処理するデータの例を示す説明図である。以下、本図を参照して説明する。本図に示すデータは、ある文書（ドキュメント）に出現する用語（ターム）の対応付けを記録するものである。各文書はドキュメントＩＤで識別され、各用語はタームＩＤで識別される。
【００３９】
図３には、ドキュメントＩＤがｄ１〜ｄ４の文書に、タームＩＤがｔ１〜ｔ１０のタームがそれぞれ出現する様子を表すデータが示されている。
【００４０】
図３では、ドキュメントＩＤが記憶される配列３０１は、ドキュメントの数と同じ４個のスロットを配列の要素３０２として持っており、各スロットの配列の要素３０２には、ドキュメントＩＤと、タームＩＤの配列３０３へのポインタが含まれている。
【００４１】
タームＩＤの配列３０３には、当該配列３０３を指すポインタを有するスロットの配列の要素３０２に記録されたドキュメントＩＤの文書に出現する用語のタームＩＤが記録されている。また、配列３０２、３０３には、それぞれ、当該配列に含まれる要素の要素の個数を記憶する領域３０５、３０６が用意されている。
【００４２】
図３に示す例は、以下のような情報を表すデータである。
（１）ドキュメントＩＤがｄ１の文書では、タームＩＤがｔ１〜ｔ４の用語が出現している。
（２）ドキュメントＩＤがｄ２の文書では、タームＩＤがｔ２、ｔ５〜ｔ７、ｔ３の用語が出現している。
（３）ドキュメントＩＤがｄ３の文書では、タームＩＤがｔ８〜ｔ１０の用語が出現している。
（４）ドキュメントＩＤがｄ４の文書では、タームＩＤがｔ８、ｔ９、ｔ３、ｔ４の用語が出現している。
【００４３】
一方、図４は、ドキュメントＩＤとタームＩＤの関係を逆にしたデータを示している。図４では、タームＩＤが記憶される配列３１１は、タームの数と同じ１０個のスロット３１２を持っており、各スロット３１２には、タームＩＤと、ドキュメントＩＤの配列３１３へのポインタが含まれている。
【００４４】
ドキュメントＩＤの配列３１３には、当該配列３１３を指すポインタを有するスロット３１２に記録されたタームＩＤの用語が出現する文書のドキュメントＩＤが記録されている。また、配列３１２、３１３に、それぞれ、当該配列に含まれる要素数を示す領域３１５、３１６があるのは、上記のものと同様である。
【００４５】
すなわち、図４に示す例は、以下のような情報を表すデータである。
（１）タームＩＤがｔ１の用語が出現する文書のドキュメントＩＤは、ｄ１である。
（２）タームＩＤがｔ２の用語が出現する文書のドキュメントＩＤは、ｄ１、ｄ２である。
（３）タームＩＤがｔ３の用語が出現する文書のドキュメントＩＤは、ｄ１、ｄ２、ｄ４である。
（４）タームＩＤがｔ４の用語が出現する文書のドキュメントＩＤは、ｄ１、ｄ４である。
（５）タームＩＤがｔ５の用語が出現する文書のドキュメントＩＤは、ｄ２である。
（６）タームＩＤがｔ６の用語が出現する文書のドキュメントＩＤは、ｄ２である。
（７）タームＩＤがｔ７の用語が出現する文書のドキュメントＩＤは、ｄ２である。
（８）タームＩＤがｔ８の用語が出現する文書のドキュメントＩＤは、ｄ３、ｄ４である。
（９）タームＩＤがｔ９の用語が出現する文書のドキュメントＩＤは、ｄ３、ｄ４である。
（１０）タームＩＤがｔ１０の用語が出現する文書のドキュメントＩＤは、ｄ３である。
【００４６】
さて、図４に示すデータ構造は、図３に示すデータ構造の「転置ファイル」と呼ばれる。
【００４７】
図３に示すデータ構造は、ドキュメントＩＤを鍵に当該ドキュメントＩＤに対応付けられるタームＩＤの群がソート（整列）されているのに対して、図４に示すデータ構造は、タームＩＤを鍵に当該タームＩＤに対応付けられるドキュメントＩＤの群がソートされているからである。
【００４８】
図５、図６は、図３、図４に示すものと等価なデータ構造を示す説明図である。すなわち、図３、図４に示されるデータ構造と図５、図６に示されるデータ構造とは、相互に変換が可能である。
【００４９】
図５では、配列内に１６個の要素が格納されており、各要素は、ドキュメントＩＤとタームＩＤがコロン「：」で結ばれた対からなっている。この対は、当該ドキュメントＩＤの文書に当該タームＩＤの用語が出現することを意味している。
【００５０】
図５は、配列内で各対がドキュメントＩＤを鍵にソートされた様子を示すものであり、図３に示される構造と等価である。
【００５１】
図６は、配列内で各対がタームＩＤを鍵にソートされた様子を示すものであり、図４に示される構造と等価である。
【００５２】
このように、転置ファイルを作成する、という作業は、対の一方の鍵でソートされている（実は、必ずしもソートされている必要はない。）データを、他方の鍵でソートし直すことに相当する。
【００５３】
ここでは、文書をドキュメントＩＤの順に走査して、用語が出現するごとに当該用語のタームＩＤを取得することで、図３や図５に相当するようなデータを入力受付部２０２が受け付ける場合を考える。特に、入力受付部２０２は、図５に示される配列４０１の要素３０２の対が個々に順に、いわゆるストリームデータとして入力される場合を考える。
【００５４】
一般に、ソートは、各レコードに含まれる要素を用いてどのような大小関係をつけるか、によって結果が定まる。上記のような文書に出現する用語の出現の様子を表す転置ファイルを作成する場合には、容易に得られる一方の要素の大小関係ではなく、他方の要素の大小関係でデータをソートすることに相当するのである。
【００５５】
以下では、理解を容易にするため、上記のような転置ファイルを作る作業に整列装置２０１を適用する場合を例にあげて説明するが、一般的な各種のソートに適用できることは明らかであり、そのような実施態様も本発明の範囲に含まれる。
【００５６】
また、本実施形態では、理解を容易にするため個々のデータを記憶するためのデータ構造として配列を採用するが、図３に示すような配列とリスト構造を併用したものを採用しても良いし、その他、配列と相互に変換可能な種々のデータ構造を採用しても良く、そのような場合も本発明の範囲に含まれる。
【００５７】
さて、不揮発記憶部２０５は、当該所定の順序付けにより既に昇順に整列されたデータを、不揮発に記憶する。
【００５８】
すなわち、不揮発記憶部２０５が記憶するのは、
（ａ）作業途中の転置ファイル。対のデータが途中までソートされたもの。
（ｂ）作業結果の転置ファイル。図６に相当するもの。
のいずれかである。したがって、初めて作業を開始する場合には、不揮発記憶部２０５に記憶されるデータは、空であり、入力受付部２０２がデータを受け付けると、適宜データが追加されて記憶されるが、記憶されている状態は、所定の順序で（本実施形態では、タームＩＤの順序で）ソートされたものである、ということになる。
【００５９】
したがって、不揮発記憶部２０５としては、ハードディスク等にデータを記録することとしても良いし、コンピュータ通信網を介して他の機器にデータを記録することとしても良い。すなわち、ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、インターフェース１０９を介して通信可能に接続された他のコンピュータ等は、不揮発記憶部２０５として機能する。
【００６０】
一方、一時記憶部２０３は、入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶する。
【００６１】
すなわち、一時記憶部２０３が記憶するのは、入力されたデータの一部、特に、最近入力された所定量（個数、バイト数等）を上限とするデータである。一時記憶部２０３は、入力されたデータを一時的にバッファリングするために機能する。
【００６２】
したがって、初めて作業を開始する場合には、一時記憶部２０３に記憶されるデータは、空であり、入力受付部２０２がデータを受け付けると、適宜データが追加されて記憶されるが、後述するように、適当なタイミングで一時記憶部２０３は消去される。典型的には、ＲＡＭ １０７が、一時記憶部２０３として機能する。
【００６３】
なお、本実施形態は、不揮発記憶部２０５と一時記憶部２０３とをうまく利用して、ソートを高速に行うためのものであり、そのためには、一時記憶部２０３に対するアクセス速度が、不揮発記憶部２０５に対するアクセス速度よりも高速であれば十分である。アクセス速度が高速な記憶媒体は、容量制限が厳しくなることが一般的である。
【００６４】
本実施形態も、アクセス速度が低速であるが記憶容量の大きいハードディスク１０４は不揮発記憶部２０５として、アクセス速度が高速であるが記憶容量の小さいＲＡＭ １０７は一時記憶部２０３として、それぞれ用いるのが好適である。
【００６５】
図７は、本実施形態の整列装置２０１で実行される整列処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００６６】
処理が開始されると、まず、ＣＰＵ １０２は、一時記憶部２０３をクリアする（ステップＳ５０１）。上記のように、一時記憶部２０３は配列として実装されており、記録できる要素の個数には上限がある。ここでは、仮に、その個数を５個とする。すなわち、記憶された対の数が５個に至ると、データ量制限に至ったこととなる。
【００６７】
なお、現在記憶されている要素の個数は、別途ＲＡＭ １０７内などに記憶するようにしておく。すると、当該個数を０にクリアすれば、ステップＳ５０１の処理が実行されることになる。
【００６８】
次に、ＣＰＵ １０２は、不揮発記憶部２０５をクリアする（ステップＳ５０２）。なお、上述したように、既存のソート済みデータに新たに要素を追加する場合は、ステップＳ５０２の処理は不要である。
【００６９】
図８から図３３は、不揮発記憶部２０５と一時記憶部２０３に用意されている配列の様子を示す説明図である。これらの図においては、ドキュメントＩＤとタームＩＤをコロン「：」で区切って各データを表記するものとする。
【００７０】
図８は、初めて実行されるステップＳ５０３の直前の様子を示すものであり、不揮発記憶部２０５、一時記憶部２０３とも、配列内にはデータが記憶されておらず、空となっている。
【００７１】
ついで、入力受付部２０２は、受け付けるデータがあるか否かを調べる（ステップＳ５０３）。データがある場合（ステップＳ５０３；Ｙｅｓ）、当該データを取得して（ステップＳ５０４）、一時記憶部２０３に追加して記憶する（ステップＳ５０５）。
【００７２】
上記のように、一時記憶部２０３は配列として構成されているため、現在記憶されている要素数を保持しておけば、追加は容易に行うことができる。
【００７３】
次に、現在一時記憶部２０３に記憶されているデータが所定のデータ量制限に至ったか否か、すなわち、本実施形態の場合には、一時記憶部２０３に記憶されたデータの個数が配列に記憶しうる個数に至ったか否かを調べ（ステップＳ５０６）、至っていなければ（ステップＳ５０６；Ｎｏ）、ステップＳ５０３に戻る。
【００７４】
上記のように、配列に記憶できる要素の上限は５個であるから、多くの場合（入力されるデータがそろそろ終了する頃以外の状況）は、５個になるまで順次データが追加されていくことになる（図９、図１０、図１１、図１２、図１３）。
【００７５】
一方、配列に記憶しうる個数に至った場合（ステップＳ５０６；Ｙｅｓ）、ステップＳ５０７に進む。図１３は、初めて実行されたステップＳ５０７に進む直前の不揮発記憶部２０５、一時記憶部２０３の様子が示されていることとなる。前者は空となっているが、後者には５個のデータが入力された順に記憶されている。
【００７６】
さてここで、マージ部２０４は、一時記憶部２０３に記憶されたデータを、所定の順序でソートする（ステップＳ５０７）。本実施形態の場合、所定の順序とは、データの対のうち、タームＩＤの順序、の意味である。したがって、図１４には、ステップＳ５０７の後の不揮発記憶部２０５、一時記憶部２０３の様子が示されており、前者は空となっているが、後者には５個のデータがタームＩＤの順に記憶されることとなる。
【００７７】
上記のように、一時記憶部２０３は、ＲＡＭ １０７などの比較的アクセスが高速な媒体を用いて実現されるため、ステップＳ５０７におけるソートも高速に行うことができる。
【００７８】
ついで、マージ部２０４は、不揮発記憶部２０５と、一時記憶部２０３に記憶されたデータを先頭から順に個別に読み出して、マージした、新たな配列を不揮発記憶部２０５に記憶させる（ステップＳ５０８）。
【００７９】
不揮発記憶部２０５と一時記憶部２０３は、いずれも配列として用意されているが、配列の先頭から要素を順に読み出す場合、これらはデータストリームとして考えることができる。
【００８０】
２つのデータストリームをマージする、とは、マージソートで用いられる手法であり、マージは、２つのソート済みのデータ列から、これらを併せたデータからなる１つのソート済みのデータ列を生成するための広く知られた手法であり、具体的には、以下のような処理を行う。
（１）一方のデータストリームの先頭と、他方のデータストリームの先頭を比較し、小さい方を出力する。
（２）両方の先頭が等しければ、どちらかを選択して出力する。
（３）出力された側のデータストリームを１つ進め、先頭を更新して、上記の処理を繰り返す。
（４）いずれかのデータストリームが終了したら、残りのデータストリームをそのまま出力する。
【００８１】
マージ（ステップＳ５０８）が終了したら、既存の配列を削除して、新たな配列を「不揮発記憶部２０５に記憶されるデータ」とする（ステップＳ５０９）。
【００８２】
典型的には、不揮発記憶部２０５に記憶されるデータは、ハードディスク１０４内でファイル名を用いて管理される。したがって、ソート済みのデータを記憶するファイル名をＸとした場合、マージ（ステップＳ５０８）されたデータを記憶する新たなファイル名としては一時的な名前Ｙを用いてハードディスク１０４に出力する。そして、ステップＳ５０９において、ファイル名Ｘのファイルを削除した後、ファイル名Ｙのファイルをファイル名Ｘにリネーム（rename）すれれば良い。
【００８３】
図１５には、初めて実行されたステップＳ５０９の後の不揮発記憶部２０５、一時記憶部２０３の様子が示されており、後者は空となっているが、前者には５個のデータがタームＩＤの順に記憶されることとなる。
【００８４】
さて、マージが終了したら、消去部２０６は、一時記憶部２０３をクリアして（ステップＳ５１０）、ステップＳ５０３に戻る。
【００８５】
一方、受け付けるデータがなくなった場合（ステップＳ５０３；Ｎｏ）の場合も、ステップＳ５１１に進む。ステップＳ５１１〜ステップＳ５１３で実行する処理は、ステップＳ５０７〜ステップＳ５０９と同じである。
【００８６】
すなわち、一時記憶部２０３に記憶されている（配列に記憶しうる個数未満の個数の）データを当該所定の順序でソートすることになる。
【００８７】
すると、最終的には、不揮発記憶部２０５に、入力を受け付けたデータ（と、もし既存のソート済みデータが不揮発記憶部２０５にあれば、それも含むデータ）をソートしたデータが、配列として記憶されることになる。
【００８８】
図８〜図３３には、このような処理によってどのように不揮発記憶部２０５と一時記憶部２０３にデータが記憶されていく様子を順に示している。
【００８９】
なお、上記の説明では、不揮発記憶部２０５と一時記憶部２０３に記憶されたデータをマージする直前に、一時記憶部２０３に記憶されたデータをソートすることとしており、データを一時記憶部２０３に追加する際には、単に有効な配列の末尾に追加するだけとしているが、データを追加する度に、大小関係を考慮して正しい順に挿入追加することとしても良い。これは、挿入ソートを行っていることに相当する。
【００９０】
上記のように、本実施形態では、一時記憶部２０３としてＲＡＭ １０７を採用し、不揮発記憶部２０５としてハードディスク１０４を採用しているが、マージ処理では、データが先頭から順に出力されるので、書き込みの際にもシークがあまり発生せず、できるだけ連続したセクタにデータが順に書き込まれることになる。したがって、ソート済データに対する以降のマージ処理でも高速なアクセスが期待できるとともに、ソート全体の所要時間の高速化を図ることもできる。
【産業上の利用可能性】
【００９１】
以上説明したように、順序付けが可能なデータを昇順に整列させるのに好適な整列装置、その制御方法、ならびに、これらをコンピュータにて実現するためのプログラムを提供することができるようになる。
【図面の簡単な説明】
【００９２】
【図１】情報処理装置の概要構成を示す模式図である。
【図２】本発明の実施形態に係る整列装置の概要構成を示す模式図である。
【図３】本実施形態の整列装置で処理するデータの例を示す説明図である。
【図４】本実施形態の整列装置で処理するデータの例を示す説明図である。
【図５】本実施形態の整列装置で処理するデータの例を示す説明図である。
【図６】本実施形態の整列装置で処理するデータの例を示す説明図である。
【図７】本発明の実施形態に係る整列装置にて実行される整列処理の制御の流れを示すフローチャートである。
【図８】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図９】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１０】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１１】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１２】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１３】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１４】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１５】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１６】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１７】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１８】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図１９】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２０】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２１】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２２】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２３】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２４】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２５】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２６】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２７】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２８】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図２９】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図３０】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図３１】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図３２】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【図３３】一時記憶部と不揮発記憶部に記憶されるデータの様子を示す説明図である。
【符号の説明】
【００９３】
１０１ 情報処理装置
１０２ ＣＰＵ
１０３ ＲＯＭ
１０４ ＨＤ
１０５ キーボード
１０６ マウス
１０７ ＲＡＭ
１０８ 表示装置
１０９ インターフェース
１１０ ＦＤドライブ
１１１ ＣＤ−ＲＯＭドライブ
２０１ 整列装置
２０２ 入力受付部
２０３ 一時記憶部
２０４ マージ部
２０５ 不揮発記憶部
２０６ 消去部
３０１ 配列
３０２ 配列の要素
３０３ 配列
３０５ 配列の要素の個数
３０６ 配列の要素の個数
３１１ 配列
３１２ 配列の要素
３１３ 配列
３１５ 配列の要素の個数
３１６ 配列の要素の個数
【特許請求の範囲】
【請求項１】
所定の順序付けが可能な複数のデータを昇順に整列する整列装置であって、
整列されるべきデータの入力を受け付ける入力受付部、
当該所定の順序付けにより既に昇順に整列されたデータを、不揮発に記憶する不揮発記憶部、
前記入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶する一時記憶部、
前記一時記憶部が所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、前記一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、前記不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、前記不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させるマージ部、
前記一時記憶部が所定のデータ量制限に至った場合、前記マージ部によるマージが行われた後に、前記一時記憶部に記憶されたデータを消去する消去部
を備えることを特徴とする物。
【請求項２】
請求項１に記載の整列装置であって、
前記一時記憶部に前記入力されたデータが記憶される毎に、前記一時記憶部に記憶されるデータは、当該所定の順序付けにより昇順に整列される
ことを特徴とする物。
【請求項３】
請求項１に記載の整列装置であって、
前記一時記憶部に記憶されるデータは、所定のデータ量制限に至った、もしくは、当該データの入力が終了した後、前記マージ部により取得される前に、当該所定の順序付けにより昇順に整列される
ことを特徴とする物。
【請求項４】
請求項１から３のいずれか１項に記載の整列装置であって、
前記マージ部は、前記一時記憶部に記憶されるデータと、前記不揮発部に記憶されるデータと、をマージソートする
ことを特徴とする物。
【請求項５】
請求項１から４のいずれか１項に記載の整列装置であって、
前記一時記憶部は、ランダムアクセスメモリであり、
前記不揮発記憶部は、ハードディスクであり、
前記不揮発記憶部は、できるだけ連続したセクタに、当該所定の順序付けにより昇順に整列されたデータを記憶する
ことを特徴とする物。
【請求項６】
所定の順序付けが可能な複数のデータを昇順に整列し、入力受付部、不揮発記憶部、一時記憶部、マージ部、消去部を有する整列装置を制御する制御方法であって、
前記不揮発記憶部には、当該所定の順序付けにより既に昇順に整列されたデータが、不揮発に記憶され、
前記入力受付部が、整列されるべきデータの入力を受け付ける入力受付工程、
前記一時記憶部に、前記入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶させる一時記憶工程、
前記マージ部が、前記一時記憶工程にて所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、前記一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、前記不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、前記不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させるマージ工程、
前記消去部が、前記一時記憶工程にて所定のデータ量制限に至った場合、前記マージ工程におけるマージが行われた後に、前記一時記憶部に記憶されたデータを消去する消去工程
を備えることを特徴とする方法。
【請求項７】
所定の順序付けが可能な複数のデータを昇順に整列させるため、コンピュータを、
整列されるべきデータの入力を受け付ける入力受付部、
当該所定の順序付けにより既に昇順に整列されたデータを、不揮発に記憶する不揮発記憶部、
前記入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶する一時記憶部、
前記一時記憶部が所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、前記一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、前記不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、前記不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させるマージ部、
前記一時記憶部が所定のデータ量制限に至った場合、前記マージ部によるマージが行われた後に、前記一時記憶部に記憶されたデータを消去する消去部
として機能させることを特徴とするプログラム。
【請求項１】
所定の順序付けが可能な複数のデータを昇順に整列する整列装置であって、
整列されるべきデータの入力を受け付ける入力受付部、
当該所定の順序付けにより既に昇順に整列されたデータを、不揮発に記憶する不揮発記憶部、
前記入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶する一時記憶部、
前記一時記憶部が所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、前記一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、前記不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、前記不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させるマージ部、
前記一時記憶部が所定のデータ量制限に至った場合、前記マージ部によるマージが行われた後に、前記一時記憶部に記憶されたデータを消去する消去部
を備えることを特徴とする物。
【請求項２】
請求項１に記載の整列装置であって、
前記一時記憶部に前記入力されたデータが記憶される毎に、前記一時記憶部に記憶されるデータは、当該所定の順序付けにより昇順に整列される
ことを特徴とする物。
【請求項３】
請求項１に記載の整列装置であって、
前記一時記憶部に記憶されるデータは、所定のデータ量制限に至った、もしくは、当該データの入力が終了した後、前記マージ部により取得される前に、当該所定の順序付けにより昇順に整列される
ことを特徴とする物。
【請求項４】
請求項１から３のいずれか１項に記載の整列装置であって、
前記マージ部は、前記一時記憶部に記憶されるデータと、前記不揮発部に記憶されるデータと、をマージソートする
ことを特徴とする物。
【請求項５】
請求項１から４のいずれか１項に記載の整列装置であって、
前記一時記憶部は、ランダムアクセスメモリであり、
前記不揮発記憶部は、ハードディスクであり、
前記不揮発記憶部は、できるだけ連続したセクタに、当該所定の順序付けにより昇順に整列されたデータを記憶する
ことを特徴とする物。
【請求項６】
所定の順序付けが可能な複数のデータを昇順に整列し、入力受付部、不揮発記憶部、一時記憶部、マージ部、消去部を有する整列装置を制御する制御方法であって、
前記不揮発記憶部には、当該所定の順序付けにより既に昇順に整列されたデータが、不揮発に記憶され、
前記入力受付部が、整列されるべきデータの入力を受け付ける入力受付工程、
前記一時記憶部に、前記入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶させる一時記憶工程、
前記マージ部が、前記一時記憶工程にて所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、前記一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、前記不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、前記不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させるマージ工程、
前記消去部が、前記一時記憶工程にて所定のデータ量制限に至った場合、前記マージ工程におけるマージが行われた後に、前記一時記憶部に記憶されたデータを消去する消去工程
を備えることを特徴とする方法。
【請求項７】
所定の順序付けが可能な複数のデータを昇順に整列させるため、コンピュータを、
整列されるべきデータの入力を受け付ける入力受付部、
当該所定の順序付けにより既に昇順に整列されたデータを、不揮発に記憶する不揮発記憶部、
前記入力を受け付けられたデータを、所定のデータ量制限に至るまで、もしくは、当該データの入力が終了するまで、一時的に記憶する一時記憶部、
前記一時記憶部が所定のデータ量制限に至った場合、もしくは、当該データの入力が終了した場合、前記一時記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、前記不揮発記憶部に記憶されるデータを当該所定の順序付けにより昇順に取得し、これら取得されたデータをマージして、前記不揮発記憶部に当該所定の順序付けにより昇順に整列された新たなデータとして不揮発に記憶させるマージ部、
前記一時記憶部が所定のデータ量制限に至った場合、前記マージ部によるマージが行われた後に、前記一時記憶部に記憶されたデータを消去する消去部
として機能させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【公開番号】特開２００６−２２７８８１（Ｐ２００６−２２７８８１Ａ）
【公開日】平成１８年８月３１日（２００６．８．３１）
【国際特許分類】
【出願番号】特願２００５−４０５３３（Ｐ２００５−４０５３３）
【出願日】平成１７年２月１７日（２００５．２．１７）
【出願人】（３９００２４３５０）株式会社ジャストシステム (123)
【公開日】平成１８年８月３１日（２００６．８．３１）
【国際特許分類】
【出願日】平成１７年２月１７日（２００５．２．１７）
【出願人】（３９００２４３５０）株式会社ジャストシステム (123)
[ Back to top ]