JPH04199364A - 曖昧さを持つ検索方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、地図上の任意の点の周辺に存在する商店の探
索やプリント基板上の任意の点の周辺に存在する部品ピ
ン群やスルーホール群の探索に好適な探索方法に関する
。

［従来の技術］ ｎ次元空間中で検索点を中心として半径ｒの範囲に存在
するデータの検索を行う方法については特開平２−１１
２０７１ｒ情報検索方法」にある。

また、２分探索法に関してはオーム社から１９８７年に
発刊されている「現代データ構造とプログラム技法」で
実現方法について詳細に論しられている。

〔発明が解決しようとする課題］ 上記特開平２−１１２０７１ｒ情報検索方法」に記載の
従来技術は、曖昧さを持つデータ検索方法についての概
念を記述しているが、その具体的な実現手段については
論しられていない。

また、上記従来技術である２分探索方法では、探索条件
に一致する場合、しない場合の２通りの実現方法につい
て論しられているが１条件に一致するデータが存在しな
い場合、与えられた条件の近傍に位置するデータを捜し
だす方法については論じられでいなかった。このため、
データか一致しない場合の探索を高速で行うためには、
まず２分探索法で検索条件データの有無を調べ、データ
が存在しない場合に条件を再設定し再トライするという
手続きが必要であった。

このように、従来技術は、一致データが存在しない場合
検索データが被検索データ列のどの辺りに位置するかと
いう様な曖昧さを持ったデータの検索については考慮さ
れておらずソフトウェア開発時負担になっていた。

本発明は、データ検索時検索キーの近くに位置するデー
タを探すという曖昧さを持った条件でデータを検索し、
条件を満足するデータやデータ群を高速に捜しだすこと
を目的とする。

［課題を解決するための手段］ 上記目的を達成するため、中央処理装置（ｃｐｕ）と、
出力手段と、入力手段と、メモリとを有するコンピュー
タシステムを用いたデータの検索方法において、上記コ
ンピュータのメモリ上に登録した上昇順または下降順に
並べたデータの中から、指定された検索条件に従い２分
探索法でデータを検索し、一致するデータが存在すれば
このデータを出力し、条件が一致するデータが上記デー
タ列の中に無い場合、検索条件から上および下にそれぞ
れ指定された巾に入る（以下、検索条件に近いという）
１または２以上のデータからなるデータ群を上記データ
列の中から捜し、検索条件に近い１または２以上のデー
タが存在すればそのデータを出力し、曖昧さを含む条件
でデータを検索することとしたものである。

［作　用］ 検索対象データをコンピュータのメモリ上に展開し、昇
順に並べる。また検索キーと一致するものが無い場合に
上記検索キーとどの程度迄を近いと判断するかの曖昧さ
を表す条件を外部より指示する。

この条件が揃った段階で、まず指示された検索キーを用
いて２分探索法を行う。この時検索キーと一致するもの
が存在すればそのデータを出力する。

もし一致するものが無い場合、２分探索法で検索した最
後のデータ位置が最も指示検索キーに近いデータ位置で
あるため、この位置から検索キーと曖昧さを持つ条件を
合わせた条件でデータの前方向に条件を満たさなくなる
まで順次探索し１次に後方に同じ方法で探索し条件を満
たすデータ群を捜しだしそのデータを出力する。

［実施例コ 以下、本発明の第１の実施例を第１図により説明する。

第１図は、本発明を構成するコンピュータの図である。

メモリ２には探索対象になるテーブル及び本発明による
プログラムを格納する。ＣＰＵＩはこのメモリ内のプロ
グラムを動作させ本発明による探索方法を実行させる。

ＣＲＴ３は実行の開始を指示する、或いは実行結果を表
示するために使用する。

第２図は、本発明を実施するに当り必要となる領域の、
メモリ２上での概念図とその相互関係を表わしたもので
ある。

ここには、探索対象となるテーブル２１及び探索キーが
セットしであるエリアＰＡ２２、近傍という曖昧さを記
録しであるエリアＰＢ２３、探索結果範囲の開始点を格
納するエリアＲＦ２４、終了点を格納するエリアＲＴ２
５が、従来の２分探察方法による結果を記録するテーブ
ルポインタＳＰ２が準備されている。

ここでテーブルＴ２１には探索対象となるｎ個のデータ
が昇順に並べられ登録されており、エリアＰＡ２２には
探索キーの値ｋが、エリアＰＢ２３には探索の結果、一
致するデータが存在しない場合に、どの範囲までを近傍
とするか判断する値ｒがセットされている。

第３図は、第２図に示すデータを用いた、本発明の実施
例のフローチャートを示したものである。

