JPH04340165A - マルチキーワード情報検索処理方式および検索ファイル作成装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、情報検索を行う情報検
索処理方式に関する。本発明は、特にマルチキーワード
を用いた部分一致検索を行うことに適し、入力されたマ
ルチ検索入力文字列と登録キーワードとの文字列照合回
数を大幅に削減して、マルチ検索入力文字列に対する部
分一致（中間一致、前方一致、後方一致）や完全一致の
各検索処理を、高速に行うことができる情報検索処理方
式に関する。本発明は、データベースシステムにおいて
マルチキーワード部分一致検索処理を行う情報検索処理
方式に適する。

【０００２】

【従来の技術】従来から、検索対象であるレコードが有
するキーワードの最初から最後まで、検索入力文字列と
の文字列照合を行い、検索者が指定する入力文字列と検
索条件に合致するキーワードからレコード番号をサーチ
する逐次検索方式や、キーワードから検索入力可能な文
字列を作成して索引形式に検索ファイルを格納し、検索
者が指定する入力文字列と検索条件に合致するキーワー
ドを検索ファイルのインデックス構造を利用してサーチ
するインデックス方式がマルチキーワードを用いた部分
一致検索技術として一般的である。

【０００３】

【発明が解決しようとする課題】しかし逐次検索方式で
は、検索対象レコードの有するキーワードの最初から最
後まで、検索入力文字列との照合を行うため、多量のキ
ーワードを有する場合、その検索に多くの時間を要する
。このため、大規模データベースの検索では、高速な文
字列照合を行う専用のプロセッサやＬＳＩが提案されて
いるが、これらの方式では、ハードウエアが限定される
ほか、検索処理を行う計算機と専用プロセッサやＬＳＩ
との間での文字列転送に時間がかかり、システムとして
満足できる高速性の実現が課題となっている。

【０００４】また、インデックス方式は、部分一致検索
の高速化が可能であるが、検索ファイルが巨大になると
いう欠点がある。このため完全一致、前方一致、後方一
致の検索が使用されているが、中間一致はサポートされ
ていないことが多い。これは、中間一致を行うために、
完全一致、前方一致、後方一致の検索インデックスとは
別に、中間一致用のインデックスが多量に必要になり、
検索ファイルの記憶容量が巨大となること、これに伴い
検索時間が増大すること、および検索ファイルの保守が
容易でないことが主な理由となっている。また、システ
ムによっては検索ファイルの規模の制約から、キーワー
ドの全ての前方一致や後方一致検索がサポートされない
こともある。しかし、検索者はキーワードの中の特徴あ
る文字や文字列を記憶することが多く、このため中間一
致を含む部分一致検索のサポートにより検索がスムーズ
に行なえるようになることが求められている。

【０００５】本発明者は、日本語の場合には、キーワー
ドになりうる単語に同じ文字や同じ文字列が出現する頻
度が低い特徴がある点に着目し、キーワード構成文字を
先頭文字から１文字ずつ、その文字と次に続く合計ｒ文
字で文字セットを作成し、これらを文字セット種ごとに
格納して検索ファイルを作成し、検索時には、検索入力
された任意の文字列の構成文字を先頭文字からｒ文字単
位の文字セットに分解し、分解した文字セットと同じ文
字セットを検索ファイルから取り出し、文字セットの連
続性を照合することにより検索を高速化することができ
ることを見出した。

【０００６】本発明は、上述の観点から巨大なデータベ
ースシステムを対象とするマルチキーワードを用いた部
分一致検索の高速化を実現することができ、しかも特定
のハードウエアに限定されず、検索処理を主記憶上で行
うことにより専用プロセッサやＬＳＩとの文字列の転送
が不要であり、文字セットと文字セット位置に着目する
ことにより任意の文字列検索が可能である汎用性に富む
情報検索処理方式を提供することを目的とする。

【０００７】

【課題を解決するための手段】本発明の第一の特徴は、
検索対象となるレコードごとに昇順の符号を付与するレ
コード識別符号付与手段と、このレコードが有する各キ
ーワードにキーワードの論理的な区分を示す属性符号を
付与するキーワード属性符号付与手段と、このキーワー
ドから１文字ずつ取り出し、その文字と次に続く合計ｒ
文字で文字セットを作成し、キーワードにおける文字セ
ットの先頭文字位置を示す文字セット位置順序符号を付
与する文字セット位置順序符号付与手段と、上記レコー
ド識別手段とキーワード属性符号と文字セット位置順序
符号とからなる文字セット位置情報を作成して、この文
字セット位置情報を文字セット種ごとの領域に格納して
検索ファイルを作成する手段とを備えたことを特徴とす
る。

【０００８】なお、文字セット位置情報は、レコードが
有する各キーワードをキーワード属性符号に対応するキ
ーワード属性領域に配列して作成するキーワード列につ
いて、各キーワードの全ての文字セットを、レコード識
別符号とキーワード属性符号と文字セット位置順序符号
とで整数からなるコードに変換して作成するもので、レ
コード識別符号×ｎ＋（Ｐａ　−１）＋文字位置順序符
号 ｎ：キーワード列文字数 Ｐａ　：キーワード属性符号ａのキーワード属性領域の
キーワード列における先頭文字位置 なる数字として与えられることが好ましい。

【０００９】また本発明の第二の特徴は、第一の特徴で
作成された検索ファイルを備え、検索入力文字列の構成
文字を先頭文字からｒ文字単位の文字セットに分解して
検索入力文字セット列を作成し、この文字セットと同じ
文字セットの文字セット位置情報を上記検索ファイルか
ら取り出す手段と、この取り出した各文字セットの文字
セット位置情報間で、レコード識別符号とキーワード属
性符号が共通で文字セット位置順序符号の差が検索入力
文字列の該当する文字セットの先頭文字位置差に等しく
、かつそのキーワード属性符号が検索入力と等しい文字
セット位置情報の組み合わせを抽出する手段と、この抽
出された文字セット位置情報の組み合わせに基づいて検
索入力文字列に対応するレコード識別符号を検索結果と
して出力する手段とを備えたことを特徴とする。

