JPH08314975A

JPH08314975A - 情報検索装置

Info

Publication number: JPH08314975A
Application number: JP7145213A
Authority: JP
Inventors: Takamasa Koyama; 隆正小山; Tetsuya Kinoshita; 哲也木下; Hirofumi Shinoki; 裕文篠木; Chuichi Kikuchi; 忠一菊池
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1995-05-22
Filing date: 1995-05-22
Publication date: 1996-11-29
Anticipated expiration: 2020-05-18
Also published as: JP3649472B2

Abstract

(57)【要約】【目的】キーワードを含むデータを高速で検索するこ
とができる情報検索装置を提供する。【構成】キーワードを含むデータを検索する情報検索
装置において、検索対象データを構成する文字の出現度
数を計算する文字情報抽出手段33と、検索対象データの
隣接する文字の組とこの文字の各出現度数を組合せた出
現度数パターンとを対応させて検索ファイルを作成する
検索ファイル生成手段35と、検索ファイルからキーワー
ドにおける隣接する文字の組に対応する出現度数パター
ンを検索し、得られた出現度数パターンを照合してキー
ワードを含む検索対象データを検索する検索手段39とを
設ける。この装置では、出現度数を利用する方式である
ために、パターンの所在場所を文字位置で押さえる従来
方式に比較して、検索ファイルのサイズを小さくでき
る。また、検索ファイルに出現度数パターンを昇順また
は降順に配列することで検索を高速化することができ
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データベースからキー
ワードで指定された文字列を含むデータを検索する情報
検索装置に関し、特に、検索処理及びデータベースへの
データの追加、更新、削除に関する処理を高速で行なえ
るようにしたものである。

【０００２】

【従来の技術】近年、情報検索では、利用者が思いつい
た言葉をキーワードとして入力すると、データベースに
登録されたデータを全文検索して、そのキーワードの文
字列を含むデータを自動検索するシステムが注目を集め
ている。特に、リレーショナルデータベース管理システ
ム（ＲＤＢＭＳ）などではその製品化が図られており、
多方面での応用が広まっている。

【０００３】この種の情報検索装置は、例えば特開昭６
３−１５５３２４、特開平１−２８２６３５、特開平２
−３０２８６９、特開平３−１１３６２６に示されてい
る。特開昭６３−１５５３２４（情報検索装置）では、
操作者が指定した検索キ−ワ−ドに対して、登録データ
を１サイクル毎に１ワ−ドづつシフトさせて比較し情報
検索を行なっている。また、特開平１−２８２６３５
（索引保守方式）では、登録データの検索に使用する索
引として、主索引と比較的小さな副索引とを保持し、追
加する登録データの索引レコ−ドを副索引に加えること
により、登録デ−タの更新・追加・削除を高速化してい
る。また、特開平３−１１３６２６（バツフア制御方式
及び装置）では、バツフア内のデ−タの検索と、補助記
憶装置からバツフアへのデ−タの転送とを並行して実行
することにより、タスクのスル−プツトの向上を図って
いる。また、特開平２−３０２８６９（フアイル編集方
式）では、メモリ領域の無駄を無くすとともに、メモリ
上の処理対象デ−タを高速に特定できるようにするた
め、メモリの空きエリアポインタを保持するテ−ブルを
作成し、このテ−ブルを参照してメモリ上の処理対象文
字列デ−タを特定している。

【０００４】これらの４つの従来の情報検索装置では、
記憶領域にデータ用領域とデータ更新用領域とをレコー
ド番号単位で確保し、データ更新時にはデータ更新用領
域にデータを蓄えて、データ用領域とデータ更新用領域
とを置き換える方式（特開昭６３−１５５４３２４、特
開平１−２８２６３５、特開平２−３０２８６９）や、
検索ファイルに格納された文字列データとそのレコード
との対応表（テーブル）を使ってデータの追加・更新・
削除を行なう方式（特開平２−３０２８６９）が採られ
ており、本発明は後者に対応する。

