(57)【要約】      （修正有）【課題】入力文字列の中から、キーワードを検出する装置において、キーワードの文字数が設計値より長い場合でも、処理性能の低下を抑える。【解決手段】キーワードを格納する記憶装置Ｄi,jと、入力文字列と記憶装置Ｄi,jに格納されているキーワードとの一致状態を表すフラグを記憶する記憶装置Ｍi,jとに対して、アドレスｉの格納領域から読み出しを行う処理と、記憶装置Ｄi,jのアドレスｉのｊ−１番目の文字とレジスタＸに格納された着目点の文字との一致判定の結果をレジスタｒのｊ番目に格納する処理と、記憶装置Ｄi,jのアドレスｉのＬ番目の文字とレジスタＸに格納された文字との一致判定の結果をレジスタｆに格納する処理と、レジスタｒの値に基づいてキーワードの検出結果を通知する処理と、記憶装置Ｍi,jのアドレスｉにレジスタｒの値を格納すると共に、レジスタＣにレジスタｆの値を格納する処理とを、クロックサイクル毎に行う。【選択図】図２
2017130075.tif 000002
【特許請求の範囲】
【請求項１】
入力文字列の中から、記憶装置にキーワードとして収録されている文字列を検出するキーワードの検出装置において、
入力文字列の先頭から順番に着目点の１文字をＳクロックサイクル毎（Ｓは３以上の整数）に取得する入力手段と、
１つのアドレスｉあたりの文字数単位が固定値Ｌ（Ｌは３以上の整数）の格納領域にキーワードを格納する記憶装置Ｄと、
前記入力文字列と前記記憶装置Ｄのアドレスｉで特定される格納領域に格納されているキーワードとの一致状態を表すフラグを、前記記憶装置Ｄに対応してアドレスｉ毎にＬビット分記憶する記憶装置Ｍと、
この記憶装置Ｍの値の更新のためにあらかじめ準備される値を保持するレジスタｒと、
前記記憶装置ＤのアドレスｉのＬ番目の格納領域に格納されている前記キーワードの文字と前記着目点の文字とが一致したことを表すフラグを一時的に保持するレジスタＣと、
このレジスタＣが次のクロックサイクルに持つべき値を保持するレジスタｆと、
前記記憶装置Ｄ，Ｍおよび前記レジスタｒ，ｆ，Ｃの値の読み書きを制御する制御手段と、
前記レジスタｒの値に基づいてキーワードの検出結果を通知する通知手段とを備え、
前記制御手段は、
（Ｓ＋１）クロックサイクルで先頭の値に戻るように一巡するアドレスｉで特定される前記記憶装置Ｄ，Ｍの格納領域から読み出しを行う読出処理と、
アドレスｉが先頭の値の場合は、前記レジスタｒの１番目の値を任意の値とすると共に、前記記憶装置Ｄのアドレスｉの１番目に前記キーワードの先頭文字が格納され、かつこの先頭文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットし、アドレスｉが先頭の値でない場合は、前記レジスタＣの値を前記レジスタｒの１番目の値として格納すると共に、前記記憶装置Ｄのアドレスｉの１番目に前記キーワードの先頭文字が格納されているか、または前記記憶装置Ｍのアドレスｉの１番目のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉの１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットし、アドレスｉが先頭の値の場合または先頭の値でない場合のいずれにおいても、前記記憶装置Ｄのアドレスｉのｊ−１番目（ｊは３からＬまでの整数）に前記キーワードの先頭文字が格納されているか、または前記記憶装置Ｍのアドレスｉのｊ−１番目のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉのｊ−１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒのｊ番目のフラグをセットする第１の更新処理と、
前記記憶装置ＤのアドレスｉのＬ番目に前記キーワードの先頭文字が格納されているか、または前記記憶装置ＭのアドレスｉのＬ番目のフラグがセットされ、かつ前記記憶装置ＤのアドレスｉのＬ番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｆのフラグをセットする第２の更新処理と、
前記記憶装置Ｍのアドレスｉで特定される格納領域に前記レジスタｒの値を格納すると共に、前記レジスタＣに前記レジスタｆの値を格納する第３の更新処理とを、クロックサイクル毎に行うことを特徴とするキーワードの検出装置。
【請求項２】
請求項１記載のキーワードの検出装置において、
前記制御手段は、前記第１の更新処理の際に、アドレスｉが先頭の値で、前記レジスタＣのフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉの１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットすることを特徴とするキーワードの検出装置。
【請求項３】
請求項１または２記載のキーワードの検出装置において、
前記通知手段は、前記第１の更新処理後のレジスタｒのｎ＋１番目（ｎは１からＬ−１までの整数）のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉのｎ番目に前記キーワードの末尾文字が格納されているか、または前記第２の更新処理後のレジスタｆのフラグがセットされ、かつ前記記憶装置ＤのアドレスｉのＬ番目に前記キーワードの末尾文字が格納されているときに、前記記憶装置Ｄにキーワードとして収録されている文字列を検出したことを外部に通知する処理を、クロックサイクル毎に行うことを特徴とするキーワードの検出装置。
【請求項４】
請求項１乃至３のいずれか１項に記載のキーワードの検出装置において、
前記入力手段と前記レジスタｒと前記レジスタｆと前記レジスタＣと前記制御手段と前記通知手段とは、ＦＰＧＡによって構成されることを特徴とするキーワードの検出装置。
【請求項５】
入力文字列の中から、記憶装置にキーワードとして収録されている文字列を検出するキーワードの検出方法において、
入力文字列の先頭から順番に着目点の１文字をＳクロックサイクル毎（Ｓは３以上の整数）に取得する入力ステップと、
１つのアドレスｉあたりの文字数単位が固定値Ｌ（Ｌは３以上の整数）の格納領域にキーワードを格納する記憶装置Ｄと、前記入力文字列と前記記憶装置Ｄのアドレスｉで特定される格納領域に格納されているキーワードとの一致状態を表すフラグを、前記記憶装置Ｄに対応してアドレスｉ毎にＬビット分記憶する記憶装置Ｍとに対して、（Ｓ＋１）クロックサイクルで先頭の値に戻るように一巡するアドレスｉで特定される前記記憶装置Ｄ，Ｍの格納領域から読み出しを行う読出ステップと、
アドレスｉが先頭の値の場合は、レジスタｒの１番目の値を任意の値とすると共に、前記記憶装置Ｄのアドレスｉの１番目に前記キーワードの先頭文字が格納され、かつこの先頭文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットし、アドレスｉが先頭の値でない場合は、レジスタＣの値を前記レジスタｒの１番目の値として格納すると共に、前記記憶装置Ｄのアドレスｉの１番目に前記キーワードの先頭文字が格納されているか、または前記記憶装置Ｍのアドレスｉの１番目のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉの１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットし、アドレスｉが先頭の値の場合または先頭の値でない場合のいずれにおいても、前記記憶装置Ｄのアドレスｉのｊ−１番目（ｊは３からＬまでの整数）に前記キーワードの先頭文字が格納されているか、または前記記憶装置Ｍのアドレスｉのｊ−１番目のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉのｊ−１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒのｊ番目のフラグをセットする第１の更新ステップと、
前記記憶装置ＤのアドレスｉのＬ番目に前記キーワードの先頭文字が格納されているか、または前記記憶装置ＭのアドレスｉのＬ番目のフラグがセットされ、かつ前記記憶装置ＤのアドレスｉのＬ番目に格納された文字と前記着目点の文字とが一致したときにレジスタｆのフラグをセットする第２の更新ステップと、
前記レジスタｒの値に基づいてキーワードの検出結果を通知する通知ステップと、
前記記憶装置Ｍのアドレスｉで特定される格納領域に前記レジスタｒの値を格納すると共に、前記レジスタＣに前記レジスタｆの値を格納する第３の更新ステップとを含み、
前記読出ステップと前記第１の更新ステップと前記第２の更新ステップと前記通知ステップと前記第３の更新ステップとをクロックサイクル毎に行うことを特徴とするキーワードの検出方法。
【請求項６】
請求項５記載のキーワードの検出方法において、
前記第１の更新ステップは、アドレスｉが先頭の値で、前記レジスタＣのフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉの１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットするステップを含むことを特徴とするキーワードの検出方法。
【請求項７】
請求項５または６記載のキーワードの検出方法において、
前記通知ステップは、前記第１の更新ステップ後のレジスタｒのｎ＋１番目（ｎは１からＬ−１までの整数）のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉのｎ番目に前記キーワードの末尾文字が格納されているか、または前記第２の更新ステップ後のレジスタｆのフラグがセットされ、かつ前記記憶装置ＤのアドレスｉのＬ番目に前記キーワードの末尾文字が格納されているときに、前記記憶装置Ｄにキーワードとして収録されている文字列を検出したことを外部に通知するステップを含むことを特徴とするキーワードの検出方法。
【請求項８】
請求項５乃至７のいずれか１項に記載のキーワードの検出方法において、
前記入力ステップと前記読出ステップと前記第１の更新ステップと前記第２の更新ステップと前記通知ステップと前記第３の更新ステップとは、ＦＰＧＡによって実行されることを特徴とするキーワードの検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力文字列の中から、記憶装置にキーワードとして収録されている文字列を検出するキーワードの検出装置および検出方法に関するものである。
【背景技術】
【０００２】
入力文字列の中から、辞書にキーワード（パタン、あるいは辞書見出し語などと表現される）として収録されている文字列を検出するキーワードの検出装置においては、あらかじめ設計時にキーワードの最長文字数を考慮して、用意される記憶装置を、キーワードを登録できる予定の規模に分割していた（非特許文献１、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Yusuke Sekihara et al.，“A study of a real-time keyword matching process targeting Twitter data.”，International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies(HEART)，2015
【非特許文献２】Kanak Agarwal et al.，“A high-speed and large-scale dictionary matching engine for Information Extraction systems”，Application-Specific Systems,Architectures and Processors(ASAP)，2013
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来のキーワードの検出装置は、非特許文献１に開示されているように、キーワードの最長文字数に基づいて設計がなされるものであった。そのため、設計上、キーワードの最長の文字数を規定する必要があり、その文字数を超えるキーワードについては、キーワードを分割して、分割した文字列毎に入力文字列とのキーワードマッチングを行った上で状態遷移による論理積演算を行う等、別途の処理によって入力文字列中にキーワードが出現するかどうかを検出する必要があった。しかしながら、このような処理はサービス全体としては処理性能の低下につながるので、必要に応じて装置を再設計しなければならない可能性があった。
【０００５】
また、従来のキーワードの検出装置では、記憶装置に収録されているキーワードの中に最長の文字数に満たないキーワードが多い場合には、活用されない記憶要素が多くなり、記憶装置の容量に対する無駄が多くなるという課題があった。また、従来のキーワードの検出装置では、記憶装置の最後の格納領域から最初の格納領域にわたってキーワードを格納することは不可能であった。
【０００６】
本発明は、上記課題を解決するためになされたもので、キーワードの文字数が設計値より長い場合でも、処理性能の低下を抑えることができるキーワードの検出装置および検出方法を提供することを目的とする。
また、本発明は、記憶装置の最後の格納領域から最初の格納領域にわたってキーワードを格納することが可能なキーワードの検出装置および検出方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、入力文字列の中から、記憶装置にキーワードとして収録されている文字列を検出するキーワードの検出装置において、入力文字列の先頭から順番に着目点の１文字をＳクロックサイクル毎（Ｓは３以上の整数）に取得する入力手段と、１つのアドレスｉあたりの文字数単位が固定値Ｌ（Ｌは３以上の整数）の格納領域にキーワードを格納する記憶装置Ｄと、前記入力文字列と前記記憶装置Ｄのアドレスｉで特定される格納領域に格納されているキーワードとの一致状態を表すフラグを、前記記憶装置Ｄに対応してアドレスｉ毎にＬビット分記憶する記憶装置Ｍと、この記憶装置Ｍの値の更新のためにあらかじめ準備される値を保持するレジスタｒと、前記記憶装置ＤのアドレスｉのＬ番目の格納領域に格納されている前記キーワードの文字と前記着目点の文字とが一致したことを表すフラグを一時的に保持するレジスタＣと、このレジスタＣが次のクロックサイクルに持つべき値を保持するレジスタｆと、前記記憶装置Ｄ，Ｍおよび前記レジスタｒ，ｆ，Ｃの値の読み書きを制御する制御手段と、前記レジスタｒの値に基づいてキーワードの検出結果を通知する通知手段とを備え、前記制御手段は、（Ｓ＋１）クロックサイクルで先頭の値に戻るように一巡するアドレスｉで特定される前記記憶装置Ｄ，Ｍの格納領域から読み出しを行う読出処理と、アドレスｉが先頭の値の場合は、前記レジスタｒの１番目の値を任意の値とすると共に、前記記憶装置Ｄのアドレスｉの１番目に前記キーワードの先頭文字が格納され、かつこの先頭文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットし、アドレスｉが先頭の値でない場合は、前記レジスタＣの値を前記レジスタｒの１番目の値として格納すると共に、前記記憶装置Ｄのアドレスｉの１番目に前記キーワードの先頭文字が格納されているか、または前記記憶装置Ｍのアドレスｉの１番目のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉの１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットし、アドレスｉが先頭の値の場合または先頭の値でない場合のいずれにおいても、前記記憶装置Ｄのアドレスｉのｊ−１番目（ｊは３からＬまでの整数）に前記キーワードの先頭文字が格納されているか、または前記記憶装置Ｍのアドレスｉのｊ−１番目のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉのｊ−１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒのｊ番目のフラグをセットする第１の更新処理と、前記記憶装置ＤのアドレスｉのＬ番目に前記キーワードの先頭文字が格納されているか、または前記記憶装置ＭのアドレスｉのＬ番目のフラグがセットされ、かつ前記記憶装置ＤのアドレスｉのＬ番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｆのフラグをセットする第２の更新処理と、前記記憶装置Ｍのアドレスｉで特定される格納領域に前記レジスタｒの値を格納すると共に、前記レジスタＣに前記レジスタｆの値を格納する第３の更新処理とを、クロックサイクル毎に行うことを特徴とするものである。
【０００８】
また、本発明のキーワードの検出装置の１構成例において、前記制御手段は、前記第１の更新処理の際に、アドレスｉが先頭の値で、前記レジスタＣのフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉの１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットすることを特徴とするものである。
また、本発明のキーワードの検出装置の１構成例において、前記通知手段は、前記第１の更新処理後のレジスタｒのｎ＋１番目（ｎは１からＬ−１までの整数）のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉのｎ番目に前記キーワードの末尾文字が格納されているか、または前記第２の更新処理後のレジスタｆのフラグがセットされ、かつ前記記憶装置ＤのアドレスｉのＬ番目に前記キーワードの末尾文字が格納されているときに、前記記憶装置Ｄにキーワードとして収録されている文字列を検出したことを外部に通知する処理を、クロックサイクル毎に行うことを特徴とするものである。
また、本発明のキーワードの検出装置の１構成例において、前記入力手段と前記レジスタｒと前記レジスタｆと前記レジスタＣと前記制御手段と前記通知手段とは、ＦＰＧＡによって構成されることを特徴とするものである。
【０００９】
また、本発明のキーワードの検出方法は、入力文字列の先頭から順番に着目点の１文字をＳクロックサイクル毎（Ｓは３以上の整数）に取得する入力ステップと、１つのアドレスｉあたりの文字数単位が固定値Ｌ（Ｌは３以上の整数）の格納領域にキーワードを格納する記憶装置Ｄと、前記入力文字列と前記記憶装置Ｄのアドレスｉで特定される格納領域に格納されているキーワードとの一致状態を表すフラグを、前記記憶装置Ｄに対応してアドレスｉ毎にＬビット分記憶する記憶装置Ｍとに対して、（Ｓ＋１）クロックサイクルで先頭の値に戻るように一巡するアドレスｉで特定される前記記憶装置Ｄ，Ｍの格納領域から読み出しを行う読出ステップと、アドレスｉが先頭の値の場合は、レジスタｒの１番目の値を任意の値とすると共に、前記記憶装置Ｄのアドレスｉの１番目に前記キーワードの先頭文字が格納され、かつこの先頭文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットし、アドレスｉが先頭の値でない場合は、レジスタＣの値を前記レジスタｒの１番目の値として格納すると共に、前記記憶装置Ｄのアドレスｉの１番目に前記キーワードの先頭文字が格納されているか、または前記記憶装置Ｍのアドレスｉの１番目のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉの１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒの２番目のフラグをセットし、アドレスｉが先頭の値の場合または先頭の値でない場合のいずれにおいても、前記記憶装置Ｄのアドレスｉのｊ−１番目（ｊは３からＬまでの整数）に前記キーワードの先頭文字が格納されているか、または前記記憶装置Ｍのアドレスｉのｊ−１番目のフラグがセットされ、かつ前記記憶装置Ｄのアドレスｉのｊ−１番目に格納された文字と前記着目点の文字とが一致したときに前記レジスタｒのｊ番目のフラグをセットする第１の更新ステップと、前記記憶装置ＤのアドレスｉのＬ番目に前記キーワードの先頭文字が格納されているか、または前記記憶装置ＭのアドレスｉのＬ番目のフラグがセットされ、かつ前記記憶装置ＤのアドレスｉのＬ番目に格納された文字と前記着目点の文字とが一致したときにレジスタｆのフラグをセットする第２の更新ステップと、前記レジスタｒの値に基づいてキーワードの検出結果を通知する通知ステップと、前記記憶装置Ｍのアドレスｉで特定される格納領域に前記レジスタｒの値を格納すると共に、前記レジスタＣに前記レジスタｆの値を格納する第３の更新ステップとを含み、前記読出ステップと前記第１の更新ステップと前記第２の更新ステップと前記通知ステップと前記第３の更新ステップとをクロックサイクル毎に行うことを特徴とするものである。
【発明の効果】
【００１０】
本発明によれば、レジスタｒに対する処理の結果（第１の更新処理の結果）を記憶装置Ｍに格納することで、この結果をＳクロックサイクル後に確認できるようにし、また記憶装置ＤのアドレスｉのＬ番目の文字と着目点の文字との一致判定の結果をレジスタｆに一旦格納した後に、レジスタＣにレジスタｆの値を格納することで、１サイクル前の結果を、記憶装置Ｄの次のアドレスｉの１番目の一致判定の際に確認できるようにしたので、キーワードの文字数と記憶装置Ｄの文字数単位Ｌの大小や、キーワードの格納位置によらず、入力文字列の中からキーワードを検出することができる。その結果、本発明では、キーワードの文字数が設計値（文字数単位Ｌ）より長い場合でも、処理性能の低下を抑えることができる。また、本発明では、キーワードの文字数が著しく短い場合を考慮して文字数単位Ｌを設定しても処理性能の低下を抑えることができるので、キーワードの文字数が文字数単位Ｌより短い場合の資源の損失を抑えることが可能となり、装置の再設計が必要になる可能性を低減することができる。
【００１１】
また、本発明では、レジスタｒに対する処理（第１の更新処理）の際に、アドレスｉが先頭の値で、レジスタＣのフラグがセットされ、かつ記憶装置Ｄのアドレスｉの１番目に格納された文字と着目点の文字とが一致したときにレジスタｒの２番目のフラグをセットすることにより、記憶装置Ｄの最後の格納領域から最初の格納領域にわたってキーワードを格納することを可能にすることができ、記憶装置Ｄへのキーワードの格納の制約を緩和することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施の形態に係るキーワードの検出装置の構成を示すブロック図である。
【図２】本発明の実施の形態に係るキーワードの検出装置の検出部の構成を示すブロック図である。
【図３】本発明の実施の形態に係るキーワードの検出装置の動作を説明するフローチャートである。
【図４】本発明の実施の形態に係るキーワードの検出装置におけるレジスタの準備処理を説明するフローチャートである。
【図５】本発明の実施の形態に係るキーワードの検出装置における検出処理を説明するフローチャートである。
【図６】本発明の実施の形態に係るキーワードの検出装置の記憶装置に格納された文字および値の例を示す図である。
【図７】本発明の実施の形態に係るキーワードの検出装置の動作を説明する図である。
【図８】本発明の実施の形態に係るキーワードの検出装置の動作を説明する図である。
【図９】本発明の実施の形態に係るキーワードの検出装置を実装する装置のブロック図である。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について図面を参照して説明する。図１は本発明の実施の形態に係るキーワードの検出装置の構成を示すブロック図である。キーワードの検出装置は、入力部１と、検出部２とを備えている。
入力部１は、入力文字列を１文字づつ出力し、検出部２に与える。入力文字列は、ファイル装置やキューなどによって与えられる文字の時系列である。
【００１４】
図２に検出部２の構成を示す。検出部２は、記憶装置Ｄi,j，Ｂi,j，Ｅi,j，Ｍi,jと、これら記憶装置Ｂi,j，Ｄi,j，Ｅi,j，Ｍi,jとの間の読み書きを行うレジスタｂ1〜ｂL，ｄ1〜ｄL，ｅ1〜ｅL，ｍ1〜ｍL，ｒ1〜ｒL，ｆ，Ｃ，Ｘと、その読み書きを制御する制御部２０と、キーワードの検出結果を通知する通知部２１とから構成される。
【００１５】
レジスタＸは、入力部１から与えられた文字を１文字格納する。記憶装置Ｄi,jは、キーワードを構成する文字列をあらかじめ記憶している。この記憶装置Ｄi,jは、キーワードの文字数に依存しない固定値Ｌ（Ｌは３以上の整数）の文字数単位のメモリである。１つのアドレスｉで特定される長さＬの格納領域に、１つのキーワードではなく、文字数Ｌより短いキーワードを複数格納することもできるし、文字数Ｌより長いキーワードを分割して格納することも可能である。
【００１６】
制御部２０は、記憶装置Ｄi,jのアドレスｉで特定される格納領域に対して長さＬの文字列を単位として読み書きを行う。ここで、ｊはこの長さＬの文字列のｊ番目の文字を示すための添え字である。
【００１７】
記憶装置Ｂi,jは、記憶装置Ｄi,jのアドレスｉの格納領域に格納されている長さＬの文字列中の各文字がキーワードの先頭文字か否かを表すフラグを、同アドレスｉで特定される格納領域にＬビット分記憶している。つまり、記憶装置Ｂi,jは、長さＬの文字列に対応する長さＬのビット列単位のメモリである。
【００１８】
制御部２０は、記憶装置Ｂi,jのアドレスｉで特定される格納領域に対して長さＬのビット列を単位として読み書きを行う。ここで、ｊはこの長さＬのビット列のｊ番目のビットを示すための添え字である。
【００１９】
記憶装置Ｅi,jは、記憶装置Ｄi,jのアドレスｉの格納領域に格納されている長さＬの文字列中の各文字がキーワードの末尾文字か否かを表すフラグを、同アドレスｉで特定される格納領域にＬビット分記憶している。記憶装置Ｂi,jと同様に、記憶装置Ｅi,jは、長さＬの文字列に対応する長さＬのビット列単位のメモリである。
【００２０】
制御部２０は、記憶装置Ｅi,jのアドレスｉで特定される格納領域に対して長さＬのビット列を単位として読み書きを行う。記憶装置Ｂi,jと同様に、ｊは長さＬのビット列のｊ番目のビットを示すための添え字である。
【００２１】
記憶装置Ｍi,jは、入力部１がレジスタＸを介して与える文字の時系列と記憶装置Ｄi,jのアドレスｉで特定される格納領域に格納されているキーワードとの一致状態を表すフラグを、アドレスｉ毎にＬビット分記憶している。各フラグは、キーワードの先頭文字から当該フラグに対応するキーワードの文字の１つ前の文字まで一致が継続していたことを表す。
【００２２】
制御部２０は、記憶装置Ｍi,jのアドレスｉで特定される格納領域に対して長さＬのビット列を単位として読み書きを行う。なお、以降の説明では、値が“１”の場合をフラグセット、“０”の場合をフラグリセットとして説明する。
【００２３】
レジスタｂ1〜ｂLは、制御部２０が記憶装置Ｂi,jから読み出した長さＬのビット列中のの各ビットを保持する。
レジスタｄ1〜ｄLは、制御部２０が記憶装置Ｄi,jから読み出した長さＬの文字列中の各文字を保持する。
レジスタｅ1〜ｅLは、制御部２０が記憶装置Ｅi,jから読み出した長さＬのビット列中の各ビットを保持する。
レジスタｍ1〜ｍLは、制御部２０が記憶装置Ｍi,jから読み出した長さＬのビット列中の各ビットを保持する。
【００２４】
レジスタｒ1〜ｒLは、記憶装置Ｍi,jの値の更新のためにあらかじめ準備される値を保持する。
レジスタＣは、クロックサイクルの度にレジスタｆの値によって更新される。レジスタＣの値は、レジスタｒ1〜ｒLのうち、特に１ビット目のレジスタｒ1および２ビット目のレジスタｒ2の値に影響を与える。詳細については後述する。
レジスタｆは、レジスタＣが次のクロックサイクルに持つべき値を保持する。
【００２５】
図３に本実施の形態のキーワードの検出装置の動作を説明するフローチャートを示す。キーワードの検出装置は、動作を開始すると、文字列の入力を待つ。例えばファイル装置から文字列が入力されると、入力部１は、入力文字列の先頭から順番に１文字取得して、取得した文字を検出部２に与える。検出部２から与えられた文字は、レジスタＸに格納される（図３ステップＳ１）。
【００２６】
検出部２の制御部２０は、レジスタＸに文字が格納されたことにより動作を開始し、検出部２の内部変数ｋを１に初期化する（図３ステップＳ２）。内部変数ｋは、１からＳ（Ｓは３以上の整数）までの値をとり得る。Ｓは、装置の固有値であるが、例えば、装置に設計上用意されている記憶装置Ｄi,jに格納可能な最大文字数を、Ｌで除算した商であると考えてよい。すなわち、記憶装置Ｄi,jは、長さＬの格納領域をＳ個備えていることになる。また、アドレスｉは、クロックサイクル毎に値が変わり、（Ｓ＋１）クロックサイクルで先頭の値に戻るように一巡する。
【００２７】
次に、制御部２０は、内部変数ｋに対応するアドレスｉで特定される記憶装置Ｂi,jの格納領域から長さＬのビット列を読み出し、このビット列中の各ビットをそれぞれレジスタｂ1〜ｂLに格納する（図３ステップＳ３）。
また、制御部２０は、アドレスｉで特定される記憶装置Ｄi,jの格納領域から長さＬの文字列を読み出し、この文字列中の各文字をそれぞれレジスタｄ1〜ｄLに格納する（図３ステップＳ３）。
【００２８】
また、制御部２０は、アドレスｉで特定される記憶装置Ｅi,jの格納領域から長さＬのビット列を読み出し、このビット列中の各ビットをそれぞれレジスタｅ1〜ｅLに格納する（図３ステップＳ３）。
さらに、制御部２０は、アドレスｉで特定される記憶装置Ｍi,jの格納領域から長さＬのビット列を読み出し、このビット列中の各ビットをそれぞれレジスタｍ1〜ｍLに格納する（図３ステップＳ３）。
【００２９】
次に、制御部２０は、記憶装置Ｍi,jのアドレスｉの格納領域を更新するための値としてレジスタｒ1〜ｒLに格納する値を準備し、またレジスタＣを更新するための値としてレジスタｆに格納する値を準備する（図３ステップＳ４）。このステップＳ４の処理の詳細を図４を用いて説明する。
【００３０】
まず、制御部２０は、内部変数ｋが１の場合（図４ステップＳ１０においてＴ）、レジスタｒ1の値を“０”または“１”のどちらか任意の値とし、またレジスタｒ2の値を次式のように設定する（図４ステップＳ１１）。
ｒ2＝ａｎｄ（ｏｒ（ｂ1，Ｃ），（ｄ1＝Ｘ））                     ・・・（１）
【００３１】
式（１）は、レジスタｂ1の値とレジスタＣの値の論理和をとり、この論理和の結果と、レジスタｄ1に格納された文字がレジスタＸに格納された文字と一致するかどうかの判定結果（一致であれば“１”（Ｔｒｕｅ）、不一致であれば“０”（Ｆａｌｓｅ））との論理積をとり、この論理積の結果をレジスタｒ2の値とすることを意味する。なお、レジスタｒ1の値を任意の値とする理由は、記憶装置Ｍi,jの、内部変数ｋ＝１に対応するアドレスｉの格納領域に格納されているｊ＝１番目の値は、レジスタｒ1〜ｒLやレジスタｆの値を決める際に参照されることがないからである。
【００３２】
また、制御部２０は、内部変数ｋが１でない場合（ステップＳ１０においてＦ）、レジスタＣの値をレジスタｒ1に格納し、またレジスタｒ2の値を次式のように設定する（図４ステップＳ１２）。
ｒ2＝ａｎｄ（ｏｒ（ｂ1，ｍ1），（ｄ1＝Ｘ））                    ・・・（２）
【００３３】
式（２）は、レジスタｂ1の値とレジスタｍ1の値の論理和をとり、この論理和の結果と、レジスタｄ1に格納された文字がレジスタＸに格納された文字と一致するかどうかの判定結果との論理積をとり、この論理積の結果をレジスタｒ2の値とすることを意味する。
【００３４】
さらに、制御部２０は、レジスタｒ3〜ｒLの値を設定すると共に、レジスタｆの値を設定する（図４ステップＳ１３）。レジスタｒ3〜ｒLの値は、内部変数ｋの値には依存せず、次式のように表すことができる（ここでは、ｊは３からＬまでの値）。
ｒj＝ａｎｄ（ｏｒ（ｂj-1，ｍj-1），（ｄj-1＝Ｘ））              ・・・（３）
【００３５】
式（３）は、レジスタｂj-1の値とレジスタｍj-1の値の論理和をとり、この論理和の結果と、レジスタｄj-1に格納された文字がレジスタＸに格納された文字と一致するかどうかの判定結果との論理積をとり、この論理積の結果をレジスタｒjの値とすることを意味する。
【００３６】
また、レジスタｆの値は、次式のように表すことができる。
ｆ＝ａｎｄ（ｏｒ（ｂL，ｍL），（ｄL＝Ｘ））                     ・・・（４）
【００３７】
式（４）は、レジスタｂLの値とレジスタｍLの値の論理和をとり、この論理和の結果と、レジスタｄLに格納された文字がレジスタＸに格納された文字と一致するかどうかの判定結果との論理積をとり、この論理積の結果をレジスタｆの値とすることを意味する。
以上で、図３のステップＳ４の処理が終了する。
【００３８】
次に、制御部２０は、記憶装置Ｄi,jにキーワードとして収録されている文字列を検出したかどうかの判定と、記憶装置Ｍi,jおよびレジスタＣの更新とを行う（図３ステップＳ５）。検出処理の詳細を図５を用いて説明する。
【００３９】
まず、制御部２０は、ビット番号ｎ＝１の場合について（図５ステップＳ２０）、ｎ＝Ｌが成立するかどうかを判定する（図５ステップＳ２１）。ここではｎ＝１，Ｌ＝４なので、制御部２０は、ａｎｄ（ｒn+1，ｅn）、すなわちレジスタｒn+1の値とレジスタｅnの値との論理積をとり（図５ステップＳ２２）、この論理積の結果が“１”であれば、記憶装置Ｄi,jにキーワードとして収録されている文字列を検出したことを通知部２１を介して外部に通知する（図５ステップＳ２３）。
【００４０】
ステップＳ２２またはＳ２３の処理終了後、制御部２０は、ビット番号ｎを１増やし（図５ステップＳ２６）、ビット番号ｎがＬより大きいかどうかを判定する（図５ステップＳ２７）。ビット番号ｎがＬ以下であれば、ステップＳ２１に戻る。次に、ビット番号ｎ＝Ｌになると（ステップＳ２１においてＴ）、制御部２０は、ａｎｄ（ｆ，ｅL）、すなわちレジスタｆの値とレジスタｅLの値との論理積をとり（図５ステップＳ２４）、この論理積の結果が“１”であれば、記憶装置Ｄi,jにキーワードとして収録されている文字列を検出したことを通知部２１を介して外部に通知する（図５ステップＳ２５）。ステップＳ２４またはＳ２５の処理終了後、制御部２０は、ビット番号ｎを１増やし（ステップＳ２６）、ビット番号ｎがＬより大きいかどうかを判定する（ステップＳ２７）。こうして、ビット番号ｎがＬより大きくなるまで（ステップＳ２７においてＴ）、ステップＳ２１〜Ｓ２６の処理を繰り返し実行する。
以上で検出処理が終了する。
【００４１】
検出処理の終了後、制御部２０は、内部変数ｋに対応するアドレスｉで特定される記憶装置Ｍi,jの格納領域にレジスタｒ1〜ｒLの値を格納することで記憶装置Ｍi,jを更新し、またレジスタＣにレジスタｆの値を格納することでレジスタＣを更新する（図３ステップＳ５）。
【００４２】
次に、制御部２０は、内部変数ｋを１増やし（図３ステップＳ６）、内部変数ｋが固定値Ｓより大きいかどうかを判定する（図３ステップＳ７）。内部変数ｋが固定値Ｓ以下であれば、ステップＳ３に戻る。こうして、内部変数ｋが固定値Ｓより大きくなるまで（ステップＳ７においてＴ）、ステップＳ３〜Ｓ６の処理を内部変数ｋ毎（すなわちアドレスｉ毎）に実行する。
【００４３】
内部変数ｋが固定値Ｓより大きくなると、ステップＳ１に戻り、新たな入力文字の到来を待つ。次のクロックサイクルにおいて入力部１が入力文字列から次の１文字を取得して、取得した文字を検出部２に与えるので、図３の処理が再開される。なお、入力部１は、Ｓクロックサイクル毎に入力文字列から次の１文字を取得する。
【００４４】
以上の構成と手順により、あるキーワードに関して、その語の最初の文字から長さＬ文字の区間の最後の文字まで（すなわちｊ＝４番目の文字まで）、入力文字Ｘとの文字の一致が続いていた場合に、この事象（Ａ）を、長さＬ文字の区間の最後の文字の次の文字（次のアドレスｉのｊ＝１番目の文字）について、検査対象の入力文字列の次の文字とも一致が続いているか検査できるように、次のＬ文字の区間の最初の文字の現在の入力文字Ｘとの一致状況を検査した後に、事象（Ａ）の記録として更新して書き込んでおくことによって、検出しようとするキーワードが長さＬ文字よりも長い場合、また、検出しようとするキーワードが、記憶装置Ｄi,jの複数のアドレスの格納領域にわたって格納されている場合にも、記憶装置Ｄi,jにキーワードとして収録されている文字列の検出が可能となった。
【００４５】
特に、検出しようとするキーワードが、記憶装置Ｄi,jの最後の格納領域から最初の格納領域にわたって格納されている場合にも、キーワードとして収録されている文字列の検出が可能となった。この検出は、レジスタｒ1およびｒ2の値の決め方を、ｋが１の場合と１でない場合とで、切り替えることによって可能となっている。
【００４６】
図６に、記憶装置Ｂi,j，Ｄi,j，Ｅi,j，Ｍi,jに格納された文字および値の例を示す。ここでは、Ｓ＝３、Ｌ＝４の場合に、「あいうえおかきくけこ」という１０文字のキーワードの検出を行うことを例とした。
【００４７】
記憶装置Ｄi,jのアドレスｉ＝１、ビット番号ｊ＝１の格納領域には文字「こ」が格納され、アドレスｉ＝１、ビット番号ｊ＝４の格納領域には文字「あ」が格納され、アドレスｉ＝２、ビット番号ｊ＝１〜４の格納領域にはそれぞれ文字「い」，「う」，「え」，「お」が格納され、アドレスｉ＝３、ビット番号ｊ＝１〜４の格納領域にはそれぞれ文字「か」，「き」，「く」，「け」が格納されている。
【００４８】
記憶装置Ｂi,jについては、アドレスｉ＝１、ビット番号ｊ＝４の格納領域の値のみが“１”であり、他の格納領域は全て“０”となっている。
記憶装置Ｅi,jについては、アドレスｉ＝１、ビット番号ｊ＝１の格納領域の値のみが“１”であり、他の格納領域は全て“０”となっている。
【００４９】
このような記憶装置Ｂi,j，Ｅi,jの値は、記憶装置Ｄi,jのアドレスｉ＝１、ビット番号ｊ＝４の格納領域がキーワードの先頭であり、記憶装置Ｄi,jのアドレスｉ＝１、ビット番号ｊ＝１の格納領域がキーワードの末尾であることを表している。つまり、「あいうえおかきくけこ」という１０文字のキーワードが、Ｌ＝４の文字数単位の境界を跨ぐように分割されて、記憶装置Ｄi,jの３つのアドレスの格納領域にわたって格納されていることになる。
【００５０】
記憶装置Ｍi,jについては、全ての格納領域の初期値が“０”となっている。なお、以上のような記憶装置Ｂi,j，Ｄi,j，Ｅi,j，Ｍi,jへの登録は、図示しない辞書管理手段によって行なわれる。
【００５１】
記憶装置Ｂi,j，Ｄi,j，Ｅi,j，Ｍi,jの内容が図６のような場合の本実施の形態の動作を図７、図８を用いて説明する。図７は各クロックサイクルにおけるレジスタｂ1〜ｂ4，ｄ1〜ｄ4，ｅ1〜ｅ4，ｍ1〜ｍ4，ｒ1〜ｒ4，ｆ，Ｃ，Ｘの値の推移を示す図であり、図８は図７の意味を説明する図である。
【００５２】
図７の例では、第１クロックサイクルから第３０クロックサイクルまでのレジスタｂ1〜ｂ4，ｄ1〜ｄ4，ｅ1〜ｅ4，ｍ1〜ｍ4，ｒ1〜ｒ4，ｆ，Ｃ，Ｘの値の推移を示している。なお、各クロックサイクルの箇所に記載されているレジスタＣの値は図３のステップＳ５の処理で更新される前の値を示している。また、「更新後Ｍ」の箇所に記載されているｊ＝１〜ｊ＝４の値はステップＳ５の処理で更新された後の記憶装置Ｍi,jの値を示している。
上記のとおり、入力部１はＳクロックサイクル毎に入力文字列から次の１文字を取得するので、図７の例では、Ｓ＝３クロックサイクル毎にレジスタＸに格納される文字が変わることになる。
【００５３】
まず、第１クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「あ」が格納され、レジスタｄ1に文字「こ」が格納され、レジスタｄ4に文字「あ」が格納される。したがって、レジスタｂ4の値は“１”であり、文字「あ」がキーワードの先頭であることが示されている。レジスタｂ4の値が“１”であり、レジスタｄ4に格納された文字「あ」がレジスタＸに格納された文字と一致するので、式（４）により、レジスタｆに“１”が格納される。
【００５４】
上記のとおり、ｋ＝１の場合、レジスタｒ1の値は任意の値（図７では“ｘ”）となり、レジスタｄ1〜ｄ3に格納された文字がレジスタＸに格納された文字「あ」と一致しないことから、式（１）、式（３）によりレジスタｒ2〜ｒ4の値は全て“０”となる。図３のステップＳ５の処理で、このレジスタｒ1〜ｒ4の値“ｘ”，“０”，“０”，“０”をアドレスｉ＝１で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“１”を格納する。
【００５５】
続いて、第２クロックサイクル（ｋ＝２，ｉ＝２）においても、レジスタＸに格納されている文字は「あ」のままであるが、新たにレジスタｄ1〜ｄ4に格納された文字「い」，「う」，「え」，「お」の中にはレジスタＸに格納された文字「あ」と一致するものはない。図３のステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“１”が格納されるが、レジスタｄ1〜ｄ3に格納された文字「い」，「う」，「え」がレジスタＸに格納された文字「あ」と一致しないことから、式（２）、式（３）によりレジスタｒ2〜ｒ4の値は全て“０”となる。
【００５６】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「お」がレジスタＸに格納された文字「あ」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“１”，“０”，“０”，“０”をアドレスｉ＝２で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００５７】
続いて、第３クロックサイクル（ｋ＝３，ｉ＝３）においても、レジスタＸに格納されている文字は「あ」のままであるが、新たにレジスタｄ1〜ｄ4に格納された文字「か」，「き」，「く」，「け」の中にはレジスタＸに格納された文字「あ」と一致するものはない。ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納され、レジスタｄ1〜ｄ3に格納された文字「か」，「き」，「く」がレジスタＸに格納された文字「あ」と一致しないことから、式（２）、式（３）によりレジスタｒ2〜ｒ4の値は全て“０”となる。
【００５８】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「お」がレジスタＸに格納された文字「あ」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“０”，“０”，“０”をアドレスｉ＝３で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００５９】
次に、第４クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「い」が格納され、レジスタｄ1に文字「こ」が格納され、レジスタｄ4に文字「あ」が格納される。ｋ＝１の場合、レジスタｒ1の値は任意の値（図７では“ｘ”）となり、レジスタｄ1〜ｄ3に格納された文字がレジスタＸに格納された文字「い」と一致しないことから、式（１）、式（３）によりレジスタｒ2〜ｒ4の値は全て“０”となる。
【００６０】
また、レジスタｂ4の値は“１”であるが、レジスタｄ4に格納された文字「あ」がレジスタＸに格納された文字「い」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“ｘ”，“０”，“０”，“０”をアドレスｉ＝１で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００６１】
続いて、第５クロックサイクル（ｋ＝２，ｉ＝２）においても、レジスタＸに格納されている文字は「い」のままであり、ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納されるが、レジスタｍ1の値が“１”であり、レジスタｄ1に格納された文字「い」がレジスタＸに格納された文字「い」と一致することから、式（２）により、レジスタｒ2の値は“１”となる。一方、レジスタｄ2，ｄ3に格納された文字「う」，「え」がレジスタＸに格納された文字「い」と一致しないことから、式（３）によりレジスタｒ3，ｒ4の値は“０”となる。
【００６２】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「お」がレジスタＸに格納された文字「い」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“１”，“０”，“０”をアドレスｉ＝２で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００６３】
続いて、第６クロックサイクル（ｋ＝３，ｉ＝３）においても、レジスタＸに格納されている文字は「い」のままであり、各レジスタの値は第３クロックサイクルの場合と同じになるので、説明は省略する。
【００６４】
次に、第７クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「う」が格納されるが、各レジスタの値は第４クロックサイクルの場合と同じになるので、説明は省略する。
【００６５】
続いて、第８クロックサイクル（ｋ＝２，ｉ＝２）においても、レジスタＸに格納されている文字は「う」のままであり、ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納され、レジスタｄ1に格納された文字「い」がレジスタＸに格納された文字「う」と一致しないことから、式（２）によりレジスタｒ2の値は“０”となるが、レジスタｍ2の値が“１”であり、レジスタｄ2に格納された文字「う」がレジスタＸに格納された文字「う」と一致することから、式（３）により、レジスタｒ3の値は“１”となる。一方、レジスタｄ3に格納された文字「え」がレジスタＸに格納された文字「う」と一致しないことから、式（３）によりレジスタｒ4の値は“０”となる。
【００６６】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「お」がレジスタＸに格納された文字「う」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“０”，“１”，“０”をアドレスｉ＝２で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００６７】
続いて、第９クロックサイクル（ｋ＝３，ｉ＝３）においても、レジスタＸに格納されている文字は「う」のままであり、各レジスタの値は第３クロックサイクルの場合と同じになるので、説明は省略する。
【００６８】
次に、第１０クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「え」が格納されるが、各レジスタの値は第４クロックサイクルの場合と同じになるので、説明は省略する。
【００６９】
続いて、第１１クロックサイクル（ｋ＝２，ｉ＝２）においても、レジスタＸに格納されている文字は「え」のままであり、ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納され、レジスタｄ1，ｄ2に格納された文字「い」，「う」がレジスタＸに格納された文字「え」と一致しないことから、式（２）、式（３）によりレジスタｒ2，ｒ3の値は“０”となるが、レジスタｍ3の値が“１”であり、レジスタｄ3に格納された文字「え」がレジスタＸに格納された文字「え」と一致することから、式（３）により、レジスタｒ4の値は“１”となる。
【００７０】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「お」がレジスタＸに格納された文字「え」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“０”，“０”，“１”をアドレスｉ＝２で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００７１】
続いて、第１２クロックサイクル（ｋ＝３，ｉ＝３）においても、レジスタＸに格納されている文字は「え」のままであり、各レジスタの値は第３クロックサイクルの場合と同じになるので、説明は省略する。
【００７２】
次に、第１３クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「お」が格納されるが、各レジスタの値は第４クロックサイクルの場合と同じになるので、説明は省略する。
【００７３】
続いて、第１４クロックサイクル（ｋ＝２，ｉ＝２）においても、レジスタＸに格納されている文字は「お」のままであり、ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納され、レジスタｄ1〜ｄ3に格納された文字「い」，「う」，「え」がレジスタＸに格納された文字「お」と一致しないことから、式（２）、式（３）によりレジスタｒ2〜ｒ4の値は全て“０”となる。
【００７４】
一方、レジスタｍ4の値が“１”であり、レジスタｄ4に格納された文字「お」がレジスタＸに格納された文字「お」と一致することから、式（４）により、レジスタｆに“１”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“０”，“０”，“０”をアドレスｉ＝２で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“１”を格納する。
【００７５】
続いて、第１５クロックサイクル（ｋ＝３，ｉ＝３）においても、レジスタＸに格納されている文字は「お」のままであり、新たにレジスタｄ1〜ｄ4に格納された文字「か」，「き」，「く」，「け」の中にはレジスタＸに格納された文字「お」と一致するものはない。ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“１”が格納されるが、レジスタｄ1〜ｄ3に格納された文字「か」，「き」，「く」がレジスタＸに格納された文字「お」と一致しないことから、式（２）、式（３）によりレジスタｒ2〜ｒ4の値は全て“０”となる。
【００７６】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「け」がレジスタＸに格納された文字「お」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“１”，“０”，“０”，“０”をアドレスｉ＝３で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００７７】
次に、第１６クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「か」が格納されるが、各レジスタの値は第４クロックサイクルの場合と同じになるので、説明は省略する。
【００７８】
続いて、第１７クロックサイクル（ｋ＝２，ｉ＝２）においても、レジスタＸに格納されている文字は「か」のままであり、ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納され、レジスタｄ1〜ｄ3に格納された文字「い」，「う」，「え」がレジスタＸに格納された文字「か」と一致しないことから、式（２）、式（３）によりレジスタｒ2〜ｒ4の値は全て“０”となる。
【００７９】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「お」がレジスタＸに格納された文字「か」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“０”，“０”，“０”をアドレスｉ＝２で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００８０】
続いて、第１８クロックサイクル（ｋ＝３，ｉ＝３）においても、レジスタＸに格納されている文字は「か」のままであり、ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納されるが、レジスタｍ1の値が“１”であり、レジスタｄ1に格納された文字「か」がレジスタＸに格納された文字「か」と一致することから、式（２）により、レジスタｒ2の値は“１”となる。一方、レジスタｄ2，ｄ3に格納された文字「き」，「く」がレジスタＸに格納された文字「か」と一致しないことから、式（３）によりレジスタｒ3，ｒ4の値は“０”となる。
【００８１】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「け」がレジスタＸに格納された文字「か」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“１”，“０”，“０”をアドレスｉ＝３で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００８２】
次に、第１９クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「き」が格納されるが、各レジスタの値は第４クロックサイクルの場合と同じになるので、説明は省略する。
第２０クロックサイクル（ｋ＝２，ｉ＝２）においても、レジスタＸに格納されている文字は「き」のままであり、各レジスタの値は第１７クロックサイクルの場合と同じになるので、説明は省略する。
【００８３】
続いて、第２１クロックサイクル（ｋ＝３，ｉ＝３）においても、レジスタＸに格納されている文字は「き」のままであり、ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納され、レジスタｄ1に格納された文字「か」がレジスタＸに格納された文字「き」と一致しないことから、式（２）によりレジスタｒ2の値は“０”となるが、レジスタｍ2の値が“１”であり、レジスタｄ2に格納された文字「き」がレジスタＸに格納された文字「き」と一致することから、式（３）により、レジスタｒ3の値は“１”となる。一方、レジスタｄ3に格納された文字「く」がレジスタＸに格納された文字「き」と一致しないことから、式（３）によりレジスタｒ4の値は“０”となる。
【００８４】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「け」がレジスタＸに格納された文字「き」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“０”，“１”，“０”をアドレスｉ＝３で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００８５】
次に、第２２クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「く」が格納されるが、各レジスタの値は第４クロックサイクルの場合と同じになるので、説明は省略する。
第２３クロックサイクル（ｋ＝２，ｉ＝２）においても、レジスタＸに格納されている文字は「く」のままであり、各レジスタの値は第１７クロックサイクルの場合と同じになるので、説明は省略する。
【００８６】
続いて、第２４クロックサイクル（ｋ＝３，ｉ＝３）においても、レジスタＸに格納されている文字は「く」のままであり、ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納され、レジスタｄ1，ｄ2に格納された文字「か」，「き」がレジスタＸに格納された文字「く」と一致しないことから、式（２）、式（３）によりレジスタｒ2，ｒ3の値は“０”となるが、レジスタｍ3の値が“１”であり、レジスタｄ3に格納された文字「く」がレジスタＸに格納された文字「く」と一致することから、式（３）により、レジスタｒ4の値は“１”となる。
【００８７】
また、レジスタｂ4，ｍ4の値が共に“０”であり、レジスタｄ4に格納された文字「け」がレジスタＸに格納された文字「く」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“０”，“０”，“１”をアドレスｉ＝３で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００８８】
次に、第２５クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「け」が格納されるが、各レジスタの値は第４クロックサイクルの場合と同じになるので、説明は省略する。
第２６クロックサイクル（ｋ＝２，ｉ＝２）においても、レジスタＸに格納されている文字は「け」のままであり、各レジスタの値は第１７クロックサイクルの場合と同じになるので、説明は省略する。
【００８９】
続いて、第２７クロックサイクル（ｋ＝３，ｉ＝３）においても、レジスタＸに格納されている文字は「け」のままであり、ステップＳ１２の処理により、レジスタｒ1にはレジスタＣの値“０”が格納され、レジスタｄ1〜ｄ3に格納された文字「か」，「き」，「く」がレジスタＸに格納された文字「け」と一致しないことから、式（２）、式（３）によりレジスタｒ2〜ｒ4の値は全て“０”となる。
【００９０】
一方、レジスタｍ4の値が“１”であり、レジスタｄ4に格納された文字「け」がレジスタＸに格納された文字「け」と一致することから、式（４）により、レジスタｆに“１”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“０”，“０”，“０”，“０”をアドレスｉ＝３で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“１”を格納する。
【００９１】
次に、第２８クロックサイクル（ｋ＝１，ｉ＝１）では、レジスタＸに文字「こ」が格納される。上記のとおり、ｋ＝１の場合、レジスタｒ1の値は任意の値（図７では“ｘ”）となるが、レジスタＣの値が“１”であり、レジスタｄ1に格納された文字「こ」がレジスタＸに格納された文字「こ」と一致することから、式（１）によりレジスタｒ2の値は“１”となる。一方、レジスタｄ2，ｄ3に格納された文字がレジスタＸに格納された文字「こ」と一致しないことから、式（３）によりレジスタｒ3，ｒ4の値は“０”となる。
【００９２】
また、レジスタｂ4の値は“１”であるが、レジスタｄ4に格納された文字「あ」がレジスタＸに格納された文字「こ」と一致しないことから、式（４）により、レジスタｆに“０”が格納される。ステップＳ５の処理で、レジスタｒ1〜ｒ4の値“ｘ”，“１”，“０”，“０”をアドレスｉ＝１で特定される記憶装置Ｍi,jの格納領域に格納し、レジスタＣにレジスタｆの値“０”を格納する。
【００９３】
以上のように、レジスタＸに格納された文字とキーワードとの一致が続いていくと、記憶装置Ｍi,jによりフラグ“１”を受け渡していくが、第２７クロックサイクルにおいてレジスタｆに書き込まれた値“１”（「け」が一致したことを表す値）により、第２８クロックサイクルにおいてレジスタＣを書き換えてから、アドレスｉ＝１で特定される記憶装置Ｍi,jの第１ビットにレジスタＣを書き込んだとしても、「・・・けこ」の一致を検出できない。
【００９４】
本実施の形態では、ｋ＝１の第２８クロックサイクルにおいて、レジスタＸの文字が次の文字「こ」に更新されたときに、レジスタｍ1の値ではなく、レジスタＣの値を参照してレジスタｒ2の値を決定することによってはじめて、所定のキーワード「あいうえおかきくけこ」の検出を行うことができた。第２８クロックサイクルでは、図５のビット番号ｎ＝１の処理の際に、レジスタｒ2の値とレジスタｅ1の値との論理積の結果が“１”となるので、キーワード「あいうえおかきくけこ」の検出が通知されることになる。
【００９５】
本実施の形態のキーワードの検出装置を実装する装置のブロック図を図９に示す。この検出装置を実装する装置は、コンピュータ（プロセッサ１００とメモリ１０１）とＦＰＧＡ（field-programmable gate array）１０２と入出力装置１０３とが搭載された装置である。これらはバス１０４により結合される。入出力装置１０３は、キーワードおよび入力文字列の入力と、検出部２の結果の出力を行う。入出力装置１０３による出力方法としては、検出部２（通知部２１）からの通知結果を画面に表示したり、検出部２からの通知結果の情報を外部に送出したりする方法がある。メモリ１０１は、プロセッサ１００のプログラムとプロセッサ１００の処理の途中結果とを格納する。
【００９６】
プロセッサ１００（ＣＰＵ：Central Processing Unit）は、メモリ１０１に格納されたプログラムに従って処理を実行し、入出力装置１０３から得た入力文字列をメモリ１０１に格納し、また検出部２内の通知部２１および制御部２０から、文字列の検出信号を得ることができる。ＦＰＧＡ１０２は、入力部１と検出部２の機能を実現する。ただし、記憶装置Ｄi,j，Ｂi,j，Ｅi,j，Ｍi,jについてはメモリ１０１上に構築される。
【００９７】
なお、前述の辞書管理手段は、プロセッサ１００と、メモリ１０１に格納されたプログラムによって実現してもよいし、図９に示した装置の外部に設けられる他のコンピュータ等の装置によって実現してもよい。
【００９８】
以上のように、本実施の形態では、レジスタｒ1〜ｒLに対する処理の結果（第１の更新処理の結果）を記憶装置Ｍi,jに格納することで、この結果をＳクロックサイクル後に確認できるようにし、また記憶装置Ｄi,jのアドレスｉのＬ番目の文字とレジスタＸに格納された文字との一致判定の結果をレジスタｆに一旦格納した後に、レジスタＣにレジスタｆの値を格納することで、１サイクル前の結果を、記憶装置Ｄi,jの次のアドレスｉの１番目の一致判定の際に確認できるようにしたので、キーワードの文字数と記憶装置Ｄi,jの文字数単位Ｌの大小や、キーワードの格納位置によらず、入力文字列の中からキーワードを検出することができる。その結果、本実施の形態では、キーワードの文字数が設計値（文字数単位Ｌ）より長い場合でも、処理性能の低下を抑えることができる。また、本実施の形態では、キーワードの文字数が著しく短い場合を考慮して文字数単位Ｌを設定しても処理性能の低下を抑えることができるので、キーワードの文字数が文字数単位Ｌより短い場合の資源の損失を抑えることが可能となり、装置の再設計が必要になる可能性を低減することができる。
【００９９】
また、本実施の形態では、レジスタｒ1〜ｒLに対する処理（第１の更新処理）の際に、アドレスｉが先頭の値（本実施の形態の例ではｉ＝１）で、レジスタＣのフラグがセットされ、かつ記憶装置Ｄi,jのアドレスｉの１番目に格納された文字とレジスタＸに格納された文字とが一致したときにレジスタｒ2の値を“１”にすることにより、記憶装置Ｄi,jの最後の格納領域から最初の格納領域にわたってキーワードを格納することを可能にすることができ、記憶装置Ｄi,jへのキーワードの格納の制約を緩和することができる。
【産業上の利用可能性】
【０１００】
本発明は、入力文字列の中からキーワードを抽出する技術に適用することができる。
【符号の説明】
【０１０１】
１…入力部、２…検出部、２０…制御部、２１…通知部、１００…プロセッサ、１０１…メモリ、１０２…ＦＰＧＡ、１０３…入出力装置、１０４…バス、Ｂi,j，Ｄi,j，Ｅi,j，Ｍi,j…記憶装置、ｂ1〜ｂL，ｄ1〜ｄL，ｅ1〜ｅL，ｍ1〜ｍL，ｒ1〜ｒL，ｆ，Ｃ，Ｘ…レジスタ。
【図１】
2017130075.tif 000003
【図２】
2017130075.tif 000004
【図３】
2017130075.tif 000005
【図４】
2017130075.tif 000006
【図５】
2017130075.tif 000007
【図６】
2017130075.tif 000008
【図７】
2017130075.tif 000009
【図８】
2017130075.tif 000010
【図９】
2017130075.tif 000011