(57)【要約】【課題】ビット列データのソート処理において、無効となる処理が発生しない、効率的なソート手法を提供する。【解決手段】最初の基準となるキーをソート対象のキーから選択し、選択されたキーより小さいキーのグループと大きいキーのグループ毎に、基準となるキーとソート対象であるビット列からなるキーのビット列比較を行い、最初に異なるビット値となるビット位置である差分ビット位置を求め、ソート対象のキーの差分ビット位置による分類を行い、同一の差分ビット位置に分類された複数のキーのうちの基準となるキーについての差分ビット位置による分類をさらに繰り返すことにより、ソート済みキー列を取得する。【選択図】図２Ａ
2011048801.tif 000002
【特許請求の範囲】
【請求項１】
ビット列で表されるソート対象のキーのソート処理を行うビット列データソート装置において、
前記ソート対象のキーを記憶するソート対象キー記憶手段と、
前記ソート対象のキー全体のうちの任意のキーである基準キーとソート対象キー記憶手段に記憶された該基準キー以外のキーとの大小比較により該基準キーより小さいキーのグループと大きいキーのグループのグループ分けを行うグループ分け手段と、
前記ソート対象キー記憶手段に記憶された前記ソート処理を構成する分類処理の分類対象である前記キーと、該分類対象であるキーのうち基準となるキーと、のビット列比較により、最初に異なるビット値となる差分ビット位置を求める差分ビット位置計算手段と、
前記差分ビット位置計算手段で求めた差分ビット位置毎に該差分ビット位置を有するキーの識別情報を記憶する分類対象キー差分ビット位置記憶手段と、
前記差分ビット位置計算手段で求めた前記差分ビット位置毎に該差分ビット位置を有するキーの識別情報を前記分類対象キー差分ビット位置記憶手段に書き込むことにより、前記分類対象であるキーを同一の差分ビット位置を有する組に分類する差分ビット位置分類手段と、
前記差分ビット位置分類手段で分類された同一の差分ビット位置を有するキーが１つの場合はそのキーを、同一の差分ビット位置を有するキーが複数の場合はそのうちの次の分類処理において基準となるキーをソート済みキーとして出力するソート済みキー出力手段と、
前記グループ分け手段、前記差分ビット位置計算手段、前記差分ビット位置分類手段及び前記ソート済みキー出力手段を制御する制御手段と、
を備え、
前記制御手段は、
最初の前記分類処理において、
前記グループ分け手段が、前記基準キーと前記基準キー以外のキーとの大小比較により該基準キーより小さいキーのグループと大きいキーのグループのグループ分けを行い、
前記差分ビット位置計算手段が、前記基準キーと該基準キー以外のキーの差分ビット位置を求め、
前記差分ビット位置分類手段が、前記基準キーより小さいキーのグループと大きいキーのグループ毎に、前記差分ビット位置計算手段が求めた前記差分ビット位置毎に該差分ビット位置を有するキーの識別情報を前記分類対象キー差分ビット位置記憶手段に書き込み、
以後の前記分類処理において、前記基準キーより小さいキーのグループと大きいキーのグループ毎に、
前記差分ビット位置計算手段が、前記差分ビット位置分類手段で分類された同一の差分ビット位置を有するキーを複数含むキーの組を前記分類対象として前記差分ビット位置を求めることを繰り返し、
前記差分ビット位置分類手段が、前記差分ビット位置計算手段が求めた差分ビット位置毎に同一の差分ビット位置を有する組に分類することを繰り返し、
前記ソート済みキー出力手段が、前記差分ビット位置分類手段が前記差分ビット位置毎に同一の差分ビット位置を有する組に分類するたびに、該同一の差分ビット位置を有するキーが１つの場合のキー及び前記基準となるキーをソート済みキーとして出力するために、
前記グループ分け手段、前記差分ビット位置計算手段、前記差分ビット位置分類手段及び前記ソート済みキー出力手段を制御すること、
を特徴とするビット列データソート装置。
【請求項２】
請求項１に記載のビット列データソート装置において、
前記基準キーを、前記ソート対象キー記憶手段から最初に読み込まれるキーとし、該基準キーより小さいキーのグループにおける前記分類対象であるキーのうち基準となるキーを最大の値をとる最大値キーとし、該基準キーより大きいキーのグループにおける前記分類対象であるキーのうち基準となるキーを最小の値をとる最小値キーとすることを特徴とするビット列データソート装置。
【請求項３】
請求項２に記載のビット列データソート装置において、
前記キーを識別する情報は、該キーが記憶された前記ソート対象キー記憶手段における該キーのアドレスである読出位置であり、
前記分類対象キー差分ビット位置記憶手段は、前記基準キーより小さいキーのグループにおける前記分類対象であるキーと該分類対象であるキーのうち基準となるキーである前記最大値キーあるいは前記基準キーとの差分ビット位置毎に、該最大値キーあるいは前記基準キーに対する同一の差分ビット位置を有するキーのうち、最大のキーの前記読出位置である親リンクを格納する第１の差分ビット位置表と、前記基準キーより大きいキーのグループにおける前記分類対象であるキーと該分類対象であるキーのうち基準となるキーである前記最小値キーあるいは前記基準キーとの差分ビット位置毎に、該最小値キーあるいは前記基準キーに対する同一の差分ビット位置を有するキーのうち、最小のキーの前記読出位置である親リンクを格納する第２の差分ビット位置表と、前記読出位置毎に該読出位置のキーと前記同一の差分ビット位置を有するキーの読出位置であるリンクを格納するリンク表から構成されることを特徴とするビット列データソート装置。
【請求項４】
請求項３に記載のビット列データソート装置において、
前記同一の差分ビット位置を有するキーの前記ソート対象キー記憶手段の読出位置をリンク表の読出位置とするリンクは、該リンクをリンク表の読出位置とし、さらに該読出位置に設定されたリンクを順次たどることにより、前記同一の差分ビット位置を有する全てのキーの前記ソート対象キー記憶手段の読出位置を参照するために設定されており、該同一の差分ビット位置を有するキーのうちの最後のキーの読出位置のリンクには、該最後のキーの読出位置が格納されていることを特徴とするビット列データソート装置。
【請求項５】
ビット列で表されるソート対象のキーのソート処理を行うビット列データソート方法において、
前記ソート対象のキーを記憶するソート対象キー記憶手段に前記ソート対象のキーを記憶するソート対象キー記憶ステップと、
前記ソート対象のキー全体のうちの任意のキーである基準キーとソート対象キー記憶手段に記憶された該基準キー以外のキーとの大小比較により該基準キーより小さいキーのグループと大きいキーのグループのグループ分けを行うグループ分けステップと、
前記ソート対象キー記憶手段に記憶された前記ソート処理を構成する分類処理の分類対象である前記キーと、該分類対象であるキーのうち基準となるキーと、のビット列比較により、最初に異なるビット値となる差分ビット位置を求める差分ビット位置計算ステップと、
前記差分ビット位置計算ステップで求めた差分ビット位置毎に、分類対象キー差分ビット位置記憶手段に該差分ビット位置を有するキーの識別情報を書き込むことにより、前記分類対象であるキーを同一の差分ビット位置を有する組に分類する差分ビット位置分類ステップと、
前記差分ビット位置分類ステップで分類された同一の差分ビット位置を有するキーが１つの場合はそのキーを、同一の差分ビット位置を有するキーが複数の場合はそのうちの次の分類処理において基準となるキーをソート済みキーとして出力するソート済みキー出力ステップと、
前記グループ分けステップ、前記差分ビット位置計算ステップ、前記差分ビット位置分類ステップ及び前記ソート済みキー出力ステップを制御する制御ステップと、
を備え、
前記制御ステップは、
最初の前記分類処理において、
前記グループ分けステップが、前記基準キーと前記基準キー以外のキーとの大小比較により該基準キーより小さいキーのグループと大きいキーのグループのグループ分けを行い、
前記差分ビット位置計算ステップが、前記基準キーと該基準キー以外のキーの差分ビット位置を求め、
前記差分ビット位置分類ステップが、前記基準キーより小さいキーのグループと大きいキーのグループ毎に、前記差分ビット位置計算ステップで求めた前記差分ビット位置毎に該差分ビット位置を有するキーの識別情報を前記分類対象キー差分ビット位置記憶手段に書き込み、
以後の前記分類処理において、前記基準キーより小さいキーのグループと大きいキーのグループ毎に、
前記差分ビット位置計算ステップが、前記差分ビット位置分類手段で分類された同一の差分ビット位置を有するキーを複数含むキーの組を前記分類対象として前記差分ビット位置を求めることを繰り返し、
前記差分ビット位置分類ステップが、前記差分ビット位置計算手段が求めた差分ビット位置毎に同一の差分ビット位置を有する組に分類することを繰り返し、
前記ソート済みキー出力ステップが、前記差分ビット位置分類ステップが前記差分ビット位置毎に同一の差分ビット位置を有する組に分類するたびに、該同一の差分ビット位置を有するキーが１つの場合のキー及び前記基準となるキーをソート済みキーとして出力するために、
前記グループ分けステップ、前記差分ビット位置計算ステップ、前記差分ビット位置分類ステップ及び前記ソート済みキー出力ステップを制御する、
ことを特徴とするビット列データソート方法。
【請求項６】
請求項５に記載のビット列データソート方法において、
前記基準キーを、前記ソート対象キー記憶手段から最初に読み込まれるキーとし、該基準キーより小さいキーのグループにおける前記分類対象であるキーのうち基準となるキーを最大の値をとる最大値キーとし、該基準キーより大きいキーのグループにおける前記分類対象であるキーのうち基準となるキーを最小の値をとる最小値キーとすることを特徴とするビット列データソート方法。
【請求項７】
請求項６に記載のビット列データソート方法において、
前記キーを識別する情報は、該キーが記憶された前記ソート対象キー記憶手段における該キーのアドレスである読出位置であり、
前記分類対象キー差分ビット位置記憶手段は、前記基準キーより小さいキーのグループにおける前記分類対象であるキーと該分類対象であるキーのうち基準となるキーである前記最大値キーあるいは前記基準キーとの差分ビット位置毎に、該最大値キーあるいは前記基準キーに対する同一の差分ビット位置を有するキーのうち、最大のキーの前記読出位置である親リンクを格納する第１の差分ビット位置表と、前記基準キーより大きいキーのグループにおける前記分類対象であるキーと該分類対象であるキーのうち基準となるキーである前記最小値キーあるいは前記基準キーとの差分ビット位置毎に、該最小値キーあるいは前記基準キーに対する同一の差分ビット位置を有するキーのうち、最小のキーの前記読出位置である親リンクを格納する第２の差分ビット位置表と、前記読出位置毎に該読出位置のキーと前記同一の差分ビット位置を有するキーの読出位置であるリンクを格納するリンク表から構成されることを特徴とするビット列データソート方法。
【請求項８】
請求項７に記載のビット列データソート方法において、
前記同一の差分ビット位置を有するキーの前記ソート対象キー記憶手段の読出位置をリンク表の読出位置とするリンクは、該リンクをリンク表の読出位置とし、さらに該読出位置に設定されたリンクを順次たどることにより、前記同一の差分ビット位置を有する全てのキーの前記ソート対象キー記憶手段の読出位置を参照するために設定されており、該同一の差分ビット位置を有するキーのうちの最後のキーの読出位置のリンクには、該最後のキーの読出位置が格納されていることを特徴とするビット列データソート方法。
【請求項９】
請求項５〜請求項８のいずれか１項に記載のビット列データソート方法をコンピュータに実行させるプログラム。
【請求項１０】
請求項５〜請求項８のいずれか１項に記載のビット列データソート方法をコンピュータに実行させるプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビット列データのソート装置、方法及びプログラムに関する。
【背景技術】
【０００２】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【０００３】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
一方、データベースに関連した処理として、データベース中のレコードのインデックスキーによるソート処理が行われている。このソート処理もビット列のソート処理に帰着される。なお、以下においては、ビット列データを、単にキーということもある。
【０００４】
ソートの手法は各種のものが開発されており、下記特許文献１には、クイックソート、ラディックソート（基数ソート）等が紹介されている。また、特許文献２にも基数ソートが記載されている。
【０００５】
図１に示すのは、従来の基数ソートの概念を説明する図である。基数ソートによれば、図１に例示するソート対象である４ビットのビット列であるキーは、０ビット目から３ビット目に至る各ビット位置におけるビット値による分類を繰り返すことにより、ソートが実行される。以下、図１の例示により、基数ソートの概念を説明する。
【０００６】
図１には、ソート対象であるキーからなるキー列１００が示されている。図１の例示では、キー列１００に含まれるキーの存在するキーの位置であるキー位置１０１が１００ａ（以下、キー位置１００ａのように表記する。）である記憶領域にはキー“１０１０”が存在する。また、キー位置１００ｂ、１００ｃ、１００ｄ、１００ｅ、１００ｆ、１００ｇには、それぞれキー“０１１１”、“１０００”、“００１０”、“０１１０”
、“１１１１”、“１０１１”が存在する。
【０００７】
図１に示すように、まずビット位置毎の分類（０ビット目）１１０ａによりキー列１００に含まれるキーの０ビット目による分類が行われる。その結果、キー“０１１１”、キー“００１０”及びキー“０１１０”からなる０ビット目の値０の組１２０ａと、キー“１０１０”、キー“１０００”、キー“１１１１”
及びキー“１０１１”からなる値１の組１２１ａが得られる。次に値０の組１２０ａはビット位置毎の分類（１ビット目）１１０ｂにより、次に値１の組１２１ａはビット位置毎の分類（１ビット目）１１０ｅによりそれぞれ１ビット目の値による分類が行われる。
【０００８】
ビット位置毎の分類（１ビット目）１１０ｂでは、１ビット目の値０の組１２０ｂとして１つのキー“００１０”が得られるので、ソート済みキー列１３０のキーを格納する位置であるキー位置１３１が１３０ａ（以下、キー位置１３０ａのように表記する。）である記憶領域に格納される。また、１ビット目の値１の組１２１ｂとして、キー“０１１１”とキー“０１１０”の組が得られ、ビット位置毎の分類（２ビット目）１１０ｃの分類で、２ビット目の値に基づく分類が行われる。
【０００９】
２ビット目の分類１１０ｃでは、キー“０１１１”とキー“０１１０”の２ビット目が共に１であることから、２ビット目の値１の組１２１ｃしか得られず、１ビット目の値１の組１２１ｂと同じキーが３ビット目による分類の対象となり、ビット位置毎の分類（３ビット目）１１０ｄにより３ビット目による分類が行われる。ビット位置毎の分類（３ビット目）１１０ｄでは、３ビット目の値０の組１２０ｄとして１つのキー“０１１０”が得られるので、キー位置１３０ｂに格納される。同様に、３ビット目の値１の組１２１ｄとして１つのキー“０１１１”が得られるので、ソート済みキー列１３０の次の値のキーを格納するキー位置１３０ｃに格納される。なお、ソート済みキー列には、キー位置の符号順に小さいほうのキーから格納されるものとする。
【００１０】
一方、ビット位置毎の分類（１ビット目）１１０ｅでは、１ビット目の値０の組１２０ｅとして、キー“１０１０”、キー“１０００”
、キー“１０１１”の組が得られ、ビット位置毎の分類（２ビット目）１１０ｆの分類で、２ビット目の値に基づく分類が行われる。また、１ビット目の値１の組１２１ｅとして、１つのキー“１１１１”が得られるので、ソート済みキー列１３０のキー位置１３０ｇに格納される。
【００１１】
ビット位置毎の分類（２ビット目）１１０ｆでは、２ビット目の値０の組１２０ｆとして、１つのキー“１０００”が得られるので、ソート済みキー列１３０のキー位置１３０ｄに格納される。また、２ビット目の値１の組１２１ｆとして、キー“１０１０”、キー“１０１１”の組が得られ、ビット位置毎の分類（３ビット目）１１０ｇの分類で、３ビット目の値に基づく分類が行われる。
【００１２】
ビット位置毎の分類（３ビット目）１１０ｇでは、３ビット目の値０の組１２０ｇとして１つのキー“１０１０”が得られるので、ソート済みキー列１３０のキー位置１３０ｅに格納される。同様に、３ビット目の値１の組１２１ｇとして１つのキー“１０１１”が得られるので、ソート済みキー列１３０の次の格納位置であるキー位置１３０ｆに格納される。
【００１３】
以上の処理により、キー列１００のキーは、ソート済みキー列１３０のキー位置１３０ａ〜１３０ｇにソートされて格納される。しかし、上述の基数ソート方法によりソートを実行する場合には、図１に示すビット位置毎の分類（２ビット目）１１０ｃにみられるように、分類が行われない無効な処理が発生する。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００２−１１６９０７号公報
【特許文献２】特開２００５−３１６６６３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１５】
そこで本発明の解決しようとする課題は、ビット列データのソート処理において、無効となる処理が発生しない、効率的なソート手法を提供することである。
【課題を解決するための手段】
【００１６】
本発明のソート処理によれば、ソート対象のビット列からなるキーであるソート対象キーから任意の基準となるキーを基準キーとして選択し、基準キーとソート対象キーの大小比較を行い、ソート対象キーの基準キーより大きいキーと基準キーより小さいキーのそれぞれのグループ毎に、基準キーとソート対象キーのビット列比較を行い、最初に異なるビット値となるビット位置である差分ビット位置を求め、差分ビット位置によるソート対象キーの分類を行い、同一の差分ビット位置に分類された複数のキーのうちの基準となるキーについての差分ビット位置による分類をさらに繰り返すことにより、ソート済みキー列を取得する。
【発明の効果】
【００１７】
本発明によれば、差分ビット位置によりキーのソートを行うため、分類が行われない無効な処理は発生しない。したがって、効率的なソート処理を実現することができる。
【図面の簡単な説明】
【００１８】
【図１】従来の基数ソートの概念を説明する図である。
【図２Ａ】本発明の一実施の形態における差分ビット位置によるソート処理の概念を説明する図である。
【図２Ｂ】本発明の一実施の形態における差分ビット位置によるソート処理で用いるデータ構造例を説明する図である。
【図２Ｃ】本発明の一実施の形態におけるビット列データソート装置の機能ブロック構成例を説明する図である。
【図３】本発明を実施するためのハードウェア構成例を説明する図である。
【図４】本発明の一実施の形態におけるソート処理全体の処理フロー例を説明する図である。
【図５】本発明の一実施の形態における基準キーより小さいソートキーのグループと大きいソートキーのグループについてそれぞれ差分ビット位置により分類する処理フロー例を説明する図である。
【図６Ａ】本発明の一実施の形態における基準キーより大きいソートキーのグループを分類する処理の前段の処理フロー例を説明する図である。
【図６Ｂ】本発明の一実施の形態における基準キーより大きいソートキーのグループを分類する処理の後段の処理フロー例を説明する図である。
【図７Ａ】本発明の一実施の形態における基準キーより小さいソートキーのグループを分類する処理の前段の処理フロー例を説明する図である。
【図７Ｂ】本発明の一実施の形態における基準キーより小さいソートキーのグループを分類する処理の後段の処理フロー例を説明する図である。
【図８】本発明の一実施の形態における基準キーより小さいソートキーを差分ビット位置順に取り出す処理の処理フロー例を説明する図である。
【図９】本発明の一実施の形態における差分ビット位置にリンクする複数のソートキーを差分ビット位置順に細分類する処理の処理フロー例を説明する図である。
【図１０】本発明の一実施の形態における基準キーより大きいソートキーを差分ビット位置順に取り出す処理の処理フロー例を説明する図である。
【図１１】本発明の一実施の形態における差分ビット位置にリンクする複数のソートキーを差分ビット位置順に細分類する処理の処理フロー例を説明する図である。
【図１２】本発明の一実施の形態におけるキーを降順に取り出すデータの流れを説明する図である。
【発明を実施するための形態】
【００１９】
以下、本発明を実施するための形態を、図１に示すキー列１００に含まれるキーと同一のキーをソート対象のキーとして例示して説明する。
本出願人は、特願２００８−３２５６９２において、ソート対象キーの差分ビット位置に基づいた分類手法をすでに提案している。この提案済みの分類手法は、基準キーをソート対象キーの最小値あるいは最大値とするものである。
それに対して、以下で説明する本発明の実施の態様においては、基準キーとしてソート対象キーの中から任意のものを選択することができる。例えばソート対象キーの格納された記憶領域の先頭の位置に格納されたソート対象キーを基準キーとする。
【００２０】
図２Ａに示すのは、本発明の一実施の形態における差分ビット位置によるソート処理の概念を説明する図である。ソート対象のキー列１００及びソート済みキー列１３０は、図１に示すものと同じである。キー列１００の先頭のキー１００ａに位置するキー“１０１０”が基準キー１４８ａとして選択されている。
キー列１００を構成する各キーは、差分ビット位置による分類１４９ａにおいて、基準キー１４８ａ、基準キーより小さく、基準キー１４８ａとの差分ビット位置が０であるキー群１４０ａ及び基準キーとの差分ビット位置が２であるキー群１４２ａ、基準キーより大きく、基準キー１４８ａとの差分ビット位置が１であるキー群１４１ａ及び基準キーとの差分ビット位置が３であるキー群１４３ａに分類される。
【００２１】
図２Ａの例では、基準キー１４８ａは“１０１０”である。キー群１４０ａにはキー“０１１１”、“００１０”及び“０１１０”が含まれており、キー群１４２ａには、キー“１０００”のみが含まれている。また、キー群１４１ａには、キー“１１１１”のみが含まれ、キー群１４３ａには、キー“１０１１”のみが含まれている。
【００２２】
基準キー１４８ａは、図の点線の矢印１５８ａに示すように、ソート済みキー列１３０のキー位置１３０ｅに格納される。また、キー群１４２ａのキーは１つのみであるので、図の点線の矢印１５２ａに示すように、ソート済みキー列１３０のキー位置１３０ｄに格納される。同様に、キー群１４１ａのキー及びキー群１４３ａのキーはそれぞれ１つのみであるので、図の点線の矢印１５１ａ及び１５３ａに示すように、ソート済みキー列１３０のキー位置１３０ｇ及び１３０ｆにそれぞれ格納される。
なお、ソート済みキー列１３０へのキーの格納については、後に詳細に説明する。
【００２３】
基準キー１４８ａとの差分ビット位置が０であるキー群１４０ａにはキーが複数含まれているので、図の点線の矢印の組１５０ａに示すように、差分ビット位置による分類１４９ｂにおいて、キー群１４０ａ内の最大値キー１４８ｂと、最大値キー１４８ｂとの差分ビット位置が１であるキー群１４１ｂ、及び最大値キー１４８ｂとの差分ビット位置が３であるキー群１４３ｂに細分類される。図の例では、最大値キー１４８ｂは“０１１１”である。キー群１４１ｂには、キー
“００１０”のみが、キー群１４３ｂには、キー“０１１０”のみが含まれている。
【００２４】
最大値キー１４８ｂは、図の点線の矢印１５８ｂに示すように、ソート済みキー列１３０のキー位置１３０ｃに格納される。最大値キー１４８ｂとの差分ビット位置が１であるキー群１４１ｂに含まれるキーは１つなので、図の点線の矢印１５１ｂに示すように、ソート済みキー列１３０のキー位置１３０ａに格納される。また、最大値キー１４８ｂとの差分ビット位置が３であるキー群１４３ｂに含まれるキーも１つなので細分類は終了し、図の点線の矢印１５３ｂに示すように、ソート済みキー列１３０のキー位置１３０ｂに格納される。
【００２５】
以上の処理により、キー列１００のキーは、ソート済みキー列１３０のキー位置１３０ａ〜１３０ｇに昇順で格納され、ソート処理が完了する。そして、本実施の態様によるソート処理は、差分ビット位置に基づいて分類を繰り返すので、分類処理毎に必ずキーの分類が実行される。
【００２６】
なお、ソート済みキー列１３０のキー位置１３０ａ〜１３０ｇは連続した記憶領域のアドレスである必要はない。キー位置１３０ａ〜１３０ｄ、１３０ｅ、１３０ｆ〜１３０ｇがそれぞれ分離した３つの記憶領域のアドレスであってもよい。また、例えばキー位置１３０ａ〜１３０ｄが記憶領域のアドレスの大きいものから小さいものの方向に割り振られたものであってもよい。基準キーとそのキー位置１３０ｅ、基準キーより小さいキーのキー位置１３０ａ〜１３０ｄとアドレスの方向、基準キーより大きいキーのキー位置１３０ｆ〜１３０ｇとアドレスの方向が分かれば、キー表１３０からキーを昇順または降順に取り出すことは容易である。勿論、キー位置１３０ａ〜１３０ｇを連続した記憶領域のアドレスの順に割り付けることも可能である。
【００２７】
次に、図２Ａを参照してその概念を説明した本実施の形態における差分ビット位置によるソート処理を実現するためのデータ構造と機能ブロック構成について説明する。本実施の形態における差分ビット位置によるソート処理は、図２Ａに例示した差分ビット位置による分類１４９ａ、１４９ｂの処理を実行する機能ブロックを、ソート対象のあらゆるキーの組み合わせに対して用意すれば実現可能であることは明らかである。しかしそれでは資源の無駄遣いであり、その実現手法は現実的でない。そこで本実施の形態においては、以下に説明する工夫を行っている。
【００２８】
図２Ｂは、本発明の一実施の形態における差分ビット位置によるソート処理で用いるデータ構造例を説明するものである。図２Ｂに示すように、キー表３０９、差分ビット位置表３１０ａ、差分ビット位置表３１０ｂ、リンク表３１１、及び基準キーを設定する記憶領域である基準キー６５０ａが用いられる。
【００２９】
キー表３０９はソート要求があったときにソート対象キー６０２が読み込まれて設定されるものである。図２Ｂの例示では、ソート対象の７つのキー６０２は、図１及び図２Ａに示すキー列１００に含まれるものが読み込まれている。キー表３０９の読出位置６０１の先頭はＰ０であり、以下、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６と続いている。読出位置Ｐ０に設定されたキーを基準キーとしているが、別の読出位置に設定されたキーを基準キーとすることも可能である。点線の矢印６８９ｄで示すように、基準キーは基準キー６５０ａに設定される。
【００３０】
差分ビット位置表３１０ａは、基準キーより小であって基準キーに対する同一の差分ビット位置を有するキーのうち、図２Ｂの例では、最大のキーの読出位置６０１を親リンク６１２ａとして差分ビット位置６１１ａ毎に格納する。図２Ｂの例示では、点線の矢印６６０ａで示すように、基準キー“１０１０”との差分ビット位置が０であるキー“０１１１”、“００１０”、“０１１０”のうち最大のキー“０１１１”の読出位置Ｐ１が差分ビット位置表３１０ａの差分ビット位置６１１ａが０である位置に格納されている。また、点線の矢印６６２ａで示すように、基準キー“１０１０”との差分ビット位置が２であるキーはキー“１０００”だけであるので、キー“１０００”の読出位置Ｐ２が差分ビット位置表３１０ａの差分ビット位置６１１ａが２である位置に格納されている。
【００３１】
差分ビット位置表３１０ｂは、基準キーより大であって基準キーに対する同一の差分ビット位置を有するキーのうち、最小のキーの読出位置６０１を親リンク６１２ｂとして差分ビット位置６１１ｂ毎に格納するものである。図２Ａの例示では、点線の矢印６６１ａで示すように、基準キー“１０１０”との差分ビット位置が１であるキーはキー“１１１１”だけであるので、キー“１１１１”の読出位置Ｐ５が差分ビット位置表３１０ｂの差分ビット位置６１１ｂが１である位置に格納されている。また、点線の矢印６６３ａで示すように、基準キー“１０１０”との差分ビット位置が３であるキーはキー“１０１１”だけであるので、キー“１０１１”
の読出位置Ｐ６が差分ビット位置表３１０ｂの差分ビット位置６１１ｂが３である位置に格納されている。
【００３２】
リンク表３１１は、基準キーに対する同一の差分ビット位置を有するキーにアクセスするためのものである。図に示すように、キーの読出位置６２１に対して、同一の差分ビット位置を有するキーの読出位置を示すリンク６２２が格納されている。
【００３３】
差分ビット位置表３１０ａからリンク表３１１への点線の矢印６７１ｂで示すように、同一の差分ビット位置０を有するキーの最大値キーの読出位置Ｐ１（親リンク）に対して、その読出位置Ｐ１を読出位置６２１とするリンク表３１１の読出位置（以下、リンク表３１１の読出位置Ｐ１のようにいう。）に、基準キー“１０１０”に対して差分ビット位置０を有するキーの最大値キー“０１１１”と同一の差分ビット位置０を有するキー“０１１０”のキー表３０９の読出位置Ｐ４が格納されている。
【００３４】
そして、図の点線の矢印６７４ｃで示すように、リンク表３１１の読出位置Ｐ４に同一の差分ビット位置０を有するキー“００１０”のキー表３０９の読出位置Ｐ３が格納されている。また、図の点線の矢印６７３ｃで示すように、リンク表３１１の読出位置Ｐ３には、同一の値のキー表３０９の読出位置Ｐ３が格納されている。これにより、それ以上同一の差分ビット位置０を有するキーは存在しないことを表している。
【００３５】
また、差分ビット位置表３１０ａからリンク表３１１への点線の矢印６７２ｂで示すように、同一の差分ビット位置２を有するキーの最大値キーの読出位置Ｐ２（親リンク）に対して、リンク表３１１の読出位置Ｐ２には、リンク表３１１の読出位置Ｐ２と同一の値のキー表３０９の読出位置Ｐ２が格納されている。これは、キー表３０９の読出位置Ｐ２のキー“１０００”が基準キー“１０１０”との差分ビット位置が２であるキーの最大のキーであるとともに、唯一のものであることを示している。
【００３６】
一方、差分ビット位置表３１０ｂからリンク表３１１への点線の矢印６７５ｂで示すように、基準キーとの同一の差分ビット位置１を有するキーの最小値キーの読出位置Ｐ５（親リンク）に対して、リンク表３１１の読出位置Ｐ５には、リンク表３１１の読出位置Ｐ５と同一の値のキー表３０９の読出位置Ｐ５が格納されている。これは、キー表３０９の読出位置Ｐ５のキー“１１１１”が基準キー“１０１０”との差分ビット位置が１であるキーの最小のキーであるとともに、唯一のものであることを示している。
【００３７】
同様に、差分ビット位置表３１０ｂからリンク表３１１への点線の矢印６７６ｂで示すように、基準キーとの同一の差分ビット位置３を有するキーの最小値キーの読出位置Ｐ５に対して、リンク表３１１の読出位置Ｐ５には、リンク表３１１の読出位置Ｐ６と同一の値のキー表３０９の読出位置Ｐ６が格納されている。これは、キー表３０９の読出位置Ｐ６のキー“１０１１”が基準キー“１０１０”との差分ビット位置が３であるキーの最小のキーであるとともに、唯一のものであることを示している。
【００３８】
上述の図２Ｂに示す差分ビット位置表３１０ａ、３１０ｂとリンク表３１１の状態は、図２Ａに示す差分ビット位置による分類１４９ａが実行されて得られるものである。
以上の説明から明らかなとおり、上述のキー表３０９は請求項１に係る発明のソート対象キー記憶手段の一実施例である。また、差分ビット位置表３１０ａ、３１０ｂとリンク表３１１で分類対象キー差分ビット位置記憶手段の一実施例を構成しており、キー表３０９の読出位置６０１はキーの識別情報に相当する。
【００３９】
図２Ｃは、本発明の一実施の形態におけるビット列データソート装置の機能ブロック構成例を説明する図である。
図に示すように、ビット列データソート装置２００は、グループ分け手段２０５、差分ビット位置計算手段２１０、差分ビット位置分類手段２２０、ソート済みキー出力手段２３０、及び制御手段２４０を含む。以下、各手段の動作の概要について、図２Ｂの例示を参照して説明する。
【００４０】
グループ分け手段２０５は、キー表３０９に記憶された全てのソート対象のキーと基準キーの大小比較を行い、基準キーより小さいキーのグループと基準キーより大きいキーのグループのグループ分けを行う。差分ビット位置計算手段２１０は、キー表３０９に記憶されたキー６０２のうちの、差分ビット位置による分類処理の対象となるキーと差分ビット位置を計算する基準となるキーの差分ビット位置を計算する。差分ビット位置を計算する最初の基準となるキーは基準キーである。
差分ビット位置分類手段２２０は、基準キーより小さいキーのグループについての差分ビット位置計算手段２１０の最初の計算結果に基づいて、差分ビット位置表３１０ａとリンク表３１１の書き込みを行い、基準キーより大きいキーのグループについての差分ビット位置計算手段２１０の最初の計算結果に基づいて、差分ビット位置表３１０ｂとリンク表３１１の書き込みを行うことで、キーの差分ビット位置による分類を行う。
最初の分類の結果として、基準キーより小さいキーのグループは、キーの識別情報をキー表３０９の読出位置６０１として、差分ビット位置が０の組（Ｐ１、Ｐ４、Ｐ３）と差分ビット位置が２の組（Ｐ２）に分類される。また、基準キーより大きいキーのグループは、差分ビット位置が１の組（Ｐ５）と差分ビット位置が３の組（Ｐ６）に分類される。
【００４１】
制御手段２４０は、キー表３０９に格納されたキーをグループ分け手段２０５により基準キーより小さいキーのグループと大きいグループにグループ分けする。そして、最初の分類処理の対象をキー表３０９に記憶された基準キーより小さい全てのキーと基準キーより大きい全てのキーとする。この場合、差分ビット位置を計算する基準となる基準キーは、読出位置Ｐ０に格納されたキー“１０１０”である。ソート済みキー出力手段２３０は、この基準キー“１０１０をソート済みキー表３１３に出力する。
【００４２】
制御手段２４０は、分類後に複数のキーが含まれる組について、さらに差分ビット位置計算手段２１０による差分ビット位置の計算と差分ビット位置分類手段２２０による分類処理が繰り返されるように制御する。
【００４３】
図３は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明によるソート処理は中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。キー表３０９、差分ビット位置表３１０ａ、差分ビット位置表３１０ｂ、リンク表３１１、ソート済みキー表３１３を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
【００４４】
図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、キー表３０９は外部記憶装置３０６に、他の表は主記憶装置３０５に持つなど、使用可能なハードウェア環境、ソート対象キーの集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
【００４５】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた主記憶装置３０５の一時記憶領域が用いられることは当然である。そして、以下の説明においては、一次記憶領域に格納されるあるいは設定される値を一時記憶領域の名前で呼ぶことがある。
【００４６】
次に、本発明の一実施の形態におけるソート処理について、図４を参照してその概要を説明する。また、その説明において、図２Ａあるいは図２Ｂの例示を適宜用いて説明する。
【００４７】
図４は、本発明の一実施の形態におけるソート処理全体の処理フロー例を説明する図である。キー表にはソート対象のキーが記憶されていることを前提とする。すなわち、図２Ａに示すキー列１００に含まれるキーは図２Ｂに示すようにキー表３０９に記憶されているものとする。
【００４８】
まず、ステップＳ４０１において、キー表の先頭位置をキー表の読出位置（以下、単に読出位置ということがある。）に設定する。ここでいう「キー表の読出位置」は、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の１つである。以下の説明では、「キー表の先頭位置をキー表の読出位置に設定する。」のように、「キー表の読出位置」が図示しない一次記憶領域であることを省略して述べることがある。
上記の設定により、図２Ｂの例示では、キー表の読出位置にＰ０が設定される。
【００４９】
次にステップＳ４０２において、キー表より、先頭位置の指すキーを基準キーとして取り出す。ここでいう「基準キーとして取り出す」は、一時記憶領域である基準キーに設定する、の意味である。この一時記憶領域は、ほとんどの場合図示されていない。以下においても、同様な表記を用いる場合がある。
【００５０】
ステップＳ４０３に進み、読出位置に次の読出位置を設定する。次にステップＳ４０４において、全てのキーは処理済みか、すなわち、全てのキーについての初段における分類処理が終了したか判定する。
【００５１】
全てのキーが処理済みでなければ、ステップＳ４０５に進み、キー表より、読出位置の指すキーをソートキーとして取り出すとともに、読出位置をソートキーの読出位置に設定する。そしてステップＳ４０６において、ソートキーと基準キーの差分ビット位置を得て、差分ビット位置によりソートキーを分類し、ステップＳ４０３に戻る。
ステップＳ４０６の処理においては、初段における分類処理として差分ビット位置表とリンク表への設定が行われる。その処理の詳細については、後に図５、図６Ａ及び図６Ｂ、図７Ａ及び図７Ｂを参照して説明する。
【００５２】
一方、ステップＳ４０４で全てのキーが処理済みであると判定されると、ステップＳ４０７に分岐する。
ステップＳ４０７では、差分ビット位置表に、基準キーより小さいソートキーの差分ビット位置表を設定し、ステップＳ４０８に進んで基準キーより小さいソートキーを差分ビット位置順に取り出す。
【００５３】
ここで、ステップＳ４０７での「差分ビット位置表に、基準キーより小さいソートキーの差分ビット位置表を設定し、」とは、次のステップＳ４０８で処理対象とする差分ビット位置表を基準キーより小さいソートキーの差分ビット位置表とすることであり、図２Ｂの例示では、差分ビット位置表３１０ａを用いた処理が行われるようにすることである。例えば差分ビット位置表のアドレスを、基準キーより小さいソートキーの差分ビット位置表のアドレスとすることにより実行される。上述の「差分ビット位置表に、基準キーより小さいソートキーの差分ビット位置表を設定し、」の意味は、以下のその他のステップにおいても同様であり、また、「差分ビット位置表に、基準キーより大きいソートキーの差分ビット位置表を設定し、」という場合も、同様に次のステップで処理対象とする差分ビット位置表を基準キーより大きいソートキーの差分ビット位置表とすることである。
【００５４】
また、ステップＳ４０８での「ソートキーを差分ビット位置順に取り出す」とは、基準キーに対する差分ビット位置の昇順あるいは降順にソートキーを取り出し、同一の差分ビット位置を有する複数のソートキーの組に対してはその組内の基準キーに対する差分ビット位置の昇順あるいは降順にソートキーを取り出すことを、全てのキーを差分ビット位置により分離して取り出すまで繰り返すことである。
ステップＳ４０８の処理の詳細は、後に図８及び図９を参照して説明する。
【００５５】
ステップＳ４０８に引き続き、ステップ４０９において、ステップＳ４０２で得た基準キーをソート済みキー表に設定する。
続いてステップＳ４１０で、差分ビット位置表に、基準キーより大きいソートキーの差分ビット位置表を設定し、ステップＳ４１１に進んで基準キーより大きいソートキーを差分ビット位置順に取り出して処理を終了する。
ステップＳ４１１の処理の詳細は、後に図１０及び図１１を参照して説明する。
【００５６】
次に、図４に示すステップＳ４０６、ステップＳ４０８及びステップＳ４１１の処理の詳細を説明する。
図５は、図４に示すステップＳ４０６の処理を詳細に説明するものであり、本発明の一実施の形態における基準キーより小さいソートキーのグループと大きいソートキーのグループについてそれぞれ差分ビット位置により分類する処理フロー例を説明する図である。
【００５７】
始めに、ステップＳ５０１において、ソートキーは基準キーより大きいか判定する。ソートキーは、図４に示すステップＳ４０５でキー表から取り出されたものである。
ソートキーが基準キーより大きければ、ステップＳ５０２に進み、ソートキーが基準キーより小さければ、ステップＳ５０４に進む。ステップＳ５０１の処理により、ソートキーは、基準キーより小さいグループと基準キーより大きいグループにグループ分けされる。そして、グループ毎にソートキーの分類処理が行われる。
【００５８】
ステップＳ５０２では、差分ビット位置表に、基準キーより大きいソートキーの差分ビット位置表を設定する。そして、ステップＳ５０３に進んで、基準キーより大きいソートキーと基準キーの差分ビット位置によりソートキーを分類し、処理を終了する。ステップＳ５０３の処理の詳細は、後に図６Ａ及び図６Ｂを参照して説明する。
【００５９】
一方、ステップＳ５０４に進んだ場合は、差分ビット位置表に、基準キーより小さいソートキーの差分ビット位置表を設定する。そして、ステップＳ５０５に進んで、基準キーより小さいソートキーと基準キーの差分ビット位置によりソートキーを分類し、処理を終了する。ステップＳ５０５の処理の詳細は、後に図７Ａ及び図７Ｂを参照して説明する。
【００６０】
次に図６Ａ及び図６Ｂを参照して本発明の一実施の形態における基準キーより大きいソートキーのグループを分類する処理を説明する。図６Ａ及び図６Ｂに記載するものは、図５に示すステップＳ５０３の処理、及び後述の図１１に示すステップＳ１１０３の処理の詳細な処理フロー例である。
図６Ａは、本発明の一実施の形態における基準キーより大きいソートキーのグループを分類する処理の前段の処理フロー例を説明する図である。
【００６１】
図６Ａに示すように、ステップＳ６０１で、ソートキーに設定されているキーと基準キーに設定されているキーをビット列として比較し、上位０ビット目からみた最初の不一致ビットのビット位置を、差分ビット位置に設定する。ソートキーは、図４に示すステップＳ４０５、あるいは後述の図１１に示すステップＳ１１０１で設定されるものであり、図６Ａ及び図６Ｂに示す分類処理の対象のキーである。
【００６２】
次にステップＳ６０２で差分ビット位置表より、ステップＳ６０１で設定した差分ビット位置の指す親リンクを読み出し、ステップＳ６０３で親リンクは設定済みであるか判定する。親リンクが設定済みでなければ、ステップＳ６０４に進み、差分ビット位置表の、差分ビット位置の指す親リンクにソートキーの読出位置を設定し、ステップＳ６０５において、リンク表の、ソートキーの読出位置の指すリンクに、ソートキーの読出位置を設定して処理を終了する。
【００６３】
差分ビット位置表には、先に述べたように同一の差分ビット位置を有するキーのうち、最大のキーの読出位置が親リンクとして格納されるが、上記ステップＳ６０４の処理は、最初のソートキーを仮の最大値キーとして、ソートキーの読出位置を差分ビット位置表の差分ビット位置の指す親リンクに設定するものである。一旦親リンクが設定済みとなった後、すなわちステップＳ６０３での判定が親リンクは設定済みになると、図６Ｂに示す後段の処理に進み、ソートキーと最大値キーの大小比較による最大値キーの更新が行われ、最終的には同一の差分ビット位置を有するキーのうち、最大のキーの読出位置が親リンクとして差分ビット位置表に格納される。
【００６４】
図６Ｂは、本発明の一実施の形態における基準キーより大きいソートキーのグループを分類する処理の後段の処理フロー例を説明する図である。
図６Ｂに示すように、ステップＳ６０６で、キー表より、親リンクの指すキーを、親ソートキーとして読み出し、ステップＳ６０７において、ソートキーは親ソートキーより大きいか判定する。
ステップＳ６０７でソートキーは親ソートキーより大きいと判定されると、ステップＳ６０８に進み、差分ビット位置表の、差分ビット位置の指す親リンクにソートキーの読出位置を設定し、ステップＳ６０９でリンク表の、ソートキーの読出位置の指すリンクに、ステップＳ６０２で得た親リンクを設定して処理を終了する。
【００６５】
上述のステップＳ６０８の処理は、差分ビット位置表の差分ビット位置の指す親リンクに同一の差分ビット位置を有するキーのうちで最大のキーの読出位置を設定するために、より大きいキーの読出位置で親リンクを更新するものである。そして、ステップＳ６０９の処理は、差分ビット位置表に新たに設定されたソートキーの読出位置の指すリンク表のリンクに、差分ビット位置表に設定されていた親リンクを設定することで、リンク表に、同一の差分ビット位置を有するキーのキー表における読出位置をたどるための情報を保持させるものである。
【００６６】
一方、ステップＳ６０７でソートキーは親ソートキーより大きくないと判定されると、ステップＳ６１０に進み、リンク表より、親リンクの指すリンクを次リンクとして読み出し、ステップＳ６１１で、次リンクと親リンクは同一か判定する。
【００６７】
ステップＳ６１１で次リンクと親リンクは同一であると判定されると、ステップＳ６１２において、リンク表の親リンクの指すリンクに、ソートキーの読出位置を設定する。そして、ステップＳ６１３において、リンク表のソートキーの読出位置の指すリンクに、ソートキーの読出位置を設定して処理を終了する。
【００６８】
一方、ステップＳ６１１で次リンクと親リンクは同一でないと判定されると、ステップＳ６１４に進み、リンク表の親リンクの指すリンクに、ソートキーの読出位置を設定する。そして、ステップＳ６１５において、リンク表のソートキーの読出位置の指すリンクに、ステップＳ６１０で得た次リンクを設定して処理を終了する。
【００６９】
上述のステップＳ６１１の判定は、同一の差分ビット位置を有するキーのうちで分類済みのキーが１つのみであったかの判定と同じである。分類済みのキーが１つのみであればこのキーの読出位置の指すリンク表のリンクにはその読出位置が格納されている。そこで、それをソートキーの読出位置で更新し、ソートキーの読出位置の指すリンク表のリンクにソートキーの読出位置を設定してソートキーが、その時点での最後の分類済みのキーであることを示す。分類済みのキーが２つ以上のときは、ステップＳ６１４とステップＳ６１５の処理により、リンク表で表現される親リンクと次リンクのリンク関係の間に、ソートキーの読出位置を挿入する。
【００７０】
次に図７Ａ及び図７Ｂを参照して本発明の一実施の形態における基準キーより小さいソートキーのグループを分類する処理を説明する。図７Ａ及び図７Ｂに記載するものは、図５に示すステップＳ５０５の処理、及び後述の図９に示すステップＳ９０３の処理の詳細な処理フロー例である。
【００７１】
基準キーより小さいソートキーのグループの分類についての図７Ａ及び図７Ｂの記載と基準キーより大きいソートキーのグループの分類についての図６Ａ及び図６Ｂの記載を比較すると、図７Ａと図６Ａに示す前段の処理フロー例は同一である。また、図７Ｂと図６Ｂに示す後段の処理フロー例も、ソートキーと親ソートキーを比較する図７ＢのステップＳ７０７ではソートキーは親ソートキーより小さいか判定するのに対し、図６ＢのステップＳ６０７ではソートキーは親ソートキーより大きいか判定することで異なるだけで、他のステップは実質的に同一である。
したがって、図７Ａ及び図７Ｂを参照する本発明の一実施の形態における基準キーより小さいソートキーのグループを分類する処理の説明は以上で終了する。
【００７２】
次に、図４に示すステップ４０８の処理の詳細を説明する。
図８は、本発明の一実施の形態における基準キーより小さいソートキーを差分ビット位置順に取り出す処理の処理フロー例を説明する図であり、図４に示すステップ４０８の処理の詳細を説明する図である。
【００７３】
図８に示すように、ステップＳ８０１において、図示しない一次記憶領域である差分ビット位置に、初期値として差分ビット位置表の差分ビット位置、すなわちソート対象のキーが有する可能性のある差分ビット位置の最大値を設定する。図２Ｂの例示では、差分ビット位置の最大値として３が設定される。
【００７４】
ステップＳ８０２において、差分ビット位置表の全ての差分ビット位置のエントリについて処理済みであるか判定し、処理済みであればソート処理を終了し、処理済みでなければステップＳ８０３に進む。
【００７５】
ステップＳ８０３では、差分ビット位置表より、差分ビット位置の指すエントリから親リンクを読み出す。差分ビット位置の指すエントリに親リンクが設定されていれば、この読み出された親リンクは一次記憶領域である親リンクに設定される。すなわち、本実施の態様の説明における「親リンクを読み出す」等の表記は、親リンクを読み出して図示しない一次記憶領域である親リンクに設定することを意味することがある。親リンク以外のものに対しても同様である。
【００７６】
次のステップＳ８０４では、ステップＳ８０３で差分ビット位置の指すエントリから読み出した親リンクは設定済みであるか判定する。設定済みでなければステップＳ８０９に分岐して差分ビット位置から値を１減らしてステップＳ８０２に戻り、一方、設定済みであればステップＳ８０５に進む。図２Ｂの例示では、最大値である差分ビット位置３には親リンクは設定されておらず、差分ビット位置２と差分ビット位置０にそれぞれ親リンクＰ２、Ｐ１が設定されている。
【００７７】
ステップＳ８０５では、キー表より、ステップＳ８０３で設定した親リンク（キー表の読出位置）の指すキーをソート済みキーとして取り出し、その取り出したソート済みキーをソート済みキー表に設定する。先に説明したように、差分ビット位置表にその読出位置が格納されているキーは、同一の差分ビット位置に分類されたキーのうちの最大値キーであるので、ステップＳ８０５でソート済みキー表に設定する。図２Ｂの例示では、差分ビット位置２においては、親リンクＰ２の指すキー表のキー“１０００”をソート済みキーとして取り出し、ソート済みキー表に設定する。差分ビット位置０においては、親リンクＰ１の指すキー表のキー“０１１１”をソート済みキーとして取り出し、ソート済みキー表に設定する。
【００７８】
次にステップＳ８０６で、リンク表より、ステップＳ８０３で設定した親リンクの指すリンクを次リンクとして読み出し、ステップＳ８０７で、差分ビット位置表の、差分ビット位置の指す親リンクを削除してステップＳ８０８に進む。ここで差分ビット位置表の差分ビット位置の指す親リンクを削除するのは、キー表の読出位置が親リンクである最大値キーの分類処理はステップＳ８０５で完了しており、もはや差分ビット位置表上のこの親リンクは必要がないことと、この親リンクが差分ビット位置表に残っていることによる後続の処理への影響を避けるためである。
【００７９】
ステップＳ８０８では、ステップＳ８０６で読み出した次リンクとステップＳ８０３で設定した親リンクが同一であるか判定する。
ステップＳ８０８で次リンクと親リンクが同一であると判定されると、先に説明したステップＳ８０９を経由してステップＳ８０２に戻る。
上述のステップＳ８０２〜ステップＳ８０９のループ処理により、差分ビット位置の降順でソート済みキーの取り出しとソート済みキー表への格納が行われる。より大きい差分ビット位置を有するキーの値がより基準キーの値に近いので、差分ビット位置の降順でソート済みキーを取り出すことにより、降順でソート済みキーが取り出される。
【００８０】
したがって、基準キーより小さいソートキーを格納する第１のソート済みキー表を基準キーより大きいソートキーを格納する第２のソート済みキー表とは別に設け、第１のソート済みキー表のアドレスの大きい方から小さい方に向かって降順でソート済みキーを格納することにより、第１のソート済みキー表からソート済みキーを昇順で読み出すことができる。
また、図５に示すステップＳ５０１の判定結果に応じて基準キーより小さいソートキーと基準キーより大きいソートキーの数をカウントし、ソート済みキー表の、基準キーより小さいソートキーを格納する範囲と基準キーを格納する位置と基準キーより大きいソートキーを格納する範囲を決めることもできる。
【００８１】
さらに、基準キーより小さいソートキーを昇順に取り出すために、差分ビット位置表の親リンクには最小値を設定し、差分ビット位置の昇順でソートキーをソート済みキーとして取り出すこともできる。ただし差分ビット位置の昇順で処理を行う場合には、同一の差分ビット位置の複数のキーがあり、後述の差分ビット位置による細分類を行うと、元の差分ビット位置表のデータが破壊される可能性があるため、別途細分類用の差分ビット位置表を用意する必要がある。
【００８２】
上述のステップＳ８０８で次リンクと親リンクが同一であると判定されるのは、親リンクが格納された差分ビット位置を有するキーが親リンクをキー表の読出位置とするキーしか存在しない場合である。図２Ｂの例示では、リンク表３１１の読出位置６２１がＰ２でリンク６２２がＰ２の場合である。また、図２Ａの例示では、キー群１４２ａがキー“１０００”のみで構成され、キー群１４２ａについての分類処理は行われない場合に相当する。そして、この場合は差分ビット位置表に親リンクが格納された差分ビット位置についての分類処理が終了したことを意味するので、差分ビット位置から値１を減らし、次の差分ビット位置についてのステップＳ８０２〜Ｓ８０８の処理に進む。図２Ａの例示では、差分ビット位置０のキー群１４０ａについての処理が行われる。
【００８３】
一方、ステップＳ８０８で次リンクと親リンクが同一でないと判定されると、ステップＳ８１０に進み、基準キーにソート済みキーを設定する。ソート済みキーは上述のステップＳ８０５で取り出され、ソート済みキー表に設定されたものであり、このソート済みキーを後述の細分類における基準キーとするために、図示しない一時記憶領域である基準キーに設定する。そして、ステップＳ８１１において、同一の差分ビット位置（ステップＳ８０１またはステップＳ８０９で設定されている。）を有する複数のキーを、下位の差分ビット位置によりさらに分類（細分類）する。ステップＳ８１１の処理の詳細については、後に図９を参照して説明する。
【００８４】
ステップＳ８０８で次リンクと親リンクが同一でないと判定される場合は、図２Ｂの例示では、リンク表３１１の読出位置６２１がＰ１でリンク６２２がＰ４の場合である。図２Ａの例示では、キー群１４０ａの複数のキーについて、差分ビット位置による分類１４９ｂが実行される。
ステップＳ８１１の処理では、差分ビット位置表とリンク表が再設定され、ステップＳ８０１に戻る。そして、再設定された差分ビット位置表の親リンクの設定された差分ビット位置についての処理が繰り返される。
【００８５】
上述の処理を、ステップＳ８０２において、差分ビット位置表の全ての差分ビット位置のエントリについて処理済みである、と判定されるまで繰り返し、その判定が得られるとソート対象のキーのソートが完了しているので処理を終了する。
【００８６】
次に図９を参照して、図８に示すステップＳ８１１の処理を詳細に説明する。
図９は、本発明の一実施の形態における同一の差分ビット位置を有する複数のキーをさらに分類する処理の詳細な処理フロー例を説明する図である。
【００８７】
図９に示すように、ステップＳ９０１において、キー表より、次リンクの指すキーをソートキーとして取り出すとともに、次リンクをソートキーの読出位置に設定する。そして、ステップＳ９０２において、リンク表より次リンクの指すリンクを読み出して退避エリアに退避する。ステップＳ９０１における次リンクは、図８に示すステップＳ８０６において、リンク表より読み出された親リンクの指すリンクである。図２Ｂの例の差分ビット位置０を有するキーの分類処理であれば、親リンクがＰ１、次リンクがＰ４、そして次リンクの指すリンクであって退避エリアに退避されるリンクはＰ３である。
【００８８】
ステップＳ９０２において次リンクの指すリンクを退避する理由は、次のステップＳ９０３において、ステップＳ９０１で取り出したソートキーの、図８に示すステップＳ８１１で設定した基準キーに対する差分ビット位置に基づく分類処理が行われ、その結果としてリンク表の次リンクの指すリンクの値が書き換えられるので、あらかじめ退避しておいて、ステップＳ９０３以後の、次リンクの指すリンクを用いた処理を正常に行うためである。
【００８９】
ステップＳ９０３では、図７Ａ及び図７Ｂを参照して詳細に説明した、ソートキーと基準キーの差分ビット位置を得て、差分ビット位置によりソートキーを分類する処理が実行される。
そして、ステップＳ９０４において、次リンクと退避リンクは一致するか判定される。退避リンクが次リンクと一致すれば、同一差分ビット位置を有する分類対象となるキーは残っていないことから処理を終了する。
【００９０】
一方、ステップＳ９０４において、退避リンクが次リンクと一致しないと判定されると、ステップＳ９０５において退避リンクを次リンクに設定してステップＳ９０１に戻り、新しく設定された次リンクをキー表の読出位置とするキーを分類対象のソートキーとして分類処理を継続する。
【００９１】
上述のステップＳ９０１〜Ｓ９０５のループ処理を、退避リンクが次リンクと一致するまで、すなわち分類処理の対象となるキーがなくなるまで繰り返し、分類処理の対象となるキーがなくなると処理を終了する。
【００９２】
次に、図４に示すステップ４１１の処理の詳細を説明する。
図１０は、本発明の一実施の形態における基準キーより大きいソートキーを差分ビット位置順に取り出す処理の処理フロー例を説明する図であり、図４に示すステップ４１１の処理の詳細を説明する図である。
【００９３】
図８に示す、基準キーより小さいソートキーを差分ビット位置順に取り出す処理の処理フロー例と比較すると、図１０に示す基準キーより大きいソートキーを差分ビット位置順に取り出す処理の処理フロー例は、ステップＳ１０１１の同一の差分ビット位置を有する複数キーをさらに分類する処理の詳細が図１１に示すものであることを除いて、図８に示すものと同一である。したがって、図１０に示す処理フロー例のこれ以上の説明は省略する。
【００９４】
図１１は、図１０に示すステップＳ１１０３の処理の詳細を示すものであり、本発明の一実施の形態における同一の差分ビット位置を有する複数のキーをさらに分類する処理の詳細な処理フロー例を説明する図である。
図９と図１１に示す同一の差分ビット位置を有する複数のキーをさらに分類する処理の詳細な処理フロー例を比較すると、同一の差分ビット位置を有する複数のキーをさらに分類する処理について、図９に示すステップＳ９０３の処理が基準キーより小さいソートキーと基準キーの差分ビット位置によりソートキーを分類するものであるのに対して、図１１に示すステップＳ１１０３の処理は基準キーより大きいソートキーと基準キーの差分ビット位置によりソートキーを分類するものであることを除いて、同一である。
そして、図９に示すステップＳ９０３の処理の詳細は図７Ａ及び図７Ｂに示すものであるのに対して、図１１に示すステップＳ１１０３の処理の詳細は図６Ａ及び図６Ｂに示すものである。したがって、図１１に示す処理フロー例のこれ以上の説明は省略する。
【００９５】
図１２は、本発明の一実施の形態におけるキーを降順に取り出すデータの流れを説明する図である。図１２に例として示すものは、図２Ａ及び図２Ｂの例示と同一のキーについて、基準キーより大きいキーと小さいキーのグループへの分類が行われた後の、基準キーより小さいキーのグループからキーを降順に取り出すデータの流れである。
【００９６】
図１２の（ａ）に示すのは、差分ビット位置表３１０ａとリンク表３１１に図２Ｂに示す初期値が設定され、最初のソート済みキー“１０００”が取り出されてソート済みキー表３１３に格納された状態である。
差分ビット位置表３１０ａは、図８に示す処理フロー例のとおり、差分ビット位置の降順でアクセスされる。
【００９７】
先ず矢印６８２ａで示す差分ビット位置６１１ａが２であるエントリに格納された親リンクＰ２が読み出され、矢印６７２ｂで示すように、リンク表３１１の読出位置６２１がＰ２のエントリからリンク６２２であるＰ２が次リンクとして読み出される。そして、親リンクと次リンクはともにＰ２で同一であると判定されるので、矢印６８２ｂで示すキー表３０９の読出位置Ｐ２よりキー“１０００”がソート済みキーとして取り出され、ソート済みキー表３１３のエントリ６４０ｄに格納される。
【００９８】
次に矢印６８０ａで示す差分ビット位置６１１ａが０であるエントリに格納された親リンクＰ１が読み出され、矢印６７１ｂで示すように、リンク表３１１の読出位置６２１がＰ１のエントリからリンク６２２であるＰ４が次リンクとして読み出され、親リンクＰ１と次リンクＰ４は同一ではないと判定される。
【００９９】
図１２の（ｂ）に示すのは、基準キー“１０１０”に対する差分ビット位置０のキーのグループの細分類において、その細分類における基準キー“０１１１”が取り出されてソート済みキー表３１３に格納され、細分類における基準キーにより差分ビット位置表とリンク表が再設定された状態である。
【０１００】
図１２の（ａ）に示す差分ビット位置表３１０ａの差分ビット位置６１１ａが０であるエントリに格納された親リンクＰ１が指す、矢印６８１ｂで示すキー表３０９の読出位置Ｐ１よりキー“０１１１”が、点線の矢印６８１ｄで示すようにソート済みキー６５０ｂに取り出され、矢印６８１ｃで示すように、ソート済みキー表３１３のエントリ６４０ｃに格納される。
【０１０１】
一方、図１２の（ａ）に示すリンク表３１１の、矢印６７４ｃ、６７３ｃで示すリンク関係に基づいて、キー表３０９から読出位置Ｐ３、Ｐ４のキーが読み出され、ソート済みキー６５０ｂを基準キーとして差分ビット位置が再計算され、差分ビット位置表３１０ａとリンク表３１１が再設定される
【０１０２】
点線の矢印６６１ａで示すように、キー表３０９の読出位置Ｐ３に格納されたキー“００１０”の差分ビット位置は１であることから、差分ビット位置表３１０ａの差分ビット位置６１１ａが１であるエントリにはＰ３が設定される。同様に、点線の矢印６６３ａで示すように、キー表３０９の読出位置Ｐ４に格納されたキー“０１１０”の差分ビット位置は３であることから、差分ビット位置表３１０ａの差分ビット位置６１１ａが３であるエントリにはＰ４が設定される。
【０１０３】
また、差分ビット位置が１であるキーも差分ビット位置が３であるキーもそれぞれ１つであることから、矢印６７３ｂ及び６７４ｂで示すように、リンク表３１１の読出位置６２１がＰ３、Ｐ４であるエントリのリンク６２２には、それぞれＰ３、Ｐ４が設定されている。
【０１０４】
図１２の（ｃ）に示すのは、キー表３０９の読出位置６０１がＰ３とＰ４であるエントリに格納されたキーがソート済みキー表３１３に格納され、基準キーより小さいキーのグループのソートが完了した状態である。
【０１０５】
先ず矢印６８３ａで示す差分ビット位置６１１ａが３であるエントリに格納された親リンクＰ４が読み出され、矢印６７４ｂで示すように、リンク表３１１の読出位置６２１がＰ４のエントリからリンク６２２であるＰ４が次リンクとして読み出される。そして、親リンクと次リンクはともにＰ４で同一であると判定されるので、矢印６８４ｂで示すキー表３０９の読出位置Ｐ４よりキー“０１１０”がソート済みキーとして取り出され、ソート済みキー表３１３のエントリ６４０ｂに格納される。
【０１０６】
次に矢印６８１ａで示す差分ビット位置６１１ａが１であるエントリに格納された親リンクＰ３が読み出され、矢印６７３ｂで示すように、リンク表３１１の読出位置６２１がＰ３のエントリからリンク６２２であるＰ３が次リンクとして読み出される。そして、親リンクと次リンクはともにＰ３で同一であると判定されるので、矢印６８３ｂで示すキー表３０９の読出位置Ｐ３よりキー“００１０”がソート済みキーとして取り出され、ソート済みキー表３１３のエントリ６４０ａに格納される。
そして、差分ビット位置６１１ａが０であるエントリには親リンクは設定されていないので、基準キーより小さいキーのグループのソートは完了する。
【０１０７】
以上本発明を実施するための形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
また、本発明のビット列データソート装置が、図２Ｂに例示するデータ構造を有するデータを記憶する記憶手段と図４に示す処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。
したがって、上記プログラム、及びプログラムを記録したコンピュータ読み取り可能な記録媒体は、本発明の実施の形態に含まれる。
以上詳細に説明した本発明が提供する新しいビット列データソート手法を用いることにより、より高速なビット列データのソートを行うことが可能となる。
【符号の説明】
【０１０８】
１００                            キー列
１３０                            ソート済みキー列
１４９ａ、１４９ｂ                差分ビット位置による分類
２００                            ビット列データソート装置
２０５                            グループ分け手段
２１０                            差分ビット位置計算手段
２２０                            差分ビット位置分類手段
２３０                            ソート済みキー出力手段
２４０                            制御手段
３０１                            データ処理装置
３０２                            中央処理装置
３０３                            キャッシュメモリ
３０４                            バス
３０５                            主記憶装置
３０６                            外部記憶装置
３０７                            通信装置
３０８                            データ格納装置
３０９                            キー表
３１０ａ、３１０ｂ                差分ビット位置表
３１１                            リンク表
３１３                            ソート済みキー表
【図１】
2011048801.tif 000003
【図２Ａ】
2011048801.tif 000004
【図２Ｂ】
2011048801.tif 000005
【図２Ｃ】
2011048801.tif 000006
【図３】
2011048801.tif 000007
【図４】
2011048801.tif 000008
【図５】
2011048801.tif 000009
【図６Ａ】
2011048801.tif 000010
【図６Ｂ】
2011048801.tif 000011
【図７Ａ】
2011048801.tif 000012
【図７Ｂ】
2011048801.tif 000013
【図８】
2011048801.tif 000014
【図９】
2011048801.tif 000015
【図１０】
2011048801.tif 000016
【図１１】
2011048801.tif 000017
【図１２】
2011048801.tif 000018