JPH0748218B2

JPH0748218B2 - 情報処理装置

Info

Publication number: JPH0748218B2
Application number: JP1178780A
Authority: JP
Inventors: 忠一菊池
Original assignee: 株式会社テレマティーク国際研究所
Priority date: 1989-07-10
Filing date: 1989-07-10
Publication date: 1995-05-24
Anticipated expiration: 2010-05-24
Also published as: JPH0342774A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、情報処理装置における国語辞典、人名辞典、
他名辞典等の辞典類の検索処理に利用する。本発明は、
情報処理装置におけるキーワードの部分一致、前方一
致、後方一致の各検索処理をそれぞれ行うためのもので
ある。

〔概要〕

本発明は、登録されたキーワードと検索入力との一致確
認により検索処理を行う情報処理装置において、登録キーワードを文字ごとに分解し、この文字ごとにキ
ーワードの登録番号とキーワードにおける文字位置順位
番号とからなる登録データを記憶しておき、検索入力を
文字ごとに分解し、分解された文字ごとに登録キーワー
ドの登録番号と文字位置順位番号とを取り出して登録キ
ーワードとの登録番号の一致と文字位置順位の連続性の
確認を行うことにより、検索におけるキーワードとの部分一致、前方一致、後方
一致のいずれの検索も行うことができるようにするもの
である。

〔従来の技術〕

検索入力に対するキーワードとの一致をとることによる
部分一致検索の技術として次のようなものが提案されて
いる。

例えば実開昭60-57849号公報では、入力レコードデータ
の入力転送速度に同期させて、レコード内の不特定場所
の部分一致検索を行う情報検索装置の技術が開示されて
いる。この技術は、入力レコードデータの中から検索の
目的とするキーワードの有無を確認するために、入力レ
コードデータの始めから終わりまで、複数バイトのキー
ワードと比較することにより、部分一致検索を行うもの
である。

また、特開昭60-72023号公報には、入力レコードデータ
に検索の目的とするキーワードの１バイト目を検出した
後、次の入力レコードデータをシフトするとともに、キ
ーワードの２バイト目と比較することにより部分一致を
行う技術が記載されている。

さらに、特開昭63-229523号公報には、先頭または末尾
の数文字以上が共通なキーワードの組を同群のキーワー
ドとして抽出しておくことによって、前方一致または後
方一致するキーワードを検索する技術が記載されてい
る。

また一般的には、インバーテッド・ファイルのインデッ
クス形式が多く使用され、前方一致あるいは後方一致に
よる検索が行われている。

〔発明が解決しようとする問題点〕

しかし、上述した入力レコードデータとキーワードとの
部分一致検索を行う技術は、入力レコードデータの中か
ら検索の目的とするキーワードの有無を確認するため
に、入力レコードデータの各々について、その始めから
終わりまで、該当するキーワードと比較しなければなら
ず、検索処理の高速化を妨げていた。

また、前方または後方一致するキーワードの組を同群の
キーワードとして抽出する技術は、部分一致用のキーワ
ード同群数が非常に多くなり、これらの記憶容量が巨大
になることと、検索時間が増大するため部分一致検索を
行うことができない問題があった。

また、上述のインバーテッド・ファイルのインデックス
形式は高速検索が可能であるが、インバーテッド・ファ
イルが巨大になるという欠点がある。このため、完全一
致、前方一致、後方一致の検索が使用されているが、部
分一致検索はサポートされていないことが多い。これは
部分一致検索を行うために、完全一致、前方一致、後方
一致の検索インデックスとは別に、部分一致用のインデ
ックスが多量に必要となり、インデックスの記憶容量が
巨大になることと、これに伴い検索時間が増大すること
が主な理由となっている。

本願発明は上述の問題を解決するもので、前方一致、後
方一致、部分一致のいずれの検索も行うことができる情
報処理装置を提供することを目的とする。

〔問題点を解決するための手段〕