【００１０】なお、検索入力文字列を先頭文字からｒ文
字単位の文字セットに分解したとき、最後の文字セット
が（ｒ−１）以下になり、ｒ文字単位の文字セットを作
成できないことがある。このときには、最後の文字セッ
トの直前の文字セットの後部から不足文字数分の文字を
取り出し、最後の文字セットの前部に連結してｒ文字単
位の文字セットを作成することが好ましい。

【００１１】また、検索入力文字セット列と同じ文字セ
ット列を構成できる文字セット位置情報の組み合わせの
抽出は、検索入力の全キーワードにおける出現頻度の低
い文字セットから順に行うことが好ましい。

【００１２】また、検索入力文字セット列と同じ文字セ
ット列を構成できる文字セット位置情報の組み合わせの
抽出は、検索入力文字セット列の全キーワードにおける
出現頻度の低い文字セットの文字セット位置順序符号を
ｉ、出現頻度の高い文字セットの文字セット位置順序符
号をｊとするとき、（文字セット位置順序符号ｉの文字
セットの文字セット位置情報）−（文字セット位置順序
符号ｊの文字セットの文字セット位置情報）＝ｉ−ｊの
式により行うことが好ましい。

【００１３】なお、キーワードが記号を含む欧文文字列
の場合は、少なくとも３文字記号単位の文字セットとし
、記号を含む欧文字のみの文字セット種グループの検索
ファイルを用いることがよい。

【００１４】また、キーワードが漢字を含む場合は、漢
字については１文字単位の文字位置情報とし、仮名文字
については少なくとも２文字単位の文字セット位置情報
とする検索ファイルを用いることができる。

【００１５】

【作用】文書中に同じ文字列が出現する頻度は低い。例
えば広辞苑の見出し語の説明文書は約９００　万字ある
が、その中で仮名文字の出現頻度を調べると平均約５３
２００　回と高い。しかし、仮名２文字の文字列の出現
頻度を調べると平均出現頻度４７２　回と低くなる。こ
のため仮名２　文字を文字セットとすると、検索入力が
ｎ文字の場合、抽出する照合対象は平均すれば（ｎ／２
）×４７２　個の文字セット位置情報となる。漢字は文
字種が仮名文字より多いので、漢字２文字の文字列の出
現頻度は仮名文字より低くなり、抽出する照合対象も仮
名文字より少なくなる。一般的に検索入力は数十文字以
下であるため、出現頻度の高い文字を含む文字列であっ
ても、全部の文字を逐次照合するものに比べるとその照
合回数は極めて少なくなる。

【００１６】例えば、「通信」という２つの文字列を使
用する用語は多々あるとしても「通信・・」という文字
列は「通信回線」、「通信装置」のように４文字で同一
の文字が発生する頻度は非常に低くなる。この結果、「
通信」に続く「回線」や「装置」の文字列を照合すると
、検索対象が急激に絞り込まれていく。このようにして
、検索入力文字セット列の構成文字セットで検索ファイ
ルとの照合を進めていくと、それまでに得られた検索対
象候補のキーワードの中から、検索入力文字セット列と
異なるキーワードが削除され、照合する構成文字セット
ごとに検索対象が絞り込まれていく。特に、検索入力の
中の全キーワードにおける出現頻度の低い文字セットか
ら順に照合を行うと一層絞り込まれて照合一致を取る回
数を低減できる。

【００１７】したがって、検索対象となるレコードが有
するキーワードを構成する各文字セットに対応して、レ
コードを特定できるレコード識別符号と、キーワードの
属性を特定できるキーワード属性符号と、キーワード中
の文字セット位置を特定できる文字セット位置順序符号
とから文字セット位置情報を作成し、この文字セット位
置情報を文字セット種ごとに格納して検索ファイルを作
成し、この検索ファイルに対して検索入力文字列との照
合一致を行うことにより文字列検索における照合一致処
理回数を大幅に低減することができる。

【００１８】この検索ファイルの作成は次のように行う
。

【００１９】まず検索対象となる各レコードに登録順序
に従って昇順にレコード識別符号を付与する。次に、各
レコードが有するキーワードの論理的な種別を属性とし
て、その属性を示すキーワード属性符号を付与する。例
えば図書検索システムの場合、図書名、著者名、発行者
名、刊行年、抄録などの属性を示すキーワード属性符号
が付与される。さらに、キーワードの先頭文字から１文
字ずつ取り出し、その文字と次に続く合計ｒ文字で文字
セットを作成し、各文字セットにキーワード中での文字
セットの先頭文字位置を示す文字セット位置順序符号を
付与する。これらのレコード識別符号とキーワード属性
符号と文字セット位置順序符号とから、キーワードの各
文字セットの文字セット位置情報を生成する。このとき
キーワード属性を文字位置で表せるように、キーワード
属性符号ごとにあらかじめ設定されたキーワードの先頭
文字位置が定数として文字セット位置情報に加算される
ようにしている。この文字セット位置情報を文字セット
種ごとにグループ化し、これらの各グループを集合して
検索ファイルを作成する。したがってこの検索ファイル
は、文字セット種ごとに文字セット位置情報が格納され
た形のファイル構造となる。