【０００５】次に、従来の情報検索装置における、デー
タの登録、変更、削除の処理について説明する。図１９
は従来の情報検索装置の処理図を、また、図２０は従来
の情報検索装置でのテーブルとデータの流れとを示して
いる。検索対象ファイルとしてテーブル図２０（ａ）の
３レコードを例として説明する。ここで、Ａレコードで
は２文字と２文字が各々データ構造として蓄えられ、Ｂ
レコードでは２文字と５文字が蓄えられるものとする。
この時、Ａレコードの「１２」とＡレコードの「あい」
が対応し、Ａレコードの「３４」とＡレコードの「う
え」が対応するエリアとなる。データの登録、変更、削
除の処理は、図１９に示すように、ステップ１：検索対象ファイルの図２０（ａ）のテーブ
ルを検索対象レコードとして順次読み込み、ステップ２：各文字の位置（レコードの何番目か）、文
字サイズ、同じアイテム（項目）へのポインタをセット
し、図２０（ａ）のテーブルを図２０（ｂ）のテーブル
に変換する処理をメモリ上で行なう。例えば、ポインタ
のセットは第一レコードＡの「１２」と第三レコードＡ
の「あい」が同じアイテムであることから「あい」への
ポインタｐ１をセットする。以下同様に第一レコードＡ
の「３４」が第三レコードＡの「うえ」へのポインタを
セットする処理をする。

【０００６】ステップ３：以上の処理を、図２０（ａ）
のテーブルの最後まで繰り返し、ステップ４：メモリの空きエリアにテーブルをセットす
ることにより図２０（ｂ）のテーブルが最終的に作成さ
れる。

【０００７】ステップ５：データを更新する場合、例え
ば図２０（ａ）で第一レコードＡの「３４」を「５６」
に更新する場合には、図２０（ｂ）のテーブルからレコ
ードＡを調べ、第３行目の内容「３４」を検出して、
「５６」に書き換える。サイズ、ポインタの変更は発生
しない。

【０００８】また、削除の場合、例えば図２０（ａ）で
第三レコードＡの「うえ」を削除する場合には、図２０
（ｂ）のテーブルからレコードＡを調べ、このテーブル
から第３行目のｐ２へのポインタを辿って第７行目の内
容「うえ」を検出し、削除する。このとき、第３行目の
「ｐ２へ」のポインタも併せて削除する。

【０００９】このように、従来の情報検索装置では、先
頭番地、サイズ、ポインタを手掛かりにテーブルを辿
り、登録、更新、削除を実現する。

【００１０】

【発明が解決しようとする課題】しかし、従来の情報検
索装置では、データベースのデータ数が多くなると、キ
ーワードで指定された文字列を含むデータの全文検索に
長い時間が掛かり、そのため、より高速での検索方式が
求められている。

【００１１】また、従来の情報検索装置では、データの
更新または削除時に、その処理のために更新または削除
するレコード分の拡張領域を確保する必要があり、膨大
な記憶領域を用意しなければならないという問題があっ
た。

【００１２】また、データの更新または削除を行なった
後に、レコードの順番を整えるためのソーティングの処
理が必要になり、そのため、データの更新、削除に時間
が掛かるという問題があった。

【００１３】また、データの更新または削除時には、デ
ータがぎっしり詰まった検索ファイル中に更新後の情報
を挿入したり、このファイル中からデータを削除してい
るため、その挿入位置や削除位置より後方のデータにつ
いては全てシフトさせなければならず、更新や削除に時
間が掛かるいう問題があった。

【００１４】また、削除するデータについて削除用のフ
ラグを立てて間に合わせる方式もあるが、この場合に
は、削除データの増加に伴って、検索ファイルが増大化
してしまうという問題点を有していた。

【００１５】本発明は、こうした従来の問題点を解決す
るものであり、キーワードで指定された文字列などを含
むデータがデータベースに存在するか否かを高速で検索
することができ、また、データの更新、削除を迅速に行
なうことができる情報検索装置を提供することを目的と
している。

【００１６】

【課題を解決するための手段】そこで、本発明では、キ
ーワードを含むデータを検索する情報検索装置におい
て、検索対象データを構成する文字の出現度数を計算す
る文字情報抽出手段と、検索対象データの隣接する文字
の組とこの文字の各出現度数を組合せた出現度数パター
ンとを対応させて検索ファイルを作成する検索ファイル
生成手段と、検索ファイルからキーワードにおける隣接
する文字の組に対応する出現度数パターンを検索し、得
られた出現度数パターンを照合してキーワードを含む検
索対象データを検索する検索手段とを設けている。