本発明は、第一の特徴として検索用のキーワードを記憶
する領域を備えた記憶装置とCPUとを備え、検索用のキ
ーワードを登録しておき、この登録キーワードと検索入
力との照合を行うことにより検索を行う情報処理装置に
おいて、上記キーワードをその登録順に登録番号を付す
手段と、この手段により登録番号を付されたキーワード
を文字単位に分解するとともに、この分解された文字ご
とに先頭からの文字位置順位番号を付す手段と、文字ご
とにこの文字を規定するコードで指定される記憶領域に
上記登録番号と文字位置順位番号とからなる情報を記憶
する手段とを備えている。

また第二の特徴として、キーワードの登録番号とその文
字位置順位番号とからなる情報をその登録キーワードを
構成する文字ごとに文字コードで規定される記憶領域に
分類し変換表として記憶する記憶装置と、検索入力を文
字ごとに分解する手段と、この分解された文字ごとに、
その文字コードで規定されるディレクトリを参照して上
記変換表を検索する手段と、上記変換表から検索入力の
構成文字順に検索入力構成文字の文字コードに対応する
記憶領域の上記情報を取り出し、登録キーワードの登録
番号が一致し、さらに登録キーワードの文字位置順位番
号が検索入力の構成文字順に則って連続している登録番
号に対応する登録キーワードを検索結果として出力する
手段とを備えたことを特徴とする。

なお、検索入力構成文字の最終文字の文字コードに対応
する記憶領域から取り出した登録キーワードの文字位置
順位番号と検索入力の文字数とが一致する登録番号の登
録キーワードを取り出す手段を含むことができ、また、
検索入力構成文字の文字コードに対応する記憶領域から
取り出した登録キーワードの文字位置順位番号と登録キ
ーワードの文字数とが一致する登録番号の登録キーワー
ドを取り出す手段を含むことができる。

〔作用〕

記憶装置に登録されるキーワードは、その登録番号とキ
ーワードにおける文字位置順位を示す番号とからなる登
録データとし、文字ごとの群にわけてコード変換表とし
て記憶される。

検索時には、登録された一つのキーワードはそのキーワ
ードを構成する文字ごとのグループに同じ登録番号とし
て記憶されているので、検索入力を構成文字ごとに分解
し文字ごとに群に分けて作られているコード変換表を参
照して、登録番号が一致し文字位置順位番号が検索入力
の構成文字順に則って連続している登録キーワードを検
索結果として抽出する。また、登録キーワードの文字位
置順位番号もコード変換表に格納されているので、検索
入力の文字数と検索入力構成文字の最終文字に対応する
群から取り出した登録キーワードの文字位置順位番号と
の一致を照合することによる前方一致、登録キーワード
の文字数と検索入力構成文字の最終文字に対応する群か
ら取り出した登録キーワードの文字位置順位番号との一
致を照合することによる後方一致のいずれの検索も行う
ことができる。

〔実施例〕

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

第１図は本発明一実施例における情報処理装置の構成を
示すものである。

本実施例の情報処理装置は、各種演算処理あるいは判断
処理を行うCPU1と、検索処理、キーワード登録処理等の
プログラム、キーワード、文字ごとに登録されたキーワ
ードのコード変換表、検索入力等を記憶するメモリ２、
キーボード４、ディスプレイ５を接続する入出力部３、
各種情報が記憶される外部記憶装置７を接続する外部記
憶装置制御部６、CPU1、メモリ２、入出力部３、外部記
憶装置制御部６を接続する共通バス８とを備える。

本実施例での情報処理装置の処理は検索処理に供するた
めの登録キーワードを文字ごとに登録してテーブルであ
る文字欄アドレス表およびコード変換表を作成する登録
処理と、検索入力に対する検索処理との二つに分けられ
る。

まず、登録キーワードのテーブルを作成する登録処理に
ついて説明する。

本実施例のキーワードの登録番号および文字位置順位番
号とによる検索用の登録キーワードのテーブルの作成
は、文字についてはJIS第一水準およびJIS第二水準漢字
表の記載順位に基づいてそのコード変換を行い、登録キ
ーワードのテーブルのディレクトリとして利用する。

