図面 (/)

技術 同値キーが存在するデータのソート方式

出願人 日本電気株式会社
発明者 上田洋一
出願日 1994年10月31日 (26年3ヶ月経過) 出願番号 1994-290451
公開日 1996年5月21日 (24年9ヶ月経過) 公開番号 1996-129478
状態 特許登録済
技術分野 データの分類、組合せ
主要キーワード 磁気テープ中 対戦情報 レコードイメージ 置換方式 キー順 キーレコード レコードポインタ 管理テーブルエントリ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1996年5月21日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (12)

目的

同値キーレコードが存在するレコードソートにおいて、同値キーレコードの削除無しに、キー比較の回数を極力減らして、性能の向上を図る。

構成

ソート時の対戦に参加しているレコード毎の情報を設定する対戦管理テーブル10に各レコード毎の同値キーフラグを設け、対戦手段2は、同値キーレコード検出時、勝者としたレコードに対応する同値キーフラグをONに設定する。この同値キーフラグは中間結果であるストリングへの出力時に制御データとしてレコードに付加する。マージ手段4は、ストリングのマージ時、対戦の優勝者の属するストリングから次のレコードを得たとき、前記優勝者のレコードに付加されていた同値キーフラグがONであれば、前記取得した次のレコードは対戦に参加させることなく直ちにストリングに出力する。

概要

背景

メモリ入り切らない大量のレコードソートする場合、レコードを1件ずつメモリに読み込み、読み込んだレコードを読み込み済みのレコード群対戦させ、対戦の優勝者を順次ワークファイルに出力していって中間結果であるストリング(部分的にソート済みレコード列)を複数作成していくプリソートフェーズを実施し、次いで、ワークファイル内の複数のストリングを繰り返しマージしていって1本のストリングにまとめて出力するマージフェーズを行うというように、前半部分のプリソートフェーズと後半部分のマージフェーズとに分けてソートを行うソート方式が一般的である。

ところで、このようなソート方式では、レコード件数が増加するに伴い、レコードの対戦の回数、従ってキー比較処理呼び出す回数が急速に増加し、中央処理装置を長時間使用するようになり、性能の低下を招くという問題点がある。そこで、同一のキー値同値キー)を持つレコードが多数存在するレコードのソートにおいて、キー比較の回数を減らし、中央処理装置の使用時間を短縮して性能の向上を図るため、従来より以下のようなソート方式が提唱されている。

(1)従来技術1
レコードのキー比較時に同値キーであった場合に、レコードの単一化を行い、同値キーレコードを1つのレコードにまとめるソート方式(例えば特開平2−259827号公報)。
(2)従来技術2
同値キーレコード数のカウンタを設け、レコードのキー比較時に、同値キーであった場合、同値キーレコード数カウンタ計数処理を行い、出力結果として、レコードのキー部分と、制御情報として、計数された同値キーレコード数を付加するソート方式(例えば特開平1−171021号公報)。

概要

同値キーレコードが存在するレコードのソートにおいて、同値キーレコードの削除無しに、キー比較の回数を極力減らして、性能の向上を図る。

ソート時の対戦に参加しているレコード毎の情報を設定する対戦管理テーブル10に各レコード毎の同値キーフラグを設け、対戦手段2は、同値キーレコード検出時、勝者としたレコードに対応する同値キーフラグをONに設定する。この同値キーフラグは中間結果であるストリングへの出力時に制御データとしてレコードに付加する。マージ手段4は、ストリングのマージ時、対戦の優勝者の属するストリングから次のレコードを得たとき、前記優勝者のレコードに付加されていた同値キーフラグがONであれば、前記取得した次のレコードは対戦に参加させることなく直ちにストリングに出力する。

目的

本発明は、上記問題点に鑑み、ソート処理過程における同値キーレコード同士の対戦を極力抑え得るようにすることにより、同値キーレコードを削除しなくてもキー比較回数を削減できるようにし、同値キーレコードが数多く存在するレコードを高速にソートすることができるようにすることを目的とする。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

レコードを1件ずつメモリに読み込み、読み込んだレコードを読み込み済みのレコード群対戦させ、対戦の優勝者を順次ワークファイルに出力していって中間結果であるストリングを複数作成していくプリソートフェーズを実施し、次いで、ワークファイル内の複数のストリングのレコード同士をストリングの先頭より順に対戦させ、対戦の優勝者を1本のストリングにまとめて出力するマージフェーズを実施するソート方式において、前記プリソートフェーズにおいて、各ストリングに出力するレコードに、当該レコードの後続のレコードが同値キーレコードであるか否かを示す同値キーフラグを付加するプリソート手段と、前記マージフェーズにおいて、対戦の優勝者レコードをストリングに出力した後、その優勝者レコードの属するストリングから次のレコードを得たときに、前記出力した優勝者レコードに付加されていた同値キーフラグをチェックし、該同値キーフラグが後続のレコードが同値キーレコードであることを示すときは、前記取得した次のレコードは対戦に参加させることなく直ちにストリングに出力するマージ手段とを備えることを特徴とする同値キーが存在するデータのソート方式。

請求項2

前記マージ手段は、最終マージ以外の場合のストリングにレコードを出力する際、前記プリソートフェーズにおける場合と同様に、当該レコードの後続のレコードが同値キーレコードであるか否かを示す同値キーフラグを付加するようにしたことを特徴とする請求項1記載の同値キーが存在するデータのソート方式。

請求項3

メモリに入り切らない大量のレコードを、プリソートフェーズとマージフェーズとに分けてソートする方式において、ソート対象レコードを格納するプリソート用レコードエリアと、該プリソート用レコードエリアに格納されたソート対象レコードのレコードポインタおよび同値キーフラグを、各レコード対応に格納する対戦管理テーブルと、キー比較手段と、対戦に参加している各レコードの前記プリソート用レコードエリア内アドレスであるレコードポインタとOFF状態初期化した同値キーフラグとを前記対戦管理テーブルに設定し、前記キー比較手段を用いてレコードの対戦を行って優勝者レコードを決定すると共に、同値キーレコード同士の対戦があった場合には、その何れか一方を勝者にしてその勝者に対応する前記対戦管理テーブルの同値キーフラグをONにする対戦手段と、外部より入力されたソート対象レコードを1件ずつ前記プリソート用レコードエリアへ読み込みながら前記対戦手段を呼び出して、前記読み込んだレコードを、前記プリソート用レコードエリア内に既に存在するレコード群と対戦させ、前記対戦手段が決定した対戦の優勝者レコードを、そのレコードに対応する前記対戦管理テーブルの同値キーフラグを付加して、前記ソートワークファイルへ順次出力していくことにより、ソート中間結果としてストリングと呼ぶ順序付けられたレコード列を作成するプリソート手段と、マージ対戦対象のレコードをそれに付加された同値キーフラグとともに格納するマージ対戦用レコードエリアと、マージ対戦対象のレコードの前記マージ対戦用レコードエリア内アドレスであるレコードポインタおよび同値キーフラグを、各レコード対応に格納するマージ対戦管理テーブルと、マージ対戦に参加している各レコードの前記マージ対戦用レコードエリア内アドレスであるレコードポインタとOFF状態に初期化した同値キーフラグとを前記マージ対戦管理テーブルに設定し、前記キー比較手段を用いてレコードの対戦を行って優勝者レコードを決定すると共に、同値キーレコード同士の対戦があった場合には、その何れか一方を勝者にしてその勝者に対応する前記マージ対戦管理テーブルの同値キーフラグをONにするマージ対戦手段と、前記ソートワークファイル内の複数のストリングを繰り返しマージしていって1本のストリングにまとめるソート処理を制御する手段であって、幾つかのストリングから1本のストリングを生成する1回のマージ処理において、今回のマージ対象のストリングの先頭レコードを順次前記マージ対戦用レコードエリアに読み込んで前記マージ対戦手段を呼び出してレコードの対戦を行わせ、前記マージ対戦手段が優勝者レコードを決定したとき、その優勝者レコードを出力レコードと決定して、該決定した出力レコードに付加されている同値キーフラグを参照し、出力レコードに付加されている同値キーフラグがONであれば、その出力レコードをそれに元々付加されていた同値キーフラグを付加してストリングに出力し且つその出力レコードの属するストリングから読み込んだ次のレコードを対戦に参加させることなく出力レコードに決定する処理を、付加されている同値キーフラグがOFFの出力レコードを読み込むまで繰り返し、出力レコードに付加されている同値キーフラグがOFFであったとき、および、その同値キーフラグがONであって前記処理が行われて同値キーフラグがOFFの出力レコードが読み込まれたときは、前記マージ対戦手段が決定した優勝者レコードに対応する前記マージ対戦管理テーブルの同値キーフラグを参照し、該同値キーフラグがONであれば、ONにした同値キーフラグを付加した出力レコードをストリングに出力し、OFFであれば、その出力レコードにOFFの同値キーフラグを付加してストリングに出力するマージ手段とを備えることを特徴とする同値キーが存在するデータのソート方式。

