(57)【要約】【課題】無駄な辞書引きを実行せず、少ない回数の辞書引きでテキストを解析することができるようにする。【解決手段】辞書引き部４が解析対象テキストの中から解析用辞書３における木構造のノードパスにより決まる文字列と部分一致する文字列を検索する辞書引きを実行するとともに、可否情報追加部１３により追加された辞書引き実行可否情報を参照して、その文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを確認し、辞書引きを実行する必要がある場合に限り、途中から始まる文字列の辞書引きを実行する。【選択図】図１
2008146323.tif 000002
【特許請求の範囲】
【請求項１】
複数の辞書見出しに共通する最左部分文字列を併合して木構造の解析用辞書を生成する辞書生成手段と、上記辞書生成手段により生成された解析用辞書における木構造のノードパスにより決まる文字列に一致する辞書見出しの連鎖を確認して、木構造のノードパスにより決まる文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを判定する実行可否判定手段と、上記実行可否判定手段の判定結果を示す辞書引き実行可否情報を上記解析用辞書における木構造のノードに追加する可否情報追加手段とを備えた辞書生成装置。
【請求項２】
複数の辞書見出しに共通する最左部分文字列を併合して木構造の解析用辞書を生成する辞書生成手段と、上記辞書生成手段により生成された解析用辞書における木構造のノードパスにより決まる文字列に一致する辞書見出しの連鎖を確認して、木構造のノードパスにより決まる文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを判定する実行可否判定手段と、上記実行可否判定手段の判定結果を示す辞書引き実行可否情報を上記解析用辞書における木構造のノードに追加する可否情報追加手段と、解析対象テキストの中から上記解析用辞書における木構造のノードパスにより決まる文字列と部分一致する文字列を検索する辞書引きを実行するとともに、上記可否情報追加手段により追加された辞書引き実行可否情報を参照して、上記文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを確認し、辞書引きを実行する必要がある場合に限り、途中から始まる文字列の辞書引きを実行する辞書引き手段と、上記辞書引き手段による辞書引き結果から最適形態素を選択する最適形態素選択手段とを備えたテキスト解析装置。
【請求項３】
可否情報追加手段は、木構造のノードに追加する辞書引き実行可否情報として、当該ノードの直前の文字に関する情報のみを追加することを特徴とする請求項２記載のテキスト解析装置。
【請求項４】
辞書生成手段が複数の辞書見出しに共通する最左部分文字列を併合して木構造の解析用辞書を生成する辞書生成ステップと、実行可否判定手段が上記辞書生成手段により生成された解析用辞書における木構造のノードパスにより決まる文字列に一致する辞書見出しの連鎖を確認して、木構造のノードパスにより決まる文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを判定する実行可否判定ステップと、可否情報追加手段が上記実行可否判定手段の判定結果を示す辞書引き実行可否情報を上記解析用辞書における木構造のノードに追加する可否情報追加ステップと、辞書引き手段が解析対象テキストの中から上記解析用辞書における木構造のノードパスにより決まる文字列と部分一致する文字列を検索する辞書引きを実行するとともに、上記可否情報追加手段により追加された辞書引き実行可否情報を参照して、上記文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを確認し、辞書引きを実行する必要がある場合に限り、途中から始まる文字列の辞書引きを実行する辞書引きステップと、最適形態素選択手段が上記辞書引き手段による辞書引き結果から最適形態素を選択する最適形態素選択ステップとを備えたテキスト解析方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、解析対象のテキストに含まれている単語を同定するテキスト解析装置及びテキスト解析方法に関するものであり、特に、テキストの検索や機械翻訳を始めとする様々なテキスト解析結果を利用する分野で応用される技術に関するものである。
【背景技術】
【０００２】
従来のテキスト解析装置は、解析対象テキストに含まれている単語を同定する際、そのテキストの中から部分一致する文字列を辞書引きし、その辞書引き結果を先頭から末尾まで接続した中で、最適な辞書引き結果を正解とする方法を採用している。
このように、解析対象テキストの中から接続可能な部分一致する文字列を辞書引きする場合、一般的には、テキストの先頭から末尾まで１文字ずつ探索開始位置をずらしながら、既に辞書引きしている辞書見出しに接続可能な位置からだけ部分文字列一致する辞書見出しを取り出すようにしている。
【０００３】
このように、任意の開始位置から部分一致する辞書見出しをすべて取り出す方法は、共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）と呼ばれている。
また、辞書引き結果を先頭から末尾まで接続した中から、最適な辞書引き結果を得る方法として、最長一致法、文節数最小法、コスト最小法などの方法が知られている（例えば、非特許文献１を参照）。
【０００４】
共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を効率的に実現する方法の一つとして、トライ（ｔｒｉｅ）という方法が知られている（例えば、非特許文献２を参照）。
トライは、辞書エントリを１文字ずつに分割し、木構造の枝に文字を割り付けるものである。
即ち、最上部のノードから１文字ずつ文字が一致する枝を順番に辿っていき、ノードに割り当てられた辞書見出しを全てピックアップすることで、任意の文字列の先頭から部分一致する文字列を辞書引きするものである。
【０００５】
このように、トライ木構造を先頭から１回だけ辿ることで、文字列の先頭から一致する部分文字列を全て取り出すことができるので、共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）が高速になるが、分岐の枝数が大きくなるため、枝の選択時間を効率良くするためには、大量のメモリを必要とする。
そこで、共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）の高速性を維持しながら、データ格納効率を向上させる方法としてパトリシア（例えば、非特許文献２を参照）や、ダブル配列法（例えば、非特許文献３を参照）と呼ばれる方法も開発されている。
【０００６】
【非特許文献１】「岩波講座ソフトウェア科学（１５）  自然言語処理」ｐ．ｐ．１２２−１３０
【非特許文献２】「岩波講座ソフトウェア科学（１５）  自然言語処理」ｐ．ｐ．２５０−２５３
【非特許文献３】「ダブル配列による有限状態機械の効率的インプリメンテーション」電子情報通信学会論文誌 Ｄ Ｖｏｌ．Ｊ７０−Ｄ Ｎｏ．４ ｐ．ｐ．６５３−６６２ １９８７年４月
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来のテキスト解析装置は以上のように構成されているので、パトリシアやダブル配列法を使用すれば、共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）の高速性を維持しながら、データ格納効率を高めることができるが、無駄な辞書引きを実行してしまうことがあるなどの課題があった。
【０００８】
例えば、ダブル配列法を使用して、「ハウジングサービスを呼ぶ」というテキストを解析する場合には、テキストの先頭から１文字ずつ移動させながら、「ハウジングサービスを呼ぶ」、「ウジングサービスを呼ぶ」、「ジングサービスを呼ぶ」、「ングサービスを呼ぶ」、・・・、「呼ぶ」、「ぶ」の各文字列の先頭から部分一致する辞書見出しを検索することになる。このとき、「ハウジングサービスを呼ぶ」の辞書引き結果である「ハウジングサービス」、「ハウジング」、「ハウ」、「ハ」が共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）の結果として返されるため、「ハ」に接続可能な「ウジングサービスを呼ぶ」、「ハウ」に接続可能な「ジングサービスを呼ぶ」、・・・は、辞書引き開始位置となり、それぞれ辞書引きを行うことになる。
その結果として、（「ハウジングサービスを呼ぶ」⇒「ハウジングサービス」、「ハウジング」、「ハウ」、「ハ」）、（「ウジングサービスを呼ぶ」⇒なし）、（「ジングサービスを呼ぶ」⇒「ジン」）、（「グサービスを呼ぶ」⇒なし）、（「サービスを呼ぶ」⇒「サービス」、「サー」）、（「ビスを呼ぶ」⇒「ビス」）、（「を呼ぶ」⇒「を」）、（「呼ぶ」⇒「呼（語幹）」）、（「ぶ」⇒「ぶ（語尾）」）の順番で辞書引きすることになる。
上記のように、通常の辞書引きでは、各位置で終わる見出しがあるか否かを基準にして、辞書引きの必要性を判定しているが、実際には、あらかじめ辞書中の全ての見出しは決まっているため、単語が辞書引きされた時点で、より強力な辞書引き削減位置を決定することが可能であり、無駄な辞書引きを実施していたことになる。
【０００９】
この発明は上記のような課題を解決するためになされたもので、無駄な辞書引きを回避することができる解析用辞書を生成することができる辞書生成装置を得ることを目的とする。
また、この発明は、無駄な辞書引きを実行せず、少ない回数の辞書引きでテキストを解析することができるテキスト解析装置及びテキスト解析方法を得ることを目的とする。
【課題を解決するための手段】
【００１０】
この発明に係るテキスト解析装置は、辞書生成手段により生成された解析用辞書における木構造のノードパスにより決まる文字列に一致する辞書見出しの連鎖を確認して、木構造のノードパスにより決まる文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを判定する実行可否判定手段と、その実行可否判定手段の判定結果を示す辞書引き実行可否情報を解析用辞書における木構造のノードに追加する可否情報追加手段とを設け、辞書引き手段が解析対象テキストの中から解析用辞書における木構造のノードパスにより決まる文字列と部分一致する文字列を検索する辞書引きを実行するとともに、可否情報追加手段により追加された辞書引き実行可否情報を参照して、その文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを確認し、辞書引きを実行する必要がある場合に限り、途中から始まる文字列の辞書引きを実行するようにしたものである。
【発明の効果】
【００１１】
この発明によれば、辞書生成手段により生成された解析用辞書における木構造のノードパスにより決まる文字列に一致する辞書見出しの連鎖を確認して、木構造のノードパスにより決まる文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを判定する実行可否判定手段と、その実行可否判定手段の判定結果を示す辞書引き実行可否情報を解析用辞書における木構造のノードに追加する可否情報追加手段とを設け、辞書引き手段が解析対象テキストの中から解析用辞書における木構造のノードパスにより決まる文字列と部分一致する文字列を検索する辞書引きを実行するとともに、可否情報追加手段により追加された辞書引き実行可否情報を参照して、その文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを確認し、辞書引きを実行する必要がある場合に限り、途中から始まる文字列の辞書引きを実行するように構成したので、無駄な辞書引きを実行せず、少ない回数の辞書引きでテキストを解析することができる効果がある。
【発明を実施するための最良の形態】
【００１２】
実施の形態１．
図１はこの発明の実施の形態１によるテキスト解析装置を示す構成図であり、図２はこの発明の実施の形態１による辞書生成装置を示す構成図である。
図において、辞書データ格納部１は少なくとも辞書見出しと品詞情報からなる辞書データを格納しているメモリである。
辞書生成装置２は辞書データ格納部１に格納されている辞書データから木構造の解析用辞書３を生成するとともに、木構造のノードパスにより決まる文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを示す辞書引き実行可否情報を解析用辞書３における木構造のノードに追加する装置である。
【００１３】
辞書生成装置２の辞書生成部１１は辞書データ格納部１に格納されている複数の辞書見出しに共通する最左部分文字列を併合して木構造の解析用辞書３を生成する処理を実施する。なお、辞書生成部１１は辞書生成手段を構成している。
辞書生成装置２の実行可否判定部１２は辞書生成部１１により生成された解析用辞書３における木構造のノードパスにより決まる文字列に一致する辞書見出しの連鎖を確認して、木構造のノードパスにより決まる文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを判定する処理を実施する。なお、実行可否判定部１２は実行可否判定手段を構成している。
辞書生成装置２の可否情報追加部１３は実行可否判定部１２の判定結果を示す辞書引き実行可否情報を解析用辞書３における木構造のノードに追加する処理を実施する。なお、可否情報追加部１３は可否情報追加手段を構成している。
【００１４】
解析用辞書３は例えばトライ木などの木構造のデータ形式が採用されているテキスト解析用の辞書である。
辞書引き部４は解析対象テキストの中から解析用辞書３における木構造のノードパスにより決まる文字列と部分一致する文字列を検索する辞書引きを実行する辞書引き実行部４ａと、可否情報追加部１３により追加された辞書引き実行可否情報を参照して、辞書引き実行部４ａにより検索された文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを確認し、その確認結果を辞書引き実行部４ａに通知する辞書引き確認部４ｂとから構成されている。
なお、辞書引き部４は辞書引き手段を構成している。
最適形態素選択部５は辞書引き部４による辞書引き結果から最適形態素を選択する処理を実施する。なお、最適形態素選択部５は最適形態素選択手段を構成している。
【００１５】
図１の例では、テキスト解析装置の構成要素である辞書生成装置２、辞書引き部４及び最適形態素選択部５がそれぞれ専用のハードウェア（例えば、ＭＰＵなどのＩＣを実装している半導体集積回路基板）から構成されているものを想定しているが、テキスト解析装置がコンピュータから構成されている場合、辞書生成装置２、辞書引き部４及び最適形態素選択部５の処理内容が記述されているプログラムを予めコンピュータのメモリに格納し、コンピュータのＣＰＵが当該メモリに格納されているプログラムを実行するようにしてもよい。
【００１６】
図３はこの発明の実施の形態１による辞書生成装置の処理内容を示すフローチャートであり、図４はこの発明の実施の形態１によるテキスト解析装置の辞書引き部４の処理内容を示すフローチャートである。
図５は辞書データ格納部１に格納されている辞書データを示す説明図であり、図６は解析用辞書３のデータ構造を示す説明図である。
【００１７】
図６において、○はノードを表しており、○内の数字はノードを識別するノード番号である。
ノード（１）はルートノードであり、ノード（１）からノード（２）には、辞書引き文字列の先頭文字が「サ」のときに移動する。
同様に、ノード（２）からノード（３）には、辞書引き文字列の２番目の文字列が「ー」のときに移動する。
線が太い○のノード、即ち、ノード（３）、ノード（５）、ノード（７）、ノード（１０）、ノード（１２）、ノード（１４）、ノード（１５）、ノード（１６）、ノード（２０）、ノード（２４）、ノード（２７）、ノード（２９）は、そこまでの辞書見出しがあることを示している。
つまり、ノード（３）に移動したら「サー」という見出しが辞書にあり、辞書引きされたことを示している。また、ノード５に移動したら「サーカス」という見出しが辞書にあり、辞書引きされたことを示している。
【００１８】
図７（ａ）〜（ｃ）及び図８は図６の解析用辞書データにおける各ノードに追加される辞書引き実行可否情報の作成方法を示す説明図である。
【００１９】
次に動作について説明する。
テキスト解析に使用する辞書は、図５に示すように、少なくとも辞書見出しと品詞情報からなる辞書データを保有している必要がある。
辞書引き部４が解析対象テキストに含まれている単語を解析する際、辞書データ格納部１に格納されている図５の辞書データをそのまま利用することも可能であるが、図５の辞書データをそのまま利用する場合、辞書引きに多くの時間を要するため、一般的には、トライ木、パトリシア木やダブル配列などの方法で格納された専用の解析用辞書を使用して辞書引きを高速に行う。
【００２０】
トライ木、パトリシア木及びダブル配列は、辞書引きしたい文字列に対して、先頭から１文字ずつデータ構造を辿ることで、辞書引き対象文字列の先頭から部分一致する辞書見出しの全てを検索することが可能なデータ構造を有している。
この実施の形態１では、例えば、トライ木などの木構造のデータ形式が採用されている解析用辞書のノードに、文字列の辞書引きを実行する必要があるか否かを示す辞書引き実行可否情報を追加して、無駄な辞書引きを回避することができるようにしている。
以下、トライ木によるデータ構造を用いて説明する。
【００２１】
最初に、辞書生成装置２による解析用辞書３の生成方法について説明する。
辞書生成装置２の辞書生成部１１は、辞書データ格納部１に格納されている図５の辞書データを参照して、トライ木の解析用辞書３を生成する（図６を参照）。
即ち、辞書生成部１１は、図５の辞書データを構成している複数の辞書見出しに共通する最左部分文字列を併合して木構造の解析用辞書３を生成する。
ただし、トライ木自身の生成方法については公知の技術であるため、ここでは詳細な説明を省略する。
【００２２】
辞書生成装置２の実行可否判定部１２は、辞書生成部１１が解析用辞書３を生成すると、その解析用辞書３における木構造のノードパスにより決まる文字列に一致する辞書見出しの連鎖を確認して、木構造のノードパスにより決まる文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを判定する。
以下、図６のノード（２０）に辞書引き実行可否情報を追加する場合を例にとって、実行可否判定部１２の処理内容を具体的に説明する。
【００２３】
最初に、実行可否判定部１２は、トライ木のノードまでの文字列を生成する（ステップＳＴ１）。
ここでは、図６のノード（２０）までの文字列を生成するので、「ハウジング」という文字列を生成する。
実行可否判定部１２は、ノード（２０）までの文字列「ハウジング」を生成すると、その文字列「ハウジング」の文字長ｎ、文字位置を示すパラメータｉ、文字位置ｉ−１で終了する単語が存在するか否かを表すフラグｉｎｆｏ［ｉ］を初期化する。
文字列が「ハウジング」の場合、文字長が“５”であるため“ｎ←５”に初期化し、また、“ｉ＝０”に初期化する。
なお、ｉｎｆｏ［ｉ］＝１の場合、文字位置ｉ−１で終了する辞書見出しが存在するため、文字位置ｉから辞書引きが必要であることを示し、ｉｎｆｏ［ｉ］＝０の場合、文字位置ｉ−１で終了する辞書見出しが存在しないため、文字位置ｉから辞書引きが必要でないことを示すものである。
この段階では、“ｉｎｆｏ［０］←１”、“ｉｎｆｏ［ｉ］←０（１≦ｉ＜ｎ）”に初期化する。
【００２４】
次に、実行可否判定部１２は、文字位置を示すパラメータｉと文字長ｎを比較し、ｉ＜ｎが成立するか否かを判定する（ステップＳＴ２）。この段階では、ｉ＝０で、ｎ＝５であるため、ｉ＜ｎが成立すると判定する。
実行可否判定部１２は、ｉ＜ｎが成立すると判定すると、ｉｎｆｏ［ｉ］＝１であるか否かを判別して、文字位置ｉから辞書引きが必要であるか否かを判定する（ステップＳＴ３）。
この段階では、ｉｎｆｏ［０］＝１であるため、文字位置ｉから辞書引きが必要であると判定する。
【００２５】
実行可否判定部１２は、文字位置ｉから辞書引きが必要であると判定すると、辞書見出しから、ｉ文字目から始まる条件一致文字列をすべて抽出する（ステップＳＴ４）。
この段階では、ｉ＝０であるため、「ハ」、「ハウ」、「ハウジング」、「ハウジングサービス」を辞書引きする。
通常の部分一致であれば、「ハウジング」に部分一致する「ハ」、「ハウ」、「ハウジング」が検索されるが、ステップＳＴ４においては、図６のノード（２４）のように、「ハウジング」を含むキーワード「ハウジングサービス」が存在する場合には、キーワード「ハウジングサービス」も辞書引きする。
【００２６】
実行可否判定部１２は、ｉ文字目から始まる条件一致文字列を抽出すると、条件一致文字列の抽出結果である辞書引き結果（「ハ」、「ハウ」、「ハウジング」、「ハウジングサービス」）の単語文字長ｌｅｎをセットして、ｉｎｆｏ［ｉ＋ｌｅｎ］＝１をセットする（ステップＳＴ５）。
この段階では、ｉ＝０であるため、下記のようにセットする。
（１）  ｉｎｆｏ［ｉ＋ｌｅｎ（“ハ”）］
＝ｉｎｆｏ［０＋１］＝ｉｎｆｏ［１］＝１
（２）  ｉｎｆｏ［ｉ＋ｌｅｎ（“ハウ”）］
＝ｉｎｆｏ［０＋２］＝ｉｎｆｏ［２］＝１
（３）  ｉｎｆｏ［ｉ＋ｌｅｎ（“ハウジング”）］
＝ｉｎｆｏ［０＋５］＝ｉｎｆｏ［５］＝１
（４）  ｉｎｆｏ［ｉ＋ｌｅｎ（“ハウジングサービス”）］
＝ｉｎｆｏ［０＋９］＝ｉｎｆｏ［９］＝１
ただし、ｌｅｎ（）は、文字長を返す関数である。
【００２７】
実行可否判定部１２は、ｉｎｆｏ［ｉ＋ｌｅｎ］＝１をセットすると、辞書引き開始位置を一つ後方に移すため、文字位置を示すパラメータｉに“１”を加算して、ステップＳＴ２の処理に戻る（ステップＳＴ６）。
実行可否判定部１２は、文字位置を示すパラメータｉと文字長ｎを比較し、ｉ＜ｎが成立するか否かを判定する（ステップＳＴ２）。
ｉ＜ｎが成立している間は、ステップＳＴ２〜ＳＴ６の処理が繰り返し実施される。
文字列「ハウジング」の場合、ｎ＝５であるため、ｉ＝５になると、ｉ＜ｎが非成立になり、ステップＳＴ７の処理に移行する。
【００２８】
実行可否判定部１２は、ｉ＜ｎが非成立になると、辞書引きが完了しているため（図７（ｃ）の辞書引き結果を参照）、先頭から辞書引き結果のパスを探索して、文字列の辞書引きを実行する必要があるか否かを示す辞書引き実行可否情報を生成する。
即ち、実行可否判定部１２は、辞書引き実行可否情報の一部を構成するｐａｔｈ［ｉ］を“ｐａｔｈ［ｉ］←０（１≦ｉ＜ｎ）”に初期化する（ステップＳＴ７）。
ここで、ｐａｔｈ［ｉ］＝１は、文字位置ｉにおいて辞書引きが必要である旨を示し、ｐａｔｈ［ｉ］＝０は、文字位置ｉにおいて辞書引きが必要でない旨を示すものである。
【００２９】
実行可否判定部１２は、ｐａｔｈ［ｉ］を初期化すると、図７（ｃ）の辞書引き結果を参照して、先頭から接続可能な辞書見出し列の取り出しを順番に行う（ステップＳＴ８，ＳＴ９）。
具体的には、下記に示す順番で、先頭から接続可能な辞書見出し列の取り出しを行う。
（１）「ハ」
（２）「ハウ」
（３）「ハウ」→「ジン」
（４）「ハウ」→「ジン」→「グラフ」
（５）「ハウ」→「ジングルベル」
（６）「ハウジング」
（７）「ハウジングサービス」
【００３０】
ただし、（１）の「ハ」の場合、パスの長さ（総文字長）が“１”であり、パスの長さ（総文字長）が「ハウジング」の文字長（ｎ＝５）より短いため、後述するｐａｔｈ［ｉ］の更新には利用しない（ステップＳＴ１０）。
同様に、（２）の「ハウ」の場合、パスの長さ（総文字長）が“２”、（３）の「ハウ」→「ジン」、パスの長さ（総文字長）が“４”であり、パスの長さ（総文字長）が「ハウジング」の文字長（ｎ＝５）より短いため、後述するｐａｔｈ［ｉ］の更新には利用しない（ステップＳＴ１０）。
【００３１】
実行可否判定部１２は、（４）の「ハウ」→「ジン」→「グラフ」の場合、パスの長さ（総文字長）が“７”であり、パスの長さ（総文字長）が「ハウジング」の文字長（ｎ＝５）より短くないため、見出し開始位置ｉ（「ジン」の見出し開始位置ｉ＝２、「グラフ」の見出し開始位置ｉ＝４）と「ハウジング」の文字長（ｎ＝５）を比較して、ｉ＜ｎが成立するか否かを判定する。
（４）の「ハウ」→「ジン」→「グラフ」の場合、ｉ＜ｎが成立するため、ｐａｔｈ［ｉ］を“１”に更新する（ステップＳＴ１１）。即ち、ｐａｔｈ［２］＝１、ｐａｔｈ［４］＝１をセットする。
（６）の「ハウジング」の場合、パスの長さ（総文字長）が“５”であり、パスの長さ（総文字長）が「ハウジング」の文字長（ｎ＝５）より短くないが、辞書見出しに切れ目が無く、見出し開始位置ｉが存在しないので、ｐａｔｈ［ｉ］を更新しない。
同様に、（７）の「ハウジングサービス」の場合、パスの長さ（総文字長）が“９”であり、パスの長さ（総文字長）が「ハウジング」の文字長（ｎ＝５）より短くないが、辞書見出しに切れ目が無く、見出し開始位置ｉが存在しないので、ｐａｔｈ［ｉ］を更新しない。
【００３２】
実行可否判定部１２は、すべてのパスを探索して、ｐａｔｈ［ｉ］の更新が完了すると（ステップＳＴ８〜ＳＴ１１）、ｐａｔｈ［ｉ］（１≦ｉ＜ｎ）から辞書引き実行可否情報を生成する。
この例では、ｐａｔｈ［１］＝０、ｐａｔｈ［２］＝１、ｐａｔｈ［３］＝０、ｐａｔｈ［４］＝１であるため、辞書引き実行可否情報「０１０１」を生成する。
辞書生成装置２の可否情報追加部１３は、実行可否判定部１２が辞書引き実行可否情報「０１０１」を生成すると、図６に示すように、この辞書引き実行可否情報「０１０１」をノード（２０）にセットする（ステップＳＴ１２）。
【００３３】
ここまでは、図６のノード（２０）に辞書引き実行可否情報「０１０１」を追加する例を説明したが、辞書生成装置２が図６のノード（１６）までの文字列「ハウ」について同様に処理すれば、図７（ａ）に示すように、「ウ」から始まる文字列の辞書引きが必要である旨を示す辞書引き実行可否情報「１」が図６のノード（１６）にセットされる。
また、辞書生成装置２が図６のノード（１８）までの文字列「ハウジ」について同様に処理すれば、図７（ｂ）に示すように、「ウ」と「ジ」から文字列の始まる辞書引きが必要である旨を示す辞書引き実行可否情報「１１」が図６のノード（１８）にセットされる。
また、辞書生成装置２が図６のノード（２４）までの文字列「ハウジングサービス」について同様に処理すれば、図８に示すように、「サ」と「ビ」から始まる文字列の辞書引きが必要である旨を示す辞書引き実行可否情報「００００１０１０」が図６のノード（２４）にセットされる。
以上から明らかなように、辞書引き時に部分一致する文字列長が長くなるほど、辞書引き実行可否情報における「０」が増え、辞書引き不要な位置が増えることがわかる。
【００３４】
辞書引き部４の辞書引き実行部４ａは、解析対象テキストの中から解析用辞書３における木構造のノードパスにより決まる文字列と部分一致する文字列を検索する。
即ち、辞書引き実行部４ａは、解析対象テキストとして「ハウジングサービスを呼ぶ。」を入力すると、解析対象テキスト「ハウジングサービスを呼ぶ。」のテキスト長ｎ、辞書引き開始位置を示すパラメータｉ、辞書引きが必要な位置であるか否かを示すフラグを初期化する（ステップＳＴ２１）。
解析対象テキストが「ハウジングサービスを呼ぶ。」の場合、テキスト長が“１３”であるため“ｎ←１３”に初期化し、また、“ｉ＝０”に初期化する。
なお、ｆｌｇ［ｉ］＝１の場合、開始位置ｉで辞書引きが必要であることを示し、ｆｌｇ［ｉ］＝０の場合、開始位置ｉで辞書引きが必要でないことを示すものである。
この段階では、“ｆｌｇ［０］←１”、“ｆｌｇ［ｉ］←０（１≦ｉ＜ｎ）”に初期化する。
【００３５】
辞書引き実行部４ａは、辞書引き開始位置を示すパラメータｉとテキスト長ｎを比較し、ｉ＜ｎが成立するか否かを判定する（ステップＳＴ２２）。この段階では、ｉ＝０で、ｎ＝１３であるため、ｉ＜ｎが成立すると判定する。
辞書引き実行部４ａは、ｉ＜ｎが成立すると判定すると、ｆｌｇ［ｉ］＝１であるか否かを判別して、辞書引き開始位置ｉからの部分文字列に対して、共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を行う必要があるか否かを判定する（ステップＳＴ２３）。
この段階では、ｆｌｇ［０］＝１であるため、共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を行う必要があると判定する。
【００３６】
辞書引き実行部４ａは、共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を行う必要があると判定すると、辞書引き開始位置ｉからの部分文字列から共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を行う（ステップＳＴ２４）。
この段階では、ｉ＝０であるため、解析対象テキスト「ハウジングサービスを呼ぶ。」の先頭から共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を行う。
辞書引き実行部４ａが解析対象テキスト「ハウジングサービスを呼ぶ。」の先頭から共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を行うと、ノード（１）から部分一致する最長のノードが、ノード（１）→ノード（１５）→ノード（１６）→ノード（１８）→ノード（１９）→ノード（２０）→ノード（２１）→ノード（２２）→ノード（２３）→ノード（２４）と辿るノード（２４）であるため、「ハ」、「ハウ」、「ハウジング」、「ハウジングサービス」が辞書引き結果として得られる。
【００３７】
辞書引き部４の辞書引き確認部４ｂは、辞書引き実行部４ａが共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を実行して辞書引き結果を得ると、その辞書引き結果に対応する辞書引き実行可否情報を取得する（ステップＳＴ２５）。
この段階では、ノード（１）から部分一致する最長のノードがノード（２４）であるため、そのノード（２４）に追加されている辞書引き実行可否情報「００００１０１０」を取得する。
【００３８】
辞書引き確認部４ｂは、ノード（２４）に追加されている辞書引き実行可否情報「００００１０１０」を取得すると、辞書引き実行部４ａにより得られた辞書引き結果のうち、“０”の位置で終わる辞書引き結果を削除する（ステップＳＴ２６）。
即ち、辞書引き確認部４ｂは、辞書引き実行可否情報「００００１０１０」の左からｊビット目の値を返す関数ｂｉｔｆｌｇ（ｊ）において、ｂｉｔｆｌｇ（ｊ）＝０であれば、ｊビット目に対応する辞書引き結果を保持していても、接続可能な形態素パスを生成することができないため、その辞書引き結果を削除する。
具体的には、ｂｉｔｆｌｇ（１）＝０、ｂｉｔｆｌｇ（２）＝０であるため、１ビット目と２ビット目に対応する辞書引き結果である「ハ」と「ハウ」を削除する。
【００３９】
辞書引き確認部４ｂは、“０”の位置で終わる辞書引き結果を削除すると、辞書引き実行可否情報の桁数を示すパラメータｍと、辞書引き実行可否情報の桁位置を示すパラメータｊを初期化する（ステップＳＴ２７）。
この段階では、ノード（２４）に追加されている辞書引き実行可否情報「００００１０１０」の桁数が８桁であるため“ｍ←８”に初期化し、また、“ｊ←１”に初期化する。
【００４０】
辞書引き確認部４ｂは、辞書引き実行可否情報の桁位置を示すパラメータｊと辞書引き実行可否情報の桁数を示すパラメータｍを比較し、ｊ≦ｍが成立するか否かを判定する（ステップＳＴ２８）。この段階では、ｊ＝１で、ｍ＝８であるため、ｊ≦ｍが成立すると判定する。
辞書引き確認部４ｂは、ｊ≦ｍが成立すると判定すると、ｆｌｇ［ｉ＋ｊ］＝０であるか否かを判別して、辞書引き開始位置であるか否かを判定する（ステップＳＴ２９）。
辞書引き確認部４ｂは、ｆｌｇ［ｉ＋ｊ］＝０である場合、辞書引き開始位置ではないため、辞書引き実行可否情報「００００１０１０」の左からｊビット目の値を取り出し、ｂｉｔｆｌｇ（ｊ）＝１であれば、ｆｌｇ［ｉ＋ｊ］＝１をセットして（ステップＳＴ３０）、辞書引き実行可否情報の桁位置を示すパラメータｊに“１”を加算する（ステップＳＴ３１）。
一方、ｆｌｇ［ｉ＋ｊ］＝１である場合、既に辞書引き開始位置になっているため、辞書引き実行可否情報の桁位置を示すパラメータｊに“１”を加算する（ステップＳＴ３１）。
【００４１】
ステップＳＴ２８〜ＳＴ３１の処理は、ｊ＝９になって、ｊ≦ｍが成立しなくなるまで繰り返し実施され、ノード（２４）に追加されている辞書引き実行可否情報「００００１０１０」については、ｊ＝５、または、ｊ＝７のとき、ｂｉｔｆｌｇ（ｊ）＝１になるので、ｆｌｇ［５］←１、ｆｌｇ［７］←１となる。
辞書引き確認部４ｂは、ｊ≦ｍが非成立であると判定すると、辞書引き開始位置を示すパラメータｉに“１”を加算する（ステップＳＴ３２）。
【００４２】
これにより、ステップＳＴ２２の処理に戻り、再度、辞書引き実行部４ａが、ｉ＜ｎ、ｆｌｇ［ｉ］＝１であるか否かを判別して、辞書引き開始位置ｉからの部分文字列に対して、共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を行う必要があるか否かを判定することになる（ステップＳＴ２２、ＳＴ２３）。
ただし、ステップＳＴ２８〜ＳＴ３１の処理において、ｆｌｇ［５］←１、ｆｌｇ［７］←１にしているが、ｆｌｇ［ｉ］＝０（１≦ｉ＜５、ｉ＝６）であるため、文字位置ｉが１〜４，６であれば、辞書引きを行うまでも無く、必要な辞書引き結果が得られるので、共通接頭辞検索（ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ）を行う必要がないと判定する。即ち、ステップＳＴ２４の処理に移行せずに、ステップＳＴ３２の処理に移行する。
【００４３】
辞書引き実行部４ａ及び辞書引き確認部４ｂが、図４の処理を繰り返し実施することにより、辞書引き不要な開始位置を判断することができるため、辞書引き回数を減らすことができる。
また、最適形態素選択部５での候補についても、「ハ」、「ハウ」といった辞書引き結果を事前に削除することができるため、最適形態素探索の処理を削減することができる。
【００４４】
最適形態素選択部５は、上記のようにして、辞書引き部４が辞書引きを行うと、辞書引き部４による辞書引き結果から最適形態素を選択する。
最適形態素選択部５における最適形態素の選択処理自体は、公知の技術であるため、ここでは詳細な説明を省略する。
【００４５】
以上で明らかなように、この実施の形態１によれば、辞書生成部１１により生成された解析用辞書３における木構造のノードパスにより決まる文字列に一致する辞書見出しの連鎖を確認して、木構造のノードパスにより決まる文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを判定する実行可否判定部１２と、その実行可否判定部１２の判定結果を示す辞書引き実行可否情報を解析用辞書３における木構造のノードに追加する可否情報追加部１３とを設け、辞書引き部４が解析対象テキストの中から解析用辞書３における木構造のノードパスにより決まる文字列と部分一致する文字列を検索する辞書引きを実行するとともに、可否情報追加部１３により追加された辞書引き実行可否情報を参照して、その文字列の途中から始まる文字列の辞書引きを実行する必要があるか否かを確認し、辞書引きを実行する必要がある場合に限り、途中から始まる文字列の辞書引きを実行するように構成したので、無駄な辞書引きを実行せず、少ない回数の辞書引きでテキストを解析することができる効果を奏する。
【００４６】
なお、この実施の形態１では、トライ木の解析用辞書３を生成するものについて示したが、パトリシア木やダブル配列の解析用辞書３を生成するようにしてもよい。特に、ダブル配列の解析用辞書３を生成する場合、ノード番号が配列の位置を参照することで表現されるように番号付けされて格納されるため、辞書引き実行可否情報を固定長とすることで、効率が良い格納と参照を実現することができる。
【００４７】
実施の形態２．
上記実施の形態１では、各ノードに対してルートノードからのパスの長さ−１のビット情報として辞書引き実行可否情報を生成するものについて示したが、当該ノードの直前の文字に関する情報のみからなる辞書引き実行可否情報を生成するようにしてもよい。
即ち、生成する辞書引き実行可否情報を、図９に示すように、直前の１文字分（最も右のビット情報）だけに限定して、１ビットで表現するようにしてもよい。
この場合、例えば、１ビット表現データ２１のように、ノード（１６）は「１」、ノード（１８）は「１」、ノード（１９）は「０」、ノード（２０）は「１」、ノード（２１）は「１」、ノード（２２）は「０」、ノード（２３）は「１」、ノード（２４）は「０」となり、ノード（２４）まで辞書引きで一致した場合の辞書引き実行可否情報である１ビット表現の辞書引き実行可否情報２３は、上記の０、１（下線部分）を順番に並べた「１１０１１０１０」となる。
このため、上記実施の形態１と比べて、辞書引き削減の効果が小さくなる可能性があるが、同様に辞書引き削減を行うことが可能である。
【００４８】
また、前方ｎ文字分のビット情報を格納する方法を取ることも可能である。
ｎ＝２とする場合、２ビット表現データ２２のように、ノード（１６）は「１」、ノード（１８）は「１１」、ノード（１９）は「１０」、ノード（２０）は「０１」、ノード（２１）は「０１」、ノード（２２）は「１０」、ノード（２３）は「０１」、ノード（２４）は「１０」となり、ノード（２４）まで辞書引きで一致した場合の辞書引き実行可否情報である２ビット表現の辞書引き実行可否情報２４は、ノード（１８）〜（２２）までは１ビット目、ノード（２４）は２ビット分（下線部分）を順番に並べた「１１００１０１０」となる。
このとき、ノード（１６）の情報は、検索時にノード（１６）までしか一致しなかった（「ハウ」までしか一致しなかった）場合の「ウ」から始まる文字列の辞書引きが必要か否かの情報として使われる。
【図面の簡単な説明】
【００４９】
【図１】この発明の実施の形態１によるテキスト解析装置を示す構成図である。
【図２】この発明の実施の形態１による辞書生成装置を示す構成図である。
【図３】この発明の実施の形態１による辞書生成装置の処理内容を示すフローチャートである。
【図４】この発明の実施の形態１によるテキスト解析装置の辞書引き部４の処理内容を示すフローチャートである。
【図５】辞書データ格納部１に格納されている辞書データを示す説明図である。
【図６】解析用辞書３のデータ構造を示す説明図である。
【図７】図６の解析用辞書データにおける各ノードに追加される辞書引き実行可否情報の作成方法を示す説明図である。
【図８】図６の解析用辞書データにおける各ノードに追加される辞書引き実行可否情報の作成方法を示す説明図である。
【図９】辞書引き実行可否情報のビット削減例を示す説明図である。
【符号の説明】
【００５０】
１  辞書データ格納部、２  辞書生成装置、３  解析用辞書、４  辞書引き部（辞書引き手段）、４ａ  辞書引き実行部、４ｂ  辞書引き確認部、５  最適形態素選択部（最適形態素選択手段）、１１  辞書生成部（辞書生成手段）、１２  実行可否判定部（実行可否判定手段）、１３  可否情報追加部（可否情報追加手段）。
【図１】
2008146323.tif 000003
【図２】
2008146323.tif 000004
【図３】
2008146323.tif 000005
【図４】
2008146323.tif 000006
【図５】
2008146323.tif 000007
【図６】
2008146323.tif 000008
【図７】
2008146323.tif 000009
【図８】
2008146323.tif 000010
【図９】
2008146323.tif 000011