JPH0268663A - 文字列検索装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は文字列照合方式、とくに、磁気ディスクや光デ
ィスク等の２次記憶に保存さｎている文書ファイルを入
力し、あらかじめ登録されているキーワードと照合を行
なうことにより、文字情報（テキスト）中から文字列を
検索する装置に関する。

（従来の技術） 従来の文字列照合方法としては、（１）ソートサーチ法
、（２）連想メモリ法、（３）セルラアレイ法、（４）
有限状態オートマトン法、（５）ＤＰ法等が上げらｎる
が、こｎらの方法には以下のような問題点があった。す
なわち、（２１、（３）は長い文字列が扱えない。（１
）　、　（３１、（４）　、　（５）は可変長文字列の
ノンアンカマツチが扱えない。（５）は処理速度が遅い
。（３）　、　（４）　、　（５）はハードウェアサイ
ズが小さくならない。

こｎらの問題点の一部を解決するために、（２）と（４
）を組み合わせた文字列検索ＬＳＩ　（日本電気−ｌ５
ＳＰ　）が開発さｎ、高橋、他「ストリング・マツチン
グ・ハードウェアのアーキテクチャ」電子通信学会研究
報告（コンピュータシステム）、ＣＰＳＹ　８６−５７
１９８６．７に発表さｎている。

（発明が解決しようとする課題） このような（２）と（４）ヲ組み合わせた文字列検索Ｌ
ＳＩでも、連想メモリ中に同一文字や良く似た文字列が
複数登録さｎているとメモリ全問が効率良く使用できな
い、連想メモリ空間において文字列の登録に固定長ブロ
ックを使用するため、短い文字列が多いと登録メモリ空
間に無駄が多くなるなどの欠点がある。本発明はこの欠
点を解決する文字列検索装置を提供することを目的とす
る。

（課題を解決するための手段） 本発明による文字列検索装置は、上記目的を達成するた
めに、登録時、入力される複数の文字列を文字列の間に
区切り文字を挿入して登録文字列として登録し、検索時
、人力される文字列の各文字を登録文字列と照合し、登
録時に各文字の登録を示し、検索時に照合一致の有無を
示す登録／照合信号を出力する登録／照合制御部と、登
録／照合信号を受け、登録時に登録文字列の文字構成を
記憶し、検索時に入力文字列と比較し、各文字ごとに一
致の有無および区切シ文字を示す文字照合信号を出力す
る文字照合部と、文字照合信号に論理演算処理を施し、
その結果より検索時、入力文字列における登録文字列の
有無を区切り文字のごとに判定する文字列検出手段とを
有する。

（作用） 登録／照合制御部は、検索する複数の文字列をへカレ、
文字列間に区切り文字を入ｎ１かつ重複する文字を除き
、登録文字列として登録する。検索時に入力される文字
列の各文字を登録文字列と照合する。登録／検索時には
、登録を示し照合の一致の有無を示す登録／照合信号を
出力する。

文字照合部は、登録／照合信号から登録時に登録文字列
の文字構成を記憶し、検索時に入力文字列と比較し、各
文字ごとに一致の有無および区切り文字を示す文字照合
信号を出力する。

文字列検出手段は、文字照合信号を入力し、検索時に入
力される文字列における登録文字列の有無および一文字
誤りのある文字列を検出する。このように、区切り文字
を用い、かつ重複する文字登録を行わないことにより、
登録メモリを効率的に使用することができる。また、文
字検出手段により登録文字列およびその一文字誤りを検
出する。

（実施例） 次に、本発明の実施例を図面を参照して説明する。

第１図は本発明の文字列検索装置の実施例を示すブロッ
ク図である。本装置は登録モードで、検索する文字列を
登録文字列として登録し、検索モードで、文書ファイル
等の文書文字列の中から登録文字列およびその一文字誤
りを検出する。

クロック生成部３０はクロック信号５ｆ、文字照合部１
０およびシーケンシャル・エンコード部２０に供給する
。各部の入出力動作はこのクロック信号５に同期して行
わｎる。文字照合部ｌＯは、登録モードで、検出するキ
ーワード、熟語、短文等の登録文字列の入力文字列ｌが
入力されると、−文字登録ごとに文字照合信号２を出力
し、複数の登録文字列の間に区切り文字ＥＯ８（Ｅｎｄ
　ｏｆ　Ｓｔｒｉｎｇ　）を挿入する。

検索モードで文書文字列の入力文字列ｌが人力さむると
、登録文字列と照合し、−文字ごとに一致の有無を示す
文字照合信号２を出力する。

シーケンシャルエンコード部２０は、この信号２を入力
し、文書文字列の中に登録文字列を検出すると完全一致
信号３を出力し、登録文字列と一文字異なる文字列を検
出すると一文字誤シ検出信号４を出力する。

