JP2010146472A5

JP2010146472A5 -

Info

Publication number: JP2010146472A5
Application number: JP2008325692A
Authority: JP
Filing date: 2008-12-22
Publication date: 2012-02-09
Anticipated expiration: 2028-12-22

Description

最小値キー１４８ｂは、図の点線の矢印１５８ｂに示すように、ソート済みキー列１３０のキー位置１３０ｃに格納される。
一方、最小値キー１４８ｂとの差分ビット位置が１であるキー群１４１ｂにはキーが複数含まれているので、図の点線の矢印の組１５１ｂに示すように、差分ビット位置による分類１４９ｃにおいて、キー群１４１ｂ内の最小値キー１４８ｃと、最小値キー１４８ｃとの差分ビット位置が３であるキー群１４３ｃ、に分類される。図の例では、最小値キー１４８ｃは“１１１０”である。キー群１４３ｃにはキー
“１１１１”のみが含まれている。

以上の処理により、キー列１００のキーは、ソート済みキー列１３０のキー位置１３０ａ〜１３０ｅに昇順で格納され、ソート処理が完了する。そして、本実施の態様によるソート処理は、差分ビット位置に基づいて分類を繰り返すので、分類処理毎に必ずキーの分類が実行される。なお、上述の例では、最小値キーを、差分ビット位置を計算する基準のキーとしているが、最大値キーを、差分ビット位置を計算する基準のキーとすることも可能である。この場合には、図１Ｂのソート対象キーの例では、最大値キーがキー“１１１１”であり、最初の差分ビット位置による分類処理の結果として、最大値キー、差分ビット位置が３のキー“１１１０”、差分ビット位置が１のキー“１０１０”及び差分ビット位置が０のキー“００１１”と“０００１”の組が得られる。

上述の処理を、ステップＳ４０９において、差分ビット位置表の全ての差分ビット位置のエントリについて処理済みである、と判定されるまで繰り返し、その判定が得られるとソート対象のキーのソートが完了しているので処理を終了する。
図４Ｂに例示する処理は、差分ビット位置を計算する基準となるキーを最小のキーとし、差分ビット位置の降順で処理を行ってソート済みキーを昇順で取り出すものである。しかし、先に述べたように、差分ビット位置を計算する基準となるキーを最大のキーとする場合には、基準キーに対して同一の差分ビット位置を有するキーのうち最大のキーの読出位置を親リンクとし、差分ビット位置の降順で処理を行ってソート済みキーを降順で取り出すことができることは、本明細書及び図面の記載によって当業者に明らかである。

ステップＳ５２２に進み、キー表より、次リンクの指すキーをソートキーとして取り出すとともに、次リンクをソートキーの読出位置に設定する。そして、ステップＳ５２３において、リンク表より次リンクの指すリンクを読み出して退避エリアに退避する。ステップＳ５２２における次リンクは、図４Ｂに示すステップＳ４１３において、リンク表より読み出された親リンクの指すリンクである。図２Ａの例の差分ビット位置０を有するキーの分類処理であれば、親リンクがＰ３、次リンクがＰ４、そして次リンクの指すリンクであって退避エリアに退避されるリンクはＰ１である。

矢印６８０ａで示す差分ビット表３１０の差分ビット位置０の親リンクＰ３が取り出され、点線の矢印６８３ｂで示すＰ３を読出位置とするキー表３０９からの点線の矢印６８３ｄに示すように、キー表３０９の読出位置Ｐ３に格納されたキー“１０１０”、すなわち親リンクＰ３の指すキーが図４Ｂに示すステップＳ４１２でソート済みキーとして取り出されて一時記憶領域であるソート済みキー６５０に設定され、さらにソート済みキー表３１３の書込位置６４０ｃに書き出される。

Claims

