(57)【要約】【課題】辞書のデータサイズを小さくでき、かつ形態素解析時の処理を効率化できる辞書装置、形態素解析装置、データ構造ならびに形態素解析の方法およびプログラムを提供する。【解決手段】トライに基づく構造で文字列のデータを格納する形態素解析用の辞書装置１２０であって、文字列のデータを区分した部分文字列および部分文字列に関する情報を、文字列に沿って交互に並べて格納する。これにより、部分文字列に関する情報を用い効率的なデータ表現が可能となり、形態素解析のために記憶する文字列に関するデータ量を小さくできる。また、採用されない部分文字列に関する情報を早い段階で判別できるため、効率よく形態素解析の処理ができる。また、部分文字列に関する情報を容易に参照できるため、部分文字列に関する情報の制約を考慮した形態素解析処理を実現できる。【選択図】図１
2015194801.tif 000002
【特許請求の範囲】
【請求項１】
トライに基づく構造で文字列のデータを格納する形態素解析用の辞書装置であって、
文字列のデータを区分した部分文字列および前記部分文字列に関する情報を、文字列に沿って交互に並べて格納することを特徴とする辞書装置。
【請求項２】
前記部分文字列に関する情報は、部分文字列の読みに関する情報を含むことを特徴とする請求項１記載の辞書装置。
【請求項３】
文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析装置であって、
請求項１または請求項２記載の辞書装置と、
入力された文字列から部分文字列を切り出し、文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を前記辞書装置に照合し、前記切り出された部分文字列の先頭の部分文字列に一致する形態素に関する情報の候補を出力する照合部と、を備えることを特徴とする形態素解析装置。
【請求項４】
文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析装置であって、
請求項２記載の辞書装置と、
入力された文字列から部分文字列を切り出し、文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を前記辞書装置に照合し、前記切り出された部分文字列の先頭の部分文字列に一致する形態素に関する情報の候補を出力する照合部と、
前記入力された文字列を構成する一部の文字に対する読みに関する情報を制約として参照し、前記照合の結果として出力された候補のうち前記制約を満たす候補を出力する制約参照部と、を備えることを特徴とする形態素解析装置。
【請求項５】
コンピュータ内の記憶部にトライに基づいて構成される形態素解析用の辞書のデータ構造であって、
文字列のデータを区分した部分文字列および前記部分文字列に関する情報が、文字列に沿って交互に並べて格納されることを特徴とするデータ構造。
【請求項６】
文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析の方法であって、
入力された文字列から部分文字列を切り出すステップと、
文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を請求項５記載のデータ構造を有する文字列のデータと照合するステップと、をコンピュータを用いて実行することを特徴とする方法。
【請求項７】
文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析の方法であって、
入力された文字列から部分文字列を切り出すステップと、
文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を、請求項５記載のデータ構造を有し、前記部分文字列に関する情報は部分文字列の読みに関する情報を含む、文字列のデータと照合するステップと、
前記入力された文字列を構成する一部の文字に対する読みの情報を制約として参照し、前記照合の結果として出力された候補のうち前記制約を満たす候補を出力するステップと、をコンピュータを用いて実行することを特徴とする方法。
【請求項８】
文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析のプログラムであって、
入力された文字列から部分文字列を切り出す処理と、
文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を請求項５記載のデータ構造を有する文字列のデータと照合する処理と、を含む一連の処理をコンピュータに実行させることを特徴とするプログラム。
【請求項９】
文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析のプログラムであって、
入力された文字列から部分文字列を切り出す処理と、
文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を、請求項５記載のデータ構造を有し、前記部分文字列に関する情報は部分文字列の読みに関する情報を含む、文字列のデータと照合する処理と、
前記入力された文字列を構成する一部の文字に対する読みの情報を制約として参照し、前記照合の結果として出力された候補のうち前記制約を満たす候補を出力する処理と、を含む一連の処理をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トライに基づく構造で文字列のデータを格納する形態素解析用の辞書装置、形態素解析装置、データ構造ならびに形態素解析の方法およびプログラムに関する。
【背景技術】
【０００２】
音声合成技術の代表的な利用形態にテキスト音声変換（Ｔｅｘｔ−Ｔｏ−Ｓｐｅｅｃｈ、ＴＴＳ）がある。テキスト音声変換は、入力されたテキストに対応する音声波形を合成する処理である。以下では、この一連の処理は、入力されたテキストを解析してテキストの読み方に関する情報を生成する処理と、読み方に関する情報から音声波形を合成する処理の、大きく２つに分ける。また、入力は日本語の漢字仮名交じり文であるとする。
【０００３】
以下では、読み方に関する情報を表現するために用いる記号を、音声合成用記号と呼ぶ。音声合成用記号には様々な形式があり得るが、ここでは、一連の音声を構成する音韻的情報と、主としてポーズや声の高さとして表現される韻律的情報を同時に表記したものを想定する。そのような音声合成用記号の例として、ＪＥＩＴＡ（電子情報技術産業協会）規格ＩＴ−４００６「日本語テキスト音声合成用記号」がある（非特許文献１参照）。この記号だけで音声の感情表現等まで表現することは困難だが、少なくとも通常の読み上げ音声の言語的特徴を記述するために必要な情報は含まれている。
【０００４】
一方、音声波形を合成する処理は、音声合成用記号の通りの波形が合成されるように行われる。したがって、日本語テキストの正確な読み上げを実現するためには、日本語の漢字仮名交じり文に対応した、正確な音声合成用記号を作成すればよい。
【０００５】
任意の日本語テキストから音声合成用記号を生成する処理は、日本語漢字仮名交じり文を形態素と呼ばれる言語表現上意味を持つ最小の単位に区切り、形態素ごとの読みを付与し、形態素列等を参照し形態素の情報を適切に変形し、必要に応じ、ポーズ等の韻律的境界を挿入し、それらを接続することで実現できる。この際、各形態素の読みは、形態素辞書情報として予め作成し格納しておく。
【０００６】
ただし、形態素は、言語学的な定義の通りである必要はなく、一連の処理を行なう上で適当に区切られた単位でもよい。例えば、形態素の並びをより適切に処理するために、複数の形態素で構成される句（複合名詞句等）を便宜的に１つの形態素と見なして処理することがある。よって以下においては、形態素とは、その用途の観点から処理上の最小単位となるべく適当に設定された文字の並び（文字列）をいい、また、全ての文は、この文字列を連結することで構成できるものとする。また、ある文に対して、それを形態素に分割する処理は、一般に形態素解析処理と呼ばれ、音声合成処理に限らず、文の構成要素の抽出等で用いられている。
【０００７】
形態素解析の方法として、以下では、最小コスト法に基づく方法を説明する。最小コスト法による形態素解析では、まず、各形態素の出現頻度を反映させた生起コスト関数と、連続する形態素の繋がりやすさを表す連接コスト関数を予め定義しておく。そして、形態素辞書に登録された形態素から、入力テキストに一致し、かつ文全体のコストが最小となるような形態素列を探すことで、適切な形態素列を得る。通常、生起コスト関数は出現頻度が高い形態素ほど、連接コスト関数は繋がりやすい形態素列ほど、その値が小さくなるよう定義される。
【０００８】
すなわち形態素列をＭ＝（ｍ１，…，ｍｎ）、生成コスト関数をＣｔ（ｍ）、連接コスト関数をＣｃ（ｍ（ｉ−ｋ＋１），…，ｍｉ）とするとき、コストの総和Σ Ｃｔ ＋Σ Ｃｃが最小となる形態素列Ｍ、すなわちａｒｇｍｉｎ （Σ Ｃｔ ＋Σ Ｃｃ）を求めることで形態素解析処理が行われる。ただし、ここで連接コスト関数はｋ個の形態素の並びで決定されるものとする。
【０００９】
このようにコスト関数を定義すると、コスト的な最適な全体系列を構成する部分系列は、その部分系列だけを見てもコスト的には最適となる。したがって、コスト的に最適でない部分系列は、最適な全体系列の構成要素にはならないので、探索において考慮する必要がなくなる。このように、最適系列を構成する可能性がない部分系列を考慮しないように進めて行く最適系列の探索法は一般に動的計画法と呼ばれ、効率よく最適系列の探索を行なうことができる。
【００１０】
コスト関数の構成要素のうち、生起コストに関する情報は形態素辞書の内容として保持することができる。一方、連接コストについては連接表と呼ばれるテーブルを予め作成しておき、その表の値を使うことで求めることができる。ただし、全ての形態素列の組み合わせの表を作ることは難しいので、例えば形態素の品詞型だけに注目した表を用いることも行われる。なお、これらの関数は値が大きいほど好ましいものとして定義される場合もある。その場合は、文全体の値が最も大きくなる形態素系列を探すことになる。
【００１１】
形態素解析における形態素列の探索処理では可能な形態素の並び全てを調べることが好ましい。そのため、通常の形態素解析では、形態素の候補を得るために、文中の任意の位置から始まる部分文字列を検索のキーとして、形態素辞書に登録された形態素のうち、キーの先頭部分文字列に等しい形態素全てを取り出す、という処理が繰り返し行われる。このような探索は、一般にＣｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈ（共通接頭辞探索）と呼ばれる。これを比較的効率よく表現するデータ構造として、ｔｒｉｅ（トライ）やＰａｔｒｉｃｉａ  ｔｒｅｅ（パトリシア木）が知られている。
【００１２】
ここで、トライは複数の文字列を格納するための多分木構造で、ここでは、各文字列の先頭文字から順に各文字を木の枝として格納していくことで構築されものとする。トライでは、文字列間の共通な接頭辞が木構造上で共有されるので、検索対処の文字列の接頭辞となる全ての登録語は、木構造の１つのパス上に配置される。つまり、トライのルート（根）から検索キーに沿って木をリーフ（葉）方向にたどって行くことで、ｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈを実現できる。
【００１３】
またパトリシア木とは、先述のトライにおいて、子が１つしかないノードを、さらにその子ノードと結合させたものをいう。この結合によって、１つの枝には１文字だけでなく、連続する複数の文字が格納されることもある。
【００１４】
トライの実現については、簡潔データ構造（succinct data structure）の１つとして挙げられるＬＯＵＤＳ（Level-Order Unary Degree Sequence）により省メモリで実現できることが知られている。（非特許文献２参照）
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】「日本語テキスト音声合成用記号」ＪＥＩＴＡ規格 ＩＴ−４００６、２０１０年３月
【非特許文献２】「Space-efficient static trees and graphs」Jacobson, G、Foundations of Computer Science, 1989., 30th Annual Symposium、pp. 549-554、１９８９年１０月
【発明の概要】
【発明が解決しようとする課題】
【００１６】
日本語やその他の多くの言語では、文字表記と読み情報の間に強い関係性がある。しかし、従来の形態素解析システムは読み情報を各形態素の付加的な情報として扱っており、文字表記と、読み情報の間の関係性をデータ表現上は利用していない。この結果、例えば、読み情報は各形態素で全く独立に符号化されており、形態素辞書のサイズが大きくなる、という問題がある。ハフマン符号化のように、読み情報を記述する記号の出現頻度を考慮する等の方法により、読み情報のサイズを圧縮することも可能であるものの、この場合、圧縮された読み情報を復号する処理が必要となり、必要な処理量が増えることになる。
【００１７】
また、木構造に基づく形態素辞書を用いた場合、読み情報は木のリーフにのみ結び付けられているため、木をルートから辿って行きリーフノードに達するまで、辿った部分までの部分的な読み情報も得ることができず、木構造辞書のアクセスの途中で処理を打ち切るといったアルゴリズムを用いる際に、読み情報を打ち切りの判断基準として考慮することができていない。
【００１８】
本発明は、このような事情に鑑みてなされたものであり、辞書のデータサイズを小さくでき、かつ形態素解析時の処理を効率化できる辞書装置、形態素解析装置、データ構造ならびに形態素解析の方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
（１）上記の目的を達成するため、本発明の辞書装置は、トライに基づく構造で文字列のデータを格納する形態素解析用の辞書装置であって、文字列のデータを区分した部分文字列および前記部分文字列に関する情報を、文字列に沿って交互に並べて格納することを特徴としている。
【００２０】
これにより、部分文字列に関する情報についても、部分文字列と同様にその先頭の共通部分が木構造上で共有されるので、形態素解析のために記憶する文字列に関するデータサイズを小さくできる。また、採用されない部分文字列に関する情報を共通接頭辞探索の早い段階で判別できるため、効率よく形態素解析の処理ができる。また、部分文字列に関する情報を容易に参照できるため、部分文字列に関する情報の制約を考慮した形態素解析処理を実現できる。
【００２１】
（２）また、本発明の辞書装置は、前記部分文字列に関する情報が、部分文字列の読みに関する情報を含むことを特徴としている。これにより、文字列の読みに関する情報を利用して辞書のデータサイズを小さくできる。また、読みに関する情報を利用して効率的に形態素解析の処理を行なうことができる。
【００２２】
（３）また、本発明の形態素解析装置は、文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析装置であって、上記の辞書装置と、入力された文字列から部分文字列を切り出し、文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を前記辞書装置に照合し、前記切り出された部分文字列の先頭の部分文字列と一致する形態素に関する情報の候補を出力する照合部と、を備えることを特徴としている。これにより、採用されない部分文字列に関する情報を早い段階で判定し、効率よく形態素解析の処理ができる。
【００２３】
（４）また、本発明の形態素解析装置は、文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析装置であって、上記の辞書装置と、入力された文字列から部分文字列を切り出し、文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を前記辞書装置に照合し、前記切り出された部分文字列の先頭の部分文字列と一致する形態素に関する情報の候補を出力する照合部と、前記入力された文字列を構成する一部の文字に対する読みに関する情報を制約として参照し、前記照合の結果として出力された候補のうち前記制約を満たす候補を出力する制約参照部と、を備えることを特徴としている。これにより、形態素解析の処理中に、形態素の読みに関する情報を容易に参照することができ、読みの情報の制約を考慮した形態素解析処理を実現できる。
【００２４】
（５）また、本発明のデータ構造は、コンピュータ内の記憶部にトライに基づいて構成される形態素解析用の辞書のデータ構造であって、文字列のデータを区分した部分文字列および前記部分文字列に関する情報が、文字列に沿って交互に並べて格納されることを特徴としている。これにより、効率的なデータ表現により文字列のデータを小さくすることができる。また、効率よく形態素解析の処理ができる。
【００２５】
（６）また、本発明の方法は、文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析の方法であって、入力された文字列から部分文字列を切り出すステップと、文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を上記のデータ構造を有する文字列のデータと照合するステップと、をコンピュータを用いて実行することを特徴としている。これにより、採用されない部分文字列に関する情報を早い段階で判定し、効率よく形態素解析の処理ができる。
【００２６】
（７）また、本発明の方法は、文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析の方法であって、入力された文字列から部分文字列を切り出すステップと、文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を、上記のデータ構造を有し、前記部分文字列に関する情報は部分文字列の読みに関する情報を含む、文字列のデータと照合するステップと、前記入力された文字列を構成する一部の文字に対する読みの情報を制約として参照し、前記照合の結果として出力された候補のうち前記制約を満たす候補を出力するステップと、をコンピュータを用いて実行することを特徴としている。これにより、形態素解析の処理中に、形態素の読みに関する情報を容易に参照することができ、読みの情報の制約を考慮した形態素解析処理を実現できる。
【００２７】
（８）また、本発明のプログラムは、文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析のプログラムであって、入力された文字列から部分文字列を切り出す処理と、文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を上記のデータ構造を有する文字列のデータと照合する処理と、を含む一連の処理をコンピュータに実行させることを特徴としている。これにより、採用されない部分文字列に関する情報を早い段階で判定し、効率よく形態素解析の処理ができる。
【００２８】
（９）また、本発明のプログラムは、文字列をもとに、これを構成する形態素列に関する情報を出力する形態素解析のプログラムであって、入力された文字列から部分文字列を切り出す処理と、文字列の順に沿って部分文字列ごとに前記切り出された部分文字列を、上記のデータ構造を有し、前記部分文字列に関する情報は部分文字列の読みに関する情報を含む、文字列のデータと照合する処理と、前記入力された文字列を構成する一部の文字に対する読みの情報を制約として参照し、前記照合の結果として出力された候補のうち前記制約を満たす候補を出力する処理と、を含む一連の処理をコンピュータに実行させることを特徴としている。これにより、形態素解析の処理中に、形態素の読みに関する情報を容易に参照することができ、読みの情報の制約を考慮した形態素解析処理を実現できる。
【発明の効果】
【００２９】
本発明によれば、効率的なデータ表現が可能となり、形態素解析のため記憶する文字列のデータサイズを小さくできる。また、採用されない部分文字列に関する情報を早い段階で判定できるため、効率よく形態素解析の処理ができる。また、部分文字列に関する情報を容易に参照できるため、部分文字列に関する情報の制約を考慮した形態素解析処理を実現できる。
【図面の簡単な説明】
【００３０】
【図１】本発明の形態素解析装置を示すブロック図である。
【図２】従来のデータ構造の一例を示す図である。
【図３】本発明のデータ構造の一例を示す図である。
【図４】本発明の形態素解析装置の動作を示すフローチャートである。
【図５】本発明の形態素解析装置の動作を示すフローチャートである。
【図６】本発明の形態素解析装置の動作を示すフローチャートである。
【図７】従来のデータ構造の一例を示す図である。
【図８】本発明のデータ構造の一例を示す図である。
【図９】本発明のデータ構造の一例を示す図である。
【発明を実施するための形態】
【００３１】
次に、本発明の実施の形態について、図面を参照しながら説明する。以下の説明において表記文字列が同じであっても読みが異なる形態素は、異なる形態素として扱う。
【００３２】
［第１の実施形態］
（形態素解析装置の構成）
図１は、形態素解析装置１００を示すブロック図である。図１に示すように、形態素解析装置１００は、照合部１１０、辞書装置１２０、制約参照部１３０、決定部１４０および連接表記憶部１５０を備え、入力された文字列をもとに、これに関する情報のうち適したものを決定し出力する。
【００３３】
照合部１１０は、入力された文字列（漢字仮名交じり文）から部分文字列を切り出し、文字列の順に沿って部分文字列ごとに切り出された部分文字列を辞書装置１２０に照合し、切り出された部分文字列のさらにその先頭部分の部分文字列と一致する形態素に関する情報の候補を出力する。これにより、採用されない形態素に関する情報を早い段階で判定し、効率よく形態素解析の処理ができる。なお、辞書装置１２０内のデータは格納された文字列に沿った順で照合される。
【００３４】
辞書装置１２０は、文字列のデータおよびこれに関する情報を格納する。辞書装置１２０は、文字列のデータを区分した部分文字列および部分文字列に関する情報を、文字列に沿って交互に並べて格納している。なお、通常、文字列のデータは複数の部分文字列に区分される。辞書装置１２０に格納されたデータは、トライに基づく構造を有している。すなわち、一端（先頭または末尾）から途中までのデータが共通する複数の文字列のデータに対して、共通する部分のデータを単一のデータで代表させるとともに、途中から他端までの共通しない部分文字列を複数のデータで枝分かれさせている。
【００３５】
このように文字と発音の関係性を利用することで効率的なデータ表現が可能となり、読み情報付きの形態素解析を、より小さいデータサイズで実現できる。また、採用されない部分文字列に関する情報を早い段階で判別できるため、効率よく形態素解析の処理ができる。
【００３６】
部分文字列に関する情報は、部分文字列の読みに関する情報を含むことが好ましい。これにより、文字列の読みに関する情報を利用して辞書のデータサイズを小さくできる。また、読みに関する情報を利用して効率的に形態素解析の処理を行なうことができる。
【００３７】
制約参照部１３０は、入力された文字列を構成する一部の文字に対する読みに関する情報を制約として参照し、照合の結果として出力された候補のうち制約を満たす候補を出力する。辞書装置１２０のデータ構造を利用することで、形態素解析の処理中に、形態素の読みに関する情報を容易に参照することができるため、読みの情報の制約を考慮した形態素解析処理を実現できる。
【００３８】
決定部１４０は、連接表を参照して形態素候補列のコストを算出し、候補列のうち最も適した系列を決定し、形態素解析結果の形態素列として出力する。連接表記憶部１５０は、部分文字列とその読みが連続したものと対応する各コストを表す連接表を記憶している。
【００３９】
（辞書装置のデータ構造）
辞書装置１２０は、そのインデックスに発音情報を埋め込んでいる。図２は、従来のデータ構造の一例を示す図である。図３は、本発明のデータ構造を示す図である。
【００４０】
図２に示すように、従来の発音情報をインデックスに含めない方法では、形態素末を表すノードに読みに関する情報が結び付けられる。この場合、インデックスの「会」の文字はトライ構造で共有されるが、読みに関する「カイシャ」「カイギ」の共通部分は直接的には共有されていない。
【００４１】
これに対し、図３に示す例では、「会社（カイシャ）」という形態素のインデックスに、「会／カイ／社／シャ」という文字列を使う。ここで文字「／」は表記の文字と読み情報を区切る区切り文字である。これにより、辞書構造にトライ（パトリシア木を含む）を使うことで、発音情報も含めて部分情報が木構造の同じノードに共有されるため、全体のサイズを抑えることができる。例えば形態素辞書に「会議（カイギ）」という形態素も存在する場合、インデックスのうち「会／カイ／社／シャ」と「会／カイ／議／ギ」の「／会／カイ／」の部分が共有される。
【００４２】
（トライに基づく特有のデータ構造）
トライにより構成された辞書装置１２０を用いて形態素解析処理を行なう場合、共通接頭辞探索として、トライのルートノードからリーフノード方向に木をたどり、ノード上の形態素を候補して出力する。
【００４３】
ただし、読み情報をインデックスに含む形態素解析辞書構造を形態素解析装置１００で用いる場合は、辞書のインデックスのうち、葉方向「／」で囲まれた区間にある読み情報は探索において無視して、その子ノードに遷移すればよい。ただし、ある文字に対して複数種類の発音情報が存在する場合には、発音情報に対応する部分のノードで複数の可能性が生じ、探索結果となり得る複数の子ノードが存在することになる。その場合、それらの全ての子ノードを候補として考える必要がある。
【００４４】
従来の方法では、共通接頭辞探索により列挙される形態素の候補は、トライの１つの経路上にしか存在しないが、本発明では、このように、異なる複数の経路上に形態素の候補が存在する可能性があるため、探索においては、このことを考慮する必要がある。具体的には、ルートからリーフまでのノードのリストを複数保持するためのリストを作成する必要がある。
【００４５】
（形態素解析装置の動作）
図４〜図６は、それぞれ形態素解析装置１００における照合部１１０の動作の一例を示すフローチャートである。図４は、照合部全体の処理を示している。図４に示すように、まず、それらの共通接頭辞探索の結果が入力された文字列に含まれる可能性のある形態素候補を列挙するように、入力された文字列から部分文字列に区切り、それらを列挙する（ステップＳ１０１）。ここでの部分文字列の列挙は、例えば、１文字目から最後の文字まで、２文字目から最後の文字まで、という処理を繰り返せばよい。次に、ひとつの部分文字列をを探索キーに設定する（ステップＳ１０２）。そして、サブルーチンＧ（ルートノード、０）を呼び出し、辞書に格納されたデータと探索キーと照合を行なう（ステップＳ１０３）。
【００４６】
図５は、文字列と探索キーとを照合するサブルーチン（Ｇ（Ｎ，ｋ））の処理を示している。Ｇ（Ｎ，ｋ）は、辞書データのノードＮと探索キーのｋ番目の文字との文字列の照合を意味している。図５に示すように、Ｎの子ノードを全て列挙し、ノードリストＬに格納し（ステップＳ２０１）、ｉに初期値０を設定する（ステップＳ２０２）。
【００４７】
次に、Ｌ［ｉ］への枝に結び付けられた文字が検索キーのｋ番目の文字と一致するかを判定する（ステップＳ２０３）。一致する場合には、Ｇ（Ｌ［ｉ］、ｋ＋１）を呼び出し（ステップＳ２０４）、ステップＳ２０７へ進む。
【００４８】
一致しない場合には、Ｌ［ｉ］への枝に結び付けられた文字が区切り文字か否かを判定する（ステップＳ２０５）。文字が区切り文字である場合には、サブルーチンＰ（Ｌ［ｉ］、ｋ）を呼び出し（ステップＳ２０６）、ステップＳ２０７に進む。一方、文字が区切り文字でない場合には、ステップＳ２０７に進む。
【００４９】
そして、ｉを１増加させ（ステップＳ２０７）、ｉがＬ［ｉ］の大きさ未満か否かを判定し（ステップＳ２０８）、未満である場合には、ステップＳ２０３に進む。ｉがＬ［ｉ］の大きさ以上である場合には、サブルーチンを終了し、もとの処理に戻る。
【００５０】
図６は、読み情報の照合のサブルーチン（Ｐ（Ｎ，ｋ））の処理を示している。サブルーチンＰ（Ｎ，ｋ）は、辞書データのノードＮと探索キーのｋ番目の文字との読みの照合を意味している。図６に示すように、Ｎの子ノードを全て列挙し、ノードリストＬに格納し（ステップＳ３０１）、ｉに初期値０を設定する（ステップＳ３０２）。
【００５１】
次に、Ｌ［ｉ］が形態素末か否かを判定する（ステップＳ３０３）。形態素末である場合には、ルートからＬ［ｉ］までの文字列を結果として出力し（ステップＳ３０４）、ステップＳ３０８へ進む。
【００５２】
形態素末でない場合には、Ｌ［ｉ］への枝に結び付けられた文字が区切り文字か否かを判定する（ステップＳ３０５）。文字が区切り文字である場合には、サブルーチンＧ（Ｌ［ｉ］、ｋ）を呼び出し（ステップＳ３０６）、ステップＳ３０８に進む。一方、文字が区切り文字でない場合には、サブルーチンＰ（Ｌ［ｉ］、ｋ）を呼び出し（ステップＳ３０７）、ステップＳ３０８に進む。
【００５３】
そして、ｉを１増加させ（ステップＳ３０８）、ｉがＬ［ｉ］の大きさ未満か否かを判定し（ステップＳ３０９）、未満である場合には、ステップＳ３０３に進む。ｉがＬ［ｉ］の大きさ以上である場合には、サブルーチンを終了し、もとの処理に戻る。なお、以上の処理は、コンピュータに処理を実行させることで行なうことができる。
【００５４】
（形態素解析処理の一例）
以下に処理の例を説明する。図７は、従来のデータ構造の一例を示す図である。図８は、本発明のデータ構造の一例を示す図である。
【００５５】
「秋葉原に行く」という文を形態素解析する場合、まず「秋葉原に行く」をキーとして共通接頭辞探索を行なう。この時、辞書に「秋（アキ）」「秋葉（アキバ）」「秋葉原（アキハバラ）」の３語が登録されている場合、形態素の候補としてこれらを列挙することになる。
【００５６】
しかし、図７に示すような従来の読み情報を含めないインデックスを用いた場合は、トライ上で、これら３語がルートノードから見て同じ経路上に存在する。つまり共通接頭辞探索において、トライ上の単一のパスのみを考慮すればよい。
【００５７】
これに対し、図８にしめすような本発明の方法では、「秋葉」と「秋葉原」は「葉」の部分の読みが異なるため、「秋葉原」に至るパス上に単語「秋葉」は存在しない。「秋／アキ／葉／」までが同じパス上にあり、それ以後は異なる枝に情報がそれぞれ格納される。
【００５８】
この処理では、親ノードがその全ての子ノードを高速に列挙できる必要がある。従来の形態素解析では、ある特定の文字が結び付けられた枝に連なる子ノードがあるか否かだけを高速に判定できれば良く、この部分が従来とは異なる。
【００５９】
しかし、そのようなデータ構造の実現は比較的容易であり、例えば親ノードは複数の子ノードのうちの１つの子ノードへのリンクだけを持ち、その子ノードを先頭に、全ての兄弟ノードに対するリスト構造を構築すればよい。あるいは、省メモリなトライの実装に使われるデータ構造であるＬＯＵＤＳは、読み情報をインデックスに含めない従来の方法であっても、木をリーフ方向にたどる際に子ノードを列挙するため、トライのデータ構造にＬＯＵＤＳを用いた実用なシステムは、本発明が要求する先述の条件を満たしている。
【００６０】
（制約が入力される場合の処理）
従来の辞書構造では、トライのノードに形態素情報が結び付けられていた。このため、読み情報に関する制約つき探索を行なう場合、共通接頭辞探索により形態素候補の全てを列挙してから、各形態素情報を調べて、読み制約を満たさない形態素候補を捨てる、といった処理が必要となる。
【００６１】
これに対し、本発明の形態素辞書構造を読み情報付で構築した場合、発音情報を単に読み飛ばすのではなく、発音情報が、与えられた読み情報に関する制約を満たすか否かをトライの探索の段階でチェックできる。そして、読み情報の制約条件を満たさない形態素を、より早い時点で形態素候補の列挙対象から除外することができる。これにより、列挙対象の形態素候補数が減り、処理量やメモリ使用量を減らすことができる。この場合、図６示したフローチャートに基づく処理を行なう場合においては、Ｓ３０３の直前に読み情報の制約条件を満たすかどうかのチェックを行ない、満たす場合はＳ３０３に、満たさない場合はＳ３０８に進むようにすればよい。
【００６２】
（その他の処理例）
図９は、本発明のデータ構造の一例を示す図である。例えば、「上（ウエ）」「上る（アガ・ル）」「上る（ノボ・ル）」の３語が辞書登録されているケースで、解析対象のテキストが「上る」、解析対象テキストのうち、「上」の読みとして、「ノボ」が指定されている場合、従来の辞書構造では、「上る」に対する共通接頭辞探索の結果、この３語を候補として得られるため、それぞれ読み情報を調べて、「上る（ノボ・ル）」以外の形態素を捨てる処理が必要となる。
【００６３】
これに対して本発明の方法では、探索において、「上／ノボ／る／＊」（ここで「＊」は「／」以外の文字で構成される全ての文字列を示す）をキーとしてｃｏｍｍｏｎ  ｐｒｅｆｉｘ  ｓｅａｒｃｈを行えばよく、インデックスが「上／ノボ／る／ル」となる「上る（ノボ・ル）」のみが共通接頭辞探索の結果として得られる。
【００６４】
この処理の際、読み方に対する揺らぎを考慮するために、先述のような読み情報の完全一致ではなく、別の選択基準を用いることもできる。例えば、指定された読み情報に対して編集距離がある値以下（一致文字数がある文字数以上）のみの形態素を形態素辞書の探索結果として列挙する、といったような曖昧性を認めた制約条件設定も可能である。
【００６５】
上記の説明では、表記文字列を構成する部分文字列と、それに対応する発音記号の間に、区切り記号「／」を入れるが、表記文字列１文字毎に発音情報が付与されることが規則化されている場合は、表記文字列の文字と発音情報の間に、区切り記号「／」を書かない形態も可能である。
【００６６】
あるいは、区切り記号を定義するのではなく、各ノードにおいて、その直前の枝に格納された文字が、表記文字列を表す文字か、読み情報を表す文字かを示す1ビットの情報を格納し、これを用いてもよい。これにより辞書のサイズをより抑えることができる。
【００６７】
また、これまでの説明では読み情報を片仮名だけで構成される文字列として例示しているが、これに限らない。例えば、ＪＥＩＴＡ  ＩＴ−４００６のように韻律情報を含む記号を用いてもよい。また、表記文字から読み情報が規則的に決まるケースについては、「規則的に決める」という意味を持つ符号を読み情報の１つとして定義し、読み情報の長さを削減する方法を用いることもできる。規則的に決まる読みの例としては、１種類の音読みしかない漢字が挙げられる。
【００６８】
また、本発明の方法では、読み情報以外の情報を格納してもよい。例えば形態素の生起コストが、文字表記における各文字の生起コストの和で定義されるような形態素解析システムにおいては、文字生起コストを表す記号を定義し、文字とこの記号の組を並べてトライのインデックスを構成することで、トライの木構造そのものに、形態素の生起コストに関する情報を直接埋め込むことができる。
【００６９】
この構造では、トライをたどる過程で生起コストの値が得られるので、形態素する候補を列挙する過程で形態素生成コストが大きい候補を捨てるといったような、形態素の生起コストを考慮した候補の列挙を行なうことができる。また、格納する情報は、読み情報と文字生起コストの組み合わせ等、様々な情報の組み合わせでもよい。
【００７０】
また、全ての表記文字列を前後逆順にした形での辞書構成も可能である。たとえば、文字列を前後逆にした形態素辞書を構築しておき、文の形態素解析では、逆順にした文の先頭から、すなわち元の文の末尾から先頭方向に向かって形態素候補を列挙する方法が考えられる。この場合、最終的に得られる最適な形態素列が、文頭から文末に向かって確定していくが、多くの装置では、形態素解析結果も文頭から文末方向に向かって出力するため、形態素解析結果を文末から文頭方向に確定させていく場合と異なり、形態素解析結果を一時的に保存する必要がなくなる、といった利点がある。
【符号の説明】
【００７１】
１００  形態素解析装置
１１０  照合部
１２０  辞書装置
１３０  制約参照部
１４０  決定部
１５０  連接表記憶部
【図１】
2015194801.tif 000003
【図２】
2015194801.tif 000004
【図３】
2015194801.tif 000005
【図４】
2015194801.tif 000006
【図５】
2015194801.tif 000007
【図６】
2015194801.tif 000008
【図７】
2015194801.tif 000009
【図８】
2015194801.tif 000010
【図９】
2015194801.tif 000011