文字照合部２の構成を第２図に示す。登録／照合制御部
ｌ・２は、登録および検索モードで入力文字列１を文字
コード３に変換して出力する。

文字登録／照合部１４は、登録モードにおいて、文字コ
ード３を入力し、例えば、登録文字列が「あいまい検索
情報Ｆ：ＯＳ情報検索ＥＯ８Ｊとすると、その中から重
複文字を除いて［あいま検索情報ＥＯ８Ｊのように、メ
モリ空間を節約した登録を行ない、かつ各文字の登録／
照合信号７をアクティブにする。文字列変換テーブル１
６は、この信号７をクロック信号５により、元の登録文
字列の文字構成に展開して記憶素子に記憶する。検索モ
ードにおいて、文字コード３で入力される文書文字列の
各文字を記憶内容と照合し、一致があわば、登録／照合
信号７′！ｉ−アクティブに出力する。文字列変換テー
ブル１６はこの信号７と記憶素子の内容が一致すると、
この例では「あいまい検索ＥＯ８情報検索ＥＯ８Ｊの各
文字ごとの文字照合信号２をアクティブにする。

文字変換テーブル１６を第３図（、）、記憶素子を同図
（ｂ）に示す。テーブル１６を示す格子のドツトはメモ
リ素子が一文字を記憶した状態を示す。各記憶素子は１
ビツトのラッチｉ　６　ｉ１アンドｒ〜ト１６２、オア
ダート１６３で構成さｎている。各列には列の左よりク
ロック信号５に同期する登録／照合信号７が印加さ粗、
各行には上から下にクロック信号５が印加される。

登録モードで、ラッチ１６１は、端子ＣおよびＤにクロ
ック信号５および登録／照合信号７を同時に入力すると
、１文字を記憶し、その出力をハイレベル″Ｈ″′にす
る。こｎによって文字変換テーブル１６の格子点が図示
したドツトの記憶状態になる。検索モードで、行および
列にそｎぞｎクロック信号５および登録／照合信号７が
印加さｎｌその格子点のラッチ１６１が登録状態であｎ
ば、アンドゲート１６２はＨｎをオアダート１６３に出
力し、オアゲート１６３は文字照合信号２をＨ”にする
。

第４図に文字列変換テーブル１６のＥＯＳラッチ部分の
構成例を示す。登録／照合制御部１２から文字ＥＯ８を
示す登録／照合信号７が印加される列の各格子点に他の
列と同様にランチ１６１が接続さｎている。ラッチ１６
１はクロック信号５とＥＯ８の信号７の印加により文字
ＥＯ８を記憶し、かつＥＯＳラッチ出力８をＨ′にする
。

第５図に文字列検出手段であるシーケンシャルエンコー
ド部２０の構成を示す。登録文字列の各文字例えば、「
あいまい」に対応する検出を行なう回路よりなり、この
回路はアンドゲートａ、ｂ、ｃ、オアゲートｄ１１ビッ
トラッチｅ、ｆで構成さｎている。各回路の入出力は互
に縦続に接続され、検出する文字列と登録文字列が一致
すると、終端「い」の回路より完全−致信号３を出力し
、−文字の誤りがあると、その文字の回路から一文字誤
り信号４を出力する。

図示の回路において、文字列に「あいまい・・・」の前
位の入力文字列が終了するとその区切り文字のＥＯＳラ
ッチ出力８が各ラッチｅ、ｆのノリセット端子ＳＥＴに
出力さｎ１各ラツチを記憶可能の状態にセントする。「
あ」の回路において、オアケ゛−トａに入力する文字照
合信号２が「ア」の一致を示す”Ｈ”であわば、ゲート
ａはラッチｅに”Ｈ″を出力し、ラッチｅはこｎを記憶
して「い」の回路への出力を”Ｈ”にする。一方、アン
ドｙ　−トｂおよびＣはそｎぞｆｉ”ｌ、”および”Ｈ
′を出力するので、オアゲートｄは”Ｌ”を出力し、ラ
ッチｆはこｎを記憶して「い」の回路へＬ＃を出力する
。

「い」の回路において、文字照合信号２が不一致を示す
Ｌ”であわば、オアヶｔ　　）ａの出力は”Ｌ″となり
、ラッチｅはＬ″を出力する。アンドゲートｂはＨｎを
出力し、アンド’ｙ”　−）　ｃはＬ′を出力し、その
結果オアゲートｄはＨ”を出力し、ラッチｆは誤りを記
憶し一文字誤シ検出信号９＆−文字誤りを示すＨ′とす
る。

さて、文字「あいまい」の各文字照合信号２が一致を示
しだときは、最終文字「い」の回路が、各回路の文字照
合信号２の論理積である完全一致信号３を”Ｈ”にして
出力し、−文字の誤りがあるとこの信号３を”Ｌ”にす
る。

