(57)【要約】【課題】検出すべきキーワード列が多数であっても、比較的簡単な構成で、登録された多数のキーワード列が入力ストリームに含まれているか否かを調べる。【解決手段】第１階層のキーワード検出部２０により、入力ストリームＳＴＭからキーワード（ＫＷ）を検出してその識別子ＫＷを出力し、次いで第２階層のキーワード列検出部３０により、複数のキーワード（ＫＷ）からなるキーワード列（ＫＷＡ）を検出してその識別子ＫＷＡを出力し、次いで第３階層のＷ／Ｇ／Ｂ総合判定部４０により、同一グループに属する１個以上の検出されたキーワード列識別子ＫＷＡが全体としてホワイトＷ、グレイＧ又はブラックＢのいずれであるかを判定してその結果を出力する。【選択図】図１
2010231272.tif 000002
【特許請求の範囲】
【請求項１】
入力ストリームが供給され、複数登録されているキーワード列のどれが該入力ストリームに含まれているかを調べてその識別子を出力するキーワード列検出装置において、
該入力ストリームに、複数登録されているキーワードのどれと一致するものが含まれているかを調べて、一致するキーワードの識別子を順次出力するキーワード検出手段と、
該複数のキーワード識別子のそれぞれに対応して、キーワードが該複数のキーワード列のどれのどの位置に含まれているかを示すキーワード列識別子・列内位置情報が格納された変換情報記憶手段と、
該複数のキーワード列のそれぞれがどのキーワードまで検出されているかを示す現状態が格納されるキーワード列検出状態記憶手段と、
該キーワード検出手段で検出されたキーワード識別子に対応したキーワード列識別子・列内位置情報を該変換情報記憶手段から読み出させ、読み出されたキーワード列識別子・列内位置情報に基づいて、該キーワード列検出状態記憶手段内の対応する現状態を読み出させ、この現状態がこの情報の列内位置情報に対応していればこの現状態を次状態に遷移させ、遷移後の現状態が出力状態であればキーワード列識別子を出力する状態遷移制御手段と、
を有することを特徴とするキーワード列検出装置。
【請求項２】
該変換情報記憶手段は、インデックステーブル記憶部とキーワード列識別子・列内位置情報記憶部とを有し、
該インデックステーブル記憶部には、該複数のキーワード識別子のそれぞれに対応して、該キーワード列識別子・列内位置情報記憶部内の情報ブロックの先頭アドレスとワード数情報とが格納され、
該情報ブロックは、対応するキーワード識別子で識別されるキーワードが複数のキーワード列のどれのどの位置に含まれているかを示すキーワード列識別子・列内位置情報を、該ワード数情報で示されるワード数分有する、
ことを特徴とする請求項１に記載のキーワード列検出装置。
【請求項３】
該キーワード列検出状態記憶手段は、各キーワード列識別子に対応したアドレスに、このキーワード列識別子で識別されるキーワード列のどのキーワードまで検出されているかを示すカウンタが現状態として格納される現状態アレイを有する、
ことを特徴とする請求項１又は２に記載のキーワード列検出装置。
【請求項４】
各キーワード列識別子に対応したアドレスは、ワードアドレスとワード内カウンタの位置とで表されることを特徴とする請求項３に記載のキーワード列検出装置。
【請求項５】
該キーワード列検出状態記憶手段はさらに、現状態アレイに対応した初期状態アレイを有し、
該状態遷移制御手段は、所定のタイミングで該初期状態アレイの内容の一部又は全部を、該現状態アレイの対応する一部又は全部に代入させ、次状態に遷移させるためにカウンタの内容を変化させたときにカウンタが所定値になり又は該カウンタからのキャリーがセットされているときに出力状態と判定する、
ことを特徴とする請求項３又は４に記載のキーワード列検出装置。
【請求項６】
１つ以上の現状態を含むワード毎を１ビットに対応させた初期化要否判定用ビットマップをさらに有し、
該状態遷移制御手段は、供給されるリセット信号の活性化に応答して、該初期化要否判定用ビットマップを初期化させ、該１つ以上の現状態を含むワードの内容を読み出す際に該初期化要否判定用ビットマップの対応するビットが初期化されていれば、このワードを、対応する初期状態のワードで初期化するとともに、該ビットを反転させる、
ことを特徴とする請求項１乃至５のいずれか１つに記載のキーワード列検出装置。
【請求項７】
各情報ブロックは、
該カウンタが複数含まれカウント値によりその有効／無効を判定可能な複数カウンタワードを１以上含む現状態ワード群と、
各複数カウンタワードが１ビットに対応し、該現状態ワード群に含まれる各複数カウンタワードに対応したビットが有効であることを示す複数カウンタワード有無ビットマップと、
を有することを特徴とする請求項３乃至５のいずれか１つに記載のキーワード列検出装置。
【請求項８】
入力ストリームが供給され、複数登録されているキーワード列のどれが該入力ストリームに含まれているかを調べてその識別子を出力するキーワード列検出方法において、
キーワード検出手段に対し、該入力ストリームに、複数登録されているキーワードのどれと一致するものが含まれているかを調べさせて、一致するキーワードの識別子を順次出力させ、
状態遷移制御手段に対し、
該複数のキーワード識別子のそれぞれに対応して、キーワードが該複数のキーワード列のどれのどの位置に含まれているかを示すキーワード列識別子・列内位置情報が格納された変換情報記憶手段から、該キーワード検出手段で検出されたキーワード識別子に対応したキーワード列識別子・列内位置情報を読み出させ、
読み出されたキーワード列識別子・列内位置情報に基づいて、該複数のキーワード列のそれぞれがどのキーワードまで検出されているかを示す現状態が格納されるキーワード列検出状態記憶手段内の対応する現状態を読み出させ、この現状態がこの情報の列内位置情報に対応していればこの現状態を次状態に遷移させ、遷移後の現状態が出力状態であればキーワード列識別子を出力させる、
ことを特徴とするキーワード列検出方法。
【請求項９】
該キーワード列検出状態記憶手段は、各キーワード列識別子に対応したアドレスに、このキーワード列識別子で識別されるキーワード列のどのキーワードまで検出されているかを示すカウンタが現状態として格納される現状態アレイを有し、
該状態遷移制御手段に対し、所定のタイミングで、現状態アレイに対応した初期状態アレイの内容の一部又は全部を、該現状態アレイの対応する一部又は全部に代入させ、次状態に遷移させるためにカウンタの内容を変化させたときにカウンタが所定値になり又は該カウンタからのキャリーがセットされているときに出力状態と判定させる、
ことを特徴とする請求項８に記載のキーワード列検出方法。
【請求項１０】
１つ以上の現状態を含むワード毎を１ビットに対応させた初期化要否判定用ビットマップをさらに有し、
該状態遷移制御手段に対し、供給されるリセット信号の活性化に応答して、該初期化要否判定用ビットマップを初期化させ、該１つ以上の現状態を含むワードの内容を読み出す際に該初期化要否判定用ビットマップの対応するビットが初期化されていれば、このワードを、対応する初期状態のワードで初期化するとともに、該ビットを反転させる、
ことを特徴とする請求項８又は９に記載のキーワード列検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キーワード列検出方法及び装置に関する。
【背景技術】
【０００２】
インターネットを介して様々な情報を入手したり多数の人とコミュニケーションをとることができる反面、ソーシャル・ネットワーキング・サービス（ＳＮＳ）やブログなどのコミュニティサイトで、個人や組織を誹謗中傷したり、公序良俗に反したりする文章が書き込まれると、社会問題となる。意に反する書き込みにより自社の悪評が世間に広まると、そのイメージを払拭するのは容易でなく、企業の存亡に関わる。そこで、ウェブページ上の書き込みを監視するウェブパトロールが、業として行われている。
【０００３】
検索エンジンにキーワードを入力し、その結果のリストから人がリンクをクリックしてウェブページを閲覧することによりウェブパトロールを行うのは、効率が悪い。ソフトウェアによりウェブパトロールを自動化することもできるが、大量の情報を高速に処理することは困難である。
【０００４】
正規表現を用いてキーワード検索を行えば、１つのキーワードで多数の単純キーワードを検索することができる。正規表現検索は、非決定性オートマトン（ＮＦＡ）を用いて実行することができる。
【０００５】
下記特許文献１には、ワンチップ上に数千のＮＦＡを並列動作させることが可能な状態機械アーキテクチャが開示されている。また、ＮＦＡを階層構造にすることも開示されている。
【０００６】
この技術によれば、高速処理が可能であるので、ネットワーク上のデータをコンピュータに入力する前に、データをフィルタリング可能である。
【特許文献１】特表２００５−５３７５５０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、ウェブページ上の書き込み監視を上記特許文献１の状態機械アーキテクチャで行おうとすると、次のような問題が生ずる。
【０００８】
すなわち、この文献の実施例では、１つのＮＦＡの状態遷移評価シンボルの数（文字数）はキーワード列検出状態記憶部３２で、１シンボルは１バイトである。日本語のように文字セットの文字数が数千で且つ１文字が２バイトである場合に、この状態機械アーキテクチャを適用すると、１つのＮＦＡが大規模になる。このため、多数のチップを結合させ、それら全体を制御する必要があり、構成が複雑になる。
【０００９】
一方、ＮＦＡは、理論的にはＤＦＡ（決定性オートマトン）に変換することができる。しかし、例えば、第１〜３キーワードのそれぞれが１００個の単純キーワードを含み、第１〜３キーワードがこの順に、文章に含まれているか否かを調べる場合、ＤＦＡでは、この１つの状態遷移評価キーワード列（パターン）だけでも、１００×１００×１００＝１００万の状態遷移を想定して、ステートマシンを構成しなければならない。このため、例えば状態遷移評価キーワード列数が不適切書き込み検出装置１０万である場合、キーワード列をＤＦＡで検出しようとすると状態爆発が起こり、実用的でない。
【００１０】
このような問題は、Ｗｅｂページ上の不適切な書き込みだけではなく、好評の書き込みや、インターネット上での市場ニーズ調査や、書類を分類して整理する場合や、テキストマイニングにおいても生ずる。キーワード列を構成するそれぞれのキーワードが文字以外のコードで構成される場合にも、同様の問題が生ずる。
【００１１】
本発明の目的は、上記問題点に鑑み、検出すべきキーワード列が多数であっても、比較的簡単な構成で、登録された多数のキーワード列が入力ストリームに含まれているか否かを調べることが可能なキーワード列検出方法及び装置を提供することにある。
【課題を解決するための手段】
【００１２】
本発明の第１態様では、入力ストリームが供給され、複数登録されているキーワード列のどれが該入力ストリームに含まれているかを調べてその識別子を出力するキーワード列検出装置において、
該入力ストリームに、複数登録されているキーワードのどれと一致するものが含まれているかを調べて、一致するキーワードの識別子を順次出力するキーワード検出手段と、
該複数のキーワード識別子のそれぞれに対応して、キーワードが該複数のキーワード列のどれのどの位置に含まれているかを示すキーワード列識別子・列内位置情報が格納された変換情報記憶手段と、
該複数のキーワード列のそれぞれがどのキーワードまで検出されているかを示す現状態が格納されるキーワード列検出状態記憶手段と、
該キーワード検出手段で検出されたキーワード識別子に対応したキーワード列識別子・列内位置情報を該変換情報記憶手段から読み出させ、読み出されたキーワード列識別子・列内位置情報に基づいて、該キーワード列検出状態記憶手段内の対応する現状態を読み出させ、この現状態がこの情報の列内位置情報に対応していればこの現状態を次状態に遷移させ、遷移後の現状態が出力状態であればキーワード列識別子を出力する状態遷移制御手段とを有する。
【発明の効果】
【００１３】
上記第１態様の構成によれば、第１階層のキーワード検出手段で、入力ストリームに含まれているキーワードを検出してその識別子を順次出力し、第２階層において、キーワード識別子に対応したキーワード列識別子・列内位置情報を変換情報記憶手段から読み出させ、読み出されたキーワード列識別子・列内位置情報に基づいて、キーワード列検出状態記憶手段内の対応する現状態を読み出させ、この現状態がこの情報の列内位置情報に対応していればこの現状態を次状態に遷移させ、遷移後の現状態が出力状態であればキーワード列識別子を出力するので、検出すべきキーワード列が多数であっても、比較的簡単な構成で、登録された多数のキーワード列が入力ストリームに含まれているか否かを調べることができるという効果を奏する。
【００１４】
本発明の他の目的、構成及び効果は以下の説明から明らかになる。
【実施例１】
【００１５】
キーワード識別子をＫＷ、キーワード列識別子をＫＷＡで表し、複数のＫＷ及びＫＷＡのそれぞれにインデクスを付加してそれらを区別し、識別子の対象を（識別子）で表す。例えば、キーワード列（ＫＷＡ３）が１つの文章中にキーワード（ＫＷ５）、（ＫＷｍ）及び（ＫＷ３）をこの順に含んでいることを表し、キーワード間に０個以上の任意の文字が存在していてもよいとする。これは、正規表現を用いて、
（ＫＷＡ３）＝（ＫＷ５）．＊（ＫＷｍ）．＊（ＫＷ３）      ・・・（１）
と表すことができる。「．」は改行を含む任意の１文字であり、＊は直前の文字の０個以上の繰り返しを意味する。なお、「．」は一般的な定義のように、改行を含まない任意の１文字とし、改行を１文章の終わりとみなしてもよい。
【００１６】
図１は、本発明の実施例１に係る不適切書き込み検出装置１０の概略ブロック図である。
【００１７】
この装置１０は、掲示板やブログなどのＷｅｂ頁上の不適切な書き込みを３階層で自動検出するものであり、第１階層のキーワード検出部２０により、入力ストリームＳＴＭからキーワード（ＫＷ）を検出してその識別子ＫＷを出力し、次いで第２階層のキーワード列検出部３０により、複数のキーワード（ＫＷ）からなるキーワード列（ＫＷＡ）を検出してその識別子ＫＷＡを出力し、次いで第３階層のＷ／Ｇ／Ｂ総合判定部４０により、同一グループに属する１個以上の検出されたキーワード列識別子ＫＷＡが全体としてホワイト（問題なし）Ｗ、グレイ（人の判断要）Ｇ又はブラック（不適切表現）Ｂのいずれであるかを判定してその結果を出力する。
【００１８】
例えば、ブラックＢのキーワード列（ＫＷＡ１）＝「モルヒネ」．＊「買いたい」が検出されても、ホワイトＷのキーワード列（ＫＷＡ２）＝「疼痛治療」．＊「モルヒネ」も検出され、ＫＷＡ１とＫＷＡ２とが同一グループに属すると定義されていれば、全体としてホワイトＷと判定される。
【００１９】
キーワード検出部２０には、インターネットを介してコンピュータ内のメモリ又は補助記憶装置に格納されたＷｅｂ頁の書き込みデータが、入力ストリームＳＴＭとして供給される。
【００２０】
キーワード検出部２０は、例えばハードウエア構成の有限状態オートマトン記憶装置２１を備えており、入力ストリームＳＴＭがクロックに同期して例えばバイト単位で入力シンボルとして有限状態オートマトン記憶装置２１に順次供給され、入力シンボルと現状態とに基づいて次状態が読み出される処理が繰り返され、現状態が出力状態であることを意味していれば、すなわち、予め登録されたキーワード（ＫＷ）のいずれかに一致するものが入力ストリームＳＴＭに含まれていると判定されると、この出力状態が格納されているメモリのアドレスが、キーワード識別子ＫＷとしてキーワード検出部２０から出力され、キーワード列検出部３０に供給される。
【００２１】
有限状態オートマトン記憶装置２１は、例えば１０万個のキーワードを検出可能となっている。キーワードは、正規表現を含まない単純キーワードであっても、正規表現キーワードであってもよい。正規表現キーワードについては、これを検出するＮＦＡがＤＦＡに展開される。さらに、ＡＣ法（Aho-Corasick algorithm）により、全ＤＦＡが１つのＤＦＡに纏められており、入力ストリームＳＴＭをキーワード検出部２０へ１回供給するだけで、キーワードを検出可能となっている。
【００２２】
キーワード列検出部３０は、本発明の実施例の特徴部分であり、変換情報記憶部３１と、キーワード列検出状態記憶部３２と、状態遷移制御部３３とで構成されている。
【００２３】
変換情報記憶部３１には、キーワード検出部２０で検出可能な全てのキーワードのそれぞれについて、そのキーワード（ＫＷ）が、予め登録された多数のキーワード列（ＫＷＡ）のどれのどの位置ＰＯＳに含まれているかを示す情報が格納されている。
【００２４】
図２は、この情報を視覚的に表すＫＷ／ＫＷＡ・ＰＯＳマトリックステーブルを示す。このテーブルのセルには、その列に対応したキーワード列（ＫＷＡ）に、その行に対応したキーワード（ＫＷ）がどの位置に含まれているかを示す値ＰＯＳが記入されている。
【００２５】
キーワード識別子ＫＷ及びキーワード列識別子ＫＷＡをそれぞれ変換情報記憶部３１の行アドレス及び列アドレスとして、変換情報記憶部３１に列内キーワード位置ＰＯＳの値を格納することも可能であるが、図２の空白セルに対応した無駄な領域が多くなるとともに、各キーワード識別子ＫＷについて、全ての列アドレス（キーワード列識別子ＫＷＡ）のそれぞれに、列内キーワード位置ＰＯＳが格納されているか否かを調べなければならないので、処理時間が長くなる。
【００２６】
そこで、変換情報記憶部３１には、図３に示すようなインデックステーブル３１１と、キーワード列識別子・列内位置情報３１２とが格納されている。インデックステーブル３１１のワードアドレスＡＤＤＲ＝ｉには、キーワード識別子ＫＷｉと、これに関係したキーワード列識別子・列内位置情報３１２の先頭アドレスＳＡＤＲｉと、この先頭アドレスからのワード数ＷＮｉとが格納されている。例えばＫＷ２は、キーワード列識別子・列内位置情報３１２のワードアドレスＡＤＤＲ２から４ワードに渡って各ワードに、ＫＷ２に関係したキーワード列識別子ＫＷＡと列内キーワード位置ＰＯＳとが格納されている。
【００２７】
図１のキーワード列検出状態記憶部３２には、図４（Ａ）に示すように、登録された全キーワード列のそれぞれの識別子ＫＷＡの値に対応した（等しい又は一定値シフトした値等）アドレスに、現状態（現検出状態）ＳＴが格納された現状態アレイ３２１と、初期状態ＳＴ０が格納された初期状態アレイ３２２とが格納されている。図４（Ａ）では、ｉ番目のキーワード列識別子ＫＷＡｉの現状態をＳＴｉ、初期状態をＳＴ０ｉで表している。各ｉの値について、現状態ＳＴｉのアドレスは、初期状態ＳＴｉ０のそれに一定値を加算した値である。
【００２８】
図１に戻って、入力ストリームＳＴＭが文章の終わりを示すと、状態遷移制御部３３に供給されるリセット信号ＲＳＴが活性になる。状態遷移制御部３３は、これに応答してキーワード列検出状態記憶部３２に対し、図４（Ｂ）に示す初期化処理３３２を実行する。以下、括弧内は図中のステップ識別符号である。
【００２９】
（Ｓ０）初期化中フラグＦをセットする。
【００３０】
（Ｓ１）図４（Ａ）において、ｉ＝１〜ｎのそれぞれにつき現状態ＳＴｉに初期状態ＳＴ０ｉを代入する。この処理は、ソフトウエアでＣＰＵを介し行っても、ＤＭＡＣ（ダイレクトメモリアクセス制御）で行ってもよい。
【００３１】
ここで、図１に示すように、状態遷移制御部３３はＫＷキュー３３１を備えており、有限状態オートマトン記憶装置２１が上述のように出力状態となると、そのアドレスがキーワード識別子ＫＷとしてキーワード検出部２０から出力され、状態遷移制御部３３のＫＷキュー３３１に入力される。このアドレスを所定値シフトしたり、ＣＡＭメモリを介してアドレス間を詰めたものをキーワード識別子ＫＷとしてもよい。
【００３２】
図５は、状態遷移制御部３３によるキーワード列状態遷移処理３３３を示すフローチャートであり、このキーワード列状態遷移処理３３３は、ソフトウエアで行ってもハードウエアで行ってもよい。
【００３３】
（Ｓ１０）ＫＷキュー３３１からキーワード識別子ＫＷを１つ読み出す。
【００３４】
（Ｓ１１）ＫＷキュー３３１が空（キーワード識別子ＫＷがＮＵＬＬ）であればステップＳ１０へ戻り、そうでなければステップＳ１２へ進む。
【００３５】
（Ｓ１２）ステップＳ１０で読み出されたキーワード識別子ＫＷｉが格納されているインデックステーブル３１１のワードアドレスＡＤＤＲを検出する。これは、例えば２分探索法（バイナリサーチ）により検出することができる。インデックステーブル３１１を有限オートマトン装置のメモリに反映して、この探索を有限オートマトン装置で行う構成であってもよい。また、ＣＡＭメモリで１回のアクセスによりワードアドレスＡＤＤＲを検出する構成であってもよい。
【００３６】
（Ｓ１３）検出されたワードアドレスＡＤＤＲから、先頭アドレスＳＡＤＲｉ及びワード数ＷＮｉを読出し、それぞれ変数ＡＤＲ及びＣＮＴに代入する。以下、ステップＳ１４〜Ｓ２３の処理を、ＷＮｉ回繰り返す。
【００３７】
（Ｓ１４）ＡＤＲでキーワード列識別子・列内位置情報３１２をアドレス指定して、キーワード列識別子・列内位置情報３１２からキーワード列識別子ＫＷＡ及び列内キーワード位置ＰＯＳを読出す。
【００３８】
（Ｓ１５）Ｆ＝‘１’であれば、すなわち図４（Ｂ）の初期化処理３３２が実行中であれば、その処理が終了するのを待ってステップＳ１６へ進み、そうでなければ直接、ステップＳ１６へ進む。
【００３９】
（Ｓ１６）キーワード列検出状態記憶部３２のキーワード列識別子ＫＷＡｉから現状態ＳＴｉを読み出す。
【００４０】
（Ｓ１７）読み出した現状態ＳＴｉが、ステップＳ１４で読み出した列内キーワード位置ＰＯＳｉの値に対応していれば、ステップＳ１８へ進み、そうでなければステップＳ２１へ進む。
【００４１】
ここで、図６（Ａ）を参照して、現状態ＳＴ及び列内キーワード位置ＰＯＳの表現の具体例を説明する。
【００４２】
１つのキーワード列（ＫＷＡ）に含まれるキーワード数は最大８であるとし、現状態ＳＴ及び列内キーワード位置ＰＯＳをそれぞれ１バイトで表す。キーワード列識別子ＫＷＡはこのバイトのアドレスに対応している。任意のキーワード列（ＫＷＡ）について、その最後のキーワード、上式（１）の（ＫＷＡ３）の場合はキーワード（ＫＷ３）を、１バイトの最上位ビット（ＭＳＢ）に対応させ、それからｊ個前のキーワードを（７−ｊ）ビットに対応させる。例えば、対応したビットのみを‘１’とし、他のビットを全て‘０’とする。すなわち、ＫＷＡ３の現状態ＳＴ３の初期状態ＳＴ０３を‘００１０００００’と表す。
【００４３】
（Ｓ１８）現状態ＳＴをＭＳＢ側へ１ビットシフトさせる。
【００４４】
上記の例の場合、図６（Ｂ）に示すように、キーワード（ＫＷ５）が検出され且つＳＴ３＝ＰＯＳであれば、現状態ＳＴをＭＳＢ側へ１ビットシフトさせて、ＳＴ３＝‘０１００００００’とする。ＳＴ３がこの値のときに、キーワード（ＫＷｍ）が検出されれば現状態ＳＴをＭＳＢ側へ１ビットシフトさせてＳＴ３＝‘１０００００００’とする。ＳＴ３がこの値のときに、キーワード（ＫＷ３）が検出されれば現状態ＳＴをＭＳＢ側へ１ビットシフトさせてＳＴ３＝‘１０００００００’とする。このとき、キャリーＣが‘１’になる。
【００４５】
（Ｓ１９）キャリーＣが‘１’であればステップＳ０へ進み、そうでなければステップＳ２１へ進む。
【００４６】
（Ｓ２０）キーワード列識別子ＫＷＡに対応したキーワード列（ＫＷＡ）が検出されたことを示すために、キーワード列識別子ＫＷＡを出力して、Ｗ／Ｇ／Ｂ総合判定部４０へ供給する。
【００４７】
（Ｓ２１）カウンタＣＮＴを１だけデクリメントする。
【００４８】
（Ｓ２２）ＣＮＴ＜０であればステップＳ１０へ戻り、そうでなければステップＳ２３へ進む。
【００４９】
（Ｓ２３）ワードアドレスＡＤＲを１だけインクリメントし、ステップＳ１４へ戻る。
【００５０】
このようにして、比較的簡単な構成で、多数の登録されたキーワード列（ＫＷＡ）のいずれかに一致するキーワード列が入力ストリームＳＴＭに含まれていることを検出することができる。
【００５１】
Ｗ／Ｇ／Ｂ総合判定部４０は、その記憶部に、登録された全キーワード列（ＫＷＡ）のそれぞれについて、キーワード列識別子ＫＷＡと、それがホワイトＷ、グレイＧ、ブラックＢの何れであるかを示す情報と、キーワード列識別子ＫＷＡが属するグループ識別ＩＤとが対応して格納されており、同一グループＩＤのキーワード列識別子ＫＷＡに基づいて、検出されたキーワード列識別子ＫＷＡがＷであるかＧであるかＢであるかを総合判定する。例えば、同一グループ内の複数のキーワード列識別子ＫＷＡに、Ｂのキーワード列識別子ＫＷＡが含まれていてもＷのキーワード列識別子ＫＷＡが含まれていれば、このグループに含まれる複数のキーワード列識別子ＫＷＡは、全体としてＷであると判定する。
【実施例２】
【００５２】
Ｗｅｂ頁上の書き込みが掲示板である場合、一般に１文章が短いので、リセット信号ＲＳＴが頻繁に活性化される。このため、キーワード列識別子ＫＷＡの数が例えば１０万と多いと、図４（Ｂ）の初期化処理３３２の実行時間割合が比較的大きくなる。一方、このような場合には、リセット直前において、現状態が初期状態である割合が比較的大きいと考えられるので、初期化処理３３２に無駄が生ずる。
【００５３】
そこで、本発明の実施例２では、図４（Ａ）のキーワード列検出状態記憶部３２にさらに、図８に示すような初期化済ビップマップ３２３を備え、リセット信号ＲＳＴの活性化に応答してこの初期化済ビップマップ３２３のみを初期化、例えばゼロクリアする。
【００５４】
ビップマップ３２３の先頭バイトアドレスをＡ０とすると、ビップマップ３２３のバイトアドレスＡ＝Ａ０＋ｉの第ｊビットは、現状態アレイ３２１のキーワード列識別子ＫＷＡ（８＊ｉ＋ｊ）に対応しており、この第ｊビットが‘０’であれば、その現状態ＳＴ（８＊ｉ＋ｊ）のみを初期化する。すなわち、図５のステップＳ１５の代わりに、図７に示す処理を実行する。
【００５５】
（Ｓ１５０）上記のように、キーワード列識別子ＫＷＡに対応するビットを初期化済ビップマップ３２３から読み出す。
【００５６】
（Ｓ１５１）この値が‘０’であればステップＳ１５２へ進み、そうでなければ図５のステップＳ１６へ進む。
【００５７】
（Ｓ１５２）キーワード列識別子ＫＷＡに所定アドレスを加算したアドレスから初期状態ＳＴ０を読み出して、これをアドレスＫＷＡの現状態ＳＴへ代入し、ステップＳ１６へ進む。
【００５８】
他の点は、実施例１と同様である。
【実施例３】
【００５９】
上記実施例１及び２では、現状態ＳＴのカウンタをシフトカウンタで構成する場合を説明したが、バイナリカウンタで構成することもできる。１つのキーワード列（ＫＷＡ）に含まれる最大キーワード数を例えば７とすると、このカウンタを３ビットで構成することができ、１バイトに２個のカウンタを格納することができる。バイト単位でアクセスすると、２ビットの無駄が生ずるので、６４ビットを１ワードとしてアクセスする。この場合、３×２１＝６３であるので、余りは１ビットであり、これをＭＳＢとする。
【００６０】
図９は、このような構成のキーワード列検出状態記憶部３２Ａの現状態アレイ３２１Ａを示す。図９の現状態アレイ３２１Ａにおいて、ＭＳＢのセルに記入された斜線は、この余りを示し、また、初期状態から遷移したもののみそのカウントを示している。３ビットカウンタのアドレスは、このカウンタを含むワードのアドレスと、ワード内カウンタ先頭ビットのアドレスとで指定される。初期状態アレイ３２２Ａも現態アレイ３２１Ａに対応した構成である。
【００６１】
図５のステップＳ１８では、現状態ＳＴを１ビットシフトする替わりに、現状態ＳＴを１だけインクリメントする。現状態ＳＴの初期化は、６４ビットのワード単位で、実施例１又は実施例２と同様に行う。
【００６２】
他の点は、実施例１と同様である。
【００６３】
本実施例３によれば、キーワード列検出状態記憶部３２Ａの記憶容量を低減できるので、特にキーワード列識別子ＫＷＡの数が多い場合に好適である。
【実施例４】
【００６４】
実施例２では、初期化済ビップマップ３２３の１ビットを１つのキーワード列識別子ＫＷＡに対応させたが、実施例３では１ワード＝６４ビットに２１個の状態が対応するので、実施例３に実施例２の初期化済ビップマップ３２３を適用する場合、現状態をワード単位で初期化した方が効率がよい。
【００６５】
そこで、本発明の実施例４では、この１ワード毎に、すなわち２１個の現状態ＳＴ毎に、図１０に示す初期化済ビップマップ３２３Ａの１ビットを対応させ、リセット信号ＲＳＴの活性化に応答して初期化済ビップマップ３２３Ａのみを初期化し、図５のステップＳ１５の代わりに、図７と同様の処理をワード単位で行う。
【００６６】
初期化済ビップマップ３２３Ａの各ワードのＭＳＢは、有効ビットＶＢであり、ＶＢ＝‘０’であれば、このワードの有効ビットＶＢを除いた残り６３ビットが全て‘０’であることを意味し、ＶＢ＝‘１’であれば、この６３ビットの少なくとも１ビットが‘１’であることを示している。まず有効ビットＶＢの値により、初期化要否の概略を判定できる。キーワード列検出状態記憶部３２Ｂは、この初期化済ビップマップ３２３Ａと、図９の初期状態アレイ３２２Ａ及び現状態アレイ３２１Ａと同一の構成とからなる。
【００６７】
初期化済ビップマップ３２３Ａの、ＭＳＢを除いたｋ番目のビットは、現状態アレイ３２１Ａの上からｋ番目のワードの２１個の現状態ＳＴに対応しており、ビップマップ３２３Ａ及び現状態アレイ３２１Ａのそれぞれの先頭ワードアドレスをＷＡ０及びＷＡ１で表すと、ビップマップ３２３Ａのワードアドレス（ＷＡ０＋ｉ）の第ｊビットは、現状態アレイ３２１Ａのワードアドレス（ＷＡ１＋ｉ＊６３＋ｊ）のワードの、２１個の現状態ＳＴに対応している。
【００６８】
図７のステップＳ１５１でこの第ｊビットが‘０’であれば、ステップＳ１５１において、初期状態アレイ３２２Ａのワードアドレス（ＷＡ２＋ｉ＊６３＋ｊ）の値を、現状態アレイ３２１Ａのワードアドレス（ＷＡ１＋ｉ＊６３＋ｊ）に代入して、２１個の現状態ＳＴを同時に初期化する。ここにＷＡ２は、初期状態アレイ３２２Ａの先頭ワードアドレスである。
【００６９】
また、図３のキーワード列識別子・列内位置情報３１２の代わりに、図１１に示すようなキーワード列識別子・列内位置情報３１２Ａを用いる。例えば図３の情報ブロック３１２−２は、図１１の情報ブロック３１２Ａ−２に対応している。この情報ブロック３１２Ａ−２は、有効ＰＯＳビットマップ３１３と、ＰＯＳワード群３１４とからなる。
【００７０】
ビットマップ３１３は、構成としては形式上、ビップマップ３２３Ａと同一である。しかし、ビットマップ３１３は初期化と関係がなく、ビット‘１’は、その位置に対応した現状態アレイ３２１Ａのワードに対応した、２１個のＰＯＳ（ＰＯＳワード）が、ＰＯＳワード群３１４に含まれていることを意味している。
【００７１】
ＰＯＳワード群３１４には、ビットマップ３１３のＭＳＢを除くビットのうち‘１’に対応したＰＯＳワードのみが含まれ、有効ＰＯＳビットマップ３１３の‘１’のみのビット群についてｋ番目の‘１’は、ＰＯＳワード群３１４のｋ番目のワードに対応している。
【００７２】
より具体的には、ビットマップ３１３及びＰＯＳワード群３１４の先頭ワードアドレスをそれぞれＷＡ３及びＷＡ４で表すと、ワードアドレス（ＷＡ３＋ｉ）の第ｊビットが、ビットマップ３１３上の‘１’のみについてｋ番目の‘１’（ＭＳＢの‘１’を除く）であれば、ＰＯＳワード群３１４のワードアドレス（ＷＡ４＋ｋ−１）のＰＯＳワードは、現状態アレイ３２１Ａのワードアドレス（ＷＡ１＋ｉ＊６３＋ｊ）の２１個の現状態ＳＴに対応している。このＰＯＳワードは、値が０でないＰＯＳのみ有効であり、有効なＰＯＳが、これに対応する現状態ＳＴと、図５のステップＳ１７で比較される。
【００７３】
ビットマップ３１３から図３のワード数ＷＮが分かるので、図３のワード数ＷＮはなくてもよい。
【００７４】
本実施例４では特に、インデックステーブル３１１の１つの先頭アドレスＳＡＤＲに対応したキーワード列識別子ＫＷＡの数が比較的大きくかつ互いに接近している場合に、ＰＯＳワード群３１４の１ワードで多数のＰＯＳを処理することができるので、特にハードウエアでこの処理を並列に行うことにより、高速処理が可能となる。ソフトウエアで処理する場合であっても、メモリアクセス回数を低減してＣＰＵ内のレジスタで処理できる量が増えるので、処理を高速化することが可能である。
【００７５】
本発明の好適な実施例を説明したが、本発明には他にも種々の変形例が含まれ、上記複数の実施例で述べた構成要素の他の組み合わせ、各構成要素の機能を実現する他の構成を用いたもの、当業者であればこれらの構成又は機能から想到するであろう他の構成も、本発明に含まれる。例えば、本発明には以下のような変形例が含まれる。
【００７６】
例えば、実施例１又は２のキーワード列識別子・列内位置情報３１２及びキーワード列検出状態記憶部３２と実施例４のキーワード列識別子・列内位置情報３１２Ａ及びキーワード列検出状態記憶部３２Ｂとの両方を備え、１つのキーワード（ＫＷ）が含まれるキーワード列（ＫＷＡ）の数が設定値以下であれば実施例１又は２のキーワード列識別子・列内位置情報３１２及びキーワード列検出状態記憶部３２を用い、設定値を超えれば実施例４のキーワード列識別子・列内位置情報３１２Ａ及びキーワード列検出状態記憶部３２Ｂを用いる構成であってもよい。
【００７７】
また、現状態ＳＴとして、アップカウンタの替わりにダウンカウンタを用い、所定値、例えば０を出力状態とする構成であってもよい。
【００７８】
さらに、現状態ＳＴと位置ＰＯＳの一方をシフトカウンタとし、他方をバイナリカウンタとし、制御部で両者が実質的に一致（対応）しているか否かを判定する構成であってもよい。
【００７９】
また、上記いずれの実施例も本発明を不適切書き込み検出装置１０に適用した場合を説明したが、よい評判の書き込みを検出する装置や、文章や書類を分類して整理する装置や、要望表現を検出して市場ニーズ調査を行う装置や、テキストマイニング装置などにも適用することができる。さらに、文章以外のバイナリデータに本発明を適用することもできる。
【図面の簡単な説明】
【００８０】
【図１】本発明の実施例１に係る不適切書き込み検出装置の概略ブロック図である。
【図２】図１の変換情報記憶部に論理的に格納される情報を視覚的に表すキーワード識別子ＫＷ／キーワード列識別子ＫＷＡ・列内位置ＰＯＳマトリックステーブルを示す図である。
【図３】図１の変換情報記憶部に格納される情報の構造説明図である。
【図４】（Ａ）は図１のキーワード列検出状態記憶部に格納される情報の構造説明図であり、（Ｂ）は図１の状態遷移制御部による現状態初期化処理を示すフローチャートである。
【図５】図１の状態遷移制御部によるキーワード列状態遷移処理を示すフローチャートである。
【図６】（Ａ）は現状態ＳＴ及び列内キーワード位置ＰＯＳの表現の具体例説明図であり、（Ｂ）は列内キーワード位置ＰＯＳによる現状態ＳＴの遷移説明図である。
【図７】本発明の実施例２に係る現状態初期化処理を示す部分フローチャートである。
【図８】この現状態初期化処理で用いられる初期化済ビップマップの説明図である。
【図９】本発明の実施例３に係るキーワード列検出状態記憶部に格納される情報の構造説明図である。
【図１０】本発明の実施例４に係るキーワード列検出状態記憶部に格納される情報の構造説明図である。
【図１１】本発明の実施例４に係るキーワード列識別子・列内位置情報記憶部に格納される情報の構造説明図である。
【符号の説明】
【００８１】
１０  不適切書き込み検出装置
２０  キーワード検出部
２１  有限状態オートマトン記憶装置
３０  キーワード列検出部
３１  変換情報記憶部
３１１  インデックステーブル
３１２、３１２Ａ  キーワード列識別子・列内位置情報記憶部
３１２−２、３１２Ａ−２  情報ブロック
３１３  有効ＰＯＳビットマップ
３１４  ＰＯＳワード群
３２、３２Ａ、３２Ｂ  キーワード列検出状態記憶部
３２１、３２１Ａ  現状態アレイ
３２２、３２２Ａ  初期状態アレイ
３２３、３２３Ａ  初期化済ビップマップ
３３  状態遷移制御部
３３１  ＫＷキュー
３３２  初期化処理
３３３  キーワード列状態遷移処理
４０  Ｗ／Ｇ／Ｂ総合判定部
Ｆ  初期化中フラグ
ＳＡＤＲ、ＳＡＤＲｉ  先頭アドレス
ＷＮ、ＷＮｉ  ワード数
ＡＤＤＲ  ワードアドレス
Ｃ  キャリー
ＫＷ、ＫＷｉ  キーワード識別子
ＫＷＡ、ＫＷＡｉ  キーワード列識別子
ＰＯＳ、ＰＯＳｉ  列内キーワード位置
ＳＴ、ＳＴｉ  現状態
ＳＴ０、ＳＴ０ｉ  初期状態
ＶＢ  有効ビット
【図１】
2010231272.tif 000003
【図２】
2010231272.tif 000004
【図３】
2010231272.tif 000005
【図４】
2010231272.tif 000006
【図５】
2010231272.tif 000007
【図６】
2010231272.tif 000008
【図７】
2010231272.tif 000009
【図８】
2010231272.tif 000010
【図９】
2010231272.tif 000011
【図１０】
2010231272.tif 000012
【図１１】
2010231272.tif 000013