【手続補正書】
【提出日】平成24年11月28日(2012.11.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１
【補正方法】変更
【補正の内容】
【請求項１】
ビット列で表されるソート対象のキーのソート処理を行うビット列データソート装置において、
前記ソート対象のキーを記憶するソート対象キー記憶手段と、
前記ソート対象のキー全体のうちの任意のキーである基準キーとソート対象キー記憶手段に記憶された該基準キー以外のキーとの大小比較により該基準キーより小さいキーのグループと大きいキーのグループのグループ分けを行うグループ分け手段と、
前記ソート対象キー記憶手段に記憶された前記ソート処理を構成する分類処理の分類対象である前記キーと、該分類対象であるキーのうち基準となるキーと、のビット列比較により、最初に異なるビット値となる差分ビット位置を求める差分ビット位置計算手段と、
前記差分ビット位置計算手段で求めた差分ビット位置毎に該差分ビット位置を有するキーの識別情報を記憶する分類対象キー差分ビット位置記憶手段と、
前記差分ビット位置計算手段で求めた前記差分ビット位置毎に該差分ビット位置を有するキーの識別情報を前記分類対象キー差分ビット位置記憶手段に書き込むことにより、前記分類対象であるキーを同一の差分ビット位置を有する組に分類する差分ビット位置分類手段と、
前記差分ビット位置分類手段で分類された同一の差分ビット位置を有するキーが１つの場合はそのキーを、同一の差分ビット位置を有するキーが複数の場合はそのうちの次の分類処理において基準となるキーをソート済みキーとして出力するソート済みキー出力手段と、
前記グループ分け手段、前記差分ビット位置計算手段、前記差分ビット位置分類手段及び前記ソート済みキー出力手段を制御する制御手段と、
を備え、
前記制御手段は、
最初の前記分類処理において、
前記グループ分け手段が、前記基準キーと前記基準キー以外のキーとの大小比較により該基準キーより小さいキーのグループと大きいキーのグループのグループ分けを行い、
前記差分ビット位置計算手段が、前記基準キーと該基準キー以外のキーの差分ビット位置を求め、
前記差分ビット位置分類手段が、前記基準キーより小さいキーのグループと大きいキーのグループ毎に、前記差分ビット位置計算手段が求めた前記差分ビット位置毎に該差分ビット位置を有するキーの識別情報を前記分類対象キー差分ビット位置記憶手段に書き込み、
以後の前記分類処理において、前記基準キーより小さいキーのグループと大きいキーのグループ毎に、
前記差分ビット位置計算手段が、前記差分ビット位置分類手段で分類された同一の差分ビット位置を有するキーを複数含むキーの組を前記分類対象として前記次の分類処理において基準となるキーに対する差分ビット位置を求めることを繰り返し、
前記差分ビット位置分類手段が、前記分類対象としたキーの組に含まれる複数のキーを前記差分ビット位置計算手段が求めた差分ビット位置毎に同一の差分ビット位置を有する組にさらに分類することを繰り返し、
前記ソート済みキー出力手段が、前記差分ビット位置分類手段が前記差分ビット位置毎に同一の差分ビット位置を有する組に分類するたびに、該同一の差分ビット位置を有するキーが１つの場合のキー及び前記基準となるキーをソート済みキーとして出力するために、
前記グループ分け手段、前記差分ビット位置計算手段、前記差分ビット位置分類手段及び前記ソート済みキー出力手段を制御すること、
を特徴とするビット列データソート装置。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項５
【補正方法】変更
【補正の内容】
【請求項５】
ビット列で表されるソート対象のキーのソート処理を行うビット列データソート方法において、
前記ソート対象のキーを記憶するソート対象キー記憶手段に前記ソート対象のキーを記憶するソート対象キー記憶ステップと、
前記ソート対象のキー全体のうちの任意のキーである基準キーとソート対象キー記憶手段に記憶された該基準キー以外のキーとの大小比較により該基準キーより小さいキーのグループと大きいキーのグループのグループ分けを行うグループ分けステップと、
前記ソート対象キー記憶手段に記憶された前記ソート処理を構成する分類処理の分類対象である前記キーと、該分類対象であるキーのうち基準となるキーと、のビット列比較により、最初に異なるビット値となる差分ビット位置を求める差分ビット位置計算ステップと、
前記差分ビット位置計算ステップで求めた差分ビット位置毎に、分類対象キー差分ビット位置記憶手段に該差分ビット位置を有するキーの識別情報を書き込むことにより、前記分類対象であるキーを同一の差分ビット位置を有する組に分類する差分ビット位置分類ステップと、
前記差分ビット位置分類ステップで分類された同一の差分ビット位置を有するキーが１つの場合はそのキーを、同一の差分ビット位置を有するキーが複数の場合はそのうちの次の分類処理において基準となるキーをソート済みキーとして出力するソート済みキー出力ステップと、
前記グループ分けステップ、前記差分ビット位置計算ステップ、前記差分ビット位置分類ステップ及び前記ソート済みキー出力ステップを制御する制御ステップと、
を備え、
前記制御ステップは、
最初の前記分類処理において、
前記グループ分けステップが、前記基準キーと前記基準キー以外のキーとの大小比較により該基準キーより小さいキーのグループと大きいキーのグループのグループ分けを行い、
前記差分ビット位置計算ステップが、前記基準キーと該基準キー以外のキーの差分ビット位置を求め、
前記差分ビット位置分類ステップが、前記基準キーより小さいキーのグループと大きいキーのグループ毎に、前記差分ビット位置計算ステップで求めた前記差分ビット位置毎に該差分ビット位置を有するキーの識別情報を前記分類対象キー差分ビット位置記憶手段に書き込み、
以後の前記分類処理において、前記基準キーより小さいキーのグループと大きいキーのグループ毎に、
前記差分ビット位置計算ステップが、前記差分ビット位置分類ステップで分類された同一の差分ビット位置を有するキーを複数含むキーの組を前記分類対象として前記次の分類処理において基準となるキーに対する差分ビット位置を求めることを繰り返し、
前記差分ビット位置分類ステップが、前記分類対象としたキーの組に含まれる複数のキーを前記差分ビット位置計算ステップで求めた差分ビット位置毎に同一の差分ビット位置を有する組にさらに分類することを繰り返し、
前記ソート済みキー出力ステップが、前記差分ビット位置分類ステップが前記差分ビット位置毎に同一の差分ビット位置を有する組に分類するたびに、該同一の差分ビット位置を有するキーが１つの場合のキー及び前記基準となるキーをソート済みキーとして出力するために、
前記グループ分けステップ、前記差分ビット位置計算ステップ、前記差分ビット位置分類ステップ及び前記ソート済みキー出力ステップを制御する、
ことを特徴とするビット列データソート方法。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
差分ビット位置表３１０ｂは、基準キーより大であって基準キーに対する同一の差分ビット位置を有するキーのうち、最小のキーの読出位置６０１を親リンク６１２ｂとして差分ビット位置６１１ｂ毎に格納するものである。図２Ｂの例示では、点線の矢印６６１ａで示すように、基準キー“１０１０”との差分ビット位置が１であるキーはキー“１１１１”だけであるので、キー“１１１１”の読出位置Ｐ５が差分ビット位置表３１０ｂの差分ビット位置６１１ｂが１である位置に格納されている。また、点線の矢印６６３ａで示すように、基準キー“１０１０”との差分ビット位置が３であるキーはキー“１０１１”だけであるので、キー“１０１１”
の読出位置Ｐ６が差分ビット位置表３１０ｂの差分ビット位置６１１ｂが３である位置に格納されている。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
同様に、差分ビット位置表３１０ｂからリンク表３１１への点線の矢印６７６ｂで示すように、基準キーとの同一の差分ビット位置３を有するキーの最小値キーの読出位置Ｐ６に対して、リンク表３１１の読出位置Ｐ６には、リンク表３１１の読出位置Ｐ６と同一の値のキー表３０９の読出位置Ｐ６が格納されている。これは、キー表３０９の読出位置Ｐ６のキー“１０１１”が基準キー“１０１０”との差分ビット位置が３であるキーの最小のキーであるとともに、唯一のものであることを示している。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた主記憶装置３０５の一時記憶領域が用いられることは当然である。そして、以下の説明においては、一時記憶領域に格納されるあるいは設定される値を一時記憶領域の名前で呼ぶことがある。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４８
【補正方法】変更
【補正の内容】
【００４８】
まず、ステップＳ４０１において、キー表の先頭位置をキー表の読出位置（以下、単に読出位置ということがある。）に設定する。ここでいう「キー表の読出位置」は、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の１つである。以下の説明では、「キー表の先頭位置をキー表の読出位置に設定する。」のように、「キー表の読出位置」が図示しない一時記憶領域であることを省略して述べることがある。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
図８に示すように、ステップＳ８０１において、図示しない一時記憶領域である差分ビット位置に、初期値として差分ビット位置表の差分ビット位置、すなわちソート対象のキーが有する可能性のある差分ビット位置の最大値を設定する。図２Ｂの例示では、差分ビット位置の最大値として３が設定される。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００７５
【補正方法】変更
【補正の内容】
【００７５】
ステップＳ８０３では、差分ビット位置表より、差分ビット位置の指すエントリから親リンクを読み出す。差分ビット位置の指すエントリに親リンクが設定されていれば、この読み出された親リンクは一時記憶領域である親リンクに設定される。すなわち、本実施の態様の説明における「親リンクを読み出す」等の表記は、親リンクを読み出して図示しない一時記憶領域である親リンクに設定することを意味することがある。親リンク以外のものに対しても同様である。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００８１
【補正方法】変更
【補正の内容】
【００８１】
さらに、基準キーより小さいソートキーを昇順に取り出すために、差分ビット位置表の親リンクには最小値キーの読出位置を設定し、差分ビット位置の昇順でソートキーをソート済みキーとして取り出すこともできる。ただし差分ビット位置の昇順で処理を行う場合には、同一の差分ビット位置の複数のキーがあり、後述の差分ビット位置による細分類を行うと、元の差分ビット位置表のデータが破壊される可能性があるため、別途細分類用の差分ビット位置表を用意する必要がある。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００９４
【補正方法】変更
【補正の内容】
【００９４】
図１１は、図１０に示すステップＳ１０１１の処理の詳細を示すものであり、本発明の一実施の形態における同一の差分ビット位置を有する複数のキーをさらに分類する処理の詳細な処理フロー例を説明する図である。
図９と図１１に示す同一の差分ビット位置を有する複数のキーをさらに分類する処理の詳細な処理フロー例を比較すると、同一の差分ビット位置を有する複数のキーをさらに分類する処理について、図９に示すステップＳ９０３の処理が基準キーより小さいソートキーと基準キーの差分ビット位置によりソートキーを分類するものであるのに対して、図１１に示すステップＳ１１０３の処理は基準キーより大きいソートキーと基準キーの差分ビット位置によりソートキーを分類するものであることを除いて、同一である。
そして、図９に示すステップＳ９０３の処理の詳細は図７Ａ及び図７Ｂに示すものであるのに対して、図１１に示すステップＳ１１０３の処理の詳細は図６Ａ及び図６Ｂに示すものである。したがって、図１１に示す処理フロー例のこれ以上の説明は省略する。