【００２０】検索処理では、検索入力文字列と検索入力
文字列属性とが対で１個以上入力される。各検索入力文
字列について検索入力文字列を先頭文字からｒ文字単位
の文字セットに分解し、検索ファイル中から分解した文
字セットと同じ文字セットの文字セット位置情報を取り
出して、レコード識別符号が共通で文字セット位置順序
符号の差が該当する検索入力文字列の文字セットの先頭
文字位置差に等しく、かつそのキーワード属性符号が検
索入力と等しい文字位セット置情報の組み合わせを照合
して取り出す。取り出した各検索入力に対応する文字セ
ット位置情報の組み合わせから検索入力文字列に対応す
るレコード識別符号を検索結果として取り出す。

【００２１】なお、検索入力文字列を先頭文字からｒ文
字単位の文字セットに分解したとき、最後の文字セット
が（ｒ−１）以下になり、ｒ文字単位の文字セットを作
成できないことがある。このときには、最後の文字セッ
トの直前の文字セットの後部から不足文字数分の文字を
取り出し、最後の文字セットの前部に連結してｒ文字単
位の文字セットを作成する。

【００２２】この照合処理は、検索入力と検索ファイル
との文字セット列の連続性の一致と属性の一致とをみる
もので、検索ファイル中の文字セット位置情報からレコ
ードの識別符号が共通していて文字セット位置順序符号
の差が該当する検索入力文字列の文字セットの先頭文字
位置差に等しくかつキーワード属性符号が同じキーワー
ドを取り出すことにより行う。

【００２３】これにより、検索ファイル中の全キーワー
ドとの照合が不要になり、検索ファイルにある検索入力
と同じ文字セットの文字セット位置情報だけの照合一致
を行えばよいので、照合回数は逐次照合に比べるときわ
めて低減することができる。また、日本語の単語では、
同じ文字列の出現頻度が低いので、ｒ文字単位の文字セ
ットを照合するたびに、検索対象が絞り込まれるので、
照合回数は低減していく。

【００２４】さらに、検索ファイルから取り出した文字
セット位置情報を照合するとき、検索入力の中の全キー
ワードにおける出現頻度の低い文字セットから順に行う
と検索対象が一層絞り込まれ、照合一致をとる回数がさ
らに低減できる。

【００２５】このようにして検索入力に合致する文字セ
ット位置情報を見出したときは検索入力に対応するレコ
ード識別符号に該当するレコードを抽出して、検索者に
検索結果として出力する。

【００２６】

【実施例】以下図面を参照して本発明の実施例を説明す
る。

【００２７】図１は本発明一実施例における情報検索処
理装置の構成を示すものである。

【００２８】本実施例の情報検索処理装置は、各種演算
処理あるいは判断処理を行うＣＰＵ１と、検索処理、検
索ファイル作成等のプログラム、作成されたあるいは検
索処理を行うための検索ファイル、検索入力等を記憶す
るメモリ２、キーボード４、ディスプレイ５を接続する
入出力部３、各種情報が記憶される外部記憶装置７を接
続する外部記憶装置制御部６、ＣＰＵ１、メモリ２、入
出力部３、外部記憶装置制御部６を接続する共通バス８
とを備える。

【００２９】本実施例での情報検索処理は、検索処理に
供するための検索対象となるレコードが有するマルチキ
ーワードから作成するキーワード列について各キーワー
ドの構成文字をキーワード列の先頭文字から１文字ずつ
取り出し、その文字と次に続く文字の合計２文字で文字
セットを作成し、これらの文字セット種を文字セット種
ごとに格納して検索ファイルを作成する検索ファイル作
成処理と、検索ファイルとの照合一致を行って検索入力
に合致するキーワードのレコードを抽出する検索処理と
の二つに分けられる。

【００３０】まず、検索ファイル作成処理について説明
する。

【００３１】この検索ファイル作成処理は、大まかに分
けると、■検索ファイル領域確保、■各キーワード構成
文字セットへの文字セット位置情報の付与、■文字セッ
ト種別ごとにグループ化した文字セット位置情報のファ
イルへの格納の３つに分けることができる。この各処理
についてそれぞれ説明する。

【００３２】■　　検索ファイル領域確保検索ファイル
は、図２に示すように、ＪＩＳコード表に記載されてい
る文字順に配列された文字セット群で構成される。各文
字セット群は図３に示すように、ＪＩＳコード表に記載
されている文字順に、記載文字を先頭文字とする２文字
の文字列で構成される文字セットグループで構成される
。そこで登録するレコードの有するキーワードの先頭文
字から１文字ずつ取り出し、その文字と次に続く合計２
文字で文字セットを作成し、これらの文字セット種ごと
に出現頻度を計数する。これにより、検索ファイルを構
成する各文字セット種グループに登録される文字セット
位置情報の数がわかるので、全文字セット種グループで
構成される検索ファイルの領域を確保できる。また同時
に、各文字セット種グループに登録される文字セット位
置情報の数から、検索ファイル内に連続して格納される
文字セット種グループの先頭番地もわかる。この文字セ
ット種グループの先頭番地を図３の文字セット群一覧の
記載順に配列したのが図４に示す文字セットグループア
ドレス表である。

【００３３】■　　各キーワード構成文字セットへの文
字セット位置情報の付与 ここで述べる文字セット位置情報は、レコードが有する
各キーワードをキーワード属性番号に対応するキーワー
ド属性領域に配列して作成するキーワード列において、
各キーワードを構成するすべての文字セットが属するレ
コードの登録する順番を示すレコード番号と、キーワー
ドにおけるその文字セットの出現する位置をその文字セ
ットの先頭文字の位置で示す文字セット位置番号と、キ
ーワードの論理的な種別を示すキーワード属性番号とで
作成される。

【００３４】まずレコード番号を説明する。例えば、一
般的な図書検索システムでは、図書名、著者名、発行者
名、刊行年、抄録のキーワードで図書を検索する。この
ときレコードは、図書名、著者名、発行者名、刊行年、
抄録のキーワードで構成される検索対象であって、この
レコードが登録される順序に１から昇順に番号を付与し
てレコード番号とする。