【００１７】また、検索ファイル生成手段が、出現度数
パターンを検索ファイル上に昇順または降順に配列し、
検索手段が、検索ファイル上で昇順または降順を満たす
範囲にある出現度数パターンを照合に使用している。

【００１８】また、検索ファイル生成手段は、検索ファ
イルの作成に当たって、出現度数パターンの配列の終端
にその前に在る出現度数パターンと同じ出現度数パター
ンを付け加え、検索手段は、付け加えられた出現度数パ
ターンに照合の順番が達したときその照合を止める。

【００１９】また、検索ファイルにおける出現度数パタ
ーンの配列の終端に空白の拡張領域を付け加えるととも
に、検索対象データの変更に伴って出現度数パターンの
追加が必要になったときにこの拡張領域に出現度数パタ
ーンを追加する検索ファイル修正手段を設けている。

【００２０】また、検索ファイルに記述された出現度数
パターンの内からキーワードの検索に使用する有効出現
度数パターンの範囲を特定するために、有効出現度数パ
ターンの配列の終端にその前に在る出現度数パターンと
同じ出現度数パターンを書き加え、有効でない出現度数
パターンだけの配列の前に空白の拡張領域を付け加える
検索ファイル修正手段を設けている。

【００２１】

【作用】この情報検索装置では、検索対象データの文字
種ごとの出現度数、つまり、各文字がその文字種におい
て何番目に出現した文字であるかを計算し、データの文
字列を１文字ずつずらしながら、その文字と隣接する文
字とから成る文字パターンの各文字の出現度数を組にし
た出現度数パターンを求め、この出現度数パターンを集
めて検索ファイルを構成する。検索時には、キーワード
を複数の文字パターンに分割し、各文字パターンに対応
する出現度数パターンをこの検索ファイルから求め、そ
の出現度数パターンを照合し、各文字パターンが検索対
象データにおいて連続していると判明したとき、そのデ
ータがキーワードを含むものとして検出している。

【００２２】この情報検索装置では、出現度数を利用す
る方式であるために、パターンの所在場所を文字位置で
押さえる従来方式に比較して、検索ファイルのサイズを
小さくできる。また、キーワードの検索に当たっては、
検索対象データの文字列の中から、キーワードの文字パ
ターンに一致する文字パターンだけを検索ファイルより
読出し、その出現度数パターンを基にキーワードの包含
の有無を照合しているため、検索対象データの全ての文
字列を照合対象とする必要がないので、高速での検索が
可能となる。

【００２３】また、検索ファイルでの出現度数パターン
の順番を昇順または降順に設定し、検索時には、この昇
順または降順を満たす範囲で出現度数パターンの照合を
進めることにより、照合の不必要な相手を高速で確認す
ることができる。そのため、照合回数を減らすことがで
き、検索を高速化することができる。

【００２４】データ更新時には、検索ファイルの出現度
数パターンまたは拡張領域の上に新たな出現度数パター
ンを上書きすることができるため、検索ファイルのデー
タを一つずつずらすなどの処理が不要であり、検索ファ
イルの更新を高速で行なうことができる。また、出現度
数パターンの書き加えが可能な拡張領域を、出現度数パ
ターンの各配列の後に設けることにより、検索ファイル
中での拡張領域の配置割合が一定化し、更新処理時間の
平均化を図ることができ、更新時間の目安を立てること
ができる。

【００２５】また、データの削除時には、検索ファイル
の関連データを全て削除する代わりに、無効となる出現
度数パターンの配列の前に、昇順または降順を崩す出現
度数パターンや空白の拡散領域を設けることによって、
有効出現度数パターンと区別することができる。そのた
め、検索ファイルを削除する必要がないので、短時間で
削除処理を実現することができる。

【００２６】なお、本明細書では、「文字」という用語
を、文字データだけでなく、パターン化または記号化さ
れたデータの全てを含むものとして用いている。本発明
の情報検索装置は、文字データだけでなく、パターン化
または記号化されたデータの全てを対象として、そのデ
ータの登録、更新、削除、検索を実現することができ
る。

【００２７】