請求項4

請求項3記載の同値キーが存在するデータのソート方式において、対戦で勝ち上がった方のレコードの情報を一時的に設定しておくための作業領域である勝ち上がりレコードエントリを備え、前記対戦手段はレコード対戦方式としてトーナメント置換方式を用い、対戦は2進木構造で定義される対戦構造の下位から上位に向けて勝ち抜き戦形式で行っていき、対戦構造の各ノード毎に、前記対戦管理テーブルのエントリを対応させ、該エントリには対戦で負けた方のレコードの情報を設定し、対戦の開始時には、読み込んだレコードの情報を前記勝ち上がりレコードエントリに設定し、その後勝ち上がりレコードエントリのレコードと対戦管理テーブルのレコード群とを、対戦構造に従って順次対戦させていき、前記対戦管理テーブル側のレコードが勝った場合は、前記勝ち上がりレコードエントリと対戦管理テーブル側のレコードの対戦管理テーブルエントリとを交換し、以下同様に対戦を続け、対戦終了時に、前記勝ち上がりレコードエントリに設定されているレコードを対戦の優勝者に決定し、更に、同値キーレコードの対戦があった場合、前記勝ち上がりレコードエントリに設定されているレコードを勝者と決定し、前記勝ち上がりレコードエントリの同値キーフラグをONに設定することを特徴とする同値キーが存在するデータのソート方式。

請求項5

請求項4記載の同値キーが存在するデータのソート方式において、前記対戦手段による対戦の優勝者,優勝者の同値キーフラグ,次に入力したレコードの対戦開始エントリを含む対戦情報を一時的に記憶しておくための対戦結果保存手段を備え、前記対戦手段は1回の対戦が終了して優勝者が決定した時点で、前記対戦結果保存手段に対戦情報を保存すると共に、対戦を行うにあたり、前記対戦結果保存手段に保存されている前回の対戦での優勝者レコードと今回入力されたレコードとのキーを比較し、同値キーでなければ、前記対戦結果保存手段に保存されている対戦開始エントリからトーナメントの対戦を開始し、同値キーであれば、トーナメントの対戦はスキップし、入力されたレコードを直ちに今回の対戦の優勝者と決定すると共に、前記対戦結果保存手段により保存されている前回の優勝者の同値キーフラグの値を、今回の対戦の優勝者の同値キーフラグとして引き継いだ後、前記対戦結果保存手段により保存されている前回の優勝者の同値キーフラグはONに設定し、前記プリソート手段は、前記対戦手段による1回の対戦を行って優勝者を決定した時点で、前記対戦結果保存手段により保存されている前回の対戦での優勝者およびその同値キーフラグを出力することを特徴とする同値キーが存在するデータのソート方式。

請求項6

請求項3記載の同値キーが存在するデータのソート方式において、前記マージ対戦手段による対戦で勝ち上がった方のレコードの情報を一時的に設定しておくための作業領域である勝ち上がりレコードエントリを備え、前記マージ対戦手段はレコード対戦方式としてトーナメント置換方式を用い、対戦は2進木構造で定義される対戦構造の下位から上位に向けて勝ち抜き戦形式で行っていき、対戦構造の各ノード毎に、前記マージ対戦管理テーブルのエントリを対応させ、該エントリには対戦で負けた方のレコードの情報を設定し、対戦の開始時には、読み込んだレコードの情報を前記勝ち上がりレコードエントリに設定し、その後勝ち上がりレコードエントリのレコードとマージ対戦管理テーブルのレコード群とを、対戦構造に従って順次対戦させていき、前記マージ対戦管理テーブル側のレコードが勝った場合は、前記勝ち上がりレコードエントリとマージ対戦管理テーブル側のレコードのマージ対戦管理テーブルエントリとを交換し、以下同様に対戦を続け、対戦終了時に、前記勝ち上がりレコードエントリに設定されているレコードを対戦の優勝者に決定し、更に、同値キーレコードの対戦があった場合、前記勝ち上がりレコードエントリに設定されているレコードを勝者と決定し、前記勝ち上がりレコードエントリの同値キーフラグをONに設定することを特徴とする同値キーが存在するデータのソート方式。

請求項7

請求項6記載の同値キーが存在するデータのソート方式において、前記マージ対戦手段による対戦の優勝者,優勝者の同値キーフラグ,次に入力したレコードの対戦開始エントリを含む対戦情報を一時的に記憶しておくための対戦結果保存手段を備え、前記マージ対戦手段は1回の対戦が終了して優勝者が決定した時点で、前記対戦結果保存手段に対戦情報を保存すると共に、対戦を行うにあたり、前記対戦結果保存手段に保存されている前回の対戦での優勝者レコードと今回入力されたレコードとのキーを比較し、同値キーでなければ、前記対戦結果保存手段に保存されている対戦開始エントリからトーナメントの対戦を開始し、同値キーであれば、トーナメントの対戦はスキップし、入力されたレコードを直ちに今回の対戦の優勝者と決定するとともに、前記対戦結果保存手段により保存されている前回の優勝者の同値キーフラグの値を、今回の対戦の優勝者の同値キーフラグとして引き継いだ後、前記対戦結果保存手段により保存されている前回の優勝者の同値キーフラグはONに設定し、前記マージ手段は、前記マージ対戦手段による1回の対戦を行って優勝者を決定した時点で、前記対戦結果保存手段により保存されている前回の対戦での優勝者およびその同値キーフラグとを出力することを特徴とする同値キーが存在するデータのソート方式。

請求項8

請求項3記載の同値キーが存在するデータのソート方式において、前記対戦手段はレコード対戦方式としてバイナリインサーション方式を用い、対戦は、前記プリソート用レコードエリアに新たに読み込んだレコードを、既に読み込み済みでキー順に並んでいるレコード群内のどの位置に挿入すべきかを、バイナリインサーション方式により決定して、決定した位置にレコードを挿入する方式で行い、且つ、挿入位置の決定は、レコード群を半分ずつの2つのグループに分割し、分割した境界に位置するレコードと、挿入するレコードとを対戦させることにより、挿入するレコードがどちらのグループに属するかを判定することで行い、且つ、挿入するレコードとの対戦相手は、分割した下位のグループの最上位レコードを採用し、同値キーレコードの対戦においては、挿入するレコードの方を勝ちとし、挿入するレコードに対応する前記対戦管理テーブルの同値キーフラグをONにすることを特徴とする同値キーが存在するデータのソート方式。

請求項9

請求項3記載の同値キーが存在するデータのソート方式において、前記マージ対戦手段はレコード対戦方式としてバイナリインサーション方式を用い、対戦は、前記マージ対戦用レコードエリアに新たに読み込んだレコードを、既に読み込み済みでキー順に並んでいるレコード群内のどの位置に挿入すべきかを、バイナリインサーション方式により決定して、決定した位置にレコードを挿入する方式で行い、且つ、挿入位置の決定は、レコード群を半分ずつの2つのグループに分割し、分割した境界に位置するレコードと、挿入するレコードとを対戦させることにより、挿入するレコードがどちらのグループに属するかを判定することで行い、且つ、挿入するレコードとの対戦相手は、分割した下位のグループの最上位レコードを採用し、同値キーレコードの対戦においては、挿入するレコードの方を勝ちとし、挿入するレコードに対応する前記マージ対戦管理テーブルの同値キーフラグをONにすることを特徴とする同値キーが存在するデータのソート方式。

技術分野

