(57)【要約】  決定性有限オートマトンのメモリサイズを小さくし、メモリ使用量およびキャッシュ利用効率を上げることを目的とする。  検索キーワードに応じて生成されたオートマトンに基づいて、検索対象から前記検索キーワードを検索する検索装置であって、第１メモリ領域24と、第２メモリ領域27と、第１情報23及び第２情報22から第３情報を生成する情報生成部26と、判定部30と、選択部31と、を有し、第１メモリ領域から第１情報に対応する第１状態25が読み出され、第２メモリ領域から第３情報に対応する第４情報及び第２状態28が読み出され、判定部は、第１情報及び第２情報からなる第５情報29と、第４情報とが一致するか、又はしないかを判定し、選択部は判定において一致しない場合に第１状態を選択し、判定において一致する場合に前記第２状態を選択する。
2009050797.tif 000002
【特許請求の範囲】
【請求項１】
検索キーワードに応じて生成されたオートマトンに基づいて、検索対象から前記検索キーワードを検索する検索装置であって、
第１メモリ領域と、
第２メモリ領域と、
第１情報及び第２情報から第３情報を生成する情報生成部と、
判定部と、
選択部と、を有し、
前記第１メモリ領域から、前記第１情報に対応する第１状態が読み出され、
前記第２メモリ領域から、前記第３情報に対応する第４情報及び第２状態が読み出され、
前記判定部は、前記第１情報及び前記第２情報からなる第５情報と、前記第４情報とが一致するか、又はしないかを判定し、
前記選択部は、前記判定において一致しない場合に前記第１状態を選択し、前記判定において一致する場合に前記第２状態を選択することを特徴とする検索装置。
【請求項２】
前記第１情報は、検索における現在の状態であり、
前記第２情報は、前記検索対象の文字に対応したコードであり、
前記情報生成部は、前記現在の状態と前記コードを所定の方法でハッシングして前記第３情報を生成し、
前記第４情報は、前記現在の状態に対応したコード、前記検索対象の文字に対応したコード又は、前記現在の状態と前記検索対象の文字とに対応したコードを含み、
前記第１状態および前記第２状態は、次の状態である、ことを特徴とする請求項１に記載の検索装置。
【請求項３】
前記検索対象の文字に対応した入力コードが、所定のコードと一致するかを判定する入力判定部をさらに有し、
前記入力判定部が一致すると判定した入力コードに対しては、前記情報生成部、前記判定部および前記選択部は動作を行わず、現在の状態を更新しないことを特徴とする請求項１に記載の検索装置。
【請求項４】
前記第２メモリ領域は、複数のメモリ領域を有し、
前記情報生成部は、前記複数のメモリ領域のそれぞれに対応したハッシングの方法で、前記第３情報を生成することを特徴とする請求項２に記載の検索装置。
【請求項５】
前記第２メモリ領域の前記複数のメモリ領域は、空きエントリ数が近似していることを特徴とする請求項４に記載の検索装置。
【請求項６】
前記第２メモリ領域に格納できない前記第４情報及び前記第２状態を格納する第３メモリ領域をさらに有し、
前記第２メモリ領域は、前記第３メモリ領域の存在を示すフラグを有することを特徴とする請求項１に記載の検索装置。
【請求項７】
前記第２メモリ領域から読み出された前記第４情報と前記第５情報とが一致しない場合、
前記第３メモリ領域から、前記第３状態が読み出され、
前記選択部は、前記第３状態を選択することを特徴とする請求項６に記載の検索装置。
【請求項８】
前記第１メモリ領域から前記第３メモリ領域は、さらに出力情報を格納することを特徴とする請求項６に記載の検索装置。
【請求項９】
検索キーワードに応じて生成されたオートマトンに基づいて、検索対象から前記検索キーワードを検索する検索方法であって、
前記オートマトンの現在の状態に対応する第１アドレスに応じて第１メモリ領域に第１アクセスして第２アドレスを読み出し、
前記第１アドレスと検索対象の文字に対応したコードとをハッシングして第３アドレスを生成し、
前記第３アドレスに応じて第２メモリ領域に第２アクセスして、第４アドレスと第５アドレスからなる第６アドレス情報を読み出し、
前記第１アドレスと前記第４アドレスとを比較し、
前記第１アドレスと前記第４アドレスとが一致しない場合には、前記第２アドレスを、前記オートマトンにおいて遷移する次の状態とし、
前記第１アドレスと前記第４アドレスが一致した場合には、前記第５アドレスを、前記オートマトンにおいて遷移する前記次の状態とすることを特徴とする検索方法。
【請求項１０】
前記第４アドレスは、前記現在の状態に対応し、
前記第５アドレスは前記遷移する次の状態に対応することを特徴とする請求項９に記載の検索方法。
【請求項１１】
前記検索対象の文字に対応した入力コードが、所定のコードと一致するかを判定し、
前記入力判定部が一致すると判定した入力コードに対しては、処理を行わず、現在の状態を更新しないことを特徴とする請求項９に記載の検索方法。
【請求項１２】
前記第２メモリ領域は、複数のメモリ領域を有し、
前記第１アドレスと検索対象の文字に対応したコードとから前記第３アドレスを生成するハッシングの方法を、前記複数のメモリ領域のそれぞれに対応して異ならせることを特徴とする請求項１に記載の検索方法。
【請求項１３】
前記第２メモリ領域の前記複数のメモリ領域は、空きエントリ数が近似するように前記第６アドレス情報が記録されていることを特徴とする請求項１２に記載の検索方法。
【請求項１４】
前記第２メモリ領域から読み出された前記第４情報と前記第５情報とが一致しない場合、
前記第２メモリ領域に記録できない前記第５アドレスを格納した第３メモリ領域に、前記第１アドレスと前記検索対象の文字に対応したコードとで第３アクセスして、前記第５アドレスを読み出し、
前記第３アクセスで読み出した前記第５アドレスを、前記オートマトンにおいて遷移する前記次の状態とすることを特徴とする請求項９に記載の検索方法。
【請求項１５】
前記第２アドレス、前記６アドレス情報および前記第９アドレスは、さらに出力情報を有することを特徴とする請求項１４に記載の検索方法。
【請求項１６】
検索キーワードに応じて生成されたオートマトンに基づいて、検索対象から前記検索キーワードを検索する検索方法であって、
前記オートマトンの第１ノードに対応する第１アドレスと前記第１ノードに対応するコードとから第１タグを生成し、
前記第１タグと前記第１ノードの次の遷移先となる第２ノードに対応する第２アドレスとからなる情報を第２メモリ領域に格納し、
前記第２メモリ領域の前記遷移先として選択されない第３コードに対応する第３アドレスを第１メモリ領域に格納し、
前記第１メモリ領域から読み出される第１情報と、前記第２メモリ領域から読み出される第２情報とを、入力される前記第１アドレス及び前記コードからなる第２タグと、前記第１タグとの比較に基づいて選択することを特徴とする検索方法。
【請求項１７】
前記第１アドレスは、検索における現在の状態であり、
前記第１ノードに対応するコードは、前記検索対象の文字に対応したコードであり、
前記第１タグと前記第２アドレスからなる情報を格納する前記第２メモリ領域のアドレスは、前記第１アドレスと前記第１ノードに対応するコードをハッシングすることにより生成されることを特徴とする請求項１６に記載の検索方法。
【請求項１８】
前記第２メモリ領域は、複数のメモリ領域を有し、
前記複数のメモリ領域へアクセスするためのアドレスは、それぞれに対応した異なるハッシングの方法で生成される請求項１７に記載の検索方法。
【請求項１９】
前記第２メモリ領域の前記複数のメモリ領域への前記第１タグと前記第２アドレスからなる情報の格納は、メモリ領域ごとの空きエントリ数を比較し、一番空きエントリの多いメモリ領域に順に格納し、前記複数のメモリ領域の空きエントリ数が近似していることを特徴とする請求項１８に記載の検索方法。
【請求項２０】
前記第２メモリ領域に格納できない前記第１タグと前記第２アドレスからなる情報を第３メモリ領域に格納し、
前記第１メモリ領域から読み出される第１情報と、前記第２メモリ領域から読み出される第２情報と、前記第３メモリ領域から読み出される第３情報とを、入力される前記第１アドレス及び前記コードからなる第２タグと、前記第２および第３メモリ領域から読み出された前記第１タグとの比較に基づいて選択することを特徴とする請求項１６に記載の検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オートマトン処理技術を使用して、与えられた入力文字列であるテキストから任意の文字列であるパターンを検索する検索装置および検索方法に関する。
【背景技術】
【０００２】
近年、さまざまな分野で情報量が爆発的に増加している。ある分野においてはギガバイトオーダーからテラバイトオーダーになりつつあり、その莫大なデータから所望のデータを短時間の間に取り出すことが困難になりつつある。【０００３】
与えられたテキストから任意の種類のパターンを検索するパターンマッチングは、ワープロソフト、データベースの検索など、多様な分野で応用されている。【０００４】
従来パターンマッチングによる検索には各種の手法が提案されているおり、特許文献１（特開２００５−７０９１１）は、決定性有限オートマトンを用いた検索装置および方法を記載している。【０００５】
図１は、キーワード検索アルゴリズムの１つであるシグマ（Ｓｉｇｍａ）アルゴリズムを説明する図である。この図に示したのは、検索対象の文書から”ｂｌｕｅ”，”ｇｒｅｅｎ”，”ｒｅｄ”，”ｙｅｌｌｏｗ”のキーワードが存在するか検索する例である。図示のように、各キーワード条件に対応したオートマトンを作成する。具体的には、０で示す根から、各キーワードの先頭文字”ｂ”、”ｇ”、”ｒ”、”ｙ”に遷移し、さらに各キーワード列の文字に遷移するオートマトンを作成する。各キーワード列の最後の文字まで一致すればキーワード列が検索される。ここで、”ｇｒｅｅｎ”のキーワード列には”ｒｅ”が含まれており、その後に”ｄ”があれば”ｒｅｄ”と一致するので、図示のように”ｇｒｅｅｎ”の途中から”ｒｅｄ”の”ｄ”に遷移する経路が存在する。【０００６】
検索は、根からは始まり、オートマトン内のキーワードがあれば順次遷移し、キーワードと関係のない文字が読み込まれたら根に戻る。例えば、図１の（Ｂ）の”ｂｌａｃｋ”を含む文書が入力されると、”ｂｌｕｅ”の先頭の”ｂ”に遷移し、さらに次の”ｌ”に遷移するが、次が”ａ”であるので根に戻る。文書内にオートマトンのキーワード列があれば、各キーワード列の最後まで到達してヒット（Ｈｉｔ）情報が出力され、キーワード列が存在することが判明する。【０００７】
ここで、オートマトン検索において、各キーワード列の何番目の文字にあるかをノードまたは「状態」で表す。例えば、根が状態１で、”ｂｌｕｅ”の”ｂ”にいれば状態２で、”ｕ”にいれば状態４と称する。【０００８】
図２は、決定性有限オートマトンを用いた検索装置の概略構成を示す図である。ディスク装置などに格納された検索対象文書１１が流し込まれ、そこから順に文字バイトコード１２が取り出される。以下の説明では、文字バイトコード１２は８ビットで、２５６エントリを形成するとする。レジスタに保持された現在の状態（を示すデータ）１３と、文字バイトコード１２とを合わせたインデックスを、検索キーワードオートマトンを形成するメモリ１５の入力アドレス１４とする。入力アドレス１４が入力されたメモリ１５は、出力データ１６を出力し、それには次の状態１７と、ヒット情報が含まれる。次の状態１７は、現在の状態１３に置き換えられる。【０００９】
図３は、図２の検索装置の動作を説明する図である。ここでは、説明を簡単にするために、”ｆｏ”のキーワード列を検索する例を示す。図３の（Ａ）に示すように、状態１から”ｆ”（０ｘ６６）が出現すると状態２に進み、状態２で”ｏ”（０ｘ６Ｆ）が出現すると状態３に進み、再び”ｆ”（０ｘ６６）が出現すると状態２を維持し、それ以外の場合は状態１に戻る。【００１０】
この検索キーワードオートマトンは、図３の（Ｂ）に示される。文字バイトコードは８ビットであり、各状態は２５６エントリ（アドレス）を有する。左側のメモリ部分Ｍ−Ｘが状態１からの遷移先を表し、中央のメモリ部分Ｍ−Ｙが状態２からの遷移先を表し、右側のメモリ部分Ｍ−Ｚが状態３からの遷移先を表す。メモリ部分Ｍ−Ｘは、状態１であることを表す0xXXXX部分と、複数のキーワード列を表すXX部分と、各キーワード列の状態１のエントリを表す00-ff部分を組み合わせたアドレスに対して、遷移先を格納する。エントリを表す00-ffのうち66で状態２に遷移し、それ以外の場合は再び状態１を維持するので、0xXXXX_XX66に状態２のアドレス0xYYYY_YY00が、それ以外のアドレスに対して状態１のアドレス0xXXXX_XX00が格納される。なお、メモリ部分Ｍ−Ｘのヒット情報ＨＩＴは、ヒットしたことを示さないＮ／Ａである。他のキーワード列についても同様に、下から３および４桁のXXを異ならせて格納される。【００１１】
同様に、メモリ部分Ｍ−Ｙは、状態２であることを表すアドレス部分0xYYYYと、複数のキーワード列を表すYYと、各キーワード列の状態２のエントリを表す00-ffを組み合わせたアドレスに対して、遷移先を格納する。エントリを表す00-ffのうち6fで状態３に遷移し、66で状態２を維持し、それ以外の場合は状態１に戻るので、0xYYYY_YY6fに状態３のアドレス0xZZZZ_ZZ00が、0xYYYY_YY66に状態２のアドレス0xYYYY_YY00が、それ以外のアドレスに対して状態１のアドレス0xXXXX_XX00が格納される。なお、メモリ部分Ｍ−Ｙのヒット情報ＨＩＴは、ヒットしたことを示さないＮ／Ａである。【００１２】
同様に、メモリ部分Ｍ−Ｚは、状態３であることを表すアドレス部分0xZZZZと、複数のキーワード列を表すZZと、各キーワード列の状態３のエントリを表す00-ffを組み合わせたアドレスに対して、遷移先を格納する。エントリを表す00-ffのうち66で状態２に遷移し、それ以外の場合は状態１に戻るので、0xZZZZ_ZZ66に状態２のアドレス0xYYYY_YY00が、それ以外のアドレスに対して状態１のアドレス0xXXXX_XX00が格納される。メモリ部分Ｍ−Ｙのヒット情報ＨＩＴは、ヒットしたことを示すＨＩＴである。従って、状態３のメモリＭ−Ｚまで到達すれば、キーワード列が存在する。【００１３】
図４は、上記のようなオートマトンを利用した検索装置の構築処理とそれによる検索処理を示すフローチャートである。【００１４】
ステップ１０１では、検索条件の入力を行う。上記の例であれば、”ｆｏ”を入力する。また、図１の例であれば、”ｂｌｕｅ”，”ｇｒｅｅｎ”，”ｒｅｄ”，”ｙｅｌｌｏｗ”が入力される。【００１５】
ステップ１０２では、入力された検索条件、すなわちキーワード列に基づいてオートマトンの作成を行う。【００１６】
ステップ１０３では、メモリ上にオートマトンを構築する。【００１７】
ステップ１０４では、検索対象文書を入力としてメモリ上のオートマトンを用いて検索を行う。【００１８】
ステップ１０５では、検索結果を出力する。【００１９】
図５は、ステップ１０３のメモリ上のオートマトンの構築処理をより詳細に示すフローチャートであり、例えばメモリ上に図３の（Ｂ）のようなテーブルを構築する処理を示す。【００２０】
ステップ１１１では、オートマトンのノード（状態）ごとにテーブルを作成する。【００２１】
ステップ１１２では、オートマトンの辺（遷移先）を表現するために、テーブルのエントリに遷移先ノードのテーブルの先頭ポイント（アドレス）を書き込む。【００２２】
ステップ１１３では、最後の状態のテーブルにヒットフラグを書き込む。【００２３】
図６は、ステップ１０４のメモリ上に構築したオートマトンを使用しての検索処理をより詳細に示すフローチャートである。【００２４】
ステップ１２１では、検索対象の文書から次の１文字を読み出し、ステップ１２２で、文書が終わりであるかを判定する。終わりであれば、ステップ１０５に進み、終わりでなければステップ１２３に進む。【００２５】
ステップ１２３では、現在の状態と読み出した文字の文字コードを入力アドレスとして、オートマトンを構築したメモリからのデータの読み出しを行う。【００２６】
ステップ１２４では、読み出されたデータから、キーワードがヒットしたか、すなわちヒット情報が含まれる状態に到達したかが判定され、ヒットしていなければステップ１２６に進み、ヒットしていればステップ１２５に進む。【００２７】
ステップ１２５ではヒット情報を更新する。【００２８】
ステップ１２６では、「現在の状態」を、ステップ１２３で読み出したデータに含まれる「次の状態」に更新してステップ１２１に戻る。【００２９】
以上、検索キーワードオートマトンのメモリ上での構築とそれを利用したキーワード検索を説明したが、同一の検索キーワードオートマトンを構築したメモリを複数用意して、検索対象文書を複数の部分に分割して各メモリに並列に供給して、検索を並列に行うことにより、検索の高速化を図ることが行われている。また、検索キーワードオートマトンをキャッシュメモリにロードして、検索の高速化を図ることも行われている。【００３０】
上記の従来のオートマトンを利用した検索装置および方法では、検索式が多い場合や、検索式が複雑な場合には、オートマトンのサイズが非常に大きくなるという問題があった。オートマトンのサイズが大きくなると、メモリの使用量が増加し、プロセッサなどで処理する際にキャッシュミスを多発し、検索速度が低下するという問題を生じたり、ハードウエアコストが大きくなるという問題を生じる。【００３１】
特許文献２（特開２００５−２４２６６８）は、テキストにハッシュ関数を適用することにより、オートマトンのメモリサイズを削減し、スループットを向上する検索装置および方法を記載している。【００３２】
【特許文献１】特開２００５−７０９１１
【特許文献２】特開２００５−２４２６６８
【発明の開示】
【発明が解決しようとする課題】
【００３３】
しかし、特許文献２に記載された方法では、ハッシュ関数を使用するため、マッチしないテキスト文字列でもマッチしたとして検出する可能性があり、さらにオートマトンのメモリサイズを十分に削減できないという問題がある。【００３４】
本発明は、膨大な文書から高速かつ少ないメモリサイズで所望のデータを取り出せる検索装置および検索方法の実現を目的とし、具体的には決定性有限オートマトンのメモリサイズを小さくし、メモリ使用量およびキャッシュ利用効率を上げることを目的とする。
【課題を解決するための手段】
【００３５】
上記目的を実現するため、本発明の検索装置および検索方法は、同一遷移先のエントリをデフォルト(default)遷移先として特別にデフォルト用メモリ領域（第１メモリ領域）を用意し、キーワードに関連するデフォルトでない遷移先を表現するために、デフォルト用メモリ領域とは別にイベント用メモリ領域（第２メモリ領域）を用意する。デフォルト用メモリ領域では、１エントリまたはある定められた入力ごとにデフォルトの遷移先を格納する。
なお、第１メモリ領域と第２メモリ領域は、独立したメモリとして形成することも、同一メモリ内に形成することも可能である。これは後述する第３メモリ領域についても同様である。以下の説明では、説明を簡単にするために、メモリ領域を単にメモリと称するものとする。【００３６】
図３に示すように、従来例によれば、オートマトンを構築したメモリは、大部分の入力文字（エントリ）に対する遷移先が、根である第１の状態である。従って、この部分をまとめて表現できれば、メモリのサイズを大幅に低減できる。そこで、本発明では、現在の状態（第１状態）を表す情報（第１情報）と入力文字（第２情報）をハッシングしたものを入力とするイベント用メモリを用意し、そこに検索キーワードに関連する遷移先を含む情報を格納し、それ以外の入力はまとめてデフォルトの遷移先としてデフォルト用メモリに格納する。大きな部分を占めるデフォルトの遷移先が１つにまとめられるので、メモリサイズは大幅に低減できる。さらに、メモリサイズの低減に応じて、検索処理の高速化も図れる。【００３７】
イベント用メモリでは、現在の状態（第１状態）を表す情報（第１情報）と入力文字（第２情報）をハッシングした情報（第３情報）を入力とし、エントリに対する情報として、遷移先情報（第２状態）に加え、入力文字及び／又は現在の状態を特定するための情報（第４情報）をタグとして登録しておくことで、メモリサイズを抑えつつ、デフォルトでない遷移を表現する。これにより、ハッシングすることで異なるイベントが同一エントリに割り当てられ、すなわちエントリ干渉が起き、マッチしていない場合にもマッチしていると誤判定されるハッシングに起因するエラーを防止できる。【００３８】
また、ハッシングすることで異なるイベントが同一エントリに割当てられるのをなるべく減らすために、イベント用メモリを複数用意し、連想を持たせてエントリ干渉を低減するようにしてもよい。また、連想ごとにハッシュ関数を変えることで、エントリ干渉の頻度を低減できる。【００３９】
この場合、複数のイベント用メモリのユニットへの情報の格納は、ユニットごとの空きエントリ数を比較し、一番空きエントリの多いメモリユニットに順に格納し、複数のユニットの空きエントリ数を近似させることが望ましい。【００４０】
さらに、検索対象文書から読み出した入力文字が、改行記号など特定の文字コードであれば、処理を行わずに現在の状態を維持するようにしてもよい。【００４１】
さらに、イベント用メモリに格納できないキーワード列を記憶する第３メモリを用意して、イベント用メモリには第３メモリの存在を示すフラグを設けるようにする。そして、現在の状態と入力文字の組みがイベント用メモリからの情報と一致しない場合、第３メモリにアクセスして、そこにもキーワード列が無ければデフォルトの遷移先に遷移する。
【図面の簡単な説明】
【００４２】
【図１】オートマトンによるキーワード検索アルゴリズムの一例であるシグマアルゴリズムを説明する図である。
【図２】メモリ上にオートマトンを形成した従来の検索装置の概略構成を示す図である。
【図３】図１のオートマトンの遷移図と、メモリ上のデータを示す図である。
【図４】従来の検索装置の処理を示すフローチャートである。
【図５】従来の検索装置のメモリ上でのオートマトンの構築処理を示すフローチャートである。
【図６】従来の検索装置におけるオートマトンを用いた検索処理を示すフローチャートである。
【図７】本発明の第１実施形態の検索装置の構成を示す図である。
【図８】第１実施形態におけるオートマトンの構築処理を示すフローチャートである。
【図９】第１実施形態におけるオートマトンを用いた検索処理を示すフローチャートである。
【図１０】第１実施形態におけるオートマトンの例と、そのメモリ上でのデータを示す図である。
【図１１】第１実施形態のイベント用メモリのデータ例を示す図である。
【図１２】本発明の第２実施形態の検索装置の構成を示す図である。
【図１３】本発明の第３実施形態の検索装置の構成を示す図である。
【図１４】本発明の第４実施形態の検索装置の構成を示す図である。
【符号の説明】
【００４３】
２１    検索対象文書
２２    入力文字（第２情報）
２３    現在の状態（第１情報）
２４    デフォルト用メモリ
２５    次の状態（第１状態）
２６    ハッシュ器（ＸＯＲ）
２７    イベント用メモリ
２８    第４情報＋第２状態
３１    選択回路
【発明を実施するための最良の形態】
【００４４】
以下、本発明の実施形態を添付の図面を参照して説明する。【００４５】
図７は、本発明の第１実施形態の検索装置の構成を示す図である。ディスク装置などに格納された検索対象文書２１が流し込まれ、そこから順に入力文字（バイトコード）２２が取り出される。レジスタには、現在の状態２３が保持されている。デフォルト用メモリ２４は、現在の状態２３を入力とし、デフォルトの遷移先、すなわち根に相当する状態が記憶されており、その状態が次の状態２５として出力される。【００４６】
入力文字２２と現在の状態２３は、ハッシュ器２６に入力されると共に、第５情報レジスタ２９に入力される。ハッシュ器２６は、ここではＸＯＲ回路であり、現在の状態（第１情報）２３と入力文字（第２情報）２２の排他的論理和を演算してイベント用メモリ２７へアクセスするためのアドレス（第３情報）を生成する。イベント用メモリ２７は、キーワード列のオートマトンを構成するメモリであり、キーワード列の文字とキーワード列における順番（状態）のＸＯＲの値をアドレスとする位置に、（現在の）状態と文字の組み、次の遷移先である次の状態、およびヒット（ＨＩＴ）情報が格納されており、それ以外の位置にはゼロが格納されている。イベント用メモリ２７は、アクセス時のアドレスに応じて記憶しているデータを出力するので、キーワード列の状態と文字のＸＯＲの値がアドレスとして入力されると、キーワード列の状態と文字の組み、次の状態、およびヒット（ＨＩＴ）情報を含む出力データ２８を出力し、それ以外のアドレスが入力されると、ゼロデータを出力する。ヒット情報が出力された時には、キーワード列が存在することが判明する。【００４７】
デフォルト用メモリ２４とイベント用メモリ２７は、キャッシュメモリ上で実現することが望ましい。前述のように、第１メモリ領域および第２メモリ領域は、独立したメモリとして形成することも、同一メモリ内に形成することも可能であり、第１メモリ領域に対応するデフォルト用メモリ２４および第２メモリ領域に対応するイベント用メモリ２７も同様である。従って、デフォルト用メモリ２４およびイベント用メモリ２７は、独立したキャッシュメモリとして形成されるか、または同一のキャッシュメモリ内に実現されることが望ましい。【００４８】
イベント用メモリ２７の出力データ２８のうち、状態と文字の組みは、第５情報レジスタ２９に保持された現在の状態と入力文字の組みと比較され、一致するか判定される。一致すれば、キーワード列内に、現在の状態２３と入力文字２２から決定される根以外の遷移先があることを意味するので、選択回路３１でイベント用メモリ２７の出力データ２８の次の状態が選択される。一致しなければ、キーワード列内に、現在の状態２３と入力文字２２から決定される根以外の遷移先がないことを意味するので、すなわちデフォルトの状態であるので、選択回路３１でデフォルト用メモリ２４から出力された次の状態が選択される。選択された次の状態は、現在の状態２３を格納するレジスタに入力される。これにより、現在の状態は、選択された次の状態に置き換えられる。【００４９】
第１実施形態の検索装置におけるオートマトン構築処理とそれによる検索処理は、図４のフローチャートと同じであり、ステップ１０３とステップ１０４の内容が異なる。【００５０】
図８は、第１実施形態の検索装置におけるオートマトン構築処理を示すフローチャートである。【００５１】
ステップ２０１では、オートマトンのノードごとに、デフォルト遷移先をデフォルト用メモリ２４に書き込む。デフォルト遷移先は、各キーワード列の根に相当するので、各キーワード列に対して１つである。【００５２】
ステップ２０２では、デフォルト以外のオートマトンの辺（遷移先）を表現するために、各キーワード列の状態ＩＤ（アドレス）と遷移入力条件（文字）のＸＯＲ値をインデックス（アドレス）として、状態ＩＤ、入力文字、遷移先状態（次の状態）ＩＤ（アドレス）をイベント用メモリ２７に書き込む。【００５３】
ステップ２０３では、イベント用メモリ２７の最後の状態にヒットフラグを書き込む。【００５４】
以上のようにして、デフォルト用メモリ２４およびイベント用メモリ２７へのデータの書き込み、すなわちオートマトンの構築が完了する。【００５５】
図９は、構築したオートマトンを使用しての検索処理をより詳細に示すフローチャートである。【００５６】
ステップ２１１では、検索対象文書から次の１文字を読み出す。【００５７】
ステップ２１２では、ステップ２１１で読み出した文字がない場合、文書が終わりであると判定し、読み出した文字がある場合にはステップ２１３に進む。【００５８】
ステップ２１３では、現在の状態２３を入力として、デフォルト用メモリ２４にアクセスし、デフォルトの遷移先、すなわち次の状態２５を読み出す。さらに、現在の状態２３と入力文字コード（１バイト）２２とのＸＯＲ値を演算し、それを入力としてイベント用メモリ２７にアクセスし、記憶されている情報を読み出す。各キーワード列の状態ＩＤ（アドレス）と遷移入力条件（文字）のＸＯＲ値をアドレスとする番地に格納された情報には、状態ＩＤと入力文字コードの組み、次の状態、およびヒット情報が格納され、それ以外のアドレスに格納された情報には、ゼロが格納されている。従って、現在の状態２３と入力文字コード２２が、キーワード列の状態と遷移条件（文字）と同じであれば、そのＸＯＲ値でイベント用メモリ２７にアクセスするとゼロ以外のデータ出力２８が得られ、現在の状態２３と入力文字コード２２が、キーワード列の状態と遷移条件（文字）と同じでなければゼロが、出力データ２８として出力される。この出力データ２８には、次の状態とヒット情報も含まれる。【００５９】
ステップ２１４では、イベント用メモリ２７の出力データ２８のいずれかが、現在の状態２３と入力文字コード２２と一致するかが判定され、一致すればステップ２１５に進み、一致しなければステップ２１６に進む。【００６０】
ステップ２１５では、選択器３１が、一致したイベント用メモリ２７の出力データ２８に含まれる次の状態を選択する。【００６１】
ステップ２１６では、選択器３１が、デフォルト用メモリ２４の出力した次の状態２５を選択する。【００６２】
ステップ２１７では、イベント用メモリ２７の出力データ２８のヒット情報がキーワードにヒット（ＨＩＴ）したかを判定し、ヒットしていればステップ２１８に進み、ヒットしていなければステップ２１９に進む。【００６３】
ステップ２１８では、ヒット情報を「ヒット」に更新し、ステップ２１９に進む。【００６４】
ステップ２１９では、「現在の状態２３を、選択した「次の状態」に更新し、ステップ２１１に戻る。【００６５】
以上の処理を繰り返すことにより、検索対象文書内のキーワードの存在を検出する。【００６６】
図１０は、第１の実施形態における処理を具体例を挙げて説明する図である。【００６７】
図１０の（Ａ）は、図３と同様に、キーワード”ｆｏ”を検索する場合のオートマトンと、デフォルト用メモリ２４およびイベント用メモリ２７内の格納データの内容と、を示す図である。【００６８】
図１０の（Ａ）に示すように、オートマトンの定義されていない（キーワードでない）入力の遷移先を示す点線はすべて0x00ノードに向かっているので、デフォルト用メモリ２４は１エントリで、図１０の（Ｂ）に示すように、遷移先情報0x00と、ヒットしないことを示すヒット（ＨＩＴ）情報と、を格納する。１つのキーワードについて、これだけの情報をデフォルト用メモリ２４に記憶すればよい。【００６９】
イベント用メモリ２７は、８ビットの２５６エントリの１枚構成とし、ハッシング関数として、インデックス（アドレス）＝現在の状態のＩＤｘｏｒ入力文字バイトコード、と定義する。タグは、現在の状態のＩＤのみとし、入力文字バイトコードはタグとして保持しない。これは、入力文字バイトコードはインデックス（アドレス）と現在の状態のＩＤから演算可能であるためで、図７の構成で、イベント用メモリ２７から出力される現在の状態のＩＤと入力文字バイトコード２２から演算して出力データ２８に挿入する演算機構を設ける。もちろんイベント用メモリ２７に入力文字バイトコード２２も格納するようにしてもよいが、その分メモリサイズが大きくなる。【００７０】
図１０の（Ａ）のオートマトンのイベント用メモリ２７の格納データは図１０の（Ｃ）に示すようになる。第１状態が0x00で示され、”ｆ”は0x66であり、そのハッシング（ＸＯＲ）値は0x66であるので、アドレス0x66には、タグとして現在の状態0x00が格納され、遷移先情報として第２状態0x01が格納され、ヒット情報として、０（ヒットせず）が格納される。【００７１】
第２状態0x01からは、”ｆ”0x66で同じ状態を維持し、すなわち第２状態0x01へ遷移するので、そのＸＯＲ値は0x67となり、アドレス0x67にタグ0x01、遷移先情報0x01を格納する。また、第２状態0x01からは、”ｏ”0x6Fで第３状態0x02に遷移するので、そのＸＯＲ値は0x6Eとなり、アドレス0x6Eにタグ0x01、遷移先情報0x02を格納する。さらに、第３状態0x02からは、”ｆ”0x66で第２状態0x01へ遷移するので、そのＸＯＲ値は0x64となり、アドレス0x64にタグ0x02、遷移先情報0x01を格納する。【００７２】
次に、入力文字列”ａｆａｆｆａｆｏ”があり、この中から”ｆｏ”を検索するオートマトン処理を行う場合を説明する。【００７３】
入力"a(0x61)"に対し、イベント用メモリ２７のインデックスは0x61でエントリ未格納であるので、デフォルト用メモリ２４が出力する次の状態（遷移先情報）0x00が選択され、そのヒット情報は０である。現在の状態は、0x00になる。【００７４】
入力"f(0x66)"に対し、イベント用メモリ２７のインデックスは0x66でタグが0x00、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。【００７５】
次の入力"a(0x61)"に対し、イベント用メモリ２７のインデックスは0x60でエントリ未格納であるので、デフォルト用メモリ２４が出力する次の状態（遷移先情報）0x00が選択され、そのヒット情報は０である。現在の状態は、0x00になる。【００７６】
次の入力"f(0x66)"に対し、イベント用メモリ２７のインデックスは0x66でタグが0x00、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。【００７７】
次の入力"f(0x66)"に対し、イベント用メモリ２７のインデックスは0x67でタグが0x01、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。【００７８】
次の入力"a(0x61)"に対し、イベント用メモリ２７のインデックスは0x60でエントリ未格納であるので、デフォルト用メモリ２４が出力する次の状態（遷移先情報）0x00が選択され、そのヒット情報は０である。現在の状態は、0x00になる。【００７９】
次の入力"f(0x66)"に対し、イベント用メモリ２７のインデックスは0x66でタグが0x00、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。【００８０】
次の入力"o(0x6F)"に対し、イベント用メモリ２７のインデックスは0x6Eでタグが0x01、次の状態（遷移先情報）が0x01で、そのヒット情報は１である。タグと現在の状態が一致するので、ヒット情報は１で、現在の状態は、0x01になる。【００８１】
以上が、”ｆｏ”を検索する場合の例であるが、多数のキーワードを検索するオートマトンの場合も同様である。例えば、図１１は、キーワード”ｂｌｕｅ”，”ｒｅｄ”，”ｙｅｌｌｏｗ”，”ｏｒａｎｇｅ”，”ｇｒｅｅｎ”，”ｐｕｒｐｌｅ”，”ｗｈｉｔｅ”を検索するオートマトンを格納したイベント用メモリ２７の利用分布（利用されるインデックス）を示す。図示のようにエントリにまだ余裕があることが分かる。【００８２】
図１１のようなオートマトンを従来技術で実現する場合、約３６ＫＢのメモリサイズが必要であるが、本実施形態であれば、デフォルト用メモリ２４が１４４Ｂ、イベント用メモリ２７が２０４８Ｂの合計２．１９ＫＢであり、メモリサイズを約１／１６に削減できる。【００８３】
一般的に、従来技術では、文字コードサイズをｎ、キーワード文字数をｋ、状態ＩＤサイズをｍとすると、メモリ容量は２n×（ｋ＋１）×ｍで表される。ｎ＝８（ビット）、ｋ＝１００、ｍ＝４とすれば、メモリ容量は約１００ＫＢになる。【００８４】
これに対して、本発明によれば、タグサイズをｓとすれば、メモリ容量は（ｋ＋１）×ｍ＋（ｋ＋α）×（ｓ＋ｍ）である。ｓ＝１００とすれば、メモリ容量は約２．８ＫＢになる。通常、ハッシュ値に偏りがあるので、必要なメモリ量は上記の数倍と成るが、それでも大幅なメモリ容量の低減が可能である。【００８５】
図１２は、本発明の第２実施形態の検索装置の構成を示す図である。第１実施形態の検索装置と異なるのは、レジスタに記憶された改行記号など検索において無視するコード４１と、検索対象文書２１から読み出した入力文字コードとを比較器４２で比較し、一致した時には、その入力文字コードは検索処理を行わず、現在の状態を維持するように、各部に指令することである。これにより、無駄な検索処理を省くことが可能になる。【００８６】
図１３は、本発明の第３実施形態の検索装置の構成を示す図である。第１実施形態の検索装置と異なるのは、第３メモリ５２を設けて、イベント用メモリ２７に収容できなかったキーワードを検索するオートマトンを第３メモリ５２に構築し、選択回路３１の出力と第３メモリ５２の出力の一方を選択する第２選択回路５３が設けられたことである。第３メモリ５２は、図２に示した従来と同様のオートマトンであり、現在の状態２３と入力文字２２をアドレスとしてアクセスされる。言い換えれば、第３メモリ５２は、ハッシュされたアドレスではアクセスされない。【００８７】
イベント用メモリ２７はミスフラグを有し、第３メモリ５２を設けた場合には、ミスフラグを１にする。【００８８】
第１実施形態と同様に、入力文字がイベント用メモリ２７に格納されたキーワード列の文字であるかを判定する。入力文字がイベント用メモリ２７に格納されたキーワード列の文字である場合には、選択回路５３は選択回路３１の出力を選択して出力する。入力文字がイベント用メモリ２７に格納されたキーワード列の文字でなく、メインメモリ５２に構築されたオートマトンのキーワード列の文字である場合には、選択回路５３はメインメモリ５２の出力を選択して出力する。入力文字がイベント用メモリ２７に格納されたキーワード列の文字でなく且つメインメモリ５２に構築されたオートマトンのキーワード列の文字でもない場合には、選択回路５３は選択回路３１の出力を選択して、すなわちデフォルトメモリ２４の出力する次の状態２５を選択して出力する。現在の状態２３は、選択回路５３の出力する次の状態で置き換えられる。なお、図１３では、ヒット情報については説明を省略したが、メインメモリ５２にもヒット情報が格納され、第１実施形態と同様に処理される。【００８９】
メインメモリ５２は、デフォルト用メモリ２４およびイベント用メモリ２７とは独立したメモリとして形成することも、同じメモリ内に形成することも可能であるが、デフォルト用メモリ２４およびイベント用メモリ２７はキャッシュメモリで実現し、メインメモリ５２はそれとは異なるアクセス速度の低いメモリとして実現することが望ましい。また、メインメモリ５２は、ディスク装置内に形成することも可能である。【００９０】
図１４は、本発明の第４実施形態の検索装置の構成を示す図である。第３実施形態の検索装置と異なるのは、ハッシュ器（ＸＯＲ）が異なるハッシュ関数の演算を行う複数のハッシュ器２６Ａ−２６Ｄで構成され、イベント用メモリが複数のハッシュ器２６Ａ−２６Ｄに対応するイベント用メモリユニット２７Ａ−２７Ｄで構成されることである。【００９１】
複数の異なるハッシュ器２６Ａ−２６Ｄを設け、それに対応した複数のイベント用メモリ（領域）２７Ａ−２７Ｄを設けることで、異なるイベント（キーワード列の文字）が同一エントリに割当てられるのをなるべく減らすことができ、エントリ干渉の頻度を低減できる。【００９２】
第４実施形態の場合、複数のイベント用メモリ２７Ａ−２７Ｄへの情報の格納は、メモリごとの空きエントリ数を比較し、一番空きエントリの多いメモリに順に格納し、複数のメモリの空きエントリ数を近似させることが望ましい。【００９３】
以上、本発明の実施形態を説明したが、各種の変形例があり得ることはいうまでもない。例えば、第２実施形態の特徴を第３および第４実施形態に適用することも可能である。
【産業上の利用可能性】
【００９４】
本発明は、どのような決定性有限オートマトンにも適用可能であり、そのようなオートマトンを使用するワープロソフト、データデース検索などに適用可能である。
【図１】
2009050797.tif 000003
【図２】
2009050797.tif 000004
【図３】
2009050797.tif 000005
【図４】
2009050797.tif 000006
【図５】
2009050797.tif 000007
【図６】
2009050797.tif 000008
【図７】
2009050797.tif 000009
【図８】
2009050797.tif 000010
【図９】
2009050797.tif 000011
【図１０】
2009050797.tif 000012
【図１１】
2009050797.tif 000013
【図１２】
2009050797.tif 000014
【図１３】
2009050797.tif 000015
【図１４】
2009050797.tif 000016
【手続補正書】
【提出日】平成22年1月5日(2010.1.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
検索キーワードに応じて生成されたオートマトンに基づいて、検索対象から前記検索キーワードを検索する検索装置であって、
第１メモリ領域と、
第２メモリ領域と、
第１情報及び第２情報から第３情報を生成する情報生成部と、
判定部と、
選択部と、を有し、
前記第１メモリ領域から、前記第１情報に対応する第１状態が読み出され、
前記第２メモリ領域から、前記第３情報に対応する第４情報及び第２状態が読み出され、
前記判定部は、前記第１情報及び前記第２情報からなる第５情報と、前記第４情報とが一致するか、又はしないかを判定し、
前記選択部は、前記判定において一致しない場合に前記第１状態を選択し、前記判定において一致する場合に前記第２状態を選択することを特徴とする検索装置。
【請求項２】
前記第１情報は、検索における現在の状態であり、
前記第２情報は、前記検索対象の文字に対応したコードであり、
前記情報生成部は、前記現在の状態と前記コードを所定の方法でハッシングして前記第３情報を生成し、
前記第４情報は、前記現在の状態に対応したコード、前記検索対象の文字に対応したコード又は、前記現在の状態と前記検索対象の文字とに対応したコードを含み、
前記第１状態および前記第２状態は、次の状態である、ことを特徴とする請求項１に記載の検索装置。
【請求項３】
前記検索対象の文字に対応した入力コードが、所定のコードと一致するかを判定する入力判定部をさらに有し、
前記入力判定部が一致すると判定した入力コードに対しては、前記情報生成部、前記判定部および前記選択部は動作を行わず、現在の状態を更新しないことを特徴とする請求項１に記載の検索装置。
【請求項４】
前記第２メモリ領域は、複数のメモリ領域を有し、
前記情報生成部は、前記複数のメモリ領域のそれぞれに対応したハッシングの方法で、前記第３情報を生成することを特徴とする請求項２に記載の検索装置。
【請求項５】
前記第２メモリ領域に格納できない前記第４情報及び前記第２状態を格納する第３メモリ領域をさらに有し、
前記第２メモリ領域は、前記第３メモリ領域の存在を示すフラグを有することを特徴とする請求項１に記載の検索装置。
【請求項６】
前記第２メモリ領域から読み出された前記第４情報と前記第５情報とが一致しない場合、
前記第３メモリ領域から、前記第３状態が読み出され、
前記選択部は、前記第３状態を選択することを特徴とする請求項５に記載の検索装置。
【請求項７】
検索キーワードに応じて生成されたオートマトンに基づいて、検索対象から前記検索キーワードを検索する検索方法であって、
前記オートマトンの現在の状態に対応する第１アドレスに応じて第１メモリ領域に第１アクセスして第２アドレスを読み出し、
前記第１アドレスと検索対象の文字に対応したコードとをハッシングして第３アドレスを生成し、
前記第３アドレスに応じて第２メモリ領域に第２アクセスして、第４アドレスと第５アドレスからなる第６アドレス情報を読み出し、
前記第１アドレスと前記第４アドレスとを比較し、
前記第１アドレスと前記第４アドレスとが一致しない場合には、前記第２アドレスを、前記オートマトンにおいて遷移する次の状態とし、
前記第１アドレスと前記第４アドレスが一致した場合には、前記第５アドレスを、前記オートマトンにおいて遷移する前記次の状態とすることを特徴とする検索方法。
【請求項８】
検索キーワードに応じて生成されたオートマトンに基づいて、検索対象から前記検索キーワードを検索する検索方法であって、
前記オートマトンの第１ノードに対応する第１アドレスと前記第１ノードに対応するコードとから第１タグを生成し、
前記第１タグと前記第１ノードの次の遷移先となる第２ノードに対応する第２アドレスとからなる情報を第２メモリ領域に格納し、
前記第２メモリ領域の前記遷移先として選択されない第３コードに対応する第３アドレスを第１メモリ領域に格納し、
前記第１メモリ領域から読み出される第１情報と、前記第２メモリ領域から読み出される第２情報とを、入力される前記第１アドレス及び前記コードからなる第２タグと、前記第１タグとの比較に基づいて選択することを特徴とする検索方法。
【請求項９】
前記第２メモリ領域は、複数のメモリ領域を有し、
前記複数のメモリ領域へアクセスするためのアドレスは、それぞれに対応した異なるハッシングの方法で生成される請求項８に記載の検索方法。
【請求項１０】
前記第２メモリ領域の前記複数のメモリ領域への前記第１タグと前記第２アドレスからなる情報の格納は、メモリ領域ごとの空きエントリ数を比較し、一番空きエントリの多いメモリ領域に順に格納し、前記複数のメモリ領域の空きエントリ数が近似していることを特徴とする請求項９に記載の検索方法。
【国際調査報告】
2009050797.tif 000017
2009050797.tif 000018
2009050797.tif 000019
2009050797.tif 000020