JPH05265708A - コンピュータ動作方法 - Google Patents
コンピュータ動作方法Info
- Publication number
- JPH05265708A JPH05265708A JP4325708A JP32570892A JPH05265708A JP H05265708 A JPH05265708 A JP H05265708A JP 4325708 A JP4325708 A JP 4325708A JP 32570892 A JP32570892 A JP 32570892A JP H05265708 A JPH05265708 A JP H05265708A
- Authority
- JP
- Japan
- Prior art keywords
- keys
- key
- subsets
- subset
- instruction
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
- G06F7/24—Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in general
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【目的】 本発明は、キーの集合を部分集合に分割し、
予め定義されたシーケンスで、該部分集合を分類処理す
る、コンピュータにおける分類処理方法を提供する。 【構成】 キーの集合の部分集合への分割は、キーの集
合の選択された１つのキーに対して、区別可能なコード
ワードを有する１つ以上のキーを各々が含む部分集合に
ならしめ、各々が対応するレコードに関連するキーの集
合を分類するための、コンピュータの動作方法である。
本発明の実施例では、代表キーを求めるために、ランダ
ムにキーの集合を抽出することによって選択キーが選択
される。代表キーが識別できない場合、従来方法のＭＳ
Ｂ基数法分類が用いられる。本方法は、キーの集合を完
全に分類するまで繰り返される。
予め定義されたシーケンスで、該部分集合を分類処理す
る、コンピュータにおける分類処理方法を提供する。 【構成】 キーの集合の部分集合への分割は、キーの集
合の選択された１つのキーに対して、区別可能なコード
ワードを有する１つ以上のキーを各々が含む部分集合に
ならしめ、各々が対応するレコードに関連するキーの集
合を分類するための、コンピュータの動作方法である。
本発明の実施例では、代表キーを求めるために、ランダ
ムにキーの集合を抽出することによって選択キーが選択
される。代表キーが識別できない場合、従来方法のＭＳ
Ｂ基数法分類が用いられる。本方法は、キーの集合を完
全に分類するまで繰り返される。
Description
【０００１】
【産業上の利用分野】本発明は、コンピュータにおける
分類処理方法に関する。
分類処理方法に関する。
【０００２】
【従来の技術及び発明が解決しようとする課題】分類処
理を管理するキーと呼ばれるレコードの１つのフィール
ドの値に従ったレコードから成るファイルの分類処理
は、非常に重要であり、データ処理システムで、よく使
用される機能である。
理を管理するキーと呼ばれるレコードの１つのフィール
ドの値に従ったレコードから成るファイルの分類処理
は、非常に重要であり、データ処理システムで、よく使
用される機能である。
【０００３】一般に分散分類と呼ばれる最上位バイト
（ＭＳＢ）基数法分類は、両方の全てのキーを比較する
ことが、コンピュータ時代において無駄である一方で、
長いキーを分類するのに適した分類方法である。この方
法は、著者D E Knuth によって題名"コンピュータ・プ
ログラミング手法、分類と検索"（"The Art of Compute
rProgramming、Sorting and Searching"、Addison Wesl
ey 1973 ）に記載されている。この方法によれば、キー
は、キーの最上位のバイトに従って最初に分類される。
次に、同じ最上位のバイトのキーは、該キーの次の最上
位のバイトで分類され、各々のキーの配置が分類リスト
に確定されるまて、これが繰返される。これは、各キー
の最上位のバイトに従って、最初に全てのキーを２５６
のパーティション又はバケット ｂ0、ｂ1、．．．、ｂ
255、に分散させることによって行われる。次に、ｆｏ
ｒ ｉ＝０、．．．２５５の代入のこの順序において、
ｂi が唯一１つだけのキーを含むならば、このキーは、
作成される分類リストの末端に加えられ、ｂi が、２つ
以上のキーを含むならば、これらのキーは、該キーの２
番目のバイトで始まる接尾部によって同様に反復的に分
類される。全てのキーが、分類リストに付加されるま
で、この分散を繰返すことによって、分類処理が達成さ
れる。
（ＭＳＢ）基数法分類は、両方の全てのキーを比較する
ことが、コンピュータ時代において無駄である一方で、
長いキーを分類するのに適した分類方法である。この方
法は、著者D E Knuth によって題名"コンピュータ・プ
ログラミング手法、分類と検索"（"The Art of Compute
rProgramming、Sorting and Searching"、Addison Wesl
ey 1973 ）に記載されている。この方法によれば、キー
は、キーの最上位のバイトに従って最初に分類される。
次に、同じ最上位のバイトのキーは、該キーの次の最上
位のバイトで分類され、各々のキーの配置が分類リスト
に確定されるまて、これが繰返される。これは、各キー
の最上位のバイトに従って、最初に全てのキーを２５６
のパーティション又はバケット ｂ0、ｂ1、．．．、ｂ
255、に分散させることによって行われる。次に、ｆｏ
ｒ ｉ＝０、．．．２５５の代入のこの順序において、
ｂi が唯一１つだけのキーを含むならば、このキーは、
作成される分類リストの末端に加えられ、ｂi が、２つ
以上のキーを含むならば、これらのキーは、該キーの２
番目のバイトで始まる接尾部によって同様に反復的に分
類される。全てのキーが、分類リストに付加されるま
で、この分散を繰返すことによって、分類処理が達成さ
れる。
【０００４】この種類の分類は、単一のキーがバケット
に残ると、キー・テール又は接尾部の処理が避けられる
ことから、その効率及び利点が大いに発揮される。しか
しながら、キーがランダムに分散されず且つ、かなりの
数のキーが共通の接頭部を共有しない状況では、この分
類の多くの利点が失われ、プロセッサ資源は、大きい値
のキー及びより小さい値のキーの部分集合にキーを分離
されても、その効果がなく、キーのバケットからバケッ
トへの無駄な移動が行われる。
に残ると、キー・テール又は接尾部の処理が避けられる
ことから、その効率及び利点が大いに発揮される。しか
しながら、キーがランダムに分散されず且つ、かなりの
数のキーが共通の接頭部を共有しない状況では、この分
類の多くの利点が失われ、プロセッサ資源は、大きい値
のキー及びより小さい値のキーの部分集合にキーを分離
されても、その効果がなく、キーのバケットからバケッ
トへの無駄な移動が行われる。
【０００５】
【課題を解決するための手段】本発明は、キーの集合を
部分集合に分割し、予め定義されたシーケンスで、該部
分集合を分類処理する方法を有し、該分割は、キーの集
合の選択された１つのキーに対して、区別可能なコード
ワードを有する１つ以上のキーを各々が有する部分集合
にならしめ、各々が対応するレコードに関連するキーの
集合を分類するための、コンピュータの動作方法を提供
する。
部分集合に分割し、予め定義されたシーケンスで、該部
分集合を分類処理する方法を有し、該分割は、キーの集
合の選択された１つのキーに対して、区別可能なコード
ワードを有する１つ以上のキーを各々が有する部分集合
にならしめ、各々が対応するレコードに関連するキーの
集合を分類するための、コンピュータの動作方法を提供
する。
【０００６】キーのコードワードは、参照キーに対する
キーの順序を維持するための、キーの短縮表示である。
キーのコードワードは、必ずしも常にではないが、一般
に、参照キーとキーの比較に関する２つの情報を含む。
（ｉ）それぞれ異なるキーの最上位の数字のインデック
スと、（ｉｉ）キーの上記数字の値。
キーの順序を維持するための、キーの短縮表示である。
キーのコードワードは、必ずしも常にではないが、一般
に、参照キーとキーの比較に関する２つの情報を含む。
（ｉ）それぞれ異なるキーの最上位の数字のインデック
スと、（ｉｉ）キーの上記数字の値。
【０００７】キーの部分集合が分類される予め定義され
たシーケンスでは、各部分集合の全てのキーは、シーケ
ンスでの後続する部分集合のキーよりも、小さい値を有
することが正しい。
たシーケンスでは、各部分集合の全てのキーは、シーケ
ンスでの後続する部分集合のキーよりも、小さい値を有
することが正しい。
【０００８】コードワードを使用することによって、共
通の接頭部が効果的にスキップされることから、選択キ
ーと共通の接頭部を共有するキーの処理速度が向上す
る。従って、かなりの数のキーが、共通の接頭部を共有
するケースでは、分類の効率が著しく改善される。
通の接頭部が効果的にスキップされることから、選択キ
ーと共通の接頭部を共有するキーの処理速度が向上す
る。従って、かなりの数のキーが、共通の接頭部を共有
するケースでは、分類の効率が著しく改善される。
【０００９】本発明の利点である形式では、コードワー
ドは、参照キー及びインデックスの数字の値とは異なる
キーの最上位の数字のインデックスを有する。このケー
スにおける方法は、インデックスの各可能的な値に、各
々が対応する多数の命令の集合を先行して格納するステ
ップを含み、各集合は、数字の各可能的な値のそれぞれ
に対する命令を有し、上記命令は、数字の連続した可能
的な値に対して、該命令のメモリ・アドレスが連続する
ように各集合に配置され、それぞれのインデックスで参
照キーの値に対応する各集合の命令は、最下位の数字に
対応する集合以外の集合の次の命令のメモリ・アドレス
をスタックにプッシュさせ、且つ、次の最上位の数字の
インデックスに対応する集合の第１の命令に分岐するよ
うに実行させ、他の各集合の命令は、非オペレーション
命令状態であり、追加された命令を有する各命令の集合
は、スタックの最上部のアドレスを検索させて、該アド
レスに分岐するように実行させ、及びここにおいて、キ
ーの集合を部分集合に分割する分割化は、部分集合が、
最初に置かれたキーを有する場合に、命令が部分集合を
分類できるように、それぞれの区別可能なコードワード
に対応する命令を変えることを含み、命令の集合が、最
上位の数字に対応する集合で開始を実行させられる場合
に、部分集合が、予め定義されたシーケンスで分類され
る。
ドは、参照キー及びインデックスの数字の値とは異なる
キーの最上位の数字のインデックスを有する。このケー
スにおける方法は、インデックスの各可能的な値に、各
々が対応する多数の命令の集合を先行して格納するステ
ップを含み、各集合は、数字の各可能的な値のそれぞれ
に対する命令を有し、上記命令は、数字の連続した可能
的な値に対して、該命令のメモリ・アドレスが連続する
ように各集合に配置され、それぞれのインデックスで参
照キーの値に対応する各集合の命令は、最下位の数字に
対応する集合以外の集合の次の命令のメモリ・アドレス
をスタックにプッシュさせ、且つ、次の最上位の数字の
インデックスに対応する集合の第１の命令に分岐するよ
うに実行させ、他の各集合の命令は、非オペレーション
命令状態であり、追加された命令を有する各命令の集合
は、スタックの最上部のアドレスを検索させて、該アド
レスに分岐するように実行させ、及びここにおいて、キ
ーの集合を部分集合に分割する分割化は、部分集合が、
最初に置かれたキーを有する場合に、命令が部分集合を
分類できるように、それぞれの区別可能なコードワード
に対応する命令を変えることを含み、命令の集合が、最
上位の数字に対応する集合で開始を実行させられる場合
に、部分集合が、予め定義されたシーケンスで分類され
る。
【００１０】この実行時間修正コードの使用は、シーケ
ンスの部分集合の処理に特に都合のよい方法をもたら
す。
ンスの部分集合の処理に特に都合のよい方法をもたら
す。
【００１１】選択キーは、集合のかなりの数の他のキー
で、共通の接頭部を共有するキーを選択して求めるため
に、ランダムにキーを抽出することによって選択され
る。
で、共通の接頭部を共有するキーを選択して求めるため
に、ランダムにキーを抽出することによって選択され
る。
【００１２】キーがランダムに分散させられているかど
うかが分からない場合、かなりの数のキーが、共通の接
頭部を共有するのかどうかが決まるまで、キーをランダ
ムに抽出する分類方法が提供され、決定後は、上記方法
を用いてキーを分類する。このケースでのランダム・サ
ンプリングは、キーの集合からキーの部分集合をランダ
ムに選ぶことを含み、共通の接頭部を有するキーの集合
に、かなりの数のキーがある場合に、共通の接頭部を共
有するキーの部分集合に２つのキーが有るかどうかを求
める。共通の接頭部を共有する２つのキーがない場合、
キーの集合は、該キーの最上位のバイトの値に従って従
来の方法で部分集合に分割される。分類方法は、キーが
完全に分類されるまで、キーの部分集合に対して繰り返
される。
うかが分からない場合、かなりの数のキーが、共通の接
頭部を共有するのかどうかが決まるまで、キーをランダ
ムに抽出する分類方法が提供され、決定後は、上記方法
を用いてキーを分類する。このケースでのランダム・サ
ンプリングは、キーの集合からキーの部分集合をランダ
ムに選ぶことを含み、共通の接頭部を有するキーの集合
に、かなりの数のキーがある場合に、共通の接頭部を共
有するキーの部分集合に２つのキーが有るかどうかを求
める。共通の接頭部を共有する２つのキーがない場合、
キーの集合は、該キーの最上位のバイトの値に従って従
来の方法で部分集合に分割される。分類方法は、キーが
完全に分類されるまで、キーの部分集合に対して繰り返
される。
【００１３】本発明を他の見地から考察するに、本発明
は、各々が対応するレコードと関連するキーの集合を分
類するための、データ処理システムを提供し、該システ
ムは、キーの集合を部分集合に分割し、予め定義された
シーケンスで、キーの部分集合のそれぞれを分類するた
めの論理を含み、上記分割は、キーの集合の選択された
１つのキーに対して区別可能なコードワードを有する１
つ以上のキーを各々が有する部分集合に分割を行う。
は、各々が対応するレコードと関連するキーの集合を分
類するための、データ処理システムを提供し、該システ
ムは、キーの集合を部分集合に分割し、予め定義された
シーケンスで、キーの部分集合のそれぞれを分類するた
めの論理を含み、上記分割は、キーの集合の選択された
１つのキーに対して区別可能なコードワードを有する１
つ以上のキーを各々が有する部分集合に分割を行う。
【００１４】
【実施例】本発明の実施例における、ファイルの分類処
理は、便宜上、"分散"と称する分散プロシージャを反復
的に呼出すことによって実施される。プロシージャの目
的は、キーのｉ番目以降のバイトにおいて、キーが有す
る値によって、キーの集合Ｋをバケットに分散させるこ
とにある。プロシージャの"分散"が呼出される毎に、集
合Ｋの全てのキーは、ｉ−１バイトの共通接頭部を共有
する。"分散"は、キーの集合及び接頭部長さｓバイトで
ある補助変数Ｓを用いる。
理は、便宜上、"分散"と称する分散プロシージャを反復
的に呼出すことによって実施される。プロシージャの目
的は、キーのｉ番目以降のバイトにおいて、キーが有す
る値によって、キーの集合Ｋをバケットに分散させるこ
とにある。プロシージャの"分散"が呼出される毎に、集
合Ｋの全てのキーは、ｉ−１バイトの共通接頭部を共有
する。"分散"は、キーの集合及び接頭部長さｓバイトで
ある補助変数Ｓを用いる。
【００１５】プロシージャの"分散"の疑似コード記述
は、下記に示され且つ、図１にブロック図形式で示され
ている。
は、下記に示され且つ、図１にブロック図形式で示され
ている。
【００１６】プロシージャの"分散"（Ｋ、ｉ）を説明す
る。
る。
【００１７】ステップ１．Ｓを空にする。
【００１８】ステップ２．Ｓではない集合Ｋから、キー
Ｑをランダムに選ぶ。
Ｑをランダムに選ぶ。
【００１９】ステップ３．ｉ番目のバイトのｓバイトで
あるＳに属するキーＰが、Ｑの対応ｓバイトに等しい場
合、ステップ７に進む。
あるＳに属するキーＰが、Ｑの対応ｓバイトに等しい場
合、ステップ７に進む。
【００２０】ステップ４．該当するキーがない場合、Ｑ
をＳに加える。
をＳに加える。
【００２１】ステップ５．Ｓにおける現在のキー数が、
予め設定された限界ｍ個よりまだ、小さい場合は、ステ
ップ２へ戻る。
予め設定された限界ｍ個よりまだ、小さい場合は、ステ
ップ２へ戻る。
【００２２】ステップ６．従来のＭＳＢ基数法分類で、
キーを分散する。即ち、 ａ．２５６個のバケット、ｂ0、ｂ1、．．．、ｂ255
（各可能的バイト値に対して１バケット）を用意する。 ｂ．集合ＫのＱ＝ｑ1ｑ2．．．ｑd の個々の全てのメン
バを、Ｑのｉ番目のバイトｑiによって示されるバケッ
トｂに移動する。 ｃ．Ｆｏｒ ｊ＝０、１、．．．、２５５、の代入を実
行する。 １）ｂjが空であるならば、実行しない。 ２）ｂjが唯一１つのキーを有するか、又はｂjが有する
全てのキーが同じ値であるならば、ｂj の全てのキーを
作成される分類リストに加える。 ３）ｂjが少くとも２つの異なるキーを有するならば、"
分散"（｛ｂj｝、ｉ＋１）を呼出す。 ｄ．終了する。
キーを分散する。即ち、 ａ．２５６個のバケット、ｂ0、ｂ1、．．．、ｂ255
（各可能的バイト値に対して１バケット）を用意する。 ｂ．集合ＫのＱ＝ｑ1ｑ2．．．ｑd の個々の全てのメン
バを、Ｑのｉ番目のバイトｑiによって示されるバケッ
トｂに移動する。 ｃ．Ｆｏｒ ｊ＝０、１、．．．、２５５、の代入を実
行する。 １）ｂjが空であるならば、実行しない。 ２）ｂjが唯一１つのキーを有するか、又はｂjが有する
全てのキーが同じ値であるならば、ｂj の全てのキーを
作成される分類リストに加える。 ３）ｂjが少くとも２つの異なるキーを有するならば、"
分散"（｛ｂj｝、ｉ＋１）を呼出す。 ｄ．終了する。
【００２３】ステップ７．ピボットＰ＝Ｐ1Ｐ2．．．Ｐ
d に関するそれぞれのコードワードに応じて、キーを分
散する。即ち、 ａ．１≦ｌ≦ｄ且つ０≦ｖ≦２５５であるｄ×２５６個
のバケットｂ（ｌ、ｖ）、（各可能的コードワードに対
して１つのバケット）を用意する。 ｂ．集合Ｋの各メンバＱに対して、ピボットＰに対する
Ｑのコードワード（ｌ、ｖ）を計算し、Ｑをバケットｂ
（ｌ、ｖ）へ移動する。 ｃ．以下の順序でバケットを処理する。 ｂ（１、０）、ｂ（１、１）、ｂ（１、２）、．．．、
ｂ（１、ｐ1 −１）、ｂ（２、０）、ｂ（２、
１）、．．．、ｂ（２、ｐ2 −１）、．．．、ｂ（ｊ、
０）、ｂ（ｊ、１）、．．．、ｂ（ｊ、ｐj −
１）、．．．、ｂ（ｄ、０）、ｂ（ｄ、１）、．．．、
ｂ（ｄ、ｐd −１）、ｂ（ｄ、ｐd）、ｂ（ｄ、ｐd＋
１）、．．．、ｂ（ｄ、２５５）、．．．、ｂ（ｊ、ｐ
j＋１）、ｂ（ｊ、ｐj＋２）、．．．、ｂ（ｊ、２５
５）、．．．、ｂ（１、ｐ1＋１）、ｂ（１、ｐ1＋
２）、．．．、ｂ（１、２５５）。この順序は、各バケ
ットのキーが、シーケンスの後続するバケットのキーよ
りも小さいことを保証する。各バケットｂ（ｌ、ｖ）に
対して、以下を実行する。 １）ｂ（ｌ、ｖ）が空ならば、実行しない。 ２）ｂ（ｌ、ｖ）が、唯一１つのキーを有するか、又は
ｂ（ｌ、ｖ）が有する全てのキーが同じ値であるなら
ば、ｂ（ｌ、ｖ）の全てのキーを、作成される分類リス
トに加える。 ３）ｂ（ｌ、ｖ）が少くとも２つの異なるキーを有する
ならば、"分散"（（ｂ｛ｌ、ｖ｝）、ｌ＋１）を呼出
す。 ｄ．終了する。
d に関するそれぞれのコードワードに応じて、キーを分
散する。即ち、 ａ．１≦ｌ≦ｄ且つ０≦ｖ≦２５５であるｄ×２５６個
のバケットｂ（ｌ、ｖ）、（各可能的コードワードに対
して１つのバケット）を用意する。 ｂ．集合Ｋの各メンバＱに対して、ピボットＰに対する
Ｑのコードワード（ｌ、ｖ）を計算し、Ｑをバケットｂ
（ｌ、ｖ）へ移動する。 ｃ．以下の順序でバケットを処理する。 ｂ（１、０）、ｂ（１、１）、ｂ（１、２）、．．．、
ｂ（１、ｐ1 −１）、ｂ（２、０）、ｂ（２、
１）、．．．、ｂ（２、ｐ2 −１）、．．．、ｂ（ｊ、
０）、ｂ（ｊ、１）、．．．、ｂ（ｊ、ｐj −
１）、．．．、ｂ（ｄ、０）、ｂ（ｄ、１）、．．．、
ｂ（ｄ、ｐd −１）、ｂ（ｄ、ｐd）、ｂ（ｄ、ｐd＋
１）、．．．、ｂ（ｄ、２５５）、．．．、ｂ（ｊ、ｐ
j＋１）、ｂ（ｊ、ｐj＋２）、．．．、ｂ（ｊ、２５
５）、．．．、ｂ（１、ｐ1＋１）、ｂ（１、ｐ1＋
２）、．．．、ｂ（１、２５５）。この順序は、各バケ
ットのキーが、シーケンスの後続するバケットのキーよ
りも小さいことを保証する。各バケットｂ（ｌ、ｖ）に
対して、以下を実行する。 １）ｂ（ｌ、ｖ）が空ならば、実行しない。 ２）ｂ（ｌ、ｖ）が、唯一１つのキーを有するか、又は
ｂ（ｌ、ｖ）が有する全てのキーが同じ値であるなら
ば、ｂ（ｌ、ｖ）の全てのキーを、作成される分類リス
トに加える。 ３）ｂ（ｌ、ｖ）が少くとも２つの異なるキーを有する
ならば、"分散"（（ｂ｛ｌ、ｖ｝）、ｌ＋１）を呼出
す。 ｄ．終了する。
【００２４】プロシージャは、入力としてキーの集合Ｋ
を受信し、代表キーが、かなりの数の他のキーにおい
て、共通の接頭部を共有するキーを見つけられるかどう
かにもとづいて、代表キーに対して区別可能なコードワ
ードを有する部分集合にキーの集合を分割するか、或い
は従来のＭＳＢ基数法分類によってバイトｉの値に対応
するキーの集合を分割する。
を受信し、代表キーが、かなりの数の他のキーにおい
て、共通の接頭部を共有するキーを見つけられるかどう
かにもとづいて、代表キーに対して区別可能なコードワ
ードを有する部分集合にキーの集合を分割するか、或い
は従来のＭＳＢ基数法分類によってバイトｉの値に対応
するキーの集合を分割する。
【００２５】キーの集合を分類するには、集合Ｋが全体
としての入力で、且つｉ＝１において、プロシージャ
の"分散"が、最初に呼出されるだけである。プロシージ
ャの反復的性質上、集合Ｋ全体が分類されるまで処理が
続く。
としての入力で、且つｉ＝１において、プロシージャ
の"分散"が、最初に呼出されるだけである。プロシージ
ャの反復的性質上、集合Ｋ全体が分類されるまで処理が
続く。
【００２６】接頭部の長さｓの値が、かなり小さく選択
される場合、かなりの数の他のキーとで共通の接頭部を
共有しないピボットが選ばれる機会が生ずる。ｓの値
が、かなり大きく選択される場合、共通の接頭部を共有
するかなりの数のキーがないために不本意に終了する場
合、キーの集合は、一般のＭＳＢ基数法分類を使用して
分類される。本発明の実施例では、２つのキーの４バイ
トを機械命令で比較実行することにより、その処理が特
に容易であるＩＢＭ Ｓ／３７０プロセッサを使用する
ので、値ｓ＝４を使用する。２つのキーが、それぞれの
４バイト長さの接頭部で一致するならば、かなりの数の
他のキーとで、２つのキーは、共通の接頭部をほとんど
確実に共有することが分かっている。しかしながら、４
バイトより小さい接頭部を共有するかなりの数のキーが
有るならば、一般のＭＳＢ基数法分類の使用に関与す
る、タイム・ペナルティ（time penalty）が使用可能で
ある。
される場合、かなりの数の他のキーとで共通の接頭部を
共有しないピボットが選ばれる機会が生ずる。ｓの値
が、かなり大きく選択される場合、共通の接頭部を共有
するかなりの数のキーがないために不本意に終了する場
合、キーの集合は、一般のＭＳＢ基数法分類を使用して
分類される。本発明の実施例では、２つのキーの４バイ
トを機械命令で比較実行することにより、その処理が特
に容易であるＩＢＭ Ｓ／３７０プロセッサを使用する
ので、値ｓ＝４を使用する。２つのキーが、それぞれの
４バイト長さの接頭部で一致するならば、かなりの数の
他のキーとで、２つのキーは、共通の接頭部をほとんど
確実に共有することが分かっている。しかしながら、４
バイトより小さい接頭部を共有するかなりの数のキーが
有るならば、一般のＭＳＢ基数法分類の使用に関与す
る、タイム・ペナルティ（time penalty）が使用可能で
ある。
【００２７】予め設定される限界ｍは、バイト数ｓの関
数であり、且つ、２つのキーのｓバイト長さの接頭部を
比較することによる消費時間と、キーを一方のバケット
から他方のバケットへ移動させる消費時間との比率であ
る。本発明の実施例では、ｓ＝４、且つ比率ｒが約１／
３の場合、ｍ＝３５で最適であることが分かった。言い
換えると、３５個のキーが抽出され、サンプルに４バイ
トの接頭部を共有するキーが２つない場合、一般のＭＳ
Ｂ基数法分類を使用して抽出を行って、キーを分類する
のが得策である。４バイトの接頭部を共有する２つのキ
ーが、サンプルに有る場合は、これらの２つのうちの１
つに対するキーのコードワードにもとづく方法を使用す
るのが有利である。比率ｒが１／８であるならば、ｍ＝
５２が最適であり、ｒ＝０．６ならば、ｍ＝１６が最適
であることが分かった。ｒとｓの異なる値に対応するｍ
の最適値は、単純なプログラムによって前もって準備さ
れたテーブルで、調べられることが理解できよう。
数であり、且つ、２つのキーのｓバイト長さの接頭部を
比較することによる消費時間と、キーを一方のバケット
から他方のバケットへ移動させる消費時間との比率であ
る。本発明の実施例では、ｓ＝４、且つ比率ｒが約１／
３の場合、ｍ＝３５で最適であることが分かった。言い
換えると、３５個のキーが抽出され、サンプルに４バイ
トの接頭部を共有するキーが２つない場合、一般のＭＳ
Ｂ基数法分類を使用して抽出を行って、キーを分類する
のが得策である。４バイトの接頭部を共有する２つのキ
ーが、サンプルに有る場合は、これらの２つのうちの１
つに対するキーのコードワードにもとづく方法を使用す
るのが有利である。比率ｒが１／８であるならば、ｍ＝
５２が最適であり、ｒ＝０．６ならば、ｍ＝１６が最適
であることが分かった。ｒとｓの異なる値に対応するｍ
の最適値は、単純なプログラムによって前もって準備さ
れたテーブルで、調べられることが理解できよう。
【００２８】本発明の実施例において、バケットの処理
順序は、下記のように実行時間修正コードを使用して、
追跡できる。
順序は、下記のように実行時間修正コードを使用して、
追跡できる。
【００２９】ピボットＰ＝ｐ1ｐ2．．．ｐd でステップ
７に分岐される場合、コードのｄ番目のセグメントは、
図２で示されるように初期化されて準備される。図２に
おいて、Ｎｏ−Ｏｐ（No-Operation）は動作なし、即
ち、後続する命令に、ただ進むだけであり、及びＢｒ
Ｒは、サブルーチンＲへの分岐、即ち、Ｒとしてラベル
付けされたセグメントへ進むことを意味し、また、サブ
ルーチンＲの実行完了後に制御が戻るべき、分岐命令に
後続する命令のアドレスである、復帰アドレスを格納す
る。
７に分岐される場合、コードのｄ番目のセグメントは、
図２で示されるように初期化されて準備される。図２に
おいて、Ｎｏ−Ｏｐ（No-Operation）は動作なし、即
ち、後続する命令に、ただ進むだけであり、及びＢｒ
Ｒは、サブルーチンＲへの分岐、即ち、Ｒとしてラベル
付けされたセグメントへ進むことを意味し、また、サブ
ルーチンＲの実行完了後に制御が戻るべき、分岐命令に
後続する命令のアドレスである、復帰アドレスを格納す
る。
【００３０】また、アドレスのスタックＳが、用意され
る。
る。
【００３１】サブルーチンＲ２は、復帰アドレスをスタ
ックＳにプッシュし、呼出されたセグメントの元の位置
の後のセグメントの開始点に進む、即ち、セグメントが
セグメントｉから呼出されたならば、サブルーチンＲ２
は、セグメントｉ＋１の第１の命令に進む。最後のセグ
メントであるセグメントｄは、Ｒ２への分岐命令を含ま
ない。
ックＳにプッシュし、呼出されたセグメントの元の位置
の後のセグメントの開始点に進む、即ち、セグメントが
セグメントｉから呼出されたならば、サブルーチンＲ２
は、セグメントｉ＋１の第１の命令に進む。最後のセグ
メントであるセグメントｄは、Ｒ２への分岐命令を含ま
ない。
【００３２】サブルーチンＲ３は、スタックＳの最上部
からアドレスをポップ・アウトし、該アドレスに進む。
スタックＳが空であるならば、制御は、アルゴリズムに
戻り、分岐後のポイントの第１のセグメントに進む。
からアドレスをポップ・アウトし、該アドレスに進む。
スタックＳが空であるならば、制御は、アルゴリズムに
戻り、分岐後のポイントの第１のセグメントに進む。
【００３３】ステップ７のｂにおける分散処理中、キー
が最初にバケットｂ（ｌ、ｖ）に入ると、セグメントｌ
において、ｖ番目の命令が、Ｂｒ Ｒ１命令に変わる。
コードワードの定義によって、キーは、どのバケットｂ
（ｌ、ｐ1 ）にも入らず、命令Ｂｒ Ｒ２が、そのまま
残ることに注目されたい。
が最初にバケットｂ（ｌ、ｖ）に入ると、セグメントｌ
において、ｖ番目の命令が、Ｂｒ Ｒ１命令に変わる。
コードワードの定義によって、キーは、どのバケットｂ
（ｌ、ｐ1 ）にも入らず、命令Ｂｒ Ｒ２が、そのまま
残ることに注目されたい。
【００３４】分散が完了すると、セグメント１に分岐す
ることによって、ステップ７のｃが実行される。
ることによって、ステップ７のｃが実行される。
【００３５】サブルーチンＲ１は、呼出す命令（サブル
ーチンＲ１の復帰アドレスに先行する命令のアドレス）
のアドレスを計算し、該アドレスに従って対応するバケ
ットｂを見つけ、その内容を作成される分類リストに加
えるか、或いは、バケットｂに少くとも２つの異なるキ
ーが有るならば、ｂの内容で"分散"を呼出す。
ーチンＲ１の復帰アドレスに先行する命令のアドレス）
のアドレスを計算し、該アドレスに従って対応するバケ
ットｂを見つけ、その内容を作成される分類リストに加
えるか、或いは、バケットｂに少くとも２つの異なるキ
ーが有るならば、ｂの内容で"分散"を呼出す。
【００３６】主プロシージャにおいて、ステップ６へ分
岐される場合、２５７個の命令の１つのセグメントが用
意され、上記のセグメントｄとして初期化される。スタ
ックＳは、空で用意される。このケースでは、スタック
Ｓが満たされることはない。
岐される場合、２５７個の命令の１つのセグメントが用
意され、上記のセグメントｄとして初期化される。スタ
ックＳは、空で用意される。このケースでは、スタック
Ｓが満たされることはない。
【００３７】ステップ６のｂにおける分散処理中、キー
が最初にバケットｂj に入ると、セグメントにおいて、
ｊ番目の命令が、Ｂｒ Ｒ１命令に変わる。
が最初にバケットｂj に入ると、セグメントにおいて、
ｊ番目の命令が、Ｂｒ Ｒ１命令に変わる。
【００３８】分散が完了すると、セグメントの第１の命
令に分岐することによって、ステップ６のｃが実行され
る。
令に分岐することによって、ステップ６のｃが実行され
る。
【００３９】
【発明の効果】コードワードを使用することによって、
共通の接頭部が、効果的にスキップされることから、選
択キーと共通の接頭部を共有するキーの処理速度が向上
する。従って、かなりの数のキーが、共通の接頭部を共
有するケースでは、分類の効率が著しく改善される。
共通の接頭部が、効果的にスキップされることから、選
択キーと共通の接頭部を共有するキーの処理速度が向上
する。従って、かなりの数のキーが、共通の接頭部を共
有するケースでは、分類の効率が著しく改善される。
【図１】本発明の実施例の方法の概略的な流れ図を示
す。
す。
【図２】本発明の実施例で使用された実行時間修正コー
ドのセグメントを示す図である。
ドのセグメントを示す図である。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 サミュエル・ガル イスラエル共和国、ハイファ、シャベディ ア・ストリート 16 (72)発明者 ヨナ・ホランダー イスラエル共和国、テルアビブ、シカン・ ダン、ミシャマ・ハヤーデン・ストリート 37 (72)発明者 ダフナ・シェインワルド イスラエル共和国36803、ノフィット（ピ −ナー） 183
Claims (8)
- 【請求項１】キーの集合を部分集合に分割し、予め定義
されたシーケンスで該部分集合を分類処理する方法を有
し、該分割はキーの集合の選択された１つのキーに対し
て区別可能なコードワードを有する１つ以上のキーを各
々が有する部分集合にならしめる、各々が対応するレコ
ードに関連するキーの集合を分類するためのコンピュー
タ動作方法。 - 【請求項２】上記予め定義されたシーケンスにおいて、
各部分集合の全てのキーが、該シーケンスにおける後続
する部分集合のキーよりも小さい値を有することを特徴
とする請求項１記載の方法。 - 【請求項３】上記コードワードは参照キー及びインデッ
クスの数字の値とは異なるキーの最上位の数字のインデ
ックスを有し、上記方法はインデックスの各可能的な値
に各々が対応する多数の命令の集合を先行して格納する
ステップを含み、各集合は数字の可能的な値のそれぞれ
に対する命令を有し、上記命令は数字の連続した可能的
な値に対して該命令のメモリ・アドレスが連続するよう
に各集合に配置され、それぞれのインデックスで参照キ
ーの値に対応する各集合の命令は最下位の数字に対応す
る集合以外の集合の次の命令のメモリ・アドレスをスタ
ックにプッシュさせ、且つ、次の最上位の数字のインデ
ックスに対応する集合の第１の命令に分岐するように実
行させ、他の各集合の命令は非オペレーション命令状態
であり、追加された命令を有する各命令の集合はスタッ
クの最上部のアドレスを検索させて該アドレスに分岐す
るように実行させ、 及びここにおいて、キーの集合を部分集合に分割する分
割化は部分集合が最初に置かれたキーを有する場合に、
命令が部分集合を分類できるようにそれぞれの区別可能
なコードワードに対応する命令を変えることを含み、命
令の集合が最上位の数字に対応する集合にて開始を実行
させられる場合に、部分集合が予め定義されたシーケン
スで分類されることを特徴とする請求項１又は請求項２
記載の方法。 - 【請求項４】代表キーを求めるために、ランダムにキー
を抽出することによって選択キーが選択されることを特
徴とする請求項１乃至３記載の方法。 - 【請求項５】キーが、共通の接頭部を共有するかどうか
が決まるまで、ランダムにキーを抽出し、キーが共通の
接頭部を有する場合、選択キーとして共通の接頭部を共
有する集合のキーの１つで、請求項１乃至４記載の方法
を用いてキーを分類処理する、各々が対応するレコード
に関連するキーの集合を分類するための、コンピュータ
動作方法。 - 【請求項６】ランダムに抽出する方法は、キーの集合か
らキーの部分集合をランダムに選択することを含み、該
方法は、共通の接頭部を有するキーの集合に、かなりの
数のキーがある場合に、共通の接頭部を共有するキーの
部分集合に２つのキーが有るかどうかを求めることを含
むことを特徴とする請求項５記載のコンピュータ動作方
法。 - 【請求項７】キーの集合を部分集合に分割し、予め定義
されたシーケンスで該部分集合のそれぞれを分類処理す
る方法を有する、各々が対応するレコードに関連するキ
ーの集合を分類するためのコンピュータ動作方法であっ
て、キーの集合を部分集合に分割する方法が、 （ａ）キーの集合から１つのキーを選択するステップ
と、 （ｂ）キーの集合の各キーに対して、選択キーに対する
キーのコードワードを査定し、コードワードに対応する
部分集合にキーを置き、部分集合の分割化の終了時にお
いて、選択キーに対して区別可能なコードワードを有す
る単一のキー又は複数のキーを含ませるステップとを有
する上記方法。 - 【請求項８】キーの集合を部分集合に分割し、予め定義
されたシーケンスでキーの部分集合のそれぞれを分類す
るための論理を含み、上記分割がキーの集合の選択され
た１つのキーに対して区別可能なコードワードを有する
１つ以上のキーを各々が有する部分集合に分割を行う、
各々が対応するレコードに関連するキーの集合を分類す
るためのデータ処理システム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| GB92300324.8 | 1992-01-15 | ||
| EP92300324A EP0551691A1 (en) | 1992-01-15 | 1992-01-15 | Sorting method |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05265708A true JPH05265708A (ja) | 1993-10-15 |
Family
ID=8211229
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4325708A Pending JPH05265708A (ja) | 1992-01-15 | 1992-12-04 | コンピュータ動作方法 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5490269A (ja) |
| EP (1) | EP0551691A1 (ja) |
| JP (1) | JPH05265708A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8122064B2 (en) | 2005-06-30 | 2012-02-21 | Fujitsu Limited | Computer program, method, and apparatus for data sorting |
Families Citing this family (16)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB2283591B (en) * | 1993-11-04 | 1998-04-15 | Northern Telecom Ltd | Database management |
| GB2292821A (en) * | 1994-09-03 | 1996-03-06 | Ibm | Sorting method. |
| JPH0954676A (ja) * | 1995-08-11 | 1997-02-25 | Yamaha Corp | 整順列化方法および整順列化装置 |
| US5884297A (en) * | 1996-01-30 | 1999-03-16 | Telefonaktiebolaget L M Ericsson (Publ.) | System and method for maintaining a table in content addressable memory using hole algorithms |
| US5857196A (en) * | 1996-07-19 | 1999-01-05 | Bay Networks, Inc. | Method for storing a tree of potential keys in a sparse table |
| US5924091A (en) * | 1996-08-28 | 1999-07-13 | Sybase, Inc. | Database system with improved methods for radix sorting |
| CA2270472A1 (en) * | 1996-11-15 | 1998-05-28 | Michael Schindler | Computer sorting system for data compression |
| US6496830B1 (en) * | 1999-06-11 | 2002-12-17 | Oracle Corp. | Implementing descending indexes with a descend function |
| US7203694B2 (en) * | 2002-12-20 | 2007-04-10 | International Business Machines Corporation | System and method for multicolumn sorting in a single column |
| US7587396B2 (en) * | 2004-11-24 | 2009-09-08 | Oracle International Corporation | Encoding data to be sorted |
| US7680791B2 (en) * | 2005-01-18 | 2010-03-16 | Oracle International Corporation | Method for sorting data using common prefix bytes |
| US8150870B1 (en) | 2006-12-22 | 2012-04-03 | Amazon Technologies, Inc. | Scalable partitioning in a multilayered data service framework |
| US8095548B2 (en) | 2008-10-14 | 2012-01-10 | Saudi Arabian Oil Company | Methods, program product, and system of data management having container approximation indexing |
| US8185534B1 (en) * | 2009-02-05 | 2012-05-22 | Google Inc. | Consolidated record generation with stable identifiers for data integration systems |
| FR3068149B1 (fr) * | 2017-06-26 | 2019-11-22 | Continental Automotive France | Procede de surveillance de l’espace libre d’une pile memoire |
| US11637685B2 (en) | 2021-08-31 | 2023-04-25 | Samsung Display Co., Ltd. | System and method for transition encoding with flexible word-size |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4809158A (en) * | 1985-10-23 | 1989-02-28 | Mccauley Peter B | Sorting method and apparatus |
| JPS62187977A (ja) * | 1986-02-13 | 1987-08-17 | Dainippon Screen Mfg Co Ltd | 画像デ−タ処理装置 |
| US5237678A (en) * | 1987-05-08 | 1993-08-17 | Kuechler William L | System for storing and manipulating information in an information base |
| US5218700A (en) * | 1990-01-30 | 1993-06-08 | Allen Beechick | Apparatus and method for sorting a list of items |
-
1992
- 1992-01-15 EP EP92300324A patent/EP0551691A1/en not_active Withdrawn
- 1992-12-04 JP JP4325708A patent/JPH05265708A/ja active Pending
-
1993
- 1993-01-13 US US08/003,929 patent/US5490269A/en not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8122064B2 (en) | 2005-06-30 | 2012-02-21 | Fujitsu Limited | Computer program, method, and apparatus for data sorting |
Also Published As
| Publication number | Publication date |
|---|---|
| US5490269A (en) | 1996-02-06 |
| EP0551691A1 (en) | 1993-07-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH05265708A (ja) | コンピュータ動作方法 | |
| US5412807A (en) | System and method for text searching using an n-ary search tree | |
| US5440482A (en) | Forward and reverse Boyer-Moore string searching of multilingual text having a defined collation order | |
| US7882109B2 (en) | Computer representation of a data tree structure and the associated encoding/decoding methods | |
| US7558802B2 (en) | Information retrieving system | |
| US7062499B2 (en) | Enhanced multiway radix tree and related methods | |
| US5485373A (en) | Language-sensitive text searching system with modified Boyer-Moore process | |
| US7526497B2 (en) | Database retrieval apparatus, retrieval method, storage medium, and program | |
| US5421007A (en) | Key space analysis method for improved record sorting and file merging | |
| AU7738596A (en) | Storage and retrieval of ordered sets of keys in a compact 0-complete tree | |
| US5367677A (en) | System for iterated generation from an array of records of a posting file with row segments based on column entry value ranges | |
| US6735600B1 (en) | Editing protocol for flexible search engines | |
| EP0381418A2 (en) | A small fast lookup table for use in a data processing system | |
| JPH06131392A (ja) | データベースシステム | |
| US8204882B2 (en) | Method for accessing a storage unit during the search for substrings, and a corresponding storage unit | |
| JP2001527240A (ja) | データ構造内の管理 | |
| US7870119B2 (en) | Advanced scrolling for relational database applications | |
| US20030084031A1 (en) | System and method for searching a signature set for a target signature | |
| Janus et al. | An adaptive method for unknown distributions in distributive partitioned sorting | |
| US8019768B1 (en) | Bidirectional data structure processing | |
| US6411958B1 (en) | Data processing system and method for generating a structured listing of symbols | |
| US7747635B1 (en) | Automatically generating efficient string matching code | |
| US20030187843A1 (en) | Method and system for searching for a list of values matching a user defined search expression | |
| WO1998056005A2 (en) | Method and device for data sequence manipulation | |
| Merlini et al. | Modified binary searching for static tables |