0001

本発明はソート方式に関するものであり、特に同値キーレコードが数多く存在する場合に好適なソート方式に関する。

背景技術

0002

メモリ入り切らない大量のレコードをソートする場合、レコードを1件ずつメモリに読み込み、読み込んだレコードを読み込み済みのレコード群対戦させ、対戦の優勝者を順次ワークファイルに出力していって中間結果であるストリング(部分的にソート済みレコード列)を複数作成していくプリソートフェーズを実施し、次いで、ワークファイル内の複数のストリングを繰り返しマージしていって1本のストリングにまとめて出力するマージフェーズを行うというように、前半部分のプリソートフェーズと後半部分のマージフェーズとに分けてソートを行うソート方式が一般的である。

0003

ところで、このようなソート方式では、レコード件数が増加するに伴い、レコードの対戦の回数、従ってキー比較処理呼び出す回数が急速に増加し、中央処理装置を長時間使用するようになり、性能の低下を招くという問題点がある。そこで、同一のキー値(同値キー)を持つレコードが多数存在するレコードのソートにおいて、キー比較の回数を減らし、中央処理装置の使用時間を短縮して性能の向上を図るため、従来より以下のようなソート方式が提唱されている。

0004

(1)従来技術1
レコードのキー比較時に同値キーであった場合に、レコードの単一化を行い、同値キーレコードを1つのレコードにまとめるソート方式(例えば特開平2−259827号公報)。
(2)従来技術2
同値キーレコード数のカウンタを設け、レコードのキー比較時に、同値キーであった場合、同値キーレコード数カウンタ計数処理を行い、出力結果として、レコードのキー部分と、制御情報として、計数された同値キーレコード数を付加するソート方式(例えば特開平1−171021号公報)。

発明が解決しようとする課題

0005

上述したように従来のソート方式においては、同値キーレコードが多く存在するソート処理高速化のアプローチとして、キー比較処理のなかで同値キーレコードを削除して、その後の対戦では同値キーレコードの対戦を少なくすることにより、キー比較回数を減らしていく技術が採用されている。

0006

しかしながら、ソート結果として同値キーレコードを削除せずにそのまま出力するような場合は、上述した従来技術では、単一化した元のレコードまたは計数された同値キーレコード数分だけレコードを複写する処理、キー情報からもとのレコードの形式復元する処理等を組み合わせて実行する必要がある。この結果、キーの比較回数は少なくて済むが、特に同値キーレコードが多数存在する場合には、レコードを複写する処理やレコードからキー情報を抽出する処理やキー情報からレコードを復元する処理等の占める割合が多くなり、却ってソート性能の劣化を招くことになる。

0007

勿論、同値キーレコードを削除しない通常のソート処理を行えばそのような問題はないが、前述したようにレコード件数が増加するに伴い、キー比較回数が急激に増加して、中央処理装置を長時間使うようになり、性能低下が問題となる。

0008

本発明は、上記問題点に鑑み、ソート処理の過程における同値キーレコード同士の対戦を極力抑え得るようにすることにより、同値キーレコードを削除しなくてもキー比較回数を削減できるようにし、同値キーレコードが数多く存在するレコードを高速にソートすることができるようにすることを目的とする。

0009

本発明の同値キーが存在するデータのソート方式は、上記の目的を達成するために、レコードを1件ずつメモリに読み込み、読み込んだレコードを読み込み済みのレコード群と対戦させ、対戦の優勝者を順次ワークファイルに出力していって中間結果であるストリングを複数作成していくプリソートフェーズを実施し、次いで、ワークファイル内の複数のストリングのレコード同士をストリングの先頭より順に対戦させ、対戦の優勝者を1本のストリングにまとめて出力するマージフェーズを実施するソート方式において、プリソートフェーズにおいて、各ストリングに出力するレコードに、当該レコードの後続のレコードが同値キーレコードであるか否かを示す同値キーフラグを付加するプリソート手段と、マージフェーズにおいて、対戦の優勝者レコードをストリングに出力した後、その優勝者レコードの属するストリングから次のレコードを得たときに、前記出力した優勝者レコードに付加されていた同値キーフラグをチェックし、該同値キーフラグが後続のレコードが同値キーレコードであることを示すときは、前記取得した次のレコードは対戦に参加させることなく直ちにストリングに出力するマージ手段とを備えている。これにより、プリソートフェーズにおけるキー比較回数を増加させることなく、マージフェーズにおけるキー比較回数を減らすことができ、トータルなキー比較回数が削減される。

0010

また、マージ手段は、最終マージ以外の場合のストリングにレコードを出力する際、プリソートフェーズにおける場合と同様に、当該レコードの後続のレコードが同値キーレコードであるか否かを示す同値キーフラグを付加する。これにより、マージされて得られたストリングを更に他のストリングとマージする処理において、前述と同様にしてキー比較回数を減らすことができる。以下、このような本発明のソート方式のより具体的な構成および作用を説明する。

0011

本発明の同値キーが存在するデータのソート方式は、メモリに入り切らない大量のレコードを、同値キーレコードについてはそのまま出力するようにしてソートする方式であり、プリソート手段,対戦手段,キー比較手段,マージ手段,マージ対戦手段,ソートワークファイル,プリソート用レコードエリア,対戦管理テーブル,マージ対戦用レコードエリア,マージ対戦管理テーブルを備え、プリソート手段,対戦手段,キー比較手段,ソートワークファイル,プリソート用レコードエリア,対戦管理テーブルを使ってプリソートフェーズを実施し、マージ手段,マージ対戦手段,マージ対戦管理テーブル,キー比較手段,マージ対戦用レコードエリア,ソートワークファイルを使用してマージフェーズを実施する。

0012

プリソートフェーズでは以下のような動作が行われる。プリソート手段は、ファイルあるいはアプリケーションプログラムから入力したソート対象レコードを1件ずつプリソート用レコードエリアへ読み込みながら、対戦手段を呼び出して、読み込んだレコードを、プリソート用レコードエリア内に既にあるレコード群と対戦させる。対戦手段は、キー比較手段を用いてレコードの対戦(キーの比較)を行っていき、対戦の優勝者(キー順で最初に出力すべきレコード)を決定する。プリソート手段は、対戦手段が決定した対戦の優勝者を、ソートワークファイルへ書き込んでいくことにより、ソート中間結果としてストリングと呼ぶ順序付けられたレコード列を生成する。

0013

そして、本発明の特徴として、対戦手段は、対戦に参加している各レコードのプリソート用レコードエリア内アドレスを示すレコードポインタに加えて同値キーフラグを含む情報を対戦管理テーブルにより管理し、レコードの対戦で同値キーであった場合、そのいずれか一方を勝者として、そのレコードに対応する対戦管理テーブルのエントリの同値フラグをONにする。また、プリソート手段は、対戦手段が決定した対戦の優勝者レコードを、ソートワークファイルへ書き込んでいく際には、同値キーフラグもレコード制御情報として付加する。

0014

マージフェーズにおいては以下のような動作が行われる。マージ手段は、ソートワークファイル内の複数のストリングを繰り返しマージしていき、1本のストリングにまとめ、出力する。このマージ手段の1回のマージ処理おいて以下のような動作が行われる。

0015

マージ手段は、まず各ストリングの先頭レコードを、マージ対戦用レコードエリアに読み込み、マージ対戦手段を呼び出してレコードの対戦を行わせる。マージ対戦手段は、キー比較手段を用いて、レコードの対戦(キーの比較)を行っていき、対戦の優勝者(キー順に最初に出力すべきレコード)を決定する。マージ手段は、マージ対戦手段が決定した優勝者をマージ結果として出力する。即ち、最終マージにおいてはファイル或いはアプリケーションプログラムに出力し、それ以外の場合はストリングとしてソートワークファイルへ再度書き込む。

0016

ここで、マージ手段は、優勝者を出力した後、優勝者の属するストリングから次のレコードをマージ対戦用レコードエリアに読み込み、再度マージ対戦手段を呼び出し、読み込んだレコードをマージ対戦用レコードエリア内のレコード群と対戦させて優勝者を決定し、マージ結果として出力する。以上の処理を、マージする全ストリングのレコードを読み終わるまで繰り返し、ストリングのマージを行っていく。

