(57)【要約】サブワードの入力ストリング中で、与えられたリストからの一つまたは複数のワードの存在を検査するためのシステムである。ワードリストは、一つのサブワードを格納する各メモリセルに対して一つの比較器を有するメモリアレイに格納される。ストリングはサブストリングに分割される。比較レジスタに複数回ロードされる。サブストリングの各々は、毎回、一サブワードずつロールシフトされる。各メモリセルにおいて、入力サブストリングと同時比較がなされる。各メモリセル用の論理回路は、ストリングのサブワードと、リストのワードのサブワードとの間の連続した一致を検出する。リストの全ワードについて一致が生じるごとに、このワードに対して信号がセットされる。リスト一致信号がセットされ、一致ワードの一つのアドレス（位置）を出力するために、プライオリティエンコーダが用いられる。
2005505094.tif 000002
【特許請求の範囲】
【請求項１】
与えられたワード（単語）リストからの一つまたは複数のワードの存在をサブワードのストリングについて検査する逆検索システムであって、
前記システムは、以下の（ａ）〜（ｇ）を含むことにより、メモリアレイに格納されたワードリストの一つまたは複数のワードの任意の位置における存在をサブワードのストリングに対してチェックするという複数の連続する検索処理を、連続して行う。
（ａ）前記ワードリストを格納するメモリアレイ；前記メモリアレイは、所定の順序に従って配置された複数のメモリセルを含み、前記メモリセルのそれぞれは、一つのサブワードを格納し、比較手段および論理回路と接続される。
（ｂ）前記サブワードのストリングを、所定数以下の数のサブワードを含むサブストリングに分割するバッファ／区分手段；
（ｃ）前記所定数以下の数のワードを含むように設計された前記サブストリングを格納する入力バッファレジスタ回路；
（ｄ）比較処理の間、前記サブストリングを異なる位置に格納する比較レジスタ回路；
（ｅ）サブストリングのそれぞれを前記比較レジスタ回路へ複数回与えるローラ／シフタ回路；前記サブストリングは、全ての必要なサブワード位置でチェックできるように、前記比較レジスタ回路へ与えられるたびに、シフトされロールされる。
（ｆ）比較レジスタに格納されたデータを前記メモリセルへ伝達する一組のビットライン；前記ビットラインの接続は、二つの隣接するメモリセルの比較器が、入力として、前記比較レジスタの二つの隣接セルのデータ、または、前記比較レジスタの最終または最初のセルのデータのいずれかをそれぞれ受け取るように、循環的に構成されている。
（ｇ）前記メモリセルへ論理信号を伝達することにより、各ロールシフト処理後の前記サブストリングのサブワードの新しい位置をマークする一組の区切りライン；前記区切りラインの接続は、前記二つの隣接メモリセルに接続された論理回路が、入力として、前記比較レジスタの二つの隣接セルからの論理信号、または、前記比較レジスタの最終または最初のセルの論理信号のいずれかをそれぞれ受け取るように、循環的に構成されている。
【請求項２】
メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する、請求項１に記載の逆検索システムであって、
前記比較レジスタのセルのそれぞれが、一つの区切りラインに接続され、前記区切りラインに接続された前記比較レジスタのセルが現在検査されている格納ワードの最初のサブワードを格納する場合、区切りラインは論理１にセットされ、
これにより、前記論理信号は、前記メモリへ、前記サブワードストリングの最初のサブワードの位置と先行サブワードストリングの最終のサブワードの位置とを指示する。
【請求項３】
メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する、請求項１に記載の逆検索システムであって、
前記比較レジスタのセルのそれぞれが、一対の第１および第２の区切りラインに接続され、前記第１の区切りラインが、前記第１の区切りラインに接続された比較レジスタのセルが現在検査されているワードのストリングの最初のサブワードを格納する場合に、論理１にセットされることにより、前記メモリへ前記ストリングの最初のサブワードの位置を指示する論理信号を生成し、第２の区切りラインは、前記第２の区切りラインに接続される比較レジスタのセルが、現在チェックされているストリングの最終のサブワードを格納する場合に、論理１にセットされることにより、前記メモリへ前記ストリングの最終のサブワードの位置を指示する論理信号を生成する。
【請求項４】
メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する、前記の先行請求項のいずれかに記載の逆検索システムであって、
前記ローラシフタ回路は、非活動状態であり、ただ一つのサブワードが前記入力レジスタへ与えられ、ただ一つのサブワードが前記比較レジスタへ与えられ、前記検査処理は、入力レジスタおよび比較レジスタの両方を単一回路に実装することにより達成される。
【請求項５】
メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する、前記の先行請求項のいずれかに記載の逆検索システムであって、
前記ローラシフタ手段がソフトウェアである。
【請求項６】
メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する、前記の先行請求項のいずれかに記載の逆検索システムであって、
前記バッファ区分手段は電気回路である。
【請求項７】
メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する、前記の先行請求項のいずれかに記載の逆検索システムであって、
前記逆検索システムは、複数のワードが一致すると判明した場合に一致ワードの一つのアドレスを、所定の有線順序に従って出力するために用いられるプライオリティエンコーダを含む。
【請求項８】
逆検索システムにおいて、メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する逆検索方法であって、
前記逆検索方法は、以下のステップを含む。
（ａ）ワードリストを、所定の順序に従って配置された複数のメモリセルを有するメモリアレイへ、各メモリセルが一つのサブワードを格納するように格納する；
（ｂ）前記サブワードのストリングを、所定数以下の数のサブワードを含むサブストリングに分割する；、
（ｃ）前記サブストリングの一つを、前記所定数以下の数のサブワードを含むように設計された入力バッファレジスタ回路内に格納する；
（ｄ）前記サブストリングを、当該サブストリングが全ての必要なサブワード位置でチェックされるように、様々なロールシフトされた位置で、比較レジスタ回路へ繰り返し与える；
（ｅ）前記サブストリングの最初のサブワードを格納する比較レジスタのメモリセルに接続された区切りラインを除いて、前記区切りラインを第１の論理状態にセットする；
（ｆ）前記メモリアレイ中の各メモリセルに接続された比較手段へ、前記セルの両方に接続されたビットラインにより、前記比較レジスタの一つのセルにそれぞれ格納された一つのサブワードのデータを入力する；前記ビットラインの接続は、二つの隣接メモリセルｋおよびｋ＋１が、入力として、二つの隣接セルのいずれかのデータまたは比較レジスタの最終および最初のセルのデータをそれぞれ受け取るように循環的に配置されている。
（ｇ）前記サブストリング中で存在がチェックされるワードの最初および最後のサブワードをそれぞれ格納するメモリセルに、ワード開始信号およびワード終了信号を設定する；
（ｈ）メモリアレイ中のメモリセルに格納されたサブワードと前記メモリアレイ中で前記サブワードへ信号を伝達する比較レジスタのセルに格納されたサブワードとの間で同時に比較を行う比較手段を操作する；
（ｉ）一致が発見された場合、前記メモリアレイの一致メモリセルのそれぞれにおいてサブワード一致信号をセットする；
（ｊ）前記メモリセルのそれぞれに接続された論理回路により、サブワード一致信号を以下のａ）〜ｃ）に論理的に連結する；ａ）先行メモリセルの一致信号、ｂ）開始および終了ワード信号、ｃ）検査されているワードの先行サブワードが先行する隣接サブストリングに位置しておりかつ一致すると判明した場合にセットされる部分一致信号。
（ｋ）前記ワードの開始サブワードから始めて、前記メモリセルのそれぞれのサブワード一致信号を、前記メモリセルのそれぞれの直前にあるセルからの信号にそれぞれ累積的に連結することにより、前記メモリセルに先行する全てのメモリセルが一致するか検査する；
（ｌ）前記ワードの開始サブワードから始まる全ての先行サブワードが一致すると判明した場合、前記ワードの終了サブワードにおいてワード一致信号を発行する。
【請求項９】
逆検索システムにおいて、メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する請求項８に記載の逆検索方法であって、
複数のワードが一致すると判明した場合、所定の優先順位に従って一致ワードの一つのアドレスを出力するプライオリティエンコーダが用いられる。
【請求項１０】
逆検索システムにおいて、メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する請求項８または９に記載の逆検索方法であって、
前記ワードのストリングをサブストリングへ分割することが、ソフトウェア手段によって実行される。
【請求項１１】
逆検索システムにおいて、メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する請求項８または９に記載の逆検索方法であって、
前記ワードのストリングをサブストリングへ分割することが、ハードウェア手段によって実行される。
【請求項１２】
逆検索システムにおいて、メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する請求項８ないし１１のいずれかに記載の逆検索方法であって、
前記リストの一つまたは複数のワードが一致すると判明した場合、リスト一致信号がセットされる。
【請求項１３】
逆検索システムにおいて、メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する請求項８ないし１２のいずれかに記載の逆検索方法であって、
必要とされるシフトロール処理の数が、前記比較レジスタのサブワード数と等しい。
【請求項１４】
逆検索システムにおいて、メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する請求項８ないし１２のいずれかに記載の逆検索方法であって、
前記リストのワードのそれぞれが、前記メモリアレイに２回格納され、前記ワードのそれぞれの２回の出現は、ワードの最初の出現の最初のサブワードが、前記ワードの２回目の出現の最初のサブワードと並列なサブワードからｎ／２サブワードの距離で除去される比較レジスタのサブワードと並列になるように配置されることにより、必要なシフトロール処理の回数が比較レジスタのサブワード数の半分まで減少される。
【請求項１５】
逆検索システムにおいて、メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する請求項８ないし１２のいずれかに記載の逆検索方法であって、
前記リストの各ワードは、前記メモリアレイにＸ回格納され、前記ワードのそれぞれのＸ回の出現は、ワードの最初の出現の最初のサブワードが、前記ワードの次の出現の最初のサブワードと並列なサブワードからｎ／Ｘサブワードの距離で除去される比較レジスタのサブワードと並列になるように配置されることにより、必要なシフトロール処理の回数が比較レジスタのサブワード数のｎ／Ｘに減少される。
【請求項１６】
メモリアレイに格納された所定のワードリストからの一つまたは複数のワードの存在を、サブワードのストリングに対して検査する逆検索方法システムにおいて適用される論理連結方法であって、前記メモリアレイのメモリセルのそれぞれに一つのサブワードが格納され、前記メモリセルのそれぞれに論理回路が接続され、メモリセルｉの論理回路Ｌiは、以下の（ａ）〜（ｃ）の条件の一つが満たされた場合に、次のメモリセルｉ＋１の回路へ入力される中間連結信号Ｃｂiを出力する。
（ａ）先行回路Ｌi-1の中間連結信号Ｃｂi-1もセットされており、前記メモリセルｉのサブワードＳｗiが一致すると判明し、区切りラインから信号を受信していない。すなわち、前記サブワードＳｗiは新しいサブストリングの最初のサブワードではなく、現在のサブストリングは、現在検査されている格納ワードの最初のサブワードから始まる全ての先行サブワードに一致することが判明している。または、
（ｂ）前記区切りラインがセットされている。すなわち、前記サブワードＳｗiは新しいサブストリングの最初のサブワードであり、一致信号がセットされている。前記一致信号とは、前の隣接サブストリング上の先行処理の結果、前記先行ストリングの最終部分が前記メモリアレイの格納ワードの一部に一致することが判明し、前記サブワードＳｗiが一致すると判明していることを表す。
（ｃ）前記区切りライン上に信号がセットされている。すなわち、前記サブワードＳｗiが前記サブストリングの最初のサブワードであり、前記サブワードＳｗiが一致すると判明している。
ＣＢi信号がセットされている場合、ワード一致が出力される。ワード一致は、前記格納ワードの全ての先行サブワードが一致したと判明しており、前記サブワードＳｗiが、前記格納ワードの最終サブワードとして、前記サブワードＳｗiのワード終了信号によって、または、次のサブワードＳｗi+1のワード開始信号によってマークされていることを意味する。
ＣＢi信号がセットされ、当該サブワードが前記格納ワードの最終サブワードでなく、当該サブワードが前記サブストリングの最終サブワードと平行である場合に、部分一致が出力される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一つまたはそれ以上のワードの存在をデータ列中の所定のリストから検出するために通信システムに適用されるシステムおよび方法に関する。
【背景技術】
【０００２】
このような検査手続は、ウィルス署名を含むデータパケットを検出して遮蔽したり、特定のインターネットサイトのアドレスを検出して遮蔽するために用いられる。
【０００３】
データ中で、予め定義されたリストからのワードの存在を検索するとき、データ中のワードの最終的な位置はわからない。また、通常、検索されるワードのデータ中での開始位置を示すマークやサインはない。例えば、検索されるデータがバイトデータのパケットである場合、検索されるワードは、そのデータ中の任意のバイト位置から始まる可能性がある。このため、それぞれの開始位置をチェックするために、実行される検索の回数は非常に多くなり、総検索時間は非常に長くなる可能性がある。
【０００４】
このような検査手続きは、データ検査に用いられるとき、システム全体の処理スピードを落とすこととなる。現存のシステムにおいて、比較処理を行うためには主にソフトウェアが用いられ、処理ユニットは、リストの一ワードとデータの一箇所との比較を行う。リスト中には多くのワードが存在するので、プロセッサは、データをセクションに分割する手続きを用いる。このセクションは、リストの一ワードと同じサイズを持つ。そして、プロセッサは、各セクションと同一のワードとの比較を行う。この全体手続きは、リスト中に存在するワードと同じ回数だけ繰り返される。データ検査処理に必要な総時間は、そのために非常に長くなる可能性があり、通信またはコンピュータシステムの処理スピードを極端に落とすこととなる。
【０００５】
そこで、データの一群の中で、一つまたは複数のワードの存在を、予め記憶されたそのようなワードのリストから、高速に検出できる検査システムを提供することが望まれている。
【発明の開示】
【０００６】
本発明は、サブワード列において、与えられたリストからの一つまたは複数のワードの存在を検査するためのシステムおよび方法を提供する。ワードリストは、一つのサブワードを格納する各メモリセルに対して一つの比較器を備えたメモリアレイに格納されている。検査されるデータ列は、一連のサブストリングに分割される。各サブストリングは、比較レジスタに複数回ロードされ、毎回一つのサブワードずつロールシフトされる。各メモリセルにおいて、入力されたサブストリングと同時比較がなされる。入力ストリングのサブワードとリストのワードのサブワードとの連続した一致を検出するために、論理回路が、各メモリセルに関連付けられている。リストの全ワードについて一致が発生すると、このワードに対して信号がセットされる。最後に、全体一致信号がセットされ、一致する複数のワードの一つのアドレス（位置）を出力するために、プライオリティエンコーダを用いることもできる。
【発明を実施するための最良の形態】
【０００７】
本発明は、検査処理を実行することにより、所定のワードリストからの一つまたは複数のワードの存在を、データ列において検出する方法およびシステムを提供する。本発明のシステムおよび方法において、前記リストは、可変長ワードを含んでも良い。
【０００８】
通信システムにおいて、通信装置を通過するデータが、所定のワードリストからの一つまたは複数のワードを含むかチェックすることが望ましいかも知れない。例えば、前記ワードリストは、ウィルス署名のリストであっても良い。この新規なシステムは、そのようなウィルス署名を含むデータパケットを検出し遮蔽するために採用される。第二の例としては、前記ワードリストは、そこへのアクセスが遮蔽されるべきサイトのインターネットアドレスのリストであっても良い。
【０００９】
コンピュータシステムにおける他の適用によれば、異なる領域にデータを格納することが好ましい。そのような領域の選択は、格納されるデータの種類に依存する。このために、データの選択を特徴付けるワードリストが格納され、データ中に前記リストの一つのワードが存在すれば、データは選択領域に格納される。その中に見つかったワードに応じて、そのようなワードのいくつかの異なるリストを定義することができ、データの分類をすることができる。このような格納により、与えられた対象に関連するワードの一つを含むテキストを検索することが可能となる。
【００１０】
上述の検索手続きは、システム全体の処理スピードをかなり遅くする傾向がある。
【００１１】
本発明において、単一の比較サイクルにおいて多数の比較が実行される検査システムが提案される。これにより、処理スピードをかなり向上させることができる。時間単位毎にチェック可能なデータサイズは非常に大きく、本発明にかかる検査手続きは、システム全体の処理スピードに最小の影響を与えるかまたは全く影響を与えることなく、通信またはコンピュータシステムで利用可能である。
【００１２】
本発明に従って設計されたシステムは、例えば、ウィルス検出、ファイアウォール、インテリジェントルータ、侵入者に対する防御、データベース管理などの多くのコンピュータおよび通信システムに用いることができる。
【００１３】
一つの予め定義されたワードをワードリストから検索する手続きに対して、ワードリストからの一つのワードの存在をデータ列から検索するこのような検索手続きのことを、ここでは、「逆検索」システムと称する。
【００１４】
以下に、本発明について、好適な実施形態を示して詳細に説明する。しかし、より広い側面において、発明から乖離することなく、多くの変更や改良が可能であることは理解されるであろう。従って、添付された請求項は、真実の精神および本発明の範囲に入る限り、そのような変更および改良の範囲内で拡張されるべきである。
【００１５】
図１に、一般的なブロック図を示す。検索および検査されるデータは、文字列（入力ストリング）の形式で示されており、予め格納されたリスト（ワードリスト）からの一つまたは複数のワードの存在を検出するために、逆検索システムへ入力される。データは、どのような種類であっても良く、図１に示された文字は、任意のビット数を持つ任意のデータを表す。このデータは、データの基本部分であり、ここでは「サブワード」と称する。
【００１６】
入力ストリングのサブワードの番号ｎを格納するために、入力バッファレジスタが用いられる。各サブワードは、一つのメモリセルに格納される。入力ストリングを小さなサイズのサブストリングに分割するために、バッファ／区分器が用いられる。各サブストリングは、入力バッファレジスタに格納することができるサブワード数以下の数のサブワードを含む。このバッファ／区分器は、次に、入力ストリングの全てのサブストリングのデータを、メモリアレイに格納されたデータと比較するために、入力バッファレジスタに順に書き込む。入力ストリングの全てのサブストリングは、入力バッファレジスタに順に入力される。そして、各サブストリングは、検査され、以下に説明する手続きにより、ワードリストと比較される。そして、全てのセクションが入力バッファレジスタを「通過して検査された」とき、入力ストリングの全体が検査される。バッファ／区分器の機能は、ここでは示されていない。それは、一般的なソフトウェアおよびハードウェア技術を用いた、プロセッサおよび／または論理回路として実現可能である。特に、このバッファ区分器は、流れるデータに対して動作可能である。すなわち、入力ストリングを通信ラインから順次受け取る。この場合、入力ストリングは、無限長であっても良い。ｎ個のサブワードを受け取るごとに、そのｎ個のサブワードのサブストリングが入力バッファレジスタへロードされ検査される。図１において、入力ストリングの二つのサブストリングｐとｐ＋１とが示され、入力バッファレジスタがｐサブストリングのデータを格納しているところが示されている。
【００１７】
図１は、また、ワードリストを格納するために用いられるメモリセルアレイも示している。各メモリセルは、一つのサブワードを格納できる。各ワードは、連続するメモリセルに、メモリアレイの所定の順序に従って格納されるサブワードの列からなる。このような所定のメモリ順序を図２に示す。
【００１８】
図１には、ワード開始信号およびワード終了信号も示されている。これらの信号は、各メモリセルに対して設定することができ、メモリアレイに格納されているワードの最初および最後のサブワードをマークするために用いられる。これらの信号は、ワードリストをメモリアレイにロードするときに、様々な手段により設定することができる。図１では、ワード開始信号は星印で示され、ワード終了信号は二重丸で示されている。
【００１９】
図１に示すシステムは、ｎ個のメモリセルを備えた比較レジスタも含み、ｎ個のサブワードを格納することができる。
【００２０】
図１に示すように、また、図３により詳細に示すように、比較器Ｃiが、メモリアレイの各メモリセルに関連付けられている。比較レジスタの一つのセルに格納された一つのサブワードのデータは、図１および図３に示すビットラインにより、この比較器に入力される。図３において、一つのビットラインは、メモリセルの各ビットについて示されている。図１では、分かりやすくするために、全てのサブワードについて一つのラインのみ示している。しかしながら、各サブワードは、複数のビットを含み、典型的には、サブワードのビット毎に一つまたは二つのビットラインが必要である。各サブワードについて、サブワードのビット数と少なくとも同数のビットラインが存在することが分かるだろう。
【００２１】
各メモリセルについて、比較器が、メモリセルに格納されたサブワードと比較レジスタの一つのセルのサブワードとを比較するように設計される。この種の比較器は、コンテントアドレッサブルメモリに一般的に用いられている。ビットラインの接続は循環的になされており、二つの隣接するメモリセルｋおよびｋ＋１の比較器は、入力として、二つの隣接するセルのデータ、または、比較レジスタの最後または最初のセルのデータのいずれかを、それぞれ受け取る。この明細書において、メモリアレイのセルの比較器が、入力として比較レジスタのあるセルに格納されているデータを受け取る場合、そのメモリセルは比較レジスタのそのセルに「並列である」と定義する。
【００２２】
再び図１を参照すると、ローラ／シフタ回路が示されている。この回路の機能は、入力バッファレジスタからのサブストリングを、比較レジスタへ必要な回数だけ移動させることである。データは、比較レジスタへの入力がなされるごとに、１回または複数回シフトおよびロールさせられる。その結果、各サブストリングは、ロードされ、メモリアレイのワードと、可能な最終的な一致を含む、シフトロールされた可能な構成の全てについて、比較される。シフトおよびロールは、ここでは、ｋがｎより小さければ、比較レジスタのセルｋに格納されたサブワードが、セルｋ＋１に移動され、最後のセルｎのサブワードが最初のセル１に移動されることをいう。好適な実施形態では、シフト／ロール処理は時計回りになされるが、反時計回りの処理も本発明の方法およびシステムの範囲内に属することは明らかであろう。
【００２３】
本発明の方法の好適な実施形態において、シフトロール処理の必要回数は、比較レジスタのサブワードの数ｎと等しい。しかし、シフトロール処理の回数は、アプリケーションの要求に応じて、ｎよりも小さくても良い。本発明の方法が、一致するケースの制限された数を定義する規則に従って実行されても良いことは、本発明の方法の枠組み内で予見される。
【００２４】
このため、例えば、逆検索システムを高速に動作させることが好ましい。このために、逆検索方法は、リストの各ワードをメモリアレイに２回ロードし、前記同じワードの２回の出現は、前記ワードの最初の出現の最初のサブワードが、前記ワードの２回目の出現の最初のサブワードと並列なサブワードからｎ／２サブワードの距離で除去される比較レジスタのサブワードと並列に配置されるように、適用することができる。メモリアレイへリストのワードを２回ロードするこの方法によれば、リストの一つのワードの存在を検査する際に、ｎ／２だけのロール／シフト位置が必要とされる。なぜならば、最終的な一致は、メモリ内のワードの最初または２番目の出現のいずれかで起こる可能性があるからである。より高速な処理が必要とされる場合は、ワードのリストを、メモリアレイへ、３回以上ロードしても良い。
【００２５】
図１には、ｎ本の「区切りライン」ＤＬ1〜ＤＬnも示されている。一方の区切りラインは、比較レジスタの各メモリセルに連携している。各区切りラインは、その区切りラインに連携する比較レジスタのメモリセルに並列な全てのメモリセルに導かれている。区切りラインの論理状態は、その区切りラインに連携する比較レジスタのセルが、現在検査されているサブストリングの最初のサブワードを格納するときに、論理１にセットされる。この結果、区切りライン上の信号は、各ロールシフト処理後のサブストリングの最初のサブワード位置をマークすることとなる。図１の例では、「Ａ−ＬＯＮＧ−Ｏ」というサブストリングが入力バッファレジスタへロードされており、３回のロールシフトの後に、そのサブストリングは、「Ｇ−ＯＡＬＯＮ」として比較レジスタへロードされている。サブストリングの最初にある「Ａ」という文字の直前の３つ目の区切りラインは、そこで、論理１にセットされることにより、サブストリングの最初のサブワードをマークする。そして、区切りライン上のこの信号は、そのサブストリングの最初のサブワードを含む比較レジスタのメモリセルに「並列な」メモリセルに連携する全ての論理回路へ入力される。論理レベル１にセットされた３つ目の区切りラインは、太い線として図１に示されている。
【００２６】
この好適な実施形態において、比較レジスタの各セルに対して一つの区切りラインが用いられている。この場合、論理状態１にセットされたこの区切りラインは、サブストリングの最初のサブワードをマークし、サブストリングの最後のサブワードは、セットされた次のサブワードの区切りラインによってマークされる。本発明の範囲内の他の好適な実施形態では、二つの異なるラインを各サブワードに対して用いることが可能である。この場合、一つのラインは、最初のサブワードをマークするために用いられ、もう一つのラインは、最後のサブワードをマークするために用いられる。このような場合、比較レジスタに格納されたサブストリングは、比較レジスタそのものよりも小さいサイズであっても良い。ここでは、説明を明確にする目的だけで、比較レジスタセル毎に一つの区切りラインを有する好適な実施形態を示す。比較レジスタに格納されたサブストリングの最初および最後のサブワードの両方を信号でマークするシステムでは、これら二つのマークは、これらの最初および最後のサブワードのデータが格納された比較レジスタのセルに並列なメモリアレイの全てのセルに伝達される。比較レジスタの各サブワード毎に二つの区切りラインが用いられる場合、サブストリングの最初のサブワードが、これらの区切りラインの一つをセットすることでマークされ、サブストリングの最後のサブワードは、他方の区切りラインをセットすることでマークされる。この好適な実施形態は、比較レジスタの最初のサブワードが一つの連携された区切りラインによりマークされることにより、先行するサブワードが最後のサブワードとして自動的にマークされる、単純化されたケースである。
【００２７】
図３において、メモリアレイの二つの隣接セルｉ−１およびｉと連携する回路とが示されている。ブロックＬi-1およびＬiは、図４を参照して後述する論理回路を表す。Ｌi回路は、３つの出力信号ＣＭi、ＰＭＳi、ＷＭiと、７つの入力、すなわち、ＳＷＭi、ＷＳi、ＷＥi、ＣＭi-1、ＰＭi-1、並びに、区切りラインＤＬkおよびＤＬk+1の信号を有する。
【００２８】
ＳＷＭi（サブワード一致）はメモリセルの比較器からの出力信号である。一致した場合、信号はセットされる。
【００２９】
ＣＭi（連結一致）は、いくつかの連続するメモリセルの一致をチェックするために生成される中間信号である。
【００３０】
ＷＳiおよびＷＥiは、ワード開始およびワード終了信号である。
【００３１】
ＰＭi-2およびＰＭi-1ブロックは、「部分一致」を表す信号であり、先行するＬi-1から出力されるＰＭＳi-1信号によりセットされ、区切りライン信号によりリセットされる。ＰＭi-1信号は、サブストリングの終端部分がメモリアレイのワードの一致部分であると判明したことを示す情報を格納するために用いられる。後続サブストリングに格納される入力ストリングの後続文字が、そのワードの後続部分に一致する可能性がある。
【００３２】
ＷＭi（ワード一致）は、ワード全体が一致したと判明したことを表す信号である。
【００３３】
まず、逆検索システムの概略機能を説明し、その後、好適な実施形態の論理回路の詳細を示す。
【００３４】
前述のように、入力ストリングは、バッファ／区分器によりサブストリングに分割され、全てのサブストリングは、一つずつ、入力バッファレジスタへロードされる。各サブストリングは、入力バッファレジスタへロードされたとき、１サブワードずつシフト／ロールされ、比較レジスタへｎ回ロードされる。サブストリングが所定のシフト／ロールと共に比較レジスタへロードされる毎に、メモリアレイの全ての比較器が、メモリアレイに格納されているサブワードと比較レジスタの並列セルに格納されているサブワードとの比較を同時に実行する。一致が発見されると、サブワード一致信号（ＳＷＭi）が、アレイの一致メモリセルのそれぞれにおいて発行される。これらのサブワード一致信号は、Ｌ回路によって、ａ）先行セルの一致信号、ｂ）ワード開始および終了信号、ｃ）区切りライン信号、および最後にｄ）先行セルの「部分一致信号」と論理的に結合される。これにより、入力ストリングのいずれかの一連のサブワードがリストのワードの一連のサブワードと一致した場合に、ワード一致信号が出力される。
【００３５】
論理的組み合わせの機能の原理は下記のとおりである。
【００３６】
ワードの開始サブワードから始まる先行サブワードの全てが一致信号を有する場合、リストのワードの最終サブワードにおいてワード一致信号が発行される。これは、各メモリセルで連結一致中間信号が生成されることにより、チェックされる。この信号は、メモリセルの格納されたサブワードが一致すると判明したときにセットされ、先行する連結一致信号もセットされる。入力ストリング中に前記ワードが存在するが、いくつかのサブストリング間で分断されている場合、連続するサブワードがそのサブストリングの最終まで一致すると判明する毎に、部分一致信号がセットされ、そのサブストリングの最終サブワードは区切りラインによりマークされる。次のサブストリングがロードされシフトされたとき、このサブストリングの最初のワードの位置が、部分一致が発見された場所の隣の位置に対応すれば、部分一致は、次のサブストリングをチェックするための条件として用いられる。最初のサブストリングにおいて部分一致があった場合、比較処理は２番目のサブストリングに続くが、最初のサブストリングにおいて一致が発見されなかった場合、この特定のワードに対する比較処理は中止される。
【００３７】
比較処理が、連続した一致結果と共に、ワードの終端に到達した場合、ワード一致信号が発行される。
【００３８】
部分一致信号は、セットされている場合、次のサブストリングの一致チェックに用いられた後にリセットされなければならない。これは、次のように行われる。すなわち、メモリアレイの各セルに対して、対応する区切りラインがセットされる毎に（比較レジスタの並列セルがサブストリングの最初のサブワードを含むことを表す）、部分一致信号がもしセットされていれば、まずＬ回路へ入力され、それから論理ゼロにリセットされる。
【００３９】
図４に、上述の論理回路Ｌiの機能を実行する論理的な組み合わせを示す。このような論理回路は、ワードのリストを格納するメモリセルのアレイにおける各セルに接続される。
【００４０】
各Ｌi回路は、次のＬi+1回路へ入力される中間連結信号ＣＢiを出力する。この連結信号は、以下の３つの条件のいずれかが満たされた場合に出力される。
【００４１】
ａ）先行回路Ｌi-1の信号ＣＢi-1もセットされており、サブワードｉが一致すると判明しており（すなわち、比較器ＣiがＳＷＭi信号を出力）、区切りラインがセットされていない。
【００４２】
ｂ）区切りラインがセットされ、部分一致がセットされ、サブワードが一致する（ＳＷＭiがセットされている）と判明している。このケースは、部分一致が先行サブストリングの先行処理によってセットされている場合に生ずる。
【００４３】
ｃ）サブワードがワードの最初のサブワードであり（開始ワードマークＳＷiがセットされている）、サブワードが一致すると判明していれば、ＣＢiがセットされている（ＳＷＭiがセットされている）。
【００４４】
ＣＢiがセットされていれば部分一致ＰＭiがセットされるのは、そのワードの全ての先行サブワードが一致すると判明しており、サブワードｉがサブストリングの最終サブワードに並列であり、ワードの終端まで到達していないことを意味する。このため、ＣＢi信号と次のメモリセルへ導かれるＤＬ信号とＷＥiの反転信号とを連結するＡＮＤ関数が提供されている。このＡＮＤ関数の出力は、部分一致信号をセットするために用いられる。
【００４５】
「ワード一致」（ＷＭi）は、以下の条件が満たされた場合に出力される。すなわち、そのワードの全ての先行サブワードが一致すると判明したことを意味するＣＢiがセットされ、サブワードが最終の「サブワード」としてワード終了信号（ＷＥiがセットされている）によりマークされている場合である。
【００４６】
最後に、図５に示すように、少なくとも一つのワード一致信号がセットされていれば、リスト一致信号がセットされる。
【００４７】
さらに、図６に示すように、全てのワード一致信号は、プライオリティエンコーダへ導かれ、一致ワードの一つの位置（アドレス）がプライオリティエンコーダの公知の技術を用いて出力される。
【００４８】
本発明の逆検索システムおよび方法は、メモリアレイに格納されたワードリストの一つまたは複数のワードの任意の位置における存在をサブワードのストリングに対してチェックするという複数の連続する検索処理を、連続して行うことにより、処理時間の大きな短縮を達成することが可能である。
【図面の簡単な説明】
【００４９】
【図１】発明の逆検索システムの好適な実施形態の一般的な構成を示すブロック図である。
【図２】逆検索システムにおいてワードリストを格納するために用いられるメモリセルアレイについて定義された順序を示す。
【図３】位置ｉおよびｉ＋１において二つの隣接するメモリセルＭiとＭi+1と、これらのメモリセルに連携する回路と、メモリアレイの各メモリセルＭiに連携する回路（Ｌi）の入出力信号とを示す。
【図４】Ｌi回路の機能を実現する論理回路を示す。
【図５】リスト一致信号を生成するＯＲ回路を示す。
【図６】いくつかの同時一致結果の場合に適用され得るプライオリティエンコーダを示す。
【図１】
2005505094.tif 000003
【図２】
2005505094.tif 000004
【図３】
2005505094.tif 000005
【図４】
2005505094.tif 000006
【図５】
2005505094.tif 000007
【図６】
2005505094.tif 000008
【国際公開パンフレット】
2005505094.tif 000009
2005505094.tif 000010
2005505094.tif 000011
2005505094.tif 000012
2005505094.tif 000013
2005505094.tif 000014
2005505094.tif 000015
2005505094.tif 000016
2005505094.tif 000017
2005505094.tif 000018
2005505094.tif 000019
2005505094.tif 000020
2005505094.tif 000021
2005505094.tif 000022
2005505094.tif 000023
2005505094.tif 000024
2005505094.tif 000025
2005505094.tif 000026
2005505094.tif 000027
2005505094.tif 000028
2005505094.tif 000029
【国際調査報告】
2005505094.tif 000030
2005505094.tif 000031
2005505094.tif 000032