【００３５】次にキーワード属性番号を説明する。一般
的に検索者は、検索する図書を特定しやすいキーワード
を検索入力としたり、あるいは記憶しているキーワード
を検索入力する。このため図書検索システムでは、例え
ば図書名、著者名、発行者名、刊行年、抄録の各キーワ
ードにキーワード属性を付加し、検索入力と図書検索シ
ステムのキーワード間に論理的な関連付けを行っている
。ここではキーワード属性番号として、図書名に「１」
、著者名に「２」、発行者名に「３」、刊行年に「４」
、抄録に「５」を付与する。

【００３６】次に文字セット位置番号を説明する。キー
ワードごとに、キーワードの先頭から１文字ずつ取り出
し、その文字と次に続く文字の合計２文字で文字セット
を作成し、作成順に１、２、３・・・と昇順に番号を付
与して文字セット位置番号とする。キーワードの最後の
文字にはキーワードの最後を示す特殊記号ＥＭ（エンド
マーク）を付加し、このＥＭ記号と連結させて文字セッ
トとし、文字セット位置番号を付与する。なおＥＭ記号
にはＪＩＳコード表の未使用コードを割り当てる。ここ
では数字９の直後にあるＪＩＳコードＡ３ＢＡを割り当
てる。

【００３７】次にキーワード列を説明する。レコードの
有するキーワードに対する部分一致検索を検索入力文字
セット列との文字セット列照合により実現するために、
レコードの有するすべてのキーワードを連結して文字列
を構成し、これをキーワード列とする。すなわち、各キ
ーワードをキーワード属性番号に対応する固定長のキー
ワード属性領域に配列しキーワード列を作成する。これ
によりキーワード列における文字位置から、その文字セ
ットが属するキーワードの属性がわかる。なお、各キー
ワード属性領域に続いてキーワード属性領域の区切りを
示すＥＮＤ記号がキーワード列に配列される。このＥＮ
Ｄ記号はＪＩＳコード表の未使用コードを割り当てる。 ここではＥＭ記号の直後にあるＪＩＳコードＡ３ＢＢを
割り当てる。

【００３８】そしてこのキーワード列を対象として、レ
コード番号とキーワード属性番号と文字セット位置番号
からキーワードを構成するすべての文字セットを整数か
らなるコードに変換して文字セット位置情報を作成する
。この文字セット位置情報は、次の式（１）で与えられ
る整数のコードである。 文字セット位置情報コード＝レコード番号×ｎ＋（Ｐａ
　−１）＋ｐ…（１） ｎ：キーワード列文字数 Ｐａ　：キーワード属性番号ａのキーワード属性領域の
キーワード列における先頭文字位置 ｐ：文字セット位置番号

【００３９】例えば、キーワード列のキーワード属性領
域サイズが、図書名＝６４バイト３２文字、著者名＝３
２バイト１６文字、発行者＝６４バイト３２文字、刊行
年＝８バイト４文字、抄録＝４００　バイト２００　文
字の図書検索システムにおいて、レコード番号が１００
　のレコードが、「図書名＝通信文書の構造」、「著者
名＝田中一郎」、「発行者＝太平洋出版」、「刊行年＝
１９９０」、「抄録＝初めての人にも〜ている」の場合
、キーワード列は図５に示すようになる。このときキー
ワード列は５７８　バイト（２８９　文字）であるから
各文字セットの文字セット位置情報は図６に示すように
構成される。

【００４０】そして、このように文字セット位置情報を
それぞれ４バイトのコードで構成すれば、２８９　文字
数のキーワード列を２３２÷２８９　≒１４８６万個取
り扱うことが可能である。

【００４１】■　　文字位置情報の検索ファイルへの登
録次にこの各文字セットごとに付与された文字セット位
置情報を検索ファイルに登録する。上述のように文字セ
ット種グループは、ＪＩＳコード表に記載された順に検
索ファイルに格納される。そして各文字セットの文字セ
ット位置情報を各文字セット種グループに登録する。こ
の文字セット位置情報の登録は、文字セット種グループ
の未格納領域の先頭にそれぞれ文字セット位置情報を格
納することによって行われる。このため、登録順にレコ
ード番号を付与すれば文字セット種グループ内には文字
セット位置情報が数値順の昇順に登録されることになる
。

【００４２】上述の図書名「通信文書の構造」の文字セ
ット位置情報を検索ファイルに登録した例を図７に示す
。このとき、各グループ内の文字セット位置情報は昇順
に格納される。このファイル容量は、文字セット位置情
報が４バイトであると、

【数１】 になる。

【００４３】なお、文字セット位置情報の追加登録は、
追加レコードが有する各キーワードの各文字セットに該
当するグループの未格納領域の先頭に新規コードを追加
することで行う。また、削除は削除レコードが有する各
キーワードの各文字セットに該当するグループ内の該当
文字セット位置情報を特殊記号に変更することによって
行う。これにより追加登録と削除を短時間に行うことが
できる。

【００４４】なお上述のようにこの検索ファイルの各文
字セット種グループごとに格納された文字セット位置情
報は、図４の文字セットグループアドレス表の各文字セ
ットグループ先頭番地をディレクトリとして取り出すこ
とができる。

【００４５】以上の検索ファイルの作成処理の流れを図
８ａ、図８ｂに示す。