0017

そして本発明の特徴として、プリソートフェーズと同様に、マージ対戦手段は、対戦に参加している各レコードのマージ対戦用レコードエリア内アドレスを示すレコードポインタに加えて同値キーフラグを含む情報をマージ対戦管理テーブルにより管理し、マージ手段は、レコードを対戦に参加させる際に、そのレコードに対応するマージ対戦管理テーブルのエントリの同値キーフラグをOFFリセットし、また、マージ対戦用レコードエリアへレコードを読み込む際には、制御情報である同値キーフラグも同時に読み込む。ここで、マージ対戦用レコードエリアに読み込んだ同値キーフラグ(同値キーレコードフラグと呼ぶこともある)と、マージ対戦管理テーブルのエントリ内の同値キーフラグとは別の情報であることに注意されたい。

0018

そして、マージ対戦手段は、レコードの対戦で同値キーであった場合、そのいずれか一方を勝者として、そのレコードに対応するマージ対戦管理テーブルのエントリの同値キーフラグをONにし、マージ手段は、マージ対戦手段が優勝者レコードを決定したとき、その優勝者レコードを出力レコードと決定して、該決定した出力レコードに付加されている同値キーフラグを参照し、以下の処理を行う。

0019

出力レコードに付加されている同値キーフラグがONであれば、その出力レコードをそれに元々付加されていた同値キーフラグを付加してストリングに出力し且つその出力レコードの属するストリングから読み込んだ次のレコードを対戦に参加させることなく出力レコードに決定する処理を、付加されている同値キーフラグがOFFの出力レコードを読み込むまで繰り返す。出力レコードに付加されている同値キーフラグがOFFであったとき、および、その同値キーフラグがONであって前記処理が行われて同値キーフラグがOFFの出力レコードが読み込まれたときは、前記マージ対戦手段が決定した優勝者レコードに対応する前記マージ対戦管理テーブルの同値キーフラグを参照し、該同値キーフラグがONであれば、ONにした同値キーフラグを付加した出力レコードをストリングに出力し、OFFであれば、その出力レコードにOFFの同値キーフラグを付加してストリングに出力する

0020

対戦手段,マージ対戦手段におけるレコード対戦方式は、トーナメント置換方式バイナリインサーション方式等の任意の方式を用いることができる。

0021

対戦手段にトーナメント置換方式を用いる場合は、対戦で勝ち上がった方のレコードの情報を一時的に設定しておくための作業領域である勝ち上がりレコードエントリが備えられ、対戦手段の対戦は2進木構造で定義される対戦構造の下位から上位に向けて勝ち抜き戦形式で行っていき、対戦構造の各ノード毎に、前記対戦管理テーブルのエントリを対応させ、該エントリには対戦で負けた方のレコードの情報を設定し、対戦の開始時には、読み込んだレコードの情報を前記勝ち上がりレコードエントリに設定し、その後勝ち上がりレコードエントリのレコードと、対戦管理テーブルのレコード群とを、対戦構造に従って順次対戦させていき、前記対戦管理テーブル側のレコードが勝った場合は、前記勝ち上がりレコードエントリと対戦管理テーブル側のレコードの対戦管理テーブルエントリとを交換し、以下同様に対戦を続け、対戦終了時に、前記勝ち上がりレコードエントリに設定されているレコードを対戦の優勝者に決定し、更に、同値キーレコードの対戦があった場合、前記勝ち上がりレコードエントリに設定されているレコードを勝者と決定し、前記勝ち上がりレコードエントリの同値キーフラグをONに設定する。

0022

そして、対戦手段にトーナメント置換方式を用いた構成における好適な実施例においては、対戦手段による対戦の優勝者,優勝者の同値キーフラグ,次に入力したレコードの対戦開始エントリを含む対戦情報を一時的に記憶しておくための対戦結果保存手段をも備え、前記対戦手段は1回の対戦が終了して優勝者が決定した時点で、前記対戦結果保存手段に対戦情報を保存すると共に、対戦を行うにあたり、前記対戦結果保存手段に保存されている前回の対戦での優勝者レコードと今回入力されたレコードとのキーを比較し、同値キーでなければ、前記対戦結果保存手段に保存されている対戦開始エントリからトーナメントの対戦を開始し、同値キーであれば、トーナメントの対戦はスキップし、入力されたレコードを直ちに今回の対戦の優勝者と決定すると共に、前記対戦結果保存手段により保存されている前回の優勝者の同値キーフラグの値を、今回の対戦の優勝者の同値キーフラグとして引き継いだ後、前記対戦結果保存手段により保存されている前回の優勝者の同値キーフラグはONに設定し、前記プリソート手段は、前記対戦手段による1回の対戦を行って優勝者を決定した時点で、前記対戦結果保存手段により保存されている前回の対戦での優勝者およびその同値キーフラグを出力するようにしている。

0023

対戦手段にバイナリインサーション方式を用いる場合は、前記対戦手段による対戦は、前記プリソート用レコードエリアに新たに読み込んだレコードを、既に読み込み済みでキー順に並んでいるレコード群内のどの位置に挿入すべきかを、バイナリインサーション方式により決定して、決定した位置にレコードを挿入する方式で行い、且つ、挿入位置の決定は、レコード群を半分ずつの2つのグループに分割し、分割した境界に位置するレコードと挿入するレコードとを対戦させることにより、挿入するレコードがどちらのグループに属するかを判定することで行い、且つ、挿入するレコードとの対戦相手は、分割した下位のグループの最上位レコードを採用し、同値キーレコードの対戦においては、挿入するレコードの方を勝ちとし、挿入するレコードに対応する前記対戦管理テーブルの同値キーフラグをONにする。

0024

マージ対戦手段にトーナメント置換方式を用いる場合は、マージ対戦手段による対戦で勝ち上がった方のレコードの情報を一時的に設定しておくための作業領域である勝ち上がりレコードエントリを備え、前記マージ対戦手段による対戦は2進木構造で定義される対戦構造の下位から上位に向けて勝ち抜き戦形式で行っていき、対戦構造の各ノード毎に、前記マージ対戦管理テーブルのエントリを対応させ、該エントリには対戦で負けた方のレコードの情報を設定し、対戦の開始時には、読み込んだレコードの情報を前記勝ち上がりレコードエントリに設定し、その後勝ち上がりレコードエントリのレコードとマージ対戦管理テーブルのレコード群とを、対戦構造に従って順次対戦させていき、前記マージ対戦管理テーブル側のレコードが勝った場合は、前記勝ち上がりレコードエントリとマージ対戦管理テーブル側のレコードのマージ対戦管理テーブルエントリとを交換し、以下同様に対戦を続け、対戦終了時に、前記勝ち上がりレコードエントリに設定されているレコードを対戦の優勝者に決定し、更に、同値キーレコードの対戦があった場合、前記勝ち上がりレコードエントリに設定されているレコードを勝者と決定し、前記勝ち上がりレコードエントリの同値キーフラグをONに設定する。

0025

そして、マージ対戦手段にトーナメント置換方式を用いた構成における好適な実施例においては、マージ対戦手段による対戦の優勝者,優勝者の同値キーフラグ,次に入力したレコードの対戦開始エントリを含む対戦情報を一時的に記憶しておくための対戦結果保存手段をも備え、前記マージ対戦手段は1回の対戦が終了して優勝者が決定した時点で、前記対戦結果保存手段に対戦情報を保存すると共に、対戦を行うにあたり、前記対戦結果保存手段に保存されている前回の対戦での優勝者レコードと今回入力されたレコードとのキーを比較し、同値キーでなければ、前記対戦結果保存手段に保存されている対戦開始エントリからトーナメントの対戦を開始し、同値キーであれば、トーナメントの対戦はスキップし、入力されたレコードを直ちに今回の対戦の優勝者と決定するとともに、前記対戦結果保存手段により保存されている前回の優勝者の同値キーフラグの値を、今回の対戦の優勝者の同値キーフラグとして引き継いだ後、前記対戦結果保存手段により保存されている前回の優勝者の同値キーフラグはONに設定し、前記マージ手段は、前記マージ対戦手段による1回の対戦を行って優勝者を決定した時点で、前記対戦結果保存手段により保存されている前回の対戦での優勝者およびその同値キーフラグとを出力するようにしている。