まず、従来の２分探索方法による探索４１を行う。

この結果から判断ボックス４１１でエリアＰ　Ａ、　２
２中の探索キーにの近傍に位置するデータが存在するか
否かを判断する。

この時、２分探索結果であるテーブルポインタ５Ｐ２６
が示すテーブルＴ２１上のデータの値が探索キーｋを含
む曖昧さを示すエリアＰＢ２３中の値の範囲外であれば
存在しないという条件が成立する。

この場合には処理４１２で近傍点無しの意味を持つパラ
メータを返却し、処理を終了する。

次に、近傍点がある場合は、判断処理４２で探索キーに
と一致するデータが存在するか否かテーブルＴ２１上の
収束点の値と比較を行い、探索キーにと一致するデータ
がテーブルＴ２１の中に無かった場合、曖昧さを加味し
た探索を実行する。

この時、テーブルＴ２１を検索するためのテーブルポイ
ンタ５Ｐ２６中のポインタの値は、テーブル２１中でも
最も探索キーに近い値を持つ位置がｍであるとすれば２
分探索の結果である収束点の探索ポインタの値は最後の
探索点であるｍの位置を示している。

ここで、有効データ範囲の終了位置を見つけるための探
索を実施する。

まず、２分探索結果のｍの値をエリアＲＴ２５にセット
する処理４２１を実施し、後側の範囲探索を行うため、
処理４４でエリアＲＴ２５の値を更新し、テーブル２１
内のデータに着目し近傍のデータかどうかを判断するた
めに比較処理４５を行う。

この時エリアＲＴ２５の値がｊでありＴ（ｉ）＞　ｋ、
　＋　ｒの関係となっている場合、ｉより後方には有効
データは存在しない事が自明でありデータの終了位置は
ｉ−１となるため処理４６でこれを行う。

しかし、　Ｔ　（ｉ）≦に十ｒの関係が成立する場合、
まだ後方に有効データが存在する事が考えられるためさ
らに後方のデータ探索を行う必要があるが１着目してい
るデータがテーブルＴ２１の最後のデータである場合、
処理４５１でこれを判断する。エリアＲＴ２５の値は、
処理４５３でテーブルＴ２１の有効数とする。

着目しているデータがテーブルＴ２１の最後のデータで
はない場合には、ループ４５２で後方探索を続行する。

そしてＴ（ｉ）＞ｋ＋ｒの関係が成立するまでこれを繰
り返す。

この関係が成立すると処理４６に進み、エリアＲＴ２５
の値を決定する。この時のこの点のデータは範囲外であ
るため有効範囲の終了位置は１−１となる。

次に、有効データ範囲の開始位置を見つけるための探索
を実施する。

まず、２分探索結果のｍの値をエリアＲＦ２４にセット
する処理４７１を実施し、前側の範囲探索を行うため処
理４７でエリアＲＦ２４の値を更新する。そしてテーブ
ル２１中のデータに着目し、近傍のデータか判断するた
めに比較４５を行う。

この時エリアＲＦ２４の値かでｉありＴ　（ｉ）＜　ｋ
　−ｒの関係となっているる場合、ｉより前方には有効
データは存在しない事が自明でありデータの終了位置は
ｉ＋１となるため処理４７でこれを行う。

しかし、Ｔ　（ｉ）≧に＋ｒの関係が成立する場合、ま
だ前方に有効データが存在する事が考えられるためさら
に前方のデータ探索を行う必要がある。そこで１着目し
ているデータがテーブルＴ２１の先頭のデータであるか
どうか処理４８１でこれを判断し、先頭の場合は、エリ
アＲＦ２４の値は、処理４８３で１とし、先頭のデータ
ではない場合には、ループ４８２で前方探索を続行する
。

そしてＴ（ｉ）＜ｋ−ｒの関係が成立するまでこれを繰
り返す。

この関係が成立すると処理４９に進みエリアＲＦ２４の
値を決定する。

この時この点のデータは範囲外であるため有効範囲の開
始位置はｉ＋１となる。

２分探索法で一致するデータがテーブル２１の中に存在
する場合には、処理４３でエリアＲＦ２４＝エリアＲＴ
２５＝２分探索結果ｍとして処理を終了する。

第１の実施例の動作の説明は１以上である。

本実施例において、テーブルを探索キーで昇順に並へる
のは２分探索を行うための必須条件になっているためと
、曖昧さを持つデータの範囲を探索する際に少ない探索
回数で済むためである。

また、開始側、終了側の値を外部インタフェースとして
持つことにより、曖昧さを持った探索の結果、テーブル
上の連続した複数のデータが選択された場合、その開始
点と終了点を返却することが出来る。

