(57)【特許請求の範囲】
【請求項１】
圧縮前の文字列と、該文字列に対応する圧縮後の符号とを対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させる第１オートマトンとを記憶する記憶部と、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンを、前記前半ビットによって第１ノードから中間ノードに状態遷移が発生し、前記前半ビットによって前記第１ノードから状態遷移した先の前記中間ノードを遷移元として前記後半ビットによって、第２ノードに状態遷移が発生する第２オートマトンに変換する変換部と、
前記第２オートマトンの各中間ノードの遷移先となる第２ノードを比較し、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合する統合部と、
を有することを特徴とするオートマトン処理装置。
【請求項２】
前記統合部は、前記第２オートマトンに含まれる第１ノードと中間ノードと第２ノードとの状態遷移の関係を集計し、集計した結果を基にして、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合することを特徴とする請求項１に記載のオートマトン処理装置。
【請求項３】
検索キーワードと、圧縮前の文字列および該文字列に対応する圧縮後の符号を対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させ前記検索キーワードの照合する第１オートマトンとを記憶する記憶部と、
前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードに含まれる文字の存在しない前記圧縮辞書の文字列の符号を、前記検索キーワードによる検索に関与しない文字列の符号として特定する特定部と、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンにおいて、前記特定部が特定した符号によって状態遷移する第１ノードを特定し、特定した各第１ノードの状態遷移先を同一の中間ノードに設定することで、前記第１オートマトンを第２オートマトンに変換する変換部と、
を有することを特徴とするオートマトン処理装置。
【請求項４】
前記特定部は、前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードの部分文字列として含まない前記圧縮辞書の文字列、または、前記検索キーワードの接尾辞の何れかと接頭辞の一致しない前記圧縮辞書の文字列、または、前記検索キーワードの接頭辞のいずれかと接尾辞の一致しない前記圧縮辞書の文字列を、前記検索キーワードによる検索に関与しない文字列として特定することを特徴とする請求項３に記載のオートマトン処理装置。
【請求項５】
コンピュータが実行するオートマトン処理方法であって、
圧縮前の文字列と、該文字列に対応する圧縮後の符号とを対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させる第１オートマトンとを前記コンピュータの記憶装置に記憶させ、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンを、前記前半ビットによって第１ノードから中間ノードに状態遷移が発生し、前記前半ビットによって前記第１ノードから状態遷移した先の前記中間ノードを遷移元として前記後半ビットによって、第２ノードに状態遷移が発生する第２オートマトンに変換し、
前記第２オートマトンの各中間ノードの遷移先となる第２ノードを比較し、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合する、
各処理を実行することを特徴とするオートマトン処理方法。
【請求項６】
コンピュータが実行するオートマトン処理方法であって、
検索キーワードと、圧縮前の文字列および該文字列に対応する圧縮後の符号を対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させ前記検索キーワードの照合する第１オートマトンとを記憶装置に記憶させ、
前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードに含まれる文字の存在しない前記圧縮辞書の文字列の符号を、前記検索キーワードによる検索に関与しない文字列の符号として特定し、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンにおいて、特定された符号によって状態遷移する第１ノードを特定し、特定した各第１ノードの状態遷移先を同一の中間ノードに設定することで、前記第１オートマトンを第２オートマトンに変換する
各処理を実行することを特徴とするオートマトン処理方法。
【請求項７】
コンピュータに、
圧縮前の文字列と、該文字列に対応する圧縮後の符号とを対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させる第１オートマトンとを前記コンピュータの記憶装置に記憶させ、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンを、前記前半ビットによって第１ノードから中間ノードに状態遷移が発生し、前記前半ビットによって前記第１ノードから状態遷移した先の前記中間ノードを遷移元として前記後半ビットによって、第２ノードに状態遷移が発生する第２オートマトンに変換し、
前記第２オートマトンの各中間ノードの遷移先となる第２ノードを比較し、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合する、
各処理を実行させることを特徴とするオートマトン処理プログラム。
【請求項８】
コンピュータに、
検索キーワードと、圧縮前の文字列および該文字列に対応する圧縮後の符号を対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させ前記検索キーワードの照合する第１オートマトンとを記憶装置に記憶させ、
前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードに含まれる文字の存在しない前記圧縮辞書の文字列の符号を、前記検索キーワードによる検索に関与しない文字列の符号として特定し、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンにおいて、特定された符号によって状態遷移する第１ノードを特定し、特定した各第１ノードの状態遷移先を同一の中間ノードに設定することで、前記第１オートマトンを第２オートマトンに変換する
各処理を実行させることを特徴とするオートマトン処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オートマトン処理装置等に関する。
【背景技術】
【０００２】
圧縮されたテキストデータに検索キーワードが含まれるか否かを、圧縮されたままの状態で検索する圧縮検索の従来技術が存在する。
【０００３】
従来技術の一例について説明する。検索キーワードＱを「ａｂａａ」とする。圧縮前のテキストデータＴを「ｄａｂａａｂａａｃｄｃｄ」とする。圧縮後のテキストデータＣを「６１０２５」とする。圧縮前のテキストデータＴは、圧縮辞書データに基づいて、圧縮後のテキストデータＣに圧縮される。
【０００４】
図４３は、従来の圧縮辞書データのデータ構造の一例を示す図である。図４３に示すように、この圧縮辞書データは、文字列と圧縮符号とを対応付ける。例えば、文字列「ａａ」は、圧縮符号「０」に圧縮される。
【０００５】
従来技術は、検索キーワードと圧縮辞書とを基にして、オートマトンを生成する。図４４は、従来のオートマトンのデータ構造の一例を示す図である。図４４に示すように、オートマトン５０は、ノード５１、５２、５３、５４、５５を有する。
【０００６】
ノード５１は、初期状態のノードである。現在の状態がノード５１の場合に、符号３、４、５、６、７の何れかにより、現在の状態はノード５１に遷移する。また、現在の状態がノード５１の場合に、符号０または２により、現在の状態はノード５２に遷移する。また、現在の状態がノード５１の場合に、符号１により、現在の状態はノード５３に遷移する。
【０００７】
ノード５２は、文字列「ａ」に対応するノードである。現在の状態がノード５２の場合に、符号０により、現在の状態はノード５２に遷移する。また、現在の状態がノード５２の場合に、符号３、４、５、６、７の何れかにより、現在の状態はノード５１に遷移する。また、現在の状態がノード５２の場合に、符号２により、現在の状態はノード５５に遷移する。ここで、ノード５２からノード５５への遷移は、照合情報付きの遷移となる。照合情報付きの遷移が発生すると、テキストデータＣが検索キーワードＱにヒットしたことになる。また、現在の状態がノード５２の場合に、符号１により、現在の状態はノード５２に遷移する。
【０００８】
ノード５３は、文字列「ａｂ」に対応するノードである。現在の状態がノード５３の場合に、符号１により、現在の状態はノード５３に遷移する。また、現在の状態がノード５３の場合に、符号３、４、５、６、７の何れかにより、現在の状態はノード５１に遷移する。また、現在の状態がノード５３の場合に、符号２により、現在の状態はノード５２に遷移する。また、現在の状態がノード５３の場合に、符号０により、現在の状態はノード５５に遷移する。ここで、ノード５３からノード５５への遷移は、照合情報付きの遷移となる。
【０００９】
ノード５４は、文字列「ａｂａ」に対応するノードである。現在の状態がノード５４の場合に、符号２により、現在の状態はノード５２に遷移する。また、現在の状態がノード５４の場合に、符号３、４、５、６、７の何れかにより、現在の状態はノード５１に遷移する。また、現在の状態がノード５４の場合に、符号０により、現在の状態はノード５２に遷移する。また、現在の状態がノード５４の場合に、符号１により、現在の状態はノード５３に遷移する。ここで、ノード５４からノード５２への遷移およびノード５４からノード５３への遷移は、照合情報付きの遷移となる。
【００１０】
ノード５５は、文字列「ａｂａａ」に対応するノードである。現在の状態がノード５５の場合に、符号０により、現在の状態はノード５２に遷移する。また、現在の状態がノード５５の場合に、符号１により、現在の状態はノード５３に遷移する。また、現在の状態がノード５５の場合に、符号３、４、５、６、７により、現在の状態はノード５１に遷移する。現在の状態がノード５５の場合に、符号２により、現在の状態が再度ノード５５に遷移する。ここで、ノード５５からノード５５への遷移は、照合情報付きの遷移となる。
【００１１】
図４４に示すオートマトン５０は、圧縮後のテキストデータＣの１符号に対して、状態遷移が１回発生する。このようなオートマトン５０を１符号１遷移型のオートマトンと呼ぶ。テキストデータＣを先頭から順にオートマトン５０に入力して行くと、照合情報付きの遷移が２回発生する。この場合には、圧縮前のテキストデータＴに、検索キーワードＱが２回出現することがわかる。
【００１２】
図４４に示したオートマトンを構成するノード５１〜５５のデータ構造について説明する。図４５は、従来のノードのデータ構造の一例を示す図である。図４５に示すように、ノードは、ノードＩＤ５０ａと、遷移先リスト５０ｂと、照合情報リスト５０ｃを有する。ノードＩＤ５０ａは、ノードを一意に識別する情報を格納する。遷移先リスト５０ｂは、全ての符号に対して、その遷移先を与えるリストである。１つの圧縮符号のビット長をｎとすると、リスト長は２ｎとなる。
【００１３】
照合情報リスト５０ｃは、遷移先リスト５０ｂと対応付けられ、遷移が照合情報付きの遷移であるか否かを識別するための情報を格納するリストである。１つの圧縮符号のビット長をｎとすると、リスト長は２ｎとなる。なお、照合情報リスト５０ｃは、検索キーワードが複数の場合には、照合したキーワードＩＤの集合を格納する。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開平１０−２６０９８０号公報
【発明の概要】
【発明が解決しようとする課題】
【００１５】
しかしながら、上述した従来技術では、オートマトンのサイズが大きくなってしまうという問題があった。
【００１６】
図４５に示したように、オートマトンを構成する各ノードは、遷移先リスト５０ｂ、照合情報リスト５０ｃを有しており、遷移先リスト５０ｂおよび照合情報リスト５０ｃのサイズは、圧縮符号のビット長に依存する。このため、圧縮符号の種類が多くなり、１つの圧縮符号のビット長が大きくなると、オートマトンが巨大化してしまう。
【００１７】
開示の技術は、上記に鑑みてなされたものであって、オートマトンのサイズが大きくなることを防止することができるオートマトン処理装置、オートマトン処理方法およびオートマトン処理プログラムを提供すること目的とする。
【課題を解決するための手段】
【００１８】
開示のオートマトン処理装置は、記憶部と、変換部と、統合部とを有する。記憶部は、圧縮前の文字列と該文字列に対応する圧縮後の符号とを対応付けた圧縮辞書圧縮辞書と、圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させる第１オートマトンを記憶する。変換部は、複数の中間ノードを生成し、符号を前半ビットおよび後半ビットに分割する。変換部は、第１オートマトンを、前半ビットによって第１ノードから中間ノードに状態遷移が発生し、後半ビットによって中間ノードから第２ノードに状態遷移が発生する第２オートマトンに変換する。統合部は、第２オートマトンの各中間ノードの遷移先となる第２ノードを比較し、後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合する。
【発明の効果】
【００１９】
開示のオートマトン処理装置によれば、オートマトンのサイズが大きくなることを防止することができるという効果を奏する。
【図面の簡単な説明】
【００２０】
【図１】図１は、本実施例１に係るオートマトン処理装置の構成を示す機能ブロック図である。
【図２】図２は、圧縮辞書のデータ構造の一例を示す図である。
【図３】図３は、圧縮テキストのデータ構造の一例を示す図である。
【図４】図４は、キーワード集合のデータ構造の一例を示す図である。
【図５】図５は、本実施例１に係る１符号１遷移型のオートマトンのデータ構造の一例を示す図である。
【図６】図６は、本実施例１に係る変換部の処理手順を示すフローチャートである。
【図７】図７は、本実施例１に係る変換部の処理を説明するための図（１）である。
【図８】図８は、本実施例１に係る変換部の処理を説明するための図（２）である。
【図９】図９は、本実施例１に係る変換部の処理を説明するための図（３）である。
【図１０】図１０は、本実施例１に係る変換部の処理を説明するための図（４）である。
【図１１】図１１は、本実施例１に係る変換部の処理を説明するための図（５）である。
【図１２】図１２は、１符号２遷移型のオートマトンのノードのデータ構造の一例を示す図である。
【図１３】図１３は、中間ノードのデータ構造の一例を示す図である。
【図１４】図１４は、本実施例１に係る統合部の処理手順を示すフローチャート（１）である。
【図１５】図１５は、本実施例１に係る統合部の処理手順を示すフローチャート（２）である。
【図１６】図１６は、集計表のデータ構造の一例を示す図である。
【図１７】図１７は、本実施例１に係る統合部の処理を説明するための図（１）である。
【図１８】図１８は、本実施例１に係る統合部の処理を説明するための図（２）である。
【図１９】図１９は、本実施例１に係る統合部の処理を説明するための図（３）である。
【図２０】図２０は、本実施例１に係る統合部の処理を説明するための図（４）である。
【図２１】図２１は、本実施例１に係る照合部の処理手順を示すフローチャートである。
【図２２】図２２は、本実施例１に係る照合部の処理を説明するための図（１）である。
【図２３】図２３は、本実施例１に係る照合部の処理を説明するための図（２）である。
【図２４】図２４は、本実施例１に係る照合部の処理を説明するための図（３）である。
【図２５】図２５は、本実施例１に係る照合部の処理を説明するための図（４）である。
【図２６】図２６は、本実施例１に係る照合部の処理を説明するための図（５）である。
【図２７】図２７は、本実施例１に係るオートマトン処理装置の処理手順を示すフローチャートである。
【図２８】図２８は、ステップＳ３０１の処理手順を具体的に示すフローチャートである。
【図２９】図２９は、本実施例２に係るオートマトン処理装置の構成を示す機能ブロック図である。
【図３０】図３０は、本実施例２に係る１符号１遷移型のオートマトンのデータ構造の一例を示す図である。
【図３１】図３１は、本実施例２に係る特定部の処理手順を示すフローチャート（１）である。
【図３２】図３２は、本実施例２に係る特定部の処理手順を示すフローチャート（２）である。
【図３３】図３３は、本実施例２に係る変換部の処理手順を示すフローチャートである。
【図３４】図３４は、本実施例２に係る変換部の処理を説明するための図（１）である。
【図３５】図３５は、本実施例２に係る変換部の処理を説明するための図（２）である。
【図３６】図３６は、本実施例２に係る変換部の処理を説明するための図（３）である。
【図３７】図３７は、本実施例２に係るオートマトン処理装置の処理手順を示すフローチャートである。
【図３８】図３８は、ステップＳ５０３の処理手順を具体的に示すフローチャートである。
【図３９】図３９は、圧縮辞書のその他のデータ構造を示す図（１）である。
【図４０】図４０は、圧縮辞書のその他のデータ構造を示す図（２）である。
【図４１】図４１は、本実施例３に係る特定部の処理手順を示すフローチャートである。
【図４２】図４２は、オートマトン処理プログラムを実行するコンピュータの一例を示す図である。
【図４３】図４３は、従来の圧縮辞書データのデータ構造の一例を示す図である。
【図４４】図４４は、従来のオートマトンのデータ構造の一例を示す図である。
【図４５】図４５は、従来のノードのデータ構造の一例を示す図である。
【発明を実施するための形態】
【００２１】
以下に、本願の開示するオートマトン処理装置、オートマトン処理方法およびオートマトン処理プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００２２】
本実施例１に係るオートマトン処理装置の構成について説明する。図１は、本実施例１に係るオートマトン処理装置の構成を示す機能ブロック図である。図１に示すように、オートマトン処理装置１００は、通信部１１０、入力部１２０、表示部１３０、記憶部１４０、制御部１５０を有する。
【００２３】
通信部１１０は、ネットワークを介して利用者端末とデータ通信を実行する処理部である。通信部１１０は、例えば、各種の通信装置に対応する。通信部１１０は、利用者端末から各種の情報を受信し、受信した情報を制御部１５０に出力する。通信部１１０が受信する各種の情報は、圧縮辞書、キーワード集合、圧縮後テキスト等に対応する。圧縮辞書、キーワード集合、圧縮後テキストに関する説明は後述する。また、通信部１１０は、検索結果を制御部１５０から取得した場合には、検索結果を利用者端末に送信する。
【００２４】
入力部１２０は、利用者などが、各種の情報を入力する入力装置である。例えば、入力部１２０は、キーボード、マウス、タッチパネル等に対応する。入力部１２０は、受け付けた各種データを制御部１５０に出力する。例えば、利用者は、入力部１２０を操作して、圧縮辞書、キーワード集合、圧縮後テキスト等をオートマトン処理装置１００に入力しても良い。
【００２５】
表示部１３０は、各種の情報を表示する表示装置である。例えば、表示部１３０は、ディスプレイやタッチパネルに対応する。例えば、表示部１３０は、制御部１５０から検索結果等を受け付け、受け付けた検索結果を表示する。
【００２６】
記憶部１４０は、圧縮辞書１４１、圧縮後テキスト１４２、キーワード集合１４３、オートマトン１４４、集計表１４５を記憶する。記憶部１４０は、例えば、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ（Flash  Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【００２７】
圧縮辞書１４１は、圧縮前の文字列と、該文字列に対応する圧縮後の符号とを対応付ける情報である。図２は、圧縮辞書のデータ構造の一例を示す図である。図２に示すように、圧縮辞書１４１は、文字列と符号とを対応付ける。例えば、文字列「ａａ」を圧縮すると、符号「０」となる。
【００２８】
圧縮辞書１４１の符号は３ビット表記である。括弧内は符号を１ビットの前半ビットと、２ビットの後半ビットとで表記したものである。例えば、３ビット表記の符号「０」は、前半ビットおよび後半ビットを用いて表記すると「００」となる。
【００２９】
圧縮後テキスト１４２は、圧縮辞書１４１に基づいて圧縮されたテキスト情報である。図３は、圧縮テキストのデータ構造の一例を示す図である。図３に示すように、この圧縮テキスト１４２には、符号列「６１０２５」を有する。この圧縮テキスト１４２を圧縮する前のテキストは「ｄａｂａａｂａａｃｄｃｄ」となる。このテキスト「ｄａｂａａｂａａｃｄｃｄ」を、圧縮時書１４１に基づいて圧縮することで、圧縮テキスト１４２の符号列「６１０２５」が生成される。
【００３０】
キーワード集合１４３は、検索対象となる検索キーワードを有する。図４は、キーワード集合のデータ構造の一例を示す図である。図４に示す例では、キーワード集合１４３には、検索キーワード「ａｂａａ」が含まれる。キーワード集合１４３は、この他にも検索キーワードを含んでも良い。
【００３１】
オートマトン１４４は、キーワード集合１４３の検索キーワードが圧縮後テキスト１４２に含まれるか否かを判定する場合に利用されるオートマトンである。詳細については後述するが、初めに、１符号１遷移型のオートマトンが生成され、この１符号１遷移型のオートマトンが、１符号２遷移型のオートマトンに変換される。本実施例１では、適宜、１符号１遷移型のオートマトンをオートマトン１４４Ａと表記し、１符号２遷移型のオートマトンをオートマトン１４４Ｂと表記する。オートマトン１４４Ａ、１４４Ｂに関する詳細な説明は後述する。
【００３２】
集計表１４５は、オートマトン１４４の状態遷移に関する各種の情報を保持する。集計表１４５に関する詳細な説明は後述する。
【００３３】
制御部１５０は、データ管理部１５１、オートマトン生成部１５２、変換部１５３、統合部１５４、照合部１５５を有する。制御部１５０は、例えば、ＡＳＩＣ（Application  Specific  Integrated  Circuit）や、ＦＰＧＡ（Field  Programmable  Gate  Array）などの集積装置に対応する。また、制御部１５０は、例えば、ＣＰＵやＭＰＵ（Micro  Processing  Unit）等の電子回路に対応する。
【００３４】
データ管理部１５１は、通信部１１０または入力部１２０から、圧縮辞書１４１と、圧縮後テキスト１４２と、キーワード集合１４３とを取得する。データ管理部１５１は、圧縮辞書１４１と、圧縮後テキスト１４２と、キーワード集合１４３とを記憶部１４０に格納する。
【００３５】
オートマトン生成部１５２は、圧縮辞書１４１とキーワード集合１４３とを基にして、１符号１遷移型のオートマトン１４４Ａを生成する処理部である。オートマトン生成部１５２は、検索キーワードに含まれる文字または文字列に対応する複数のノードを生成する。そして、オートマトン生成部１５２は、圧縮辞書１４１の符号によって遷移する遷移元のノードおよび遷移先のノードを特定し、各ノードを対応付けることで、オートマトン１４４Ａを生成する。なお、オートマトン生成部１４４は、どのような従来技術を用いて、オートマトン１４４Ａを生成しても良い。例えば、オートマトン生成部１４４は、特開２０１０−２８７０５２号公報に開示された技術を用いてオートマトン１４４Ａを生成しても良い。
【００３６】
図５は、本実施例１に係る１符号１遷移型のオートマトンのデータ構造の一例を示す図である。図５に示すように、オートマトン１４４Ａは、ノード５１、５２、５３、５４、５５を有する。図５に示すオートマトン１４４Ａは、図４４に示したオートマトン５０に対応するものである。オートマトン１４４Ａに含まれるノード５１〜５５に関する説明は、オートマトン５０に含まれるノード５１〜５５に関する説明と同様である。また、ノード５１〜５５のデータ構造は、図４５で説明したデータ構造に対応する。
【００３７】
変換部１５３は、１符号１遷移型のオートマトン１４４Ａを、１符号２遷移型のオートマトン１４４Ｂに変換する処理部である。
【００３８】
変換部１５３の処理の概要を説明する。変換部１５３は、中間ノードを生成し、ある符号によって遷移する遷移元のノードと遷移先のノードを選択する。変換部１５３は、符号を前半ビットおよび後半ビットに分割する。変換部１５３は、前半ビットによって遷移元のノードから中間ノードに遷移し、後半ビットによって中間ノードから遷移先のノードに遷移するように、遷移元のノードおよび中間ノードの遷移先リストを変更する。このような処理を、オートマトン１４４Ａの各ノードに対して実行することで、変換部１５３は、オートマトン１４４Ａをオートマトン１４４Ｂに変換する。
【００３９】
ここで、変換部１５３の処理手順を具体的に説明する。図６は、本実施例１に係る変換部の処理手順を示すフローチャートである。例えば、図６に示す処理は、オートマトン１４４Ａが生成されたことを契機に実行される。図６に示すように、変換部１５３は、未処理のノードが存在するか否かを判定する（ステップＳ１０１）。変換部１５３は、未処理のノードが存在しない場合には（ステップＳ１０１，Ｎｏ）、処理を終了する。
【００４０】
一方、変換部１５３は、未処理のノードが存在する場合には（ステップＳ１０１，Ｙｅｓ）、未処理のノードのうち、任意のノードを選択してノードｖに設定する（ステップＳ１０２）。
【００４１】
変換部１５３は、ノードｖの遷移先リストにおいて、未処理の符号が存在するか否かを判定する（ステップＳ１０３）。変換部１５３は、未処理の符号が存在しない場合には（ステップＳ１０３，Ｎｏ）、ステップＳ１０１に移行する。
【００４２】
一方、変換部１５３は、未処理の符号が存在する場合には（ステップＳ１０３，Ｙｅｓ）、下記の処理を実行する。変換部１５３は、未処理の符号のうち、任意の１つの符号を符号ｓに設定し、ノードｖの符号ｓに関する遷移先ノードをノードｗ、照合情報をｆに設定する（ステップＳ１０４）。ここでｓ＝ｓ１・ｓ２とする。ｓ１は、符号ｓの前半ビットである。ｓ２は、符号ｓの後半ビットである。
【００４３】
変換部１５３は、ノードｖからｓ１に関する中間ノードｎが生成済みの場合には、中間ノードｎのｓ２に関する遷移先をノードｗに設定する。変換部１５３は、中間ノードｎが未生成の場合には、中間ノードｎを生成し、ノードｖのｓ１に関する遷移先を中間ノードｎに設定する。また、変換部１５３は、中間ノードｎのｓ２に関する遷移先をノードｗに設定する。最後に、変換部１５３は、中間ノードｎに関する照合情報をｆに設定する（ステップＳ１０５）。変換部１５３は、ステップＳ１０５の処理終了後に、ステップＳ１０１に移行する。
【００４４】
次に、変換部１５３が、１符号１遷移型のオートマトン１４４Ａを、１符号２遷移型のオートマトン１４４Ｂに変換する処理の過程について説明する。図７〜図１１は、本実施例１に係る変換部の処理を説明するための図である。
【００４５】
図７について説明する。変換部１５３は、ノード５１に関して変換を実施する。ノード５１は、符号０、２によって、ノード５２に遷移する。ノード５１は、符号１によって、ノード５３に遷移する。ノード５１は、符号３〜７の何れかによって、ノード５１に遷移する。変換部１５３は、符号０、１、２、３、４、５、６、７を前半ビットおよび後半ビットに分割すると、各符号はそれぞれ、（００）、（０１）、（０２）、（０３）、（１０）、（１１）、（１２）、（１３）となる。各符号は、前半ビット０、１と、後半ビット０〜３の組みで表される。
【００４６】
変換部１５３は、前半ビット「０」に関する中間ノード６１を生成する。変換部１５３は、ノード５１の前半ビット「０」に関する遷移先を中間ノード６１に設定する。また、変換部１５３は、中間ノード６１の後半ビット「０」、「２」に関する遷移先をノード５２に設定する。変換部１５３は、中間ノード６１の後半ビット「１」に関する遷移先をノード５３に設定する。変換部１５３は、中間ノード６１の後半ビット「３」に関する遷移先をノード５１に設定する。
【００４７】
変換部１５３は、前半ビット「１」に関する中間ノード６２を生成する。変換部１５３は、ノード５１の前半ビット「１」に関する遷移先を中間ノード６２に設定する。また、変換部１５３は、中間ノード６２の後半ビット「０」、「１」、「２」、「３」に関する遷移先をノード５１に設定する。
【００４８】
図８について説明する。変換部１５３は、ノード５２に関して変換を実施する。ノード５２は、符号０によって、ノード５２に遷移する。ノード５２は、符号１によって、ノード５３に遷移する。ノード５２は、符号２により、ノード５５に遷移する。この符号２による遷移は、照合情報付きの遷移である。ノード５２は、符号３〜７の何れかによって、ノード５１に遷移する。変換部１５３は、各符号を前半ビットと後半ビットに分割する。
【００４９】
変換部１５３は、前半ビット「０」に関する中間ノード６３を生成する。変換部１５３は、ノード５２の前半ビット「０」に関する遷移先を中間ノード６３に設定する。また、変換部１５３は、中間ノード６３の後半ビット「０」に関する遷移先をノード５２に設定する。変換部１５３は、中間ノード６３の後半ビット「１」に関する遷移先をノード５３に設定する。変換部１５３は、中間ノード６３の後半ビット「２」に関する遷移先をノード５５に設定し、照合情報を「１」に設定する。変換部１５３は、中間ノード６３の後半ビット「３」に関する遷移先をノード５１に設定する。
【００５０】
変換部１５３は、前半ビット「１」に関する中間ノード６４を生成する。変換部１５３は、ノード５２の前半ビット「１」に関する遷移先を中間ノード６４に設定する。また、変換部１５３は、中間ノード６４の後半ビット「０」、「１」、「２」、「３」に関する遷移先をノード５１に設定する。
【００５１】
図９について説明する。変換部１５３は、ノード５３に関して変換を実施する。ノード５３は、符号０によって、ノード５５に遷移する。この符号０による遷移は、照合情報付きの遷移である。ノード５３は、符号１によって、ノード５３に遷移する。ノード５３は、符号２によって、ノード５２に遷移する。ノード５３は、符号３〜７の何れかによって、ノード５１に遷移する。変換部１５３は、各符号を前半ビットと後半ビットに分割する。
【００５２】
変換部１５３は、前半ビット「０」に関する中間ノード６５を生成する。変換部１５３は、ノード５３の前半ビット「０」に関する遷移先を中間ノード６５に設定する。また、変換部１５３は、中間ノード６５の後半ビット「０」に関する遷移先をノード５５に設定し、照合情報を「１」に設定する。変換部１５３は、中間ノード６５の後半ビット「１」に関する遷移先をノード５３に設定する。変換部１５３は、中間ノード６５の後半ビット「２」に関する遷移先をノード５２に設定する。変換部１５３は、中間ノード６５の後半ビット「３」に関する遷移先をノード５１に設定する。
【００５３】
変換部１５３は、前半ビット「１」に関する中間ノード６６を生成する。変換部１５３は、ノード５３の前半ビット「１」に関する遷移先を中間ノード６６に設定する。また、変換部１５３は、中間ノード６６の後半ビット「０」、「１」、「２」、「３」に関する遷移先をノード５１に設定する。
【００５４】
図１０について説明する。変換部１５３は、ノード５４に関して変換を実施する。ノード５４は、符号０によって、ノード５２に遷移する。この符号０による遷移は、照合情報付きの遷移である。ノード５４は、符号１によって、ノード５３に遷移する。この符号１による遷移は、照合情報付きの遷移である。ノード５４は、符号２によって、ノード５２に遷移する。ノード５４は、符号３〜７の何れかによって、ノード５１に遷移する。
【００５５】
変換部１５３は、前半ビット「０」に関する中間ノード６７を生成する。変換部１５３は、ノード５４の前半ビット「０」に関する遷移先を中間ノード６７に設定する。また、変換部１５３は、中間ノード６７の後半ビット「０」に関する遷移先をノード５２に設定し、照合情報を「１」に設定する。変換部１５３は、中間ノード６７の後半ビット「１」に関する遷移先をノード５３に設定し、照合情報を「１」に設定する。変換部１５３は、中間ノード６７の後半ビット「２」に関する遷移先をノード５２に設定する。変換部１５３は、中間ノード６７の後半ビット「３」に関する遷移先をノード５１に設定する。
【００５６】
変換部１５３は、前半ビット「１」に関する中間ノード６８を生成する。変換部１５３は、ノード５４の前半ビット「１」に関する遷移先を中間ノード６８に設定する。また、変換部１５３は、中間ノード６８の後半ビット「０」、「１」、「２」、「３」に関する遷移先をノード５１に設定する。
【００５７】
図１１について説明する。変換部１５３は、ノード５５に関して変換を実施する。ノード５５は、符号０、２によって、ノード５２に遷移する。ノード５５は、符号１によって、ノード５３に遷移する。ノード５５は、符号３〜７の何れかによって、ノード５１に遷移する。
【００５８】
変換部１５３は、前半ビット「０」に関する中間ノード６９を生成する。変換部１５３は、ノード５５の前半ビット「０」に関する遷移先を中間ノード６９に設定する。また、変換部１５３は、中間ノード６９の後半ビット「０」に関する遷移先をノード５２に設定する。変換部１５３は、中間ノード６９の後半ビット「１」に関する遷移先をノード５３に設定する。変換部１５３は、中間ノード６９の後半ビット「２」に関する遷移先をノード５５に設定し、照合情報を「１」に設定する。変換部１５３は、中間ノード６９の後半ビット「３」に関する遷移先をノード５１に設定する。
【００５９】
変換部１５３は、前半ビット「１」に関する中間ノード７０を生成する。変換部は、ノード５５の前半ビット「１」に関する遷移先を中間ノード７０に設定する。また、変換部１５３は、中間ノード７０の後半ビット「０」、「１」、「２」、「３」に関する遷移先をノード５１に設定する。
【００６０】
変換部１５３が図６〜図１１に説明した処理を実行することで、１符号１遷移型のオートマトン１４４Ａは、１符号２遷移型のオートマトン１４４Ｂに変換される。なお、変換部１５３は、１符号２遷移型のオートマトン１４４Ｂに変換した後に、１符号１遷移に関する遷移情報を、ノード５１〜５５から削除する。かかる遷移情報は、１符号１遷移型で用いる照合情報リスト、１符号１遷移型で用いる遷移先リストに対応する。
【００６１】
ここで、図１１等に示したオートマトン１４４Ｂのノード５１〜５５のデータ構造および中間ノード６１〜７０のデータ構造について説明する。
【００６２】
図１２は、１符号２遷移型のオートマトンのノードのデータ構造の一例を示す図である。図１２に示すように、ノードは、ノードＩＤ５０ａと、遷移先リスト５０ｄとを有する。ノードＩＤ５０ａは、ノードを一意に識別する情報を格納する。遷移先リスト５０ｄは、各前半ビットに対して、その遷移先を与えるリストである。遷移先リスト５０ｄには、遷移先として中間ノードが指定される。前半ビットのビット長をｂとすると、リスト長は、２ｂとなる。前半ビットのビット長は、分割前のビット長よりも短い。このため、図１２に示す遷移先リスト５０ｄは、図４５に示した遷移先リスト５０ｃよりも短くなり、データ量が少なくなる。また、図１２のノードのデータ構造と、図４５の従来のノードのデータ構造を比較すると、図１２のノードのデータ構造には、照合情報リストが存在しないため、更にデータ量が少なくなる。
【００６３】
図１３は、中間ノードのデータ構造の一例を示す図である。図１３に示すように、中間ノードは、ノードＩＤ６０ａと、遷移先リスト６０ｂと、照合情報リスト６０ｃとを有する。ノードＩＤ６０ａは、中間ノードを一意に識別する情報を格納する。遷移先リスト６０ｂは、各後半ビットに対して、その遷移先を与えるリストである。遷移先リスト６０ｂには、遷移先としてノードが指定される。後半ビットのビット長をｃとすると、リスト長は、２ｃとなる。
【００６４】
照合情報リスト６０ｃは、すべての後半ビットに対して、０または１を割り当てるリストである。照合情報リスト６０ｃのリスト長は、遷移先リスト６０ｂのリスト長と同じである。後半ビットに対応する遷移が、照合情報付きの遷移の場合には、照合情報リスト６０ｃの照合情報に１が設定される。それ以外の場合には、照合情報に０が設定される。また、キーワード集合１４３に複数の検索キーワードが含まれる場合には、どの検索キーワードを照合したのかを識別するために、照合情報に、検索キーワードのＩＤが設定される。
【００６５】
統合部１５４は、オートマトン１４４Ｂを基にして、集計表１４５を生成する。また、統合部１５４は、集計表１４５を基にして、オートマトン１４４Ｂに含まれる中間ノードの遷移先となるノードを比較し、後半ビットの如何によらず同一のノードに遷移する中間ノードを統合する処理部である。
【００６６】
統合部１５４の処理手順を具体的に説明する。図１４および図１５は、本実施例１に係る統合部の処理手順を示すフローチャートである。図１４に示すように、統合部１５４は、オートマトン１４４の全ノードをスキャンし、開始ノードＩＤ、前半ビット、後半ビット、中間ノードのノードＩＤ、終端ノードＩＤ、照合情報の各項目からなる集計表１４５を生成する（ステップＳ１１０）。ここで、開始ノードＩＤは、遷移元のノードＩＤである。終端ノードＩＤは、中間ノードの遷移先のノードＩＤである。
【００６７】
統合部１５４は、集計表１４５において、開始ノードＩＤと前半ビットとの組みが共通するもの同士をグループ化する（ステップＳ１１１）。統合部１５４は、グループの全レコードにおける、後半ビット、終端ノードＩＤ、照合情報の挙動が完全に一致するグループ集合を検出する（ステップＳ１１２）。統合部１５４は、検出したグループ集合を、統合対象の中間ノード集合として決定する（ステップＳ１１３）。
【００６８】
図１５の説明に移行する。統合部１５４は、ｉの値に１を設定し（ステップＳ１２０）、中間ノードの集合Ｍｉが存在するか否かを判定する（ステップＳ１２１）。統合部１５４は、中間ノード集合Ｍｉが存在しない場合には（ステップＳ１２１，Ｎｏ）、処理を終了する。
【００６９】
統合部１５４は、中間ノードの集合Ｍｉが存在する場合には（ステップＳ１２１，Ｙｅｓ）、中間ノードの集合Ｍｉに含まれる中間ノードのうち、１つを代表中間ノードｖに設定する。また、統合部１５４は、その他の中間ノードをｗ１、・・・、ｗｋに設定する（ステップＳ１２２）。統合部１５４は、ｊの値に１を設定する（ステップＳ１２３）。
【００７０】
統合部１５４は、中間ノードｗｊが存在するか否かを判定する（ステップＳ１２４）。統合部１５４は、中間ノードｗｊに向かう全ての遷移の遷移先を、代表中間ノードｖに置き換え、オートマトン１４４から中間ノードｗｊを削除する（ステップＳ１２５）。統合部１５４は、ｊの値に１を加算し（ステップＳ１２６）、ステップＳ１２４に移行する。
【００７１】
ところで、統合部１５４は、ステップＳ１２４において、中間ノードｗｊが存在しない場合には（ステップＳ１２４，Ｎｏ）、ｉの値に１を加算し（ステップＳ１２７）、ステップＳ１２０に移行する。
【００７２】
次に、統合部１５４が生成する集計表１４５について説明する。図１６は、集計表のデータ構造の一例を示す図である。図１６に示すように、集計表１４５は、開始ノードＩＤ、前半ビット、中間ノードのノードＩＤ、後半ビット、終端ノードＩＤ、照合情報を対応付ける。ここで、照合情報は、該当する中間ノードから終端ノードへの遷移が、照合情報付きの遷移であるか否かを示す情報である。照合情報付きの遷移である場合には、照合情報には「ｙｅｓ」が格納される。
【００７３】
図１６の１段目に着目すると、ノード５１は、前半ビット「０」により中間ノード６１に遷移する。そして、中間ノード６１は、後半ビット「０」により、ノード５２に遷移する。かかる遷移に対応する照合情報には何も格納されていないので、該当遷移は、照合情報付きの遷移ではない。
【００７４】
次に、統合部１５４が、中間ノードを統合する処理の過程について説明する。図１７〜図２０は、本実施例１に係る統合部の処理を説明するための図である。
【００７５】
まず、統合部１５４は、集計表１４５において、開始ノードＩＤと前半ビットが共通する中間ノード同士をグループ化する。また、統合部１５４は、グループの全レコードにおいて、後半ビット、終端ノードＩＤ、照合情報の挙動が一致するグループ集合を検出する。
【００７６】
図１７について説明する。ここでは、上記処理の結果として、グループ集合Ｍ１に、ノード６２、６４、６８、７０が含まれるものとする。代表中間ノードｖをノード６６とする。中間ノードｗ１、ｗ２、ｗ３、ｗ４を、中間ノード６２、６４、６６、６８、７０とする。
【００７７】
図１８について説明する。統合部１５４は、ノード５１の遷移先リストにおいて、前半ビット「１」による遷移先を、中間ノードｗ１から代表中間ノードｖに置き換える。そして、統合部１５４は、中間ノードｗ１をオートマトン１４４から削除する。
【００７８】
図１９について説明する。統合部１５４は、ノード５２の遷移先リストにおいて、前半ビット「１」による遷移先を、中間ノードｗ２から代表中間ノードｖに置き換える。そして、統合部１５４は、中間ノードｗ２をオートマトン１４４から削除する。
【００７９】
図２０について説明する。統合部１５４は、ノード５４の遷移先リストにおいて、前半ビット「１」による遷移先を、中間ノードｗ３から代表中間ノードｖに置き換える。そして、統合部１５４は、中間ノードｗ３を削除する。また、統合部１５４は、ノード５５の遷移先リストにおいて、前半ビット「１」による遷移先を、中間ノードｗ４から代表中間ノードｖに置き換える。そして、統合部１５４は、中間ノードｗ３、ｗ４を、オートマトン１４４から削除する。
【００８０】
上記のように、統合部１５４が、図１７〜図２０に示した処理を実行することで、同一グループに属する各中間ノードは、代表中間ノードｖに統合される。
【００８１】
照合部１５５は、圧縮後テキスト１４２に含まれる符号を順次読み出して、オートマトン１４４と順次比較することで、圧縮後テキスト１４２に検索キーワードが含まれているか否かを照合する処理部である。例えば、照合部１５５は、照合を行い、検索キーワードが圧縮後テキスト１４２に何個含まれているか否かを計数する。照合部１５５は、照合結果を、表示部１３０に出力して、照合結果を表示させる。または、照合部１５５は、照合結果を、ネットワークを介して、利用者端末に送信しても良い。
【００８２】
照合部１５５の処理手順を具体的に説明する。図２１は、本実施例１に係る照合部の処理手順を示すフローチャートである。例えば、図２１に示す処理は、圧縮後テキスト１４２が、記憶部１４０に登録された場合に実行される。図２１に示すように、照合部１５５は、圧縮後テキスト１４２の最初の符号をｓに代入する（ステップＳ２０１）。
【００８３】
照合部１５５は、Ａｎｓ（ｑ１）〜Ａｎｓ（ｑｎ）の値を０に設定する（ステップＳ２０２）。Ａｎｓ（ｑ１）〜Ａｎｓ（ｑｎ）は、キーワード集合１４３に含まれる各検索キーワードｑ１〜ｑｎの照合回数に対応する。
【００８４】
照合部１５５は、オートマトン１４４の初期ノードをノードｖに代入する（ステップＳ２０３）。照合部１５５は、ｓが存在するか否かを判定する（ステップＳ２０４）。照合部１５５は、ｓが存在しない場合には（ステップＳ２０４，Ｎｏ）、Ａｎｓ（ｑ１）〜Ａｎｓ（ｑｎ）を出力する（ステップＳ２０５）。
【００８５】
一方、照合部１５５は、ｓが存在する場合には（ステップＳ２０４，Ｙｅｓ）、ｓ＝ｓ１・ｓ２とする。ここで、ｓ＝ｓ１・ｓ２とするとは、符号ｓを、前半ビットｓ１と後半ビットｓ２として捉えることを意味する。照合部１５５は、ノードｖのｓ１に関する遷移先の中間ノードをノードｎとする。照合部１５５は、ノードｎのｓ２に関する照合情報をｆとする（ステップＳ２０６）。
【００８６】
照合部１５５は、ｆが空集合であるか否かを判定する（ステップＳ２０７）。照合部１５５は、ｆが空集合の場合には（ステップＳ２０７，Ｙｅｓ）、ステップＳ２０９に移行する。一方、照合部１５５は、ｆが空集合ではない場合には（ステップＳ２０７，Ｎｏ）、ｆに含まれる全ての検索キーワードに対して、Ａｎｓ（ｑ）を１増やす（ステップＳ２０８）。
【００８７】
照合部１５５は、ノードｎのｓ２に関する遷移先をノードｖに設定する（ステップＳ２０９）。照合部１５５は、圧縮後テキスト１４２における次の符号をｓに設定し（ステップＳ２１０）、ステップＳ２０４に移行する。
【００８８】
次に、照合部１５５が、照合する処理の過程について説明する。図２２〜図２６は、本実施例１に係る照合部の処理を説明するための図である。また、圧縮後テキスト１４２には、図３に示したように「６１０２５」の符号を含む。ここでは一例として、ｑ１＝ａｂａａとする。
【００８９】
図２２について説明する。照合部１５５は、初期ノードをノード５１に設定する。照合部１５５は、圧縮後テキスト１４２の１つ目の符号「６」を読み出し、ｓに「６」を設定する。「６」の前半ビットｓ１は「１」となり、後半ビットｓ２は「２」となる。照合部１５５は、ノード５１の遷移先リストと、前半ビットｓ１＝１とを比較して、ノード５１から中間ノード６６に現在の状態を遷移させる。
【００９０】
照合部１５５は、中間ノード６６の遷移先リストと、後半ビットｓ２＝２とを比較して、中間ノード６６からノード５１に現在の状態を遷移させる。図２２の処理が終了した時点で、Ａｎｓ（ｑ１）の値は０となる。
【００９１】
図２３について説明する。照合部１５５は、圧縮後テキスト１４２の２つ目の符号「１」を読み出し、ｓに「１」を設定する。「１」の前半ビットｓ１は「０」となり、後半ビットは「１」となる。照合部１５５は、ノード５１の遷移先リストと、前半ビットｓ１＝０とを比較して、ノード５１から中間ノード６１に現在の状態を遷移させる。
【００９２】
照合部１５５は、中間ノード６１の遷移先リストと、後半ビットｓ２＝１とを比較して、中間ノード６１からノード５３に現在の状態を遷移させる。図２３の処理が終了した時点で、Ａｎｓ（ｑ１）の値は０となる。
【００９３】
図２４について説明する。照合部１５５は、圧縮後テキスト１４２の３つ目の符号「０」を読み出し、ｓに「０」を設定する。「０」の前半ビットｓ１は「０」となり、後半ビットは「０」となる。照合部１５５は、ノード５３の遷移先リストと、前半ビットｓ１＝０とを比較して、ノード５３から中間ノード６５に現在の状態を遷移させる。
【００９４】
照合部１５５は、中間ノード６５と、後半ビットｓ２＝０とを比較して、中間ノード６５からノード５５に現在の状態を遷移させる。中間ノード６５からノード５５への遷移は、照合情報付きの遷移となる。このため、照合部１５５は、Ａｎｓ（ｑ１）の値に１を加算する。図２４の処理が終了した時点で、Ａｎｓ（ｑ１）の値は１となる。
【００９５】
図２５について説明する。照合部１５５は、圧縮後テキスト１４２の４つ目の符号「２」を読み出し、ｓに「２」を設定する。「２」の前半ビットｓ１は「０」となり、後半ビットは「２」となる。照合部１５５は、ノード５５の遷移先リストと、前半ビットｓ１＝０とを比較して、ノード５５から中間ノード６９に現在の状態を遷移させる。
【００９６】
照合部１５５は、中間ノード６９と、後半ビットｓ２＝２とを比較して、中間ノード６９からノード５５に現在の状態を遷移させる。中間ノード６９からノード５５への遷移は、照合情報付きの遷移となる。このため、照合部１５５は、Ａｎｓ（ｑ１）の値に１を加算する。図２５の処理が終了した時点で、Ａｎｓ（ｑ１）の値は２となる。
【００９７】
図２６について説明する。照合部１５５は、圧縮後テキスト１４２の５つ目の符号「５」を読み出し、ｓに「５」を設定する。「５」の前半ビットｓ１は「１」となり、後半ビットは「１」となる。照合部１５５は、ノード５５の遷移先リストと、前半ビットｓ１＝１とを比較して、ノード５５から中間ノード６６に現在の状態を遷移させる。
【００９８】
照合部１５５は、中間ノード６６と、後半ビットｓ２＝１とを比較して、中間ノード６６からノード５１に現在の状態を遷移させる。図２６の処理が終了した時点で、Ａｎｓ（ｑ１）の値は２となる。照合部１５５は、圧縮後テキスト１４２の符号を全て読み出したので、照合結果「Ａｎｓ（ｑ１）＝２」を出力する。「Ａｎｓ（ｑ１）＝２」は、検索テキストｑ１＝ａｂａａが、圧縮後テキスト１４２に２回現れている旨を示す。
【００９９】
次に、本実施例１に係るオートマトン処理装置１００の処理手順について説明する。図２７は、本実施例１に係るオートマトン処理装置の処理手順を示すフローチャートである。例えば、図２７に示す処理は、圧縮辞書１４１、キーワード集合１４３が記憶部１４０に記憶されたことを契機として実行される。図２７に示すように、オートマトン処理装置１００は、キーワード集合１４３、圧縮辞書１４１、前半ビット長ｂ１、後半ビット長ｂ２を基にして、１符号１遷移型のオートマトン１４４Ａを、１符号２遷移型のオートマトン１４４Ｂに変換する（ステップＳ３０１）。
【０１００】
オートマトン処理装置１００は、１符号２遷移型のオートマトン１４４Ｂを基にして集計表１４５を生成し、統合対象の中間ノードを特定する（ステップＳ３０２）。オートマトン処理装置１００は、中間ノードを統合して１符号２遷移型のオートマトン１４４Ｂを更新する（ステップＳ３０３）。オートマトン処理装置１００は、オートマトン１４４Ｂを出力する（ステップＳ３０４）。
【０１０１】
図２７のステップＳ３０１に示した処理の処理手順を具体的に説明する。図２８は、ステップＳ３０１の処理手順を具体的に示すフローチャートである。図２８に示すように、オートマトン処理装置１００は、キーワード集合１４３と圧縮辞書１４１とから１符号１遷移型のオートマトン１４４Ａを作成する（ステップＳ３１０）。
【０１０２】
オートマトン処理装置１００は、前半ビット長ｂ１と後半ビット長ｂ２とを用いて、１符号１遷移型のオートマトン１４４Ａを、１符号２遷移型のオートマトン１４４Ｂに変換する（ステップＳ３１１）。オートマトン処理装置１００は、１符号２遷移型のオートマトン１４４Ｂを出力する（ステップＳ３１２）。ステップＳ３１１に示す処理は、図６に示した変換部１５３の処理に対応する。
【０１０３】
ところで、図２７のステップＳ３０２に示す処理の詳細は、図１４に示した統合部１５４の処理に対応する。図２７のステップＳ３０３に示す処理の詳細は、図１５に示した統合部１５４の処理に対応する。
【０１０４】
次に、本実施例１に係るオートマトン処理装置１００の効果について説明する。オートマトン処理装置１００は、中間ノードを生成し、符号の前半ビットで中間ノードに遷移し、符号の後半ビットで中間ノードからノードに遷移させることで、１符号１遷移型のオートマトン１４４Ａを、１符号２遷移型のオートマトン１４４Ｂに変換する。そして、オートマトン処理装置１００は、オートマトンの各中間ノードの遷移先となるノードを比較し、後半ビットの如何によらず同一のノードに遷移する中間ノードを統合する。このため、オートマトン処理装置１００によれば、オートマトンのサイズが大きくなることを防止することができるという効果を奏する。
【０１０５】
例えば、１符号１遷移型のオートマトン１４４Ａを、図５に示すものとし、単一のノードのサイズを「１６」とすると、オートマトン１４４Ａの合計サイズは「８０」となる。ここで、オートマトン処理装置１００が、中間ノードを生成して、１符号１遷移型のオートマトン１４４Ａを、１符号２遷移型のオートマトン１４４Ｂに変換すると、例えば、図１１に示すものとなる。ノードは、遷移先リストが小さくなるので、単一のノードのサイズは、例えば「２」となる。しかし、中間ノードが新たに生成されており、中間ノードのサイズは「８」となる。このため、オートマトン１４４Ｂの合計サイズは「９０」となり、図５のものと比較してサイズが大きくなってしまう。ここで、オートマトン処理装置１００が、中間ノードを統合することで、オートマトン１４４Ｂは、図２０に示すものとなる。図２０のものは、図１１のものと比較して、中間ノードの数が減っており、合計サイズは「５８」となる。
【０１０６】
また、オートマトンのサイズが大きくなることを防止するため、照合に要する時間を短縮することができる。１符号２遷移でオートマトンを照合する場合には、一見、既存技術よりも検索が遅くなるように見える。しかし、実験結果によれば、圧縮辞書１４１のサイズが４０９６の場合、上述の１符号２遷移のオートマトンを用いた方が、１符号１遷移のオートマトンを用いるよりも、１．２倍高速に動作する。オートマトンの省領域化に伴うキャッシュミス率の低下の結果、高速化できたものと考えられる。
【実施例２】
【０１０７】
次に、本実施例２に係るオートマトン処理装置の構成について説明する。図２９は、本実施例２に係るオートマトン処理装置の構成を示す機能ブロック図である。図２９に示すように、このオートマトン処理装置２００は、通信部２１０、入力部２２０、表示部２３０、記憶部２４０、制御部２５０を有する。
【０１０８】
通信部２１０、入力部２２０、表示部２３０に関する説明は、図１に示した通信部１１０、入力部１２０、表示部１３０に関する説明と同様である。
【０１０９】
記憶部２４０は、圧縮辞書２４１、圧縮後テキスト２４２、キーワード集合２４３、オートマトン２４４を記憶する。記憶部２４０は、例えば、ＲＡＭ、ＲＯＭ、フラッシュメモリなどの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【０１１０】
圧縮辞書２４１は、圧縮前の文字列と、該文字列に対応する圧縮後の符号とを対応付ける情報である。圧縮辞書のデータ構造は、図２に示したものと同様である。
【０１１１】
圧縮後テキスト２４２は、圧縮辞書２４１に基づいて圧縮されたテキスト情報である。圧縮後テキスト２４２のデータ構造は、図３に示したものと同様である。
【０１１２】
キーワード集合２４３は、検索対象となる検索キーワードを有する。キーワード集合２４３のデータ構造は、図４に示したものと同様である。
【０１１３】
オートマトン２４４は、キーワード集合２４３の検索キーワードが圧縮後テキスト２４２に含まれるか否かを判定する場合に利用されるオートマトンである。本実施例２では、適宜、１符号１遷移型のオートマトンをオートマトン２４４Ａと表記し、１符号２遷移型のオートマトンをオートマトン２４４Ｂと表記する。オートマトン２４４のデータ構造は後述する。
【０１１４】
制御部２５０は、データ管理部２５１、オートマトン生成部２５２、特定部２５３、変換部２５４、照合部２５５を有する。制御部２５０は、例えば、ＡＳＩＣや、ＦＰＧＡなどの集積装置に対応する。また、制御部２５０は、例えば、ＣＰＵやＭＰＵ等の電子回路に対応する。
【０１１５】
データ管理部２５１は、通信部２１０または入力部２２０から、圧縮辞書２４１と、圧縮後テキスト２４２と、キーワード集合２４３とを取得する。データ管理部２５１は、圧縮辞書２４１と、圧縮後テキスト２４２と、キーワード集合２４３とを記憶部２４０に格納する。
【０１１６】
オートマトン生成部２５２は、圧縮辞書２４１とキーワード集合２４３とを基にして、１符号１遷移型のオートマトン２４４Ａを生成する処理部である。オートマトン生成部２５２の具体的な処理の説明は、実施例１のオートマトン生成部１５２の説明と同様である。
【０１１７】
図３０は、本実施例２に係る１符号１遷移型のオートマトンのデータ構造の一例を示す図である。図３０に示すように、オートマトン２４４Ａは、ノード５１、５２、５３、５４、５５を有する。図３０に示すオートマトン２４４Ａは、図４４に示したオートマトン５０に対応するものである。オートマトン２４４Ａに含まれるノード５１〜５５に関する説明は、オートマトン５０に含まれるノード５１〜５５に関する説明と同様である。また、ノード５１〜５５のデータ構造は、図４５で説明したデータ構造に対応する。
【０１１８】
特定部２５３は、圧縮辞書２４１とキーワード集合２４３の検索キーワードとを基にして、検索キーワードによる検索に関与しない文字列の符号を特定する処理部である。特定部２５３は、特定結果を変換部２５４に出力する。
【０１１９】
ここで、特定部２５３の処理手順を具体的に説明する。図３１および図３２は、本実施例２に係る特定部の処理手順を示すフローチャートである。特定部２５３は、図３１に示す処理を実行した後に、図３２に示す処理を実行する。図３１の処理では、特定部２５３は、圧縮辞書２４１に含まれる符号のうち、検索キーワードによる検索に関与しない符号集合Ｓを特定する。
【０１２０】
図３１に示すように、特定部２５３は、ｓに値０を設定し（ステップＳ４０１）、符号集合Ｓを空集合に設定する（ステップＳ４０２）。特定部２５３は、キーワード集合２４３に含まれる全ての文字の集合をΣとする（ステップＳ４０３）。
【０１２１】
特定部２５３は、符号ｓが存在するか否かを判定する（ステップＳ４０４）。特定部２５３は、符号ｓが存在しない場合には（ステップＳ４０４，Ｎｏ）、符号集合Ｓを出力する（ステップＳ４０５）。
【０１２２】
一方、特定部２５３は、符号ｓが存在する場合には（ステップＳ４０４，Ｙｅｓ）、符号ｓが表す文字列が、Σの文字列の何れかを含むか否かを判定する（ステップＳ４０６）。特定部２５３は、Σの文字列の何れかを含む場合には（ステップＳ４０６，Ｙｅｓ）、ステップＳ４０８に移行する。
【０１２３】
一方、特定部２５３は、Σの文字列の何れかを含まない場合には（ステップＳ４０６，Ｎｏ）、符号ｓを符号集合Ｓに追加する（ステップＳ４０７）。特定部２５３は、符号ｓに１を加算し（ステップＳ４０８）、ステップＳ４０４に移行する。
【０１２４】
次に、図３２の処理について説明する。図３２の処理では、特定部２５３は、前半ビットのみで特定可能な符号を検出する。
【０１２５】
図３２に示すように、特定部２５３は、前半ビットｓ１の値を０に設定する（ステップＳ４１０）。特定部２５３は、「ｓ１≦２ｂ１−１」の条件が満たされない場合には（ステップＳ４１１，Ｎｏ）、符号集合Ｓを出力する（ステップＳ４１２）。ｂ１は、前半ビット長である。
【０１２６】
一方、特定部２５３は、「ｓ１≦２ｂ１−１」の条件が満たされる場合には（ステップＳ４１１，Ｙｅｓ）、前半ビットがｓ１である符号ｓ（ｓ１・０≦ｓ≦ｓ１・（２ｂ２−１））の全てが符号集合Ｓに含まれるか否かを判定する（ステップＳ４１３）。ｂ２は、後半ビット長である。
【０１２７】
特定部２５３は、前半ビットがｓ１である符号ｓ（ｓ１・０≦ｓ≦ｓ１・（２ｂ２−１））の全てが符号集合Ｓに含まれる場合には（ステップＳ４１３，Ｙｅｓ）、ステップＳ４１５に移行する。
【０１２８】
特定部２５３は、前半ビットがｓ１である符号ｓ（ｓ１・０≦ｓ≦ｓ１・（２ｂ２−１））の全てが符号集合Ｓに含まれない場合には（ステップＳ４１３，Ｎｏ）、下記の処理を行う。特定部２５３は、前半ビットがｓ１である符号集合Ｓの要素を符号集合Ｓから全て削除する（ステップＳ４１４）。特定部２５３は、前半ビットｓ１に１を加算し（ステップＳ４１５）、ステップＳ４１１に移行する。
【０１２９】
ここで、特定部２５３の処理の一例について説明する。キーワード集合２４３に含まれる文字列を「ａｂａａ」とする。特定部２５３は、キーワード集合２４３の文字列に含まれる文字集合をΣ＝｛ａ、ｂ｝とする。特定部２５３は、文字集合Σと、圧縮辞書２４１の文字列とを基にして、文字集合の文字を含まない文字列の符号を符号集合として特定する。例えば、文字ａも文字ｂも含まない文字列の符号は、「４，５，６，７」となる。このため、特定部２５３は、符号集合Ｓとして、符号「４，５，６，７」を特定する。
【０１３０】
続いて、特定部２５３は、符号集合Ｓの符号「４，５，６，７」のうち、前半ビットのみで特定可能な符号集合Ｓを特定する。符号集合Ｓに含まれる符号「４，５，６，７」は、前半ビット「１」で特定可能であるため、特定部２５３は、符号集合Ｓの各符号「４，５，６，７」の何れも削除しない。特定部２５３は、符号集合Ｓの情報を、変換部２５４に出力する。
【０１３１】
変換部２５４は、１符号１遷移型のオートマトン２４４Ａを、１符号２遷移型のオートマトン２４４Ｂに変換する処理部である。
【０１３２】
変換部２５４は、統合中間ノードを生成し、符号集合Ｓに含まれる符号によって状態遷移するノードを特定する。そして、変換部２５４は、特定したノードの状態遷移先を、統合中間ノードに設定することで、１符号１遷移型のオートマトン２４４Ａを、１符号２遷移型のオートマトン２４４Ｂに変換する。
【０１３３】
なお、変換部２５４は、圧縮辞書２４１に含まれる符号のうち、符号集合Ｓに含まれない符号に関する遷移を、中間ノードを作って生成する。かかる処理は、実施例１に示した変換部１５３の処理と同様である。
【０１３４】
ここで、変換部２５４の処理手順を具体的に説明する。図３３は、本実施例２に係る変換部の処理手順を示すフローチャートである。図３３に示すように、変換部２５４は、未処理の統合中間ノードが、統合中間ノード集合Ｎに存在するか否かを判定する（ステップＳ４２０）。この統合中間ノード集合Ｎの初期値には、異なる前半ビット毎の統合中間ノードが存在する。
【０１３５】
変換部２５４は、未処理の統合中間ノードが、統合中間ノード集合Ｎに存在しない場合には（ステップＳ４２０，Ｎｏ）、処理を終了する。
【０１３６】
一方、変換部２５４は、未処理の統合中間ノードが、統合中間ノード集合Ｎに存在する場合には（ステップＳ４２０，Ｙｅｓ）、未処理の統合中間ノードをｎｃｕｒ＝ｎ（ｓ１）とする（ステップＳ４２１）。
【０１３７】
変換部２５４は、オートマトン２４４の全てのノードｖに対して、ノードｖの前半ビットｓ１に関する遷移先をｎｃｕｒに設定する（ステップＳ４２２）。変換部２５４は、統合中間ノードｎｃｕｒにおける全ての後半ビットに関する遷移先を、オートマトン２４４の初期状態のノードに設定し（ステップＳ４２３）、ステップＳ４２０に移行する。
【０１３８】
次に、変換部２５４が、１符号１遷移型のオートマトン２４４Ａを、１符号２遷移型のオートマトン２４４Ｂに変換する処理の過程について説明する。図３４〜図３６は、本実施例２に係る変換部の処理を説明するための図である。一例として、変換部２５４が、特定部２５３から取得する符号集合Ｓには、符号「４、５、６、７」が含まれているものとする。また、初期のオートマトン２４４Ａのデータ構造を、図３０に示すものとする。
【０１３９】
符号集合Ｓには、符号「４、５、６、７」が含まれている。各符号を前半ビット、後半ビットで表すと、１０、１１、１２、１３となり、前半ビットは１種類のみとなる。このため、変換部２５４は、統合中間ノードを１つ生成すればよい。
【０１４０】
図３４について説明する。変換部２５４は、統合中間ノード８０を生成する。統合中間ノード８０のデータ構造は、図１３に示した中間ノードのデータ構造と同様である。
【０１４１】
図３５について説明する。変換部２５４は、オートマトン２４４のノード５１〜５５に関して、前半ビット「１」に関する遷移先を統合中間ノード８０に設定する。変換部２５４は、統合中間ノード８０の後半ビット０、１、２、３に関する遷移先を、初期状態となるノード５１に設定する。
【０１４２】
図３６について説明する。変換部２５４は、圧縮辞書２４１に含まれる符号のうち、符号集合Ｓに含まれない符号に関する遷移を、中間ノードを作って生成する。変換部２５４は、中間ノード６１、６３、６５、６７、６９を生成し、各ノードと接続する。中間ノード６１、６３、６５、６７、６９に関する説明は、図１１に説明したものと同様である。
【０１４３】
変換部２５４が図３４〜図３６に説明した処理を実行することで、１符号１遷移型のオートマトン２４４Ａは、１符号２遷移型のオートマトン２４４Ｂに変換される。なお、変換部２５４は、１符号２遷移型のオートマトン２４４Ｂに変換した後に、１符号１遷移に関する遷移情報を、ノード５１〜５５から削除する。かかる遷移情報は、１符号１遷移型で用いる照合情報リスト、１符号１遷移型で用いる遷移先リストに対応する。
【０１４４】
照合部２５５は、圧縮テキスト２４２に含まれる符号を順次読み出して、オートマトン２４４と順次比較することで、圧縮テキスト２４２に検索キーワードが含まれているか否かを照合する処理部である。照合部２５５に関する説明は、実施例１の照合部１５５と同様である。
【０１４５】
次に、本実施例２に係るオートマトン処理装置２００の処理手順について説明する。図３７は、本実施例２に係るオートマトン処理装置の処理手順を示すフローチャートである。例えば、図３７に示す処理は、圧縮辞書２４１、キーワード集合２４３が記憶部２４０に記憶されたことを契機として実行される。図３７に示すように、オートマトン処理装置２００は、キーワード集合２４３と、圧縮辞書２４１とを基にして、無関与の符号を検出し、無関与の符号の集合を、符号集合Ｓに設定する（ステップＳ５０１）。オートマトン処理装置２００は、符号集合Ｓの符号のうち、前半ビットのみで特定可能な符号を抽出し、抽出した符号の集合を新たな符号集合Ｓに設定する（ステップＳ５０２）。
【０１４６】
オートマトン処理装置２００は、符号集合Ｓの符号のうち、前半ビット長ｂ１、後半ビット長ｂ２から、１符号２遷移型のオートマトン２４４Ｂを生成する。オートマトン処理装置２００は、オートマトンを生成する際に、符号集合Ｓの任意の符号に関する遷移は、統合中間ノードを用いて生成する（ステップＳ５０３）。オートマトン処理装置２００は、オートマトン２４４Ｂを出力する（ステップＳ５０４）。
【０１４７】
図３７のステップＳ５０１に示した処理の詳細は、図３１に示した処理に対応する。図３７のステップＳ５０２に示した処理の詳細は、図３２に示した処理に対応する。
【０１４８】
図３７のステップＳ５０３に示した処理の処理手順を具体的に説明する。図３８は、ステップＳ５０３の処理手順を具体的に示すフローチャートである。図３８に示すように、オートマトン処理装置２００は、キーワード集合２４３と圧縮辞書２４１から、１符号１遷移型のオートマトン２４４Ａを生成する（ステップＳ５１０）。
【０１４９】
オートマトン処理装置２００は、符号集合Ｓの全符号における相異なる前半ビットｓ１の数だけ、統合中間ノードｎを生成する。また、オートマトン処理装置２００は、統合中間ノードｎの集合を統合中間ノード集合Ｎとする（ステップＳ５１１）。
【０１５０】
オートマトン処理装置２００は、オートマトン２４４の全てのノードから、符号集合Ｓに含まれる全符号に関する遷移を作成する（ステップＳ５１２）。ステップＳ５１２では、統合中間ノードを通って初期状態に向かう遷移を作成する。
【０１５１】
オートマトン処理装置２００は、オートマトンの全てのノードから、符号集合Ｓに含まれない全符号に関する遷移を、中間ノードを作って作成する（ステップＳ５１３）。オートマトン処理装置２００は、オートマトン２４４から１符号１遷移に関する遷移情報を削除する（ステップＳ５１４）。
【０１５２】
図３８に示したステップＳ５１２に示した処理の詳細は、図３３に示した処理に対応する。図３８に示したステップＳ５１３に示した処理の詳細は、実施例１の図６に示した処理に対応する。
【０１５３】
次に、本実施例２に係るオートマトン処理装置２００の効果について説明する。オートマトン処理装置２００は、検索キーワードによる検索に関与しない文字列の符号を集めた符号集合Ｓを作成し、統合中間ノードを生成する。そして、オートマトン処理装置２００は、ノードの状態遷移先を、統合中間ノードに設定することで、１符号１遷移型のオートマトン２４４Ａを、１符号２遷移型のオートマトン２４４Ｂに変換する。このため、オートマトン処理装置２００によれば、オートマトンのサイズが大きくなることを防止することができるという効果を奏する。また、オートマトン処理装置２００によれば、中間ノードを生成した後に、各中間ノードを統合する処理を行わず、初めから統合中間ノードを生成するため、統合に係る処理負荷を軽減することができる。
【実施例３】
【０１５４】
以下では、上述した実施例１、２以外の処理を、実施例３として説明する。
【０１５５】
まず、圧縮辞書２４１のデータ構造を他の例に置き換えて、特定部２５３の処理を説明する。図３９および図４０は、圧縮辞書のその他のデータ構造を示す図である。図３９の圧縮辞書２４１に対して、特定部２５３が検索に関与しない文字列の符号を特定すると、符号２、３、６、７が、検索に関与しない文字列の符号となる。ただし、このままでは、検索に関与しない文字列の符号の前半ビットと、検索に関与する文字列の符号の前半ビットとが同じになってしまう。
【０１５６】
このため、特定部２５３は、検索に関与する文字列の符号の前半ビットと、検索に関与しない文字列の符号の前半ビットとが異なるように、各文字列の前半ビットおよび後半ビットを修正する。図４０に示す例では、特定部２５３は、符号２、３の前半ビットおよび後半ビットを「１０」、「１１」に修正する。特定部２５３は、符号４、５の前半ビットおよび後半ビットを「２０」、「２１」に修正する。特定部２５３は、符号６、７の前半ビットおよび後半ビットを「３０」、「３１」に修正する。
【０１５７】
特定部２５３が、上記処理を実行することで、検索に関与する文字列の符号の前半ビットと、検索に関与しない文字列の符号の前半ビットとが異なるようになる。このため、実施例２に示したように、中間ノードを利用して、オートマトン２４４のサイズを小さくすることができる。
【０１５８】
次に、特定部２５３のその他の処理について説明する。特定部２５３は、圧縮辞書２４１とキーワード集合２４３の検索キーワードとを基にして、以下に示す条件により、検索キーワードに関与しない文字列の符号を特定しても良い。
【０１５９】
例えば、特定部２５３は、検索キーワードの部分文字列として含まない圧縮辞書２４１の文字列の符号を、検索キーワードに関与しない符号として特定する。特定部２５３は、検索キーワードの接尾辞の何れかと接頭辞が一致しない圧縮辞書２４１の文字列の符号を、検索キーワードに関与しない符号として特定する。特定部２５３は、検索キーワードの接頭辞のいずれかと接尾辞が一致しない圧縮辞書２４１の文字列の符号を、検索キーワードに関与しない符号として特定する。特定部２５３は、特定した文字列の符号の集合を、符号集合Ｓとして、変換部２５４に出力する。
【０１６０】
具体例を用いて、特定部２５３の処理を説明する。ここでは、検索キーワードを「ａｂａａ」とする。また、圧縮辞書のデータ構造を、図２に示すものとする。検索キーワード「ａｂａａ」の接頭辞は「ａ」、「ａｂ」、「ａｂａ」となる。検索キーワード「ａｂａａ」の接尾辞は「ａ」、「ａａ」、「ｂａａ」となる。
【０１６１】
特定部２５３は、圧縮辞書２４１の１段目（ｓ＝０）の文字列「ａａ」が検索キーワードに関与しない検索キーワードか否かを判定する。文字列「ａａ」は、検索キーワードの接尾辞「ａａ」に一致する。このため、特定部２５３は、文字列「ａａ」を、検索キーワードに関与する検索キーワードと判定する。
【０１６２】
特定部２５３は、圧縮辞書２４１の２段目（ｓ＝１）の文字列「ａｂ」が検索キーワードに関与しない検索キーワードか否かを判定する。文字列「ａｂ」は、検索キーワードの接頭辞「ａｂ」に一致する。このため、特定部２５３は、文字列「ａｂ」を、検索キーワードに関与する検索キーワードと判定する。
【０１６３】
特定部２５３は、圧縮辞書２４１の３段目（ｓ＝２）の文字列「ｂａａ」が検索キーワードに関与しない検索キーワードか否かを判定する。文字列「ｂａａ」の接尾辞「ａ」が、検索キーワードの接頭辞「ａ」と一致する。このため、特定部２５３は、文字列「ｂａａ」を、検索キーワードに関与する検索キーワードと判定する。
【０１６４】
特定部２５３は、圧縮辞書２４１の４段目（ｓ＝３）の文字列「ｂｃａｄ」が検索キーワードに関与しない検索キーワードか否かを判定する。文字列「ｂｃａｄ」は、３条件を満たさないので、特定部２５３は、文字列「ｂｃａｄ」を、検索キーワードに関与しない検索キーワードと判定する。
【０１６５】
ここで３条件の１つ目は、圧縮辞書２４１の文字列が、検索キーワードの部分文字列として含むという条件である。３条件の２つ目は、圧縮辞書２４１の文字列の接頭辞が、検索キーワードの接尾辞の何れかと一致するという条件である。３条件の３つ目は、圧縮辞書２４１の文字列の接尾辞が、検索キーワードの接頭辞の何れかと一致するという条件である。
【０１６６】
特定部２５３は、圧縮辞書２４２の５段目（ｓ＝４）から８段目（ｓ＝７）の文字列に対しても、検索キーワードに関与しない検索キーワードか否かを判定する。各文字列は、３条件を満たさない。このため、特定部は、文字列「ｃｃ」、「ｃｄｃｄ」、「ｄ」、「ｄｃｃ」を、検索キーワードに関与しない検索キーワードと判定する。
【０１６７】
特定部２５３は、上記の処理を実行することで、符号集合Ｓ「３、４、５、６、７」を特定する。ここで、符号「３」の前半ビットは「０」であり、符号「４〜７」の前半ビットは「１」である。前半ビットが０である符号の数が１つなので、特定部２５３は、符号集合Ｓから「３」を削除する。特定部２５３は、最終的に、符号集合Ｓ「４、５、６、７」を変換部２５４に出力する。
【０１６８】
実施例３に係る特定部２５３の処理手順について説明する。図４０は、本実施例３に係る特定部の処理手順を示すフローチャートである。図４０に示すように、特定部２５３は、ｓの値に０を設定し（ステップＳ６０１）、ｉの値に１を設定する（ステップＳ６０２）。
【０１６９】
特定部２５３は、ｑｉはキーワード集合２４３に属する（ｑｉ∈キーワード集合２４３）か否かを判定する（ステップＳ６０３）。特定部２５３は、ｑｉがキーワード集合２４３に属さない場合には（ステップＳ６０３，Ｎｏ）、符号集合Ｓを出力する（ステップＳ６０４）。
【０１７０】
一方、特定部２５３は、ｑｉがキーワード集合２４３に属する場合には（ステップＳ６０３，Ｙｅｓ）、「ｓ≦２ａ−１」の条件を満たすか否かを判定する（ステップＳ６０５）。特定部２５３は、「ｓ≦２ａ−１」の条件を満たさない場合には（ステップＳ６０５，Ｎｏ）、ｉに１を加算する（ステップＳ６０６）。特定部２５３は、ｓの値を０に設定し（ステップＳ６０７）、ステップＳ６０３に移行する。なお、ステップＳ６０５のａは、圧縮に用いる符号の符号長である。
【０１７１】
特定部２５３は、「ｓ≦２ａ−１」の条件を満たす場合には（ステップＳ６０５，Ｙｅｓ）、組（ｑｉ、ｐ）が３条件の何れも満たさない場合に、符号ｓを符号集合Ｓに追加する（ステップＳ６０８）。特定部２５３は、ｓに１を加算し（ステップＳ６０９）、ステップＳ６０５に移行する。なお、ステップＳ６０８のｐは、符号ｓに対応する圧縮前の文字列である。
【０１７２】
実施例３の特定部２５３は、３条件を満たすか否かにより、検索キーワードによる検索に関与しない文字列を特定するので、実施例２の特定部２５３と比較して、検索に関与しない文字列をより正確に特定することが可能となる。
【０１７３】
次に、実施例１、２に示したオートマトン処理装置１００、２００と同様の機能を実現するオートマトン処理プログラムを実行するコンピュータの一例を説明する。図４２は、オートマトン処理プログラムを実行するコンピュータの一例を示す図である。
【０１７４】
図４２に示すように、コンピュータ３００は、各種演算処理を実行するＣＰＵ３０１と、ユーザからのデータの入力を受け付ける入力装置３０２と、ディスプレイ３０３を有する。また、コンピュータ３００は、記憶媒体からプログラム等を読取る読み取り装置３０４と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインターフェース装置３０５とを有する。また、コンピュータ３００は、各種情報を一時記憶するＲＡＭ３０６と、ハードディスク装置３０７を有する。そして、各装置３０１〜３０７は、バス３０８に接続される。
【０１７５】
ハードディスク装置３０７は、例えば、オートマトン生成プログラム３０７ａ、変換プログラム３０７ｂ、統合プログラム３０７ｃ、照合プログラム３０７ｄ、特定プログラム３０７ｅを有する。ＣＰＵ３０１は、各プログラム３０７ａ〜３０７ｅを読み出して、ＲＡＭ３０６に展開する。
【０１７６】
オートマトン生成プログラム３０７ａは、オートマトン生成プロセス３０６ａとして機能する。変換プログラム３０７ｂは、変換プロセス３０６ｂとして機能する。統合プログラム３０７ｃは、統合プロセス３０６ｃとして機能する。照合プログラム３０７ｄは、照合プロセス３０６ｄとして機能する。特定プログラム３０７ｅは、特定プロセス３０６ｅとして機能する。
【０１７７】
例えば、オートマトン生成プロセス３０６ａは、オートマトン生成部１５１、２５２に対応する。変換プロセス３０６ｂは、変換部１５３、２５４に対応する。統合プロセス３０６ｃは、統合部１５４に対応する。照合プロセス３０６ｄは、照合部１５５、２５５に対応する。特定プロセス３０６ｅは、特定部２５３に対応する。
【０１７８】
なお、各プログラム３０７ａ〜３０７ｅについては、必ずしも最初からハードディスク装置３０７に記憶させておかなくてもよい。例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ３００がこれらから各プログラム３０７ａ〜３０７ｅを読み出して実行するようにしてもよい。
【０１７９】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１８０】
（付記１）圧縮前の文字列と、該文字列に対応する圧縮後の符号とを対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させる第１オートマトンを記憶する記憶部と、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンを、前記前半ビットによって第１ノードから中間ノードに状態遷移が発生し、前記後半ビットによって中間ノードから第２ノードに状態遷移が発生する第２オートマトンに変換する変換部と、
前記第２オートマトンの各中間ノードの遷移先となる第２ノードを比較し、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合する統合部と、
を有することを特徴とするオートマトン処理装置。
【０１８１】
（付記２）前記統合部は、前記第２オートマトンに含まれる第１ノードと中間ノードと第２ノードとの状態遷移の関係を集計し、集計した結果を基にして、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合することを特徴とする付記１に記載のオートマトン処理装置。
【０１８２】
（付記３）検索キーワードと、圧縮前の文字列および該文字列に対応する圧縮後の符号を対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させ前記検索キーワードの照合する第１オートマトンとを記憶する記憶部と、
前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードによる検索に関与しない文字列の符号を特定する特定部と、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンにおいて、前記特定部が特定した符号によって状態遷移する第１ノードを特定し、特定した各第１ノードの状態遷移先を同一の中間ノードに設定することで、前記第１オートマトンを第２オートマトンに変換する変換部と、
を有することを特徴とするオートマトン処理装置。
【０１８３】
（付記４）前記特定部は、前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードに含まれる文字の存在しない前記圧縮辞書の文字列を、前記検索キーワードによる検索に関与しない文字列として特定することを特徴とする付記３に記載のオートマトン処理装置。
【０１８４】
（付記５）前記特定部は、前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードの部分文字列として含まない前記圧縮辞書の文字列、または、前記検索キーワードの接尾辞の何れかと接頭辞の一致しない前記圧縮辞書の文字列、または、前記検索キーワードの接頭辞のいずれかと接尾辞の一致しない前記圧縮辞書の文字列を、前記検索キーワードによる検索に関与しない文字列として特定することを特徴とする付記３に記載のオートマトン処理装置。
【０１８５】
（付記６）コンピュータが実行するオートマトン処理方法であって、
圧縮前の文字列と、該文字列に対応する圧縮後の符号とを対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させる第１オートマトンを前記コンピュータの記憶装置に記憶させ、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンを、前記前半ビットによって第１ノードから中間ノードに状態遷移が発生し、前記後半ビットによって中間ノードから第２ノードに状態遷移が発生する第２オートマトンに変換し、
前記第２オートマトンの各中間ノードの遷移先となる第２ノードを比較し、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合する、
各処理を実行することを特徴とするオートマトン処理方法。
【０１８６】
（付記７）前記中間ノードを統合する処理は、前記第２オートマトンに含まれる第１ノードと中間ノードと第２ノードとの状態遷移の関係を集計し、該集計した結果を基にして、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合することを特徴とする付記６に記載のオートマトン処理方法。
【０１８７】
（付記８）コンピュータが実行するオートマトン処理方法であって、
検索キーワードと、圧縮前の文字列および該文字列に対応する圧縮後の符号を対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させ前記検索キーワードの照合する第１オートマトンとを記憶装置に記憶させ、
前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードによる検索に関与しない文字列の符号を特定し、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンにおいて、前記特定部が特定した符号によって状態遷移する第１ノードを特定し、特定した各第１ノードの状態遷移先を同一の中間ノードに設定することで、前記第１オートマトンを第２オートマトンに変換する
各処理を実行することを特徴とするオートマトン処理方法。
【０１８８】
（付記９）前記検索に関与しない文字列の符号を特定する処理は、前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードに含まれる文字の存在しない前記圧縮辞書の文字列を、前記検索キーワードによる検索に関与しない文字列として特定することを特徴とする付記８に記載のオートマトン処理方法。
【０１８９】
（付記１０）前記検索に関与しない文字列の符号を特定する処理は、前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードの部分文字列として含まない前記圧縮辞書の文字列、または、前記検索キーワードの接尾辞の何れかと接頭辞の一致しない前記圧縮辞書の文字列、または、前記検索キーワードの接頭辞のいずれかと接尾辞の一致しない前記圧縮辞書の文字列を、前記検索キーワードによる検索に関与しない文字列として特定することを特徴とする付記８に記載のオートマトン処理方法。
【０１９０】
（付記１１）コンピュータに、
圧縮前の文字列と、該文字列に対応する圧縮後の符号とを対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させる第１オートマトンを前記コンピュータの記憶装置に記憶させ、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンを、前記前半ビットによって第１ノードから中間ノードに状態遷移が発生し、前記後半ビットによって中間ノードから第２ノードに状態遷移が発生する第２オートマトンに変換し、
前記第２オートマトンの各中間ノードの遷移先となる第２ノードを比較し、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合する、
各処理を実行させることを特徴とするオートマトン処理プログラム。
【０１９１】
（付記１２）前記中間ノードを統合する処理は、前記第２オートマトンに含まれる第１ノードと中間ノードと第２ノードとの状態遷移の関係を集計した集計表を生成し、該集計表を基にして、前記後半ビットの如何によらず同一の第２ノードに遷移する中間ノードを統合することを特徴とする付記１１に記載のオートマトン処理プログラム。
【０１９２】
（付記１３）コンピュータに、
検索キーワードと、圧縮前の文字列および該文字列に対応する圧縮後の符号を対応付けた圧縮辞書と、前記圧縮辞書の符号によって第１ノードから第２ノードへの状態遷移を発生させ前記検索キーワードの照合する第１オートマトンとを記憶装置に記憶させ、
前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードによる検索に関与しない文字列の符号を特定し、
複数の中間ノードを生成し、
前記符号を前半ビットおよび後半ビットに分割し、
前記第１オートマトンにおいて、前記特定部が特定した符号によって状態遷移する第１ノードを特定し、特定した各第１ノードの状態遷移先を同一の中間ノードに設定することで、前記第１オートマトンを第２オートマトンに変換する
各処理を実行させることを特徴とするオートマトン処理プログラム。
【０１９３】
（付記１４）前記検索に関与しない文字列の符号を特定する処理は、前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードに含まれる文字の存在しない前記圧縮辞書の文字列を、前記検索キーワードによる検索に関与しない文字列として特定することを特徴とする付記１３に記載のオートマトン処理プログラム。
【０１９４】
（付記１５）前記検索に関与しない文字列の符号を特定する処理は、前記圧縮辞書と前記検索キーワードとを基にして、前記検索キーワードの部分文字列として含まない前記圧縮辞書の文字列、または、前記検索キーワードの接尾辞の何れかと接頭辞の一致しない前記圧縮辞書の文字列、または、前記検索キーワードの接頭辞のいずれかと接尾辞の一致しない前記圧縮辞書の文字列を、前記検索キーワードによる検索に関与しない文字列として特定することを特徴とする付記１３に記載のオートマトン処理プログラム。
【符号の説明】
【０１９５】
１００  オートマトン処理装置
１１０  通信部
１２０  入力部
１３０  表示部
１４０  記憶部
１５０  制御部
【図１】
0005807517.tif 000002
【図２】
0005807517.tif 000003
【図３】
0005807517.tif 000004
【図４】
0005807517.tif 000005
【図５】
0005807517.tif 000006
【図６】
0005807517.tif 000007
【図７】
0005807517.tif 000008
【図８】
0005807517.tif 000009
【図９】
0005807517.tif 000010
【図１０】
0005807517.tif 000011
【図１１】
0005807517.tif 000012
【図１２】
0005807517.tif 000013
【図１３】
0005807517.tif 000014
【図１４】
0005807517.tif 000015
【図１５】
0005807517.tif 000016
【図１６】
0005807517.tif 000017
【図１７】
0005807517.tif 000018
【図１８】
0005807517.tif 000019
【図１９】
0005807517.tif 000020
【図２０】
0005807517.tif 000021
【図２１】
0005807517.tif 000022
【図２２】
0005807517.tif 000023
【図２３】
0005807517.tif 000024
【図２４】
0005807517.tif 000025
【図２５】
0005807517.tif 000026
【図２６】
0005807517.tif 000027
【図２７】
0005807517.tif 000028
【図２８】
0005807517.tif 000029
【図２９】
0005807517.tif 000030
【図３０】
0005807517.tif 000031
【図３１】
0005807517.tif 000032
【図３２】
0005807517.tif 000033
【図３３】
0005807517.tif 000034
【図３４】
0005807517.tif 000035
【図３５】
0005807517.tif 000036
【図３６】
0005807517.tif 000037
【図３７】
0005807517.tif 000038
【図３８】
0005807517.tif 000039
【図３９】
0005807517.tif 000040
【図４０】
0005807517.tif 000041
【図４１】
0005807517.tif 000042
【図４２】
0005807517.tif 000043
【図４３】
0005807517.tif 000044
【図４４】
0005807517.tif 000045
【図４５】
0005807517.tif 000046