0026

マージ対戦手段にバイナリインサーション方式を用いる場合は、前記マージ対戦手段の対戦は、前記マージ対戦用レコードエリアに新たに読み込んだレコードを、既に読み込み済みでキー順に並んでいるレコード群内のどの位置に挿入すべきかを、バイナリインサーション方式により決定して、決定した位置にレコードを挿入する方式で行い、且つ、挿入位置の決定は、レコード群を半分ずつの2つのグループに分割し、分割した境界に位置するレコードと挿入するレコードとを対戦させることにより、挿入するレコードがどちらのグループに属するかを判定することで行い、且つ、挿入するレコードとの対戦相手は、分割した下位のグループの最上位レコードを採用し、同値キーレコードの対戦においては、挿入するレコードの方を勝ちとし、挿入するレコードに対応する前記対戦管理テーブルの同値キーフラグをONにする。

0027

次に本発明の実施例について図面を参照して詳細に説明する。

0028

図1は本発明の一実施例のブロック図である。同図に示すように、本実施例のソート方式は、プリソート手段1と、対戦手段2と、キー比較手段3と、マージ手段4と、マージ対戦手段5と、ソートワークファイル7と、プリソート用レコードエリア9と、対戦管理テーブル10と、マージ対戦用レコードエリア11と、マージ対戦管理テーブル12と、勝ち上がりレコードエントリ13と、対戦結果保存手段14とを備え、磁気ディスク磁気テープ中のファイルFIあるいはアプリケーションプログラムAPから入力データ(ソート対象レコード)6を入力してソート処理を行い、出力データ(ソート済レコード)8を、磁気ディスクや磁気テープ中のファイルFOあるいはアプリケーションプログラムAPに出力するものである。

0029

本実施例のソート方式における処理は大きく分けて、入力データ6をプリソート用レコードエリア9に読み込みながらソートしていって中間結果である幾つかのストリングをソートワークファイル7へ出力していくプリソート処理と、このプリソート処理で作成した幾つかのストリングを、マージ対戦用レコードエリア11に読み込みながら繰り返しマージしていき、最終的に1本のストリングにまとめ、出力データ8として出力するマージ処理の2つ分けられ、プリソート処理はプリソート手段1が制御を司り、マージ処理はマージ手段4が制御を司る。

0030

本実施例のソート方式が従来のソート方式と大きく相違する点の1つは、プリソートフェーズにおいてソートワークファイル7内に作成する各ストリング中のレコードに、当該レコードの後続のレコードが同値キーレコードであるか否かを示す同値キーフラグを付加した点にある。このために、対戦に参加している各レコードの情報を保持する対戦管理テーブル10および勝ち上がりレコードエントリ13には、各レコード対応の同値キーフラグを設定し、プリソートフェーズ中における処理でこの同値キーフラグを操作するようにしている。なお、対戦管理テーブル10および勝ち上がりレコードエントリ13には、同値キーフラグ以外に、対戦に参加している各レコードが格納されているプリソート用レコードエリア9のアドレスを示すレコードポインタや、用いるソート手法に応じて必要となる種々の情報も格納されている。

0031

本実施例のソート方式が従来のソート方式と大きく相違する他の点は、マージフェーズにおいて、マージ対象となるソートワークファイル7内のストリング中のレコードイメージをそれに付加された同値キーフラグと共にマージ対戦用レコードエリア11に読み込み、また、マージ対戦に参加している各レコードの情報を保持するマージ対戦管理テーブル12および勝ち上がりレコードエントリ13に各レコード対応の同値キーフラグ(この同値キーフラグはマージ対戦用レコードエリア11に設定された同値キーフラグとは別のものである)を設定し、これら2つの同値キーフラグを用いてマージ処理を進めるようにした点にある。なお、マージ対戦管理テーブル12には、同値キーフラグ以外に、マージ対戦に参加している各レコードが格納されているマージ対戦用レコードエリア11のアドレスを示すレコードポインタや、用いるソート手法に応じて必要となる種々の情報も格納されている。

0032

以下、本実施例について詳しく説明していく。まずプリソート処理の流れの概略を説明する。プリソート手段1は、入力データ6中のレコードをプリソート用レコードエリア9へ1件ずつ読み込んでいき、レコードを1件読み込む毎に対戦手段2を呼び出し、読み込んだレコードと、プリソート用レコードエリア9に読み込み済みのレコード群との対戦を行わせる。

0033

対戦手段2は、キー比較手段3を用いて、レコードのキーを比較していき、優勝者(キー順で最初に出力すべきレコード)を決定し、決定した優勝者レコードの情報を、勝ち上がりレコードエントリ13に設定するとともに、優勝者レコードの後続レコードに同値キーのレコードがあるか否かを示す同値キーフラグも同時に勝ち上がりレコードエントリ13に設定する。

0034

本実施例では、対戦手段2における対戦は、対戦管理テーブル10と対戦結果保存手段14とを用いて、トーナメント置換方式により行われるが、処理の詳細については、図2を参照して後述する。

0035

なお、対戦手段2におけるソート方式としてバイナリインサーション方式を用いることも可能であり、対戦手段2にバイナリインサーション方式を適用した実施例の処理の詳細については、図3を参照して後述する。

0036

さて、プリソート手段1は、対戦手段2が決定した対戦の優勝者レコードを、順次ソートワークファイル7へ出力していき、ストリングを作成していくが、その際に同値キーフラグも制御情報として優勝者レコードに付加する。

0037

プリソート手段1は入力データ6の全レコードを幾つかのストリングとしてソートワークファイル7に出力し終わると、マージ手段4に制御を渡し、プリソート処理を終了する。以後、マージ処理が以下のように行われる。

0038

マージ手段4は、ソートワークファイル7の各ストリングからマージ対戦用レコードエリア11に、レコードを1件ずつ読み込んでいき、レコードを1件読み込む毎にマージ対戦手段5を呼び出し、読み込んだレコードと、マージ対戦用レコードエリア11に読み込み済みのレコード群との対戦を行わせる。

0039

マージ対戦手段5は、対戦手段2と同様に、キー比較手段3を用いてレコードのキーを比較していき、優勝者レコード(キー順で最初に出力すべきレコード)を決定し、決定した優勝者レコードの情報を、勝ち上がりレコードエントリ13に設定するとともに、優勝者レコードの後続レコードに同値キーレコードがあるか否かを示す同値キーフラグも同時に勝ち上がりレコードエントリ13に設定する。

0040

このマージ対戦手段5における対戦は、本実施例では、対戦手段2と同様に、マージ対戦管理テーブル12と対戦結果保存手段14とを用いてトーナメント置換方式により行われる。勿論、対戦手段2がバイナリインサーション方式を採用し得ると同様に、マージ対戦手段5もバイナリインサーション方式を採用することができる。

0041

マージ手段4は、最終マージの場合は、マージ対戦手段5が決定した対戦の優勝者レコードを出力データ8として順次出力していき、最終マージでない場合は、マージ対戦手段5が決定した対戦の優勝者レコードをソートワークファイル7へ順次出力していき、マージ結果としての新たなストリングを作成していく。このとき、マージ手段4は、ソートワークファイル7内のストリングの各レコードに制御情報として付加されている同値キーフラグと、マージ対戦手段5により決定した対戦の優勝者レコードのマージ対戦管理テーブル12の同値キーフラグとの2つのフラグ情報を参照して、ストリングとして出力するレコードに同値キーフラグを付加する。また、各レコードに付加されている同値キーフラグはキー比較回数の削減(対戦回数の削減)にも利用される。このようなマージ手段4の処理の詳細は、同値キーフラグの扱いを含め、図4を参照して後に詳細に説明する。

0042

以下、対戦手段2およびマージ手段4の処理手順について、本発明の特徴部分である同値キーフラグの扱いを中心にして、図2から図4フローチャートを参照して詳細に説明する。

0043

先ず、トーナメント置換方式を用いた対戦手段2の処理手順の詳細を説明する。

0044