【実施例】

（第１実施例）実施例の情報検索装置では、テキストの
文字列が例えば「ああいああいあんんああんあい」であ
る場合に、図３に示すように、文字種（「あ」「い」
「ん」）別の出現度数、即ち、文字列のそれぞれの
「あ」が何番目の「あ」であるか、それぞれの「い」が
何番目の「い」であるか、また、それぞれの「ん」が何
番目の「ん」であるかを求めて文字パターン度数表（図
３）を作成し、次いで、文字列の連続する２文字の組を
文字パターンとして、その文字パターンに対応する出現
度数のパターンを求める。文字列の「ああいあ」に対し
て、文字パターンは（あ，あ）（あ，い）（い，あ）で
あり、各文字パターンの出現度数パターンは（１，２）
（２，１）（１，３）となる。次に、文字パターンごと
に出現度数パターンを集めて、図５に示す各テキストご
との出現度数リスト（インデックスファイル）を作成す
る。

【００２８】一方、キーワードの文字列が「あいあ」で
ある場合に、この文字列の文字パターンは（あ，い）
（い，あ）である。キーワードとテキストとの照合に際
しては、まず、テキストの出現度数リストから、キーワ
ードの文字パターンに対応する出現度数パターンを得
る。図５の出現度数リストから得た（あ，い）の出現度
数パターンは（２，１）（４，２）（８，３）であり、
（い，あ）の出現度数パターンは（１，３）（２，５）
である。この（あ，い）の出現度数パターンの第２要素
と、（い，あ）の出現度数パターンの第１要素とが一致
するとき、テキストはキーワードの文字列「あいあ」を
含むことになる。この例の場合、（２，１）の第２要素
（１）と（１，３）の第１要素（１）とが一致し、ま
た、（４，２）の第２要素（２）と（２，５）の第１要
素（２）とが一致するから、このテキストは「あいあ」
というキーワードを含んでいる。

【００２９】実施例の情報検索装置は、基本的にこうし
た方式でキーワードを含むテキストを検索する。この装
置は、図１に示すように、検索対象のテキストデータを
収めたテキストデータベース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は、出現度数パターンの数が既にある出
現度数パターンリストを超えた場合に出現度数パターン
用の拡張領域を追加する。

【００５４】このテキスト変更に伴うインデックスファ
イルデータの更新の動作を図１１の処理フローを用いて
説明する。ここではテキストレコードの「ああいああい
あんんああんあい」を「ああいあいいあんああいんあ
い」に変更する場合を例に説明をする。

【００５５】ステップ１：先ず、修正テキスト読取部31
2は、変更後のテキストレコードを読み取り、レコード
番号をセットする。

【００５６】ステップ２：連続文字情報抽出部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は、全て
の出現度数パターンリストの最後尾にリスト最後の出現
度数パターンと同じ出現度数パターンを追加し、また、
削除後テキストレコードにおいて出現しなかった文字パ
ターンについては出現度数パターンリストの先頭に拡張
領域を追加する。

【００７２】図１８に削除した後のインデックスファイ
ルを示している。ここで、有効な出現度数パターンは太
線で囲った部分であり、その他は検索に使用されない無
効部分となる。

【００７３】削除されたインデックスファイルの検索の
処理手順は図７と同様である。なお、インデックスファ
イルの検索は出現度数パターンの要素が昇順を保ってい
る範囲でのみ実行されるので、図１８に示すインデック
スファイルの無効部分での検索は行なわれない。

【００７４】このように第３実施例の情報検索装置で
は、インデックスファイルを削除する時に、不要なイン
デックスファイルを全て削除するのでは無く、インデッ
クスファイルの最小限度の範囲を更新するだけで済ませ
ている。従って、削除の手間が削減され、削除を高速で
行なうことができる。

【００７５】

【発明の効果】以上の実施例の説明から明らかなよう
に、本発明の情報検索装置は、データベースから、指定
されたキーワードを高速に検索することができ、また、
データベースへのデータの追加、更新、削除の処理を高
速で行なうことができる。

【００７６】このデータベースへのデータの追加、更
新、削除の際には、既存のインデックスファイルに拡張
領域を設けたり、最後の出現度数パターンを再録するこ
とにより、インデックスファイルの修正を最小限に保ち
ながら、データの整理（ごみ削除）を行なうことができ
る。

