(57)【要約】探索装置101は、行に含まれるキー順に行が並んだテキストファイルが記録された記録部102から、パターンにマッチする行を探索する。すなわち、受付部104が、パターンを受け付けると、初期化部103は、探索範囲の上限および下限を初期化し、算定部105は、上限と下限の間の中間位置を算定する。取得部106は、記録部102に記録されたテキストファイルにおいて、中間位置もしくは中間位置より前を先頭とし、中間位置より後を末尾とする中間行を取得する。中間行に含まれるキーがパターンにマッチすれば、出力部107は中間行を探索結果として出力する。制御部108は、中間行に含まれるキーとパターンの大小関係に基づいて、探索範囲の上限もしくは下限を再設定し、上限と下限が改行よりも離れていれば、中間位置の算定以降を繰り返す。そうでなければ、出力部107は、発見できなかった旨を出力する。
2018055680.tif 000002
【特許請求の範囲】
【請求項１】
複数の行が並べられたテキストファイルであって、前記複数の行は前記複数の行のそれぞれに含まれるキーの順に並べられ、前記複数の行のそれぞれの末尾には改行が配置されるテキストファイルが記録された記録部、
探索をするためのパターンを受け付ける受付部、
前記テキストファイルの先頭および末尾の位置を、探索範囲の下限および上限に設定する初期化部、
前記下限と前記上限との間の中間位置を算定する算定部、
前記記録部に記録されたテキストファイルから、
(x) 前記算定された中間位置もしくは当該中間位置より前を先頭とし、
(y) 前記算定された中間位置より後を末尾とする
中間行を取得する取得部、
前記取得された中間行に含まれるキーと、前記受け付けられたパターンと、が、マッチすれば、前記取得された中間行を前記探索の結果として出力する出力部、
前記取得された中間行に含まれるキーが、前記受け付けられたパターンより、
(p) 大きければ、前記中間行の先頭の位置を、前記下限に再設定し、
(q) 小さければ、前記中間行の末尾の位置を、前記上限に再設定して、
前記上限から1つの改行の長さだけ後の位置が前記下限より前であれば、前記算定部による算定および前記取得部による取得を繰り返す制御部
を備え、
前記上限から1つの改行の長さだけ後の位置が前記下限より前でなければ、前記出力部は、前記受け付けられたパターンにマッチする行が発見できなかった旨を前記探索の結果として出力する
ことを特徴とする探索装置。
【請求項２】
前記初期化部は、先行長および後行長を、第1初期値および第2初期値に初期化し、
前記取得部は、
(a) 前記算定された中間位置から先行長だけ前の位置もしくは前記テキストファイルの先頭から、
(b) 前記算定された中間位置から後行長だけ後の位置もしくは前記テキストファイルの末尾まで
のデータを、前記記録部から読み出し、前記読み出されたデータから前記中間行の取得を試行し、前記中間行の取得ができなければ、前記先行長および前記後行長を増加させて、前記中間行の取得を再試行する
ことを特徴とする請求項1に記載の探索装置。
【請求項３】
前記中間行の取得ができたときの前記先行長および前記後行長を、次の探索における第1初期値および第2初期値とする
ことを特徴とする請求項2に記載の探索装置。
【請求項４】
前記初期化部は、
(1) 先行長を、前記複数の行の最大長と改行の長さとの和から1を減じた値以上に設定し、
(2) 後行長は、前記複数の行の最大長以上に設定し、
前記取得部は、
(a) 前記算定された中間位置から先行長だけ前の位置もしくは前記テキストファイルの先頭から、
(b) 前記算定された中間位置から後行長だけ後の位置もしくは前記テキストファイルの末尾まで
のデータを、前記記録部から読み出し、前記読み出されたデータから前記中間行を取得する
ことを特徴とする請求項1に記載の探索装置。
【請求項５】
前記最大長は、前記取得部による前記中間行の取得ができなければ、前記テキストファイルを走査することにより、同定される
ことを特徴とする請求項4に記載の探索装置。
【請求項６】
前記最大長は、前記テキストファイルが更新されるごとに、同定される
ことを特徴とする請求項4に記載の探索装置。
【請求項７】
複数の行が並べられたテキストファイルであって、前記複数の行は前記複数の行のそれぞれに含まれるキーの順に並べられ、前記複数の行のそれぞれの末尾には改行が配置されるテキストファイルが記録された記録部を探索する探索方法であって、
探索装置が、探索をするためのパターンを受け付ける受付ステップ、
前記探索装置が、前記テキストファイルの先頭および末尾の位置を、探索範囲の下限および上限に設定する初期化ステップ、
前記探索装置が、前記下限と前記上限との間の中間位置を算定する算定ステップ、
前記探索装置が、前記記録部に記録されたテキストファイルから、
(x) 前記算定された中間位置もしくは当該中間位置より前を先頭とし、
(y) 前記算定された中間位置より後を末尾とする
中間行を取得する取得ステップ、
前記取得された中間行に含まれるキーと、前記受け付けられたパターンと、が、マッチすれば、前記探索装置が、前記取得された中間行を前記探索の結果として出力する出力ステップ、
前記取得された中間行に含まれるキーが、前記受け付けられたパターンより、
(p) 大きければ、前記探索装置が、前記中間行の先頭の位置を、前記下限に再設定し、
(q) 小さければ、前記探索装置が、前記中間行の末尾の位置を、前記上限に再設定して、
前記上限から1つの改行の長さだけ後の位置が前記下限より前であれば、前記探索装置が、前記算定ステップおよび前記取得ステップを繰り返す制御ステップ
を備え、
前記上限から1つの改行の長さだけ後の位置が前記下限より前でなければ、前記探索装置が、前記受け付けられたパターンにマッチする行が発見できなかった旨を前記探索の結果として出力する
ことを特徴とする探索方法。
【請求項８】
複数の行が並べられたテキストファイルであって、前記複数の行は前記複数の行のそれぞれに含まれるキーの順に並べられ、前記複数の行のそれぞれの末尾には改行が配置されるテキストファイルが記録された記録部を有するコンピュータを、
探索をするためのパターンを受け付ける受付部、
前記テキストファイルの先頭および末尾の位置を、探索範囲の下限および上限に設定する初期化部、
前記下限と前記上限との間の中間位置を算定する算定部、
前記記録部に記録されたテキストファイルから、
(x) 前記算定された中間位置もしくは当該中間位置より前を先頭とし、
(y) 前記算定された中間位置より後を末尾とする
中間行を取得する取得部、
前記取得された中間行に含まれるキーと、前記受け付けられたパターンと、が、マッチすれば、前記取得された中間行を前記探索の結果として出力する出力部、
前記取得された中間行に含まれるキーが、前記受け付けられたパターンより、
(p) 大きければ、前記中間行の先頭の位置を、前記下限に再設定し、
(q) 小さければ、前記中間行の末尾の位置を、前記上限に再設定して、
前記上限から1つの改行の長さだけ後の位置が前記下限より前であれば、前記算定部による算定および前記取得部による取得を繰り返す制御部
として機能させるプログラムであって、
前記上限から1つの改行の長さだけ後の位置が前記下限より前でなければ、前記出力部は、前記受け付けられたパターンにマッチする行が発見できなかった旨を前記探索の結果として出力する
ことを特徴とするプログラム。
【請求項９】
前記プログラムは、前記コンピュータが有するメモリへロードされて、前記コンピュータが有するプロセッサにより実行され、
前記プログラムは、前記プロセッサを、
前記受付部として機能させる受付コード、
前記初期化部として機能させる初期化コード、
前記算定部として機能させる算定コード、
前記取得部として機能させる取得コード、
前記制御部として機能させる制御コード
を含み、
前記下限、前記上限、前記中間位置、前記中間行、および、前記探索の結果は、前記メモリに格納される
ことを特徴とする請求項8に記載のプログラムが記録された非一時的なコンピュータ読取可能な情報記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テキストファイルを二分探索する探索装置、探索方法、プログラム、ならびに、情報記録媒体に関する。
【背景技術】
【０００２】
従来から、ソート済みの配列から所望の要素を高速に探索する二分探索の技術が提案されている(非特許文献1参照)。ここで、二分探索では、探索の対象となる配列には同じデータサイズの要素が格納されることを前提としている。【０００３】
特許文献1には、テキストデータを二分探索するために、テキストデータからあらかじめ二分木を生成する技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平8-272827号公報
【非特許文献】
【０００５】
【非特許文献１】ウィキペディア「Binary search algorithm」の項, [online], [平成28年2月25日検索], https://en.wikipedia.org/wiki/Binary_search_algorithm
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、任意の長さの行を含むテキストファイルから、所望のパターンにマッチするキーを含む行を探す場合には、各データは行により表現され、データサイズは一定でない。【０００７】
また、頻繁にデータが追加更新されるログファイル等や、莫大なサイズのテキストファイルを探索する際に、二分木を生成するのは事実上困難な場合も多い。【０００８】
したがって、複数の行を含むテキストファイルから、所望のパターンにマッチするキーを含む行を二分探索する技術が望まれている。【０００９】
本発明は、これらの課題を解決するもので、テキストファイルを二分探索する探索装置、探索方法、プログラム、ならびに、情報記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の観点に係る探索装置は、
複数の行が並べられたテキストファイルであって、前記複数の行は前記複数の行のそれぞれに含まれるキーの順に並べられ、前記複数の行のそれぞれの末尾には改行が配置されるテキストファイルが記録された記録部を参照し、
探索をするためのパターンを受け付け、
前記テキストファイルの先頭および末尾の位置を、探索範囲の下限および上限に設定し、
前記下限と前記上限との間の中間位置を算定し、
前記記録部に記録されたテキストファイルから、
(x) 前記算定された中間位置もしくは当該中間位置より前を先頭とし、
(y) 前記算定された中間位置より後を末尾とする
中間行を取得し、
前記取得された中間行に含まれるキーと、前記受け付けられたパターンと、が、マッチすれば、前記取得された中間行を前記探索の結果として出力し、
前記取得された中間行に含まれるキーが、前記受け付けられたパターンより、
(p) 大きければ、前記中間行の先頭の位置を、前記下限に再設定し、
(q) 小さければ、前記中間行の末尾の位置を、前記上限に再設定して、
前記上限から1つの改行の長さだけ後の位置が前記下限より前であれば、前記算定および前記取得を繰り返し、
前記上限から1つの改行の長さだけ後の位置が前記下限より前でなければ、前記受け付けられたパターンにマッチする行が発見できなかった旨を前記探索の結果として出力する。
【発明の効果】
【００１１】
本発明によれば、テキストファイルを二分探索する探索装置、探索方法、プログラム、ならびに、情報記録媒体を提供することができる。
【図面の簡単な説明】
【００１２】
【図１】本実施形態に係る探索装置の概要構成を示す説明図である。
【図２】探索の対象となるテキストファイルfの様子を示す説明図である。
【図３】探索の対象となるテキストファイルfの中間位置mから読み出されたデータ列zの様子を示す説明図である。
【図４】パターンにマッチする1つの行を探索する処理の制御の流れを示すフローチャートである。
【図５】パターンにマッチする行の範囲を探索する処理の制御の流れを示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下に本発明の実施形態を説明する。なお、本実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。
【実施例１】
【００１４】
本実施形態に係る探索装置は、各用途のために用意されたコンピュータが、プログラムを実行することにより実現される。【００１５】
当該プログラムは、当該プログラムを販売等する提供者が運営する配布サーバから、コンピュータ通信網等の一時的(transitory)伝送媒体を介して、配布することができる。たとえば、ウェブサーバ等からインターネット等を介して、当該プログラムを配布することが可能である。【００１６】
また、当該プログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、ROM(Read Only Memory)、EEPROM(Electrically Erasable Programmable ROM)、フラッシュメモリ、半導体メモリ等のコンピュータ読取可能な非一時的(non-transitory)情報記録媒体に記録することができる。この情報記録媒体は、コンピュータとは独立して配布・販売することもできる。【００１７】
配布されたプログラムは、ダウンロード先のコンピュータのフラッシュメモリやハードディスク等の非一時的(non-transitory)情報記録媒体に記録される。【００１８】
コンピュータのCPU(Central Processing Unit)あるいはプロセッサは、非一時的に記録されたプログラムを一時的(temporary)記憶装置であるRAM(Random Access Memory)等のメモリに読み出してから、プログラム内のコードを実行する。【００１９】
ただし、ROMとRAMを一つのメモリ空間にマッピングして実行することが可能なアーキテクチャや、システムコールを利用することによりハードディスク等の情報記録媒体に記録されたファイルを当該メモリ空間にマッピングすることが可能な環境では、ROMやハードディスク等に格納されたプログラムに含まれる指令を、直接CPUが読み出して実行する。【００２０】
また、後述する処理において利用される各種の変数(variables)は、RAMあるいはプロセッサもしくはCPUに用意されたレジスタに値を読み書きすることによって実現される。【００２１】
なお、コンピュータにより本実施形態の各機器を実現するのではなく、専用の電子回路を用いて構成することも可能である。この態様では、プログラムは、電子回路の配線図やタイミングチャート等を生成するための素材として機能する。このような態様では、プログラムに定められる仕様を満たすような電子回路が、FPGA(Field Programmable Gate Array)や、ASIC(Application Specific Integrated Circuit)等により構成される。前記電子回路は、前記プログラムに定められた機能を果たす専用機器として機能する。【００２２】
図1は、本実施形態に係る探索装置の概要構成を示す説明図である。本図に示すように、探索装置101は、記録部102、初期化部103、受付部104、算定部105、取得部106、出力部107、制御部108を備える。これらの各部は、プログラムに含まれるそれぞれの機能に対応付けられるコードまたは指令をプロセッサもしくはCPUが実行することによって実現される。以下、各部の機能の概要を説明する。【００２３】
記録部102には、探索の対象となるテキストファイルが記録される。ハードディスク等の不揮発性の記録媒体、RAM等の揮発性の記録媒体、コンピュータ通信網を介して接続されたネットワークストレージなどを記録部102として利用することができる。【００２４】
初期化部103は、探索を開始するための初期化を行い、プロセッサあるいはCPUにより実現される。【００２５】
受付部104は、探索に用いるパターンを受け付けるもので、キーボードやマウスなどの入力装置のほか、コンピュータ通信網を介して接続された他の端末により実現される。【００２６】
算定部105は、二分探索における中間位置を算定し、プロセッサあるいはCPUにより実現される。【００２７】
取得部106は、テキストファイルの中間位置から中間行を取得し、プロセッサあるいはCPUが、記録部102と協働することにより実現される。【００２８】
出力部107は、取得された中間行がパターンにマッチしているか否かを判定し、マッチしていれば探索結果として出力するもので、プロセッサあるいはCPUにより実現される。【００２９】
制御部108は、取得された中間行に含まれるキーとパターンとの大小関係に基づいて、探索範囲を狭めて探索を繰り返す制御を行うもので、プロセッサあるいはCPUにより実現される。【００３０】
以下、探索装置101の動作について、詳細に説明する。理解を容易にするため、データ列におけるインデックスは0から始まること(0-origin)を想定して説明する。ただし、インデックスが1から始まる形態(1-origin)においても、インデックスを適宜変換することで、以下の形態を実現することが可能である。【００３１】
また、あるデータ列sに対して、位置pから始まる長さnの部分列をs(p,p+n)と表記する。さらに、数値a, bのいずれか大きい方をmax(a,b)、小さい方をmin(a,b)と表記する。【００３２】
図2は、探索の対象となるテキストファイルfの様子を示す説明図である。以下、本図を参照して説明する。【００３３】
本実施形態では、末尾に改行が配置された行が複数並べられたテキストファイルを、探索の対象とする。各行からは、たとえば日時を表す文字列などをキーとして抽出することができ、複数の行は、当該キーの順に並べられている。【００３４】
たとえば、タブやコンマなどによって値が区切られて1行内に1つのレコードが表記されるCSV(Character Separated Value)形式のテキストファイルにおいて、特定のフィールド、たとえば先頭フィールドに、日時を表す文字列が配置されるログファイルなどが典型的な例である。このようなログファイルでは、監視すべきイベントが発生するたびに、当該イベントが発生した日時と、当該イベントの内容と、を表す行が、ログファイルの末尾に追記される。したがって、別途ソートの処理などを必要とせず、イベント発生日時の順に、行が並ぶことになる。【００３５】
なお、各行の末尾に改行が配置され、各行からキーが抽出可能であり、各行がキーの順にソートされているテキストファイルであれば、ログファイルに限らず、任意のテキストファイルに本実施形態の二分探索を適用することができる。【００３６】
以下では、テキストファイルに含まれるデータ列f全体の長さをLとする。なお、データの単位(データ列の1要素)は、ファイルの文字コードによって異なる。ASCII, UTF-8, EUC, Shift-JIS等の場合には、1文字は1バイト乃至3バイトで表現されるので、1バイト(8ビット)がデータの単位である。【００３７】
UTF-16等の場合には、1文字は2バイトもしくは4バイトで表現されるので、2バイト(16ビット)をデータの単位とすることができる。UTF-32等の場合には、4バイト(32ビット)がデータの単位となる。【００３８】
以下では、改行を表すデータ列をnlと表記し、nlの長さを#nl と表記する。UNIX(登録商標)などのOS(Operating System)では、改行nlは、長さ1で、その中身はラインフィードを表す数値10である(nl = [10], #nl = 1)。DOS(Disk Operating System)やWindows(登録商標)では、改行nlは、長さ2で、その中身はキャリッジリターンを表す数値13に数値10が続く列である(nl = [13, 10], #nl = 2)。このほか、任意の文字コードのファイルシステムにおいても、同様に改行nlを定義することが可能である。【００３９】
本実施形態では、テキストファイルf全体をメモリに読み出すのではなく、その一部を取得する。その際に、先行長Aおよび後行長Bというパラメータを参照し、読み出すデータ長を(A+B)とする。【００４０】
図3は、探索の対象となるテキストファイルfの中間位置mから読み出されたデータ列zの様子を示す説明図である。本図に示すように、先行長Aと後行長Bは、テキストファイルから読み出したデータ列に、少なくとも1つの行全体(以下「中間行」と呼ぶ。)が含まれ、当該中間行が、先行長A部分内から始まって後行長B部分内にて終わるか、後行長B部分の先頭から始まって後行長B部分内にて終わるように定める。【００４１】
以下、テキストファイルfに含まれる行の最大長をXと表記する。最大長Xには、行の末尾に配置される改行の長さを含むものとする。【００４２】
図4は、パターンにマッチする1つの行を探索する処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。【００４３】
本処理が開始されると、探索装置101は、探索の対象となるテキストファイルfの指定や、探索したいパターンpatの指定を受け付ける(ステップS400)。【００４４】
ついで、探索装置101は、先行長A、後行長Bを初期化する(ステップS401)。【００４５】
上記のようにデータ列を取得した結果、中間行の末尾の改行の1データのみが、先行長A部分内におさまらず、後行長B部分に突出していた場合に、中間行の先頭を検出するためには、中間行の前の行の末尾に配置された改行が、先行長A部分内に読み出される必要がある。したがって、先行長Aは、以下のように初期化すれば良い。以下、記号「←」により、代入もしくは設定を表現する。
A ← X + #nl - 1【００４６】
一方、後行長Bについては、中間行が後行長B部分の先頭から始まって後行長B部分内にて終わった場合を想定すれば良い。中間行の直前の行の末尾に配置された改行は、先行長A部分内に読み出されているはずだからである。したがって、後行長Bは、以下のように初期化すれば良い。
B ← X【００４７】
一般に、#nl≧1 であるから、A≧Bが成立する。そこで、先行長Aと後行長Bを別途設定するのではなく、先行長Aを後行長Bにも利用することとしても良い。【００４８】
本実施形態においては、従来技術における二分探索と同様に、探索範囲の下限bおよび上限eを参照する。下限bおよび上限eの初期値は、テキストファイルfの先頭および末尾の位置である。テキストファイルfの長さをデータ単位で表現した値をLとすると、探索装置101は、下限b, 上限eの初期値を、以下のように設定する(ステップS402)。
b ← 0; 
e ← L 【００４９】
なお、テキストファイルfの長さLは、テキストファイルfのバイト数を、たとえば、statシステムコールなどを利用して取得した後、上記のデータの単位バイト数にて除算すれば得ることができる。【００５０】
以下、二分探索の繰り返しを始める。まず、探索装置101は、中間位置mを
b ≦ m < e
を満たすように定める(ステップS403)。典型的には、
m ← (b+e)/2
のように設定する。なお、斜線「/」により表現される整数除算においては、余りは切り捨てる。【００５１】
テキストファイルfにおいて、中間位置mは、多くの場合、行の先頭とはならない。すなわち、テキストファイルfの中間位置mからデータを読み出しても、中間行は得られない。したがって、従来技術をそのまま適用して二分探索を実現することは不可能である。【００５２】
そこで、本実施形態では、先行長Aおよび後行長Bを参照して、中間位置mに位置するデータ列を取得し、その中から中間行を取得する。【００５３】
探索装置101は、ファイルfのうち、bからeまでの区間の中央である中間位置m付近のデータ列zを取得する(ステップS404)。殆どの場合には、図2に示すように、
z ← f(m-A, m+B)
とすれば良い。【００５４】
一般には、mがファイルの先頭0や末尾L付近である場合を考慮して
z ← f(max(m-A,0), min(m+B,L))
とすれば良い。以下、理解を容易にするため、
S ← max(m-A,0)
と表記すると、
z ← f(S, min(m+B,L))
となる。【００５５】
データ列zの取得は、たとえば、テキストファイルfをopenシステムコールで開き、読み出し位置をseekシステムコールでS(もしくはこれにデータ単位を乗じた値)に設定した後、readシステムコールでmin(m+B,L)-S個分のデータをメモリ内に読み出すことで実現できる。【００５６】
このほか、mmapシステムコールでテキストファイルfをメモリ空間にマップした場合には、マップ先のメモリのアドレスをデータ列zの先頭に設定すれば良い。【００５７】
ついで、探索装置101は、読み出されたデータ列zから、元のテキストファイルfにおける中間位置m、すなわち、データ列zにおける位置m-Sに位置する中間行z(p,q)を抽出する。上記のように、図3は、探索の対象となるテキストファイルfの中間位置mから読み出されたデータ列zの様子を示す説明図である。以下、本図を参照して説明する。【００５８】
本図では、S=max(m-A,0)=m-Aの場合を想定しているので、位置m-Sは、位置Aに相当する。【００５９】
中間行z(p,q)は、元のファイルfにおいては、f(p+S,q+S)に相当する。
z(p,q) = f(p+S,q+S)    【００６０】
ここで、データ列zから抽出されるべき中間行z(p,q)の先頭および末尾の位置を表すパラメータp, qは、4条件
0 ≦ p ≦ m-S < q; 
z(p - #nl, p) = nl あるいは S = 0 = p; 
z(q - #nl, q) = nl; 
∀r | p≦r<(q - #nl) z(r,r + #nl) ≠ nl
をすべて満たすものである。このようなp,qおよび中間行z(p,q)=f(p+S,q+S)は、データ列zを先頭から走査することにより、探し出すことが可能である。【００６１】
このように、テキストファイルfの最大長Xに基づいて先行長A, 後行長Bを設定してデータ列zを取得すれば、中間位置mに位置する中間行z(p,q)=f(p+S,q+S)が必ず抽出できる点に、本実施形態の特徴の一つが現れている。【００６２】
最大長Xは、テキストファイルfが更新されるごとに探索装置101が同定することとしても良い。しかしながら、テキストファイルfとしてログファイルを想定する場合には、テキストファイルfが随時更新されるため、行の最大長Xをあらかじめ調べておくことが難しいことも多い。図4においては、このような場合の制御の流れが示されている。【００６３】
すなわち、
(1)探索を始める際に適当な初期値を先行長A、後行長Bに与えて(ステップS401)、
(2)データ列zを読み出した(ステップS404)上で、中間行z(p,q)の抽出を試行し(ステップS405)、
(3)抽出に失敗したら(ステップS406;No)、たとえば正定数を加算あるいは乗算したり、テキストファイルfそのものを走査して最大長Xを同定し直すことにより、A, Bを増加させて(ステップS407)、
(4)上記(2)に戻ってデータ列zの読み出しおよび中間行z(p,q)の抽出の試行を繰り返す
処理を実行すれば良い。【００６４】
上記のように、A, Bは、異なる値としても良いし、等しい値としても良い。たとえば、先行長Aを後行長Bとしても利用するように設定すれば、メモリを節約し、計算を抑制することができる。【００６５】
一旦増加されたA, Bは、メモリ内に保持し、あるいは、ハードディスク等の不揮発な記録装置や記録媒体に記録して、それ以降の検索におけるA, Bの初期値として利用しても良い。A, Bの初期値は、テキストファイルfごとに異なるものとして保持、記録しても良いし、共通化しても良い。【００６６】
抽出に成功したら(ステップS406;Yes)、探索装置101は、取得された中間行z(p,q)から、キーkを抽出し(ステップS408)、当該キーkと、パターンpatと、を対比照合する(ステップS409)。【００６７】
両者がマッチすれば(ステップS409;マッチ)、探索装置101は、中間行z(p,q)=f(p+S,q+S)、もしくは、元のファイルにおける中間行z(p,q)の先頭の位置p+Sおよび末尾の位置q+Sを探索結果(の一つ)として出力して終了する(ステップS410)。【００６８】
ここで、中間行から抽出したキーと、探索に用いるパターンと、のマッチは、最も単純には、データ列の完全一致とすれば良い。また、前方一致(prefix match)によって、キーとパターンのマッチを判断しても良い。【００６９】
たとえば、ログファイル内の日時がマイクロ秒単位で記録されている環境下で、タイムゾーンとしてグリニッジ標準時を想定したキー「2015-02-26T19:24:25.193+00:00」の先頭部分は、パターン「2015」(2015年発生のイベント)「2015-02」(同年2月発生のイベント)「2015-02-26」(同月26日発生のイベント)「2015-02-26T19」(同日19時発生のイベント)「2015-02-26T19:24」(同日19時24分発生のイベント)「2015-02-26T19:24:25」(同日19時24分25秒発生のイベント)「2015-02-26T19:24:25.193」(同日19時24分25.193秒発生のイベント)に一致するので、当該キーはこれらのパターンに前方一致する。そこで、当該キーが、これらのパターンにマッチする、として扱うことができる。【００７０】
キーとパターンの大小関係は、文字列比較の大小関係と同様に定めることができる。たとえば、パターン「2015」「2015-02」「2015-02-26」「2015-02-26T19」「2015-02-26T19:24」「2015-02-26T19:24:25」は、いずれも、キー「2015-02-26T19:24:25.193+00:00」より小さいことになる。【００７１】
一般に、キーとパターンのマッチは、用途に応じて完全一致もしくは前方一致を採用し、キーとパターンの大小関係は、データ列を先頭からコード順に比較したいわゆる辞書式順序(lexicographical order)により定めれば良い。【００７２】
さて、上記のように
b ≦ m < e; 
p+S ≦ m < q+S
が成立するから、
b < q+S, 
p+S < e
が常に満たされる。【００７３】
抽出された中間行z(p,q)=f(p+S,q+S)のキーkが、所望のパターンpatよりも小さければ(ステップS409;k<pat)、中間行よりも後ろに所望の行があることになるから、探索装置101は、下限bを、
b ← q+S
のように更新して(ステップS411)、探索範囲を中間行f(p+S,q+S)よりも後に絞り込み、ステップS413に制御を進める。上記の関係式より、当該更新によって、下限bは必ず増加することになる。【００７４】
一方、抽出された行z(p,q)=f(p+S,q+S)のキーkが、所望のパターンpatよりも大きければ(ステップS409;pat<k)、中間行よりも前に所望の行があることになるから、探索装置101は、上限eを、
e ← p+S
のように更新して(ステップS412)、探索範囲を中間行f(p+S,q+S)よりも前に絞り込み、ステップS413に制御を進める。上記の関係式より、当該更新によって、eは必ず減少することになる。【００７５】
そして、探索装置101は、下限b, 上限eを比較する(ステップS413)。比較の結果、b < e (図示せず。)あるいは、所望の中間行には必ず改行が含まれることを考慮して、b + #nl < e であれば(ステップS413;Yes)、探索装置101は、ステップS403に制御を戻して、上記の処理を繰り返す。【００７６】
そうでなければ(ステップS413;No)、探索装置101は、テキストファイルfには、所望のパターンpatにマッチする行は存在しない旨を出力して(ステップS414)、処理を終了する。【００７７】
このように、本実施例によれば、各行の長さが必ずしも一致しないテキストファイルから、所望のキーを有する行を二分探索により探索することができる。
【実施例２】
【００７８】
上記実施例では、パターンにマッチする行が、テキストファイル内に一つだけある状況を想定して説明した。以下では、パターンにマッチする行が、テキストファイル内に複数連続して並んでいることがある場合の探索について説明する。【００７９】
まず、理解を容易にするため、上記実施例の「テキストファイルfの、位置x乃至位置yから、所望のパターンpatにマッチする行を1つ探す」という処理を、
search(f, x, y, pat)
のように表記する。上記例は、b, eの初期値として、0, Lを使用しているので、search(f, 0, L, pat)を実行していることになる。【００８０】
search(f, x, y, pat)によってマッチする行が見つかった場合には、search(f, x, y, pat)は、当該ファイルfにおける当該マッチする行の先頭および末尾の位置s, tと、当該マッチする行が見つかった際の探索範囲の上限eおよび下限bを出力するものとする。これを、
OK (b,s,t,e) = search(f, x, y, pat)
と表記する。明らかに、x≦b≦s<t≦e≦yが成立する。【００８１】
上記実施例に合わせて説明すれば、search(f, 0, L, pat)の実行により、パターンpatにマッチする中間行z(p,q)が見つかった場合には、OK (b,p+S,q+S,e)が出力されることになる。【００８２】
また、見つからなかった場合には、search(f, x, y, pat)は、その旨を返す。これを、
FAIL = search(f, x, y, pat)
と表記する。【００８３】
図5は、パターンにマッチする行の範囲を探索する処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。【００８４】
まず、探索装置101は、上記処理を用いて、パターンpatにマッチする行を1つ探し出し、探索結果をrに得る(ステップS500)。すなわち、
r ← search(f, 0, L, pat)
を実行する。【００８５】
次に、探索装置101は、rの中身を吟味する(ステップS501)。r = FAILであれば(ステップS501; FAIL)、パターンpatにマッチする行は一つもないこととなるので、その旨を出力して(ステップS502)、本処理を終了する。【００８６】
一方、r = OK (b,s,t,e)であれば(ステップS501; OK (b,s,t,e))、その前方を探索する処理
u ← search(f, b, s, pat)
を実行する(ステップS503)。【００８７】
そして、探索装置101は、uの中身を吟味する(ステップS504)。u = FAIL であれば(ステップS504; FAIL)、位置sが、パターンpatにマッチする行のうち最も前にある行の開始位置となるので、探索装置101は、ステップS511に制御を進める。【００８８】
一方、u = OK (b', s', _, _)であれば(ステップS504; OK (b', s', _, _))、探索装置101は、探索範囲を前に移動するため、
b ← b'; 
s ← s'
を実行して(ステップS505)、ステップS503に制御を戻す。なお、下線「_」は、処理search()が返した結果の当該部分を無視することを意味する。【００８９】
パターンpatにマッチする行のうち最も前にある行の開始位置sが求められたら、パターンpatにマッチする行のうち最も後にある行の末尾位置を求めることもできるし、開始位置sからファイルfを走査することにより、マッチする行をすべて得ることもできる。【００９０】
以下では、末尾位置を探索する処理について説明する。すなわち、上記のr = OK (b,s,t,e)に基づいて、後方を探索する処理
v ← search(f, t, e, pat)
を実行する(ステップS511)。【００９１】
ついで、探索装置101は、探索結果vを吟味する(ステップS512)。v = FAILであれば(ステップS512; FAIL)、位置tが、パターンpatにマッチする行のうち最も後にある行の末尾位置となるので、開始位置s, 終了位置tを出力して(ステップS521)、本処理を終了する。【００９２】
v = OK (_, _, t', e')であれば(ステップS512; OK (_, _, t', e'))、さらに後を探す必要があるので、探索装置101は、処理
t ← t'; 
e ← e'
を実行して(ステップS513)、制御をステップS511に戻す。【００９３】
このようにして、テキストファイルfから、パターンpatにマッチする1以上の行全体の先頭位置および末尾位置を二分探索により求めることができる。【００９４】
(まとめ)
以上説明したように、本実施形態に係る探索装置は、
複数の行が並べられたテキストファイルであって、前記複数の行は前記複数の行のそれぞれに含まれるキーの順に並べられ、前記複数の行のそれぞれの末尾には改行が配置されるテキストファイルが記録された記録部、
探索をするためのパターンを受け付ける受付部、
前記テキストファイルの先頭および末尾の位置を、探索範囲の下限および上限に設定する初期化部、
前記下限と前記上限との間の中間位置を算定する算定部、
前記記録部に記録されたテキストファイルから、
(x) 前記算定された中間位置もしくは当該中間位置より前を先頭とし、
(y) 前記算定された中間位置より後を末尾とする
中間行を取得する取得部、
前記取得された中間行に含まれるキーと、前記受け付けられたパターンと、が、マッチすれば、前記取得された中間行を前記探索の結果として出力する出力部、
前記取得された中間行に含まれるキーが、前記受け付けられたパターンより、
(p) 大きければ、前記中間行の先頭の位置を、前記下限に再設定し、
(q) 小さければ、前記中間行の末尾の位置を、前記上限に再設定して、
前記上限から1つの改行の長さだけ後の位置が前記下限より前であれば、前記算定部による算定および前記取得部による取得を繰り返す制御部
を備え、
前記上限から1つの改行の長さだけ後の位置が前記下限より前でなければ、前記出力部は、前記受け付けられたパターンにマッチする行が発見できなかった旨を前記探索の結果として出力する。【００９５】
また、本実施形態に係る探索装置において、
前記初期化部は、先行長および後行長を、第1初期値および第2初期値に初期化し、
前記取得部は、
(a) 前記算定された中間位置から先行長だけ前の位置もしくは前記テキストファイルの先頭から、
(b) 前記算定された中間位置から後行長だけ後の位置もしくは前記テキストファイルの末尾まで
のデータを、前記記録部から読み出し、前記読み出されたデータから前記中間行の取得を試行し、前記中間行の取得ができなければ、前記先行長および前記後行長を増加させて、前記中間行の取得を再試行する
ように構成することができる。【００９６】
また、本実施形態に係る探索装置において、
前記中間行の取得ができたときの前記先行長および前記後行長を、次の探索における第1初期値および第2初期値とする
ように構成することができる。【００９７】
また、本実施形態に係る探索装置において、
前記初期化部は、
(1) 先行長を、前記複数の行の最大長と改行の長さとの和から1を減じた値以上に設定し、
(2) 後行長は、前記複数の行の最大長以上に設定し、
前記取得部は、
(a) 前記算定された中間位置から先行長だけ前の位置もしくは前記テキストファイルの先頭から、
(b) 前記算定された中間位置から後行長だけ後の位置もしくは前記テキストファイルの末尾まで
のデータを、前記記録部から読み出し、前記読み出されたデータから前記中間行を取得する
ように構成することができる。【００９８】
また、本実施形態に係る探索装置において、
前記最大長は、前記取得部による前記中間行の取得ができなければ、前記テキストファイルを走査することにより、同定される
ように構成することができる。【００９９】
また、本実施形態に係る探索装置において、
前記最大長は、前記テキストファイルが更新されるごとに、同定される
ように構成することができる。【０１００】
本実施形態に係る探索方法は、
複数の行が並べられたテキストファイルであって、前記複数の行は前記複数の行のそれぞれに含まれるキーの順に並べられ、前記複数の行のそれぞれの末尾には改行が配置されるテキストファイルが記録された記録部を探索
探索装置が、探索をするためのパターンを受け付ける受付ステップ、
前記探索装置が、前記テキストファイルの先頭および末尾の位置を、探索範囲の下限および上限に設定する初期化ステップ、
前記探索装置が、前記下限と前記上限との間の中間位置を算定する算定ステップ、
前記探索装置が、前記記録部に記録されたテキストファイルから、
(x) 前記算定された中間位置もしくは当該中間位置より前を先頭とし、
(y) 前記算定された中間位置より後を末尾とする
中間行を取得する取得ステップ、
前記取得された中間行に含まれるキーと、前記受け付けられたパターンと、が、マッチすれば、前記探索装置が、前記取得された中間行を前記探索の結果として出力する出力ステップ、
前記取得された中間行に含まれるキーが、前記受け付けられたパターンより、
(p) 大きければ、前記探索装置が、前記中間行の先頭の位置を、前記下限に再設定し、
(q) 小さければ、前記探索装置が、前記中間行の末尾の位置を、前記上限に再設定して、
前記上限から1つの改行の長さだけ後の位置が前記下限より前であれば、前記探索装置が、前記算定ステップおよび前記取得ステップを繰り返す制御ステップ
を備え、
前記上限から1つの改行の長さだけ後の位置が前記下限より前でなければ、前記探索装置が、前記受け付けられたパターンにマッチする行が発見できなかった旨を前記探索の結果として出力する。【０１０１】
本実施形態に係るプログラムは、
複数の行が並べられたテキストファイルであって、前記複数の行は前記複数の行のそれぞれに含まれるキーの順に並べられ、前記複数の行のそれぞれの末尾には改行が配置されるテキストファイルが記録された記録部を有するコンピュータを、
探索をするためのパターンを受け付ける受付部、
前記テキストファイルの先頭および末尾の位置を、探索範囲の下限および上限に設定する初期化部、
前記下限と前記上限との間の中間位置を算定する算定部、
前記記録部に記録されたテキストファイルから、
(x) 前記算定された中間位置もしくは当該中間位置より前を先頭とし、
(y) 前記算定された中間位置より後を末尾とする
中間行を取得する取得部、
前記取得された中間行に含まれるキーと、前記受け付けられたパターンと、が、マッチすれば、前記取得された中間行を前記探索の結果として出力する出力部、
前記取得された中間行に含まれるキーが、前記受け付けられたパターンより、
(p) 大きければ、前記中間行の先頭の位置を、前記下限に再設定し、
(q) 小さければ、前記中間行の末尾の位置を、前記上限に再設定して、
前記上限から1つの改行の長さだけ後の位置が前記下限より前であれば、前記算定部による算定および前記取得部による取得を繰り返す制御部
として機能させ、
前記上限から1つの改行の長さだけ後の位置が前記下限より前でなければ、前記出力部は、前記受け付けられたパターンにマッチする行が発見できなかった旨を前記探索の結果として出力する。【０１０２】
本実施形態において、前記プログラムは、非一時的なコンピュータ読取可能な情報記録媒体に記録され、
前記プログラムは、前記コンピュータが有するメモリへロードされて、前記コンピュータが有するプロセッサにより実行され、
前記プログラムは、前記プロセッサを、
前記受付部として機能させる受付コード、
前記初期化部として機能させる初期化コード、
前記算定部として機能させる算定コード、
前記取得部として機能させる取得コード、
前記制御部として機能させる制御コード
を含み、
前記下限、前記上限、前記中間位置、前記中間行、および、前記探索の結果は、前記メモリに格納される
ように構成することができる。【０１０３】
本発明は、本発明の広義の精神と範囲を逸脱することなく、様々な実施の形態及び変形が可能とされるものである。また、上述した実施の形態は、この発明を説明するためのものであり、本発明の範囲を限定するものではない。すなわち、本発明の範囲は、実施の形態ではなく、特許請求の範囲によって示される。そして、特許請求の範囲内及びそれと同等の発明の意義の範囲内で施される様々な変形が、この発明の範囲内とみなされる。
【産業上の利用可能性】
【０１０４】
本発明によれば、テキストファイルを二分探索する探索装置、探索方法、プログラム、ならびに、情報記録媒体を提供することができる。
【符号の説明】
【０１０５】
101 探索装置
102 記録部
103 初期化部
104 受付部
105 算定部
106 取得部
107 出力部
108 制御部
【図１】
2018055680.tif 000003
【図２】
2018055680.tif 000004
【図３】
2018055680.tif 000005
【図４】
2018055680.tif 000006
【図５】
2018055680.tif 000007
【国際調査報告】
2018055680.tif 000008
2018055680.tif 000009