【００４６】すなわち、文字セット種の出現度数を計数
して文字セット欄アドレス表を作成し（Ｓ１１、１２）
、検索ファイルの領域を確保する（Ｓ１３）。次にレコ
ード登録順位カウンタをｋ＝１に初期設定して、レコー
ド番号を「１」に、キーワード列文字数をｎ＝２８９　
に、キーワード属性領域の先頭文字位置を図書名用とし
てＰ１　＝１、著者名用としてＰ２　＝３４、発行者名
用としてＰ３　＝５１、刊行年用としてＰ４　＝８４、
抄録用としてＰ５　＝８９を設定する（Ｓ１４）。そし
て最初のレコードを取り出す（Ｓ１５）。ここまでが登
録の前処理である。ここからレコードごとの登録処理と
なり、まず、キーワード属性番号をａ＝１にセットし（
Ｓ１６）、レコードの中からキーワード属性番号ａのキ
ーワードを取り出す（Ｓ１７）。さらに、キーワードの
構成文字数をｍに、文字セット位置番号をｐ＝１に、キ
ーワード属性番号ａに該当するキーワード属性領域の先
頭文字位置をＰａ　に設定する（Ｓ１８）。次に、取り
出したキーワードの先頭文字から順に、文字セット位置
番号ｐに相当する文字セット位置情報を Ｄ＝ｋ×ｎ＋（Ｐａ　−１）＋ｐ　　…（２）の式（２
）を用いて作成する（Ｓ１９）。

【００４７】そして、文字セット位置番号ｐにある文字
セットの文字セット種グループが格納されている検索フ
ァイルの文字セット欄を示す文字セット欄ディレクトリ
（文字セット欄先頭番地）を文字セット欄アドレス表か
ら取り出して（Ｓ２０）、文字セット欄ディレクトリが
示す検索ファイルの文字セット欄の未格納行の先頭に文
字セット位置情報を格納する（Ｓ２１）。そして、ｐ＝
ｐ＋１、ｍ＝ｍ−１とし、キーワード内のすべての文字
セットを処理したところで、ａ＝ａ＋１でキーワード属
性番号を＋１して次のキーワード処理に移る（Ｓ２４、
Ｓ２５）。また、レコードが有するすべてのキーワード
を処理すると、ｋ＝ｋ＋１でレコード登録順位カウンタ
を＋１して次のレコードの処理に移る（Ｓ２６、Ｓ２７
、Ｓ２８）。全レコードの処理が終了すると登録処理が
終わる（Ｓ２６）。

【００４８】次にこのようにして作成された検索ファイ
ルを用いる検索処理について説明する。

【００４９】本実施例では、検索ファイルから取り出し
た文字セット位置情報を対象として、検索入力文字列と
同じ文字列を含むキーワードを文字列照合し、かつ検索
入力と同じ属性であることを確認後、すべての検索入力
文字列に共通するレコードを検索する例で説明する。

【００５０】まず、その検索処理は大まかに分けると以
下の構成からなっている。■検索入力文字列をその先頭
文字から２文字単位の文字セットに分解し、検索入力文
字セット列を作成する。■検索入力文字セット列の各文
字セットに該当する文字セットグループアドレス表内の
文字セットグループ先頭番地を算出する。■検索入力文
字セット列を出現頻度の少ない文字セットから順に並べ
変える。■並べ変えた文字セット列の先頭から順に該当
する文字セット種グループを検索ファイルから取り出し
てそこに格納されている文字セット位置情報から検索入
力文字セット列を構成できる文字セット位置情報の組み
合わせを取り出す。■抽出した文字セット位置情報から
検索入力と同じ属性を有する文字セット位置情報を取り
出し照合一致とする。■■〜■を検索入力数分繰り返し
た後、すべての検索入力文字列に共通するレコード番号
を検索結果として出力する。

【００５１】次に具体的にそれぞれの処理を説明する。

【００５２】■　　検索入力文字セット列の作成検索フ
ァイルに格納されている文字セットと照合可能なように
、検索入力文字列を先頭文字から２文字単位の文字セッ
トに分解し、検索入力文字セット列とする。なお、検索
入力文字列を先頭文字から２文字単位の文字セットに分
解したとき、最後に１文字が残り２文字単位の文字セッ
トを作成できないことがある。このときには、最後の１
文字の直前の文字セットから不足分の１文字を取り出し
、最後の１文字の前部に連結した２文字単位の文字セッ
トを作成する。

【００５３】■　　各検索入力文字セットに該当する文
字セットグループアドレス表内の文字セットグループ先
頭番地の算出 検索ファイルの作成時と同様に、各検索入力文字セット
の図３における文字セット記載順位を算出し、これを文
字セットグループアドレス表における各検索入力文字セ
ットのアドレスポインタとする。

【００５４】■　　出現頻度順の並べ変えそして、検索
ファイルの各文字セット種グループの先頭番地を示す文
字セットグループアドレス表の文字セットグループ先頭
番地を参照して、各検索入力文字セットの出現頻度を調
べ、検索入力文字セット列を全キーワードにおける出現
頻度の低いものから順に並べ変える。上述のように、文
字セットグループアドレス表内の先頭番地は、検索ファ
イルに格納されている各文字セット種グループの先頭番
地を示しており、次に続く文字セットグループ先頭番地
との差をとれば、各文字セット種グループに格納されて
いる文字セット位置情報の数から、全キーワードにおけ
る文字セット種別出現頻度がわかる。

【００５５】これは出現頻度の低い文字セットから照合
一致を行うことにより、検索ファイルに格納された各文
字セットの文字セット位置情報間の照合回数をきわめて
低減できるためである。すなわち文字セット位置情報を
照合して各文字セットの連続性を調べる場合に二つの文
字セット種グループ内の文字セット位置情報中のレコー
ド番号と文字セット位置番号とキーワード属性番号とを
照合するため、その二つの文字セット種グループ内に格
納されている文字セット位置情報の数が少なければそれ
だけ照合回数を少なくすることができる。したがって、
文字セット位置情報の照合を行うときに、出現頻度の低
い文字セットから照合を行うことが照合回数を低減させ
る。特に検索入力文字が多くなるほど出現頻度の低い文
字セットが含まれる割合が高まるため低減効果は大きい
。