【図面の簡単な説明】

【図１】本発明の実施例における情報検索装置の構成を
示すブロック図、

【図２】第１実施例におけるインデックスファイル生成
の処理フロー、

【図３】第１実施例におけるテキストレコードに対する
文字パターン度数表、

【図４】第１実施例における出現度数リストの説明図、

【図５】第１実施例における文字パターンと出現度数パ
ターン、

【図６】第１実施例におけるインデックスファイル、

【図７】第１実施例におけるインデックスファイル検索
の処理フロー、

【図８】第１実施例における検索時の文字パターンと出
現度数パターンリスト、

【図９】第１実施例における連続性照合の説明図、

【図１０】第１実施例における検索照合順の説明図、

【図１１】第２実施例におけるインデックスファイル更
新の処理フロー、

【図１２】第２実施例における更新テキストレコードに
対する文字パターン出現度数表、

【図１３】第２実施例における文字パターンと出現度数
パターン、

【図１４】第２実施例におけるインデックスファイル、

【図１５】第３実施例におけるインデックスファイル削
除の処理フロー、

【図１６】第３実施例における削除テキストレコードに
対する文字パターン出現度数表、

【図１７】第３実施例における文字パターンと出現度数
パターン、

【図１８】第３実施例におけるインデックスファイル、

【図１９】従来の情報検索装置の処理の流れを示す図、

【図２０】従来の情報検索装置のデータテーブルであ
る。

【符号の説明】

31 テキストデータベース 32 テキスト生成部 33 連続文字情報抽出部 34 インデックスファイル記憶部 35 インデックス生成部 36 拡張領域生成部 37 更新データ生成部 38 キーワード読取部 39 インデックス検索部 310 文字度数存在検索部 311 検索結果出力部 312 修正テキスト読取部

───────────────────────────────────────────────────── フロントページの続き (72)発明者菊池忠一大阪府門真市大字門真1006番地松下電器産業株式会社内

Claims

【特許請求の範囲】

【請求項１】キーワードを含むデータを検索する情報
検索装置において、検索対象データを構成する文字の出現度数を計算する文
字情報抽出手段と、検索対象データの隣接する文字の組と、前記文字の各出
現度数を組合せた出現度数パターンとを対応させて検索
ファイルを作成する検索ファイル生成手段と、前記検索ファイルから、キーワードにおける隣接する文
字の組に対応する出現度数パターンを検索し、得られた
出現度数パターンを照合してキーワードを含む検索対象
データを検索する検索手段とを設けたことを特徴とする
情報検索装置。
【請求項２】前記検索ファイル生成手段が、前記出現
度数パターンを前記検索ファイル上に昇順または降順に
配列し、前記検索手段が、前記検索ファイル上で昇順ま
たは降順を満たす範囲にある前記出現度数パターンを前
記照合に使用することを特徴とする請求項１に記載の情
報検索装置。
【請求項３】前記検索ファイル生成手段が、前記検索
ファイルの作成に当たって、前記出現度数パターンの配
列の終端に、その前に在る出現度数パターンと同じ出現
度数パターンを付け加え、前記検索手段が、付け加えら
れた前記出現度数パターンに前記照合の順番が達したと
き、前記照合を止めることを特徴とする請求項２に記載
の情報検索装置。
【請求項４】前記検索ファイルにおける出現度数パタ
ーンの配列の終端に空白の拡張領域を付け加えるととも
に、検索対象データの変更に伴って出現度数パターンの
追加が必要になったときに、前記拡張領域に前記出現度
数パターンを追加する検索ファイル修正手段を設けたこ
とを特徴とする請求項１乃至３に記載の情報検索装置。
【請求項５】前記検索ファイルに記述された出現度数
パターンの内から、キーワードの検索に使用する有効出
現度数パターンの範囲を特定するために、有効出現度数
パターンの配列の終端にその前に在る出現度数パターン
と同じ出現度数パターンを書き加え、有効でない出現度
数パターンだけの配列の前に空白の拡張領域を付け加え
る検索ファイル修正手段を設けたことを特徴とする請求
項１乃至３に記載の情報検索装置。