(57)【特許請求の範囲】
【請求項１】
キーワードを含むデータを検索する情報検索装置において、
検索対象データを構成する文字の出現順序番号を計算する文字情報抽出手段と、
検索対象データの隣接する文字の組と、前記文字の各出現順序番号を組合せた出現順序番号パターンとを対応させて検索ファイルを作成する検索ファイル生成手段と、
前記検索ファイルから、キーワードにおける隣接する文字の組に対応する出現順序番号パターンを検索し、得られた出現順序番号パターンを照合してキーワードを含む検索対象データを検索する検索手段と
を設けたことを特徴とする情報検索装置。
【請求項２】
前記検索ファイル生成手段が、前記出現順序番号パターンを前記検索ファイル上に昇順または降順に配列し、前記検索手段が、前記検索ファイル上で昇順または降順を満たす範囲にある前記出現順序番号パターンを前記照合に使用することを特徴とする請求項１に記載の情報検索装置。
【請求項３】
前記検索ファイル生成手段が、前記検索ファイルの作成に当たって、前記出現順序番号パターンの配列の終端に、その前に在る出現順序番号パターンと同じ出現順序番号パターンを付け加え、前記検索手段が、付け加えられた前記出現順序番号パターンに前記照合の順番が達したとき、前記照合を止めることを特徴とする請求項２に記載の情報検索装置。
【請求項４】
前記検索ファイルにおける出現順序番号パターンの配列の終端に空白の拡張領域を付け加えるとともに、検索対象データの変更に伴って出現順序番号パターンの追加が必要になったときに、前記拡張領域に前記出現順序番号パターンを追加する検索ファイル修正手段を設けたことを特徴とする請求項１乃至３に記載の情報検索装置。
【請求項５】
前記検索ファイルに記述された出現順序番号パターンの内から、キーワードの検索に使用する有効出現順序番号パターンの範囲を特定するために、有効出現順序番号パターンの配列の終端にその前に在る出現順序番号パターンと同じ出現順序番号パターンを書き加え、有効でない出現順序番号パターンだけの配列の前に空白の拡張領域を付け加える検索ファイル修正手段を設けたことを特徴とする請求項１乃至３に記載の情報検索装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、データベースからキーワードで指定された文字列を含むデータを検索する情報検索装置に関し、特に、検索処理及びデータベースへのデータの追加、更新、削除に関する処理を高速で行なえるようにしたものである。
【０００２】
【従来の技術】
近年、情報検索では、利用者が思いついた言葉をキーワードとして入力すると、データベースに登録されたデータを全文検索して、そのキーワードの文字列を含むデータを自動検索するシステムが注目を集めている。特に、リレーショナルデータベース管理システム（ＲＤＢＭＳ）などではその製品化が図られており、多方面での応用が広まっている。
【０００３】
この種の情報検索装置は、例えば特開昭６３−１５５３２４、特開平１−２８２６３５、特開平２−３０２８６９、特開平３−１１３６２６に示されている。特開昭６３−１５５３２４（情報検索装置）では、操作者が指定した検索キ−ワ−ドに対して、登録データを１サイクル毎に１ワ−ドづつシフトさせて比較し情報検索を行なっている。また、特開平１−２８２６３５（索引保守方式）では、登録データの検索に使用する索引として、主索引と比較的小さな副索引とを保持し、追加する登録データの索引レコ−ドを副索引に加えることにより、登録デ−タの更新・追加・削除を高速化している。また、特開平３−１１３６２６（バツフア制御方式及び装置）では、バツフア内のデ−タの検索と、補助記憶装置からバツフアへのデ−タの転送とを並行して実行することにより、タスクのスル−プツトの向上を図っている。また、特開平２−３０２８６９（フアイル編集方式）では、メモリ領域の無駄を無くすとともに、メモリ上の処理対象デ−タを高速に特定できるようにするため、メモリの空きエリアポインタを保持するテ−ブルを作成し、このテ−ブルを参照してメモリ上の処理対象文字列デ−タを特定している。
【０００４】
これらの４つの従来の情報検索装置では、記憶領域にデータ用領域とデータ更新用領域とをレコード番号単位で確保し、データ更新時にはデータ更新用領域にデータを蓄えて、データ用領域とデータ更新用領域とを置き換える方式（特開昭６３−１５５４３２４、特開平１−２８２６３５、特開平２−３０２８６９）や、検索ファイルに格納された文字列データとそのレコードとの対応表（テーブル）を使ってデータの追加・更新・削除を行なう方式（特開平２−３０２８６９）が採られており、本発明は後者に対応する。
【０００５】
次に、従来の情報検索装置における、データの登録、変更、削除の処理について説明する。図１９は従来の情報検索装置の処理図を、また、図２０は従来の情報検索装置でのテーブルとデータの流れとを示している。検索対象ファイルとしてテーブル図２０（ａ）の３レコードを例として説明する。ここで、Ａレコードでは２文字と２文字が各々データ構造として蓄えられ、Ｂレコードでは２文字と５文字が蓄えられるものとする。この時、Ａレコードの「１２」とＡレコードの「あい」が対応し、Ａレコードの「３４」とＡレコードの「うえ」が対応するエリアとなる。データの登録、変更、削除の処理は、図１９に示すように、
ステップ１：検索対象ファイルの図２０（ａ）のテーブルを検索対象レコードとして順次読み込み、
ステップ２：各文字の位置（レコードの何番目か）、文字サイズ、同じアイテム（項目）へのポインタをセットし、図２０（ａ）のテーブルを図２０（ｂ）のテーブルに変換する処理をメモリ上で行なう。例えば、ポインタのセットは第一レコードＡの「１２」と第三レコードＡの「あい」が同じアイテムであることから「あい」へのポインタｐ１をセットする。以下同様に第一レコードＡの「３４」が第三レコードＡの「うえ」へのポインタをセットする処理をする。
【０００６】
ステップ３：以上の処理を、図２０（ａ）のテーブルの最後まで繰り返し、
ステップ４：メモリの空きエリアにテーブルをセットすることにより図２０（ｂ）のテーブルが最終的に作成される。
【０００７】
ステップ５：データを更新する場合、例えば図２０（ａ）で第一レコードＡの「３４」を「５６」に更新する場合には、図２０（ｂ）のテーブルからレコードＡを調べ、第３行目の内容「３４」を検出して、「５６」に書き換える。サイズ、ポインタの変更は発生しない。
【０００８】
また、削除の場合、例えば図２０（ａ）で第三レコードＡの「うえ」を削除する場合には、図２０（ｂ）のテーブルからレコードＡを調べ、このテーブルから第３行目のｐ２へのポインタを辿って第７行目の内容「うえ」を検出し、削除する。このとき、第３行目の「ｐ２へ」のポインタも併せて削除する。
【０００９】
このように、従来の情報検索装置では、先頭番地、サイズ、ポインタを手掛かりにテーブルを辿り、登録、更新、削除を実現する。
【００１０】
【発明が解決しようとする課題】
しかし、従来の情報検索装置では、データベースのデータ数が多くなると、キーワードで指定された文字列を含むデータの全文検索に長い時間が掛かり、そのため、より高速での検索方式が求められている。
【００１１】
また、従来の情報検索装置では、データの更新または削除時に、その処理のために更新または削除するレコード分の拡張領域を確保する必要があり、膨大な記憶領域を用意しなければならないという問題があった。
【００１２】
また、データの更新または削除を行なった後に、レコードの順番を整えるためのソーティングの処理が必要になり、そのため、データの更新、削除に時間が掛かるという問題があった。
【００１３】
また、データの更新または削除時には、データがぎっしり詰まった検索ファイル中に更新後の情報を挿入したり、このファイル中からデータを削除しているため、その挿入位置や削除位置より後方のデータについては全てシフトさせなければならず、更新や削除に時間が掛かるいう問題があった。
【００１４】
また、削除するデータについて削除用のフラグを立てて間に合わせる方式もあるが、この場合には、削除データの増加に伴って、検索ファイルが増大化してしまうという問題点を有していた。
【００１５】
本発明は、こうした従来の問題点を解決するものであり、キーワードで指定された文字列などを含むデータがデータベースに存在するか否かを高速で検索することができ、また、データの更新、削除を迅速に行なうことができる情報検索装置を提供することを目的としている。
【００１６】
【課題を解決するための手段】
そこで、本発明では、キーワードを含むデータを検索する情報検索装置において、検索対象データを構成する文字の出現順序番号を計算する文字情報抽出手段と、検索対象データの隣接する文字の組とこの文字の各出現順序番号を組合せた出現順序番号パターンとを対応させて検索ファイルを作成する検索ファイル生成手段と、検索ファイルからキーワードにおける隣接する文字の組に対応する出現順序番号パターンを検索し、得られた出現順序番号パターンを照合してキーワードを含む検索対象データを検索する検索手段とを設けている。
【００１７】
また、検索ファイル生成手段が、出現順序番号パターンを検索ファイル上に昇順または降順に配列し、検索手段が、検索ファイル上で昇順または降順を満たす範囲にある出現順序番号パターンを照合に使用している。
【００１８】
また、検索ファイル生成手段は、検索ファイルの作成に当たって、出現順序番号パターンの配列の終端にその前に在る出現順序番号パターンと同じ出現順序番号パターンを付け加え、検索手段は、付け加えられた出現順序番号パターンに照合の順番が達したときその照合を止める。
【００１９】
また、検索ファイルにおける出現順序番号パターンの配列の終端に空白の拡張領域を付け加えるとともに、検索対象データの変更に伴って出現順序番号パターンの追加が必要になったときにこの拡張領域に出現順序番号パターンを追加する検索ファイル修正手段を設けている。
【００２０】
また、検索ファイルに記述された出現順序番号パターンの内からキーワードの検索に使用する有効出現順序番号パターンの範囲を特定するために、有効出現順序番号パターンの配列の終端にその前に在る出現順序番号パターンと同じ出現順序番号パターンを書き加え、有効でない出現順序番号パターンだけの配列の前に空白の拡張領域を付け加える検索ファイル修正手段を設けている。
【００２１】
【作用】
この情報検索装置では、検索対象データの文字種ごとの出現順序番号、つまり、各文字がその文字種において何番目に出現した文字であるかを計算し、データの文字列を１文字ずつずらしながら、その文字と隣接する文字とから成る文字パターンの各文字の出現順序番号を組にした出現順序番号パターンを求め、この出現順序番号パターンを集めて検索ファイルを構成する。検索時には、キーワードを複数の文字パターンに分割し、各文字パターンに対応する出現順序番号パターンをこの検索ファイルから求め、その出現順序番号パターンを照合し、各文字パターンが検索対象データにおいて連続していると判明したとき、そのデータがキーワードを含むものとして検出している。
【００２２】
この情報検索装置では、出現順序番号を利用する方式であるために、パターンの所在場所を文字位置で押さえる従来方式に比較して、検索ファイルのサイズを小さくできる。また、キーワードの検索に当たっては、検索対象データの文字列の中から、キーワードの文字パターンに一致する文字パターンだけを検索ファイルより読出し、その出現順序番号パターンを基にキーワードの包含の有無を照合しているため、検索対象データの全ての文字列を照合対象とする必要がないので、高速での検索が可能となる。
【００２３】
また、検索ファイルでの出現順序番号パターンの順番を昇順または降順に設定し、検索時には、この昇順または降順を満たす範囲で出現順序番号パターンの照合を進めることにより、照合の不必要な相手を高速で確認することができる。そのため、照合回数を減らすことができ、検索を高速化することができる。
【００２４】
データ更新時には、検索ファイルの出現順序番号パターンまたは拡張領域の上に新たな出現順序番号パターンを上書きすることができるため、検索ファイルのデータを一つずつずらすなどの処理が不要であり、検索ファイルの更新を高速で行なうことができる。また、出現順序番号パターンの書き加えが可能な拡張領域を、出現順序番号パターンの各配列の後に設けることにより、検索ファイル中での拡張領域の配置割合が一定化し、更新処理時間の平均化を図ることができ、更新時間の目安を立てることができる。
【００２５】
また、データの削除時には、検索ファイルの関連データを全て削除する代わりに、無効となる出現順序番号パターンの配列の前に、昇順または降順を崩す出現順序番号パターンや空白の拡散領域を設けることによって、有効出現順序番号パターンと区別することができる。そのため、検索ファイルを削除する必要がないので、短時間で削除処理を実現することができる。
【００２６】
なお、本明細書では、「文字」という用語を、文字データだけでなく、パターン化または記号化されたデータの全てを含むものとして用いている。本発明の情報検索装置は、文字データだけでなく、パターン化または記号化されたデータの全てを対象として、そのデータの登録、更新、削除、検索を実現することができる。
【００２７】
【実施例】
（第１実施例）
実施例の情報検索装置では、テキストの文字列が例えば「ああいああいあんんああんあい」である場合に、図３に示すように、文字種（「あ」「い」「ん」）別の出現順序番号（なお、図面では「出現順序番号」を「出現度数」と表示している。）、即ち、文字列のそれぞれの「あ」が何番目の「あ」であるか、それぞれの「い」が何番目の「い」であるか、また、それぞれの「ん」が何番目の「ん」であるかを求めて文字パターン度数表（図３）を作成し、次いで、文字列の連続する２文字の組を文字パターンとして、その文字パターンに対応する出現順序番号のパターンを求める。文字列の「ああいあ」に対して、文字パターンは（あ，あ）（あ，い）（い，あ）であり、各文字パターンの出現順序番号パターンは（１，２）（２，１）（１，３）となる。次に、文字パターンごとに出現順序番号パターンを集めて、図５に示す各テキストごとの出現順序番号リスト（インデックスファイル）を作成する。
【００２８】
一方、キーワードの文字列が「あいあ」である場合に、この文字列の文字パターンは（あ，い）（い，あ）である。キーワードとテキストとの照合に際しては、まず、テキストの出現順序番号リストから、キーワードの文字パターンに対応する出現順序番号パターンを得る。図５の出現順序番号リストから得た（あ，い）の出現順序番号パターンは（２，１）（４，２）（８，３）であり、（い，あ）の出現順序番号パターンは（１，３）（２，５）である。この（あ，い）の出現順序番号パターンの第２要素と、（い，あ）の出現順序番号パターンの第１要素とが一致するとき、テキストはキーワードの文字列「あいあ」を含むことになる。この例の場合、（２，１）の第２要素（１）と（１，３）の第１要素（１）とが一致し、また、（４，２）の第２要素（２）と（２，５）の第１要素（２）とが一致するから、このテキストは「あいあ」というキーワードを含んでいる。
【００２９】
実施例の情報検索装置は、基本的にこうした方式でキーワードを含むテキストを検索する。この装置は、図１に示すように、検索対象のテキストデータを収めたテキストデータベース31と、テキストデータベース31からテキストを一つずつ読込んで各テキストごとのテキストレコードを生成するテキスト生成部32と、検索したいキーワードを読み込むキーワード読込部38と、テキスト修正用の修正テキストデータを読込む修正テキスト読取部312と、テキストレコードや修正用のテキストレコードから文字パターン度数表を作成し、またキーワードから文字パターンを作成する連続文字情報抽出部33と、文字パターン度数表から文字パターンとその出現順序番号パターンとより成るインデックスファイルデータを作成するインデックス生成部35と、連続文字情報抽出部33で作成される文字パターン度数表やインデックス生成部35で作成されるインデックスファイルを格納するインデックスファイル記憶部34と、インデックスファイルの出現順序番号パターンリストの最後に拡張領域を追加する拡張領域生成部36と、インデックスファイルのデータとキーワードの文字パターンとを照合してキーワードの文字パターンがテキスト中に連続する状態で含まれているかどうかを検索するインデックス検索部39と、照合すべき出現順序番号パターンが無くなったときにインデックス検索部39に照合の停止を命令する文字度数存在検索部310と、インデックス検索部39の検索結果を表示出力する検索結果出力部311と、テキスト修正時にインデックスファイルの出現度数パターンを更新する更新データ生成部37とを備えている。
【００３０】
第１実施例では、テキストからインデックスファイルを生成する動作と、このインデックスファイルを使ってキーワードが含まれるテキストを検索する動作とについて説明する。この場合、図１の情報検索装置の修正テキスト読取部312及び更新データ生成部37は使用しない。
【００３１】
インデックスファイルの生成は図２の処理フローに従って行なわれる。
【００３２】
ステップ１：先ず、テキスト生成部32は、テキストデータベース31からテキストを読込み、そのテキストのテキストレコードにレコード番号Niを付与する。いま、このテキストレコードが「ああいああいあんんああんあい」であるとする。  ステップ２：連続文字情報抽出部33は、テキストレコードの先頭の文字にポインタｐをセットし、文字種の出現順序番号N(A)のカウント値を初期化した後、
ステップ３：ポインタ位置における文字の
ステップ４：文字種ごとの出現順序番号をカウントし、
ステップ５：文字パターン度数表（図３）を作成して、インデックスファイル記憶部34に格納する。この表には文字種ごとの出現順序番号とレコード番号との組が記述される。
【００３３】
ステップ６：ポインタ位置がテキストレコードの最後の文字に達していないときは、
ステップ７：ポインタを次の文字に移し、ステップ３に戻って、その文字の文字種ごとの出現順序番号を調べる。
【００３４】
この手順を繰り返して、レコード番号Niのテキストレコードに関する文字パターン度数表の作成が終了すると、
ステップ８：インデックス生成部35は、この文字パターン度数表のテキストレコードの先頭に、文字パターン（２文字ずつの文字の組）を指定するポインタｉをセットし、
ステップ９：ポインタｉの指し示す文字パターンの各文字における出現順序番号を求め、
ステップ10：この出現順序番号の組から成る出現順序番号パターンを、文字パターンと対応させてインデックスファイル（図５）に記録する。また、インデックスファイルにはレコード番号Niを併せて記録する。
【００３５】
ステップ11：ポインタｉがテキストレコードの終端に達していなければ、
ステップ12：ポインタｉを１文字分移動して、ステップ９に戻り、
文字パターン度数表からポインタの指し示す文字パターンの出現順序番号パターンを求め、その文字パターンが未だインデックスファイルに記録されていないときは、その文字パターンと出現順序番号パターンとを対応させてインデックスファイルに記録し、併せてレコード番号Niを記録する。また、その文字パターンが既にインデックスファイルに記録されているときは、その文字パターンに対応する出現順序番号パターンリストの末尾に、求めた出現順序番号パターンを記録する。
【００３６】
こうした手順を繰り返し、ポインタｉがテキストレコードの終端にまで達すると、
ステップ13：領域拡張生成部36は、インデックスファイルの全ての出現順序番号パターンリストの最後尾に拡張領域を設け、そこを空白領域としたり、またはそこに最後の出現順序番号パターンと同じ出現順序番号パターンを記録する。
【００３７】
図６に拡張領域を加えたインデックスファイルのデータ構造を示している。なお、このファイルの出現順序番号パターンリストでは、出現順序番号パターンを構成する個々の要素が昇順に並んでいる。即ち、出現順序番号リストの要素を（Ai，Bi）とすると、A1＜A2＜‥＜Am、B1＜B2＜‥＜Bmの関係が成り立つ。
【００３８】
ステップ14：以上の処理を、テキストデータベース31から順番に読出したテキストレコードに対して繰り返し、
ステップ15：テキストデータベース31に格納されたテキストの全てに対する処理が終えると、インデックスファイルの生成を終了する。
【００３９】
次に、インデックスファイルを使ってキーワードが含まれるテキストを検索する動作について説明する。これは図７の手順で行なわれる。ここでは、キーワードが「あいあ」であるとする。
【００４０】
ステップ１：先ず、キーワード読取部38はキーワードを読み込み、
ステップ２：連続文字情報抽出部33は、このキーワードを２文字ずつの文字パターンの組（A[p]，B[p+1]）（B[p+1]，C[p+2]）‥に分解する。ここでA[p]はキーワードのｐ番目の文字Ａを示す。キーワード「あいあ」の場合には（あ，い）と（い，あ）とに分解される。
【００４１】
ステップ３：連続文字情報抽出部33は、レコード番号Niをセットし、
ステップ４：ポインタｐをキーワードの先頭文字位置にセットして、
ステップ５：キーワードの最初の２つの文字パターン、実例では（あ，い）と（い，あ）、を照合の対象として設定する。
【００４２】
ステップ６：インデックス検索部39は、インデックスファイル記憶部34に格納されたレコード番号Niのインデックスファイル（図６）から、第１の文字パターン（あ，い）の出現順序番号リスト（M[p][j]，N[p][j]）の先頭（ｊ＝１）の出現順序番号パターン（２，１）を読取り、
ステップ７：また、第２の文字パターン（い，あ）の出現順序番号リスト（M[p+1][ｋ]，N[p+1][ｋ]）の先頭（ｋ＝１）の出現順序番号パターン（１，３）を読取る。  ここでキーワード「あいあ」に対応するインデックスファイルを図８に示す。文字パターン（A[p]，B[p+1]）＝（あ，い）及び(B[p+1]，C[p+2]）＝（い，あ）に対して、出現順序番号パターンは、それぞれ（MA[p][1]，MB[p+1][1]）＝（２，１）‥(MA[p][n]，MB[p+1][n]）＝（８，３）と（MB[p+1][1]，MC[p+2][1]）＝（１，３）‥(MB[p+1][n]，MC[p+2][n]）＝（２，５）とが対応する。このMA[q][j]は文字Ａ、キーワード文字列のｑ番目の文字パターンに関するｊ番目の出現度数パターンを意味する。また、各文字パターンに対する出現順序番号パターンの終端には拡張領域として空欄または最後の出現順序番号パターンと同じ出現順序番号パターンが格納されている。
【００４３】
ステップ８：インデックス検索部39は、図９に示すように、第１の文字パターンにおける出現順序番号パターン（２，１）の第２要素と、第２の文字パターンにおける出現順序番号パターン（１，３）の第１要素とが一致するかどうかをチェックし、第１の文字パターンと第２の文字パターンとが連続しているかどうかを照合する。それらが一致しているときは、
ステップ９：検索結果出力部311に、連続する文字「あいあ」とインデックス
ファイルのレコード番号Niとを出力する。
【００４４】
ステップ10：インデックス検査部39は、次の連続性の照合のために、第１の文字パターンにおける出現順序番号パターンの第２要素（N[p][j]）と第２の文字パターンにおける出現順序番号パターンの第１要素（M[p+1][k])との大きさを比較し、第１要素（M[p+1][k])の方が大きいとき、または、第２要素（N[p][j]）と第１要素（M[p+1][k])とが等しいときには、
ステップ11：ｊをインクリメントし、
ステップ12：第１の文字パターンにおける出現順序番号パターンの第２要素（N[p][j]）の方が大きいとき、または、第２要素（N[p][j]）と第１要素（M[p+1][k])とが等しいときには、
ステップ13：ｋをインクリメントする。
【００４５】
ステップ14：出現順序番号存在検索部310は、第１の文字パターンにおける出現度数パターンの第２要素（N[p][j]）と、その文字パターンにおける次の出現順序番号パターンの第２要素（N[p][j+1]）との大小を比較し、また、第２の文字パターンにおける出現順序番号パターンの第１要素（M[p+1][k]）と、その文字パターンにおける次の出現順序番号パターンの第１要素（M[p+1][k+1]）との大小を比較し、昇順の関係にあるときは、
ステップ15：ステップ８に戻って、更新した出現順序番号パターン間の第２要素と第１要素とを照合する。
【００４６】
また、ステップ14において、昇順の関係にないとき、つまり、次の出現順序番号パターンが、領域拡張生成部36によって出現順序番号リストの末尾に生成された空白領域または最後の出現順序番号パターンと同じ出現順序番号パターンを記録した領域に達したときは、その文字パターンに関する照合を終了する。
【００４７】
ここで、図１０にキーワード「あいあ」についての検索の流れを示す。第１文字パターン（あ，い）の出現順序番号リスト（２，１）（４，２）（８，３）（８，３）の最初の出現順序番号パターン（２，１）と、第２文字パターン（い，あ）の出現順序番号リスト（１，３）（２，５）（２，５）の最初の出現順序番号パターン（１，３）とを比較し、第１の出現順序番号パターンの第２要素「１」が第２の出現順序番号パターンの第１要素「１」と一致するので、その結果を検索結果出力部311に格納する。続いて第１文字パターンにおける２番目の出現順序番号パターン（４，２）と、第２文字パターンにおける２番目の出現順序番号パターン（２，５）とを比較し、第１の出現順序番号パターンの第２要素「２」が第２の出現順序番号パターンの第１要素「２」と一致するので、その結果も検索結果出力部311に格納する。続いて第１文字パターンにおける３番目の出現順序番号パターン（８，３）と、第２文字パターンにおける３番目の出現順序番号パターン（２，５）とを比較することになるが、この第２文字パターンにおける３番目の出現順序番号パターン（２，５）は、同じ文字パターンにおける２番目の出現順序番号パターン（２，５）に対して昇順の関係を満たしていない。そのため、この文字パターンの照合処理をここで終了する。
【００４８】
ステップ16：ステップ14において、その文字パターンに対する照合処理が終了したときは、キーワードの他の文字パターンとの照合が済んでいるかどうかを調べ、済んでいなければ、
ステップ17：ステップ５以下の処理を行なう。
【００４９】
ステップ18：キーワードの全ての文字パターンについての連続性の照合が終了したときは、そのキーワードの全ての文字パターンに対してステップ９の照合結果が得られているかどうかを調べ、得られているときは、レコード番号Niのテキストを、キーワードを含むものとして表示する。
【００５０】
このように実施例の情報検索装置では、テキストの文字パターン（連続する文字種の組合せ）に、その文字パターンの出現順序番号パターンを昇順に配列した出現順序番号リストを対応させて、検索ファイルを作成し、この検索ファイルからキーワードの文字パターンに対応する各出現順序番号リストを読出し、そのリスト間の出現順序番号パターンを照合することによって、キーワードの文字列がテキストデータ中に存在しているかどうかを検索する。この出現順序番号パターンの照合では、出現順序番号パターンが昇順に並んでいるため、出現順序番号パターン同士を網羅的に照合する必要が無く、少ない照合回数で検索することができる。従って、高速での検索が可能になる。
【００５１】
なお、出現順序番号リストにおける出現順序番号パターンの順序は降順にしてもよい。また、この情報検索装置は、文字列データだけで無く、その他のパターン化されたデータのパターン列を検索対象とすることができる。
【００５２】
（第２実施例）
第２実施例では、データベースに格納されたテキストの変更に伴うインデックスファイルのデータ更新について説明する。
【００５３】
図１の情報検索装置において、修正テキスト読込部312は、テキストデータ番号が付けられたテキスト更新用の修正テキストデータを読み込み、連続文字情報抽出部33は、修正テキストデータから文字パターン度数表を作成する。作成された文字パターン度数表はインデックスファイル記憶部34に格納される。インデックス生成部35は、この文字パターン度数表から文字パターン毎の出現順序番号パターンを作成し、更新データ生成部37は、既にあるインデックスファイルの出現順序番号パターンリストにこの出現順序番号パターンを上書きする。また、拡張領域生成部36は、出現順序番号パターンの数が既にある出現順序番号パターンリストを超えた場合に出現順序番号パターン用の拡張領域を追加する。
【００５４】
このテキスト変更に伴うインデックスファイルデータの更新の動作を図１１の処理フローを用いて説明する。ここではテキストレコードの「ああいああいあんんああんあい」を「ああいあいいあんああいんあい」に変更する場合を例に説明をする。
【００５５】
ステップ１：先ず、修正テキスト読取部312は、変更後のテキストレコードを読み取り、レコード番号をセットする。
【００５６】
ステップ２：連続文字情報抽出部33は、ポインタｐをテキストレコードの先頭文字「あ」にセットし、文字種の出現順序番号N(A)のカウント値を初期化した後、
ステップ３：ポインタ位置における文字の
ステップ４：文字種ごとの出現順序番号をカウントし、
ステップ５：文字パターン度数表（図１２）を作成して、インデックスファイル記憶部34に格納する。この表には更新後テキストレコードの文字種ごとの出現順序番号がレコード番号とともに記述される。
【００５７】
ステップ６：ポインタ位置が更新後テキストレコードの最後の文字に達していないときは、
ステップ７：ポインタを次の文字に移し、ステップ３に戻って、その文字の文字種ごとの出現順序番号を調べる。
【００５８】
この手順を繰り返して、レコード番号Niの更新後テキストレコードに関する文字パターン度数表の作成が終了すると、
ステップ８：インデックス生成部35は、テキストレコード番号Niに対応するインデックスファイルをインデックスファイル記憶部34から探索し、このファイルの先頭にポインタをセットした後、
ステップ９：文字パターン度数表（図１２）の更新後テキストレコードの先頭に、文字パターン（２文字ずつの文字の組）を指定するポインタｉをセットし、
ステップ10：ポインタｉの指し示す文字パターンの各文字における出現順序番号を求める。
【００５９】
ステップ11：更新データ生成部37は、この出現順序番号の組から成る出現順序番号パターンを、ポインタの指し示すインデックスファイルの出現順序番号パターンリストに記述されている出現順序番号パターンや拡張領域の上に上書きする。
【００６０】
ステップ12：出現順序番号パターンリストが一杯になると、拡張領域生成部36は、リストの最後尾に拡張領域を追加する。
【００６１】
ステップ13：インデックス生成部35は、ポインタｉが更新後テキストレコードの終端にまで達していなければ、
ステップ14：ポインタｉを１文字分移動して、ステップ10に戻り、その文字パターンの出現順序番号パターンを求める動作を繰り返す。
【００６２】
ステップ15：ポインタｉがテキストレコードの終端にまで達すると、更新データ生成部37は、全ての出現順序番号パターンリストの最後尾にリスト最後の出現順序番号パターンと同じ出現順序番号パターンを生成し、また、拡張領域生成部36は、全ての出現順序番号パターンリストの最後に拡張領域を追加する。また、更新データ生成部37は、上書きがされなかった更新前のテキストレコードに関する出現順序番号パターンの全てを拡張領域に更新する。
【００６３】
図１３に更新用テキストレコードにおける出現順序番号パターンリストとインデックスファイルとの関係を示し、図１４に更新した後のインデックスファイルの構成図を示している。出現順序番号パターンリストの最後には同一の出現順序番号パターンと拡張領域とが追加されている。また、文字パターン（ん，ん）のように、更新前は出現順序番号パターンが存在したが更新後出現しないものについては拡張領域に置き代わっている。
【００６４】
更新されたインデックスファイルを用いて行なわれる検索の処理手順は図７と同様である。
【００６５】
このように、実施例の情報検索装置では、インデックスファイルの出現順序番号パターンリストの最後尾に空白の拡張領域を設けているため、更新される出現順序番号パターンの数が、既に登録されている出現順序番号パターンの数より多くなる場合でも、その拡張領域に直ちに上書きすることができるので、高速でのデータ更新が可能である。また、この拡張領域は、出現順序番号パターンを記録するエリアが不足しない程度に、その都度、拡張領域を追加する構成であるため、追加の手間が少なくて済む。また、膨大なインデックスファイルを予め用意する場合には、メモリ容量が徒に大きくなるだけでなく、消去や更新の対象となる出現順序番号パターンを調べるために手間取ることになるが、実施例の装置の場合には、そうした虞れが少なく、テキストデータの変更に伴うインデックスファイルの更新を高速で行なうことができる。
【００６６】
（第３実施例）
第３実施例では、テキストの一部が削除されたときのインデックスファイルの修正について説明する。
【００６７】
テキストレコード「ああいああいあんんああんあい」の後半を削除して、「ああいああいあん」に修正した場合を例として、その動作を説明する。このときの情報検索装置の動作手順を図１５に示している。この動作手順の内、ステップ１からステップ10までは、第２実施例で示したテキストレコードの更新時の動作（図１１）と同じである。削除後のテキストレコードにより、図１６に示す文字パターン度数表が構成され、インデックス生成部35は、この文字パターン度数表から文字パターンの各文字における出現順序番号を求める。
【００６８】
ステップ11：更新データ生成部37は、この出現順序番号の組から成る出現順序番号パターンを、既存の同一レコード番号を有するインデックスファイルの出現順序番号パターンリストに上書きする。
【００６９】
このとき、テキストレコードの一部削除によって出現順序番号パターンの数はそれまでより減少するので、出現順序番号パターンが拡張領域の上に上書きされることは無いし、また、拡張領域の追加が必要になる事態も発生しない。
【００７０】
図１６の文字パターン度数表を使って、文字パターンに対応する出現順序番号パターンを求める動作を削除後テキストレコードの終端まで行なったときに、図１７に示す出現順序番号パターンリストが得られる。
【００７１】
ステップ14：更新データ生成部37は、全ての出現順序番号パターンリストの最後尾にリスト最後の出現順序番号パターンと同じ出現順序番号パターンを追加し、また、削除後テキストレコードにおいて出現しなかった文字パターンについては出現順序番号パターンリストの先頭に拡張領域を追加する。
【００７２】
図１８に削除した後のインデックスファイルを示している。ここで、有効な出現順序番号パターンは太線で囲った部分であり、その他は検索に使用されない無効部分となる。
【００７３】
削除されたインデックスファイルの検索の処理手順は図７と同様である。なお、インデックスファイルの検索は出現順序番号パターンの要素が昇順を保っている範囲でのみ実行されるので、図１８に示すインデックスファイルの無効部分での検索は行なわれない。
【００７４】
このように第３実施例の情報検索装置では、インデックスファイルを削除する時に、不要なインデックスファイルを全て削除するのでは無く、インデックスファイルの最小限度の範囲を更新するだけで済ませている。従って、削除の手間が削減され、削除を高速で行なうことができる。
【００７５】
【発明の効果】
以上の実施例の説明から明らかなように、本発明の情報検索装置は、データベースから、指定されたキーワードを高速に検索することができ、また、データベースへのデータの追加、更新、削除の処理を高速で行なうことができる。
【００７６】
このデータベースへのデータの追加、更新、削除の際には、既存のインデックスファイルに拡張領域を設けたり、最後の出現順序番号パターンを再録することにより、インデックスファイルの修正を最小限に保ちながら、データの整理（ごみ削除）を行なうことができる。
【図面の簡単な説明】
【図１】  本発明の実施例における情報検索装置の構成を示すブロック図、
【図２】  第１実施例におけるインデックスファイル生成の処理フロー、
【図３】  第１実施例におけるテキストレコードに対する文字パターン度数表、
【図４】  第１実施例における出現順序番号リストの説明図、
【図５】  第１実施例における文字パターンと出現順序番号パターン、
【図６】  第１実施例におけるインデックスファイル、
【図７】  第１実施例におけるインデックスファイル検索の処理フロー、
【図８】  第１実施例における検索時の文字パターンと出現順序番号パターンリスト、
【図９】  第１実施例における連続性照合の説明図、
【図１０】  第１実施例における検索照合順の説明図、
【図１１】  第２実施例におけるインデックスファイル更新の処理フロー、
【図１２】  第２実施例における更新テキストレコードに対する文字パターン出現順序番号表、
【図１３】  第２実施例における文字パターンと出現順序番号パターン、
【図１４】  第２実施例におけるインデックスファイル、
【図１５】  第３実施例におけるインデックスファイル削除の処理フロー、
【図１６】  第３実施例における削除テキストレコードに対する文字パターン出現順序番号表、
【図１７】  第３実施例における文字パターンと出現順序番号パターン、
【図１８】  第３実施例におけるインデックスファイル、
【図１９】  従来の情報検索装置の処理の流れを示す図、
【図２０】  従来の情報検索装置のデータテーブルである。
【図１】
0003649472.tif 000002
【図２】
0003649472.tif 000003
【図３】
0003649472.tif 000004
【図４】
0003649472.tif 000005
【図５】
0003649472.tif 000006
【図６】
0003649472.tif 000007
【図７】
0003649472.tif 000008
【図８】
0003649472.tif 000009
【図９】
0003649472.tif 000010
【図１０】
0003649472.tif 000011
【図１１】
0003649472.tif 000012
【図１２】
0003649472.tif 000013
【図１３】
0003649472.tif 000014
【図１４】
0003649472.tif 000015
【図１５】
0003649472.tif 000016
【図１６】
0003649472.tif 000017
【図１７】
0003649472.tif 000018
【図１８】
0003649472.tif 000019
【図１９】
0003649472.tif 000020
【図２０】
0003649472.tif 000021