【００５６】■　　文字列の照合 出現頻度の低い文字セットから文字セットグループアド
レス表を参照してそれぞれの文字セット種グループに格
納されている文字セット位置情報を取り出す。そして取
り出した文字セット位置情報をもとに、出現頻度の低い
文字セット種グループから順に、各文字セット種グルー
プ間でレコード番号が等しくかつ文字セット位置番号の
差が検索入力文字列の該当する文字セットの先頭文字位
置差に等しい文字セット位置情報の組み合わせを抽出す
る。

【００５７】この文字セット位置情報の照合は、検索入
力文字セット列の全キーワードにおける出現頻度の低い
文字セットの文字セット位置番号をｉ、出現頻度の高い
文字セットの文字セット位置番号をｊとするとき、次の
式（３）で （文字セット位置番号ｉの文字セットの文字セット位置
情報）−（文字セット位置番号ｊの文字セットの文字セ
ット位置情報）＝ｉ−ｊ　　　　…　　（３）となる文
字セット位置情報の組み合わせを抽出すればよい。

【００５８】この文字セット種グループ間での文字セッ
ト位置情報の照合処理では、出現頻度の低い文字セット
種グループの文字セット位置情報とそれより出現頻度の
高い文字セット種グループの文字セット位置情報との差
を取って文字の連続を照合する。

【００５９】検索入力文字列における任意の文字セット
をＡＢとＣＤとすると、該当する文字セット位置情報を
抽出するには、ＡＢとＣＤとの文字セット位置番号差が
Ｌであるとし、グループＡＢの文字セット位置情報をＡ
ｘ　、グループＣＤの文字セット位置情報をＣｙ　とし
たとき Ａｘ　＋Ｌ＞Ｃｙ　ならＣｙ　を削除 Ａｘ　＋Ｌ＜Ｃｙ　ならＣｘ　を削除 Ａｘ　＋Ｌ＝Ｃｙ　ならＡｘ　、Ｃｙ　を合致として共
に削除というように不連続な文字セット位置情報を照合
対象から削除していくことによりその照合回数を削減さ
せる。

【００６０】例えばグループＡＢの文字セット位置情報
が ５７１　、１１４０、１０２３０　、１１３６５　、１
１９２８　、１３０６９グループＣＤの文字セット位置
情報が ５６９　、１７０６、１０２３１　、１０２３５　、１
１３６２文字セット位置番号差Ｌ＝２ であった場合、この二つのグループ間の照合回数は全体
で７回だけですみ、グループ内の全ての文字セット位置
情報を照合する必要はない。

【００６１】■　　キーワード属性番号の照合文字列照
合から得られた文字セット位置情報の文字セット位置番
号についてキーワード属性を照合する。すなわち、文字
セット位置番号が１〜３２ならば文字セット位置情報の
キーワード属性は図書名であり、文字セット位置番号が
３４〜４９ならば文字セット位置情報のキーワード属性
は著者名であり、文字セット位置番号が５１〜８２なら
ば文字セット位置情報のキーワード属性は発行者名であ
り、文字セット位置番号が８４〜８７ならば文字セット
位置情報のキーワード属性は刊行年であり、文字セット
位置番号が８９〜２８８　ならば文字セット位置情報の
キーワード属性は抄録であることがわかる。そこで、文
字セット列照合で得られた文字セット位置情報の中から
検索入力時に指定された属性と同じ文字セット位置情報
だけを取り出す。

【００６２】■　　レコード番号の抽出検索入力の数だ
け■〜■を繰り返し、得られた各検索入力文字列に該当
する文字セット位置情報間で、すべての検索入力文字列
に共通するレコード番号を取り出す。なお、この実施例
では検索入力が１個以上の場合について説明した。また
、検索入力が複数の場合には、各検索入力間で論理積演
算を行う例として説明したが、論理積演算以外の論理演
算を伴う複数の検索入力の場合は、照合結果として残っ
たレコード番号を各検索入力に対応付けて指定された論
理演算を行って検索入力の論理を満足するレコード番号
を検索結果として出力する。

【００６３】なお、１検索入力を複数の文字列で指定す
る場合、例えば抄録のような文字数が多い項目を対象と
する場合よくあることであるが、最初の文字列のキーワ
ード属性照合終了後、２番目以降の文字列に対しては、
その文字列の最初の照合文字セットの文字セット種グル
ープから、それまで得られたレコード番号とキーワード
属性番号を有する文字セット位置情報を取り出し、得ら
れた文字セット位置情報を文字セット列照合の先頭文字
の文字セット種グループとして同じ文字列内の他の文字
セットについて照合処理を行う。

【００６４】以上の■〜■の動作を具体例を挙げて説明
する。

【００６５】検索対象として図書名が指定され、検索入
力文字列としては「通信文書の」が指定されたとする。 この場合図書名のキーワードの属性の属性番号は「１」
とする。

【００６６】検索入力が「通信文書の」であるから、検
索入力文字セットは「通信」と「文書」と「書の」にな
る。全キーワードにおける出現頻度が「通信」＜「文書
」＜「書の」の順であり、照合をこの順序に行うとする
と、まず検索ファイル中の「通信」の文字セットグルー
プ欄から取り出した文字セット位置情報と「文書」の文
字セットグループ欄から取り出した文字セット位置情報
との間で、検索入力「通信文書の」における「通」と「
文」との文字位置が各々「１」と「３」であるから、文
字セット位置差が「−２」になる文字セット位置情報を
抽出すると、図７の検索ファイルの「通信」内の文字セ
ット位置情報の「２８９０１　」と「文書」内の「２８
９０３　」とを連続性ある文字セット位置情報の組み合
わせとして抽出することができる。次に「通信」の中で
照合結果として残った文字セット位置情報と、検索ファ
イル中の「書の」の文字セットグループ欄から取り出し
た文字セット位置情報との間で、文字セット位置差が「
−３」になる文字セット位置情報を抽出すると、図７の
検索ファイルの「通信」内の文字セット位置情報の「２
８９０１　」と「書の」内の文字セット位置情報の「２
８９０４　」とを連続性ある文字セット位置情報の組み
合わせとして抽出することができる。さらに、キーワー
ド属性は「図書名」であるから、これまでの文字セット
列照合で残った文字セット位置情報の中から、文字セッ
ト位置番号が１〜３２の文字位置情報として、「２８９
０１　」と「２８９０３　」と「２８９０４　」とを抽
出できる。