第２図は文字欄アドレス表であって、CPU1がプログラム
を実行するときに、外部記憶装置７からメモリ２にロー
ドされる。この文字欄アドレス表は、JIS第一水準およ
びJIS第二水準の漢字表に登録されているすべての文字
と空き領域に対応するように構成されて、全部で8836個
の文字欄ディレクトリを格納する行で構成されている。
これにより、キーワードを構成する文字の文字欄ディレ
クトリを文字欄アドレス表から参照することができる。

この文字欄アドレス表は、具体的はJIS第一水準表の
「縦欄A1−横欄A1」（16進表示）を開始点として、これ
に記載順位No.1とし、「縦欄CF−横欄FE」を記載順位N
o.4418とし、JIS第二水準表の「縦欄D0−横欄A1」を継
続点とし、「縦欄FE−横欄FE」を記載順位No.8836とし
て、登録するキーワードの構成文字にすべて記載順位値
を割り当ててコード変換を行う。

このキーワードの構成文字にJIS第一水準およびJIS第二
水準漢字表の記載順位値を与える具体的な例を述べる。
例えば登録するキーワードが「雪国の春」であった場
合、「雪」はJIS第一水準およびJIS第二水準漢字表で29
81番目の文字であり、「国」は2337番目の文字であり、
「春」は2685番目の文字である。このため、「雪」につ
いては、文字欄アドレス表の2981行、「国」について
は、2337行、「春」については、2685行の内容を参照す
れば、その文字のディレクトリが得られる。

第３図はこの文字欄アドレス表に対応して作成されるキ
ーワードのコード変換表である。

このコード変換表は、CPU1がプログラムを実行するとき
に、外部記憶装置７からメモリ２へロードされる。この
コード変換表は、JIS第一水準漢字表およびJIS第二水準
漢字表に登録されているすべての文字と空き領域の中で
登録キーワードで使用されているキーワードの登録文字
データを登録する。したがって、このコード変換表の文
字欄は登録キーワードの文字種の数に等しい文字欄を有
しており、各文字欄はキーワードの登録初期時に全キー
ワードの文字別使用度数から必要数が確保される。な
お、この第３図のコード変換表の行数は一応の例であ
り、その行数はキーワードの登録により増加するもので
ある。

この各文字欄に登録されるキーワードの文字データは、
１文字ごとに、第２図に示す文字欄アドレス表から得ら
れる文字欄ディレクトリをディレクトリとして、該当す
る文字の文字欄の最初の行から順に新規に登録する。こ
の登録キーワードの登録データは、登録するキーワード
の登録順位を示す登録番号と、登録するキーワードの構
成文字の先頭からの順位を示す文字位置順位番号とによ
って構成される。具体的には例えば、登録するキーワー
ドが第500番目であるときは、登録順位は500であり、そ
の文字位置順位が１であれば、登録データは50001とい
う数値となる。文字位置順位が２の文字は、50002の数
値となり、これらの数値は、コード変換表のそれぞれの
文字欄の空の先頭行に登録される。

次に具体的に「雪国の春」をキーワードとして登録する
際の動作を第４図にフローチャートを示し、また文字欄
アドレス表およびコード変換表の例を第５図および第６
図に挙げて説明する。

キーワードの登録動作が起動されると、まず、JIS第一
水準およびJIS第二水準漢字表に対応させて、登録する
全キーワードの構成文字の種類別に使用度数を調べ、文
字欄アドレス表の該当位置にコード変換表の行を示すデ
ィレクトリを格納する。例えば、JIS第一水準およびJIS
第二水準漢字表の記載順位No.378の文字が４回、記載順
位No.380の文字が２回使用されている場合には、文字欄
アドレス表の記載順位No.378文字欄ディレクトリに１
を、記載順位No.379とNo.380文字欄ディレクトリに１＋
４＝５から５を、記載順位No.381〜No.384文字欄ディレ
クトリに５＋２＝７から７を、それぞれ文字欄アドレス
表に格納する。また、登録する全キーワードの構成文字
の種類別使用度数に対応させて、コード変換表に使用度
数分の行を確保する。例えば、記載順位No.378文字欄と
して４行を、記載順位No.380文字欄として２行を確保す
る。

