【手続補正書】
【提出日】平成24年10月29日(2012.10.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項５
【補正方法】変更
【補正の内容】
【請求項５】
請求項４に記載のビット列データソート装置において、
前記下位ｎビットソート手段は、親リンクが前記差分ビット位置表に格納された差分ビット位置毎に、前記差分ビット位置表の当該差分ビット位置に格納された親リンクと該親リンクの指す前記ソート対象キー記憶手段に記憶されたキーの当該差分ビット位置の下位ｎビットの組、及び該親リンクと同一の差分ビット位置を有する全てのキーのリンクと該リンクの指す前記ソート対象キー記憶手段に記憶されたキーの当該差分ビット位置の下位ｎビットの組をソート対象データとし、前記各組のキーの下位ｎビットをソートキーとして、前記ソート対象データをソートすることを前記差分ビット位置順に実行するものであり、
前記ソート済みキー出力手段は、差分ビット位置順に、前記下位ｎビットソート手段によりソートされたソート対象データの前記親リンクあるいはリンクの指す前記ソート対象キー記憶手段からキーを読み出してソート済みキーとして出力する、
ことを特徴とするビット列データソート装置。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
請求項９に記載のビット列データソート方法において、
前記下位ｎビットソートステップは、親リンクが前記差分ビット位置表に格納された差分ビット位置毎に、前記差分ビット位置表の当該差分ビット位置に格納された親リンクと該親リンクの指す前記ソート対象キー記憶手段に記憶されたキーの当該差分ビット位置の下位ｎビットの組、及び該親リンクと同一の差分ビット位置を有する全てのキーのリンクと該リンクの指す前記ソート対象キー記憶手段に記憶されたキーの当該差分ビット位置の下位ｎビットの組をソート対象データとし、前記各組のキーの下位ｎビットをソートキーとして、前記ソート対象データをソートすることを前記差分ビット位置順に実行し、
前記ソート済みキー出力ステップは、差分ビット位置順に、前記下位ｎビットソートステップにおいてソートされたソート対象データの前記リンクの指す前記ソート対象キー記憶手段からキーを読み出してソート済みキーとして出力する、
ことを特徴とするビット列データソート方法。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
最小値キー１４８ａとの差分ビット位置が０であるキー群１４０ａにはキーが複数含まれているので、図の点線の矢印の組１５０ａに示すように、差分ビット位置の下位ｎビットによるソート１４９ｂにおけるソートの対象となる。差分ビット位置の下位ｎビットによるソート１４９ｂにおけるソートでは、差分ビット位置による分類１４９ａで分類に用いられた差分ビット位置０の下位ビット、図２Ａの例では１ビット目から３ビット目までの３ビットを切り出してソートする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
差分ビット位置表３１０は、最小値キーに対する同一の差分ビット位置を有するキーのうち、キー表３０９から最初に読み出されたキーの読出位置６０１が親リンク６１２として差分ビット位置６１１毎に格納されている。図２Ｂの例示では、点線の矢印６６０ａで示すように、最小値キー“０００１”との差分ビット位置が０であるキー“１１１１”、“１０１０”、“１１１０”のうち最初に読み出されるキー“１１１１”の読出位置Ｐ１が差分ビット位置表３１０の差分ビット位置６１１が０である位置に格納されている。また、点線の矢印６６２ａで示すように、最小値キー“０００１”との差分ビット位置が２であるキーはキー“００１１”だけであるので、キー“００１１”の読出位置Ｐ２が差分ビット位置表３１０の差分ビット位置６１１が２である位置に格納されている。なお、親リンクに設定される読出位置は、上述のように最初に読み出されるキーの読出位置に限ることはない。後述のリンク表３１１に格納されたリンク関係と併せて、最小値キーに対して同一の差分ビット位置を有するキーにアクセスすることができればよい。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
差分ビット位置表３１０からリンク表３１１への点線の矢印６７１ｂで示すように、同一の差分ビット位置０を有する親リンクのキーの読出位置Ｐ１に対して、その読出位置Ｐ１を読出位置６２１とするリンク表３１１の読出位置（以下、リンク表３１１の読出位置Ｐ１のようにいう。）に、最小値キー“０００１”に対して差分ビット位置０を有する親リンクのキー“１１１１”と同一の差分ビット位置０を有するキー“１１１０”のキー表３０９の読出位置Ｐ４が格納されている。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４１
【補正方法】変更
【補正の内容】
【００４１】
まず、ステップＳ４０１において、キー表の先頭位置をキー表の読出位置（以下、単に読出位置ということがある。）に設定する。ここでいう「キー表の読出位置」は、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の１つである。以下の説明では、「キー表の先頭位置をキー表の読出位置に設定する。」のように、「キー表の読出位置」が図示しない一時記憶領域であることを省略して述べることがある。
上記の設定により、図２Ｂの例示では、キー表の読出位置にＰ０が設定される。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００４２
【補正方法】変更
【補正の内容】
【００４２】
次にステップＳ４０２において、キー表より、先頭位置の指すキーを最小値キーとして取り出す。ここでいう「最小値キーとして取り出す」は、図示しない一時記憶領域である最小値キーに設定する、の意味である。以下においても、同様な表記を用いる場合がある。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
ステップＳ４０８においては、図示しない一時記憶領域である差分ビット位置に、初期値として差分ビット位置表の差分ビット位置、すなわちソート対象のキーが有する可能性のある差分ビット位置の最大値を設定する。図２Ｂの例示では、差分ビット位置の最大値として３が設定される。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００４９
【補正方法】変更
【補正の内容】
【００４９】
ステップＳ４１０では、差分ビット位置表より、差分ビット位置の指すエントリから親リンクを読み出す。差分ビット位置の指すエントリに親リンクが格納されていれば、この読み出された親リンクは一時記憶領域である親リンクに設定される。すなわち、本実施の態様の説明における「親リンクを読み出す」等の表記は、親リンクを読み出して図示しない一時記憶領域である親リンクに設定することを意味することがある。親リンク以外のものに対しても同様である。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
ステップＳ４１３ａでは、リンク表より、ステップＳ４１０で読み出した親リンク（キー表の読出位置）の指すリンク列に含まれるキーをソートし、ソート済みキー表に設定してステップＳ４１６に進む。ステップＳ４１３ａの処理の詳細は、後に図５Ｂを参照して説明する。また、親リンクの指すリンク列に含まれるキーについても後に説明する。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正の内容】
【００６５】
図５Ｂは、図４Ｂに示すステップＳ４１３ａの処理である、本発明の一実施の形態における各差分ビット位置に分類されたキーをソートし、ソート済みキーとして出力する処理フロー例を説明する図である。本実施の形態においては、リンク表に基づいて親リンクの指すリンク列に含まれるキーを取り出してソートし、ソート済みキー表に設定する。