周知のように、トーナメント置換方式は、2進木構造で定義される対戦構造の下位から上位に向けて勝ち抜き戦形式で対戦を行っていく方式であり、対戦構造の各ノード毎に、対戦管理テーブル10のエントリを対応させ、該エントリには対戦で負けた方のレコードの情報を設定する。他方、対戦で勝ち上がった方のレコードの情報は勝ち上がりレコードエントリ13に一時的に保持される。この勝ち上がりレコードエントリ13の形式は対戦管理テーブル10のエントリと同じである。

0045

対戦は、勝ち上がりレコードエントリのレコードと、対戦管理テーブル10のレコード群とを、対戦構造に従って順次対戦させていく形式で行い、そして各対戦においては、対戦管理テーブル10の対戦相手が勝ち上がりレコードエントリ13のレコードに勝った場合には、勝ったレコードと負けたレコードとを対戦管理テーブル10と勝ち上がりレコードエントリ13との間で入れ換え、対戦終了時に勝ち上がりレコードエントリ13に設定されているレコードが対戦の優勝者となる。

0046

以下、図2を参照して、トーナメント置換方式を用いた対戦手段2の処理手順の詳細を説明する。

0047

対戦手段2は、対戦を開始するにあたり、ステップ201において、プリソート手段1から受け取ったレコードの、プリソート用レコードエリア9内アドレス(レコードポインタ)を、勝ち上がりレコードエントリ13に設定し、ステップ202において、勝ち上がりレコードエントリ13の同値キーフラグをOFFに初期設定する。

0048

ステップ203では、プリソート用レコードエリア9内にレコードが満杯になった後かを判定し、満杯になった後でなければステップ211へ進み、満杯になった後ならばステップ204に進む。従って、ソート開始直後は未だプリソート用レコードエリア9はレコードで満杯になっていないので、ステップ211へ進むことになる。

0049

ステップ211では、対戦管理テーブル10で管理されるレコード群の中から最初に(次に)対戦するレコードを選択する。

0050

ステップ212では、ステップ211での選択の結果、対戦するレコードが存在したか否かを判定し、存在した場合は、ステップ213で、勝ち上がりレコードエントリ13のレコードと対戦相手のレコードとを対戦させる。トーナメント置換方式の手順として周知のように、対戦はまずストリング番号の比較で行い、ストリング番号の小さい方を勝ちと決定し、ストリング番号が同一の場合にのみキーの比較で判定する。

0051

ステップ214では、対戦の結果、同値キーであったか否かを判定し、同値キーならば、勝ち上がりレコードエントリ13のレコードを勝者と見做し、勝ち上がりレコードエントリ13の同値キーフラグをONに設定した後、ステップ211へ戻り、対戦を続行する。

0052

対戦の結果、同値キーでなければ、ステップ216で、どちらのレコードが勝ちかを判定する。

0053

ステップ216の判定の結果、対戦相手(対戦管理テーブル10側のレコード)の勝ちであれば、ステップ217において、対戦相手のレコードの対戦管理テーブル10のエントリと、勝ち上がりレコードエントリ13とを交換することにより、対戦相手を新たな勝ち上がりレコードに設定した後、ステップ211へ戻り、対戦を続行する。また、ステップ216での判定の結果、勝ち上がりレコードが勝ちならば、そのままステップ211へ戻り、対戦を続行する。

0054

このような対戦が続けられ、ステップ212で次に対戦するレコードが存在しないと判定されると、今回のレコードの入力時点での対戦が終了したことになり、ステップ218へ移行し、勝ち上がりレコードエントリ13に設定されているレコードを対戦の優勝者と決定し、ステップ219において、優勝者レコード,優勝者レコードの同値キーフラグ,次の入力レコードの対戦開始エントリ等の対戦結果を、対戦結果保存手段14に保存して、今回のレコード入力時点における対戦処理を終了する。

0055

以上のような対戦がレコード入力毎に行われ、プリソート用レコードエリア9内にレコードが満杯になった後に次のレコードが入力されると、ステップ203からステップ204へ移行する。ステップ204では、対戦結果保存手段14により保存されている前回の対戦の優勝者レコードと、勝ち上がりレコードエントリ13のレコード(今回の入力レコード)とのキーを比較し、ステップ205で同値キーかを判定する。

0056

ステップ205の判定の結果、同値キーであれば、ステップ206において、勝ち上がりレコードエントリ13の同値キーフラグとして、対戦結果保存手段14が保存している、前回の対戦での優勝者レコードの同値キーフラグの値をそのまま引き継ぎ、ステップ207において、対戦結果保存手段14が保存している、前回の対戦での優勝者レコードの同値キーフラグをONに設定し直した後、トーナメントによる対戦を行うことなくステップ218へ移行し、勝ち上がりレコードエントリ13のレコード(今回の入力レコード)を対戦の優勝者と決定する。

0057

また、ステップ205の判定の結果、同値キーでなければ、ステップ208において、どちらのレコードの勝ちかを判定し、勝ち上がりレコードエントリ13のレコード(今回の入力レコード)の勝ちならば、トーナメント置換方式の手順として周知のように、ステップ209において、今回の入力レコードのストリング番号に1を加算する。そして、ステップ210において、対戦結果保存手段14により保存されている対戦開始エントリを得て、ステップ211以降の対戦処理を開始する。

0058

以上が、トーナメント置換方式を用いた対戦手段2の処理手順の詳細であり、次にその理解を容易にするために、実際の入力データを使用して対戦手段2の処理の流れを再度説明する。

0059

図5乃至図9は、対戦手段2の処理の流れについて、実際の入力データを使用して例示したものものである。各図において、501〜520は各ステップを示し、1つのステップが1回の対戦の状態を示すものであり、入力データは小文字英字文字で示し、下線を引いた部分がカレント入力データである。また、△はカレント入力データの対戦開始エントリ、↑は次の入力データの対戦開始エントリを示し、太線は対戦の優勝者の対戦経緯を示す。さらにトーナメントツリーの各ノードにおける記号は、最初の1文字がストリング番号、2文字目がキー、3文字目に”−”を付加した場合は、対応する対戦管理テーブル10の同値キーフラグがONであることを示す。但し、ストリングのデータに”−”を付加した場合は付加データとしての同値キーフラグがONであること示す。また、( )で囲んである場合は、そのノードにおける対戦で勝者となったことを示し、実際のエントリは上位のノードにあることを意味する。なお、ソートは昇順で行われるものと仮定している。

0060

以下処理を順に追って説明していく。処理は大きくわけて3つに分けられる。最初の部分は図5のステップ501から504までで、トーナメントツリーで示されるレコードエントリが満杯になるまでの処理、つまり入力データとして、c,d,d,cの4つが処理されるまでである。図2のフローチャートで言えば、ステップ203でYESと判定されるまでの処理である。この部分では、入力レコードの対戦開始エントリは左から順番に進められる。この段階における本発明の特徴に関する処理はステップ504であり、図2のステップ214で同値キー(c)が検出されることにより、勝ち上がりレコードエントリ13の同値キーがONにされている。

0061

処理の第2の部分は、図6のステップ505から図8のステップ516までで、トーナメントツリーで示されるレコードエントリが満杯になってから、入力データが終了するまでの処理である。この部分では、入力レコードの対戦開始エントリは、前回の対戦での優勝者の対戦開始エントリとなる。またストリング番号の決定はトーナメント置換方式の手順として知られているように以下のように行う。即ち、レコード入力時に入力レコードと前回の優勝者(各ステップで一番右上に記したレコード。例えばステップ505で言えば1c−)を対戦させ(図2のステップ204)、入力レコードが勝ったならば、入力レコードのストリング番号を1増し、以降の対戦ではストリング番号の小さい方が、キーの大小によらずに勝ちとなるようにする。今の例では、ステップ506における入力データ(a)が前回の優勝者(c)に勝ったため、aのストリング番号を2にしている。またステップ515における入力データ(a)が前回の優勝者(b)に勝ったため、aのストリング番号を3にしている。また、優勝者のストリング番号が切り替わった時点で、出力するストリングの切り換えを行う。今の例では、ステップ512で優勝者のストリング番号が1から2に切り替わったので、出力するストリングを今までのストリング1からストリング2に切り替えている。なお、図9のステップ518でも、優勝者のストリング番号が2から3に切り替わったので、出力するストリングを今までのストリング2からストリング3に切り替えている。