次に、キーワード登録順位を示すカウンタの数値をｋ＝
１にセットする。次に登録キーワードが入力されると、
登録キーワードの構成文字数をカウントしてそのカウン
ト数ｎをセットする。キーワードが「雪国の春」であれ
ば４文字であるからｎ＝４となる。登録キーワードの構
成文字の位置を示す文字位置順位ｐをｐ＝１にセットす
る。ここまでは初期処理となる。

そして登録キーワードをそれぞれの構成文字を一文字ご
とに分解し、その文字位置順位が１番目の文字をコード
変換して、登録データを作成する。このコード変換は、
キーワード登録順位をｋとするとき、Ｄ＝ｋ×100＋１を登録データＤとするものであり、この数値を文字コー
ド変換された登録キーワードの登録データのコード変換
表に格納する。これは登録キーワードの登録番号を100
位以上で表現し、登録キーワードにおける構成文字位置
を10以下の数値で表現している。このため、登録キーワ
ードの構成文字は99文字まで可能である。

例えばキーワード「雪国の春」が500番目に登録された
とすると、先頭文字の「雪」の登録データの数値は「50
001」となる。

これらの登録キーワードの登録データは、文字欄アドレ
ス表の文字欄ディレクトリを参照して、コード変換表の
対応する文字欄の空の先頭行に格納する。「雪」の場合
には、コード変換表のNo.2981の文字欄の空の先頭行に
登録データ「50001」を格納する。

次に登録キーワードの第２文字目の登録データをＤ＝ｋ
×100＋２により作成し、この「50002」を対応するコー
ド変換表の対応する「国」の文字欄の空の先頭行に格納
する。

そして、キーワードの構成文字の登録が終了すると、登
録番号ｋを＋１して、次のキーワードの登録を待つ。

このときの文字欄アドレス表のディレクトリとコード変
換表の例を第５図および第６図に示す。文字欄アドレス
表で、No.2981の「雪」の文字欄のディレクトリはコー
ド変換表の第3675行目を示し、No.2337の「国」の文字
欄のディレクトリはコード変換表の第2500行目を示して
おり、キーワード「雪国の春」の「国」の登録データ
「50002」は文字欄「国」の第１行目に登録され、
「雪」の登録データ「50001」は文字欄「雪」の第４行
目に登録されたことを示している。

登録キーワードを分解して対応するコード変換表の文字
欄に格納する動作についてさらに説明する。

まず、分解された登録キーワードの構成文字のそれぞれ
について、JIS第一水準およびJIS第二水準の漢字表にお
ける記載順位値をディレクトリとして、文字欄アドレス
表から該当する文字欄ディレクトリを取り出す。このと
き取り出した文字欄ディレクトリの格納行以降の内容を
＋１する。これは、登録キーワードの登録データをコー
ド変換表に格納すると、以降の文字欄の格納行がそれぞ
れ１ずつずれるからである。そしてこの取り出したディ
レクトリに示される文字欄の空の先頭行に登録キーワー
ドの登録データを格納する。

以上でキーワードがその登録番号とそのキーワードでの
文字位置順位の番号とからなる登録データとして、それ
ぞれの文字ごとにグループ化されて、キーワードのコー
ド変換表にテーブルとして格納される。

次にこのコード変換表を用いて検索処理を行う動作につ
いて第７図にフローチャートを示して説明する。ここで
は検索入力と登録キーワードとの部分一致を検出する部
分一致検索の例で説明する。

検索要求が発生して検索入力が入力されると、この入力
された検索入力を取り出し、登録キーワードとの部分一
致検索を行うために１文字ごとに分解して切り出す。ま
た検索入力における文字位置順位番号ｐを１として初期
化しておく。

そして、検索入力のｐ番目の文字についてそのJIS第一
水準およびJIS第二水準の漢字表における記載順位値を
求め、その記載順位値から文字アドレス表の対応する文
字のディレクトリを取り出す。そしてこの文字欄ディレ
クトリから登録キーワードについての登録データが格納
されたコード変換表の対応する文字欄の登録データをす
べて取り出す。

そして取り出した順に、１番目の文字欄と２番目の文字
欄にある登録データとの算術差が−１、すなわち１番目
の文字欄の登録データより数値が１多い登録データを２
番目の文字欄から抽出し、1/2番目文字欄結果とする。
さらに、検索入力文字数だけ、文字欄結果と登録データ
との算術差が−１の登録データを抽出し、抽出した登録
データの中で、登録番号の重複を削除して部分一致検索
結果である登録番号を検出する。