登録モードの動作例として、登録文字列が、「あいまい
検索」　「情報検索」　「・　・」である場合を＄６図
〜第８図に示す。入力文字列ｌとしては、登録文字列の
終わりを示す区切り制御文字ＥＯ８が挿入された「あい
まい検索ＥＯ８情報検索ＥＯ８・・・」が入力される。

第１図において登録モードの状態で入力文字列ｌが入力
されると、文字照合部１０では第２図の登録／照合制御
部１２に１文字ずつ登録文、字列の登録を行なう。その
際、最初の登録文字列の先頭文字「あ」は登録／照合制
御部１２の第１列に登録さｎ、こｎと同時に文字列変換
テーブル１６の（１，１）の格子点の位置にドツトが付
加される。

文字列変換テーブル１６の格子点は、例えば前述のよう
に第３図のような回路で構成されている。縦線は第２図
の登録／照合信号７に相当し、横線は同図の文字照合信
号２に相当している。ここで先のドツトはラッチ１６１
がセント（出力が“Ｈ”）状態にあることを意味する。

とｎはドツトを付加したい格子点の列の線（縦線）をア
クティブに保ちながら同格子点の行の登録クロック信号
を立ち上げることによってセントされる。以降、検索モ
ード時に登録文字がヒントし登録／照合信号７がアクテ
ィブになると、その登録／照合信号７上でドツトが付加
さゎた行の文字照合信号２がすべてアクティブになる。

第７図で、続いて２文字目「い」は登録／照合側Ｈ！ｔ
ｓｔｚの第２列に登録さｎ１同時に文字列変換テーブル
１６の（２，２）の格子点にドツトが付加される。３文
字目「ま」も同様にして（３，３）にドツトが付加され
るが、４文字目「い」は既に第２列に登録さｎているた
め、登録／照合制御部１２には登録さｊず、文字列変換
テーブル１６の（２，４）の格子点にドツトのみが付加
さむる。第８図で同様にしてｉ釦「索」も重複して出現
するので２度目以降は登録／照合制御部１２に登録さｎ
ず、文字列変換テーブル１６の所定の位置にドツトのみ
が付加される。つまり、文字照合部ｌＯは登録文字列を
登録する際、同一文字が登録されているかどうかをチエ
ツクし、既に登録さｎている場合には重複登録を行なわ
ず文字列変換テーブル１６の所定の位置に処理を加える
。

以上と同様にして登録文字列のＮ文字目（ＥＯ８も１文
字と数える）の情報がＮ行目のドツトとして登録される
。区切り制御文字ＥＯ８がＮ文字目として登録／照合制
御部１２に入力されるとＥＯ８の列がアクティブになる
。文字列変換テーブル１６のＥＯＳラッチ部分では、第
４図に示すように、その状態でＮ行目の登録クロックを
立ち上げるとＮ行目のＥＯＳラッチ１６１がセットされ
る。ラッテ１６１の出力は第５図のシーケンシャル・エ
ンコード部２０の２つのランチａ、ｆの非同期グリセッ
ト端子ＳＥＴに入力されるため、こｎらのラッチは”Ｈ
”を出力し続ける。

検索モードの動作例として、文書文字列が「近年、情報
検索分野においてあいまい検索の研究が盛んである・　
・」であるときを示す。

入力文字列ｌは登録モード時と同様に文字照合部１０に
同期的に入力される。文書文字列が入力さｎたときの文
字照合部１０の動作を第９図から第１４図に示す。登録
／照合制御部１２では、１文字人力されるごとに登録さ
ｎている全文字と比較し、合致する文字の登録／照合信
号７をアクティブにする。第９図で「近年、」まで入力
されたときは、まだ合致する文字が存在していないので
登録／照合信号７はどｎもアクティブにならない。第１
０図で、続いて「情」が入力されると、登録／照合制御
部１２の第６列の登録／照合信号７がアクティブになり
、（６゜８）のドツトによって第８行の文字照合信号２
もアクティブになる。なお、この図で破縁部分はアクテ
ィブな信号線を表している。さらに「報」　「検」　「
索」と入力されると、アクティブな信号線は第１１図〜
第１３図のように変化する。またさらに進んで、「あい
まい検索」の「索」が入力さｎた時点を示したのが第１
４図である。ここで第１０図〜第１４図中において丸で
囲１れた文字はシーケンシャル・エンコード部２０にお
けるその文字の完全一致信号が”Ｈ”状態にあることを
意味する。

文字列変換テーブル１６の出力（行方向の信号線）であ
る文字照合信号２は、このようにして１文字ずつ照合さ
ｎた結果として、シーケンシャル・エンコード部２ｏに
実時間で転送される。シーケンシャル・エンコ−１’Ｗ
ｚｏ（第５図）は、前述のように、登録／照合部１４と
同期して動作する複数の１ビツトランチとＡＮＤ　。

