(57)【特許請求の範囲】
【請求項１】
日本語テキストを入力として与えられた際に、入力文を構成する単語列を出力する日本語形態素解析方法であって、
前向きＤＰ探索手段が、前記入力文のある文字位置から始まる全ての部分文字列を単語辞書の単語表記と照合して単語候補として提案し、文頭からある単語に至るまでの単語列の同時確率を最大化する最適部分経路の確率を最後の単語が異なる場合毎に計算し、計算結果を最適経路スコアテーブルに記録する前向きＤＰ探索ステップと、
単語仮説生成手段が、前記前向きＤＰ探索ステップにおいて、前記入力文のある文字位置から始まる部分文字列が前記単語辞書の内容を照合しなかった場合、その部分文字列が単語を構成すると仮定した場合の単語出現確率を、単語長確率と単語内文字２つ組の確率から単語を構成する文字列の同時確率を与える単語モデルから求める単語仮説生成ステップと、
後向きＡ*探索手段が、前記前向きＤＰ探索ステップで計算された前記最適経路スコアテーブルの値を入力とし、文末から文頭へ一単語ずつ進むＡ*アルゴリズムを用いて、単語二つ組確率の積が最も大きいものから順番に一つずつ形態素解析候補を求める後向きＡ*探索ステップと、
を行うことを特徴とする日本語形態素解析方法。
【請求項２】
入力文に含まれる単語の中で辞書に登録されていないものを出力する辞書未登録語収集方法であって、
前向きＤＰ探索手段が、入力文のある文字位置から始まる全ての部分文字列を単語辞書の単語表記と照合して単語候補として提案し、文頭からある単語に至るまでの単語列の同時確率を最大化する最適部分経路の確率を最後の単語が異なる場合毎に計算し、計算結果を最適経路スコアテーブルに記録する前向きＤＰ探索ステップと、
単語仮説生成手段が、前記前向きＤＰ探索ステップにおいて、前記入力文のある文字位置から始まる部分文字列が前記単語辞書の内容を照合しなかった場合、その部分文字列が単語を構成すると仮定した場合の単語出現確率を、単語長確率と単語内文字２つ組の確率から単語を構成する文字列の同時確率を与える単語モデルから求める単語仮説生成ステップと、
後向きＡ*探索手段が、前記前向きＤＰ探索ステップで計算された前記最適経路スコアテーブルの値を入力とし、文末から文頭へ一単語ずつ進むＡ＊アルゴリズムを用いて、単語二つ組確率の積が最も大きいものから順番に一つずつ形態素解析候補を求める後向きＡ*探索ステップと、
単語頻度推定手段が、前記後向きＡ＊探索ステップにより求められた一つの文に対する複数の形態素解析候補とその確率から単語の頻度の期待値を求める単語頻度推定ステップと、
日本語テキストにおける前記単語の頻度の期待値が大きい順番に任意の個数の単語仮説を辞書未登録語として提示する出力ステップと、
を行うことを特徴とする辞書未登録語収集方法。
【請求項３】
日本語テキストを入力として与えられた際に、入力文を構成する単語列を出力する出力手段を有する日本語形態素解析装置であって、
単語２つ組確率から文を構成する単語列の同時確率を与える単語分割モデルと、
単語長確率と単語内文字２つ組の確率から単語を構成する文字列の同時確率を与える単語モデルと、
入力文のある文字位置から始まる全ての部分文字列を単語辞書の単語表記と照合して単語候補として提案し、文頭からある単語に至るまでの単語列の同時確率を最大化する最適部分経路の確率を最後の単語が異なる場合毎に計算し、計算結果を最適経路スコアテーブルに記録する前向きＤＰ探索手段と、
前記前向きＤＰ探索手段において、前記入力文のある文字位置から始まる部分文字列が前記単語辞書の内容を照合しなかった場合、その部分文字列が単語を構成すると仮定した場合の単語出現確率を前記単語モデルから求める単語仮説生成手段と、
前記前向きＤＰ探索手段で計算された前記最適経路スコアテーブルの値を入力とし、文末から文頭へ一単語ずつ進むＡ*アルゴリズムを用いて、単語二つ組確率の積が最も大きいものから順番に一つずつ形態素解析候補を求める後向きＡ*探索手段と、
を有することを特徴とする日本語形態素解析装置。
【請求項４】
入力文に含まれる単語の中で辞書に登録されていないものを出力する辞書未登録語収集装置であって、
単語２つ組確率から文を構成する単語列の同時確率を与える単語分割モデルと、
単語長確率と単語内文字２つ組の確率から単語を構成する文字列の同時確率を与える単語モデルと、
入力文のある文字位置から始まる全ての部分文字列を単語辞書の単語表記と照合して単語候補として提案し、文頭からある単語に至るまでの単語列の同時確率を最大化する最適部分経路の確率を最後の単語が異なる場合毎に計算し、計算結果を最適経路スコアテーブルに記録する前向きＤＰ探索手段と、
前記前向きＤＰ探索手段において、前記入力文のある文字位置から始まる部分文字列が前記単語辞書の内容を照合しなかった場合、その部分文字列が単語を構成すると仮定した場合の単語出現確率を前記単語モデルから求める単語仮説生成手段と、
前記前向きＤＰ探索手段で計算された前記最適経路スコアテーブルの値を入力とし、文末から文頭へ一単語ずつ進むＡ*アルゴリズムを用いて、単語二つ組確率の積が最も大きいものから順番に一つずつ形態素解析候補を求める後向きＡ*探索手段と、
前記後向きＡ＊探索手段により求められた一つの文に対する複数の形態素解析候補とその確率から単語の頻度の期待値を求める単語頻度推定手段と、
日本語テキストにおける前記単語の頻度の期待値が大きい順番に任意の個数の単語仮説を辞書未登録語として提示する出力手段と、
を有することを特徴とする辞書未登録語収集装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、日本語文を単語に分割する日本語形態素解析方法と装置及び辞書未登録語収集方法と装置に係り、特に、分かち書きされた日本語テキストデータベースから統計的手法により求めた単語分割モデルと単語モデルを用いることにより、入力文が辞書未登録語を含む場合でも精度のよい形態素解析が可能な日本語形態素解析方法と装置及び、形態素解析結果に基づいて辞書未登録語を収集するための辞書未登録語収集方法と装置に関する。
【０００２】
【従来の技術】
従来の第１の日本語形態素解析システムは、文法規則と発見的探索に基づく方法が主流であった。これらは、文法規則として品詞接続表を用い、形態素解析候補の探索の際には、最長一致法や最小文節数法などの発見的規則（heuristics）を用いて候補の順位付けを行なう。しかし、発見的探索に基づく方式は、形態素解析候補に与えられる優先順位の根拠が不明確であり、解析精度もあまり高くない。
【０００３】
近年では、従来の第１の日本語形態素解析システムに代わって、第２の方法として、統計的言語モデルと動的計画法に基づく方法が主流になりつつある。この方法では、大量のテキストデータから学習した統計的な言語モデルを用いることにより、形態素解析候補の優先度の根拠が明確になり、かつ、候補の詳細な順位付けができるようになってきている。
【０００４】
また、動的計画法により、入力文の長さに比例する計算量で効率的に最尤な形態素解析候補を求められるようになってきている。特に、前向きＤＰ後向きＡ* アルゴリズムを用いれば、確率が高い順番に任意の個数の形態素解析候補を求めることができる（永田「前向きＤＰ後向きＡ* アルゴリズムを用いた確率的日本語形態素解析」情報処理学会研究報告94-NL-101-10,pp.73-80,1994）。
【０００５】
しかし、上記の文法規則と発見的探索に基づく方法、および、統計的言語モデルと動的計画法に基づく方法のいずれも、入力文が辞書未登録語、すなわち、未知語を多く含む場合には、解析精度が大きく低下するという問題点がある。
文法規則と発見的探索に基づく方法における未知語処理は、非常に「場あたり的（ad hoc）」である。多くのシステムは、「同じ字種の文字の連続が単語を構成することが多い」、あるいは、「カタカナの連続は外来語の名詞であることが多い」というような文字種に関する発見的規則を用いて、単語の分割および、品詞の付与を行なう方法（吉村・武内・津田・首藤「未登録語を含む日本語文の形態素解析」情処論Vol.30 No.3,pp.294-301,1989)がとられている。あるいは、付属語列などから文節を推定し、そこから付属語を取り除いた部分列を未知語とみなす方法が使われていることも多い。
【０００６】
前者は、未知語処理において、文字列の単語らしさを評価する方法、後者は、ある文脈における文字列の単語らしさを評価する方法とみなすことができるが、どちらの場合も、尤度の根拠が不明確であり、単語仮説の詳細な順位付けも難しい。
【０００７】
統計的言語モデルを用いた未知語処理としては、まず、造語単位の二つ組を用いて単語の生起確率を推定する方法が提案されている（永井・日高「日本語における単語の造語モデルとその評価」情処論Vol.34 No.9,pp.1944-1955,1993)。この方法では、単語辞書の見出し語から造語モデルのパラメータを推定する。この方法は、未知語の単語らしさを評価する有力な手段を与えるが、次のような問題点がある。
（１）漢字で表記される複合語に対する造語モデルであり、漢字文字列以外では、造語単位の設定基準が必ずしも明確ではなく、自動的な処理が難しい。
（２）辞書の見出し語からモデルパラメータを推定するので、モデルパラメータが対象領域のテキストの性質を反映しない。
（３）文字列の単語らしさを評価するだけて、その文字列が現れた文脈（前後の文字列）の情報を使って、単語としての尤もらしさを評価しているわけではない。
【０００８】
この三つの問題を解決する方法として、品詞出現確率・品詞別単語長確率・品詞別文字三つ組確率から構成される単語モデルを用いて文字列の単語らしさに基づいて単語仮説を生成し、前向きＤＰ後向きＡ* アルゴリズムを用いて前後の文脈を考慮した上で最尤な単語仮説を決定する方法が提案されている（永田「文字認識誤り訂正のための頑健な日本語形態素解析法」，情報処理学会  自然言語処理の応用に関するシンポジウム，p.17-24,1995) 。
【０００９】
【発明が解決しようとする課題】
しかしなら、上記の三つ組確率よりなる単語モデルにより単語仮説を生成し、前向きＤＰ後向きＡ* アルゴリズムを用いて最尤な単語仮説を決定する方法には次のような問題点がある。
（１）一つの文に対する単語分割に曖昧性がある場合、互いに重なり合う単語仮説の尤もらしさを比較できない。また、異なる文に含まれている単語仮説の尤もらしさを比較できない。
（２）未知語の品詞推定を単語分割と同時に行なう方法は、一つの文字列に対して複数の品詞候補を割り当てるので、形態素解析の計算量が大幅に増加する。このために処理速度が遅く、より精緻な単語モデルを導入したり探索範囲を広げることにより解析精度を上げることが難しい。
【００１０】
本発明は、上記の点に鑑みなされたもので、
（１）辞書に登録されていない入力文中の単語を正しく同定できない、特に、未知語の品詞推定と単語分割と同時に行なうために、計算量の制約から解析精度を向上することが難しい、
（２）同定された単語仮説の尤もらしさを文内および文間で比較できない、
という従来手法の問題点を解決し、辞書に登録されていない単語が入力文に含まれている場合でも、確率が高い順番に入力文を構成する単語列が提示可能な日本語形態素解析方法及び装置を提供することを目的する。
【００１１】
また、本発明の更なる目的は、訓練テキスト集合における単語仮説の頻度の期待値が大きい順番に任意の個数の単語仮説を辞書未登録語として提示できる辞書未登録語収集方法及び装置を提供することである。
【００１２】
【課題を解決するための手段】
図１は、本発明の原理を説明するためのフローチャートである。
本発明は、日本語テキストを入力として与えられた際に、入力文を構成する単語列を出力する日本語形態素解析方法であって、
前向きＤＰ探索手段が、入力文のある文字位置から始まる全ての部分文字列を単語辞書の単語表記と照合して単語候補として提案し、文頭からある単語に至るまでの単語列の同時確率を最大化する最適部分経路の確率を最後の単語が異なる場合毎に計算し、計算結果を最適経路スコアテーブルに記録する前向きＤＰ探索ステップ（ステップ１）と、
単語仮説生成手段が、前向きＤＰ探索ステップにおいて、入力文のある文字位置から始まる部分文字列が単語辞書の内容を照合しなかった場合、その部分文字列が単語を構成すると仮定した場合の単語出現確率を、単語長確率と単語内文字２つ組の確率から単語を構成する文字列の同時確率を与える単語モデルから求める単語仮説生成ステップ（ステップ２）と、
後向きＡ*探索手段が、前向きＤＰ探索ステップで計算された最適経路スコアテーブルの値を入力とし、文末から文頭へ一単語ずつ進むＡ＊アルゴリズムを用いて、単語二つ組確率の積が最も大きいものから順番に一つずつ形態素解析候補を求める後向きＡ*探索ステップ（ステップ３）と、を行う。
【００１３】
本発明は、入力文に含まれる単語の中で辞書に登録されていないものを出力する辞書未登録語収集方法であって、
前向きＤＰ探索手段が、入力文のある文字位置から始まる全ての部分文字列を単語辞書の単語表記と照合して単語候補として提案し、文頭からある単語に至るまでの単語列の同時確率を最大化する最適部分経路の確率を最後の単語が異なる場合毎に計算し、計算結果を最適経路スコアテーブルに記録する前向きＤＰ探索ステップと、
単語仮説生成手段が、前向きＤＰ探索ステップにおいて、入力文のある文字位置から始まる部分文字列が単語辞書の内容を照合しなかった場合、その部分文字列が単語を構成すると仮定した場合の単語出現確率を、単語長確率と単語内文字２つ組の確率から単語を構成する文字列の同時確率を与える単語モデルから求める単語仮説生成ステップと、
後向きＡ*探索手段が、前向きＤＰ探索ステップで計算された最適経路スコアテーブルの値を入力とし、文末から文頭へ一単語ずつ進むＡ＊アルゴリズムを用いて、単語二つ組確率の積が最も大きいものから順番に一つずつ形態素解析候補を求める後向きＡ*探索ステップと、
単語頻度推定手段が、後向きＡ＊探索ステップにより求められた一つの文に対する複数の形態素解析候補とその確率から単語の頻度の期待値を求める単語頻度推定ステップと、
日本語テキストにおける単語の頻度の期待値が大きい順番に任意の個数の単語仮説を辞書未登録語として提示する出力ステップと、を行う。
【００１４】
図２は、本発明の原理構成図である。
本発明は、日本語テキストを入力として与えられた際に、入力文を構成する単語列を出力する出力手段を有する日本語形態素解析装置１００であって、
単語２つ組確率から文を構成する単語列の同時確率を与える単語分割モデルと、
単語長確率と単語内文字２つ組の確率から単語を構成する文字列の同時確率を与える単語モデルと、
入力文のある文字位置から始まる全ての部分文字列を単語辞書の単語表記と照合して単語候補として提案し、文頭からある単語に至るまでの単語列の同時確率を最大化する最適部分経路の確率を最後の単語が異なる場合毎に計算し、計算結果を最適経路スコアテーブル１１４に記録する前向きＤＰ探索手段１１１と、
前向きＤＰ探索手段１１１において、入力文のある文字位置から始まる部分文字列が単語辞書の内容を照合しなかった場合、その部分文字列が単語を構成すると仮定した場合の単語出現確率を単語モデルから求める単語仮説生成手段１１２と、
前向きＤＰ探索手段１１１で計算された最適経路スコアテーブル１１４の値を入力とし、文末から文頭へ一単語ずつ進むＡ*アルゴリズムを用いて、単語二つ組確率の積が最も大きいものから順番に一つずつ形態素解析候補を求める後向きＡ*探索手段１１３と、を有する。
【００１７】
本発明は、入力文に含まれる単語の中で辞書に登録されていないものを出力する辞書未登録語収集装置２００であって、
単語２つ組確率から文を構成する単語列の同時確率を与える単語分割モデルと、
単語長確率と単語内文字２つ組の確率から単語を構成する文字列の同時確率を与える単語モデルと、
入力文のある文字位置から始まる全ての部分文字列を単語辞書の単語表記と照合して単語候補として提案し、文頭からある単語に至るまでの単語列の同時確率を最大化する最適部分経路の確率を最後の単語が異なる場合毎に計算し、計算結果を最適経路スコアテーブル１１４に記録する前向きＤＰ探索手段１１１と、
前向きＤＰ探索手段１１１において、入力文のある文字位置から始まる部分文字列が単語辞書の内容を照合しなかった場合、その部分文字列が単語を構成すると仮定した場合の単語出現確率を単語モデルから求める単語仮説生成手段１１２と、
前向きＤＰ探索手段１１１で計算された最適経路スコアテーブル１１４の値を入力とし、文末から文頭へ一単語ずつ進むＡ*アルゴリズムを用いて、単語二つ組確率の積が最も大きいものから順番に一つずつ形態素解析候補を求める後向きＡ*探索手段１１３と、
後向きＡ*探索手段１１３により求められた一つの文に対する複数の形態素解析候補とその確率から単語の頻度の期待値を求める単語頻度推定手段２１０と、
日本語テキストにおける単語の頻度の期待値が大きい順番に任意の個数の単語仮説を辞書未登録語として提示する出力手段と、を有する。
【００１９】
本発明にかかる日本語形態素解析装置は、単語二つ組確率から構成される単語分割モデル、単語長確率と単語内文字二つ組確率から構成される単語モデル、確率が高い順番に任意の個数の形態素解析候補を求める形態素解析手段、１つの文に対する複数の形態素解析候補とその確率から単語の頻度の期待値を求める単語頻度推定手段を用いて、入力文が辞書に登録されていない単語を含む場合でも、確率が高い順番に形態素解析候補を提示することが可能となる。
【００２０】
さらに、提示された形態素解析候補を用いて、かつ、処理対象となる日本語テキストにおける辞書未登録語を頻度の期待値が大きい順に提示可能な辞書未登録語収集装置が提供可能となる。
従って、このような構成により、（１）辞書に登録されていない入力文中の単語を正しく同定し、（２）同定された単語を最も尤もらしい順に提示する、日本語形態素解析装置および辞書未登録語収集装置が実現できる。
【００２１】
【発明の実施の形態】
図３は、本発明のシステム構成図である。同図に示す日本語形態素解析装置１００と当該日本語形態素解析装置１００（以下、形態素解析装置と記す）を含む辞書未登録語収集装置２００から構成される。
【００２２】
形態素解析装置１００は、形態素解析部１１０、単語二つ組確率テーブルを有する単語分割モデル１３０、単語長確率テーブル１４１と単語内文字二つ組確率テーブル１４２を有する単語モデル１４０、形態素解析部１１０の解析結果を格納する形態素解析候補テーブル１５０及び単語テーブル１６０より構成される。また、辞書未登録語収集装置２００は、上記の形態素解析装置１００に、単語頻度推定部２１０を加えた構成である。
【００２３】
上記の構成の形態素装置の詳細を図４に示す。図４は、この発明の一実施例の概略ブロック図である。
本発明の日本語形態素解析装置は、前向きＤＰ探索部１１１、最適経路スコアテーブル１１４、後向きＡ* 探索部１１３、形態素解析候補テーブル１１５、単語仮説生成部１１２、単語長確率テーブル１４１、単語内文字二つ組確率テーブル１４２、単語二つ組確率テーブル１３０、単語テーブル１６０より構成される。
【００２４】
前向きＤＰ探索部１１１は、入力文の文頭から文末へ一文字ずつ進む動的計画法（Dynamic Programming)を用いて、単語列の同時確率、すなわち、単語二つ組確率の積を最大化するような、入力文の単語分割を求める。
単語二つ組確率テーブル１３０は、単語二つ組確率を格納し、単語テーブル１６０は単語辞書を格納する。
【００２５】
前向きＤＰ探索部１１１は、入力文のある文字位置から始まる全ての部分文字列を、単語テーブル１６０の単語表記と照合し、単語候補として提案する。そして、文頭からある単語に至るまでの単語列の同時確率を最大化する最適部分経路（単語列）の確率を、最後の単語が異なる場合毎に計算し、最適経路スコアテーブル１１４に記録する。
【００２６】
単語仮説生成部１１２は、前向きＤＰ探索部１１１において、入力文のある文字位置から始まる部分文字列が単語テーブル１６０と照合しなかった場合、その部分文字列が単語を構成すると仮定した場合の単語出現確率を求める。単語出現確率は、単語長確率テーブル７、単語内文字二つ組確率テーブル１４２の値を用いて計算される。単語仮説生成部１１２が生成した単語の表記と出現確率の組を単語仮説と呼ぶ。
【００２７】
後向きＡ*探索部１１３は、前向きＤＰ探索部１１１で計算された最適経路スコアテーブル１１４を入力とし、文末から文頭へ一旦後ずつ進むＡ*アルゴリズムを用いて、単語二つ組確率の積の最も大きいものから順番に一つずつ形態素解析候補を求める。
【００２８】
辞書未登録語収集装置２００の単語頻度推定部２１０は、後向きＡ* 探索部１１３が形態素解析候補テーブル１１５に格納した上位Ｎ個（Ｎは任意の整数）の形態素解析候補を入力とし、単語仮説の頻度の期待値とする。そして、頻度の期待値が大きい順番に任意の個数の単語仮説を、辞書未登録語として出力する。
【００２９】
以下では、単語分解モデル１４０、単語モデル１３、前向きＤＰ探索部１１１による前向きＤＰ探索、後向きＡ* 探索部１１３による後向きＡ* 探索、辞書未登録語収集装置２００の単語頻度推定部２１０による単語頻度推定の順に説明する。
【００３０】
（１）  単語分割モデル
文字列Ｃ＝ｃ1 ｃ2 ・・・ｃm から構成される入力文が、単語列Ｗ＝1 ｗ2 ・・・ｗn に分割されるとする。形態素解析は、文字列が与えられた時の単語列の同時確率Ｐ（Ｗ｜Ｃ）を最大化する単語列Ｗ’を求める問題である。文字列Ｃはすべての形態素解析候補に共通なので、実際にはＰ（Ｗ）を最大化するものを求めればよい。
【００３１】
【数１】
0003777456.tif 000002
【００３２】
本発明では同時確率Ｐ（Ｗ）をマルコフモデルで近似する。すなわち、単語二つ組確率Ｐ（ｗi ｜ｗi-1 ）を用いて次式で表す。
【００３３】
【数２】
0003777456.tif 000003
【００３４】
図５に、単語二つ組頻度の例として、「言語」という単語とこれに後続する単語の二つの組の出現頻度を示す。単語二つ組確率Ｐ（ｗi ｜ｗi-1 ）は、単語二つ組頻度を先行する単語の出現頻度で割ることにより得られる。例えば、訓練テキスト集合における「言語」の出現頻度が５６１で、「言語」および「が」の二つ組の出現頻度が２２ならば、Ｐ（が｜言語）＝２２／５６１＝０．０３９である。
【００３５】
（２）  単語モデル
単語モデルは、辞書未登録語を構成する文字列の同時確率分布として定義される。未知語（辞書未登録語）を〈ＵＮＫ〉で表すことにすると、単語モデルは、一般性を失うことなく、以下のような単語長確率Ｐ（ｋ）と単語表記確率Ｐ（ｃ1 ・・・ｃk ｜ｋ）の積に分解できる。
【００３６】
Ｐ（ｗi ｜〈ＵＮＫ〉）
＝Ｐ（ｃ1 ・・・ｃk ｜〈ＵＮＫ〉）
＝Ｐ（ｋ）Ｐ（ｃ1 ・・・ｃk ｜ｋ）            （３）
ここでｃ1 ・・・ｃk は、単語を構成する長さｋの文字列である。
【００３７】
本発明では、未知語の単語長の分布Ｐ（ｋ）が訓練集合中の単語の平均文字長λをパラメータとするポワソン分布に従うと仮定する。
【００３８】
【数３】
0003777456.tif 000004
【００３９】
上式は、隠れた（長さゼロ）の単語境界標識の間の距離を単語の長さと考え、この単語境界標識が平均的には平均単語長と等しい間隔で無作為に文中に置かれるものとみなしている。
次に、単語長が与えられた時の未知語の表記の確率Ｐ（ｃ1 ・・・ｃk ｜ｋ，Ｔ）は、以下のように、訓練集合中の単語内文字二つ組確率の積で近似する。
【００４０】
【数４】
0003777456.tif 000005
【００４１】
ここで“＃”は、単語の先頭および末尾を表す特別な記号である。
図６に、単語内文字二つ組頻度の例として、「永」という文字とこれに後続する文字の二つ組の頻度を示す。単語内文字二つ組確率Ｐ（ｃi ｜ｃi-2 ）は、単語内文字二つ組頻度を先行する文字の出現頻度で割ることにより得られる。例えば、訓練テキスト集合において、「永」という文字の出現頻度が３３４で、「永」および「ら」の単語内文字二つ組の出現頻度が８ならば、Ｐ（ら／永）＝８／３３４＝０．０２４である。
【００４２】
入力文が未知語を含む場合でも、式（３）の単語モデルを用いることにより、式（２）の単語分割モデルのパラメータは次式のようにして求めることができる。
【００４３】
【数５】
0003777456.tif 000006
【００４４】
ここでＣ（・）は、対応する事象の訓練集合における頻度を表す。ｗi が未知語である場合の単語二つ組頻度Ｃ（ｗi-1 ，ｗi ）は、訓練集合においてｗi-1 の後に未知語が現れる頻度Ｃ（ｗi-1 ，〈ＵＮＫ〉）と表記がｗi であるような未知語の出現確率Ｐ（ｗi ｜〈ＵＮＫ〉）の積で近似する。なお、未知語を含む単語二つ組頻度Ｃ（ｗi-1 ，〈ＵＮＫ〉）は、訓練集合の中で一回しか現れなかった単語を未知語とみなすことにより求める。
【００４５】
（３）  前向きＤＰ探索
前向きＤＰ探索部１１１が、最適経路スコアテーブルを計算する手順を示す。入力文を長さｎの文字列Ｃ＝ｃ1 ｃ2 ・・・ｃn とし、部分文字列ｃp+1 ・・・ｃq をｃp q で表す。まず、任意の部分文字列ｃp q を単語候補の集合｛ｗi ｝に写像する関数Ｄを考える。関数Ｄは辞書を一般化したものである。関数Ｄは、もしｃp q と照合する表記をもつ単語が辞書中にあればそれを返す。もし照合しなければ、単語モデルを用いてｃp q を表記とする単語仮説を作成する。
【００４６】
次に、部分文字列ｃp q が最後の単語ｗi であるような、部分文字列ｃ0 q の最尤な単語分割の確率（最適経路確率）φp q （ｗi ）を考える。最適経路確率φp q （ｗi ）は、次式を用いて文頭から順番に計算することができる。
【００４７】
【数６】
0003777456.tif 000007
【００４８】
前向きＤＰ探索部１１１における式（７）の計算は、図７のようなフローチャートで表せる。以下では、この図７に従って、前向きＤＰ探索部１１１の動作を説明する。
前向きＤＰ探索は、入力文の先頭から始まり、文末方向へ一文字ずつ進む。
【００４９】
ステップ１０１）  探索の開始位置を入力文の先頭に設定する。
ステップ１０２）  探索が文末に達したかを判断する。もし、文末に達していれば、前向き探索を終了する。そうでなければ、以下の処理を各文字位置で行なう。
【００５０】
ステップ１０３）  現在の文字位置に到達する全ての部分解析を最適経路スコアテーブル１１４から検索し、その中の一つを現在の部分解析として選ぶ。
ステップ１０４）  全ての部分解析を調べたかを判定する。もしそうならば、ステップ１２２において探索を次の文字位置へ進める。そうでなければ、以下の処理を各部分解析について行なう。
【００５１】
ステップ１０５）  現在の文字位置から始まる最左部分文字列と照合する全ての単語候補を単語テーブル１６０から検索する。また、照合しない時は、単語モデル１４０を用いて単語仮説を作成する。そして、その中の一つを現在の単語として選ぶ。
【００５２】
ステップ１０６）  全ての単語を調べたかを判定する。もしそうならば、ステップ１１１に移行し、次の部分解析を選ぶ。そうでなければ、以下の処理を各単語について行なう。
ステップ１０７）  現在の単語とその直前の単語から構成される単語二つ組確率を単語二つ組テーブル１３０から検索する
ステップ１０８）  単語二つ組確率がゼロかどうかを判定する。もし単語二つ組確率が０ならば、ステップ１１０において次の単語を選ぶ。もしそうでなければ、以下の処理を行なう。
【００５３】
ステップ１０９）  まず、現在の部分解析の末尾に現在の単語を付け加えた新しい部分解析を作成する。新しい部分解析の（文頭から現在の単語の末尾までの）最適経路スコアは、現在の部分解析の最適経路スコアと単語二つ組確率の積である。次に、最適経路スコアテーブル１１４から、この新しい部分解析の最後の単語と同じ単語を最後に持つ部分解析を検索する。もしこのような部分解析が存在しないか、あるいは、既に存在する部分解析よりも新しい部分解析のスコアが良ければ、新しい部分解析を最適経路スコアテーブル１１４に登録する。
【００５４】
ステップ１１０）  次の単語を選び、ステップ１０６へ戻る。
ステップ１１１）  次の部分解析を選び、ステップ１０４へ戻る。
ステップ１１２）  探索を次の文字位置へ進め、ステップ１０２へ戻る。
（４）  後向きＡ* 探索
後向きＡ* 探索部１１３が、確率が高い順番に一つずつ形態素解析候補を求める手順を示す。本発明の後向きＡ* 探索では、前向きＤＰ探索により求めた、文頭からある単語までの部分解析を、Ａ* アルゴリズムにおけるグラフのノードと考える。そして、コストとしては、確率の対数の絶対値を用いる。これにより、確率最大の解はコスト最小の解に対応し、確率の積はコストの和に対応する。
【００５５】
一般に、Ａ* 探索では、ヒューリスティック関数ｆ（ｎ）を考える。ヒューリスティック関数ｆ（ｎ）は、現在のノードｎを生成した経路に沿って、初期状態から最終状態へ至るまでのコストの推定値を与える。初期状態から現在のノードへ至るまでのコストを与える関数をｇ（ｎ）、現在のノードから最終状態へ至るまでのコストの推定値を与える関数をｈ（ｎ）とすると、ヒューリスティック関数ｆ（ｎ）は次式により与えられる。
【００５６】
ｆ（ｎ）＝ｇ（ｎ）＋ｈ（ｎ）              （８）
本発明の後向き探索では、関数ｇとして、文末から現在の単語に至るまでの単語二つ組確率の積の対数の絶対値を用いる。また、関数ｈとしては、前向き探索で求めた、文頭から現在の単語に至るまでの単語二つ組確率の積の最大値の対数の絶対値を用いる。
【００５７】
Ａ* 探索では、ｏｐｅｎとｃｌｏｓｅという二つのリストを用いる。リストｏｐｅｎは、既に生成され、ヒューリスティック関数が適用されているが、まだ展開されて（調べられて）いないノードの集合である。このリストは、ヒューリスティック関数の値に基づく優先度付きキューになっている。リストｃｌｏｓｅは、既に展開された（調べられた）ノードの集合である。
【００５８】
Ａ* 探索では、目標状態に対応するノードを生成するまで、各ステップで一つのノードを展開する。各ステップでは、既に生成されているが、まだ展開されていない、最も有望なノードを展開する。すなわち、選ばれたノードの後続のノードを生成し、ヒューリスティック関数を適用し、既に生成されていないかを検査した後にリストｏｐｅｎに加える。この検査によって、各ノードはグラフの中に一回だけ現れることが保証される。また、二つ以上の経路が同じノードを生成する時は、スコアの良い方だけを記録する。
【００５９】
本発明の後向き探索では、あるノードから後続するノードへの遷移のコストとして、単語二つ組確率の対数の絶対値を用いる。
図８、図９は、本発明の後向きＡ* 探索部の動作を説明するためのフローチャートである。
【００６０】
以下では、この図８、図９に従って、後ろ向きＡ＊探索部１１３の動作を説明する。
ステップ２０１）  文末に到達した部分解析に対応するノードのリストをｏｐｅｎに代入する。また、ｃｌｏｓｅｄには空リストを代入する。
【００６１】
ステップ２０２）  ｏｐｅｎが空リストかどうかを調べる。もしそうならば、解が見つからなかったので探索が失敗したことを通知して探索を終了する。そうでなければ、以下の処理を行なう。
ステップ２０３）  ｏｐｅｎの先頭要素を取り出して変数ｂｅｓｔｐａｔｈに代入する。
【００６２】
ステップ２０４）  そして、探索が文頭に達したかを調べる。もし、探索が文頭に達していれば、ｂｅｓｔｐａｔｈが最適解であり、探索が成功したことを通知して探索を終了する。そうでなければ、以下の処理を行なう。また、探索は成功したが、さらにその次に確率が高い解を求めたい場合には、以下の処理を行なう。
【００６３】
ステップ２０５）  ｂｅｓｔｐａｔｈをリストｃｌｏｓｅｄへ挿入し、ｃｌｏｓｅｄの要素を初期状態から最終状態までのコストの推定値ｆ（ｎ）の順にソートする。
ステップ２０６）  ｂｅｓｔｐａｔｈが表す部分解析の左側に連接する全ての部分解析を最適部分経路スコアテーブルから検索し、その中の一つを現在の部分解析とする。
【００６４】
ステップ２０７）  全ての部分解析を調べたかどうかを判定する。もしそうであれば、ステップ２０２へ進む。そうでなければ以下の処理を行なう。
ステップ２０８）  ｂｅｓｔｐａｔｈから現在の部分解析へ遷移する経路を表す新しいノードを作成し、これを変数ｎｅｗｐａｔｈに代入する。文末からこのノードまでのコストｇ（ｎｅｗｐａｔｈ）は、文末からｂｅｓｔｐａｔｈへ至るまでのコストｇ（ｂｅｓｔｐａｔｈ）と、ｂｅｓｔｐａｔｈからｎｅｗｐａｔｈへの遷移のコストの和となる。また、このノードのヒューリスティック関数ｆ（ｎｅｗｐａｔｈ）は、文末からこのノードまでのコストｇ（ｎｅｗｐａｔｈ）と、前向き探索で求めた文頭からこのノードまでの最適コストｈ（ｎｅｗｐａｔｈ）の和となる。
【００６５】
ステップ２０９）  現在の部分解析への遷移を表すノードがｏｐｅｎに含まれているかどうかを検査する。もし含まれていなければ、ステップ２１３へ進む。含まれていれば、以下の処理を行なう。
ステップ２１０）  現在の部分解析への遷移を表すｏｐｅｎの中のノードを変数ｏｌｄｐａｔｈに代入する。
【００６６】
ステップ２１１）  ｎｅｗｐａｔｈのコストｆ（ｎｅｗｐａｔｈ）とｏｌｄｐａｔｈのコストｆ（ｏｌｄｐａｔｈ）を比較する。もし、ｎｅｗｐａｔｈのコストの方が大きければ、何もせずにステップ２１８へ進む。
ステップ２１２）  もし、ｎｅｗｐａｔｈのコストの方が小さければ、ｏｐｅｎからｏｌｄｐａｔｈを削除し、ｎｅｗｐａｔｈをｏｐｅｎへ挿入した後にコストの順にソートする。そしてステップ２１８へ進む。
【００６７】
ステップ２１３）  現在の部分解析への遷移を表すノードがｃｌｏｓｅｄに含まれているかどうかを検査する。もし含まれていなければ、ステップ２１７へ進む。含まれていれば、以下の処理を行なう。
ステップ２１４）  現在の部分解析への遷移を表すｃｌｏｓｅｄの中のｐａｔｈ構造を変数ｏｌｄｐａｔｈに代入する。
【００６８】
ステップ２１５）  ｎｅｗｐａｔｈのコストｆ（ｎｅｗｐａｔｈ）とｏｌｄｐａｔｈのコストｆ（ｏｌｄｐａｔｈ）を比較する。もし、ｎｅｗｐａｔｈのコストの方が大きければ、何もせずにステップ２１８へ進む。
ステップ２１６）  もし、ｎｅｗｐａｔｈのコストの方が小さければ、ｃｌｏｓｅｄからｏｌｄｐａｔｈを削除し、ｎｅａｐａｔｈをｃｌｏｓｅｄへ挿入した後にコストの順にソートする。そしてステップ２１８へ進む。
【００６９】
ステップ２１７）  ｎｅｗｐａｔｈをｏｐｅｎへ挿入した後にコストの順にソートする。そしてステップ２１８へ進む。
ステップ２１８）  次の部分解析を選ぶ。
（５）  単語頻度推定
辞書未登録語収集装置２００の単語頻度推定部２１０が入力文に含まれる単語の頻度の期待値を求め、頻度の期待値が大きい順番に辞書未登録語を出力する手順を示す。
【００７０】
前向きＤＰ探索に続いて後向きＡ* 探索を行なえば、入力文に対する形態素解析候補を確率が高い順番に任意の個数だけ得ることができる。ここで、訓練テキストの集合の第ｉ番目の文の第ｊ番目の形態素解析候補をＯj i とする。形態素解析候補の確率Ｐ（Ｏj i ）は単語分割モデルと単語モデルから求められる。本発明では、第ｉ番目の文における単語ｗαの頻度の期待値Ｃi （ｗα）は次式により計算する。
【００７１】
【数７】
0003777456.tif 000008
【００７２】
ここでｎj i （ｗα）は、第ｉ番目の文の第ｊ番目の形態素解析候補に単語ｗαが出現した回数を表す。
【００７３】
【数８】
0003777456.tif 000009
【００７４】
【実施例】
以下に本発明の実施例を図面と共に説明する。以下の実施例では、第１の実施例として、日本語形態素解析装置を説明し、第２の実施例として辞書未登録語収集装置を説明する。
【００７５】
［第１の実施例］
図１０は、本発明の第１の実施例の形態素解析候補の例を示す。この例では、入力文
「キャノンゼロワンショップ横須賀からパワーマックを買う。」
に対する上位３個の形態素解析候補が示されている。各形態素解析候補には、その対数確率が示されており、この値が大きいほど尤もらしい。
【００７６】
この例では「キヤノンゼロワンショップ横須賀」という文字列の単語分割に際して、本発明の日本語形態素解析装置は、第１候補では、
「キヤノン」「ゼロワンショップ」「横須賀」
第２候補では、
「キヤノン」「ゼロワン」「ショップ」「横須賀」
第３候補では、
「キヤノン」「ゼロ」「ワン」「ショップ」「横須賀」
という単語分割を提示している。この中で「ゼロワンショップ」と「ゼロワン」は辞書には登録されておらず、未知語として提示されている。また、「パワーマック」という文字列も辞書には登録されていないので、未知語として提示されている。
【００７７】
このように本実施例によれば、入力文が辞書に登録されていない単語を含む場合でも、確率が高い順番に任意の個数の形態素解析候補を提示できる。
［第２の実施例］
本発明の辞書未登録語収集装置２００では、訓練テキスト集合における単語の頻度の期待値を、入力文中の任意の部分文字列が単語を構成しているかどうかに関する確からしさの尺度として用いる。ここで、単語仮説を単語とみなすかどうかの閾値をθとする。本発明では、単語仮説の中で、その頻度の期待値が閾値θよりも大きいものを辞書未登録語として収集する。
【００７８】
【数９】
0003777456.tif 000010
【００７９】
最後に、本発明における単語頻度推定部２１０の単語の頻度の期待値の計算手段を簡単な例を用いて示す。入力テキストが５つの文字から構成される文字列「言語学入門」であり、その上位３個の形態素解析候補が図９に示すように「言語学／入門」「言／語学／入門」「言語／学／入門」であるとする。図１１の左端の数字は形態素解析候補の相対確率であり、式（９）の
【００８０】
【数１０】
0003777456.tif 000011
【００８１】
に相当する。
式（９）に従って、第ｊ番目の形態素解析候補における単語ｗαの出現回数ｎj i （ｗα）に、第ｊ番目の形態素解析候補の相対確率
【００８２】
【数１１】
0003777456.tif 000012
【００８３】
を掛けた値を全ての形態素解析候補に関して加えると、各単語候補の頻度の期待値は以下のようになる。
Ｃ（入門）＝０．７＋０．２＋０．１＝１．０
Ｃ（言語学）＝０．７
Ｃ（言語）＝Ｃ（学）＝０．２
Ｃ（言）＝Ｃ（語学）＝０．１
仮に、単語と同定するための頻度の期待値の閾値θを０．１５に設定したとする。もし仮に、「入門」「言語学」「言語」「学」「言」「語学」の全ての文字列が辞書に登録されていないのであれば、本発明の方法では、「入門」「言語学」「言語」「学」の４つを辞書未登録語として提示する。
【００８４】
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内で種々変更・応用が可能である。
【００８５】
【発明の効果】
上述のように、本発明の日本語形態素解析装置によれば、単語二つ組から構成される単語分割モデル、単語長確率と単語内文字二つ組確率から構成される単語モデル、動的計画法を用いた前向き探索とＡ* アルゴリズムを用いた後ろ向き探索により、単語列の同時確率が高い順番に任意の個数の形態素解析候補を提示する形態素解析処理により、辞書に登録されていない単語が入力文に含まれている場合でも確率が高い順番に入力文を構成する単語列を提示することが可能となる。
【００８６】
また、本発明の辞書未登録語収集装置によれば、複数の形態素解析候補とその確率から単語の頻度で期待値を求める単語頻度推定処理により、訓練テキスト集合における単語仮説の頻度の期待が大きい順番に任意の個数の単語仮説を辞書未登録語として提示することが可能となる。
【図面の簡単な説明】
【図１】本発明の原理を説明するためのフローチャートである。
【図２】本発明の原理構成図である。
【図３】本発明のシステム構成図である。
【図４】本発明の日本語形態素解析装置及び辞書未登録語収集装置の構成図である。
【図５】本発明の単語二つ組頻度の例である。
【図６】本発明の単語内文字二つ組頻度の例である。
【図７】本発明の前向きＤＰ探索を示すフローチャートである。
【図８】本発明の後ろ向きＡ* 探索を示すフローチャート（その１）である。
【図９】本発明の後ろ向きＡ* 探索を示すフローチャート（その２）である。
【図１０】本発明の第１の実施例の形態素解析候補の例である。
【図１１】本発明の第２の実施例の単語頻度期待値計算の例である。
【符号の説明】
１００  日本語形態素解析装置
１１０  形態素解析手段
１１１  前向きＤＰ探索手段、前向きＤＰ探索部
１１２  単語仮説生成手段、単語仮説生成部
１１３  後向きＡ*探索手段、後向きＡ*探索部
１１４  最適経路スコアテーブル
１１４  形態素解析候補テーブル
１４１  単語長確率テーブル
１４２  単語内文字二つ組確率テーブル
１５０  形態素解析候補テーブル
１６０  単語テーブル(単語辞書)
２００  辞書未登録語収集装置
２１０  単語頻度推定手段
【図１】
0003777456.tif 000013
【図２】
0003777456.tif 000014
【図３】
0003777456.tif 000015
【図４】
0003777456.tif 000016
【図５】
0003777456.tif 000017
【図６】
0003777456.tif 000018
【図７】
0003777456.tif 000019
【図８】
0003777456.tif 000020
【図９】
0003777456.tif 000021
【図１０】
0003777456.tif 000022
【図１１】
0003777456.tif 000023