0062

この第2の部分における同値キーフラグの扱いは第1の部分と同様であり、今の例では、ステップ506,509,510,511,513,514における対戦で同値キーを検出している。特にステップ509では、入力レコードと前回の優勝者が同値キー(e)であるため、実際にはトーナメントによる対戦はスキップして、入力レコードをそのまま優勝者と決定しており、前回の優勝者の同値キーフラグをONに変更して出力している。同様に、ステップ514でも、入力レコードと前回の優勝者が同値キー(b)であり、トーナメントによる対戦はスキップして、入力レコードをそのまま優勝者と決定している。

0063

第3の部分は図9のスキップ517以降で、入力レコードが終了してから、残っているレコードを順次追い出していく処理である。本例では、残っているレコードを順次追い出していくために、ダミーレコード(図中の”Z”で示す)を対戦に参加させ、通常のレコードとダミーレコードとの対戦では必ず通常のレコードの勝ちと決定するように定めている。そして、対戦を行っていき、ダミーレコードが優勝者となった時点で処理は終了する。

0064

以上、トーナメント置換方式を用いた対戦手段2の処理手順について説明した。トーナメント置換方式を用いたマージ対戦手段5の処理手順についても全く同様であり、上述の説明において、対戦手段2をマージ対戦手段5に、対戦管理テーブル10をマージ対戦管理テーブル12に、プリソート用レコードエリア9をマージ対戦用レコードエリア11に、それぞれ読み換えれば、トーナメント置換方式を用いたマージ対戦手段5の処理手順の詳細は容易に理解されるであろう。

0065

次に、バイナリインサーション方式を用いた対戦手段2の処理手順の詳細ついて説明する。

0066

周知のように、バイナリインサーション方式は、ソート済みのレコード列と、そのレコード列に挿入したいレコードとが与えられたときに、レコード列を半分ずつの2つのグループに分割し、分割した境界に位置するレコードと、挿入するレコードとを対戦させることにより、挿入するレコードがどちらのグループに属するかを判定し、以下同様に、レコード列を半分ずつに区切って、属するグループを特定する処理を、分割したグループのレコード数が1になるまで繰り返して挿入位置を決定する(但し、レコードの対戦で同値キーとなった場合は、その時点で挿入位置が決定する)方式である。

0067

バイナリインサーション方式を適用する場合、図1の実施例のソート処理においては、プリソート用レコードエリア9に読み込み済みで且つ既にソート済みのレコード群(これらは対戦管理テーブル10により管理され、対戦管理テーブル10のエントリはキー順に線形に並んでいる)と、新たに読み込んだレコードとを対戦させ、挿入位置を決定する処理を繰り返していき、最上位に位置付けられたレコードを、ストリングとしてソートワークファイル7へ順次出力していく方法で処理が進められる。

0068

以下、図3を参照して、対戦管理テーブル10により管理されたソート済みのレコード群に、新たに読み込んだレコードを挿入する処理手順の詳細を説明する。

0069

対戦手段2は、まずステップ301にて、対戦管理テーブル10で管理されるレコード群を、比較対象レコード群(挿入するレコードが属するレコード群)と設定し、ステップ302では、挿入するレコードの対戦管理テーブル10のエントリの同値キーフラグをOFFに初期設定する。

0070

次に、ステップ303では、比較対象レコード群を、キーの大小で2つのグループに分割する。なお、以下の説明において、分割した上位グループとは、キーの順序で先に出力すべきグループを意味し、同様に下位グループとは、キーの順序で後から出力すべきグループを意味するものとする。またステップ303の処理において、比較対象グループの要素数が1である場合は、便宜上下位グループに入れ、上位グループは空集合とする。

0071

ステップ304では、挿入するレコードと、ステップ303で分割した下位グループ内の最上位(キー順で最初に出力すべき)レコードとのキーを比較し、ステップ305では、キー比較の結果、同値キーであったか否かを判定する。

0072

判定の結果、同値キーならば、ステップ306で、挿入するレコードの同値キーフラグをONに設定し、ステップ307では、下位グループの最上位レコードの直前に、挿入するレコードの対戦管理テーブル10のエントリを挿入して処理を終了する。

0073

他方、ステップ305の判定の結果、同値キーでなければ、ステップ308において、どちらのレコードが勝ち(キー順で先に出力すべき)かを判定する。

0074

ステップ308の判定の結果、挿入するレコードの勝ちであれば、ステップ309で、下位グループの要素数をチェックし、要素数が1であれば、ステップ310において、下位グループの(唯一の)レコードの直前に、挿入するレコードの対戦管理テーブル10のエントリを挿入して、今回の処理を終了し、要素数が2以上ならば、ステップ311において、上位グループを新たな比較対象グループとして設定して、ステップ303に戻り、比較を続行する。

0075

また、ステップ308の判定の結果、比較した相手(下位グループの最上位レコード)が勝ちであれば、ステップ312で、下位グループの要素数をチェックし、要素数が1であれば、ステップ313において、下位グループの(唯一の)レコードの直後に、挿入するレコードの対戦管理テーブル10のエントリを挿入して、今回の処理を終了し、要素数が2以上ならば、ステップ314において、下位グループを新たな比較対象グループとして設定して、ステップ303に戻り、比較を続行する。

0076

以上がバイナリインサーション方式を用いた対戦手段2の処理手順の詳細である。なお、バイナリインサーション方式を用いたマージ対戦手段5についても全く同様であり、上述の説明において、対戦手段2をマージ対戦手段5に、対戦管理テーブル10をマージ対戦管理テーブル12に、プリソート用レコードエリア9をマージ対戦用レコードエリア11に、それぞれ読み換えれば、バイナリインサーション方式を用いたマージ対戦手段5の処理手順の詳細は容易に理解されるであろう。

0077

次に、マージ手段4における1回のマージ処理の処理手順の詳細について、図4を参照して説明する。なお、以下では、ソートワークファイル7内のストリングをマージして、新たなストリングとして再度ソートワークファイル7に書き込む場合(即ち最終マージでない場合)の処理について説明する。

0078

マージ手段4は、まずステップ401において、マージする各ストリングの先頭レコードを、マージ対戦用レコードエリア11に読み込みながら、マージ対戦手段5による対戦を行っていく。このとき、プリソート処理において既に制御データとしてレコードに付加されている同値キーフラグも、レコードイメージと同時にマージ対戦用レコードエリア11に読み込む。ここで、マージ対戦用レコードエリア11に読み込んだ同値キーフラグと、マージ対戦管理テーブル12の同値キーフラグとは別のものであることに注意されたい。また、プリソート時と同様に、レコードを対戦に参加させる際には、該当レコードのマージ対戦管理テーブル12の同値キーフラグはOFFに設定する。

0079

次に、ステップ402では、対戦の優勝者を出力レコードと決定する。即ち、全ストリングの先頭レコードを読み終わった時点での優勝者を最初に出力すべきレコードとする。

0080

ステップ403では、出力レコードに付加されている同値キーフラグがONであるか否かをチェックし、ONであれば、ステップ404で、出力レコードをソートファイル7へ出力(付加されている同値キーフラグもそのまま付加して出力する)し、ステップ405で、出力レコードの属するストリングから次のレコード(これは先に出力したレコードと同値キーを持つレコードである)を読み込み、新たな出力レコードに決定して、ステップ403に戻る。

0081

ステップ403〜405の処理を、同値キーフラグがOFFのレコードを読み込むまで繰り返した後、ステップ406に移行する。

0082

ステップ406では、直前の対戦での優勝者の、マージ対戦管理テーブル12のエントリの同値キーフラグをチェックし、ONであれば、マージ時の対戦で新たに同値キーレコードが見つかったということなので、ステップ407において、出力レコードとそれに付加する同値キーフラグ(ONに設定)とを、ソートワークファイル7へ出力する。他方、チェックの結果、同値キーフラグがOFFであれば、ステップ408において、出力レコードとそれに付加する同値キーフラグ(OFFに設定)とを、ソートワークファイル7へ出力する。

0083

出力レコードをソートワークファイル7へ出力した後、ステップ409において、出力レコードの属するストリングから次のレコードを読み込み、ステップ410では、読み込みの結果、出力レコードが属するストリングのレコードが終了していたか否かを判定する。