この部分一致検出動作をさらに説明する。

検索入力をC₁C₂・・C_i-1C_iとするとき、登録データの中か
ら、初めに１番目の文字であるC₁と２番目の文字である
C₂が連続している登録データを抽出する。すなわち、文
字C₁を構成文字として含む登録キーワードを特定できる
キーワード登録順位番号とその登録キーワードにおける
文字C₁の先頭文字からの順位を特定できる文字順位番号
とで構成されている登録データ群である文字欄を取り出
す。この文字欄には登録したキーワードに出現するすべ
ての文字C₁の登録データが含まれる。同様に、文字C₂を
構成文字として含む登録キーワードを特定できるキーワ
ード登録順位番号と、その登録キーワードにおける文字
C₁の先頭文字からの順位を特定できる文字位置順位番号
とで構成されている登録データ群である文字欄を取り出
す。

なお、登録データＤは、システム内のキーワード登録順
位番号をｋ、登録キーワード内の文字位置順位番号をｐ
とするとき、Ｄ＝ｋ×100＋ｐで表せるから、登録キー
ワード内の先頭文字からの文字位置順位が（ｊ−１）と
ｊである隣接する文字S_j-1S_jの登録データD_j-1D_jは、 D_j-1＝ｋ×100＋（ｊ−１）と、D_j＝ｋ×100＋ｊにな
る。

そこで、文字C₁に該当する文字欄にある登録データと、
文字C₂に該当する文字欄にある登録データが−１差であ
る２文字は、同一キーワードにある隣接文字であるか
ら、これら２個の文字欄の算術差が−１である文字C₂に
該当する文字欄内の登録データを抽出する。

次に、上記で抽出した文字C₂に該当する文字欄内の登録
データと、文字C₃に該当する登録データ群である文字欄
を取り出し、これら２個の文字欄の算術差が−１である
文字C₃に該当する文字欄内の登録データを抽出する。

以下文字C_iまで同様に処理し、２個の文字欄の算術差が
−１である文字C_iに該当する文字欄内の登録データを抽
出すると、検索入力C₁C₂・・C_i-1C_iと同じ文字列が含まれ
るキーワードに相当する登録データが得られる。

なお、文字欄にある登録データは、登録順に登録番号を
付加しコード変換表に格納しているので、各文字欄には
登録データの昇順に自動配列されており、上記の各文字
欄間の算術差−１検出処理ごとに、不要な登録データが
１個ずつ削除され、算術差−１の場合には登録データが
２個処理対象から削除され、高速な検索処理を実現して
いる。

以上の検索処理は、登録キーワードとの部分一致検索処
理であるが、上記の部分一致検索で、検索入力の最後の
文字C_iまで処理し、文字C_iに該当する文字欄内の登録デ
ータを検索結果として抽出する。一方、登録データＤ
は、システム内のキーワード登録順位番号をｋ、登録キ
ーワード内の文字位置順位番号をｐとするとき、Ｄ＝ｋ
×100＋ｐで表せるから、検索結果として得られた登録
データの文字位置順位番号ｐに該当する数値、すなわち
１〜99の任意の数値は、検索入力C₁C₂・・C_i-1C_iの最後の
文字C_iが、キーワード内で出現している位置になる。し
たがって、検索結果として得られた登録データの文字位
置順位番号ｐと、検索入力C₁C₂・・C_i-1C_iの最後の文字C_i
の文字位置順位番号ｉが等しいと、登録キーワードには
先頭からC₁C₂・・C_i-1C_iの文字列が存在しているといえる
ので、上記の部分一致検索処理で取り出した登録データ
の文字位置順位番号が、検索入力の文字数と一致する登
録データのみを抽出する手順を上述の部分一致検索処理
に追加することにより、前方一致検索を行うことができ
る。