ビット列で表されるソート対象のキーのソート処理を行うビット列データソート装置において、
前記ソート対象のキーを記憶するソート対象キー記憶手段と、
前記ソート対象キー記憶手段に記憶された前記ソート処理を構成する分類処理の分類対象である前記キーと、該分類対象であるキーのうち基準となるキーと、のビット列比較により、最初に異なるビット値となる差分ビット位置を求める差分ビット位置計算手段と、
前記差分ビット位置計算手段で求めた差分ビット位置毎に該差分ビット位置を有するキーの識別情報を記憶する分類対象キー差分ビット位置記憶手段と、
前記差分ビット位置計算手段で求めた前記差分ビット位置毎に該差分ビット位置を有するキーの識別情報を前記分類対象キー差分ビット位置記憶手段に書き込むことにより、前記分類対象であるキーを同一の差分ビット位置を有する組に分類する差分ビット位置分類手段と、
前記差分ビット位置分類手段で分類された同一の差分ビット位置を有するキーが１つの場合はそのキーを、同一の差分ビット位置を有するキーが複数の場合はそのうちの次の分類処理において基準となるキーをソート済みキーとして出力するソート済みキー出力手段と、
前記差分ビット位置計算手段、前記差分ビット位置分類手段及び前記ソート済みキー出力手段を制御する制御手段と、
を備え、
前記制御手段は、
前記差分ビット位置計算手段が、前記差分ビット位置計算手段の最初の処理における前記分類対象をソート対象のキー全体とし、以後、前記差分ビット位置分類手段で分類された同一の差分ビット位置を有するキーを複数含むキーの組を前記分類対象として前記差分ビット位置をもとめることを繰り返し、
前記差分ビット位置分類手段が、前記差分ビット位置計算手段で求められた差分ビット位置毎に同一の差分ビット位置を有する組に分類することを繰り返し、
前記ソート済みキー出力手段は、前記差分ビット位置分類手段が前記差分ビット位置毎に同一の差分ビット位置を有する組に分類するたびに、該同一の差分ビット位置を有するキーが１つの場合のキー及び前記基準となるキーをソート済みキーとして出力するように、
前記差分ビット位置計算手段、前記前記差分ビット位置分類手段及び前記ソート済みキー出力手段を制御し、
前記分類対象であるキーのうち基準となるキーを、分類対象であるキーのうち最小の値をとる最小値キーあるいは最大の値をとる最大値キーとすること
を特徴とするビット列データソート装置。
請求項１に記載のビット列データソート装置において、
前記キーを識別する情報は、該キーが記憶された前記ソート対象キー記憶手段における該キーのアドレスである読出位置であり、
前記分類対象キー差分ビット位置記憶手段は、前記分類対象であるキーと該分類対象であるキーのうち基準となるキーである前記最小値キーあるいは最大値キーとの差分ビット位置毎に、該最小値キーあるいは最大値キーに対する同一の差分ビット位置を有するキーのうち、最小あるいは最大のキーの前記読出位置である親リンクを格納する差分ビット位置表と、前記読出位置毎に該読出位置のキーと前記同一の差分ビット位置を有するキーの読出位置であるリンクを格納するリンク表から構成されることを特徴とするビット列データソート装置。
請求項２に記載のビット列データソート装置において、
前記同一の差分ビット位置を有するキーの前記キー表の読出位置をリンク表の読出位置とするリンクは、該リンクをリンク表の読出位置とし、さらに該読出位置に設定されたリンクをたどることにより、前記同一の差分ビット位置を有する全てのキーの前記ソート対象キー記憶手段の読出位置を参照するために設定されており、該同一の差分ビット位置を有するキーのうちの最後のキーの読出位置のリンクには、該最後のキーの読出位置が格納されていることを特徴とするビット列データソート装置。
請求項３に記載のビット列データソート装置において、
前記制御手段は、前記差分ビット位置分類手段が、前記差分ビット位置表の差分ビット位置の降順あるいは昇順に、該差分ビット位置に格納された前記親リンクを読出位置とするキーと同一の差分ビット位置を有する組を分類することを繰り返すように、制御することを特徴とするビット列データソート装置。
ビット列で表されるソート対象のキーのソート処理を行うビット列データソート方法において、
前記ソート対象のキーを記憶するソート対象キー記憶手段に前記ソート対象のキーを記憶するソート対象キー記憶ステップと、
前記ソート対象キー記憶手段に記憶された前記ソート処理を構成する分類処理の分類対象である前記キーと、該分類対象であるキーのうち基準となるキーと、のビット列比較により、最初に異なるビット値となる差分ビット位置を求める差分ビット位置計算ステップと、
前記差分ビット位置計算ステップで求めた差分ビット位置毎に、分類対象キー差分ビット位置記憶手段に該差分ビット位置を有するキーの識別情報を書き込むことにより、前記分類対象であるキーを同一の差分ビット位置を有する組に分類する差分ビット位置分類ステップと、
前記差分ビット位置分類ステップで分類された同一の差分ビット位置を有するキーが１つの場合はそのキーを、同一の差分ビット位置を有するキーが複数の場合はそのうちの次の分類処理において基準となるキーをソート済みキーとして出力するソート済みキー出力ステップと、
前記差分ビット位置計算ステップ、前記差分ビット位置分類ステップ及び前記ソート済みキー出力ステップを制御する制御ステップと、
を備え、
前記制御ステップは、
最初の処理における前記分類対象をソート対象のキー全体として前記差分ビット位置計算ステップを実行し、以後、前記差分ビット位置分類ステップで分類された同一の差分ビット位置を有するキーを複数含むキーの組を前記分類対象として前記差分ビット位置計算ステップを繰り返し、
前記差分ビット位置計算ステップで求められた差分ビット位置毎に同一の差分ビット位置を有する組に分類する前記差分ビット位置分類ステップを繰り返し、
前記差分ビット位置分類ステップが前記差分ビット位置毎に同一の差分ビット位置を有する組に分類するたびに、前記ソート済みキー出力ステップが、該同一の差分ビット位置を有するキーが１つの場合のキー及び前記基準となるキーをソート済みキーとして出力するように、前記差分ビット位置計算ステップ、前記前記差分ビット位置分類ステップ及び前記ソート済みキー出力ステップを制御するものであり、
前記分類対象であるキーのうち基準となるキーを、分類対象であるキーのうち最小の値をとる最小値キーあるいは最大の値をとる最大値キーとする、
ことを特徴とするビット列データソート方法。
請求項５に記載のビット列データソート方法において、
前記キーを識別する情報は、該キーが記憶された前記ソート対象キー記憶手段における該キーのアドレスである読出位置であり、
前記分類対象キー差分ビット位置記憶手段は、前記分類対象であるキーと該分類対象であるキーのうち基準となるキーである前記最小値キーあるいは最大値キーとの差分ビット位置毎に、該最小値キーあるいは最大値キーに対する同一の差分ビット位置を有するキーのうち、最小あるいは最大のキーの前記読出位置である親リンクを格納する差分ビット位置表と、前記読出位置毎に該読出位置のキーと前記同一の差分ビット位置を有するキーの読出位置であるリンクを格納するリンク表から構成されることを特徴とするビット列データソート方法。
請求項６に記載のビット列データソート方法において、
前記同一の差分ビット位置を有するキーの前記キー表の読出位置をリンク表の読出位置とするリンクは、該リンクをリンク表の読出位置とし、さらに該読出位置に設定されたリンクをたどることにより、前記同一の差分ビット位置を有する全てのキーの前記ソート対象キー記憶手段の読出位置を参照するために設定されており、該同一の差分ビット位置を有するキーのうちの最後のキーの読出位置のリンクには、該最後のキーの読出位置が格納されていることを特徴とするビット列データソート方法。
請求項７に記載のビット列データソート方法において、
前記制御ステップは、前記差分ビット位置分類ステップが、前記差分ビット位置表の差分ビット位置の降順あるいは昇順に、該差分ビット位置に格納された前記親リンクを読出位置とするキーと同一の差分ビット位置を有する組を分類することを繰り返すように、制御することを特徴とするビット列データソート方法。
請求項５〜請求項８のいずれか１項に記載のビット列データソート方法をコンピュータに実行させるプログラム。
請求項５〜請求項８のいずれか１項に記載のビット列データソート方法をコンピュータに実行させるプログラムを記憶したコンピュータ読み取り可能な記憶媒体。