0084

出力レコードが属するストリングのレコードが終了していたならば、ステップ411で、マージ対戦用レコードエリア11内のレコードで、まだ出力していないレコードが残っているか否かを判定し、残っていなければ処理(1回のマージ処理)を終了し、残っていれば、ステップ412にて、残っているレコードで対戦を行って新たな優勝者を決定し、ステップ402に戻り、処理を続行する。

0085

ステップ410の判定の結果、出力レコードが属するストリングのレコードが終了していなければ、即ちステップ409で次のレコードが読み込まれたならば、ステップ413にて、読み込んだレコードを対戦に参加させて新たな優勝者を決定し、ステップ402に戻って処理を続行する。

0086

以上がマージ手段4における1回のマージ処理の手順の詳細であるが、より理解を容易にするために、実際の入力データを使用して更に説明する。

0087

図10および図11は、マージ手段4における1回のマージ処理の流れについて、実際の入力データを使用して例示したものである。この例では3本のストリング1〜3をマージして、再度ソートワークファイル7へ出力する例である。各図において、601〜611は各ステップを示し、1つのステップが1回の対戦の状態を示すものであり、入力データは小文字の英字1文字で示す。各ストリングのデータは、その時点でメモリに読み込まれている(最左端のデータ)か、または、これから読み込むデータを示しており、出力済みのデータについては記述していない。また、図5図9と同様に、”−”は同値キーフラグを示し、ストリングのデータの後ろに”−”を付記した場合は、制御データとしてレコードに付加されている同値キーフラグがONであることを意味し、対戦の勝者に”−”を付記した場合は、対戦の勝者レコードの、マージ対戦管理テーブル12の同値キーフラグがONであることを意味する。なお、対戦はトーナメント置換方式により行うものと仮定している。

0088

以下処理の順を追って説明していく。ステップ601では、ストリングの先頭レコードの対戦を行う。本例では、同値キーの場合、ストリング番号が小さい方を勝者とするので、この対戦の結果の優勝者は、ストリング2に所属するレコードaであり、優勝者のレコードaの同値キーフラグはマージ対戦手段5によってONにされている(図2のステップ215相当の処理による)ため、図4のステップ403の結果はYESとなり、出力レコードaに付加する同値キーフラグもONとなる。

0089

ステップ602では、ステップ601での優勝者の属するストリング2から次のレコードbを読み込んで対戦を行い、ストリング3に所属するレコードaが優勝者となり、出力される。このとき、対戦相手は同値キーでなかったので、図4のステップ403の判定結果はNOとなり、且つ、優勝者レコードbに対応するマージ対戦管理テーブル12の同値キーフラグはOFFなので、図4のステップ406の判定結果はNOとなり、その結果、出力レコードaの同値キーフラグはOFFのままである。

0090

ステップ603では、ステップ602での優勝者の属するストリング3から次のレコードを読み込み(図4のステップ409)、対戦を行い、ストリング2に所属するレコードbが優勝者となり、出力される。

0091

ステップ604では、ステップ603での優勝者の属するストリング2から次のレコードcを読み込んで対戦を行い、ストリング3に所属するレコードbが優勝者となり、出力される。

0092

ストリング605では、ストリング604での優勝者の属するストリング3から次のレコードを読み込むが、ストリング3内のレコードが終了しているため、ストリング1と2のレコードで対戦を行い、ストリング1に所属するレコードcが優勝者となり、出力される。このとき、出力レコードcに付加されている同値キーフラグがONであるため、後続の同値キーレコードcも対戦させることなく直ちに出力する。さらに、マージ対戦管理テーブル12の該当同値キーフラグもON(ストリング2のレコードcと同値キーであったため)であるため、後続の同値キーレコードcに付加する同値キーフラグをONにして出力する。

0093

ステップ606では、ステップ605での優勝者の属するストリング1から次のレコードdを読み込んで対戦を行い、ストリング2に所属するレコードcが優勝者となり、出力される。このとき、出力レコードcに付加されている同値キーフラグがONであり、後続に2個の同値キーレコードcが存在するため、それらの同値キーレコードも対戦させることなく直ちに出力する。

0094

以上のようにして、ストリング1における2個の連続する同値キーレコード(c−c)と、ストリング2における3個の連続する同値キーレコード(c−c−c)とがマージされて、5個の連続する同値キーレコード(c−c−c−c−c)にまとめられる。

0095

以下、ステップ607以降についても同様である。

発明の効果

0096

以上説明したように、本発明は、プリソートフェーズにおいて、各ストリングに出力するレコードに、当該レコードの後続のレコードが同値キーレコードであるか否かを示す同値キーフラグを付加し、マージフェーズにおいて、対戦の優勝者レコードをストリングに出力した後、その優勝者レコードの属するストリングから次のレコードを得たときに、前記出力した優勝者レコードに付加されていた同値キーフラグをチェックし、該同値キーフラグが後続のレコードが同値キーレコードであるこを示すときは、前記取得した次のレコードは対戦に参加させることなくそのままストリングに出力するようにしたので、マージフェーズにおける同値キーレコード同士の対戦が極力抑えられ、同値キーレコードの削除を行う従来技術の場合と同様にキー比較回数を削減することができ、しかも、従来技術のように出力時に(ソート時にカウントした)同値キーレコード数分だけレコードを複写したり、キー情報を元にレコードイメージを復元したりする処理を行う必要もないので、その分、ソート処理時間を短縮することができる効果がある。

0097

また、マージフェーズにおいて、最終マージ以外の場合のストリングにレコードを出力する際、プリソートフェーズにおける場合と同様に、当該レコードの後続のレコードが同値キーレコードであるか否かを示す同値キーフラグを付加したことにより、これらのストリングのマージ時に前述と同様の原理でキー比較回数を減らすことができる。

図面の簡単な説明

0098

図1本発明の一実施例のブロック図である。
図2トーナメント置換方式を用いた対戦手段の処理手順を示すフローチャートである。
図3バイナリインサーション方式を用いた対戦手段の処理手順を示すフローチャートである。
図4マージ手段における1回のマージ処理の手順を示すフローチャートである。
図5対戦手段の処理の流れについて実際の入力データを使用して例示した図である。
図6対戦手段の処理の流れについて実際の入力データを使用して例示した図である。
図7対戦手段の処理の流れについて実際の入力データを使用して例示した図である。
図8対戦手段の処理の流れについて実際の入力データを使用して例示した図である。
図9対戦手段の処理の流れについて実際の入力データを使用して例示した図である。
図10マージ手段における1回のマージ処理の流れについて実際の入力データを使用して例示した図である。
図11マージ手段における1回のマージ処理の流れについて実際の入力データを使用して例示した図である。

--

0099

1…プリソート手段
2…対戦手段
3…キー比較手段
4…マージ手段
5…マージ対戦手段
6…入力データ
7…ソートワークファイル
8…出力データ
9…プリソート用レコードエリア
10…対戦管理テーブル
11…マージ対戦用レコードエリア
12…マージ対戦管理テーブル
13…勝ち上がりレコードエントリ
14…対戦結果保存手段

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

該当するデータがありません

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • ルネサスエレクトロニクス株式会社の「 半導体集積回路装置及びデータ比較方法」が 公開されました。( 2019/04/04)

    【課題】メモリ空間上のデータをCPUを使用せずに比較し、比較回数及び比較条件一致回数の少なくとも一方に基づく割り込み条件で、割り込みを発生させる。【解決手段】割り込みコントローラ19は、CPUコアA1... 詳細

  • 国立大学法人東京工業大学の「 データソート装置」が 公開されました。( 2018/12/06)

    【課題】高い動作周波数でレコードをマージする。【解決手段】データに付加された情報に応じてデータが並べられた第1のデータ列と、第1のデータ列と異なる第2のデータ列とのうち第1のデータ列または第2のデータ... 詳細

  • 国立大学法人東京工業大学の「 データソート装置」が 公開されました。( 2018/10/04)

    【課題】 1サイクルにマージ可能なレコード数Eを増加させる場合でも、従来と比べて簡単な回路構成でレコードをマージすることができるデータソート装置を提供することを目的とする。【解決手段】 データに付... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

該当するデータがありません

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