また、条件を満足するデータが発見出来なかった場合開
始点側の値〉終了点側の値とするのは、プログラム作成
上の効率を上げようとするもので。

ＤＯループの開始点終了点にこの値を用い九ば。

特別な判定文を入れなくても処理がスキップされるため
である。

また、探索キーと一致するデータが発見出来た場合開始
点側の値＝終了点側の値とするのも同様の理由による。

第２の実施例を第４図で説明する。

第３図との違いは２分探索法で一致データが発見された
場合でも一致データの近傍に存在するデータを探索する
点であり、第３図の判断処理４２及び処理４３を取り除
くことにより実現できる。

同一値を持つデータが連続してテーブル２１中に存在す
る場合においても、第４図に示す処理を実行することに
より、このデータ群の位置を検索することができる。

本発明による処理実行後有効データが存在しない時には
エリアＲ，Ｆ　２４　＜エリアＲＴ２５となる。

第５図にプリント基板上の任意の点の周辺に存在するス
ルーホールの位置を探索する際の実施例を示す。

図中６１は探索対象プリント基板領域であり、６１１は
任意の点を示し、斜線で塗りつぶした領域６１２が探索
範囲である。

この領域６１２の中に含まれるスルーホールの座標を求
める場合、プリント基板６１上に存在するスルーホール
の座標を昇順に並べ同−Ｘ座標６２４を１アイテムとす
る。そして上記Ｘ座標６２４に含まれるＸ成分のＸ成分
テーブル６３上の開始位置を示すポインタ６２１、終了
位置を示すポインタ６２２をルコート内に持つＸ成分テ
ーブル６２とＸ成分テーブル６３に分割する。従って、
Ｘ成分テーブル２１中時には同−Ｘ座標は１ケ所にしか
表われない。

次に、任意の点６１１と近傍を表す値ｒ６２５が与えら
れた場合、このＸ座標を探索キーとして本発明による方
式でＸ成分テーブル６２内の探索を実施する。これによ
り探索が必要なＸ領域６２３を得ることが出来る。

次に、上記Ｘ成分領域６２３の小さいＸ成分から順次Ｘ
成分テーブル６３を参照し、開始ポインタ６２１と終了
ポインタ６２２で示されるｙの値が近傍距ｗ１ｒ　６２
５以内に存在する点を捜す事により点６１１の近傍ｒ６
２５に存在するスルーホールを捜し出すことが出来る。

［発明の効果］ 本発明によれば、メモリに展開されたテーブル中から探
索キーの近傍に位置するデータを高速に捜しだすことが
出来る。

【図面の簡単な説明】

第１図は本発明の第１の実施例のシステムの構成図、第
２図は本発明で使用するコンピュータメモリ」二の検索
対象テーブルの説明図、第３図は本発明による１ゴ付き
２分探索方法の実施例のフローチャート、第４図は本発
明による巾付き２分探索方法の第２の実施例のフローチ
ャート、第５図は本発明によるスルーホール検索の実施
例の説明図である。 ［符号の説明］ ］・・ＣＰＵ、２・・メモリ、３・・ＣＲＴ、２］テー
ブル。

Claims (1)

1. 【特許請求の範囲】 １、中央処理装置（ＣＰＵ）と、出力手段と、入力手段
   と、メモリとを有するコンピュータシステムを用いたデ
   ータの検索方法において、 上記コンピュータのメモリ上に登録した上昇順または下
   降順に並べたデータの中から、指定された検索条件に従
   い２分探索法でデータを検索し、 一致するデータが存在すればこのデータを出力し、 条件が一致するデータが上記データ列の中に無い場合、
   検索条件から上および下にそれぞれ指定された巾に入る
   （以下、検索条件に近いという）１または２以上のデー
   タを上記データ列の中から捜し、 曖昧さを含む条件でデータを検索することを特徴とする
   データ検索方法。 ２、請求項１記載のデータ検索方法において、指定され
   た検索条件に従い、２分探索法でデータを検索し、 検索条件と一致するデータが存在してもその検索条件に
   近いデータが存在すればそのデータも出力することを特
   徴とするデータ検索方法。 ３、請求項１記載のデータ検索方法において、メモリ中
   に同じ値を持つデータが連続して存在する際、このデー
   タの値を検索キーとして指定された場合、上記メモリ上
   の同一データ群とその近傍に存在するデータ群の位置を
   検索することを特徴とするデータ検索方法。 ４、請求項１、２または３において、上記データは、プ
   リント基板上の位置座標であることを特徴とするデータ
   検索方法。