ＯＲ論理回路からなジ、実時間で入力さ君る文字照合の
結果を逐次登録文字列と照合する。その際、各登録文字
列についてそｎぞｎ完全一致信号３と１文字誤ジ検出信
号４の２つの信号を出力する。各登録文字列の最後の文
字に対する完全一致信号３は文書文字列の中にその登録
文字列が存在したことを示し、同文字に対する１文字誤
り検出信号４はその登録文字列と１文字だけ異なる文字
列が存在したことを示す。

また、同一文字を含む登録文字列の同一文字に対する文
字照合信号２は常に同時にアクティア’になるが、シー
ケンシャル・エンコード部２０では完全一致信号３と１
文字誤、り検出信号４を逐次伝搬・合成していくので、
該当しない登録文字列の完全一致信号３と１文字誤り検
出信号４は最終的にはアクティブにならない。例えば、
第１３図において「あいまい検索」の「索」と「情報検
索」の「索」の２本の文字照合信号２がアクティブにな
っているが、前者の「索」には丸が付いていない。こｎ
は前者の「索」の完全一致信号３が”Ｌ”になっている
ことを意味している。即ち、「索」の前の文字「検」の
完全一致信号３が”Ｌ”であるためである。（例第１３
図、第１４図） １文字誤り検出信号４は「情報検索」という登録文字列
について、以下のよう１文書文字列に対してもアクティ
ブになる。

「＊報検索」　「情＊検索」　「情報＊索」　「情報検
水」（＊は任意の１文字） 以上のようにして、文書文字列を入力し、あらかじめ登
録さｎているキーワードと照合を行なうことにより、必
要な文字列を検索でき、また１文字だけ異なる文字列も
検出できる文字列検索装置が構成できる。

（発明の効果） 以上説明したように本発明は次の効果を有する。

（１）複数の登録文字列の中に同一文字が含まｎでいて
も、そｎらの文字が重複して登録さｎない、また登録文
字列が固定長ブロックで分割さｎないため、文字列登録
空間が効率的に使用できる。

（２）１文字誤りを含む文字列を検出できる。

（３）装置構成が同一構造の繰り返し構造であるため設
計が容易で実装効率が高く、ＶＬＳ　１回きである。

【図面の簡単な説明】

第１図は本発明の文字列検索装置の実施例を示すブロッ
ク図、 第２図は同実施例の文字照合部の構成例を示すブロック
図、 第３図（、）は同実施例における文字列変換テーブルの
概念的構成例を示す説明図、同図（ｂ）はその内部構成
の例全示す回路図、 第４図は同実施例の文字列変換テーブルのＥＯＳランチ
部分の内部構成例を示す説明図、第５図は同実施例のシ
ーケンシャル・エンコード部の構成例を示す回路図、 第６図ないし第８図は同実施例における登録モード時の
動作の例を時系列的に示す説明図、第９図ないし第１４
図は同実施例における検索モード時の動作の例を時系列
的に示す説明図である。 １０・・・文字照合部 １２・・・登録／照合制御部 ｌ４・・・文字登録／照合部 １６・・・文字列変換テーブル ２０・・・シーケンシャル・エンコード部３０・・・ク
ロック生成部 １６１、ｅ、ｆ・・・１ビツトラツチ １６２、ａ〜Ｃ・・・アンピケ９−ト １６３、ｄ・・・オアケ９−ト

Claims (1)

1. 【特許請求の範囲】 １、登録時、入力される複数の文字列を該文字列の間に
   区切り文字を挿入して登録文字列として登録し、検索時
   、入力される文字列の各文字を前記登録文字列と照合し
   、登録時に各文字の登録を示し、検索時に照合一致の有
   無を示す登録／照合信号を出力する登録／照合制御部と
   、該登録／照合信号を受け、登録時に登録文字列の文字
   構成を記憶し、検索時に入力文字列と比較し、各文字ご
   とに一致の有無および前記区切り文字を示す文字照合信
   号を出力する文字照合部と、 前記文字照合信号に論理演算処理を施し、その結果より
   検索時、入力文字列における前記登録文字列の有無を前
   記区切り文字ごとに判定する文字列検出手段とを有する
   ことを特徴とする文字列検索装置。 ２、請求項１に記載の装置において、前記登録／照合制
   御部は、登録文字列に同一文字があるときは重複する登
   録を行わず、検索時に前記文字照合部の前記文字構成か
   ら前記登録文字列を識別することを特徴とする文字列検
   索装置。 ３、請求項１に記載の装置において、前記文字列検出手
   段は、文書文字列中に登録文字列が含まれているときに
   は完全一致信号を出力し、登録文字列と１文字だけ異な
   る文字列が検出されたときには１文字誤り検出信号を出
   力することを特徴とする文字列検索装置。