(57)【要約】  【課題】  ＮＦＡを用いた形態素解析システムの処理速度を向上させる。  【解決手段】  自然言語文を構成する単語を単語辞書３０から検索し、この単語の連接に使用される連接規則を文法辞書４０から検索し、これらの単語および連接規則に基づいてオートマトンを生成し、形態素解析の解を求める解析処理部２０を備える。文法辞書４０は、非空遷移を表す連接規則と当該連接規則の遷移元を遷移先とし空遷移を表す連接規則とが統合された連接規則を格納する。解析処理部２０の最適解探索部２３は、オートマトンを生成するために、所定の単語をオートマトンに入力して遷移パスおよび遷移先の状態を生成する際の処理として、この単語に対応する連接規則による遷移に必要な状態のみを生成し、生成された状態に後続する空遷移を辿って遷移可能な状態を生成しない。また、直前に生成された状態を遷移元とする連接規則を、この単語に関する連接規則の中から探索する。  【選択図】  図２
2005122444.tif 000002
【特許請求の範囲】
【請求項１】
自然言語文に対する形態素解析を行う形態素解析システムにおいて、
処理対象である自然言語文を構成する文字列に対応する単語を所定の単語辞書から検索する単語候補検索部と、
前記単語候補検索部による検索によって得られた各単語の品詞に基づき、所定の文法辞書から当該単語の連接に使用される可能性のある連接規則を検索する連接規則検索部と、
前記単語候補検索部により検索された単語と前記連接規則検索部により検索された連接規則とに基づいて、処理対象の自然言語文に対応するオートマトンを生成し、形態素解析の解を求める最適解探索部とを備え、
前記最適解探索部は、所定の単語を前記オートマトンに入力して遷移パスおよび遷移先の状態を生成する場合に、当該単語に対応する連接規則による遷移に必要な状態を生成し、生成された当該状態に後続する空遷移を辿って遷移可能な状態を生成しないことを特徴とする形態素解析システム。
【請求項２】
前記連接規則検索部は、所定の非空遷移を表す連接規則と当該連接規則の遷移元を遷移先とし空遷移を表す連接規則とを統合して構成された連接規則を格納した文法辞書から、当該統合された連接規則を検索することを特徴とする請求項１に記載の形態素解析システム。
【請求項３】
前記連接規則検索部は、空遷移による状態の遷移を表す複数の連接規則であって連続し得る連接規則を統合して構成された連接規則を格納した文法辞書から、当該統合された連接規則を検索することを特徴とする請求項２に記載の形態素解析システム。
【請求項４】
前記最適解探索部は、所定の単語を前記オートマトンに入力する場合に、直前に生成された状態を遷移元とする連接規則を、前記連接規則検索部にて検索された前記所定の単語に関する連接規則の中から探索することを特徴とする請求項１に記載の形態素解析システム。
【請求項５】
自然言語文に対する形態素解析を行う形態素解析システムにおいて、
処理対象である自然言語文を構成する文字列に対応する単語を所定の単語辞書から検索する単語候補検索部と、
前記単語候補検索部による検索によって得られた各単語の品詞に基づき、所定の文法辞書から当該単語の連接に使用される可能性のある連接規則を検索する連接規則検索部と、
前記単語候補検索部により検索された単語と前記連接規則検索部により検索された連接規則とに基づいて、処理対象の自然言語文に対応するオートマトンを生成し、形態素解析の解を求める最適解探索部とを備え、
前記最適解探索部は、所定の単語を前記オートマトンに入力して遷移パスおよび遷移先の状態を生成する場合に、直前に生成された状態を遷移元とする連接規則を、前記連接規則検索部にて検索された前記所定の単語に関する連接規則の中から探索することを特徴とする形態素解析システム。
【請求項６】
前記連接規則検索部は、前記文法辞書から検索された連接規則を、遷移元をキーとしてソートすることを特徴とする請求項５に記載の形態素解析システム。
【請求項７】
自然言語文に対する形態素解析を行う形態素解析システムにおいて、
自然言語文を構成する単語を格納した単語辞書と、
前記単語辞書に格納された各単語の連接規則を格納した文法辞書と、
前記単語辞書および前記文法辞書を用いて形態素解析を実行する解析処理部と、
前記解析処理部による処理の実行に先立って、前記文法辞書に格納されている連接規則に対し、所定の非空遷移を表す連接規則と当該連接規則の遷移元を遷移先とし空遷移を表す連接規則とを統合して新たな連接規則とする変換を行う前処理部と
を備えたことを特徴とする形態素解析システム。
【請求項８】
前記前処理部は、空遷移による状態の遷移を表す複数の連接規則であって連続し得る連接規則を統合して新たな連接規則とする変換をさらに行うことを特徴とする請求項７に記載の形態素解析システム。
【請求項９】
前記解析処理部は、前記単語辞書から検索された単語と前記文法辞書から検索された連接規則とに基づいて、処理対象の自然言語文に対応するオートマトンを生成すると共に、所定の単語を前記オートマトンに入力して遷移パスおよび遷移先の状態を生成する場合に、当該単語に対応する連接規則による遷移に必要な状態を生成し、生成された当該状態に後続する空遷移を辿って遷移可能な状態を生成しないことを特徴とする請求項７に記載の形態素解析システム。
【請求項１０】
コンピュータを用いて自然言語文に対する形態素解析を行う形態素解析方法であって、
処理対象である自然言語文を構成する文字列に対応する単語を所定の記憶手段に構築された単語辞書から検索するステップと、
検索された前記単語の品詞に基づき、所定の記憶手段に構築された文法辞書から当該単語の連接に使用される可能性のある連接規則を検索するステップと、
前記コンピュータが、検索された前記単語および前記連接規則に基づいて、処理対象の自然言語文に対応するオートマトンを生成すると共に、所定の単語を当該オートマトンに入力した際に、当該単語に対応する連接規則による遷移に必要な状態を生成し、生成された当該状態に後続する空遷移を辿って遷移可能な状態を生成することなく遷移パスおよび遷移先の状態を生成するステップと
を含むことを特徴とする形態素解析方法。
【請求項１１】
コンピュータを用いて自然言語文に対する形態素解析を行う形態素解析方法であって、
処理対象である自然言語文を構成する文字列に対応する単語を所定の記憶手段に構築された単語辞書から検索するステップと、
検索された前記単語の品詞に基づき、所定の記憶手段に構築された文法辞書から当該単語の連接に使用される可能性のある連接規則を検索するステップと、
前記コンピュータが、検索された前記単語および前記連接規則に基づいて、処理対象の自然言語文に対応するオートマトンを生成すると共に、所定の単語を前記オートマトンに入力して遷移パスおよび遷移先の状態を生成する場合に、直前に生成された状態を遷移元とする連接規則を、検索された前記所定の単語に関する連接規則の中から探索するステップと
を含むことを特徴とする形態素解析方法。
【請求項１２】
コンピュータを用いて自然言語文に対する形態素解析を行う形態素解析方法であって、
前記コンピュータが、所定の記憶手段に構築された文法辞書に格納されている単語の連接規則を読み出し、所定の非空遷移を表す連接規則と当該連接規則の遷移元を遷移先とし空遷移を表す連接規則とを統合して、当該文法辞書に格納するステップと、
処理対象である自然言語文を構成する文字列に対応する単語を所定の記憶手段に構築された単語辞書から検索するステップと、
検索された前記単語の品詞に基づき、前記文法辞書から当該単語の連接に使用される可能性のある連接規則を検索するステップと、
前記コンピュータが、検索された前記単語および前記連接規則に基づいて、処理対象の自然言語文に対応するオートマトンを生成するステップと
を含むことを特徴とする形態素解析方法。
【請求項１３】
前記オートマトンを生成するステップでは、前記コンピュータが、所定の単語を当該オートマトンに入力した際に、当該単語に対応する連接規則による遷移に必要な状態を生成し、生成された当該状態に後続する空遷移を辿って遷移可能な状態を生成することなく遷移パスおよび遷移先の状態を生成することを特徴とする請求項１２に記載の形態素解析方法。
【請求項１４】
コンピュータを制御して、自然言語文に対する形態素解析を行うプログラムであって、
処理対象である自然言語文を構成する文字列に対応する単語を所定の記憶手段に構築された単語辞書から検索する処理と、
検索された前記単語の品詞に基づき、所定の記憶手段に構築された文法辞書から当該単語の連接に使用される可能性のある連接規則を検索する処理と、
検索された前記単語および前記連接規則に基づいて、処理対象の自然言語文に対応するオートマトンを生成すると共に、所定の単語を当該オートマトンに入力した際に、当該単語に対応する連接規則による遷移に必要な状態を生成し、生成された当該状態に後続する空遷移を辿って遷移可能な状態を生成することなく遷移パスおよび遷移先の状態を生成し、所定の記憶手段に格納する処理と
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１５】
コンピュータを制御して、自然言語文に対する形態素解析を行うプログラムであって、
処理対象である自然言語文を構成する文字列に対応する単語を所定の記憶手段に構築された単語辞書から検索する処理と、
検索された前記単語の品詞に基づき、所定の記憶手段に構築された文法辞書から当該単語の連接に使用される可能性のある連接規則を検索する処理と、
検索された前記単語および前記連接規則に基づいて、処理対象の自然言語文に対応するオートマトンを生成すると共に、所定の単語を前記オートマトンに入力して遷移パスおよび遷移先の状態を生成する場合に、直前に生成された状態を遷移元とする連接規則を、検索された前記所定の単語に関する連接規則の中から探索し、所定の記憶手段に格納する処理と
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１６】
コンピュータを制御して、自然言語文に対する形態素解析を行うプログラムであって、
所定の記憶手段に構築された文法辞書に格納されている単語の連接規則を読み出し、所定の非空遷移を表す連接規則と当該連接規則の遷移元を遷移先とし空遷移を表す連接規則とを統合して、当該文法辞書に格納する処理と、
処理対象である自然言語文を構成する文字列に対応する単語を所定の記憶手段に構築された単語辞書から検索する処理と、
検索された前記単語の品詞に基づき、前記文法辞書から当該単語の連接に使用される可能性のある連接規則を検索する処理と、
検索された前記単語および前記連接規則に基づいて、処理対象の自然言語文に対応するオートマトンを生成する処理と
を前記コンピュータに実行させることを特徴とするプログラム。
【請求項１７】
前記オートマトンを生成する処理では、所定の単語を当該オートマトンに入力した際に、当該単語に対応する連接規則による遷移に必要な状態を生成し、生成された当該状態に後続する空遷移を辿って遷移可能な状態を生成することなく遷移パスおよび遷移先の状態を生成する処理を前記コンピュータに実行させることを特徴とする請求項１６に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータを用いた自然言語処理における形態素解析を実行するシステムおよびその解析方法に関する。
【背景技術】
【０００２】
コンピュータを用いた自然言語処理における重要な処理として、解析対象である自然言語文（以下、入力文または単に文という）を解析して単語に分割し、得られた各単語の品詞等の推定を行う形態素解析がある。
形態素解析は、大まかに、単語候補の検索、検索によって得られた各単語候補が該当する品詞の連接規則の検索、検索された単語候補および品詞の連接規則における最適解の探索という３つのステップで処理が行われる。
【０００３】
ここで、単語候補の検索は、入力文を適当な文字列で切り分け、あらかじめ用意された単語辞書（データベース）と照合して、当該入力文を構成可能な単語（単語候補）を得る処理である。
品詞の連接規則の検索は、単語候補の検索によって得られた各単語の品詞に基づき、あらかじめ用意された文法辞書（データベース）を参照して、各単語の連接に使用される可能性のある連接規則を得る処理である。単語の中には文脈に応じて異なる品詞として扱われるものがある。そこで、単語候補の検索で得られた単語が取り得る全ての品詞（品詞候補）について連接規則を取得する。
最適解の探索は、上記の検索で得られた単語を連接規則に従って組合せ、入力文を構成する単語列として最適なものを選択する処理である。
【０００４】
通常、文中には多数の「単語候補」とそれら各単語の「品詞候補」とが含まれる。一般に、このような多数の候補を扱う処理は状態遷移として扱うことができ、「非決定性有限状態オートマトン（Non-deterministic Finite-state Automaton：ＮＦＡ）」を用いた形態素解析システムが実現されている（例えば、非特許文献１参照）。
【０００５】
図１１は、従来の形態素解析システムによる形態素解析のプロセスを示す図である。
例として、入力文「南方は夏だ。」を形態素解析する場合を考える。
まず、単語候補の検索が行われ、「南方（名詞）」、「は（助詞）」、「夏（名詞）」といった単語候補が取得される。
次に、品詞の連接規則の検索が行われ、各単語候補の各品詞に対応する連接規則が取得される。図示の例では、名詞に対する「名詞：文節頭→名詞尾」、「名詞：接頭辞→名詞尾」、助詞に対する「助詞：助詞頭→格助詞」といった連接規則が取得される。これは、例えば連接規則「名詞：文節頭→名詞尾」では、文中に所定の名詞があるとき、その名詞の前後で文節頭から名詞尾への連接が可能であることを意味している。ここで、文節頭や名詞尾などとあるのは、最適解の探索をＮＦＡにて行う場合の各状態（ノード）を示している。すなわち、連接規則「名詞：文節頭→名詞尾」の例では、入力文に対応するＮＦＡは、状態「文節頭」のときに名詞を入力すると状態「名詞尾」に遷移する。
【０００６】
また、最適解の探索用のＮＦＡでは、特定の状態から特定の状態へ入力文字を伴わない空遷移（ε遷移）にて遷移する場合がある。例えば、状態「名詞尾」のときに空遷移により状態「助詞頭」へ遷移することができ、これにより名詞の後ろに助詞が連接可能となる。したがって、この空遷移に関する情報も品詞の連接規則として文法辞書に格納されており、品詞の連接規則の検索で必要な連接規則が取得される。図１１の例では、名詞尾に対する連接規則として「ｎｕｌｌ：名詞尾→助詞頭」、「ｎｕｌｌ：名詞尾→数詞頭」などが取得されている。
【０００７】
これらの検索の後、最適解探索を行うために、図１１に示すＮＦＡが生成されていく。図示の例では、まず、名詞「南方」の入力により状態「文節頭」から状態「名詞尾」に遷移する。次に、状態「名詞尾」からは空遷移によって「数詞頭」、「助詞頭」、「英字頭」に遷移可能であり、さらに状態「数詞頭」から「漢数字」へ遷移するので、これら全ての可能な状態が生成される。そして、実際の入力文では単語「南方」の後ろに助詞「は」があるので、この助詞「は」の入力により状態「助詞頭」が選択され、状態「格助詞」へ遷移することとなる。
【０００８】
【非特許文献１】丸山宏、荻野紫穂、「正規文法に基づく日本語形態素解析」、情報処理学会論文誌、日本、情報処理学会、平成６年７月、第３５巻、第７号、ｐ．１２９３−１２９９
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上述したように、形態素解析において、解析対象の文に対して得られた単語候補と品詞の連接規則とから最適解を探索するために、非決定性有限状態オートマトン（ＮＦＡ）を用いることが可能である。
しかし、一般にＮＦＡは、同じ状態・同じ入力に対し、次の状態が一意に定まらないため、探索パスの数が多くなる傾向がある。したがって、ＮＦＡを用いた形態素解析システムは解析実行時の処理速度が遅くなるという問題があった。
【００１０】
このＮＦＡを用いた形態素解析システムの処理速度を向上させるために、プリプロセス（前処理）の段階でＮＦＡ中から空遷移が取り除かれるように品詞の連接規則を変換することが従来から行われている。例えば、図１１の例で、状態「文節頭」から状態「助詞頭」に至る遷移があることは、処理を開始する前に「品詞の連接規則」を参照するだけで分かることである。そこで、前もって非空遷移である「名詞：文節頭→名詞尾」の連接規則と空遷移である「ｎｕｌｌ：名詞尾→助詞頭」の連接規則とを統合し「名詞：文節頭→助詞頭」としておけば空遷移を扱わずに同等の処理を行うことが可能となる。この手法は、ＮＦＡ中から空遷移を取り除く変換として、形態素解析以外の分野でも用いられ、良く知られている手法である。
【００１１】
しかし、図１１を参照すれば明らかなように、形態素解析においては、「品詞の連接規則」を扱う上で生成される大半の状態は、実際に単語が入力された時点で棄却されてしまう。図１１の例では、「名詞尾」「数詞頭」「漢数字」「英字頭」などの大半の状態は、単語「南方」に続く単語「は」が入力された時点で、遷移が続く可能性がなくなり、棄却される。このように、生成した直後に棄却されるような状態を多数生成することは無駄であり、処理上のボトルネックになる。
【００１２】
また、ＮＦＡを用いて最適解を探索するためには、所定の単語間の連接規則を検索した上で、その連接規則を実際にＮＦＡに入力して受理可能かどうかを調べる照合作業を、各単語、各連接規則に対して逐一行っている。例えば図１１で、単語「南方」の入力後に、後続の単語「は」が該当する最適な連接規則を探索すると、単語「は」は助詞だけではなく、名詞としての連接規則も持つため、それぞれをＮＦＡに入力して照合することとなる。そのため、該当する連接規則が多い場合には、照合作業の実行回数が増えて、最適解の探索処理が非常に重くなる。
【００１３】
そこで本発明は、ＮＦＡを用いた形態素解析システムの処理速度を向上させることを目的とする。
また本発明は、ＮＦＡを生成する際に不要な状態の生成を抑制することにより、形態素解析の処理速度の向上を実現することを他の目的とする。
さらに本発明は、ＮＦＡにおける入力が受理可能かどうかを試行する回数を減少させることにより、形態素解析の処理速度の向上を実現することを他の目的とする。
【課題を解決するための手段】
【００１４】
上記の目的を達成する本発明は、次のように構成された形態素解析システムとして実現される。このシステムは、処理対象である自然言語文を構成する文字列に対応する単語を所定の単語辞書から検索する単語候補検索部と、得られた各単語の品詞に基づき、所定の文法辞書から、この単語の連接に使用される可能性のある連接規則を検索する連接規則検索部と、これらの単語および連接規則に基づいて、処理対象の自然言語文に対応するオートマトンを生成し、形態素解析の解を求める最適解探索部とを備える。また、文法辞書に格納されている連接規則を変換する前処理部を備える。
【００１５】
より詳細には、前処理部は、文法辞書に格納されている連接規則に対し、所定の非空遷移を表す連接規則と、この連接規則の遷移元を遷移先とし空遷移を表す連接規則とを統合して新たな連接規則とする変換を行う。また、さらに好ましくは、空遷移による状態の遷移を表す複数の連接規則であって連続し得る連接規則を統合して新たな連接規則とする変換を行う。この前処理により、文法辞書に格納された連接規則は、空遷移による連接規則が他の連接規則に統合され、除去されたものとなる。
【００１６】
上記の最適解探索部は、オートマトンを生成する際、所定の単語をオートマトンに入力して遷移パスおよび遷移先の状態を生成する場合に、この単語に対応する連接規則による遷移に必要な状態を生成し、生成された状態に後続する空遷移を辿って遷移可能な状態を生成しない。
また、所定の単語をオートマトンに入力して遷移パスおよび遷移先の状態を生成する場合に、直前に生成された状態を遷移元とする連接規則を、連接規則検索部にて検索された所定の単語に関する連接規則の中から探索する。
【００１７】
さらに上記の目的を達成する他の本発明は、コンピュータを用いて実行される、次のような形態素解析方法としても実現される。この形態素解析方法は、処理対象である自然言語文を構成する文字列に対応する単語を所定の記憶手段に構築された単語辞書から検索するステップと、検索された単語の品詞に基づき、所定の記憶手段に構築された文法辞書から、この単語の連接に使用される可能性のある連接規則を検索するステップと、検索された単語および連接規則に基づいて、処理対象の自然言語文に対応するオートマトンを生成するステップとを含む。そしてこのオートマトンを生成するステップにおいて、所定の単語をオートマトンに入力した際に、この単語に対応する連接規則による遷移に必要な状態を生成し、生成された状態に後続する空遷移を辿って遷移可能な状態を生成することなく遷移パスおよび遷移先の状態を生成する。
また、このオートマトンを生成するステップにおいて、所定の単語をオートマトンに入力して遷移パスおよび遷移先の状態を生成する場合に、直前に生成された状態を遷移元とする連接規則を、検索された所定の単語に関する連接規則の中から探索する。
さらに、上記の形態素解析の各ステップに先立って、所定の記憶手段に構築された文法辞書に格納されている単語の連接規則を読み出し、所定の非空遷移を表す連接規則と、かかる連接規則の遷移元を遷移先とし空遷移を表す連接規則とを統合して、文法辞書に格納する前処理のステップをさらに含むことができる。
【００１８】
また本発明は、コンピュータを制御して上述した形態素解析システムとして機能させるプログラム、あるいは上記の形態素解析方法の各ステップに対応する処理をコンピュータに実行させるプログラムとしても実現される。このプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより、提供することができる。
【発明の効果】
【００１９】
以上のように構成された本発明によれば、形態素解析のプリプロセスの段階で、ＮＦＡ（オートマトン）を生成するために用いられる連接規則のうち、空遷移を表す連接規則を除去しておき、ＮＦＡを生成する際に不要な状態の生成を抑制することにより、形態素解析の処理速度の向上を実現することができる。
また本発明によれば、ＮＦＡの生成時に、ＮＦＡにおける入力が受理可能かどうかを試行する回数を減少させることにより、形態素解析の処理速度の向上を実現することができる。
【発明を実施するための最良の形態】
【００２０】
以下、添付図面を参照して、本発明を実施するための最良の形態（以下、実施形態）について詳細に説明する。
図１は、本実施形態による形態素解析システムを実現するのに好適なコンピュータ装置のハードウェア構成の例を模式的に示した図である。
図１に示すコンピュータ装置は、演算手段であるＣＰＵ（Central Processing Unit：中央処理装置）１０１と、Ｍ／Ｂ（マザーボード）チップセット１０２およびＣＰＵバスを介してＣＰＵ１０１に接続されたメインメモリ１０３と、同じくＭ／Ｂチップセット１０２およびＡＧＰ（Accelerated Graphics Port）を介してＣＰＵ１０１に接続されたビデオカード１０４と、ＰＣＩ（Peripheral Component Interconnect）バスを介してＭ／Ｂチップセット１０２に接続された磁気ディスク装置（ＨＤＤ）１０５、ネットワークインターフェイス１０６と、さらにこのＰＣＩバスからブリッジ回路１０７およびＩＳＡ（Industry Standard Architecture）バスなどの低速なバスを介してＭ／Ｂチップセット１０２に接続されたフロッピー（登録商標）ディスクドライブ１０８およびキーボード／マウス１０９とを備える。
【００２１】
なお、図１は本実施形態を実現するコンピュータ装置のハードウェア構成を例示するに過ぎず、本実施形態を適用可能であれば、他の種々の構成を取ることができる。例えば、ビデオカード１０４を設ける代わりに、ビデオメモリのみを搭載し、ＣＰＵ１０１にてイメージデータを処理する構成としても良いし、外部記憶装置として、ＡＴＡ（AT Attachment）やＳＣＳＩ（Small Computer System Interface）などのインターフェイスを介してＣＤ−Ｒ（Compact Disc Recordable）やＤＶＤ−ＲＡＭ（Digital Versatile Disc Random Access Memory）のドライブを設けても良い。
【００２２】
図２は、本実施形態による形態素解析システムの機能構成を示す図である。
図２を参照すると、本実施形態の形態素解析システムは、連接規則に対する前処理を行う前処理部１０と、形態素解析を実行する解析処理部２０と、解析処理部２０による形態素解析に用いられる単語辞書３０および文法辞書４０とを備える。前処理部１０および解析処理部２０は、例えば図１に示したコンピュータ装置のプログラム制御されたＣＰＵ１０１にて実現され、単語辞書３０および文法辞書４０は、例えば図１の磁気ディスク装置１０５に格納されて実現される。
また、解析処理部２０は、単語候補の検索を行う単語候補検索部２１と、品詞の連接規則の検索を行う連接規則検索部２２と、検索結果である単語候補および品詞の連接規則における最適解を探索する最適解探索部２３とを備える。単語辞書３０には、少なくとも単語とその品詞を特定する情報が登録されている。文法辞書４０には、品詞の連接規則が格納される。連接規則は、遷移元の状態（ノード）と遷移先の状態（ノード）とを対にして表現される。初期的には、連接規則として、所定の単語の入力に伴って適用される非空遷移を表す連接規則と、所定の状態から入力文字を伴わずに適用される空遷移（ε遷移）を表す連接規則とが格納されているものとする。
【００２３】
前処理部１０は、形態素解析に対する前処理として、文法辞書４０に格納されている品詞の連接規則における空遷移（ε遷移）を表す規則を統合する。本実施の形態では、所定の非空遷移を表す連接規則と、この連接規則の前に連続（以下、このような連続関係を先続と呼ぶ）する空遷移を表す連接規則とを統合して、新たな連接規則とする。
図３は、本実施形態の前処理部１０による処理を説明するフローチャートである。
図３に示すように、前処理部１０は、まず文法辞書４０に格納されている連接規則を空遷移と非空遷移とに分類する（ステップ３０１）。そして、空遷移の数をＰとし（ステップ３０２）、処理の済んだ空遷移の数を示す変数をｐと定義して初期化（ｐ:=１）する（ステップ３０３）。
【００２４】
次に、前処理部１０は、文法辞書４０からｐ番目の空遷移を読み出し（ステップ３０４）、空遷移の統合が可能であれば統合を行う（ステップ３０５）。そして、変数ｐの値を１加算して（ステップ３０６）、全ての空遷移に対して（すなわちｐ＝Ｐとなるまで）ステップ３０４以降の処理を繰り返す（ステップ３０７）。文法辞書４０から読み出され、必要に応じて統合処理が行われた各空遷移は、例えば図１に示したメインメモリ１０３や磁気ディスク装置１０５等の所定の記憶手段に保持される。
ここで、空遷移の統合とは、次のような処理である。
図４に示すような連接規則があるものとする。空遷移を表す連接規則のうち、「ｎｕｌｌ：名詞尾→数詞頭」と「ｎｕｌｌ：数詞頭→漢数字」とに着目すると、名詞尾から数詞頭へも、数詞頭から漢数字へも何らの入力文字も伴わずに遷移し得ることがわかる。そこで、これらを統合して「ｎｕｌｌ：名詞尾→漢数字」という規則を生成する。これにより、統合された連接規則に関しては、例えば、名詞の後に漢数字が続く際に、名詞尾→数詞頭→漢数字という２段階の遷移が行われていたものを名詞尾→漢数字という１回の遷移で処理ができることとなる。
【００２５】
次に、前処理部１０は、文法辞書４０に格納されている非空遷移の数をＱとし（ステップ３０８）、処理の済んだ非空遷移の数を示す変数をｑと定義して初期化（ｑ:=１）する（ステップ３０９）。この後、前処理部１０は、文法辞書４０からｑ番目の非空遷移を読み出し（ステップ３１０）、所定の記憶手段に保持されている必要な統合処理の行われた非空遷移の中から、読み出された非空遷移に先続する空遷移を検索する（ステップ３１１）。そして、検出された空遷移（以下、先続する空遷移と呼ぶ）の数をＲとし（ステップ３１２）、処理の済んだ先続する空遷移の数を示す変数をｒと定義して初期化（ｒ:=１）する（ステップ３１３）。
【００２６】
次に、前処理部１０は、ｒ番目の先続する空遷移と着目中のｑ番目の非空遷移とを統合して新たな連接規則を生成する（ステップ３１４）。例えば、図４に示した連接規則で、「助詞：助詞頭→格助詞」をｑ番目の非空遷移として着目した場合、これに先続する空遷移の連接規則は「ｎｕｌｌ：名詞尾→助詞頭」のみである。したがって、これらを統合することによって、新たな連接規則「助詞：名詞尾→格助詞」が生成される。
【００２７】
次に前処理部１０は、変数ｒの値を１加算して（ステップ３１５）、全ての先続する空遷移に対して（すなわちｒ＝Ｒとなるまで）ステップ３１４以降の処理を繰り返す（ステップ３１６）。
着目中のｑ番目の非空遷移に先続する全ての空遷移に関して統合処理が済んだならば（ステップ３１６でＮｏ）、次に前処理部１０は、変数ｑの値を１加算して（ステップ３１７）、全ての非空遷移に対して（すなわちｑ＝Ｑとなるまで）ステップ３１０以降の処理を繰り返す（ステップ３１８）。
【００２８】
全ての非空遷移に対して以上の処理が済んだならば（ステップ３１８でＮｏ）、ステップ３１４で生成された新たな連接規則を、文法辞書４０に格納して処理を終了する。
以上のようにして、空遷移による状態の遷移を表す複数の連接規則であって連続し得る連接規則を統合して１つの連接規則にすると共に、所定の非空遷移を表す連接規則と当該連接規則の遷移元を遷移先とし空遷移を表す連接規則とを統合して１つの連接規則にする変換が行われた。そして、これ以後の形態素解析処理ではこの前処理で生成された新たな連接規則を格納した文法辞書４０にて解析処理が行われる。すなわち、この前処理は、文法辞書４０に格納されている品詞の連接規則を適宜統合して、新たな文法辞書４０を作成することに相当する。したがって、以上の前処理は、形態素解析システムにおいて最初に１回だけ行えば良く、形態素解析処理を実行するたびに行う必要はない。
【００２９】
さて、ＮＦＡを用いた状態遷移により処理を実行する場合、常に、所定の状態から次にどのような入力があっても直ちに受理可能かどうか判定できるようにする必要がある。
図５は、ＮＦＡを用いた状態遷移を説明する図である。
図５（Ａ）に示すように、図４の連接規則を用いて入力文「南方／は／夏／だ／。」を処理する場合、「南方（名詞）」が入力されて状態が名詞尾になると、次に名詞尾からの空遷移の連接規則に従って、数詞頭、助詞頭、漢数字、英字頭といった状態が生成され、「南方（名詞）」に後続する文字の入力を待つこととなる。これは、従来の先行する非空遷移と後続する空遷移を統合して空集合を除去した連接規則においても同様である。すなわち、図５（Ｂ）に示すように、「南方（名詞）」が入力された時点で、直ちに数詞頭、助詞頭、漢数字、英字頭といった状態が生成されることとなる。
【００３０】
これによって、例えば「南方（名詞）」の後に「は（助詞）」ではなく「３（数詞）」という語が入力された場合でも、すぐに次の遷移が可能かどうかを判定し遷移することができる。これは、次の入力に対して常に準備完了の状態を保つＮＦＡの動作としては望ましいものである。しかし、形態素解析システムにおいてＮＦＡを用いる場合、「南方（名詞）」の後に「は（助詞）」が入力された時点で、連接規則「助詞：助詞頭→格助詞」、「ｎｕｌｌ：名詞尾→助詞頭」もしくは統合された連接規則「助詞：名詞尾→格助詞」が選択され、数詞頭、漢数字、英字頭といった状態は棄却される。すなわち、生成直後に棄却される多数の状態を生成することになるため、非効率的である。
【００３１】
これに対し本実施形態では、所定の語が入力された際に、直ちに後続する空遷移を辿って遷移可能な全ての状態を生成することを行わない。そして、上述したように所定の非空遷移とこれに先続する空遷移とを統合して生成された新たな連接規則を用い、当該所定の語に後続する語が入力されてから、遷移に必要な状態のみを生成する。
図６は、本実施形態によるＮＦＡの状態の生成の様子を示す図である。
図６に示すように、「南方（名詞）」の入力時には名詞尾の状態までが生成され、「は（助詞）」が入力された時点で、連接規則「助詞：名詞尾→格助詞」に基づいて格助詞の状態が生成されるので、数詞頭、漢数字、英字頭といった無用の（すなわち直ちに棄却される）状態は最初から生成されない。また、助詞頭は、空遷移の連接規則「ｎｕｌｌ：名詞尾→助詞頭」が統合後の連接規則「助詞：名詞尾→格助詞」に含まれているので、これも生成されない。
【００３２】
以上の操作は、形態素解析処理にＮＦＡを用いる場合、入力文に対応するＮＦＡを生成するという処理の特徴から、生成されるＮＦＡは当該入力文にのみ対応していれば良く、一般的なＮＦＡに対する要請である「常に後続のどのような入力に対しても準備完了の状態を保つ」ことが必要ないために適用可能なものである。
上記のように、生成されるＮＦＡが空遷移を含まず、さらに生成直後に棄却されるような状態を最初から生成しないことにより、解析処理全体における処理速度の向上を図ることができる。
【００３３】
次に、解析処理部２０について説明する。
解析処理部２０は、単語候補検索部２１、連接規則検索部２２および最適解探索部２３を用いて形態素解析処理を実行する。
図７は、本実施の形態の解析処理部２０による処理を説明するフローチャートである。
図７に示すように、まず、解析処理部２０が解析対象である入力文（文字列）を入力し（ステップ７０１）、入力文の長さ（文字数）をＳとし（ステップ７０２）、処理のために着目している文字の位置を示す変数をｓと定義して初期化（ｓ:=１）する（ステップ７０３）。そして、単語候補検索部２１により、単語辞書３０を参照し、入力文のｓ番目の位置から始まる文字列に対応する単語（単語候補）を検索する（ステップ７０４）。また、連接規則検索部２２により、文法辞書４０を参照し、ステップ７０４で得られた単語候補が該当する連接規則を検索する（ステップ７０５）。検出された単語候補および連接規則は、例えば図１に示したメインメモリ１０３やＣＰＵ１０１のキャッシュメモリ等に保持され、最適解探索部２３の処理において用いられる。
【００３４】
次に、解析処理部２０は、最適解探索部２３により、連接規則検索部２２にて検出された連接規則に基づいて遷移パスおよび各状態を生成していき、入力文に対応するＮＦＡを生成する（ステップ７０６）。ＮＦＡの生成においては上述したように、所定の単語を入力した際に、当該単語に対応する連接規則による遷移に必要な状態のみを生成し、後続する空遷移を辿って遷移可能な状態は生成しない。生成されたＮＦＡは、例えば図１に示したメインメモリ１０３やＣＰＵ１０１のキャッシュメモリ等に保持される。なお、ＮＦＡの生成処理の具体的な内容については、後述する。
この後、解析処理部２０は、変数ｓの値を１加算して（ステップ７０７）、句読点や括弧などで表される入力文の文末（文の区切り位置）に達したかどうかを判断する（ステップ７０８）。文末に達していないならば、単語候補検索部２１に処理を戻し、ステップ７０７で設定された新たな変数ｓの値でステップ７０４以降の処理を繰り返す。
【００３５】
一方、文末に達したならば、この時点で入力文に対する文頭から文末に至る遷移パスが複数生成されている場合、言い換えれば、入力文を構成する単語列およびその連接規則として可能な組合せが複数存在する場合がある。そこで、次に最適解探索部２３は、生成された複数の遷移パスの中から最適解を探索する（ステップ７０９）。最適解の探索は、遷移パスに点数（コスト）を付け、遷移パス全体について点数を加算し、その数値が最も小さいもの、すなわちコストが最小のものを採用する最小コスト法など、既知の任意の手法を用いて行うことができる。得られた最適解は、形態素解析の結果として出力される（ステップ７１０）。上述した「南方は夏だ。」という入力文の場合、次のような解析結果が得られる。
南方／は  ／夏  ／だ    ／。    ／
名詞／助詞／名詞／助動詞／句読点／
この後、解析処理部２０は、変数ｓの値が入力文の長さＳに達したかどうかを判断し（ステップ７１１）、ｓ≦Ｓであれば、単語候補検索部２１に処理を戻し、ステップ７０４以降の処理を繰り返す。一方、変数ｓの値がＳを越えたならば、入力文全体に対して形態素解析処理が行われたので、処理を終了する。
【００３６】
次に、ステップ７０６のＮＦＡの生成処理について詳述する。
図８は、ステップ７０６の処理の具体的な内容を説明するフローチャートである。
図８に示すように、連接規則検索部２２は、まず着目しているｓ番目の位置に対して生成されている状態のうちで、次の遷移における遷移元となる状態の数をＴとする（ステップ８０１）。そして、処理の済んだ状態の数を示す変数をｔと定義して初期化（ｔ:=１）する（ステップ８０２）。
【００３７】
次に、連接規則検索部２２は、ステップ７０５で検索された連接規則の中で、ｔ番目の状態を遷移元に持つものがあるかどうかを調べる（ステップ８０３）。そのような連接規則が存在する場合は、その連接規則にしたがって、遷移パスおよび遷移先の状態を生成する（ステップ８０４）。
遷移パスおよび遷移先の状態を生成した後、またはｔ番目の状態を遷移元に持つ連接規則がなかった場合は、変数ｔの値を１加算して（ステップ８０５）、遷移元となる全ての状態に対して（すなわちｔ＝Ｔとなるまで）ステップ８０３以降の処理を繰り返す（ステップ８０６）。
【００３８】
以上のように、本実施形態では、所定の単語をオートマトンに入力する際に、その単語に関する連接規則がオートマトンにおいて受理可能かどうかを調べるために、まず直前に生成された状態を調べ、この状態を遷移元とする連接規則を、連接規則検索部によって検索された連接規則の中から探索する。この操作は、形態素解析処理にＮＦＡを用いる場合、入力文に対応するＮＦＡを生成するため、単語辞書３０および文法辞書４０の検索により、どの単語がどの連接規則を持つかということが前もって分かっているために、適用可能なものである。
上記のように、どの単語がどの連接規則を持つかという情報を用い、オートマトンにおいて直前に生成された状態をキーとして受理可能な連接規則を探索することにより、オートマトンが受理可能かどうかを調べるために連接規則をオートマトンへ入力する試行回数を大幅に減少させ、解析処理全体における処理速度の向上を図ることができる。
【００３９】
ここで、連接規則検索部によって連接規則が検索された際に、検出された連接規則を、遷移元の状態をキーとしてソートしておけば、この連接規則の探索において各連接規則にアクセスする場合に、バイナリサーチを行うことができ、より効率よく探索を行うことができる。この場合、この連接規則の探索において、次の遷移における遷移元となる各状態へのアクセスをランダムアクセス、各連接規則へのアクセスをリニアアクセスとして、オートマトンが受理可能かどうかを調べる対象となる連接規則の数をｎとすると、連接規則のオートマトンへの入力を試行する回数は、ｌｏｇ（ｎ）回となる。
【００４０】
従来のように、まず入力する単語が該当する連接規則を探索し、次にその連接規則を１つずつオートマトンに入力して受理可能かどうかを判断していく手法では、同じ条件で連接規則のオートマトンへの入力を試行する回数はｎ回となる。したがって、ｎの値が大きいときは、ｌｏｇ（ｎ）＜＜ｎとなり、本実施形態の手法は、従来の手法と比較して大幅な試行回数減少が得られることとなる。例えば、ｎ＝２５６のとき、ｌｏｇ（２５６）／２５６＝８／２００＝０．０４で試行回数は２５分の１になる。これにより、より一層の解析処理速度の向上が得られる。
【００４１】
以上の実施形態では、解析対象の自然言語文として日本語を用いた例を示したが、他の自然言語文に対する形態素解析においても、本発明を適用できることは言うまでもない。例えば、単語辞書３０に、図９に示すような英単語の情報が格納されており、文法辞書４０に、図１０に示すような連接規則が格納されているものとする。なお、図９において、surfaceには単語が登録され、POS codeには各単語の品詞（part of speech）が登録されている。また図１０において、Adjacency definitionsには連接規則、すなわち遷移元の状態（ノード）と遷移先の状態（ノード）とが登録されている。
この場合、図１０中の空遷移の連接規則「ｎｕｌｌ：Ｎｏｕｎ→Ｎｕｍｅｒｉｃ」は、前処理部１０による図３に示した処理により、非空遷移の連接規則「Ｎｕｍｅｒｉｃ：Ｎｕｍｅｒｉｃ→Ｖｅｒｂ」と統合して、連接規則「Ｎｕｍｅｒｉｃ：Ｎｏｕｎ→Ｖｅｒｂ」としておくことができる。
【００４２】
入力文として、“The little boy ran quickly.”という英文が与えられた場合を考える。この場合、単語候補検索部２１により図９の単語辞書３０から単語が検索され、連接規則検索部２２により図１０の文法辞書４０から各単語に対応する連接規則が検索されて、最適解探索部２３によるＮＦＡの生成が行われる。
例えば、「The(Article)」が入力されると、Ａｒｔｉｃｌｅ（冠詞）に対する連接規則「Ａｒｔｉｃｌｅ：ＳＴＡＲＴ→Ａｄｊｅｃｔｉｖｅ」に基づいて遷移パスおよび遷移先の状態が生成され、続いて「little(Adjective)」が入力されると、Ａｄｊｅｃｔｉｖｅ（形容詞）に対する連接規則「Ａｄｊｅｃｔｉｖｅ：Ａｄｊｅｃｔｉｖｅ→Ｎｏｕｎ」に基づいて遷移パスおよび遷移先の状態が生成される。
このとき、予め空遷移の連接規則が後続の非空遷移の連接規則に統合されているので、遷移規則に基づく遷移に必要な状態のみが生成され、空遷移を辿って遷移可能な全ての状態を生成することを行わない。
【００４３】
また、単語「little」に対して適用可能な連接規則は、図９の単語辞書３０および図１０の文法辞書４０によれば、単語「little」がＡｄｊｅｃｔｉｖｅである場合、Ａｄｖｅｒｂ（副詞）である場合、Ｎｏｕｎ（名詞）である場合の３つがある。そして、オートマトンがこれらの連接規則のいずれを受理可能であるかは、単語「The(Article)」の入力にしたがって生成された状態Ａｄｊｅｃｔｉｖｅをキーとして探索することで、全ての連接規則をオートマトンに入力し試行するまでもなく調べることができる。
【００４４】
上記のような操作で入力文“The little boy ran quickly.”に対するオートマトンを生成し、最終的に、次のような解析結果が得られる。
The    ／little   ／boy ／ran ／quickly／.／
Article／Adjective／Noun／Verb／Adverb ／ ／
以上説明したように、本実施形態は、英語文の形態素解析にもそのまま適用できるものであるが、その他の任意の言語における文の形態素解析に対しても、同様に適用可能である。
【図面の簡単な説明】
【００４５】
【図１】本実施形態による形態素解析システムを実現するのに好適なコンピュータ装置のハードウェア構成の例を模式的に示した図である。
【図２】本実施形態による形態素解析システムの機能構成を示す図である。
【図３】本実施形態の前処理部による処理を説明するフローチャートである。
【図４】本実施形態で用いられる連接規則の例を示す図である。
【図５】ＮＦＡ（オートマトン）を用いた状態遷移を説明する図である。
【図６】本実施形態によるＮＦＡの状態の生成の様子を示す図である。
【図７】本実施の形態の解析処理部による処理を説明するフローチャートである。
【図８】図７におけるステップ７０６の処理の具体的な内容を説明するフローチャートである。
【図９】本実施形態を英語文の形態素解析に用いる場合の単語辞書の例を示す図である。
【図１０】本実施形態を英語文の形態素解析に用いる場合の文法辞書の例を示す図である。
【図１１】従来の形態素解析システムによる形態素解析のプロセスを示す図である。
【符号の説明】
【００４６】
１０…前処理部、２０…解析処理部、２１…単語候補検索部、２２…連接規則検索部、２３…最適解探索部、３０…単語辞書、４０…文法辞書、１０１…ＣＰＵ（Central Processing Unit：中央処理装置）、１０３…メインメモリ、１０５…磁気ディスク装置（ＨＤＤ）
【図１】
2005122444.tif 000003
【図２】
2005122444.tif 000004
【図３】
2005122444.tif 000005
【図４】
2005122444.tif 000006
【図５】
2005122444.tif 000007
【図６】
2005122444.tif 000008
【図７】
2005122444.tif 000009
【図８】
2005122444.tif 000010
【図９】
2005122444.tif 000011
【図１０】
2005122444.tif 000012
【図１１】
2005122444.tif 000013