さらに後方一致検索を行う場合には、上記の部分一致検
索で、検索入力の最後の文字C_iまで処理し、文字C_iに該
当する文字欄内の登録データを検索結果として抽出す
る。一方登録データＤは、システム内のキーワード登録
順位番号をｋ、登録キーワード内の文字位置順位番号を
ｐとするとき、Ｄ＝ｋ×100＋ｐで表せるから、検索結
果として得られた登録データの文字位置順位番号ｐに該
当する数値、すなわち１〜99の任意の数値は、検索入力
C₁C₂・・C_i-1C_iの最後の文字C_iが、キーワード内で出現し
ている位置になる。したがって、検索結果として得られ
た登録データ内において、検索入力最後の文字C_iの文字
位置順位番号ｉが登録キーワードごとに設けられたキー
ワード長一覧表から取り出したキーワード構成文字数に
等しければ、検索結果として得られた登録データはキー
ワードの最後尾文字といえるので、登録キーワードごと
にもうけられたキーワード表の一覧表から文字数を抽出
し、この文字数と取り出した登録データの文字位置順位
情報とが同一の登録キーワードのみを抽出することによ
り、後方一致検索を行うことができる。

〔発明の効果〕

以上説明したように、本発明によれば、キーワードを登
録するときに、キーワードを構成する文字ごとに、キー
ワードの登録番号と文字位置順位番号とからなる登録デ
ータに変換して、コード変換表を作成しておき、このコ
ード変換表により文字ごとの検索処理を行うので、部分
一致、前方一致、後方一致の各検索処理を行うことがで
きる。

また、キーワード検索処理において、先頭文字から順次
検索処理を行う必要がなく、検索入力の文字毎に並列に
検索処理を行うこともできるため、検索処理を高速化す
ることが可能である。

【図面の簡単な説明】

第１図は実施例情報処理装置構成図。第２図は実施例文字欄アドレス表。第３図は実施例コード変換表。第４図は実施例キーワード登録処理手順を示すフローチ
ャート。第５図は文字欄アドレス表の使用例。第６図はコード変換表の使用例。第７図は実施例検索処理手順を示すフローチャート。１……CPU、２……メモリ、３……入出力部、４……キ
ーボード、５……ディスプレイ、６……外部記憶装置制
御部、７……外部記憶装置、８……共通バス。

Claims

【特許請求の範囲】

【請求項１】検索用のキーワードを記憶する領域を備え
た記憶装置とCPUとを備え、検索用のキーワードを登録しておき、この登録キーワー
ドと検索入力との照合を行うことにより検索を行う情報
処理装置において、上記キーワードをその登録順に登録番号を付す手段と、この手段により登録番号を付されたキーワードを文字単
位に分解するとともに、この分解された文字ごとに先頭
からの文字位置順位番号を付す手段と、文字ごとにこの文字を規定するコードで指定される記憶
領域に上記登録番号と文字位置順位番号とからなる情報
を記憶する手段とを備えたことを特徴とする情報処理装置。
【請求項２】キーワードの登録番号とその文字位置順位
番号とからなる情報をその登録キーワードを構成する文
字ごとに文字コードで規定される記憶領域に分類し変換
表として記憶する記憶装置と、検索入力を文字ごとに分解する手段と、この分解された文字ごとに、その文字コードで規定され
るディレクトリを参照して上記変換表を検索する手段
と、上記変換表から検索入力の構成文字順に検索入力構成文
字の文字コードに対応する記憶領域の上記情報を取り出
し、登録キーワードの登録番号が一致し、さらに登録キ
ーワードの文字位置順位番号が検索入力の構成文字順に
則って連続している登録番号に対応する登録キーワード
を検索結果として出力する手段とを備えた情報処理装置。
【請求項３】検索入力構成文字の最終文字の文字コード
に対応する記憶領域から取り出した登録キーワードの文
字位置順位番号と検索入力の文字数とが一致する登録番
号の登録キーワードを前方一致検索結果として取り出す
手段を含む請求項２に記載の情報処理装置。
【請求項４】検索入力構成文字の最終文字の文字コード
に対応する記憶領域から取り出した登録キーワードの文
字位置順位番号と登録キーワードの文字数とが一致する
登録キーワードを後方一致検索結果として取り出す手段
を含む請求項２に記載の情報処理装置。