【００６７】キーワード列の文字数が「２８９　」であ
るから、文字セット位置番号は、２８９０１÷２８９　
＝１００　余り１から、１であることがわかる。またこ
の文字列が属するレコード番号は１００　であることも
わかる。

【００６８】この検索処理動作を図９ａ、図９ｂにフロ
ーチャートとして示す。

【００６９】すなわち、キーワード列文字数をｎ＝２８
９　に、キーワード属性領域の文字位置範囲Ｐａ　を図
書名はＰ１　＝１　〜３２、著者名はＰ２　＝３４〜４
９、発行者名はＰ３＝５１〜８２、刊行年はＰ４　＝８
４〜８７、抄録はＰ５　＝８９〜２８８　に、キーワー
ド属性番号をａ＝１に設定し（Ｓ３１）、キーワード属
性番号ａの検索入力文字列がある場合にはそれを取り出
す（Ｓ３２、Ｓ３３）。ここからは検索入力文字列の照
合処理になる。そこで、検索入力を取り出し、検索入力
文字列の先頭から２文字単位の文字セットに分割して検
索入力文字セット列を作成し、その文字セット数−１を
照合回数ｑとし（Ｓ３４、Ｓ３５）、検索入力文字セッ
ト列を全キーワードにおける出現頻度の低いものから順
に並べ変える（Ｓ３６）。そして検索ファイルから、並
べ変えた各文字セットに該当する文字セット種グループ
に格納されている文字セット位置情報を取り出す（Ｓ３
７）。次に検索入力文字セット列の全キーワードにおけ
る出現頻度の低い文字セットの文字セット位置番号をｉ
、出現頻度の低い文字セットの文字セット位置番号をｊ
とするとき、二つの文字セット種グループ間で、（文字
セット位置番号ｉの文字セットの文字セット位置情報）
−（文字セット位置番号ｊの文字セットの文字セット位
置情報）＝ｉ−ｊである文字セット位置情報の組み合わ
せを取り出す（Ｓ３８）。同様の処理を検索入力文字セ
ット列の残りの文字セットについても行い（Ｓ３９、Ｓ
４０）、残った文字セット位置情報の中から文字セット
位置番号がキーワード属性番号ａの文字位置範囲Ｐａ　
内にあるレコード番号だけを取り出す。文字セット位置
情報から文字セット位置番号を取り出すには、次の式（
４）を用いる。 （文字セット位置情報）÷（キーワード列文字数）＝レ
コード番号余り文字セット位置番号…（４）ここまでの
処理で、検索入力文字列を文字列として持ち、さらに検
索入力された属性と同じキーワードを有するレコード番
号がわかる（Ｓ４１）。抄録まで同様の処理を行い、検
索入力された属性と同じキーワードを有するレコード番
号を取り出す（Ｓ４２、Ｓ４３）。すべての検索入力文
字列の照合が終わると、残ったレコード番号を対象とし
て、すべての検索入力文字列に共通するレコード番号を
検索結果として出力する（Ｓ４４）。

【００７０】上記実施例では日本語文書の検索処理の例
を説明したが、他の例として例えば英文字のように字種
の少ない言語の文書では、ＪＩＳコード表の中から、仮
名文字と漢字を除いた字種だけで検索ファイルと文字セ
ット群一覧と文字セットグループアドレス表を作成する
と、日本語文書に比べ文字セットの少ない検索ファイル
が構成でき、日本語文書に比較してコンパクトなマルチ
キーワード検索用検索ファイルが構成でき、またその検
索も容易にできる。この場合、英文字（記号を含む）に
ついてはＪＩＳコードに変えて、例えばＩＳＯコード、
ＡＳＣＩＩコードを用いた文字セットグループアドレス
表を作成し、文字セットは最低３文字で構成されたもの
とすることがよい。

【００７１】なお、マルチキーワード検索の高速性が求
められる場合、文字セットの構成文字数を増加するとま
すます文字セットの出現頻度が低くなり、各文字セット
種グループに格納される文字セット位置情報が少なくな
るため、容易に高速化を実現できる。

【００７２】また、日本語文書の場合に、連続する片仮
名文字または平仮名文字のみを文字セットとし、漢字に
ついては１文字単位とする検索ファイルを作成してもよ
い。漢字はその字種が多く、その出現頻度も低いため、
１文字単位の文字種グループとしても検索の高速化を図
ることができる。

【００７３】

【発明の効果】以上説明したように、本発明は検索対象
となるレコードが有するキーワードの構成文字の文字セ
ット種ごとにその文字セットが属するレコード識別符号
、文字セット位置順序符号、キーワードの種別を示すキ
ーワード属性番号からなる文字セット位置情報を格納し
た検索ファイルを作成し、この検索ファイルを検索入力
の文字列を構成する文字セット種ごとにその文字セット
位置情報を取り出して、検索入力を含む文字列を検索す
るようにした。

