(57)【要約】本発明に係る構文解析方法は、メモリにキーワードに対応したリファレンスデータとリファレンスデータに対応した参照先テーブルデータ及びフラグデータとから構成される１組のデータを複数組含むテーブルを複数組含むテーブルをアドレスデータに対応させて複数個用意する工程と、メモリから１つのテーブルを取出す工程と、ストリームデータからターゲットデータを抽出する工程と、ターゲットデータと取出したテーブルに含まれる複数組のデータの各リファレンスデータとを比較する工程と、ターゲットデータと一致したリファレンスデータに対応した参照先テーブルデータ及びフラグデータを選択する工程と、選択した参照先テーブルデータをアドレスデータとして利用してメモリから選択した参照先テーブルデータに対応したテーブルを出力する工程とを有する。
2004088539.tif 000002
【特許請求の範囲】
【請求項１】
検索対象のストリームデータからキーワードを検出するための構文解析方法において、
メモリに、前記キーワードに対応したリファレンスデータと、前記リファレンスデータに対応した参照先テーブルデータ及びフラグデータとから構成される１組のデータを複数組含むテーブルをアドレスデータに対応させて複数個用意する工程と、
前記メモリから１つのテーブルを取出す工程と、
前記ストリームデータからターゲットデータを抽出する工程と、
前記ターゲットデータと取出したテーブルに含まれる複数組のデータの各リファレンスデータとを比較する工程と、
前記ターゲットデータと一致したリファレンスデータに対応した参照先テーブルデータ及びフラグデータを選択する工程と、
選択した参照先テーブルデータをアドレスデータとして利用して、前記メモリから選択した参照先テーブルデータに対応したテーブルを出力する工程とを有し、
前記抽出工程、前記比較工程、前記選択工程及び前記出力工程を、前記ストリームデータを構成するデータを順次新たなターゲットデータとして抽出しながら、繰返し行うことによって前記ストリームデータから前記キーワードを検出することを特徴とする構文解析方法。
【請求項２】
前記フラグデータが、前記ストリームデータに前記キーワードが含まれるか否かを示す請求項１に記載の構文解析方法。
【請求項３】
前記メモリには、複数のキーワードに対応した、リファレンスデータ、フラグデータ及び参照先テーブルデータとから構成される１組のデータが用意される請求項１に記憶の構文解析方法。
【請求項４】
ストリームデータからプログラム設定可能なキーワードを検出するためのプログラマブル・プロセッサ・ユニットにおいて、
前記ストリームデータから抽出されたターゲットデータを記憶するレジスタと、
前記キーワードに対応したリファレンスデータと、前記リファレンスデータに対応した参照先テーブルデータ及びフラグデータとから構成される１組のデータを複数組有するテーブルを複数個記憶し、アドレスデータの入力に応じて前記アドレスデータに対応したテーブルを出力するメモリと、
前記メモリから１つのテーブルセットが有する複数組のデータを入力して、前記ターゲットデータと前記複数組のデータの各リファレンスデータとを比較し、一致した場合に、一致したリファレンスデータに対応した参照先テーブルデータ及びフラグデータを選択し、選択した参照先テーブルデータに対応したテーブルを前記メモリから入力するために、前記選択した参照先テーブルデータをアドレスデータとして出力する処理回路とを有することを特徴とするプログラマブル・プロセッサ・ユニット。
【請求項５】
前記１組のデータは更に有効バイトデータを有し、前記処理回路は、前記有効バイトデータが有効を示しているリファレンスデータが前記ターゲットデータと一致した場合に限り、前記一致したリファレンスデータに対応したフラグデータ及び参照先テーブルデータを選択する請求項４に記載のプログラマブル・プロセッサ・ユニット。
【請求項６】
前記フラグデータが、前記ストリームデータに前記キーワードが含まれるか否かを示す請求項４に記載のプログラマブル・プロセッサ・ユニット。
【請求項７】
前記メモリには、複数のキーワードに対応した、リファレンスデータ、参照先テーブルデータ及びフラグデータとから構成される１組のデータが記憶されている請求項４に記載のプログラマブル・プロセッサ・ユニット。
【発明の詳細な説明】
【技術分野】  本発明は、ＭＰＥＧなどのメディア・データ、多重化されたバイナリ・ストリームデータ及び文字列等のストリームデータから、所望のキーワードを探し出すための構文解析方法に関し、特に高速に処理を行うことができる構文解析方法にする。さらに本発明は、そのような構文解析のためのプログラマブル・プロセッサ・ユニットに関する。
【背景技術】  従来の構文解析では、検索を行いたいキーワードを一つ取出し、キーワードと検索対象のストリームデータとを、ストリームデータの先頭から最後に渡って比較していた。そして、一つのキーワードとストリームデータとの比較が終了すると、次のキーワードに関して次の比較を行うというように、処理を繰り返していた。
図１３を用いて、従来の構文解析方法の手順について説明する。図１３において、検索対象のストリームデータ１３００（ｃａｂｃｄｅａａ・・・）が、バッファに格納されているものとする。また、検索したいキーワード１３１０（「ａｂｃｄ」、「ｃａｄ」、「ｃａｅ」及び「ｃｄ」）も、同様にバッファに格納されているものとする。最初に、キーワード「ａｂｃｄ」を取出し、検索１回目１３２０に示す様に、ストリームデータ１３００の先頭から順に比較を行っていく。図１３の例では、ストリームデータ１３００の２文字目から５文字目と、キーワード「ａｂｃｄ」が一致している。引き続き、一致した事を何らかの手段によって保持しながら、ストリームデータ１３００の６文字目から最後まで比較を行う。このようにして検索１回目１３２０を終了する。
次に、キーワード「ｃａｄ」を取出し、検索２回目１３３０に示す様に、ストリームデータ１３００の先頭から順に比較を行っていく。さらに、検索３回目１３４０、検索４回目１３５０の順で、キーワード１３１０の個数分だけ比較を継続して、全ての検索処理を終了する。
このような比較を高速に行う手法として、ハッシュ法がある。ハッシュ法とは、文字列からなる集合の要素からこの要素の格納場所のアドレスを求める関数（ハッシュ関数）を定義し、ハッシュ関数によって求められたアドレスをテーブルに格納するようにした方法である。ハッシュ法を利用した従来例が特開平４−９６１７４号公報に記載されている。その従来例では、候補文字列の読出し手段と一致検索手段とを独立して動作するように構成して、比較の高速化を図っている。
しかしながら、従来の構文解析では、比較を行うキーワードが複数ある場合に、キーワードの数に比例して検索時間が増大してしまうという問題があった。また、検索対象のストリームデータが全て揃っていないと、構文解析を始められないという問題もあった。さらに、キーワードは通常固定されて設定されており、容易に変更することができないという問題もあった。
発明の要約
そこで、本発明は、予め登録し且つテーブル展開しておいた全てのキーワードに対して、ストリームデータから抽出されたターゲットデータとの比較を並行して行い、キーワードが複数あっても高速に検索することができる構文解析方法及びそのような構文解析のためのプログラマブル・プロセッサ・ユニットを提供することを目的とする。
また、本発明は、検索対象のストリームデータが全て揃っていなくても検索を行うことができる構文解析方法及びそのような構文解析のためのプログラマブル・プロセッサ・ユニットを提供することを目的とする。
上記目的を達成するために、本発明に係る構文解析方法は、メモリにキーワードに対応したリファレンスデータとリファレンスデータに対応した参照先テーブルデータ及びフラグデータとから構成される１組のデータを複数組含むテーブルをアドレスデータに対応させて複数個用意する工程と、メモリから１つのテーブルを取出す工程と、ストリームデータからターゲットデータを抽出する工程と、ターゲットデータと取出したテーブルに含まれる複数組のデータの各リファレンスデータとを比較する工程と、ターゲットデータと一致したリファレンスデータに対応した参照先テーブルデータ及びフラグデータを選択する工程と、選択した参照先テーブルデータをアドレスデータとして利用してメモリから選択した参照先テーブルデータに対応したテーブルを出力する工程とを有し、抽出工程、比較工程、選択工程及び出力工程を、ストリームデータを構成するデータを順次新たなターゲットデータとして抽出しながら、繰返し行うことによってストリームデータからキーワードを検出することを特徴とする。
本発明に係る構文解析方法では、ストリームデータから１データずつをターゲットデータとして抽出し、メモリ上にテーブル展開されたキーワードとの比較を順次行っていくので、検索対象のストリームデータが最後まで揃っていない場合でも、ストリームデータの先頭から存在する分だけでも構文解析に着手することができる。また、検索対象のストリームデータが途中で追加されても、容易に構文解析を再開又は続行することができる。さらに、検索したいキーワードが複数ある場合でも、メモリ上に全てのキーワードをテーブル展開することによって、全てのキーワードの検索を同時並行的に処理することができる。
また、上記目的を達成するために、本発明に係るプログラマブル・プロセッサ・ユニットは、ストリームデータから抽出されたターゲットデータを記憶するレジスタと、キーワードに対応したリファレンスデータとリファレンスデータに対応した参照先テーブルデータ及びフラグデータとから構成される１組のデータを複数組有するテーブルセットを複数記憶し、アドレスデータの入力に応じてアドレスデータに対応したテーブルセットを出力するメモリと、メモリから１つのテーブルセットが有する複数組のデータを入力して、ターゲットデータと複数組のデータの各リファレンスデータとを比較し、一致した場合に、一致したリファレンスデータに対応した参照先テーブルデータ及びフラグデータを選択し、選択した参照先テーブルデータに対応したテーブルセットをメモリから入力するために、選択した参照先テーブルデータをアドレスデータとして出力する処理回路とを有することを特徴とする。
本発明に係るプログラマブル・プロセッサ・ユニットは、前述した本発明に係る構文解析方法を実現するためのユニットである。また、検索したいキーワードをプログラム設定可能としたので、入来するストリームデータの仕様に応じて、キーワードを容易に変更することが可能となる。また、検索したいキーワードが複数ある場合でも、全てのキーワードの検索を同時並行的に処理することができる。
【図面の簡単な説明】  図１は、本発明に係わる構文解析方法の全体の手順を示すフローチャートである。
図２は、キーワードのテーブル展開の手順を説明するための図である。
図３は、テーブル展開されたデータの一例を示す図である。
図４は、データストリームの検索の手順の概略を説明するための図である。
図５は、データストリームの検索の一例を示す図である。
図６は、データストリームの検索の一例を示す図である。
図７は、データストリームの検索の一例を示す図である。
図８は、データストリームの検索の一例を示す図である。
図９は、データストリームの検索の一例を示す図である。
図１０は、メモリに格納されるテーブルの一例を示す図である。
図１１は、本発明に係るプログラマブル・プロセッサ・ユニットの概略構成を示す図である。
図１２は、図１１に示す処理回路の概略回路構成を示す図である。
図１３は、従来の構文解析方法を説明するための図である。
【発明を実施するための最良の形態】  図１は、本発明に係る構文解析方法の手順を示すフローチャートである。本発明に係る構文解析方法では、検索対象となるデータストリームから、予めテーブル展開されたキーワードの検索を行い、検索結果を出力することができるように構成されている。
以下に、データストリームとして以下の８通りの文字が使用されている文字列を用い、４種類のキーワード（「ａｂｃｄ」、「ｃａｄ」、「ｃａｅ」及び「ｃｄ」）の検索を行う場合を例にして説明を行う。
文字コード                ｄａｔａ
００００                  ａ
０００１                  ｂ
０００２                  ｃ
０００３                  ｄ
０００４                  ｅ
０００５                  ｆ
０００６                  ｇ
０００７                  ｈ
最初に、テーブルの総数、ポインタ配列の深さを定義し、テーブルの初期化を行う（ステップ１０１）。ここでは、テーブル総数は６、ポインタ配列の深さＮ＝１０に設定した。
次に、登録するキーワードの総数を定義し、キーワードの初期化を行う（ステップ１０２）。ここでは、キーワードの総数を４に設定した。
次に、検索を行うキーワードを一つずつ登録し、テーブル展開する（ステップ１０３）。図２に、キーワード「ｃａｅ」を登録し、テーブル展開を行う例を示す。
図２では、キーワード「ａｂｃｄ」は既に登録されているものとする。キーワード「ａｂｃｄ」の登録により、先頭文字テーブル２００、２番目の文字テーブル２１０、３番目の文字テーブル２２０及び４番目の文字テーブル２３０が作成されている。各テーブルには、図示されるようなアドレスデータが対応しており、リファレンスデータ、参照先テーブルデータ及びフラグデータから構成される１組のデータを複数含んでいる。また、リファレンスデータは、検索対象の文字列を構成している８種の文字に対応している。なお、各テーブルにおいて、参照先テーブルデータの初期値は［０ｘ００００］、またフラグデータの初期値は［ｕｎｍａｔｃｈ］に設定されている。
まず、先頭文字テーブル２００において、キーワード「ｃａｅ」の先頭文字に応じて、リファレンスデータ「ｃ」に対応する参照先テーブルデータを［０ｘ０００４］に変更し、リファレンスデータ「ｃ」に対応するフラグデータを［ｃｏｎｔｉｎｕｅ］に変更する。
次に、キーワード「ｃａｅ」の２番目の文字及び参照先テーブルデータの［０ｘ０００４］に対応して、新たに２番目の文字テーブルとして２４０を作成する。さらに、２番目のテーブル２４０のリファレンスデータ「ａ」に対応する参照先テーブルデータを［０ｘ０００５］に変更し、リファレンスデータ「ａ」に対応するフラグデータを［ｃｏｎｔｉｎｕｅ］に変更する。
次に、キーワード「ｃａｅ」の３番目の文字及び参照先テーブルデータの［０ｘ０００５］に対応して、新たに３番目の文字テーブルとして２５０を作成する。さらに、３番目のテーブル２５０のリファレンスデータ「ｅ」に対応するフラグデータを［ｍａｔｃｈ］に変更して、キーワード「ｃａｅ」の登録を完了する。
同様に、キーワード「ｃａｅ」及び「ｃｄ」の登録を行う。全てのキーワードの登録及びテーブル展開を完了した後の複数のテーブルセットを図３に示す。図３に示す複数のテーブルセットは、先頭文字テーブル３００、２番目の文字テーブル３１０及び３４０、３番目の文字テーブル３２０及び３４０、４番目の文字テーブル３５０から構成されている。
次に、全てのキーワードの登録及びテーブル展開を完了した後の複数のテーブルセットの表示を適当なディスプレイ上で行う（ステップ１０４）。複数のテーブルセットの表示は、デバックのためのものであり、不必要な場合には省略することも可能である。
次に、検索対象の文字列からキーワードの検索を実行する（ステップ１０５）。図４に、検索の手順の概略を示す。ここでは、検索対象の文字列が「ｃａｂｃｄｅ・・・」であるものとする。最初に、検索対象の文字列から最初の一文字「ｃ」をターゲットデータとして抽出し、「ｃ」と４つのキーワードの最初の一文字目との比較を行う（４０１）。ターゲットデータ「ｃ」とキーワード「ｃａｄ」、「ｃａｅ」及び「ｃｄ」の一文字目が一致するので、これらのキーワードは継続したものとする。
次に、検索対象の文字列の次の一文字「ａ」をターゲットデータとして抽出し、「ａ」と４つのキーワードとの比較を行う（４０２）。ターゲットデータ「ａ」とキーワード「ｃａｄ」及び「ｃａｅ」の２文字目が一致するので、これらのキーワードは継続したものとする。また、キーワード「ｃｄ」の２文字目は「ａ」でないので、これらは一致しない。さらに、ターゲットデータ「ａ」とキーワード「ａｂｃｄ」の一文字目が一致するので、このキーワードは継続したものとする。
次に、検索対象の文字列の次の一文字「ｂ」をターゲットデータとして抽出し、「ｂ」と４つのキーワードとの比較を行う（４０３）。ターゲットデータ「ｂ」とキーワード「ａｂｃｄ」の２文字目が一致するので、このキーワードは継続しているものとする。また、キーワード「ｃａｄ」及び「ｃａｅ」の３文字目は「ｂ」でないので、これらは一致しない。
次に、検索対象の文字列の次の一文字「ｃ」をターゲットデータとして抽出し、「ｃ」と４つのキーワードとの比較を行う（４０４）。ターゲットデータ「ｃ」とキーワード「ａｂｃｄ」の３文字目は一致するので、このキーワードは継続したものとする。さらに、ターゲットデータ「ｃ」とキーワード「ｃａｄ」、「ｃａｅ」及び「ｃｄ」の一文字目は一致するので、これらのキーワードは継続したものとする。
次に、検索対象の文字列の次の一文字「ｄ」をターゲットデータとして抽出し、「ｄ」と４つのキーワードとの比較を行う（４０５）。ターゲットデータ「ｄ」とキーワード「ａｂｃｄ」の４文字目は一致するので、このキーワードは文字列中に検出されたものとする。また、キーワード「ｃａｄ」及び「ｃａｅ」の２文字目は「ｄ」でないので、これらのキーワードは一致しない。さらに、キーワード「ｃｄ」の２文字目は「ｄ」であるが、キーワード「ａｂｃｄ」が一致しているので、キーワード「ｃｄ」は無効とする。
このようにして、検索対象の文字列から一文字ずつ抽出して、全てのキーワードとの比較を同時並行的に行う処理を、検索対象の文字列の全てについて行う。
次に、図５〜図９を用いて、上述した検索処理を、複数のテーブルセットとポインタを用いてどのように実行するかを説明する。
最初に、検索対象の文字列からターゲットデータとして「ｃ」を取出して比較を行う（図５参照）。まず、ポインタの０階層に初期設定されている［０ｘ００００］に基づいてテーブル３００を選択して（５０１）、ターゲットデータ「ｃ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ｃ」のフラグデータが［ｃｏｎｔｉｎｕｅ］であるので、参照先テーブルデータ［０ｘ０００４］をポインタに格納する（５０２）。したがって、最初のターゲットデータ「ｃ」との比較後には、ポインタは、ポインタ（後）３７０のように設定されている。なお、ポインタの最下位層には、常に［０ｘ００００］が設定される。
次に、検索対象の文字列から次のターゲットデータ「ａ」を取出して、比較を行う（図６参照）。この時ポインタは、図５の結果からポインタ（前）３６０のように設定されている。まず。ポインタの第０階層に設定されている［０ｘ０００４］に基づいてテーブル３４０を選択して（６０１）、ターゲットデータ「ａ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ａ」のフラグデータが［ｃｏｎｔｉｎｕｅ］であるので、参照先テーブルデータ［０ｘ０００５］をポインタに格納する（６０２）。次に、ポインタの第１階層に設定されている［０ｘ００００］に基づいてテーブル３００を選択して（６０３）、ターゲットデータ「ａ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ａ」のフラグデータが［ｃｏｎｔｉｎｕｅ］であるので、参照先テーブルデータ［０ｘ０００１］をポインタに格納する（６０４）。したがって、ターゲットデータ「ａ」との比較後には、ポインタは、ポインタ（後）３７０のように設定されている。
次に、検索対象の文字列から次のターゲットデータ「ｂ」を取出して、比較を行う（図７参照）。この時ポインタは、図６の結果からポインタ（前）３６０のように設定されている。まず。ポインタの第０階層に設定されている［０ｘ０００５］に基づいてテーブル３５０を選択して（７０１）、ターゲットデータ「ｂ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ｂ」のフラグデータが［ｕｎｍａｔｃｈ］であるので、ポインタへの格納はしない。次に、ポインタの第１階層に設定されている［０ｘ０００１］に基づいてテーブル３１０を選択して（７０２）、ターゲットデータ「ｂ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ａ」のフラグデータが［ｃｏｎｔｉｎｕｅ］であるので、参照先テーブルデータ［０ｘ０００２］をポインタに格納する（７０３）。次に、ポインタの第２階層に設定されている［０ｘ００００］に基づいてテーブル３００を選択して（７０４）、ターゲットデータ「ｂ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ｂ」のフラグデータが［ｕｎｍａｔｃｈ］であるので、ポインタへの格納はしない。したがって、ターゲットデータ「ｂ」との比較後には、ポインタは、ポインタ（後）３７０のように設定されている。
次に、検索対象の文字列から次のターゲットデータ「ｃ」を取出して、比較を行う（図８参照）。この時ポインタは、図７の結果からポインタ（前）３６０のように設定されている。まず、ポインタの第０階層に設定されている［０ｘ０００２］に基づいてテーブル３２０を選択して（８０１）、ターゲットデータ「ｃ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ｃ」のフラグデータが［ｃｏｎｔｉｎｕｅ］であるので、参照先テーブルデータ［０ｘ０００３］をポインタに格納する（８０２）。次に、ポインタの第１階層に設定されている［０ｘ００００］に基づいてテーブル３００を選択して（８０３）、ターゲットデータ「ｃ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ｃ」のフラグデータが［ｃｏｎｔｉｎｕｅ］であるので、参照先テーブルデータ［０ｘ０００４］をポインタに格納する（８０４）。したがって、ターゲットデータ「ｃ」との比較後には、ポインタは、ポインタ（後）３７０のように設定されている。
次に、検索対象の文字列から次のターゲットデータ「ｄ」を取出して、比較を行う（図９参照）。この時ポインタは、図８の結果からポインタ（前）３６０のように設定されている。まず。ポインタの第０階層に設定されている［０ｘ０００３］に基づいてテーブル３３０を選択して（９０１）、ターゲットデータ「ｄ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ｄ」のフラグデータが［ｍａｔｃｈ］であるので、キーワード「ａｂｃｄ」が検出されたことが判別される。次に、ポインタの第１階層に設定されている［０ｘ０００４］に基づいてテーブル３４０を選択して（９０２）、ターゲットデータ「ｄ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ｄ」のフラグデータが［ｍａｔｃｈ］であるが同レベルでキーワード「ａｂｃｄ」が検出されていることから、キーワード「ｃｄ」の検出を無効とする。次に、ポインタの第２階層に設定されている［０ｘ００００］に基づいてテーブル３００を選択して（９０３）、ターゲットデータ「ｄ」とリファレンスデータ「ａ」〜「ｆ」を比較し、一致したリファレンスデータ「ｄ」のフラグデータが［ｕｎｍａｔｃｈ］であるので、ポインタへの格納はしない。したがって、ターゲットデータ「ｄ」との比較後には、ポインタは、ポインタ（後）３７０のように設定されている。
このようにして、検索対象の文字列から１文字ずつターゲットデータを抽出しながら、検索対象の文字列の最後まで、キーワードとの比較を行っていく。したがって、本発明に係る構文解析方法では、検索対象の文字列が最後まで揃っていない場合でも、文字列の先頭から存在する分だけでも構文解析に着手することができる。また、検索対象の文字列が途中で追加されても、容易に構文解析を再開又は続行することができる。さらに、検索したいキーワードが複数ある場合でも、全てのキーワードの検索を同時並行的に処理することができる。
次に、図１０〜１２を用いて、前述した本発明に係る構文解析方法を効率良く実現するためのプログラマブル・プロセッサ・ユニットについて説明を行う。
図１０に、本発明に係るプログラマブル・プロセッサ・ユニット１０００の概略を示す。なお、図１０に示すプログラマブル・プロセッサ・ユニット１０００は、一例であって、これに限定されるものでは無い。図示されるように、プログラマブル・プロセッサ・ユニット１０００は、処理回路１００２、ターゲットレジスタ１００４、遅延回路１００６及びメモリ１００８から構成されている。
プログラマブル・プロセッサ・ユニット１０００では、検索対象の文字列１０１０がターゲットレジスタ１００４に入力され、一文字ずつターゲットデータ１０１２として処理回路１００２に入力される。処理回路１００２では、ＮＥＸＴアドレス信号１０１４を出力して遅延回路１００６に一次記憶させる。また、所定のタイミングでアドレス信号１０１６がメモリ１００８に入力される。メモリ１００８には後述する複数のテーブルセットが予め記憶され、アドレス信号１０１６に対応したテーブルセットに含まれる複数組のデータ１０１８（リファレンスデータ［ｎ］、参照先テーブルデータ［ｎ］、有効バイトデータ［ｎ］及びフラグデータ［ｎ］）が処理回路１００２に入力される。処理回路１００２では、前述した構文解析方法に基づく理論に従って、ターゲットデータ１０１２及びテーブルセットに含まれる複数組のデータ１０１８を用いて、ＮＥＸＴアドレス信号１０１４及びフラグデータ１０２０を出力するように構成されている。
次に、メモリ１００８に記憶されている複数のテーブルセットについて説明する。複数のテーブルセットは、前述した図３に示されるような６つのテーブルセット３００〜３５０であって良い。しかしながら、利用しない項目を圧縮して、図１１に示すようなテーブルセットを作成することもできる。図１１において、テーブルセット例１１００は、アドレスデータ１１０２、リファレンスデータ１１０４、参照先テーブルデータ１１０６、有効バイトデータ１１０８及びフラグデータ１１１０から構成されている。なお、有効バイトデータ１１０８は、対応するリファレンスデータの比較が必要か否かを示すデータである。
図１１に示すテーブルセットを利用すれば、一度に処理する組データ（リファレンスデータ［ｎ］、参照先テーブルデータ［ｎ］、有効バイトデータ［ｎ］及びフラグデータ［ｎ］）は、４組ずつで良くなり、ハードウエアの構成を簡素化することが可能となる。
次に、処理回路１００２の回路構成の概略を図１２に示す。図１２に示す処理回路１００２は、図１１に示すテーブルセット１１００を利用した場合に適合しており、一度に４つの組データを処理することができる。
処理回路１００２の主要部は、図１２に示すように、アドレスデコーダ１２００、コンパレータ１２０２、１２０８、１２１４及び１２２０、インバータ１２０４、１２１０、１２１６及び１２２２、ＯＲ回路１２０６、１２１２、１２１８及び１２２４、プライオリティ・エンコーダ１２２６、第１出力バッファ１２２８、及び第２出力バッファ１２３０から構成される。処理回路１００２は、有効バイトが１ビットの場合に４リファレンスデータを同時比較する理論に基づいて構成されている。
処理回路１００２は、メモリ１００８からアドレスデータに対応した４つの組データ（リファレンスデータ［ｎ］、参照先テーブルデータ［ｎ］、有効バイトデータ［ｎ］及びフラグデータ［ｎ］）を同時に参照する。図１２において、参照した４つの組データを１２４０として示す。
各行のリファレンスデータ［０］〜［３］は、アドレスデコーダ１２００によってデコードされてコンパレータ１２０２、１２０８、１２１４及び１２２０に入力されて、ターゲットデータと比較される。デコードされたリファレンスデータがターゲットデータと一致する場合には、ハイレベルがコンパレータから出力されるように構成されている。
各行の有効バイトデータ［０］〜［３］は、デコードされて、インバータ１２０４、１２１０、１２１６及び１２２２にそれぞれ入力される。したがって、有効バイトデータが”ｖａｌｉｄ”の場合は各インバータからはローベルが出力され、有効バイトデータが”ｉｎｖａｌｉｄ”の場合は各インバータからはハイベルが出力される。
各参照先テーブルデータ［０］〜［３］は、第１の出力バッファ１２２８に格納され、各フラグデータ［０］〜［３］は、第２の出力バッファ１２３０に格納される。
インバータ出力がローベルの場合、ＯＲ回路は、コンパレータからの出力がハイレベルの場合にハイレベルの出力を行う。即ち、この場合、デコードされたリファレンスデータとターゲットデータが一致したこととなる。また、インバータ出力がハイレベルの場合、ＯＲ回路は、無条件でハイレベルの出力を行う。
プライオリティ・デコーダ１２２６は、ＯＲ回路からハイレベルの出力がなされた組の参照先テーブルデータを第１出力バッファ１２２８からｎｅｘｔアドレスデータ１０１４として出力し、同様にＯＲ回路からハイレベルの出力がなされた組のフラグデータを第２出力バッファからフラグデータ１０２０として出力する。
第１出力バッファから出力されたｎｅｘｔアドレスデータ１０１４は、遅延回路１００６で一旦保持され、次のシーケンスを待つこととなる。また次のシーケンスでは、次のターゲットデータにアップデートされて、同様の処理が行われる。なお、文字列の全てについての処理が完了するまで、シーケンスは繰り返される。このようにして、全文字列に対して、キーワードが存在するか否かの検索が行われる。
このようにストリームデータ中に予めメモリ１００８にテーブル展開されたキーワードが存在するか否かを高速に検索することが可能となった。特に、本プログラマブル・プロセッサ・ユニットを利用すれば、検索対象のストリームデータが最後まで揃っていない場合でも、先頭から存在する分だけでも構文解析に着手することができる。さらに、データストリームが途中で追加されても、容易に構文解析を再開又は続行することができる。さらに、検索したいキーワードが複数ある場合でも、全てのキーワードの検索を同時並行的に処理することができる。したがって、通信手段を用いて、ＭＰＥＧなどの画像データと制御データとが混在するストリームデータを順次受信している場合に、そのようなストリームデータから制御データのみを検索する場合等に特に本発明は有効である。
また、キーワードは容易にメモリ上にプログラム設定することができるので、予め複数グループのキーワードをテーブル展開してメモリ上に記憶させておき、入来するストリームデータに応じて、検索するキーワードを切替えることも可能である。
【図１】
2004088539.tif 000003
【図２】
2004088539.tif 000004
【図３】
2004088539.tif 000005
【図４】
2004088539.tif 000006
【図５】
2004088539.tif 000007
【図６】
2004088539.tif 000008
【図７】
2004088539.tif 000009
【図８】
2004088539.tif 000010
【図９】
2004088539.tif 000011
【図１０】
2004088539.tif 000012
【図１１】
2004088539.tif 000013
【図１２】
2004088539.tif 000014
【図１３】
2004088539.tif 000015
【国際調査報告】
2004088539.tif 000016
2004088539.tif 000017