(57)【要約】【課題】  高速なデータサーチを行なうことができるデータ処理方法を提供する。【解決手段】  検索元のデータであるサーチキーと検索先のデータであるソースデータとを１つのデータチェインに記憶した後、データの内容に基づきソートを行なう。ソートされたデータ順にサーチキーを抽出する。抽出されたサーチキーの位置から１つ後方にあるソースデータを取得し、サーチキーとソースデータが一致するかを比較する。また、サーチキーの位置から１つ後方にあるデータがサーチキーであれば、ソースデータとの比較処理は行なわれない。これにより、ソースデータの無駄な検索を省く。【選択図】        図６
2006201956.tif 000002
【特許請求の範囲】
【請求項１】
第１のデータ群に含まれるデータと、第２のデータ群に含まれるデータとを比較照合するデータ処理方法であって、
前記第１のデータ群または前記第２のデータ群のうち、データ数の少ないほうをサーチキーとし、多いほうをソースデータと定義する定義ステップと、
前記第１のデータ群と前記第２のデータ群とをまとめた上で、ソートを行なうソートステップと、
前記ソートステップにおいてソートされたデータのうち、サーチキーの各々に対して、次のサーチキーのアドレスを記録する記録ステップと、
前記記録ステップにより記録されたアドレスに基づいて、前記ソートされたデータの中から、ソートの順番にサーチキーを抽出する抽出ステップと、
前記抽出されたサーチキーの位置から、ソートにおける次の順序のデータを取得する取得ステップと、
前記取得されたデータがサーチキーであるか否かを判定する判定ステップと、
前記判定ステップにおいて、前記取得されたデータがサーチキーであると判定された場合には、ヒットデータは無いものとして、前記抽出ステップにおいて次のサーチキーの抽出を行なうよう処理する処理ステップと、
前記判定ステップにおいて、前記取得されたデータがサーチキーではないと判定された場合には、前記取得されたデータが前記サーチキーのデータと一致するか否かを照合する照合ステップとを備えた、データ処理方法。
【請求項２】
前記照合ステップにおいて１つのサーチキーに対する１つのソースデータの照合が行なわれると、前記抽出ステップにおいて次のサーチキーの抽出を行なうよう処理する、請求項１に記載のデータ処理方法。
【請求項３】
前記第１のデータ群および前記第２のデータ群に含まれるデータは、Ｘ座標およびＹ座標のデータを含む、請求項１〜３のいずれかに記載のデータ処理方法。
【請求項４】
第１のデータ群に含まれるデータと、第２のデータ群に含まれるデータとを比較照合するデータ処理プログラムであって、
前記第１のデータ群または前記第２のデータ群のうち、データ数の少ないほうをサーチキーとし、多いほうをソースデータと定義する定義ステップと、
前記第１のデータ群と前記第２のデータ群とをまとめた上で、ソートを行なうソートステップと、
前記ソートステップにおいてソートされたデータのうち、サーチキーの各々に対して、次のサーチキーのアドレスを記録する記録ステップと、
前記記録ステップにより記録されたアドレスに基づいて、前記ソートされたデータの中から、ソートの順番にサーチキーを抽出する抽出ステップと、
前記抽出されたサーチキーの位置から、ソートにおける次の順序のデータを取得する取得ステップと、
前記取得されたデータがサーチキーであるか否かを判定する判定ステップと、
前記判定ステップにおいて、前記取得されたデータがサーチキーであると判定された場合には、ヒットデータは無いものとして、前記抽出ステップにおいて次のサーチキーの抽出を行なうよう処理する処理ステップと、
前記判定ステップにおいて、前記取得されたデータがサーチキーではないと判定された場合には、前記取得されたデータが前記サーチキーのデータと一致するか否かを照合する照合ステップとをコンピュータに実行させる、データ処理プログラム。
【請求項５】
請求項４に記載のデータ処理プログラムを記録した、コンピュータ読取可能な記録媒体。
【請求項６】
第１のデータ群に含まれるデータと、第２のデータ群に含まれるデータとを比較照合するデータ処理装置であって、
前記第１のデータ群または前記第２のデータ群のうち、データ数の少ないほうをサーチキーとし、多いほうをソースデータと定義する定義手段と、
前記第１のデータ群と前記第２のデータ群とをまとめた上で、ソートを行なうソート手段と、
前記ソート手段においてソートされたデータのうち、サーチキーの各々に対して、次のサーチキーのアドレスを記録する記録手段と、
前記記録手段により記録されたアドレスに基づいて、前記ソートされたデータの中から、ソートの順番にサーチキーを抽出する抽出手段と、
前記抽出されたサーチキーの位置から、ソートにおける次の順序のデータを取得する取得手段と、
前記取得されたデータがサーチキーであるか否かを判定する判定手段と、
前記判定手段において、前記取得されたデータがサーチキーであると判定された場合には、ヒットデータは無いものとして、前記抽出手段において次のサーチキーの抽出を行なうよう処理する処理手段と、
前記判定手段において、前記取得されたデータがサーチキーではないと判定された場合には、前記取得されたデータが前記サーチキーのデータと一致するか否かを照合する照合手段とを備えた、データ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明はデータ処理方法、データ処理プログラム、およびデータ処理装置に関し、特にコンピュータのデータにおいて、任意条件を満たすデータのサーチを行なう際、良好なパフォーマンスを提供するデータ処理方法、データ処理プログラム、およびデータ処理装置に関する。
【背景技術】
【０００２】
従来、任意条件に適合するデータを検索する場合、検索元条件となるデータと検索先のデータとを別々にデータチェイン（配列など）に保持して比較照合処理を行なっていた。また、従来は検索元条件と検索先データとを予め決定して、比較照合処理を行なっていた。
【０００３】
たとえば、ＣＡＤデータにおける２層間の円形データ（座標Ｘ，Ｙを有するデータ）をサーチして、同じ位置にある円形データの組合せを表示する場合を例にとり説明する。
【０００４】
図１６は、Ａ層のデータを示す図である。Ａ層のデータは、円形データを２０個（Ａ１〜Ａ２０）有しており、それぞれの円形データは、Ｘ座標１．０〜６．０、Ｙ座標１．０〜７．０のいずれかの値をとるものとする。
【０００５】
図１７は、Ｂ層のデータを示す図である。Ｂ層のデータは円形データを４２個（１〜４２）有しており、それぞれの円形データは、Ａ層と同様にＸ座標１．０〜６．０、Ｙ座標１．０〜７．０のいずれかの値をとるものとする。
【０００６】
図１８は、図１６および図１７のＡ層およびＢ層の円形データの照合を行なうデータサーチプログラムの処理を示すフローチャートである。
【０００７】
図１８を参照して、ステップＳ１０１で、円形データ保持用構造体の定義を行ない、Ａ層およびＢ層それぞれのメモリ領域を確保する。メモリ領域においては、円形データのＸおよびＹ座標が記録できるようにされる。
【０００８】
次に、ステップＳ１０３で、Ａ層のメモリ領域にＡ層のデータ（図１６）をロードする（上記構造体のＡ層用データチェインにデータをストアする）。また、Ｂ層のメモリ領域にＢ層のデータ（図１７）をロードする。
【０００９】
ステップＳ１０５で、Ａ層データチェインよりサーチキーとなるデータ（Ｘ，Ｙ座標）を抽出する。この抽出においては、Ａ１→Ａ２→Ａ３→Ａ４→…→Ａ２０の順に、サーチキー参照ポインタを移動することで、順次サーチキーとなるＡ層のデータを抽出していく。
【００１０】
ステップＳ１０７で、Ｂ層データチェインよりサーチキーと比較照合するためのソースデータ（Ｘ，Ｙ座標）を抽出する。この処理においては、Ｂ層のデータから、１→２→３→４→…→４２の順に、ソースデータ参照ポインタを移動することで順次データを抽出していく。
【００１１】
ステップＳ１０９で、サーチキーとソースデータとの比較照合処理が行なわれ、それぞれの円形データが同じ位置にあるかが判定される。ＹＥＳであれば、ステップＳ１１１において、サーチキーとソースデータとを同位置にある組合せとしてディスプレイなどに表示するなどの処理を行なう。一方、ステップＳ１０９でＮＯであれば、この処理は行なわれない。
【００１２】
次に、ステップＳ１１３で、すべてのソースデータを比較照合したかが判定され、ＮＯであればステップＳ１０７へ戻りソースデータ参照ポインタを次のソースデータに移動して、データを抽出する処理を行なう。
【００１３】
ステップＳ１１３ですべてのソースデータを比較照合したものと判断されたのであれば、ステップＳ１１５ですべてのサーチキーを比較照合したかが判定される。ステップＳ１１５でＮＯであれば、ステップＳ１０５へ戻り、サーチキー参照ポインタを次のサーチキーに移動してデータの抽出を行なう。
【００１４】
ステップＳ１１５ですべてのサーチキーを比較照合したと判断されたのであれば、処理は終了となる。
【００１５】
次に、データサーチプログラムによる図１６および図１７のデータの具体的な照合例を説明する。
【００１６】
図１９および図２０はそれぞれ、Ａ層（図１６）およびＢ層（図１７）の円形データのロード、およびデータチェインへの座標データストアが完了した時点の各データチェインの内容を表概念で表わす図である。なお、図におけるメモリアドレスは仮定のものである。これらのＡ層およびＢ層のデータチェインはそれぞれ異なるアドレスにアロケートされており、フラグメント状態になっている（コンベンショナルではない）。
【００１７】
図１９に示されるように、メモリアドレス＆１〜＆２０のそれぞれにＡ層のＡ１〜Ａ２０のデータがＸ，Ｙ座標として格納されている。同様に、図２０を参照してＢ層のデータチェインにはＢ層のデータがメモリアドレス＆１２１〜＆１６２に１〜４２のＸ，Ｙ座標として記録されている。
【００１８】
従来のアルゴリズムによると、以下のように検索処理は行なわれる。
【００１９】
（１）  サーチキー参照ポインタをＡ層データチェインのメモリアドレス＆１（図１９）にセットする。
【００２０】
（２）  ソースデータ参照ポインタをＢ層データチェインのメモリアドレス＆１２１（図２０）にセットする。
【００２１】
（３）  ソースデータ参照ポインタの参照アドレス＆１２１のＸ，Ｙ座標フィールドの座標データ（図２０）と、サーチキー参照ポインタの参照アドレス＆１のＸ，Ｙ座標フィールドの座標データ（図１９）とを比較照合する。
【００２２】
ここでは、ソースデータ（＆１２１）は、Ｘ＝３．０００、Ｙ＝４．０００であり、サーチキー（＆１）はＸ＝４．５００、Ｙ＝１．５００であるため、両データは同一座標にないと判断する。
【００２３】
（４）  ソースデータ参照ポインタを、現行の参照アドレスの次のアドレス（定義構造体の１要素シフトした位置）である＆１２２（図２０）にセットする。
【００２４】
（５）  ソースデータ参照ポインタの参照アドレス＆１２２のＸ，Ｙ座標フィールドより座標データを取得し、サーチキー参照ポインタの参照アドレス＆１のＸ，Ｙ座標フィールドの座標データ（図１９）と比較照合する。
【００２５】
ここでは、ソースデータ（＆１２２）はＸ＝５．０００、Ｙ＝２．０００であり、サーチキー（＆１）はＸ＝４．５００、Ｙ＝１．５００であるため、両データは同一座標にないと判断する。
【００２６】
（以下省略）
以上に述べたように、メモリアドレス＆１（図１９）の座標データに対して、＆１２１〜＆１６２（図２０）のすべてのデータを走査することになる。＆２〜＆２０（図１９）についても同様に、＆１２１〜＆１６２すべてのデータを走査する。すなわち、サーチキーおよびソースデータの全データを総当たりで比較照合することとなる。この処理においては、位置的に乖離したデータであっても（たとえばＡ層の＆６と、Ｂ層の＆１４０の組合せなど）、比較照合を行なっていることを意味し、大量の無駄な処理を含んでいることになる。
【発明の開示】
【発明が解決しようとする課題】
【００２７】
このように、従来のデータサーチ処理における検索は、すべての円形データを走査して比較照合が行なわれる。たとえば、図１９および図２０の例では、サーチキーの数＝２０、ソースデータの数＝４２であるため、サーチキーの数×ソースデータの数＝８４０回の比較照合処理が行なわれることとなり、パフォーマンスが悪いという問題があった。
【００２８】
本発明は以上のような問題点を解決するためになされたものであり、高速なデータサーチを行なうことができるデータ処理方法、データ処理プログラム、およびデータ処理装置を提供することを目的としている。
【課題を解決するための手段】
【００２９】
上記目的を達成するためこの発明のある局面に従うと、データ処理方法は、第１のデータ群に含まれるデータと、第２のデータ群に含まれるデータとを比較照合するデータ処理方法であって、第１のデータ群または第２のデータ群のうち、データ数の少ないほうをサーチキーとし、多いほうをソースデータと定義する定義ステップと、第１のデータ群と第２のデータ群とをまとめた上で、ソートを行なうソートステップと、ソートステップにおいてソートされたデータのうち、サーチキーの各々に対して、次のサーチキーのアドレスを記録する記録ステップと、記録ステップにより記録されたアドレスに基づいて、ソートされたデータの中から、ソートの順番にサーチキーを抽出する抽出ステップと、抽出されたサーチキーの位置から、ソートにおける次の順序のデータを取得する取得ステップと、取得されたデータがサーチキーであるか否かを判定する判定ステップと、判定ステップにおいて、取得されたデータがサーチキーであると判定された場合には、ヒットデータは無いものとして、抽出ステップにおいて次のサーチキーの抽出を行なうよう処理する処理ステップと、判定ステップにおいて、取得されたデータがサーチキーではないと判定された場合には、取得されたデータがサーチキーのデータと一致するか否かを照合する照合ステップとを備える。
【００３０】
好ましくは、データ処理方法は、照合ステップにおいて１つのサーチキーに対する１つのソースデータの照合が行なわれると、抽出ステップにおいて次のサーチキーの抽出を行なうよう処理する。
【００３１】
好ましくは、第１のデータ群および第２のデータ群に含まれるデータは、Ｘ座標およびＹ座標のデータを含む。
【００３２】
この発明の他の局面に従うと、データ処理プログラムは、第１のデータ群に含まれるデータと、第２のデータ群に含まれるデータとを比較照合するデータ処理プログラムであって、第１のデータ群または第２のデータ群のうち、データ数の少ないほうをサーチキーとし、多いほうをソースデータと定義する定義ステップと、第１のデータ群と第２のデータ群とをまとめた上で、ソートを行なうソートステップと、ソートステップにおいてソートされたデータのうち、サーチキーの各々に対して、次のサーチキーのアドレスを記録する記録ステップと、記録ステップにより記録されたアドレスに基づいて、ソートされたデータの中から、ソートの順番にサーチキーを抽出する抽出ステップと、抽出されたサーチキーの位置から、ソートにおける次の順序のデータを取得する取得ステップと、取得されたデータがサーチキーであるか否かを判定する判定ステップと、判定ステップにおいて、取得されたデータがサーチキーであると判定された場合には、ヒットデータは無いものとして、抽出ステップにおいて次のサーチキーの抽出を行なうよう処理する処理ステップと、判定ステップにおいて、取得されたデータがサーチキーではないと判定された場合には、取得されたデータがサーチキーのデータと一致するか否かを照合する照合ステップとをコンピュータに実行させる。
【００３３】
この発明のさらに他の局面に従うと、コンピュータ読取可能な記録媒体は、上述のデータ処理プログラムを記録する。
【００３４】
この発明のさらに他の局面に従うと、データ処理装置は、第１のデータ群に含まれるデータと、第２のデータ群に含まれるデータとを比較照合するデータ処理装置であって、第１のデータ群または第２のデータ群のうち、データ数の少ないほうをサーチキーとし、多いほうをソースデータと定義する定義手段と、第１のデータ群と第２のデータ群とをまとめた上で、ソートを行なうソート手段と、ソート手段においてソートされたデータのうち、サーチキーの各々に対して、次のサーチキーのアドレスを記録する記録手段と、記録手段により記録されたアドレスに基づいて、ソートされたデータの中から、ソートの順番にサーチキーを抽出する抽出手段と、抽出されたサーチキーの位置から、ソートにおける次の順序のデータを取得する取得手段と、取得されたデータがサーチキーであるか否かを判定する判定手段と、判定手段において、取得されたデータがサーチキーであると判定された場合には、ヒットデータは無いものとして、抽出手段において次のサーチキーの抽出を行なうよう処理する処理手段と、判定手段において、取得されたデータがサーチキーではないと判定された場合には、取得されたデータがサーチキーのデータと一致するか否かを照合する照合手段とを備える。
【発明を実施するための最良の形態】
【００３５】
図１は、本発明の実施の形態の１つにおけるデータサーチ装置の構成を示すブロック図である。図を参照して、データサーチ装置は、装置全体の制御を行なうＣＰＵ１０８と、フレキシブルディスクドライブやＣＤ−ＲＯＭドライブにより構成される外部記憶装置１００と、ハードディスクやＲＡＭなどにより構成される記憶装置１０２と、データのサーチ結果などを表示するためのディスプレイ１０４と、外部との間でデータのやり取りを行なう通信部１０６と、キーボードやマウスなどにより構成される入力装置１１０と、サーチ結果などをプリントするプリンタ１１２とから構成されている。
【００３６】
データサーチ装置を駆動するためのデータサーチプログラムは、ＣＤ−ＲＯＭ１００ａや、フレキシブルディスク１００ｂなどの記憶媒体により提供される。また、データサーチプログラムは通信部１０６などを介して外部から装置へ入力させるようにしてもよい。
【００３７】
また、データサーチの対象となるデータも外部記憶装置１００や通信部１０６を介して入力される。
【００３８】
図２および図３は、図１のデータサーチ装置が実行するデータサーチプログラムの処理を示すフローチャートである。
【００３９】
図を参照して、ステップＳ１において、図１の記憶装置１０２に、円形データ保持用のメモリ領域（Ａ層、Ｂ層データ合計数量分）を一括して確保する。メモリ領域として、以下のデータを記録する領域が確保される。
【００４０】
（１）  ロケートＸ座標
（２）  ロケートＹ座標
（３）  データ属性
（４）  データ後方アドレス
ステップＳ３において、Ａ層のデータのロードが行なわれる（構造体のデータチェインにデータをストアする）。ストアするデータは、Ｘ座標、およびＹ座標である。
【００４１】
ステップＳ５において、Ｂ層のデータのロードが行なわれる（上記構造体のデータチェインにデータを追加し、ストアする）。ストアするデータは、Ｘ座標、およびＹ座標である。
【００４２】
ステップＳ７において、サーチキー／ソースデータの属性のアサインが行なわれる。本実施の形態においては、Ａ層、Ｂ層のうち、データ数量の少ないほうをサーチキーとし、多いほうをソースデータとしている。たとえば、Ａ層データが図１６、Ｂ層データが図１７に示されるものであるとすると、Ａ層のほうがデータ数量が少ないため、Ａ層＝サーチキー、Ｂ層＝ソースデータと定義される。
【００４３】
ステップＳ９において、データチェインのすべてのデータを以下のファクタによって昇順にソートする。
【００４４】
第１優先：Ｘ座標
第２優先：Ｙ座標
第３優先：データ属性（サーチキーがソースデータより上になるように設定する）
すなわち、データのソートにおいては第１にＸ座標が参照される。Ｘ座標が同じデータが２つある場合には、Ｙ座標順にデータがソートされ、Ｘ座標もＹ座標も同一のデータがあれば、データ属性（サーチキーであるかソースデータであるか）に基づきソートが行なわれる。
【００４５】
ステップＳ１１において、サーチキーについて、後方（次点）データのメモリアドレスを調査して、後方アドレス管理フィールドにそのアドレスをストアする。また、サーチキーのトップアドレスを調査して、メモリの変数にストアしておく。
【００４６】
ステップＳ１３（図３）において、サーチキー参照ポインタのアドレスをセットする。一番最初の検索開始時には、データソート時に保持したトップアドレスにサーチキー参照ポインタはセットされる。その後、検索ループの処理ごとに、サーチキー参照ポインタは後方のアドレスに移動する。後方アドレスの割出しは、現行のサーチキー参照ポインタが参照しているアドレスのサーチキー後方アドレス管理フィールドよりアドレスデータを取得することで行なわれる。この際、取得したアドレスデータがＮＵＬＬの場合は、データチェインの終端であると判断し、検索ループの処理を終了する。
【００４７】
ステップＳ１５において、サーチキー参照ポインタからオフセットさせたアドレスに保持されているデータの属性がチェックされる。
【００４８】
すなわち、現行のサーチキー参照ポインタが指すアドレスから、１要素分オフセットさせたアドレス（「オフセットアドレス」ともいう。）に保持されているデータの属性が、サーチキーであるかを判断する。
【００４９】
ここで、サーチキーである場合、サーチキーデータがメモリアドレス上に連続してマッピングされていることを示している。図１６、１７に示されるように、同一の層において同一座標のデータが重複することは無く、また、データはＸ、Ｙ座標をキーにした昇順ソートを行なっている。従って、連続している同一属性のデータの座標位置は、必ず異なっていると判断できる。また、検索対象となるソースデータのアドレスは、オフセットアドレスよりも必ず後方に存在する。
【００５０】
従って、オフセットアドレスに保持されているデータの属性が、サーチキーである場合は、ソースデータの座標位置は、オフセットアドレスに保持されている（サーチキーの）座標位置と同一、もしくは異なっていると判断できる。
【００５１】
これにより、現行のサーチキー参照ポインタが指すアドレスに記録されたサーチキーに対応する座標のソースデータは存在しないことを判断することができ、コストをかけることなく（座標位置の照合検査を行なわずに）、ヒットデータは無いと判断でき、次のサーチキーの処理に移る（ステップＳ１３に戻る）。
【００５２】
ステップＳ１５において、オフセットアドレスに保持されているデータの属性が、サーチキーではないと判定された場合、オフセットアドレスに保持されているデータの属性は、ソースデータである。ソースデータがどのような座標データを有しているかは予測不可能であるため、ソースデータ参照ポインタを、オフセットアドレスにセットし、ステップＳ１７で照合処理を行なう。
【００５３】
ステップＳ１７において、座標データ比較照合処理が行なわれる。ここでは、ソースデータ参照ポインタが参照しているアドレスのＸ，Ｙ座標データフィールドより、Ｘ，Ｙ座標データを取得する。一方、サーチキー参照ポインタが参照しているアドレスのＸ，Ｙ座標データフィールドのＸ，Ｙ座標データを取得し、取得された両座標データを比較照合する。
【００５４】
座標データ比較の処理結果は、以下の２種類のうちのいずれかの属性で管理する。
【００５５】
（１）  Ｘ，Ｙ座標が異なる
（２）  Ｘ，Ｙ座標がいずれも同一である
座標比較処理結果により、以下の処理の分岐を行なう。
【００５６】
（１）の場合、ソースデータの走査を中断（見込み中断）し、サーチキーの次点の設定に戻る（Ｓ１３へ）。
【００５７】
このように、検索処理の見込み中断を行なうのは、以下の理由による。座標データは、Ｘ，Ｙ昇順にソートされているため、比較の結果、座標が異なった場合には、それ以降走査を継続しても、同一の座標データが出てくることはあり得ない。そこで、検索処理（ソースデータの読出および照合）を中断して、不要な処理がマシンサイクルを消費することを防止する。これにより、処理時間の短縮を図る。すなわち、Ｘ，Ｙ座標における位置が乖離したデータは比較処理を行なわないのである。
【００５８】
（２）の場合、同一座標検出処理を行なった後、サーチキーの次点の設定に戻る（Ｓ１３へ）。
【００５９】
このように、サーチキーの次点の設定を行なうのは、以下の理由による。座標データは、Ｘ，Ｙ昇順にソートされており、かつ同一層に同一のデータはないため、ソースデータ参照ポインタより後方のアドレスが保持している座標データは、現行のサーチキー参照ポインタが参照しているアドレスの保持している座標データとは必ず異なっている。そのため、それ以降走査を継続しても、同一の座標データが出てくることはあり得ない。そこで、検索処理（ソースデータの読出および照合）を中断して、不要な処理がマシンサイクルを消費することを防止する。これにより、処理時間の短縮を図る。
【００６０】
次に、各ステップで行なわれる処理の具体例について説明する。
【００６１】
［ステップＳ３：Ａ層データロード］
たとえば、Ａ層のデータが図１６に示されるものであった場合、ステップＳ３の処理が完了した時点の、データチェインのデータ内容を表概念で表わすと、図４のようになる。図４において、空白の欄はＮＵＬＬ（無効、この場合はデータが保持されていない状態）を示す。
【００６２】
なお、本実施の形態においてもメモリアドレスは仮定のものである。
【００６３】
図４に示されるように、メモリアドレス＆１〜＆６２のうち、＆１〜＆２０の部分に、Ａ層のデータＡ１〜Ａ２０が記録されている。それぞれのアドレスにおいてＡ層のデータのＸ座標、Ｙ座標が記録されている。また、データチェインにはサーチキー後方アドレスを記録する部分が設けられているが、この段階ではまだこれらのデータは記録されていない。
【００６４】
［ステップＳ５、Ｓ７：Ｂ層データロード、サーチキー／ソースデータ属性アサイン］
ステップＳ５およびＳ７の処理が完了した時点のデータチェインのデータ内容を表概念で表わすと図５に示されるものとなる。ここでは、図４のデータに続いて、図１７のＢ層のデータがロードされた状態を示している。図に示されるように、＆１〜＆２０のＡ層のデータに続けて、アドレス＆２１〜＆６２に、Ｂ層の１〜４２のデータがロードされている。
【００６５】
アドレス＆２１〜＆６２においても、Ｂ層のデータのＸ座標、Ｙ座標が記録されている。
【００６６】
また、ステップＳ７においては、Ａ層（図１６）およびＢ層（図１７）の両データに対して、サーチキー／ソースデータの属性をデータの数に基づき決定する。
【００６７】
サーチキーは検索条件を決定する要素となり、ソースデータは検索条件に沿って検索される被走査対象として機能する。本実施の形態におけるデータサーチアルゴリズムにおいては、サーチキーの数量がソースデータの数量よりも少ない場合に検索処理回数が減少する（処理時間短縮に有効に作用する）という特性を有する。したがって、Ａ層またはＢ層のデータのうち、データ数の少ないほうがサーチキーとされ、データ数の多いほうがソースデータとされる。
【００６８】
なお、Ａ層およびＢ層のデータの数量はデータロード時に取得することができる。このように、データ数の少ないほうをサーチキーとすることによる効果については、後に説明する。
【００６９】
［ステップＳ９：データチェインの全データを昇順ソート］
図５に示されるデータを、Ｘ座標、Ｙ座標およびデータ属性（サーチキーがソースデータよりも上になるように設定）の優先順でソートした結果を、図６に示す。なお、「サーチキーがソースデータよりも上になるように設定」とは、Ｘ，Ｙ座標データがともに同一のサーチキー、ソースデータがあった場合、サーチキーデータのほうがソースデータよりもメモリアドレス上で前方（上位）に位置するようにソートすることをいう。図６においては、＆１および＆２、＆４および＆５などの部分がデータ属性に基づいてソートが行なわれた部分を示している。
【００７０】
図６に示されるように、図５のサーチキーとソースデータとはソートにより混在した状態でメモリアドレス＆１〜＆６２に並べ替えられて記録される。ここで並べ替えは前述のようにＸ座標、Ｙ座標、データ属性の優先順に行なわれる。
【００７１】
［ステップＳ１１：サーチキーの後方データのメモリアドレスのストア］
サーチキーの後方データのメモリアドレス（後方アドレス）とは、サーチキーにおいて、真下（隣）のデータがストアされている位置をいう。この後方アドレスは、データを検索走査する際のインデックス（道しるべ）として使用される。
【００７２】
図７は、図６の状態においてサーチキー後方アドレスが付与された状態を示す図である。たとえば、メモリアドレス＆１のサーチキー後方アドレスの欄には、「＆４」が記録されているが、これは、＆１の次のサーチキーは、＆４のアドレスに格納されていることを示している。
【００７３】
また、＆５９のサーチキー後方アドレスは、＆５９より後方（下位）のメモリアドレスにはサーチキーデータが存在しないため、ＮＵＬＬとなっている。
【００７４】
［ステップＳ１３〜Ｓ１７：座標データ比較照合処理など］
ステップＳ１３〜Ｓ１７での処理の詳細を以下に示す。
【００７５】
（１）  サーチキー参照ポインタのアドレスセット（Ｓ１３）
サーチキー参照ポインタを、サーチキーデータのトップアドレス＆１にセットする（サーチキー参照ポインタ＝＆１）。なお、トップアドレスはデータソート時に保持した変数より取得する。以下、順にサーチキー後方アドレスが示すアドレスを参照することで、順次サーチキーを参照することとなる。
【００７６】
（２）  オフセットアドレス保持データの属性チェック（Ｓ１５）
サーチキー参照ポインタの参照アドレス＆１のオフセットアドレスである、アドレスデータ＆２を取得する（オフセットアドレス＝＆２）。オフセットアドレスのデータ属性が、サーチキーである場合には、ステップＳ１３に戻り、そのオフセットアドレスに、サーチキー参照ポインタがセットされる。
【００７７】
また、オフセットアドレスのデータ属性が、サーチキーでない場合には（サーチキー参照ポインタが例えば図７の＆１の場合は）、ステップＳ１７で座標照合処理を行なう。
【００７８】
（３）  座標データ比較照合処理（Ｓ１７）
サーチキー参照ポインタが参照している、アドレス＆１のＸ，Ｙ座標データフィールドが保持している座標データ（Ｘ＝１．０００，Ｙ＝１．０００）と、ソースデータ参照ポインタが参照している、アドレス＆２のＸ，Ｙ座標データフィールドが保持している座標データ（Ｘ＝１．０００，Ｙ＝１．０００）を比較照合する。ここでは、同一座標であるため、同一座標検出処理を実行する。
【００７９】
同一座標でない場合には、同一でなかった旨を記録する。
【００８０】
（４）  サーチキー参照ポインタの移動（Ｓ１３）
サーチキー参照ポインタが示す位置の、サーチキー後方アドレスフィールドより、アドレス＆４を取得して、サーチキー参照ポインタを移動する（サーチキー参照ポインタ＝＆４）。
【００８１】
（５）  オフセットアドレス保持データの属性チェック（Ｓ１５）
サーチキー参照ポインタの参照アドレス＆４のオフセットアドレスである、アドレスデータ＆５を取得する（オフセットアドレス＝＆５）。オフセットアドレスのデータ属性が、サーチキーである場合には、ステップＳ１３に戻り、そのオフセットアドレスに、サーチキー参照ポインタがセットされる。
【００８２】
また、オフセットアドレスのデータ属性が、サーチキーでない場合には（サーチキー参照ポインタが例えば＆４の場合は）、ステップＳ１７で座標照合処理を行なう。
【００８３】
（以下省略）
（ｚ）  サーチキー参照ポインタのアドレスセット（Ｓ１３）
サーチキー参照ポインタの参照アドレス＆５９のサーチキー後方アドレスフィールドより、次点のアドレスを取得しようとするものの、データはＮＵＬＬである。これにより、＆５９がサーチキーのデータの終端であると判断し、検索処理を終了する（すべてのサーチキー比較照合処理は＆５９をもって完了する）。
【００８４】
以下に、本実施の形態における特徴を説明する。
【００８５】
（１）  検索元条件となるデータ（サーチキー）と、検索先のデータ（ソースデータ）とを、同一のデータチェインに保持して、Ｘ，Ｙ座標をキーとした昇順ソートを行なう（データ属性をキーとしたソートの効果については後述）。
【００８６】
これにより、サーチキー設定後のソースデータ検索走査開始時のエントリポインタを直近のデータに設定することが可能となり、配置（位置）上で乖離したデータをチェックする無駄が省ける。
【００８７】
（２）  上記(１)のソートの際、データの属性をキーとして含める。このとき、サーチキーがソースデータよりもメモリアドレスにおいて前方（上位）になるように設定する。
【００８８】
これにより、ソースデータの検索走査方向を、メモリアドレスにおいて後方（下位）のみにすることが可能になり、前方まで検索することを省略することができる。
【００８９】
以下に、データの属性をキーとして含めたソート処理の有無による検索走査処理の違いを説明する。
【００９０】
図８は、データ属性をキーとして含めたソート処理を行なわない場合のデータの配置例を示す図である。このように、データの属性をキーとしてソートを行なわない場合、サーチキーおよびソースデータの両方に同一の座標のデータがあった場合、どちらが前方に位置するかが不明である。
【００９１】
たとえば、図８の例においては＆１および＆２の場合は、サーチキーがソースデータよりも前方になっているが、＆４および＆５の場合はソースデータがサーチキーよりも前方になるといったケースが起こり得る。この場合、サーチキーデータの設定後のソースデータ検索走査は、前方および後方の両方向に行なわなければならない。すなわち、＆５の場合、＆４および＆６への検索走査を行なわなければならないといった無駄な検索走査が必要となる。また、データチェインにおいて属性別の前方アドレス管理の必要が生じるため、メモリの消費が大きくなるという弊害が発生する。
【００９２】
図９は、データ属性をキーとして含めたソート処理を行なった場合のデータの配置例を示す図である。
【００９３】
本実施の形態のように、データ属性をキーとして含めたソートを行なうことで、サーチキーおよびソースデータの両方に同一の座標からなるデータがあった場合でも、サーチキーのほうがソースデータの位置よりも必ず前方に位置することが保証される。たとえば、図９においては＆１および＆２、＆４および＆５のいずれの場合も、サーチキーがソースデータよりも前方に位置している。これにより、サーチキーデータ設定後のソースデータ検索走査は、後方のみに行なえばよいことになり、無駄な検索走査を省くことができる（＆４の場合、＆５のみの検索走査が行なわれる）。
【００９４】
また、本実施の形態においては属性別に前方アドレスを管理する必要がなくなるため、メモリ消費を抑制することができる。
【００９５】
（３）  データ属性別の後方アドレス情報を管理する。
【００９６】
これにより、サーチキー参照ポインタを、無駄なく移動することが可能になり、処理時間の短縮が図られる。もし、後方アドレス情報を管理していない場合、メモリアドレスを１つずつシフトして、データ属性をチェックするといった工程が必要となり、処理時間の増大につながる。
【００９７】
図１０は、後方アドレス情報を管理しない場合のデータを示す図である。図１０において、サーチキー参照ポインタの移動について考察する。まず、アドレス＆１の処理が完了すると、次のサーチキーデータ＆４にポインタを移動させなければならないが、次のサーチキーのデータアドレス（＆４）は管理されていないため、ポインタは１つシフトして＆２に移動させなければならない。
【００９８】
＆２にポインタが移動後、＆２のデータ属性をチェックして、サーチキーであるかを確認することになるが、ここではソースデータであることが判明することになる。そこで、さらにポインタを１つシフトさせて、＆３に移動させ、同様にデータの属性をチェックする。ここでも結果がＮＧであるため、再度ポインタを１つシフトさせ、＆４に移動させる。ここで属性チェックを行なった結果、サーチキーであることが判明し、以降の検索処理に移ることが可能となる。
【００９９】
以上に示したように、後方アドレス情報がない場合は、１つ刻みのポインタシフトと、その都度の属性チェック処理が必要となるため、処理時間の増大につながる。これに対し、本実施の形態においては後方アドレスをサーチキーにおいて管理することにより、迅速な処理を行なうことが可能である。
【０１００】
（４）  サーチキー参照ポインタアドレスから、１要素分オフセットさせたアドレス（オフセットアドレス）に保持されているデータの属性が、「サーチキー」であるかをチェックし、サーチキーである場合には、ソースデータを走査する処理を行なわず、サーチキーの次点設定に戻る。
【０１０１】
すなわち、図１１を参照して、サーチキー参照ポインタがアドレス＆１１を参照している場合、オフセットアドレスは、＆１２である。
【０１０２】
＆１２のアドレスが保持しているデータの属性は、サーチキーである。これは、サーチキーのデータがメモリ上で連続してマップされていることを示している（＆１１、＆１２）。
【０１０３】
このことと、以下の前提条件を考慮すると、連続している同一属性のデータの座標位置は、必ず異なっていると断定できる。
【０１０４】
（条件１）  同一層における座標位置のデータの重複は許容されていない。
【０１０５】
（条件２）  データは、Ｘ、Ｙ座標をキーに昇順にソートされている。
【０１０６】
従って、＆１１と＆１２の座標データは必ず異なることがわかる。
【０１０７】
そして、走査対象となるソースデータは、オフセットアドレス（サーチキーデータ）＆１２よりも後方に存在するため、現行のサーチキー参照ポインタ＆１１の座標データと一致することはありえない。
【０１０８】
以上より、同一属性（サーチキー）のデータがメモリ上で連続してマップされている場合には、ソースデータの走査は必要ではないことをコストをかけることなく（座標位置の比較照合を行なわずに）判断できる。
【０１０９】
（５）  サーチキーとソースデータの属性は、各データ数量をチェックした上で動的に割当てる。
【０１１０】
上記で説明したように、本実施の形態におけるデータサーチアルゴリズムでは、サーチキーはすべてのデータが走査されるが、ソースデータは部分走査で処理完了となる可能性が高い。このため、サーチキー数量＜ソースデータ数量の場合に、最大のパフォーマンスが発揮される。
【０１１１】
したがって、もし事前にＡ層＝サーチキー、Ｂ層＝ソースデータと決めてしまった場合、Ａ層のデータ数量がＢ層より少ない場合にはよいが、その逆の場合にはパフォーマンスが最大にならない。これに対し、本実施の形態においてはデータの属性を動的に割当てることで、常に最大のパフォーマンスが発揮できるようにしている。
【０１１２】
たとえば、図１２のＮ層データと、図１３のＭ層データとを比較する場合を例に挙げ説明する。Ｎ層データは、円形データを１つだけ有し、Ｍ層データは円形データを４２個有している。
【０１１３】
本実施の形態のように、データ数の少ないほう（Ｎ層データ）をサーチキー、多いほう（Ｍ層データ）をソースデータとする場合の検索処理は、以下のように行なわれる。
【０１１４】
（１）  Ａ１（図１２のＮ層データ）と、２６（図１３のＭ層データ）の座標データを比較して、同一座標かをチェックする（結果は同一座標）。
【０１１５】
ここで、サーチキーデータの比較照合処理が完了となる。
【０１１６】
これに対して、逆にＮ層データをソースデータとし、Ｍ層データをサーチキーとした場合の検索処理は以下のようになる。
【０１１７】
（１）  １（Ｍ層データ）の次に、ソートされたサーチキーである２（Ｍ層データ）が連続することとなるため、ソースデータの検索は行なわず、サーチキー２の処理に移る。
【０１１８】
（２）  ２（Ｍ層データ）の次に、ソートされたサーチキーである３（Ｍ層データ）が連続することとなるため、ソースデータの検索は行なわず、サーチキー３の処理に移る。
【０１１９】
（途中省略）
（２６）  ２６（Ｍ層データ）の次に、ソースデータＡ１（Ｎ層データ）が続くため、２６とＡ１の座標データを比較して、同一座標かをチェックする（結果は同一座標）。
【０１２０】
（途中省略）
（４２）  ４２（Ｍ層データ）の次に、サーチキーもソースデータもないため、処理を中断する。
【０１２１】
以上で、すべてのサーチキーデータの比較照合処理が完了する。
【０１２２】
上述のように、図１２および図１３の例の場合、本実施の形態のように数の少ないＮ層データをサーチキーとした場合には、１回の比較処理で検索が終了するのに対し、Ｎ層データをソースデータとした場合には、４２回の処理が必要となってくる。
【０１２３】
これは、サーチキーとなるデータは全走査が行なわれるが、ソースデータの場合は部分走査で済む可能性が高いためである。
【０１２４】
なお、図１４は上記処理を実行する具体的なプログラムを示す図である。
【０１２５】
［実施の形態における効果］
以上に説明したように、本実施の形態におけるデータサーチアルゴリズムを採用することにより、不要な処理を低減させることができ、パフォーマンスの向上が可能になる。
【０１２６】
図１５は、本実施の形態における効果を示す図である。
【０１２７】
テストケースとして、サーチキー数５０００〜１０００００、ソースデータ数２０００００〜１００００００の円形データを用いて（理論上１０億〜２００億通りの座標データの組合せ）、従来および本実施の形態におけるアルゴリズムでのベンチテストを行なったところ、図１５に示されるような結果を得た。
【０１２８】
全ての状況において、上記のテストケースでは、良好なパフォーマンスの向上を得ている。特にサーチキーの数が少なく、かつソースデータ数が多い場合に、パフォーマンスの向上度がよい。また、本実施の形態によると、処理速度がソースデータの数による影響を受けにくく、サーチキーの数の影響を受けやすい、という特徴がある。
【０１２９】
なお、上述の実施の形態においてはＣＡＤの円形データを用いて説明を行なっているが、本発明の適用範囲は実施の形態に記載された例に限らず、データがソート可能なもの（上下関係を持つもの、たとえば文字データなど）であれば適用することができる。また、表面上では上下関係を持たないデータでも（たとえば色データなど）上下関係を付与することにより、本発明を適用することが可能となる。
【０１３０】
なお、上述の実施の形態においてはソフトウェアによる処理を行なうこととしたが、ハードウェア回路を用いて上述の処理を行なうようにしてもよい。
【０１３１】
また、上述の実施の形態による処理は、ネットワークに接続されたシステムにおいても、ネットワークに接続されていないシステムにおいても適用することができる。
【０１３２】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【０１３３】
【図１】本発明の実施の形態の１つにおけるデータサーチ装置の構成を示すブロック図である。
【図２】図１のデータサーチ装置が実行するデータサーチプログラムの処理を示すフローチャートである。
【図３】図２に続くフローチャートである。
【図４】Ａ層のデータがロードされた後のデータチェインの内容を示す図である。
【図５】Ｂ層のデータがロードされ、データ属性が決定された時点のデータチェインの内容を示す図である。
【図６】データの昇順ソートがなされた後のデータチェインの構成を示す図である。
【図７】図６の状態から後方アドレスが付与された状態を示す図である。
【図８】本発明の効果を説明するための第１の図である。
【図９】本発明の効果を説明するための第２の図である。
【図１０】本発明の効果を説明するための第３の図である。
【図１１】本発明の効果を説明するための第４の図である。
【図１２】Ｎ層データの例を示す図である。
【図１３】Ｍ層データの例を示す図である。
【図１４】データサーチプログラムの具体例を示す図である。
【図１５】本発明の効果を説明するための第５の図である。
【図１６】Ａ層データの具体例を示す図である。
【図１７】Ｂ層データの具体例を示す図である。
【図１８】従来のデータサーチアルゴリズムを示すフローチャートである。
【図１９】Ａ層データチェインのデータ保持内容を示す図である。
【図２０】Ｂ層データチェインのデータ保持内容を示す図である。
【符号の説明】
【０１３４】
１００  外部記憶装置、１０２  記憶装置、１０８  ＣＰＵ、１１０  入力装置。
【図１】
2006201956.tif 000003
【図２】
2006201956.tif 000004
【図３】
2006201956.tif 000005
【図４】
2006201956.tif 000006
【図５】
2006201956.tif 000007
【図６】
2006201956.tif 000008
【図７】
2006201956.tif 000009
【図８】
2006201956.tif 000010
【図９】
2006201956.tif 000011
【図１０】
2006201956.tif 000012
【図１１】
2006201956.tif 000013
【図１２】
2006201956.tif 000014
【図１３】
2006201956.tif 000015
【図１４】
2006201956.tif 000016
【図１５】
2006201956.tif 000017
【図１６】
2006201956.tif 000018
【図１７】
2006201956.tif 000019
【図１８】
2006201956.tif 000020
【図１９】
2006201956.tif 000021
【図２０】
2006201956.tif 000022