【００７４】このため、（１）　検索処理のための文字
列照合回数を低減することができるため、高速検索を行
うことができる、（２）　文字セットと文字位置に着目
して検索処理を行うため任意の文字列による検索ができ
、（３）　専用のハードウエアを用いることなくソフト
ウエアだけで高速検索を実現できるため、汎用の情報処
理装置でマルチキーワードを用いた部分一致検索を効率
よく行うことができ汎用性に富む、（４）　データベー
スシステムに利用したとき、その検索ファイルの作成に
使用可能な部分一致検索文字列の作成を行う必要がなく
、検索対象となるレコードが有するキーワードから自動
的に検索ファイルを作成することができるため、データ
ベースシステムを経済的にかつ効率よく構築することが
可能である、（５）　欧文字のように字種の少ない文字
からなる文字列も、同じ文字列の出現頻度は低いため各
文字セットの出現頻度は低くなり、その文字列を構成す
る文字セット種グループで文字セット位置情報を格納し
た検索ファイルを作成して検索することにより、高速検
索を可能にする優れた効果がある。

【図面の簡単な説明】

【図１】　　本発明一実施例に使用する情報検索処理装
置の構成例。

【図２】　　実施例の検索ファイル例表。

【図３】　　実施例の文字セット群一覧。

【図４】　　実施例の文字セットグループアドレス表。

【図５】　　実施例のキーワード例。

【図６】　　実施例の文字セット位置情報作成例。

【図７】　　実施例の検索ファイル例。

【図８ａ，ｂ】　　実施例の検索ファイル作成処理手順
を説明するフローチャート。

【図９ａ，ｂ】　　実施例の検索処理手順を説明するフ
ローチャート。

【符号の説明】

１…ＣＰＵ ２…メモリ ３…入出力部 ４…キーボード ５…ディスプレイ ６…外部記憶装置制御部 ７…外部記憶装置 ８…共通バス

Claims (7)

【特許請求の範囲】
1. 【請求項１】　　検索対象となるレコードごとに昇順の
   符号を付与するレコード識別符号付与手段と、このレコ
   ードが有する各キーワードにキーワードの論理的な区分
   を示す属性符号を付与するキーワード属性符号付与手段
   と、このキーワードを各文字ごとに分解してその文字と
   次に続く合計ｒ文字（但しｒは２以上の自然数）からな
   る文字セットを作成し、この文字セットにキーワード中
   での文字セットの先頭文字位置を示す文字セット位置順
   序符号を付与する文字セット位置順序符号付与手段と、
   上記レコード識別符号とキーワード属性符号と文字セッ
   ト位置順序符号とからなる文字セット位置情報を作成し
   て、この文字セット位置情報を文字セット種ごとの領域
   に格納して検索ファイルを作成する手段とを備えた情報
   検索処理方式。
2. 【請求項２】　　文字セット位置情報は、レコードを構
   成する各キーワードをキーワード属性符号に対応してキ
   ーワード属性領域に配列したキーワード列の各キーワー
   ドを構成するすべての文字セットについて、レコード識
   別符号×ｎ＋（Ｐａ　−１）＋文字セット位置順序符号 ｎ：キーワード列文字数 Ｐａ　：キーワード属性符号ａのキーワード属性領域の
   キーワード列における先頭文字位置 なる数字コードとして与えられる請求項１記載の情報検
   索処理方式。
3. 【請求項３】　　検索対象となるレコードのキーワード
   列について、各キーワードを構成する文字ごとに、レコ
   ードごとに昇順に付与されたレコード識別符号と、この
   レコードが有するキーワードの論理区分を示すキーワー
   ド属性符号とキーワード中でのその文字セットの先頭文
   字位置を示す文字セット位置順序符号とからなる文字セ
   ット位置情報を文字セット種別ごとに格納した検索ファ
   イルを備え、検索入力文字列の構成文字を先頭文字から
   ｒ文字単位の文字セットに分解した検索入力文字セット
   列を構成し、分解した文字セットと同じ文字セットの文
   字セット位置情報を上記検索ファイルから取り出す手段
   と、この取り出した各文字セットの文字セット位置情報
   間で、レコード識別符号とキーワード属性符号が共通で
   文字セット位置順序符号が検索入力文字列の該当する文
   字セットの先頭文字位置差に等しく、かつそのキーワー
   ド属性符号が検索入力と等しい文字セット位置情報の組
   み合わせを抽出する手段と、この抽出された文字セット
   位置情報の組み合わせに基づいて検索入力に対応するレ
   コード識別符号を検索結果として出力する手段とを備え
   た情報検索処理方式。
4. 【請求項４】　　検索入力文字セット列と同じ文字セッ
   ト列を構成できる文字セット位置情報の組み合わせの抽
   出は、検索入力文字セット列の全キーワードにおける出
   現頻度の低い文字セットから順に行う請求項３記載の情
   報検索処理方式。
5. 【請求項５】　　検索入力文字セット列と同じ文字セッ
   ト列を構成できる文字セット位置情報の組み合わせ抽出
   は、検索入力文字セット列の全キーワードにおける出現
   頻度の低い文字セットの文字セット位置順序符号をｉ、
   出現頻度の高い文字セットの文字セット位置順序符号を
   ｊとするとき、 （文字セット位置順序符号ｉの文字セットの文字セット
   位置情報）−（文字セット位置順序符号ｊの文字セット
   の文字セット位置情報）＝ｉ−ｊ に合致する文字位置情報の組み合わせを抽出する請求項
   ３または請求項４記載の情報検索処理方式。
6. 【請求項６】　　キーワードが記号を含む欧文字列の場
   合は、少なくとも３文字記号単位の文字セットで記号を
   含む欧文字の文字セット種のみの検索ファイルを用いる
   請求項１ないし請求項５のいずれか記載の情報検索処理
   方式。
7. 【請求項７】　　キーワードが漢字を含む場合は、仮名
   文字について少なくとも２文字単位の文字セット種で構
   成された検索ファイルを用いる請求項１ないし請求項５
   のいずれか記載の情報検索処理方式。