(57)【特許請求の範囲】
【請求項１】
検索キーについて不完全なソート状態であって複数レコードからなる被検索情報を記憶する記憶手段と、
レコードの検索範囲の開始位置を指定する検索キーの値である検索開始値に基づいて、前記被検索情報から該検索開始値を含む所望の情報を二分検索法により検索し、当該情報のレコードを仮検索開始レコードとする第１の二分検索手段と、
レコードの検索範囲の終了位置を指定する検索キーの値である検索終了値に基づいて、前記被検索情報から該検索終了値を含む所望の情報を前記二分検索法により検索し、当該情報のレコードを仮検索終了レコードとする第２の二分検索手段と、
前記仮検索開始レコードから前記仮検索終了レコードまでのレコード範囲を、ソート状態が不完全であるレコード範囲の最大値に基づいて拡大した範囲を検索範囲として、前記検索範囲の検索を行う検索手段と、
を備えることを特徴とする情報検索装置。
【請求項２】
前記検索手段は、前記仮検索開始レコードから前記最大値分だけ逆順方向に位置するレコードを検索開始レコードとし、前記仮検索終了レコードから前記最大値分だけ順方向に位置するレコードを検索終了レコードとする範囲を検索範囲として検索を行うことを特徴とする請求項１に記載の情報検索装置。
【請求項３】
前記検索手段は、前記検索範囲を順検索し、検索結果に対してソートをかけることを特徴とする請求項１または２に記載の情報検索装置。
【請求項４】
前記最大値を求める最大値算出手段を備えることを特徴とする請求項１〜３のいずれか一つに記載の情報検索装置。
【請求項５】
検索キーについて不完全なソート状態であって複数レコードからなる被検索情報を記憶手段に記憶させる記憶工程と、
レコードの検索範囲の開始位置を指定する検索キーの値である検索開始値に基づいて、前記被検索情報から該検索開始値を含む所望の情報を二分検索法により検索し、当該情報のレコードを仮検索開始レコードとする第１の二分検索工程と、
レコードの検索範囲の終了位置を指定する検索キーの値である検索終了値に基づいて、前記被検索情報から該検索終了値を含む所望の情報を前記二分検索法により検索し、当該情報のレコードを仮検索終了レコードとする第２の二分検索工程と、
前記仮検索開始レコードから前記仮検索終了レコードまでのレコード範囲を、ソート状態が不完全であるレコード範囲の最大値に基づいて拡大した範囲を検索範囲として、前記検索範囲の検索を行う検索工程と、
をコンピュータに実行させるための情報検索プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、完全にソートされてない情報の中から所望の情報を高速に検索する情報検索装置および情報検索プログラムを記録したコンピュータ読み取り可能な記録媒体に関するものである。
【０００２】
近年、コンピュータの普及にともなって、データベース化された情報の中から所望の情報を検索する情報検索装置があらゆる分野で利用されている。この情報検索装置においては、二分検索法等により高速検索が実現されている。しかしながら、インターネット等のインフラ環境が一般に利用される昨今においては、データベース化される情報の量も増大の一途をたどっていることから、検索時間が増大するという問題が浮上している。このことから、昨今においては、かかる問題を効果的に解決できる手段、方法が切望されている。
【０００３】
【従来の技術】
従来の情報検索装置においては、高速検索を実現する方法として二分検索法（二分探索法ともいう）が採用されている。この二分検索法は、被検索ファイルにおいてデータが昇順（または降順）にソートされている場合にのみ使用可能な方法である。図８（ａ）には、データＤＡ１〜データＤＡｎからなる被検索ファイルＦＡが図示されている。この図において、データＤＡ１〜データＤＡｎには、キーとしての通番１〜通番ｎが付与されている。また、データＤＡ１〜データＤＡｎは、レコード１〜ｎに対応付けられており、昇順にソートされている。
【０００４】
つぎに、従来の情報検索装置で、図８（ａ）に示した被検索ファイルＦＡから所望のデータを二分検索法で検索する方法について説明する。図８（ａ）において、情報検索装置は、検索キー（通番）と、レコード１〜レコードｎを二分する真ん中のレコードのデータ（通番）とを比較する。ここで、検索キー（通番）が、真ん中のレコードのデータ（通番）より大きい場合、検索キーと一致するデータが上記真ん中のレコードより下側に存在するため、情報検索装置は、上記真ん中のレコードからレコードｎまでの範囲を検索対象として、上述した動作を実行する。
【０００５】
一方、検索キー（通番）が、真ん中のレコードのデータ（通番）より小さい場合、検索キーと一致するデータが上記真ん中のレコードより上側に存在するため、情報検索装置は、レコード１〜真ん中のレコードまでの範囲を対象として、上述した動作を実行する。以後、情報検索装置は、上述した動作を繰り返すことにより、所望のデータを検索する。このように二分検索法を採用した場合には、検索範囲が半分づづ狭まるため、レコード１〜レコードｎまでを１レコードづつ順検索する場合に比して、検索時間を大幅に短縮することが可能である。
【０００６】
【発明が解決しようとする課題】
ところで、前述したように、二分検索法を用いて検索を行う場合には、被検索ファイル内においてデータが完全に昇順（または降順）にソートされていることが大前提である旨を述べた。ここで完全にソートされているとは、図８（ａ）に示したようにレコード１〜レコードｎ（最終レコード）までのデータが、一部分も入れ替わることなくソートされていることをいう。
【０００７】
したがって、図８（ｂ）に示した被検索ファイルＦＢのように、一部分のレコードのデータがソート（同図では昇順にソート）されていない場合には、二分検索法による検索を行うことができない。すなわち、図８（ｂ）には、データＤＢ１〜データＤＢｎからなる完全にソートされていない被検索ファイルＦＢが図示されている。
【０００８】
同図において、データＤＢ１〜データＤＢｎには、キーとしての時刻９：０１〜時刻１０：００が付与されている。この被検索ファイルＦＢにおいては、データＤＢ１〜データＤＢｎが時刻をキーとしてほぼ昇順に配列されている。ここでほぼ昇順に配列されていると述べたのは、一部分のレコード（レコード２〜レコード４）のデータ（データＤＢ２〜ＤＢ４）が時刻をキーとして昇順に配列されていないからである。つまり、被検索ファイルＦＢは、不完全なソート状態のファイルであるといえる。したがって、従来の情報検索装置においては、同図に示した被検索ファイルＦＢから所望のデータを二分検索法により検索することができない。
【０００９】
ここで、図８（ｂ）に示した被検索ファイルＦＢに対して時刻をキーとして昇順にソートすることにより、二分検索法による検索を行うことが可能である。このように被検索ファイルＦＢにソートをかけた後、二分検索法による検索を実行する方法は、被検索ファイルＦＢのレコード数（数レコードから数百レコード）が比較的少ない場合、短時間でソートが完了するため検索時間に及ぼす影響が少なくてすむため、有効である。しかしながら、被検索ファイルＦＢのレコード数が膨大（数十万レコード以上）である場合、かかる方法では、ソートに長時間を要するため、ソートを開始してから二分検索法による検索を終了までに相当の時間がかかるという問題がある。
【００１０】
本発明は、上記に鑑みてなされたもので、不完全なソート状態の被検索情報であっても二分検索法により高速検索を行うことができる情報検索装置および情報検索プログラムを記録したコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【００１１】
【課題を解決するための手段】
上記目的を達成するために、請求項１にかかる発明は、検索キーについて不完全なソート状態であって複数レコードからなる被検索情報を記憶する記憶手段（後述する一実施の形態の記憶装置４０に相当）と、レコードの検索範囲の開始位置を指定する検索キーの値である検索開始値に基づいて、前記被検索情報から該検索開始値を含む所望の情報を二分検索法により検索し、当該情報のレコードを仮検索開始レコードとする第１の二分検索手段（後述する一実施の形態の二分検索部５２に相当）と、レコードの検索範囲の終了位置を指定する検索キーの値である検索終了値に基づいて、前記被検索情報から該検索終了値を含む所望の情報を前記二分検索法により検索し、当該情報のレコードを仮検索終了レコードとする第２の二分検索手段（後述する一実施の形態の二分検索部５２に相当）と、前記仮検索開始レコードから前記仮検索終了レコードまでのレコード範囲を、ソート状態が不完全であるレコード範囲の最大値に基づいて拡大した範囲を検索範囲として、前記検索範囲の検索を行う検索手段（後述する一実施の形態の順検索部５３および逆順検索部５４に相当）とを備えることを特徴とする。
【００１２】
この請求項１にかかる発明によれば、検索開始値が設定されると、第１の二分検索手段は、被検索情報から二分検索法により検索した情報のレコードを仮検索開始レコードとする。つぎに、検索終了値が設定されると、第２の二分検索手段は、被検索情報から二分検索法により検索した情報のレコードを仮検索終了レコードとする。そして、検索手段は、仮検索開始レコードから仮検索終了レコードまでのレコード範囲をソート状態が不完全であるレコード範囲の最大値に基づいて拡大した範囲を検索範囲として、検索を行う。
【００１３】
このように、請求項１にかかる発明によれば、検索キーについて不完全なソート部分の存在により二分検索法のみでは検索漏れが生じる範囲を、ソート状態が不完全であるレコード範囲の最大値に基づいて検索範囲に含ませるようにしたので、検索キーについて不完全なソート状態の被検索情報であっても二分検索法により高速検索を行うことができるとともに、精度の高い検索結果を得ることができる。
【００１４】
また、請求項２にかかる発明は、請求項１に記載の情報検索装置において、前記検索手段は、前記仮検索開始レコードから前記最大値分だけ逆順方向に位置するレコードを検索開始レコードとし、前記仮検索終了レコードから前記最大値分だけ順方向に位置するレコードを検索終了レコードとする範囲を検索範囲として検索を行うことを特徴とする。
【００１５】
この請求項２にかかる発明によれば、仮検索開始レコードから、ソート状態が不完全であるレコード範囲の最大値分だけ逆順方向に位置するレコードを検索開始レコードとし、仮検索終了レコードから、ソート状態が不完全であるレコード範囲の最大値分だけ順方向に位置するレコードを検索終了レコードとする範囲を検索範囲として検索を行う。
【００１６】
このように、請求項２にかかる発明によれば、仮検索開始レコードから、ソート状態が不完全であるレコード範囲の最大値分だけ逆順方向に位置するレコードを検索開始レコードとし、仮検索終了レコードから、ソート状態が不完全であるレコード範囲の最大値分だけ順方向に位置するレコードを検索終了レコードとする範囲を検索範囲として検索を行うようにしたので、検索キーについて不完全なソート状態の被検索情報であっても二分検索法により高速検索を行うことができるとともに、精度の高い検索結果を得ることができる。
【００１７】
また、請求項３にかかる発明は、請求項１または２に記載の情報検索装置において、前記検索手段は、前記検索範囲を順検索し、検索結果に対してソートをかけることを特徴とする。
【００１８】
この請求項３にかかる発明によれば、拡大された検索範囲における検索結果に対してソートをかけるようにしたので、被検索情報におけるすべてのレコードをソート範囲とする場合に比して、ソート範囲を最小限に抑えることができる。
【００１９】
また、請求項４にかかる発明は、請求項１〜３のいずれか一つに記載の情報検索装置において、前記最大値を求める最大値算出手段（後述する一実施の形態の補正値算出部５５に相当）を備えることを特徴とする。
【００２０】
この請求項４にかかる発明によれば、検索キーについて不完全なソート状態にある被検索情報においてソートされていない一部分のレコード範囲の最大値を求めるようにしたので、不完全なソート状態が検索結果に及ぼす影響を最小限に抑えることができる。また、請求項４にかかる発明によれば、最大値算出手段により、定期的に最大値を求めるようにすれば、最大値の確度を一定以上に維持することができる。
【００２１】
また、請求項５にかかる発明は、検索キーについて不完全なソート状態であって複数レコードからなる被検索情報を記憶手段に記憶させる記憶工程と、レコードの検索範囲の開始位置を指定する検索キーの値である検索開始値に基づいて、前記被検索情報から該検索開始値を含む所望の情報を二分検索法により検索し、当該情報のレコードを仮検索開始レコードとする第１の二分検索工程（後述する一実施の形態のステップＳＡ１に相当）と、レコードの検索範囲の終了位置を指定する検索キーの値である検索終了値に基づいて、前記被検索情報から該検索終了値を含む所望の情報を前記二分検索法により検索し、当該情報のレコードを仮検索終了レコードとする第２の二分検索工程（後述する一実施の形態のステップＳＡ２に相当）と、前記仮検索開始レコードから前記仮検索終了レコードまでのレコード範囲を、ソート状態が不完全であるレコード範囲の最大値に基づいて拡大した範囲を検索範囲として、前記検索範囲の検索を行う検索工程（後述する一実施の形態のステップＳＡ３〜ステップＳＡ５に相当）とをコンピュータに実行させるための情報検索プログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００２２】
この請求項５にかかる発明によれば、検索開始値が設定されると、第１の二分検索工程では、被検索情報から二分検索法により検索した情報のレコードが仮検索開始レコードとされる。つぎに、検索終了値が設定されると、第２の二分検索工程では、被検索情報から二分検索法により検索した情報のレコードが仮検索終了レコードとされる。そして、検索工程では、仮検索開始レコードから仮検索終了レコードまでのレコード範囲がソート状態が不完全であるレコード範囲の最大値に基づいて拡大された範囲を検索範囲として、検索が行われる。
【００２３】
このように、請求項５にかかる発明によれば、検索キーについて不完全なソート部分の存在により二分検索法のみでは検索漏れが生じる範囲を、ソート状態が不完全であるレコード範囲の最大値に基づいて検索範囲に含ませるようにしたので、検索キーについて不完全なソート状態の被検索情報であっても二分検索法により高速検索を行うことができるとともに、精度の高い検索結果を得ることができる。
【００２４】
【発明の実施の形態】
以下、図面を参照して本発明にかかる情報検索装置および情報検索プログラムを記録したコンピュータ読み取り可能な記録媒体の一実施の形態について詳細に説明する。
【００２５】
図１は、本発明にかかる一実施の形態の構成を示すブロック図である。この図には、ホスト１０Ａおよび１０Ｂからのログデータ（被検索情報）を中継装置２０により中継し、上記ログデータをホスト１０Ｃにより収集するための構成が図示されている。ホスト１０Ａは、たとえば、銀行の支店に設置されており、ログデータを管理するコンピュータであり、ネットワーク３０Ａを介して中継装置２０に接続されている。
【００２６】
ここでいうログデータとは、銀行取引（入金、出金、振込等）に関する取引データおよび取引時刻を示す時刻データからなる１レコード分のデータをいう。同図には、ホスト１０Ａにおけるログデータの一例として、ログデータＬＡ１およびログデータＬＡ２が図示されている。ログデータＬＡ１には、時刻データとして「１０：００」が含まれており、ログデータＬＡ２には、時刻データとして「１０：０１」が含まれている。また、ホスト１０Ａは、時々刻々発生するログデータを記憶装置（図示略）に格納するとともに、発生順にログデータをネットワーク３０Ａを介して中継装置２０へ送信する。
【００２７】
ホスト１０Ｂは、ホスト１０Ａと同様にして、銀行の支店に設置されており、ログデータを管理するコンピュータであり、ネットワーク３０Ｂを介して中継装置２０に接続されている。同図にはホスト１０Ｂにおけるログデータの一例として、ログデータＬＢ１およびログデータＬＢ２が図示されている。ログデータＬＢ１には、時刻データとして「１０：０２」が含まれており、ログデータＬＢ２には、時刻データとして「１０：０３」が含まれている。また、ホスト１０Ｂは、ホスト１０Ａと同様にして、時々刻々発生するログデータを記憶装置（図示略）に格納するとともに、発生順にログデータをネットワーク３０Ｂを介して中継装置２０へ送信する。
【００２８】
中継装置２０は、ホスト１０Ａおよびホスト１０Ｂから送信されたログデータを受信し、受信順にネットワーク３０Ｃを介してホスト１０Ｃへ送信するという、中継機能を備えている。同図に示した例では、中継装置２０は、受信順にログデータＬＡ１、ログデータＬＢ１、ログデータＬＡ２およびログデータＬＢ２をネットワーク３０Ｃを介してホスト１０Ｃへ送信する。ここで注意すべき点は、中継装置２０は、ログデータに含まれる時刻データの昇順に関係なく、ログデータの受信順でログデータを送信している点である。
【００２９】
したがって、同図に示した例では、時刻データの昇順に着目すれば、ログデータＬＡ１（１０：００）、ログデータＬＡ２（１０：０１）、ログデータＬＢ１（１０：０２）、ログデータＬＢ２（１０：０３）という順序となるが、中継装置２０における送信（受信）順序は、上記順序と相違する。このように、中継装置２０における時刻データの順序と受信（送信）順序とが相違するのは、ネットワーク３０Ａおよびネットワーク３０Ｂにおいて伝送遅延が発生するからである。つまり、ネットワーク３０Ａとネットワーク３０Ｂとの間においては、トラフィック量や伝送速度が時々刻々変動しているため、伝送遅延が発生するのである。
【００３０】
たとえば、ネットワーク３０Ｂよりネットワーク３０Ａのほうが伝送遅延が大きい場合、ホスト１０Ａから時刻１０：０１に送信されたログデータＬＡ２は、これより遅れて時刻１０：０２にホスト１０Ｂから送信されたログデータＬＢ１より後に、中継装置２０に受信される。したがって、この場合、中継装置２０からは、ログデータＬＢ１（１０：０２）、ログデータＬＡ２（１０：０１）の順序で送信される。
【００３１】
ホスト１０Ｃは、たとえば、集中管理センタに設置されたコンピュータであり、中継装置２０から順次送信されるログデータを受信し、このログデータを受信順に記憶装置４０にログファイルＦＬとして格納する。ここで、上記ログファイルＦＬの一例を図２に示す。この図に示したように、ログファイルＦＬは、レコード１〜レコードｎにそれぞれ対応するログデータＬＡｘ（時刻データ９：００）〜ログデータＬＢｙ（時刻データ１１：００）から構成されている。時刻データ（９：００〜１１：００）は、後述する検索時のキーとして利用される。
【００３２】
また、ログファイルＦＬにおいて、ログデータＬＡｘ〜ログデータＬＢｙは、ホスト１０Ｃにおける受信順に格納されている。したがって、キーとしての時刻データに着目すると、ログファイルＦＬは、ほぼ昇順（時刻順）に配列されている。しかしながら、たとえば、レコード１００〜レコード１０３のログデータＬＡ１〜ログデータＬＢ２は、前述した伝送遅延の影響により、昇順に配列されていない。つまり、ログファイルＦＬは、不完全なソート状態にある。
【００３３】
図１に戻り、検索装置５０は、記憶装置４０にアクセスすることにより、前述した二分検索法を基礎として、補足的に順検索法および逆順検索法を利用してログファイルＦＬから所望のログデータを検索する装置である。ここで、図３を参照して、上記検索装置５０の構成について説明する。同図に示した検索装置５０において、制御部５１は、装置各部を制御するものであり、検索制御、表示制御等を行う。この制御部５１の動作の詳細については、後述する。
【００３４】
二分検索部５２は、制御部５１の制御の下で、ログファイルＦＬに対して前述した二分検索法により検索をかける。順検索部５３は、制御部５１の制御の下で、ログファイルＦＬに対して順検索法により検索をかける。逆順検索部５４は、制御部５１の制御の下でログファイルＦＬに対して逆順検索法により検索をかける。これらの二分検索部５２、順検索部５３および逆順検索部５４の動作の詳細については、後述する。
【００３５】
補正値算出部５５は、不完全なソート状態のログファイルＦＬに対して二分検索法を適用するにあたっての弊害を是正するための補正値Ｎを求める。この補正値Ｎは、ログファイルＦＬにおいて昇順となっていないレコードの範囲のうち、最大の値である。この補正値Ｎの詳細については後述する。記憶部５６は、補正値算出部５５により求められた補正値Ｎのデータや、図６に示した補正値算出テーブルＴを記憶する。
【００３６】
同図に示した補正値算出テーブルＴは、補正値Ｎを算出するためのテーブルであり、「キー」、「開始レコード」、「終了レコード」、「レコード範囲（＝Ｍ）」という四つのフィールドを有するレコード１〜レコードｍからなる。「キー」は、図２に示したログファイルＦＬにおける時刻データ（９：００等）に対応している。「開始レコード」は、上記「キー」を検索キーとする昇順検索で、ログファイルＦＬにおいて最初に検索されたログデータのレコードに対応している。
【００３７】
「終了レコード」は、上記「キー」を検索キーとする昇順検索で、ログファイルＦＬにおいて最後に検索されたログデータのレコードに対応している。「レコード範囲（＝Ｍ）」は、「開始レコード」から「終了レコード」までの範囲に対応している。具体的には、「レコード範囲（＝Ｍ）」は、前述した不完全なソート状態にある可能性が高いログデータのレコード範囲に対応している。したがって、ログファイルＦＬにおいて、上記レコード範囲内に存在するログデータは、不完全なソート状態にある可能性が高い。また、キー毎に求められる「レコード範囲（＝Ｍ）」のうち最大値を採るものが、前述した補正値Ｎとされる。
【００３８】
図３に戻り、制御部５１は、検索開始時に、記憶部５６から補正値Ｎのデータを読み込む。入力部５７は、キーボード、マウス等の入力デバイスであり、検索キーの入力等に用いられる。表示部５８は、ＣＲＴ（Cathode-Ray Tube）、ＬＣＤ（Liquid Crystal Display）等であり、検索結果、ログファイルＦＬ（図２参照）、補正値算出テーブルＴ（図６参照）等を表示する。
【００３９】
つぎに、図４に示したフローチャートを参照して図３に示した検索装置５０の動作について説明する前に、図５に示したフローチャートを参照して、図３に示した補正値算出部５５の動作について説明する。図５は、検索装置５０における検索時に用いられる補正値Ｎの算出動作を説明するフローチャートである。ただし、補正値Ｎは、算出に長時間を要するため、検索の度に算出されるものではなく、一定期間毎やホスト１０Ｃのメンテナンス時（運転休止時）に算出される。以下の説明においては、図３に示した記憶装置４０には、図２に示したログファイルＦＬが格納されているものとする。
【００４０】
図３に示した入力部５７より、補正値算出用のコマンドが入力されると、制御部５１は、補正値算出部５５に対して補正値を算出すべきことを指示する。これにより、図５に示したステップＳＢ１へ進み、昇順で、図３に示したログファイルＦＬにおける１レコードを参照する。この場合、補正値算出部５５は、ログファイルＦＬにおけるレコード１を参照した後、ステップＳＢ２へ進む。
【００４１】
ステップＳＢ２では、補正値算出部５５は、ステップＳＢ１で参照したレコード（参照レコード）におけるログデータからキーを抽出する。この場合、補正値算出部５５は、図２に示したレコード１のログデータＬＡｘからキーとして時刻データ９：００を抽出した後、ステップＳＢ３へ進む。ステップＳＢ３では、補正値算出部５５は、図６に示した補正値算出テーブルＴを更新する。この場合、補正値算出部５５は、図６に示したキー（９：００）のレコード１において「開始レコード」に「１」を書き込んだ後、ステップＳＢ４へ進む。
【００４２】
ステップＳＢ４では、補正値算出部５５は、ログファイルＦＬにおける最終レコード、すなわち、図２に示したレコードｎを参照したか否かを判断し、この場合、判断結果を「Ｎｏ」としてステップＳＢ１へ戻り、上述した動作を繰り返す。これにより、図６に示した補正値算出テーブルＴにおける「開始レコード」および「終了レコード」に対応するそれぞれのレコードにデータ（ログファイルＦＬにおけるレコード）が書き込まれる。
【００４３】
そして、ステップＳＢ１で図２に示したレコード９が参照されると、ステップＳＢ２では、補正値算出部５５は、ログデータＬＢａからキーとして時刻データデータ９：０４を抽出した後、ステップＳＢ３へ進む。ステップＳＢ３では、補正値算出部５５は、図６に示したキー（９：０４）のレコード５において「開始レコード」に「９」を書き込んだ後、ステップＳＢ４へ進む。
【００４４】
ステップＳＢ４では、補正値算出部５５は、判断結果を「Ｎｏ」として、ステップＳＢ１へ戻り、上述した動作を繰り返す。そして、ステップＳＢ１で図２に示したレコード１０が参照されると、ステップＳＢ２では、補正値算出部５５は、ログデータＬＢｂからキーとして時刻データ９：００を抽出した後、ステップＳＢ３へ進む。
【００４５】
ここでレコード１０のログデータＬＢｂには、レコード１のログデータＬＡｘと同一の時刻データ（９：００）が含まれている。ステップＳＢ３では、補正値算出部５５は、図６に示したキー（９：００）のレコード１において「終了レコード」に「１０」を書き込んだ後、ステップＳＢ４へ進む。ステップＳＢ４では、補正値算出部５５は、判断結果を「Ｎｏ」として、ステップＳＢ１へ戻り、上述した動作を繰り返す。
【００４６】
そして、図２に示したログファイルＦＬにおける最終レコード（レコードｎ）を参照した後、補正値算出テーブルＴを更新すると、補正値算出部５５は、ステップＳＢ４の判断結果を「Ｙｅｓ」として、ステップＳＢ５へ進む。この場合、補正値算出テーブルＴにおいては、図６に示したように９：００〜１１：００までのキーに対応するレコード１〜ｍまでに、「開始レコード」のデータおよび「終了デコード」のデータが書き込まれている。
【００４７】
ステップＳＢ５では、補正値算出部５５は、初期設定として初期値Ｎに０を代入した後、ステップＳＢ６へ進む。ステップＳＢ６では、補正値算出部５５は、図６に示した補正値算出テーブルＴを参照して、レコード範囲Ｍを求める。具体的には、補正値算出部５５は、補正値算出テーブルＴにおける「開始レコード」〜「終了レコード」までの範囲をレコード範囲Ｍとして求める。
【００４８】
この場合、補正値算出部５５は、補正値算出テーブルＴのレコード１に関して、開始レコード１〜終了レコード１０までのレコード範囲Ｍとして１０を求め、これを補正値算出テーブルＴに書き込だ後、ステップＳＢ７へ進む。ステップＳＢ７では、補正値算出部５５は、ステップＳＢ６で求めたレコード範囲Ｍ（この場合、１０）が補正値Ｎ（この場合、０）より大きいか否かを判断し、この場合、判断結果を「Ｙｅｓ」として、ステップＳＢ８へ進む。なお、ステップＳＢ７の判断結果が「Ｎｏ」である場合、補正値算出部５５は、ステップＳＢ９へ進む。
【００４９】
ステップＳＢ８では、補正値算出部５５は、補正値Ｎにレコード範囲Ｍ（＝１０）を代入した後、ステップＳＢ９へ進む。ステップＳＢ９では、補正値算出部５５は、ステップＳＢ６で補正値算出テーブルＴにおける最終レコード（＝レコードｍ）を参照したか否かを判断し、この場合、判断結果を「Ｎｏ」としてステップＳＢ６へ戻る。以後、補正値算出部５５は、補正値算出テーブルＴにおけるレコード２以降に関して上述した動作を繰り返す。
【００５０】
そして、補正値算出部５５は、ステップＳＢ６で、図６に示した補正値算出テーブルＴのレコード５を参照すると、開始レコード９〜終了レコード２２までのレコード範囲Ｍとして１３を求め、これを補正値算出テーブルＴに書き込だ後、ステップＳＢ７へ進む。ステップＳＢ７では、補正値算出部５５は、ステップＳＢ６で求めたレコード範囲Ｍ（この場合、１３）が補正値Ｎより大きいか否かを判断し、この場合、判断結果を「Ｙｅｓ」として、ステップＳＢ８へ進む。
【００５１】
ステップＳＢ８では、補正値算出部５５は、補正値Ｎにレコード範囲Ｍ（＝１３）を代入した後、ステップＳＢ９へ進む。ステップＳＢ９では、補正値算出部５５は、ステップＳＢ６で補正値算出テーブルＴにおける最終レコード（＝レコードｍ）を参照したか否かを判断し、この場合、判断結果を「Ｎｏ」としてステップＳＢ６へ戻る。以後、補正値算出部５５は、補正値算出テーブルＴにおけるレコード６以降に関して上述した動作を繰り返す。
【００５２】
そして、補正値算出テーブルＴにおける最終レコード（＝レコードｍ）を参照すると、補正値算出部５５は、ステップＳＢ９の判断結果を「Ｙｅｓ」として、ステップＳＢ１０へ進む。ステップＳＢ１０では、補正値算出部５５は、この時点での補正値Ｎのデータを記憶部５６に格納した後、一連の補正値算出処理を終了する。つまり、上記補正値Ｎは、図６に示した補正値算出テーブルＴにおいて最大値を採るレコード範囲Ｍである。この場合、記憶部５６に格納された補正値Ｎのデータは、補正値算出テーブルＴにおけるレコード５のレコード範囲Ｍ（＝１３）であるものとする。このように、補正値Ｎは、検索の前にあらかじめ算出される値である。
【００５３】
また、記憶部５６に補正値Ｎ（＝１３）のデータが格納されている状態において、図３に示した入力部５７より検索コマンドが入力されると、制御部５１は、記憶部５６より補正値Ｎ（＝１３）のデータを読み出し、これを順検索部５３および逆順検索部５４にそれぞれ設定する。
【００５４】
つぎに、図２に示したログファイルＦＬの検索範囲としての検索キー（検索開始時刻１０：００および検索終了時刻１０：０３）が入力部５７より入力されると、制御部５１は、二分検索部５２、順検索部５３および逆順検索部５４を制御することにより、検索を実行する。つまり、この場合には、ログファイルＦＬにおける時刻１０：００〜１０：０３までのログデータが検索される。
【００５５】
すなわち、図４に示したステップＳＡ１では、二分検索部５２は、上記検索開始時刻１０：００を検索キーとして、二分検索法によりログファイルＦＬにおいて上記検索開始時刻１０：００と一致する時刻データを含むログデータを検索する。具体的には、二分検索部５２は、前述した動作と同様にして、図２に示したレコード１〜レコードｎを二分することにより、二分検索を行う。
【００５６】
この場合、二分検索部５２は、図２に示したレコード１００のログデータＬＡ１（１０：００）を検索したものとする。ここで、注意すべき点は、ログファイルＦＬが不完全なソート状態にあるため、上記レコード１００のログデータＬＡ１は、ログファイルＦＬの昇順における検索開始位置に必ずしも該当しない点である。そして、二分検索部５２は、上記レコード１００を仮検索開始レコードとして、このデータを制御部５１へ渡した後、ステップＳＡ２へ進む。これにより、制御部５１は、仮検索開始レコード（＝レコード１００）のデータを逆順検索部５４に設定する。
【００５７】
ステップＳＡ２では、二分検索部５２は、上記検索終了時刻１０：０３を検索キーとして、二分検索法によりログファイルＦＬにおいて上記検索終了時刻１０：０３と一致する時刻データを含むログデータを検索する。具体的には、二分検索部５２は、ステップＳＡ１と同様にして、図２に示したレコード１〜レコードｎを二分することにより、二分検索を行う。
【００５８】
この場合、二分検索部５２は、図２に示したレコード１０３のログデータＬＢ２（１０：０３）を検索したものとする。ここで、注意すべき点は、ログファイルＦＬが不完全なソート状態にあるため、上記レコード１０３のログデータＬＢ２は、ログファイルＦＬの昇順における検索終了位置に必ずしも該当しない点である。そして、二分検索部５２は、上記レコード１０３を仮検索終了レコードとして、このデータを制御部５１へ渡す。制御部５１は、仮検索終了レコード（＝レコード１０３）を順検索部５３に設定する。
【００５９】
つぎのステップＳＡ３では、逆順検索部５４は、逆順検索法により、図２に示したログファイルＦＬにおいて、仮検索開始レコード（＝１００）から、Ｎレコード（＝補正値Ｎ）分、逆順方向（降順方向）へ遡り、検索開始レコードを検索する。この場合、検索開始レコードは、レコード８８である。
【００６０】
つぎのステップＳＡ４では、順検索部５３は、順検索法により、ログファイルＦＬにおいて、ステップＳＡ３で検索された検索開始レコード（＝レコード８８）から順方向に１レコードを検索した後、ステップＳＡ５へ進む。この場合、順検索部５３は、レコード８８を検索し、この検索結果として、ログデータＬＢｄを得る。ステップＳＡ５では、順検索部５３は、まず、順検索法により、図２に示したログファイルＦＬにおいて、仮検索終了レコード（＝１０３）から、Ｎレコード（補正値Ｎ）分の順方向（昇順方向）に位置するレコード（＝１１５）を検索終了レコードとする。
【００６１】
つぎに、順検索部５３は、ステップＳＡ４で検索終了レコード（＝１１５）に関する検索が終了したか否かを判断し、この場合、判断結果を「Ｎｏ」として、ステップＳＡ４へ戻る。以後、順検索部５３は、レコード８９（図示略）以降に関する順検索を行う。
【００６２】
つまり、この場合、検索開始レコード（＝レコード８８）〜検索終了レコード（＝レコード１１５）までの範囲に少なくとも時間データ１０：００〜１０：０３を含むログデータが存在している。したがって、上記範囲内を検索することで、時間データ１０：００〜１０：０３を含むログデータを抽出することが可能である。つまり、補正値Ｎは、不完全なソート状態による検索漏れを防ぐ役目をしているのである。
【００６３】
そして、検索終了レコード（＝レコード１１５）に関する検索が終了すると、順検索部５３は、ステップＳＡ５の判断結果を「Ｙｅｓ」として、ステップＳＡ６へ進む。これにより、ステップＳＡ６では、順検索部５３は、時間データ１０：００〜１０：０３を含むログデータすなわち検索結果を、時刻データをキーとして昇順にソートした後、これを制御部５１に渡す。これにより、制御部５１は、検索結果を表示部５８に表示させた後、一連の検索処理を終了する。
【００６４】
以上説明したように、一実施の形態によれば、不完全なソート部分の存在により二分検索法のみでは検索漏れが生じる範囲を、補正値Ｎに基づいて検索範囲に含ませるようにしたので、不完全なソート状態のログファイルＦＬであっても二分検索法により高速検索を行うことができるとともに、精度の高い検索結果を得ることができる。
【００６５】
また、一実施の形態によれば、図４に示したステップＳＡ６で、拡大された検索範囲（レコード８８〜レコード１１５：図２参照）における検索結果に対してソートをかけるようにしたので、ログファイルＦＬのすべてのレコードをソート範囲とする場合に比して、ソート範囲を最小限に抑えることができる。
【００６６】
また、一実施の形態によれば、不完全なソート状態にあるログファイルＦＬにおいてソートされていない一部分のレコード範囲Ｍ（図６参照）の最大値を補正値Ｎとして求めるようにしたので、不完全なソート状態が検索結果に及ぼす影響を最小限に抑えることができる。さらに、一実施の形態によれば、補正値算出部５５により、定期的に補正値Ｎを求めるようにすれば、補正値の確度を一定以上に維持することができる。
【００６７】
以上本発明にかかる一実施の形態について図面を参照して詳述してきたが、具体的な構成例はこの一実施の形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等があっても本発明に含まれる。たとえば、前述した一実施の形態においては、検索装置５０の検索機能を実現するための情報検索プログラムを図７に示したコンピュータ読み取り可能な記録媒体１００に記録して、この記録媒体１００に記録された情報検索プログラムを同図に示したコンピュータ２００に読み込ませ、実行することにより検索を行うようにしてもよい。
【００６８】
図７に示したコンピュータ２００は、上記情報検索プログラムを実行するＣＰＵ２０１と、キーボード、マウス等の入力装置２０２と、各種データを記憶するＲＯＭ（Read Only Memory）２０３と、演算パラメータ等を記憶するＲＡＭ（Random Access Memory）２０４と、記録媒体１００から情報検索プログラムを読み取る読取装置２０５と、ディスプレイ、プリンタ等の出力装置２０６と、装置各部を接続するバスＢＵとから構成されている。
【００６９】
ＣＰＵ２０１は、読取装置２０５を経由して記録媒体１００に記録されている情報検索プログラムを読み込んだ後、情報検索プログラムを実行することにより、前述した検索を行う。なお、記録媒体１００には、光ディスク、フロッピーディスク、ハードディスク等の可搬型の記録媒体が含まれることはもとより、ネットワークのようにデータを一時的に記録保持するような伝送媒体も含まれる。
【００７０】
また、一実施の形態においては、不完全な昇順ソート状態にあるログファイルＦＬに対して検索を行う例について説明したが、不完全な降順ソート状態にあるファイルであっても、同様の効果が得られることは言うまでもない。
【００７１】
さらに、一実施の形態においては、補正値Ｎを用いて、図２に示した検索開始レコードおよび検索終了レコードを決定する例について説明したが、この補正値Ｎを用いることなく、逆順検索および順検索により検索開始レコードおよび検索終了レコードを決定してもよい。
【００７２】
この場合には、図２に示した仮検索開始位置（＝レコード１００）を決定した後、逆順検索により上記仮検索開始位置から１レコードづつ逆順方向に検索し、検索キーとしての時刻データ１０：００を含むログデータが最後に検索されたレコードを検索開始レコードとすればよい。同様にして、検索終了位置を決定する際には、仮検索終了位置（＝レコード１０３）を決定した後、順検索により上記仮検索終了位置から１レコードづつ順方向に検索し、検索キーとしての時刻データ１０：０３を含むログデータが最後に検索されたレコードを検索終了レコードとすればよい。
【００７３】
【発明の効果】
以上説明したように、請求項１、５にかかる発明によれば、検索キーについて不完全なソート部分の存在により二分検索法のみでは検索漏れが生じる範囲を、ソート状態が不完全であるレコード範囲の最大値に基づいて検索範囲に含ませるようにしたので、検索キーについて不完全なソート状態の被検索情報であっても二分検索法により高速検索を行うことができるとともに、精度の高い検索結果を得ることができるという効果を奏する。また、請求項２にかかる発明によれば、仮検索開始レコードから、ソート状態が不完全であるレコード範囲の最大値分だけ逆順方向に位置するレコードを検索開始レコードとし、仮検索終了レコードから、ソート状態が不完全であるレコード範囲の最大値分だけ順方向に位置するレコードを検索終了レコードとする範囲を検索範囲として検索を行うようにしたので、検索キーについて不完全なソート状態の被検索情報であっても二分検索法により高速検索を行うことができるとともに、精度の高い検索結果を得ることができるという効果を奏する。
【００７４】
また、請求項３にかかる発明によれば、拡大された検索範囲における検索結果に対してソートをかけるようにしたので、被検索情報におけるすべてのレコードをソート範囲とする場合に比して、ソート範囲を最小限に抑えることができるという効果を奏する。
【００７５】
また、請求項４にかかる発明によれば、検索キーについて不完全なソート状態にある被検索情報においてソートされていない一部分のレコード範囲の最大値を求めるようにしたので、不完全なソート状態が検索結果に及ぼす影響を最小限に抑えることができるという効果を奏する。さらに、請求項４にかかる発明によれば、最大値算出手段により、定期的に最大値を求めるようにすれば、最大値の確度を一定以上に維持することができるという効果を奏する。
【図面の簡単な説明】
【図１】本発明にかかる一実施の形態の構成を示すブロック図である。
【図２】図１に示したログファイルＦＬを示す図である。
【図３】図１に示した検索装置５０の構成を示すブロック図である。
【図４】図３に示した検索装置５０の動作を説明するフローチャートである。
【図５】図３に示した補正値算出部５５の動作を説明するフローチャートである。
【図６】同一実施の形態における補正値算出テーブルＴを示す図である。
【図７】同一実施の形態の変形例を示すブロック図である。
【図８】従来の情報検索装置における被検索ファイルＦＡおよび被検索ファイルＦＢを示す図である。
【符号の説明】
４０  記憶装置
５１  制御部
５２  二分検索部
５３  順検索部
５４  逆順検索部
５５  補正値算出部
５６  記憶部
【図１】
0003776659.tif 000002
【図２】
0003776659.tif 000003
【図３】
0003776659.tif 000004
【図４】
0003776659.tif 000005
【図５】
0003776659.tif 000006
【図６】
0003776659.tif 000007
【図７】
0003776659.tif 000008
【図８】
0003776659.tif 000009