(57)【要約】【課題】ｎグラム等の言語的特徴（出現確率）を用いるだけでなく、所定の重要な単語を含む単語列を上位解として選択することのできる単語列探索装置を提供する。【解決手段】単語の重要度を表わす重要度スコア値を記憶する単語重要度記憶部を備え、グラフを文頭のノードから探索しながら、グラフ上のノードにおいて、文頭のノードから当該ノードまでの単語の列に関して、単語重要度記憶部から読み出した重要度スコア値の積算値をも加味した前向きスコアを計算し、グラフを文末のノードから探索しながら、各ノードにおいて、文末のノードから当該ノードまでの単語の列に関して、単語重要度記憶部から読み出した重要度スコア値の積算値をも加味した後向きスコアを計算し、前向きスコアと後向きスコアとに基づいて、ノードの総合スコアを算出し、総合スコアの上位の単語列を出力する。【選択図】図１
2010191809.tif 000002
【特許請求の範囲】
【請求項１】
単語に対応するノードと前記ノード間を結ぶアークからなるグラフを表わすデータを記憶する単語グラフ記憶部と、
ｎ個（ｎは正の整数）の連続する単語の組と、当該組における前の（ｎ−１）個の単語の並びを前提とするｎ番目の単語の確率であるｎグラムスコア値とのデータを記憶する単語ｎグラム記憶部と、
単語と、当該単語の重要度を表わす重要度スコア値とを関連付けたデータを記憶する単語重要度記憶部と、
前記単語グラフ記憶部が記憶するグラフを文頭のノードから順に探索しながら、前記グラフ上の各ノードにおいて、文頭のノードから当該ノードまでの単語の列に関して、前記単語ｎグラム記憶部から読み出したｎグラムスコア値の積算値と、前記単語重要度記憶部から読み出した重要度スコア値の積算値とを加味した当該ノードの前向きスコアを計算する前向きスコア計算部と、
前記単語グラフ記憶部が記憶するグラフを文末のノードから順に探索しながら、前記グラフ上の各ノードにおいて、文末のノードから当該ノードまでの単語の列に関して、前記単語ｎグラム記憶部から読み出したｎグラムスコア値の積算値と、前記単語重要度記憶部から読み出した重要度スコア値の積算値とを加味した当該ノードの後向きスコアを計算する後向きスコア計算部と、
前記前向きスコア計算部が計算した前記前向きスコアと、前記後向きスコア計算部が計算した前記後向きスコアとに基づいて、当該ノードの総合スコアを算出するとともに、前記総合スコアの上位の所定個数の前記総合スコアと前記総合スコアに対応する単語列とを出力する総合スコア計算部と、
を具備することを特徴とする単語列探索装置。
【請求項２】
請求項１に記載の単語列探索装置であって、
所定個数の前記総合スコアと前記総合スコアに対応する単語列とを解候補として記憶する上位解記憶部を具備し、
前記総合スコア計算部は、前記グラフを文末のノードから順に後向き探索しながら、総合スコアが上位の前記所定個数の前記解候補が記憶されるように前記上位解記憶部を更新するとともに、総合スコアが上位の前記所定個数から外れた解候補がある場合には当該外れた解候補の単語列に関しては更なる後向き探索を抑止するよう制御する、
ことを特徴とする単語列探索装置。
【請求項３】
請求項１又は請求項２に記載の単語列探索装置であって、
第１言語および第２言語でそれぞれ書かれた用例文のペアのデータを記憶する用例文記憶部と、
前記第１言語で書かれた入力文を読み取り、当該入力文と前記用例文記憶部に記憶されている前記第１言語で書かれた用例文との類似度に基づき、前記第２言語で書かれた用例文を前記用例文記憶部から読み出し、この読み出された複数の前記用例文をアライメント処理して生成した単語グラフのデータを前記単語グラフ記憶部に書き込む解候補作成部と、
当該用例文に含まれる単語に対する前記第２言語の訳語については相対的に高い値を重要度スコア値として与え、それ以外の単語に対する前記第２言語の単語については相対的に低い値を重要度スコア値として与え、これら重要度スコア値を前記単語重要度記憶部に書き込む単語重要度算出部と、
を具備することを特徴とする単語列探索装置。
【請求項４】
単語に対応するノードと前記ノード間を結ぶアークからなるグラフを表わすデータを記憶する単語グラフ記憶部と、
ｎ個（ｎは正の整数）の連続する単語の組と、当該組における前の（ｎ−１）個の単語の並びを前提とするｎ番目の単語の確率であるｎグラムスコア値とのデータを記憶する単語ｎグラム記憶部と、
単語と、当該単語の重要度を表わす重要度スコア値とを関連付けたデータを記憶する単語重要度記憶部と、
を具備するコンピュータに、
前記単語グラフ記憶部が記憶するグラフを文頭のノードから順に探索しながら、前記グラフ上の各ノードにおいて、文頭のノードから当該ノードまでの単語の列に関して、前記単語ｎグラム記憶部から読み出したｎグラムスコア値の積算値と、前記単語重要度記憶部から読み出した重要度スコア値の積算値とを加味した当該ノードの前向きスコアを計算する前向きスコア計算過程と、
前記単語グラフ記憶部が記憶するグラフを文末のノードから順に探索しながら、前記グラフ上の各ノードにおいて、文末のノードから当該ノードまでの単語の列に関して、前記単語ｎグラム記憶部から読み出したｎグラムスコア値の積算値と、前記単語重要度記憶部から読み出した重要度スコア値の積算値とを加味した当該ノードの後向きスコアを計算する後向きスコア計算過程と、
前記前向きスコア計算過程で計算した前記前向きスコアと、前記後向きスコア計算過程で計算した前記後向きスコアとに基づいて、当該ノードの総合スコアを算出するとともに、前記総合スコアが良い順に所定個数の前記総合スコアと前記総合スコアに対応する単語列とを出力する総合スコア計算過程と、
の処理を実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自然言語処理に関する。本発明は、特に、所定の目的に沿った単語列を探索する単語列探索装置およびそのコンピュータプログラムに関する。
【背景技術】
【０００２】
機械翻訳や音声認識や形態素解析などにおいて、複数の単語列の候補の中から最も尤もらしい順に所定個数の単語列候補を得る処理過程が必要とされる。
【０００３】
特許文献１および非特許文献１には、単語列候補を前向き及び後向きに探索しながら、ｎグラム（ｎ−ｇｒａｍ）に基づいて最尤度を算出し、単語列候補を順位付けする技術が開示されている。
【０００４】
例えば、従来の技術を用いて、次の３つの解候補（ア）、（イ）、（ウ）から単語３−グラム（トライグラム，３−ｇｒａｍ）の積が大きい順に最適な２つの単語列を探索する方法を説明する。
（ア）＜文頭＞−Ｉｔ−ｉｓ−ｔｈｅ−Ｐｈｉｌｉｐｐｉｎｅｓ−＜文末＞
（イ）＜文頭＞−Ｉｔ−ｉｓ−Ｌｕｚｏｎ−Ｉｓｌａｎｄ−＜文末＞
（ウ）＜文頭＞−Ｉｔ−ｉｓ−Ｍｉｎｄａｎａｏ−ｉｓｌａｎｄ−＜文末＞
【０００５】
（ア）〜（ウ）は、それぞれ、単語の列であり、単語の３−グラムの値は予め統計等に基づき与えられている。なお便宜上「＜文頭＞」および「＜文末＞」も単語の一種として扱い、これらを含む３−グラムの値も同様に与えられている。それらの３−グラムの一部は、例えば、下の通りである。
ｐ（ｉｓ｜＜文頭＞，Ｉｔ）＝０．１
ｐ（ｔｈｅ｜Ｉｔ，ｉｓ）＝０．１
ｐ（Ｐｈｉｌｉｐｐｉｎｅｓ｜ｉｓ，ｔｈｅ）＝０．０１
ｐ（＜文末＞｜ｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ）＝０．００１
ｐ（Ｌｕｚｏｎ｜Ｉｔ，ｉｓ）＝０．０１
ｐ（Ｉｓｌａｎｄ｜ｉｓ，Ｌｕｚｏｎ）＝０．０１
ｐ（＜文末＞｜Ｌｕｚｏｎ，Ｉｓｌａｎｄ）＝０．００１
ｐ（Ｍｉｎｄａｎａｏ｜Ｉｔ，ｉｓ）＝０．００１
ｐ（ｉｓｌａｎｄ｜ｉｓ，Ｍｉｎｄａｎａｏ）＝０．００１ 
ｐ（＜文末＞｜Ｍｉｎｄａｎａｏ，ｉｓｌａｎｄ）＝０．００１
【０００６】
また、一般的に単語列ｅ０−ｅ１−・・・−ｅＮに対してその最尤度を、次の式（１）で定義できる。
【０００７】
【数１】
2010191809.tif 000003
【０００８】
ここで、ｐ（ｅｉ｜ｅｉ−１，ｅｉ−２）は、３−グラムの値であり、単語列ｅｉ−１−ｅｉ−２を前提としたときに次に単語ｅｉが出現する確率（条件付確率）である。但し、コンピュータ等を用いて式（１）の値をそのまま計算した場合には、コンピュータの内部の数値表現形式によってはオーバーフローやアンダーフローが起こって適切な計算が行なえない場合もあり得るため、これを避けるために、１０を底とする対数を取り、計算する。式（１）で表わした最尤度の対数を取ったものは、次の式（２）で表わされる。
【０００９】
【数２】
2010191809.tif 000004
【００１０】
式（２）により、前記の解候補（ア）〜（ウ）それぞれの最尤度を計算すると次のようになる。
（ア）＜文頭＞−It−is−the−Philippines−＜文末＞  の場合：
ｌｏｇ［ｐ（ｉｓ｜＜文頭＞，Ｉｔ）］＋ｌｏｇ［ｐ（ｔｈｅ｜Ｉｔ，ｉｓ）］＋ｌｏｇ［ｐ（Ｐｈｉｌｉｐｐｉｎｅｓ｜ｉｓ，ｔｈｅ）］＋ｌｏｇ［ｐ（＜文末＞｜ｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ）］
＝(−１)＋（−１）＋（−２）＋（−３）＝−７
（イ）＜文頭＞−It−is−Luzon−Island−＜文末＞  の場合：
ｌｏｇ［ｐ（ｉｓ｜＜文頭＞，Ｉｔ）］＋ｌｏｇ［ｐ（Ｌｕｚｏｎ｜Ｉｔ，ｉｓ）］＋ｌｏｇ［ｐ（Ｉｓｌａｎｄ｜ｉｓ，Ｌｕｚｏｎ）］＋ｌｏｇ［ｐ（＜文末＞｜Ｌｕｚｏｎ，Ｉｓｌａｎｄ）］
＝(−１)＋（−２）＋（−２）＋（−３）＝−８
（ウ）＜文頭＞−It−is−Mindanao−island−＜文末＞  の場合：
ｌｏｇ［ｐ（ｉｓ｜＜文頭＞，Ｉｔ）］＋ｌｏｇ［ｐ（Ｍｉｎｄａｎａｏ｜Ｉｔ，ｉｓ）］＋ｌｏｇ［ｐ（ｉｓｌａｎｄ｜ｉｓ，Ｍｉｎｄａｎａｏ）］＋ｌｏｇ［ｐ（＜文末＞｜Ｍｉｎｄａｎａｏ，ｉｓｌａｎｄ）］
＝(−１)＋（−３）＋（−３）＋（−３）＝−１０
【００１１】
以上のような計算結果により、解候補を最尤度の大きい順に並べると、（ア）―（イ）―（ウ）となる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平７−２７１７９２号公報
【非特許文献】
【００１３】
【非特許文献１】永田昌明，「統計的言語モデルとＮ−ｂｅｓｔ探索を用いた日本語形態素解析法」，情報処理学会論文誌，１９９９年９月，Ｖｏｌ．４０，Ｎｏ．９，ｐｐ．３４２０−３４３１
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、従来技術による方法では、単語そのものの重要性を考慮せずに単語列の最適解を選択してしまう場合があるという問題があった。機械翻訳や音声認識や形態素解析の処理の場合、たとえｎグラムによる出現確率が小さくても、所定の重要な単語を含む単語列を最適解とすべき場合がある。例えば機械翻訳において、日本語の入力文「それはミンダナオ島である」の英訳文として前記の（ア）〜（ウ）の候補の中から解を選択する場合には、元の日本語文の訳語である英単語が重要性を有するが、従来技術ではその英単語が特に重視されずに解候補が選択されてしまうという問題があった。
【００１５】
本発明は、上記のような事情を考慮して為されたものであり、言語モデル（ｎグラム等）による出現確率だけで単語列を探索するのではなく、同時に、所定の重要な単語を含む単語列を上位解として選択できるように探索を行なう単語列探索装置およびそのコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
［１］上記の課題を解決するため、本発明の一態様による単語列探索装置は、単語に対応するノードと前記ノード間を結ぶアークからなるグラフを表わすデータを記憶する単語グラフ記憶部と、ｎ個（ｎは正の整数）の連続する単語の組と、当該組における前の（ｎ−１）個の単語の並びを前提とするｎ番目の単語の確率であるｎグラムスコア値とのデータを記憶する単語ｎグラム記憶部と、単語と、当該単語の重要度を表わす重要度スコア値とを関連付けたデータを記憶する単語重要度記憶部と、前記単語グラフ記憶部が記憶するグラフを文頭のノードから順に探索しながら、前記グラフ上の各ノードにおいて、文頭のノードから当該ノードまでの単語の列に関して、前記単語ｎグラム記憶部から読み出したｎグラムスコア値の積算値と、前記単語重要度記憶部から読み出した重要度スコア値の積算値とを加味した当該ノードの前向きスコアを計算する前向きスコア計算部と、前記単語グラフ記憶部が記憶するグラフを文末のノードから順に探索しながら、前記グラフ上の各ノードにおいて、文末のノードから当該ノードまでの単語の列に関して、前記単語ｎグラム記憶部から読み出したｎグラムスコア値の積算値と、前記単語重要度記憶部から読み出した重要度スコア値の積算値とを加味した当該ノードの後向きスコアを計算する後向きスコア計算部と、前記前向きスコア計算部が計算した前記前向きスコアと、前記後向きスコア計算部が計算した前記後向きスコアとに基づいて、当該ノードの総合スコアを算出するとともに、前記総合スコアの上位の所定個数の前記総合スコアと前記総合スコアに対応する単語列とを出力する総合スコア計算部とを具備することを特徴とする。
ここで、単語グラフのノードに対応する単語としては、通常の単語と、文の文頭と、文の文末のそれぞれが含まれる。文頭に対応するノードから、このグラフをたどって複数のノード（通常の単語に対応するノード）を通り、そして文末に対応するノードに至るパスは、単語列を表わす。つまり、この単語グラフは、複数の単語列（文）の候補を表わす。
総合スコア計算部が計算する総合スコアは、ｎグラムに基づく言語としてのスコア（確率）と与えられた単語重要度に基づくスコアの両方を加味したスコアである。このように総合スコアを計算することにより、単に言語としての確率が高いだけの単語列ではなく、所定の重要な単語が含まれる度合いも高い単語列が、上位の解候補として出力されることになる。
【００１７】
［２］また、本発明の一態様は、上記の単語列探索装置において、所定個数の前記総合スコアと前記総合スコアに対応する単語列とを解候補として記憶する上位解記憶部を更に具備し、前記総合スコア計算部は、前記グラフを文末のノードから順に後向き探索しながら、総合スコアが上位の前記所定個数の前記解候補が記憶されるように前記上位解記憶部を更新するとともに、総合スコアが上位の前記所定個数から外れた解候補がある場合には当該外れた解候補の単語列に関しては更なる後向き探索を抑止するよう制御することを特徴とするものである。
これにより、後向き探索の途中で、スコアの低い解候補については更なる後ろ向き探索が抑止されるため、総合スコア計算部は、限られた探索空間のみを探索して得られる総合スコアを計算する。これにより処理効率が向上する。
【００１８】
［３］また、本発明の一態様は、上記の単語列探索装置において、第１言語および第２言語でそれぞれ書かれた用例文のペアのデータを記憶する用例文記憶部と、前記第１言語で書かれた入力文を読み取り、当該入力文と前記用例文記憶部に記憶されている前記第１言語で書かれた用例文との類似度に基づき、前記第２言語で書かれた用例文を前記用例文記憶部から読み出し、この読み出された複数の前記用例文をアライメント処理して生成した単語グラフのデータを前記単語グラフ記憶部に書き込む解候補作成部と、当該用例文に含まれる単語に対する前記第２言語の訳語については相対的に高い値を重要度スコア値として与え、それ以外の単語に対する前記第２言語の単語については相対的に低い値を重要度スコア値として与え、これら重要度スコア値を前記単語重要度記憶部に書き込む単語重要度算出部とを具備することを特徴とするものである。
これにより、第１言語および第２言語でそれぞれ書かれた用例文のペアのデータを予め用例文記憶部に記憶させておく。また、解候補作成部は入力文と用例文との間の第１言語内類似度により用例を選択し、選択された用例についての第２言語での用例文をアライメント処理することによって作成した単語グラフのデータを単語グラフ記憶部に書き込む。また、単語重要度算出部は、前記の用例文に含まれる単語に対して第２言語の訳語となる単語に対しては高い重要度スコア値を与え、それ以外の単語に対する単語に対しては低い重要度スコア値を与え、これらを単語重要度記憶部に書き込む。これらのデータにより前向きスコアを計算し、後向きスコアを計算し、そして総合スコアを計算すると、入力文に含まれる第１言語の単語に対する訳語である第２言語の単語には高い重要度スコアが与えられているため、言語グラフが表わす解候補の単語列の中で、そのような訳語を含む単語列の総合スコアが相対的に高くなる。よって、総合スコアの上位に入る解候補は、元の入力文に対する翻訳文（用例翻訳）となっている度合いが高い。よって、本発明による単語列探索装置を用いて、用例による機械翻訳を高い精度で行うことが可能となる。
【００１９】
［４］また、本発明の一態様は、単語に対応するノードと前記ノード間を結ぶアークからなるグラフを表わすデータを記憶する単語グラフ記憶部と、ｎ個（ｎは正の整数）の連続する単語の組と、当該組における前の（ｎ−１）個の単語の並びを前提とするｎ番目の単語の確率であるｎグラムスコア値とのデータを記憶する単語ｎグラム記憶部と、単語と、当該単語の重要度を表わす重要度スコア値とを関連付けたデータを記憶する単語重要度記憶部とを具備するコンピュータに、前記単語グラフ記憶部が記憶するグラフを文頭のノードから順に探索しながら、前記グラフ上の各ノードにおいて、文頭のノードから当該ノードまでの単語の列に関して、前記単語ｎグラム記憶部から読み出したｎグラムスコア値の積算値と、前記単語重要度記憶部から読み出した重要度スコア値の積算値とを加味した当該ノードの前向きスコアを計算する前向きスコア計算過程と、前記単語グラフ記憶部が記憶するグラフを文末のノードから順に探索しながら、前記グラフ上の各ノードにおいて、文末のノードから当該ノードまでの単語の列に関して、前記単語ｎグラム記憶部から読み出したｎグラムスコア値の積算値と、前記単語重要度記憶部から読み出した重要度スコア値の積算値とを加味した当該ノードの後向きスコアを計算する後向きスコア計算過程と、前記前向きスコア計算過程で計算した前記前向きスコアと、前記後向きスコア計算過程で計算した前記後向きスコアとに基づいて、当該ノードの総合スコアを算出するとともに、前記総合スコアが良い順に所定個数の前記総合スコアと前記総合スコアに対応する単語列とを出力する総合スコア計算過程との処理を実行させるコンピュータプログラムである。
【発明の効果】
【００２０】
本発明によれば、単語列探索装置は、ｎグラムスコア値だけではなく、単語の重要度スコア値をも用いて単語列の総合スコアを計算し、その上位解を出力している。従って、言語モデルによる一般的な出現確率のみによらず、出力すべき解における単語の重要度を加味して上位解を選択肢出力することができる。これにより、単語列探索の精度が向上する。
また、本発明によれば、単語列探索装置は、前向きスコア計算部が単語ノードを文頭から前向きの方向に各ノードについての前向きスコアを計算し、後向きスコアが逆に文末から後向きの方向に探索しながら各ノードについての後ろ向きスコアを計算し、その後向き探索の過程においてノードの総合スコアを計算しながら、この総合スコアが上位の所定個数に入らない解候補については、それ以上の後向き探索を抑止するように制御している。従って、後向き探索の途中において、スコアの悪いパスを早めに枝刈りすることができ、探索の効率が上がる。特に、自然言語を対象とした現実の機械翻訳や音声認識や形態素解析の処理など、サイズの大きい単語グラフから最適な上位解を求める場合には、このように探索空間を絞り込むことによる処理時間の短縮は顕著である。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施形態による単語列探索装置の機能構成を示すブロック図である。
【図２】同実施形態における単語グラフ記憶部が記憶するデータの構成及びデータ例を示す概略図である。
【図３】同実施形態による単語グラフ記憶部が記憶するデータによって表わされる単語グラフの例を示す概略図である。
【図４】同実施形態による単語ｎグラム記憶部が記憶するデータの構成およびデータ例を示す概略図である。
【図５】同実施形態による単語重要度記憶部が記憶するデータの構成およびデータ例を示す概略図である。
【図６】同実施形態による単語列探索装置が指定された個数の上位の解（単語列）を求める処理の動作手順を示すフローチャートである。
【図７】同実施形態における単語グラフと、後向き探索によって計算する総合スコアとの関係を示す概略図である。
【図８】第２の実施形態による単語列探索装置の機能構成を示すブロック図である。
【図９】同実施形態による解候補作成部が収集した用例文のペアの集合の例を示す概略図である。
【図１０】同実施形態による解候補作成部が作成し、単語グラフ記憶部に書き込む単語グラフの一例を示す概略図である。
【発明を実施するための形態】
【００２２】
次に、本発明の実施形態について、図面を参照しながら説明する。
［第１の実施の形態］
図１は、第１の実施形態による単語列探索装置の機能構成を示すブロック図である。図示するように、本実施形態による単語列探索装置１０１は、単語ｎグラム記憶部１と、単語重要度記憶部２と、単語グラフ記憶部８と、前向きスコア計算部３と、前向きスコア記憶部４と、後向きスコア計算部５と、総合スコア計算部６と、上位解記憶部７とを含んで構成される。
これらの機能のうち、単語ｎグラム記憶部１と、単語重要度記憶部２と、単語グラフ記憶部８と、前向きスコア記憶部４と、上位解記憶部７とは、例えば半導体メモリや磁気ハードディスク装置などの記憶手段を用いて実現される。また、前向きスコア計算部３と、前向きスコア記憶部４と、後向きスコア計算部５と、総合スコア計算部６とは、例えば、二値論理を扱う電子回路を用いて実現される。
【００２３】
単語グラフ記憶部８は、入力端子を介して外部から入力される単語グラフのデータを記憶するものである。単語列の解の候補は、単語の半順序として与えられ、これがグラフのデータとして表現されている。単語ｎグラム記憶部１は、単語のｎグラムのスコアに関するデータを記憶するものである。単語重要度記憶部２は、単語の重要度を表わすスコアに関するデータを記憶するものである。なお、これらの各記憶部のデータの詳細については、後述する。
【００２４】
前向きスコア計算部３は、単語グラフ記憶部８が記憶するグラフを文頭のノードから順に探索しながら、このグラフ上の各ノードにおいて、文頭のノードから当該ノードまでの単語の列に関して、単語ｎグラム記憶部１から読み出したｎグラムスコア値の積算値と、単語重要度記憶部２から読み出した重要度スコア値の積算値とを加味した当該ノードの前向きスコアを計算し、その計算結果を前向きスコア記憶部４に書き込む。前向きスコアの計算の詳細については後述する。なお、ｎグラムスコア値の積算値あるいは重要度スコア値の積算値とは、単に各々のノードのスコア値の総積を取る場合と、各々のノードのスコア値の対数の総和を取る場合の両方を含む。
前向きスコア記憶部４は、前向きスコア計算部３によって計算されたスコアを一時的に記憶しておくものである。
【００２５】
後向きスコア計算部５は、単語グラフ記憶部８が記憶するグラフを文末のノードから順に探索しながら、このグラフ上の各ノードにおいて、文末のノードから当該ノードまでの単語の列に関して、単語ｎグラム記憶部１から読み出したｎグラムスコア値の積算値と、前記単語重要度記憶部から読み出した重要度スコア値の積算値とを加味した当該ノードの後向きスコアを計算する。後向きスコアの計算の詳細については後述する。なお、ｎグラムスコア値の積算値あるいは重要度スコア値の積算値とは、前向きスコアに関して既に述べたものと同様である。
【００２６】
総合スコア計算部６は、それぞれの単語（単語グラフ上のノード）について、前向きスコア記憶部４から読み出した前向きスコアと、後向きスコア計算部５が算出した後向きスコアとに基づいて、総合スコアを算出するとともに、ここで算出されたスコアが上位解記憶部７に記憶されている解候補（ｎ−ｂｅｓｔ）のスコアよりも良い場合には、上位解記憶部７を更新する。言い換えれば、総合スコア計算部６は、ノードの総合スコアを算出するとともに、この総合スコアの上位の所定個数の総合スコアとそれに対応する単語列とを出力する。
なお、上位解記憶部７に格納されている内容（所定個数の上位解とそのスコア）を、出力端子から装置の外部に出力できるようになっている。
【００２７】
図２は、前述の単語グラフ記憶部８が記憶するデータの構成及びデータ例を示す概略図である。単語グラフ記憶部８は、２種類のテーブルを記憶しており、そのそれぞれは、単語グラフのノードとアークとを表わすテーブルである。
図２（ａ）は、上記の２種類のうちの第１のテーブルを示す。このテーブルは、ノード番号と単語の各データ項目を有しており、ノード番号が主キーである。このテーブルの各行がノードに対応している。図示するデータ例では、ノード番号０のノードが単語「＜文頭＞」に対応し、ノード番号１のノードが単語「Ｉｔ」に対応し、ノード番号２のノードが単語「ｉｓ」に対応し、以下同様である。
図２（ｂ）は、上記の２種類のうちの第２のテーブルを示す。このテーブルは、アーク番号と開始ノード番号と終了ノード番号の各データ項目を有しており、アーク番号が主キーである。このテーグルの各行がアークに対応している。図示するデータ例では、アーク番号０のアークの開始ノード番号は０であって終了ノード番号は１である。また、アーク番号１のアークの開始ノード番号は０であって終了ノード番号は３である。また、アーク番号２のアークの開始ノード番号は１であって終了ノード番号は２であり、以下も同様である。
なお、単語グラフ記憶部８が記憶するデータによって表わされる単語グラフは、有向グラフであり、各アークは、文頭側から文末側への向きを有している。
【００２８】
図３は、単語グラフ記憶部８が記憶するデータによって表わされる単語グラフの例を図的に示す概略図である。同図において、丸印はノードを示し、矢印はアークを示す。各ノードには、ノード番号および単語が付記されている。ノードの中で、二重丸で示している２つのノードは、それぞれ「＜文頭＞」および「＜文末＞」を表わすノードである。なお、同図に示すグラフは、図２（ａ）および（ｂ）に示したデータ例に対応している。例えば、アーク番号１のアークは、ノード番号０のノード（単語「＜文頭＞」）からノード番号３のノード（単語「ｔｈｅ」）に至るものである。また例えば、アーク番号７のアークは、ノード番号５のノード（単語「Ｌｕｚｏｎ」）からノード番号６のノード（単語「Ｉｓｌａｎｄ」）に至るものである。
【００２９】
図４は、単語ｎグラム記憶部１が記憶するデータの構成およびデータ例を示す概略図である。このデータは、ｎ個（ｎは正の整数）の連続する単語の組（同図におけるｗ１，ｗ２，ｗ３）と、当該組における前の（ｎ−１）個の単語の並び（同図におけるｗ１，ｗ２）を前提とするｎ番目の単語（同図におけるｗ３）の確率であるｎグラムスコア値とのデータを記憶する。本実施形態では、単語ｎグラムとして、単語３−グラムを用いている。図示するように、このデータはテーブル形式のデータであり、単語ｗ１、単語ｗ２、単語ｗ３、スコアの各データ項目を有する。このテーブルの各行が３−グラムに対応し、３−グラムのスコアｐ（ｗ３｜ｗ１，ｗ２）は、単語列ｗ１−ｗ２を前提とするときの単語ｗ３が出現する確率（条件付確率）である。例えば、同図に示す第１行目のデータは、単語ｗ１が「＜文頭＞」、単語ｗ２が「Ｉｔ」、単語ｗ３が「ｉｓ」であり、それに対応するスコアｐ（＜文頭＞｜Ｉｔ，ｉｓ）が０．１であることを表わしている。
なお、スコアとして、ｐ（ｗ３｜ｗ１，ｗ２）の値をテーブルに保持する代わりに、１０を底とするその対数ｌｏｇ［ｐ（ｗ３｜ｗ１，ｗ２）］の値をテーブルに保持したり、それら両方をテーブルに保持したりするようにしても良い。
【００３０】
図５は、単語重要度記憶部２が記憶するデータの構成およびデータ例を示す概略図である。なお、本実施形態では、単語重要度記憶部２は、外部から与えられた単語重要度の値を予め記憶しておく。図示するように、単語重要度記憶部２はテーブル形式のデータを記憶するものであり、このテーブルは、単語ｗとスコア（重要度スコア値）の各項目のデータを関連付けて保持する。このテーブルの各行が、単語に対応する。このテーブルに記憶しているスコアｑ（ｗ）は、単語ｗに与えられた固有の値である。例えば、同図に示す第５行目のデータは、単語ｗが「Ｐｈｉｌｉｐｐｉｎｅｓ」であり、それに対応するスコアｑ（ｗ）が０．００１であることを表わしている。
なお、スコアとして、ｑ（ｗ）の値をテーブルに保持する代わりに、１０を底とするその対数ｌｏｇ［ｑ（ｗ）］の値をテーブルに保持したり、それら両方をテーブルに保持したりするようにしても良い。
【００３１】
図６は、単語列探索装置１０１が単語列のスコアを算出し、指定された個数の上位の単語列を求める処理の動作手順を示すフローチャートである。この動作手順では、前向きＤＰ後向きＡ＊アルゴリズムを用いている。また、スコアの算出においては、単語の重要度を表わすスコア値を用いている。以下、このフローチャートに沿って、説明する。
なお、この処理手順に先立って予め、単語ｎグラム記憶部１にはｎグラムのスコアのデータを格納しておき、単語重要度記憶部２には単語重要度のスコアのデータを格納しておく。また予め、入力端子から入力された単語グラフのデータを、単語グラフ記憶部８に格納しておく。
【００３２】
まずステップＳ１において、前向きスコア計算部３は、単語グラフ記憶部８から単語グラフのデータを読み出し、現ノードを文頭のノードに設定する。
次にステップＳ２において、前向きスコア計算部３は、現ノードにおける前向きスコアを計算し、その結果を、現ノードと関連付ける形で前向きスコア記憶部４に書き込む。前向きスコアの計算の詳細については、
【００３３】
次にステップＳ３において、前向きスコア計算部３は、まだ前向きスコアを計算していない未処理ノードがあるか否かを判定する。
なお、前向きスコア計算部３は、ノードの前向きスコアをパスごとにそれぞれ計算する。言い換えれば、文頭のノードからあるノードへのパスが複数存在する場合（例えば、図３に示す単語グラフの場合、ノード番号０＜文頭＞からノード番号３（「ｔｈｅ」）へは、２つのパス（ノード０−３のパスとノード０−１−２−３のパス）が存在する）、当該ノードに関して、それぞれのパスについての前向きスコアが計算される。従って、本ステップにおける判定も、すべてのパスについて前向きスコア算出の処理が完了していないノードがあるか否かにより行なう。
未処理ノードがある場合（ステップＳ３：ＹＥＳ）にはステップＳ４に進み、未処理ノードがない場合（ステップＳ３：ＮＯ）には、後向きスコア算出の処理に移るためにステップＳ５に進む。
ステップＳ４においては、前向きスコア計算部３は、現ノードを次のノード（前向きスコアをまだ計算していないノード）に設定する。ステップＳ４の処理の次には、ステップＳ２の処理に戻る。
【００３４】
ステップＳ５においては、後向きスコア計算部５は、現ノードを文末のノードに設定する。
次にステップＳ６においては、後向きスコア計算部５が現ノードにおける後ろ向きスコアを計算する。そして、同ステップにおいて、総合スコア計算部６は、前向きスコア記憶部４から読み出した当該ノードの前向きスコアと、後向きスコア計算部５が計算した後ろ向きスコアとに基づいて、総合スコアを計算する。そして、総合スコア計算部６は、上位解記憶部７に現在記憶されている上位所定個数の解（ｎ−ｂｅｓｔ解）の総合スコアと現ノードの総合スコアとを比較し、現ノードの総合スコアが上位所定個数の解に含まれるならば、当該ノードまでの単語列と総合スコアを上位解記憶部７に書き込むとともに、これによって上位解から外れることとなったノードについてはノード終了とする。なお、ノード終了となったノードについては、この先はさらなる後ろ向き探索を行なわない。
つまり、総合スコア計算部６は、単語グラフを文末のノードから順に後向き探索しながら、総合スコアが上位の所定個数の解候補が記憶されるように上位解記憶部７を更新するとともに、総合スコアが上位の所定個数から外れた解候補がある場合には当該外れた解候補の単語列に関しては更なる後向き探索を抑止するよう制御する、
【００３５】
次にステップＳ７において、後向きスコア計算部５は、まだ後向きスコアを計算していない未処理ノードがあるか否かを判定する。
なお、前向きスコア計算のときと同様に、後向きスコア計算部５は、ノードの後向きスコアをパスごとにそれぞれ計算する。また、本ステップにおける判定も、すべてのパスについて前向きスコア算出の処理が完了していないノードがあるか否かにより行なう。また、上記の通り、ノード終了となったノードから先の後向き探索は行なわれないため、本ステップにおいても、ノード終了となったノードから先のノードは完了しているものとして判定を行なう。
未処理ノードがある場合（ステップＳ７：ＹＥＳ）にはステップＳ８に進み、未処理ノードがない場合（ステップＳ７：ＮＯ）には上位の単語列を出力するためにステップＳ９に進む。
ステップＳ８においては、後向きスコア計算部５は、現ノードを次のノード（後向きスコアをまだ計算していないノードであって、ノード終了となったノードから先のノードを除く）に設定する。ステップＳ８の処理の次には、ステップＳ６の処理に戻る。
【００３６】
ステップＳ９では、単語列探索装置１０１は、上位解記憶部７に記憶されている指定された個数の上位解の単語列を出力する。
【００３７】
次に、スコアの計算の詳細と、算出例について説明する。
まず、前向きスコア計算部３による前向きスコアの計算の詳細を説明する。なお、ｅｉは、ノード番号ｉのノードに対応する単語を表わす。また、ノード番号ｉのノードにおける、ｅｉ−ｎ＋１−ｅｉ−ｎ＋２−・・・−ｅｉ−１のパスを前提とする前向きスコアを、下の式（３）のように定義する。
【００３８】
【数３】
2010191809.tif 000005
【００３９】
式（３）が表わしているように、ｉ番目のノード（単語ｅｉ）の前向きスコアは、単語ｅｉ−ｎ＋１からｅｉまでの部分単語列に依存するものであり、ひとつ前のノードの単語ｅｉ−１の重要度と、ひとつ前のノード（ノード番号ｉ−１）の前向きスコア（但し、グラフ形状によりｅｉ−ｎが複数存在する場合には、その各々のｅｉ−ｎについての最大値）と、ｎグラムの値（ｅｉが出現する条件付確率）の積である。言い換えれば、ｉ番目のノードの前向きスコアは、文頭から当該ノードまでのｎグラムの値の総積と、文頭からひとつ前のノードまでの単語重要度の値の総積との積である。つまり、前向きスコア計算部３は、単なるｎグラムの積だけではなく、単語重要度を加味した前向きスコアを計算する。
【００４０】
なお、本実施形態はｎグラムとして３−グラムを用いるため、これに応じて上の式（３）を書き換えると、下の式（４）となる。
【００４１】
【数４】
2010191809.tif 000006
【００４２】
但し、本実施形態では、１０を底とする対数によるスコアの計算を行なうため、上の式（４）で表わした値そのものではなく、下の式（５）を計算する。なお、式（５）等において、対数の底の「１０」の表記を省略している。
【００４３】
【数５】
2010191809.tif 000007
【００４４】
ノード番号０の「＜文頭＞」のノードに対して、前向きスコア計算部３は、次のように前向きスコアを計算する。
ｌｏｇ［α＃，＃（＜文頭＞）］
＝ｌｏｇ［ｑ（＃）］＋ｌｏｇ｛ｍａｘ＃［α＃，＃（＃）］｝＋ｌｏｇ｛ｐ（＜文頭＞｜＃，＃）｝
＝０＋０＋０＝０
ここで、「＃」は、ダミーの単語を表わす。このダミーの単語は、ｅ０の前向きスコアを計算する際、実際には単語ｅ−１やｅ−２が存在しないために用いるものである。なお、ダミーの単語が関係するこれらのスコア値は、次のように定義している。
ｑ（＃）＝１、よって、ｌｏｇ［ｑ（＃）］＝０
α＃，＃（＃）＝１、よって、ｌｏｇ｛ｍａｘ＃［α＃，＃（＃）］｝＝０
ｐ（＜文頭＞｜＃，＃）＝１、よって、ｌｏｇ｛ｐ（＜文頭＞｜＃，＃）｝＝０
【００４５】
そして、ノード番号１の単語「Ｉｔ」のノードに対する前向きスコアは次の通りである。
ｌｏｇ［α＃，＜文頭＞（Ｉｔ）］
＝ｌｏｇ［ｑ（＜文頭＞）］＋ｌｏｇ｛ｍａｘ｛＃｝［α＃，＃（＜文頭＞）］｝＋ｌｏｇ｛ｐ（Ｉｔ｜＃，＜文頭＞）｝
＝０＋０＋０＝０
ここでも、ダミーの単語「＃」が関係するスコア値は、定義により与えられている。また、単語重要度記憶部２に記憶されているデータにより、ｑ（＜文頭＞）＝１である。また、以下においても同様に、前向きスコア計算部３は、単語重要度記憶部２から、単語重要度ｑ（ｗ）のデータを読み出して使用する。
【００４６】
そして、ノード番号２の単語「ｉｓ」のノードに対する前向きスコアは次の通りである。
ｌｏｇ［α＜文頭＞，Ｉｔ（ｉｓ）］
＝ｌｏｇ［ｑ（Ｉｔ）］＋ｌｏｇ｛ｍａｘ｛＃｝［α＃，＜文頭＞（Ｉｔ）］｝＋ｌｏｇ｛ｐ（ｉｓ｜＜文頭＞，Ｉｔ）｝
＝０＋０＋（−１）＝−１
ここでは、前向きスコア計算部３は、α＃，＜文頭＞（Ｉｔ）の値としては、ｉ＝１のときに計算された値を利用している。また、以下においても同様に、前向きスコア計算部３は、既に計算した前向きスコアの値を、後のノードについて求める前向きスコアの計算において使用することができる。
また、単語ｎグラム記憶部１に記憶されているデータにより、３−グラムのスコアｐ（ｉｓ｜＜文頭＞，Ｉｔ）＝０．１である。また、以下においても同様に、前向きスコア計算部３は、単語ｎグラム記憶部１から、３−グラムのスコアｐ（ｗ３｜ｗ１，ｗ２）のデータを読み出して使用する。
【００４７】
そして、ノード番号３の単語「ｔｈｅ」のノードに対する前向きスコアは、２つのパスそれぞれについて、次の通りである。
まず、第１のパス（＃−＜文頭＞−ｔｈｅ）については、
ｌｏｇ［α＃，＜文頭＞（ｔｈｅ）］
＝ｌｏｇ［ｑ（＜文頭＞）］＋ｌｏｇ｛ｍａｘ｛＃｝［α＃，＃（＜文頭＞）］｝＋ｌｏｇ｛ｐ（ｔｈｅ｜＃，＜文頭＞）｝
＝０＋０＋０＝０
また、第２のパス（Ｉｔ−ｉｓ−ｔｈｅ）については、
ｌｏｇ［αＩｔ，ｉｓ（ｔｈｅ）］
＝ｌｏｇ［ｑ（ｉｓ）］＋ｌｏｇ｛ｍａｘ｛＜文頭＞｝［α＜文頭＞，Ｉｔ（ｉｓ）］｝＋ｌｏｇ｛ｐ（ｔｈｅ｜Ｉｔ，ｉｓ）｝
＝０＋（−１）＋（−１）＝−２
【００４８】
そして、ノード番号４の単語「Ｐｈｉｌｉｐｐｉｎｅｓ」のノードに対する前向きスコアは、２つのパスそれぞれについて、次の通りである。
まず、第１のパス（＜文頭＞−ｔｈｅ−Ｐｈｉｌｉｐｐｉｎｅｓ）については、
ｌｏｇ［α＜文頭＞，Ｔｈｅ（Ｐｈｉｌｉｐｐｉｎｅｓ）］
＝ｌｏｇ［ｑ（ｔｈｅ）］＋ｌｏｇ｛ｍａｘ｛＃｝［α＃，＜文頭＞（ｔｈｅ）］｝＋ｌｏｇ｛ｐ（Ｐｈｉｌｉｐｐｉｎｅｓ｜＜文頭＞，ｔｈｅ）｝
＝０＋０＋（−１）＝−１
また、第２のパス（ｉｓ−ｔｈｅ−Ｐｈｉｌｉｐｐｉｎｅｓ）については、
ｌｏｇ［αｉｓ，ｔｈｅ（Ｐｈｉｌｉｐｐｉｎｅｓ）］
＝ｌｏｇ［ｑ（ｔｈｅ）］＋ｌｏｇ｛ｍａｘ｛Ｉｔ｝［αＩｔ，ｉｓ（ｔｈｅ）］｝＋ｌｏｇ｛ｐ（Ｐｈｉｌｉｐｐｉｎｅｓ｜ｉｓ，ｔｈｅ）｝
＝０＋（−２）＋（−２）＝−４
【００４９】
そして、ノード番号５の単語「Ｌｕｚｏｎ」のノードに対する前向きスコアは次の通りである。
ｌｏｇ［αＩｔ，ｉｓ（Ｌｕｚｏｎ）］
＝ｌｏｇ［ｑ（ｉｓ）］＋ｌｏｇ｛ｍａｘ｛＜文頭＞｝［α＜文頭＞，Ｉｔ（ｉｓ）］｝＋ｌｏｇ｛ｐ（Ｌｕｚｏｎ｜Ｉｔ，ｉｓ）｝
＝０＋（−１）＋（−２）
＝−３
【００５０】
そして、ノード番号６の単語「Ｉｓｌａｎｄ」のノードに対する前向きスコアは次の通りである。
ｌｏｇ［αｉｓ，Ｌｕｚｏｎ（Ｉｓｌａｎｄ）］
＝ｌｏｇ［ｑ（Ｌｕｚｏｎ）］＋ｌｏｇ｛ｍａｘ｛Ｉｔ｝［αＩｔ，ｉｓ（Ｌｕｚｏｎ）］｝＋ｌｏｇ｛ｐ（Ｉｓｌａｎｄ｜ｉｓ，Ｌｕｚｏｎ）｝
＝（−３）＋（−３）＋（−２）＝−８
【００５１】
そして、ノード番号７の単語「Ｍｉｎｄａｎａｏ」のノードに対する前向きスコアは次の通りである。
ｌｏｇ［αＩｔ，ｉｓ（Ｍｉｎｄａｎａｏ）］
＝ｌｏｇ［ｑ（ｉｓ）］＋ｌｏｇ｛ｍａｘ｛＜文頭＞｝［α＜文頭＞，Ｉｔ（ｉｓ）］｝＋ｌｏｇ｛ｐ（Ｍｉｎｄａｎａｏ｜Ｉｔ，ｉｓ）｝
＝０＋（−１）＋（−３）＝−４
【００５２】
そして、ノード番号８の単語「ｉｓｌａｎｄ」のノードに対する前向きスコアは次の通りである。
ｌｏｇ［αｉｓ，Ｍｉｎｄａｎａｏ（ｉｓｌａｎｄ）］
＝ｌｏｇ［ｑ（Ｍｉｎｄａｎａｏ）］＋ｌｏｇ｛ｍａｘ｛Ｉｔ｝［αＩｔ，ｉｓ（Ｍｉｎｄａｎａｏ）］｝＋ｌｏｇ｛ｐ（ｉｓｌａｎｄ｜ｉｓ，Ｍｉｎｄａｎａｏ）｝
＝２＋（−４）＋（−３）＝−５
【００５３】
そして、ノード番号９の単語「＜文末＞」のノードに対する前向きスコアは、３つのパスそれぞれについて、次の通りである。
まず、第１のパス（ｔｈｅ−Ｐｈｉｌｉｐｐｉｎｅｓ−＜文末＞）については、
ｌｏｇ［αｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ（＜文末＞）］
＝ｌｏｇ［ｑ（Ｐｈｉｌｉｐｐｉｎｅｓ）］＋ｌｏｇ｛ｍａｘ｛＜文頭＞，ｉｓ｝［α＜文頭＞，ｔｈｅ（Ｐｈｉｌｉｐｐｉｎｅｓ），αｉｓ，ｔｈｅ（Ｐｈｉｌｉｐｐｉｎｅｓ）］｝＋ｌｏｇ｛ｐ（＜文末＞｜ｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ）｝
＝（−３）＋ｌｏｇ［ｍａｘ（０．１，０．０００１）］＋（−３）
＝（−３）＋（−１）＋（−３）＝−７
また、第２のパス（Ｌｕｚｏｎ−Ｉｓｌａｎｄ−＜文末＞）については、
ｌｏｇ［αＬｕｚｏｎ，Ｉｓｌａｎｄ（＜文末＞）］
＝ｌｏｇ［ｑ（Ｉｓｌａｎｄ）］＋ｌｏｇ｛ｍａｘ｛ｉｓ｝［αｉｓ，Ｌｕｚｏｎ（Ｉｓｌａｎｄ）］｝＋ｌｏｇ｛ｐ（＜文末＞｜Ｌｕｚｏｎ，Ｉｓｌａｎｄ）｝
＝（−３）＋（−８）＋（−３）＝−１４
また、第３のパス（Ｍｉｎｄａｎａｏ−ｉｓｌａｎｄ−＜文末＞）については、
ｌｏｇ［αＭｉｎｄａｎａｏ，ｉｓｌａｎｄ（＜文末＞）］
＝ｌｏｇ［ｑ（ｉｓｌａｎｄ）］＋ｌｏｇ｛ｍａｘ｛ｉｓ｝［αｉｓ，Ｍｉｎｄａｎａｏ（ｉｓｌａｎｄ）］｝＋ｌｏｇ｛ｐ（＜文末＞｜Ｍｉｎｄａｎａｏ，ｉｓｌａｎｄ）｝
＝２＋（−５）＋（−３）＝−６
【００５４】
次に、後向きスコア計算部５による後向きスコアの計算、および総合スコア計算部６による総合スコアの計算の詳細を説明する。
まず、後向きスコア計算部５は、後向きスコアを下の式（６）により計算する。
【００５５】
【数６】
2010191809.tif 000008
【００５６】
但し、単語ｅＩは「＜文末＞」である。
式（６）が表わしているように、ｉ番目のノード（単語ｅｉ）の後向きスコアは、単語ｅｉ−ｎ＋２からｅｉ＋１までの部分単語列に依存するものであり、当該ノードの単語ｅｉの重要度と、ひとつ後のノード（ノード番号ｉ＋１）の後向きスコアと、ｎグラムの値（ｅｉ＋１が出現する条件付確率）の積である。言い換えれば、ｉ番目のノードの後向きスコアは、文末（Ｉ番目のノード）から（ｉ＋１）番目のノードまでのｎグラムの値の総積と、文末から当該ノードまでの単語重要度の値の総積との積である。つまり、後向きスコア計算部５は、単なるｎグラムの積だけではなく、単語重要度を加味した後向きスコアを計算する。
【００５７】
なお、本実施形態はｎグラムとして３−グラムを用いるため、これに応じて上の式（６）を書き換えると、下の式（７）となる。
【００５８】
【数７】
2010191809.tif 000009
【００５９】
但し、本実施形態では、１０を底とする対数によるスコアの計算を行なうため、上の式（７）で表わした値そのものではなく、下の式（８）を計算する。なお、式（８）等において、対数の底の「１０」の表記を省略している。
【００６０】
【数８】
2010191809.tif 000010
【００６１】
また、総合スコア計算部６は、下の式（９）により総合スコアを計算する。
【００６２】
【数９】
2010191809.tif 000011
【００６３】
本実施形態はｎグラムとして３−グラムを用いるため、これに応じて式（９）を書き換えると、式（１０）となる。
【００６４】
【数１０】
2010191809.tif 000012
【００６５】
式（９）、式（１０）から明らかなように、ある単語列（解候補）の総合スコアは、その単語列の文頭から文末までのｎグラムの総積と、その単語列の文頭から文末までの単語重要度の総積との積である。総合スコアを対数により計算する場合は、総合スコアの対数は、その単語列の文頭から文末までのｎグラムの対数の総和と、その単語列の文頭から文末までの単語重要度の対数の総和との和である。これらを式で表わすと、下の式（１１）および式（１２）の通りである。
【００６６】
【数１１】
2010191809.tif 000013
【００６７】
【数１２】
2010191809.tif 000014
【００６８】
フローチャートを用いて説明した前述の手順の通り、後向きスコア計算部５は、文末から順に後向きスコアを計算する。
本実施形態では、上位解記憶部７は、総合スコアの上位２個の解を記憶する。この段階では、まだどのノードについても総合スコアが算出されていないため、上位解記憶部７が記憶するデータは、｛φ，φ｝である。ここで、「φ」は空（ヌル）を表わす。
【００６９】
まず、ノード番号９の「＜文末＞」のノードに対して、後向きスコア計算部５は、次のように後向きスコアを計算する。
その前のノードの単語ｅｉ−１が「Ｐｈｉｌｉｐｐｉｎｅｓ」の場合には、後向きスコアは、式（８）により、次の通りである。
ｌｏｇ［βＰｈｉｌｉｐｐｉｎｅｓ（＜文末＞）］
＝ｌｏｇ［β＜文末＞（＃）］＋ｌｏｇ［ｐ（＃｜Ｐｈｉｌｉｐｐｉｎｅｓ，＜文末＞）］＋ｌｏｇ｛ｑ（＜文末＞）｝
＝０＋０＋０＝０
なお、前向きスコアの計算のときと同様に、「＃」はダミーの単語である。
【００７０】
従って、前の単語が「Ｐｈｉｌｉｐｐｉｎｅｓ」の場合の、単語「＜文末＞」のノードの総合スコア（これを総合スコア［０１］とする）は、式（１０）により、次の通りである。
ｌｏｇ［ｑ（＜文頭＞，ｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ，＜文末＞）］
＝ｌｏｇ［αｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ（＜文末＞）］＋ｌｏｇ［βＰｈｉｌｉｐｐｉｎｅｓ（＜文末＞）］
＝（−７）+０＝−７  ・・・  総合スコア［０１］
なお、この計算において、総合スコア計算部６は、前向きスコア記憶部４から前向きスコアｌｏｇ［αｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ（＜文末＞）］のちを読み出して利用している。以下の計算においても同様に、総合スコア計算部６は、前向きスコア記憶部４から読み出した値を利用する。
【００７１】
上位解記憶部７が記憶するデータは｛φ，φ｝であったため、総合スコア計算部６は、総合スコア［０１］の計算結果を用いて、上位解記憶部７を書き換える。その結果、上位解記憶部７のデータは、｛［０１，−７］，φ｝となる。ここで、「０１」は、上記の通り、前の単語が「Ｐｈｉｌｉｐｐｉｎｅｓ」の場合の単語「＜文末＞」のノードの総合スコアが格納されていることを表わすものである。また、「−７」は、その総合スコアである。
【００７２】
また、ノード番号９の「＜文末＞」のノードに関して、前のノードの単語ｅｉ−１が「Ｉｓｌａｎｄ」の場合の後向きスコアは、次の通りである。
ｌｏｇ［βＩｓｌａｎｄ（＜文末＞）］
＝ｌｏｇ［β＜文末＞（＃）］＋ｌｏｇ［ｐ（＃｜Ｉｓｌａｎｄ，＜文末＞）］＋ｌｏｇ｛ｑ（＜文末＞）｝
＝０＋０＋０＝０
従って、前の単語が「Ｉｓｌａｎｄ」の場合の、単語「＜文末＞」のノードの総合スコア（総合スコア［０２］とする）は、同様に、次の通りである。
ｌｏｇ［ｑ（＜文頭＞，Ｌｕｚｏｎ，Ｉｓｌａｎｄ，＜文末＞）］
＝ｌｏｇ［αＬｕｚｏｎ，Ｉｓｌａｎｄ（＜文末＞）］＋ｌｏｇ［βＩｓｌａｎｄ（＜文末＞）］
＝（−１４）+０＝−１４  ・・・  総合スコア［０２］
【００７３】
この総合スコア［２］の算出結果に従い、総合スコア算出部６は、上位解記憶部７を書き換える。その結果、上位解記憶部７のデータは、｛［０１，−７］，［０２，−１４］｝となる。
【００７４】
また、ノード番号９の「＜文末＞」のノードに関して、前のノードの単語ｅｉ−１が「ｉｓｌａｎｄ」の場合の後向きスコアは、次の通りである。
ｌｏｇ［βｉｓｌａｎｄ（＜文末＞）］
＝ｌｏｇ［β＜文末＞（＃）］＋ｌｏｇ［ｐ（＃｜ｉｓｌａｎｄ，＜文末＞）］＋ｌｏｇ｛ｑ（＜文末＞）｝
＝０＋０＋０＝０
【００７５】
従って、前の単語が「ｉｓｌａｎｄ」の場合の、単語「＜文末＞」のノードの総合スコア（総合スコア［０３］とする）は、同様に、次の通りである。
ｌｏｇ［ｑ（＜文頭＞，Ｍｉｎｄａｎａｏ，ｉｓｌａｎｄ，＜文末＞）］
＝ｌｏｇ［αＭｉｎｄａｎａｏ，Ｉｓｌａｎｄ（＜文末＞）］＋ｌｏｇ［βｉｓｌａｎｄ（＜文末＞）］
＝（−６）+０＝−６  ・・・  総合スコア［０３］
【００７６】
この総合スコア［３］の算出結果に従い、総合スコア算出部６は、上位解記憶部７を書き換える。その結果、上位解記憶部７のデータは、｛［０３，−６］，［０１，−７］｝となる。
つまり、総合スコア［０２］が上位解の２個から外れたため、［０２，−１４］のデータが上位解記憶部７から削除された。また、この総合スコア［０２］に対応する単語列「−Ｉｓｌａｎｄ−＜文末＞」はノード終了となる。
さらに隣接ノードへ移って、以下では、単語列探索装置１０１は、単語「Ｐｈｉｌｉｐｐｉｎｅｓ」と単語「ｉｓｌａｎｄ」のそれぞれについて後向きスコアおよび総合スコアの算出を行なう。しかしながら上記の通り、総合スコア［０２］に対応する単語列はノード終了となっているため、単語「Ｉｓｌａｎｄ」およびそこから先の処理は行なわれなくなる。
【００７７】
次に、ノード番号４の「Ｐｈｉｌｉｐｐｉｎｅｓ」のノードに関して、後向きスコアは、次の通りである。
ｌｏｇ［βｔｈｅ（Ｐｈｉｌｉｐｐｉｎｅｓ）］
＝ｌｏｇ［βＰｈｉｌｉｐｐｉｎｅｓ（＜文末＞）］＋ｌｏｇ［ｐ（＜文末＞｜ｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ）］＋ｌｏｇ｛ｑ（Ｐｈｉｌｉｐｐｉｎｅｓ）｝
＝０＋（−３）＋（−３）＝−６
ノード番号４のノードに関しては、パスに応じた２種類の前向きスコアが算出されているため、総合スコア計算部６は、そのそれぞれについて総合スコアを計算する。
【００７８】
まず、第１のパス（＜文頭＞−ｔｈｅ−Ｐｈｉｌｉｐｐｉｎｅｓ）については、総合スコア（総合スコア［０４］とする）は次の通りである。
ｌｏｇ［ｑ（＜文頭＞，ｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ，＜文末＞）］
＝ｌｏｇ［α＜文頭＞，ｔｈｅ（Ｐｈｉｌｉｐｐｉｎｅｓ）］＋ｌｏｇ［βｔｈｅ（Ｐｈｉｌｉｐｐｉｎｅｓ）］
＝（−１）＋（−６）＝−７  ・・・  総合スコア［０４］
この結果に従い、総合スコア算出部６は、上位解記憶部７の中の［０１，−７］を［０４，−７］で置き換える。これにより上位解記憶部７のデータは、｛［０３，−６］，［０４，−７］｝となる。
【００７９】
また、第２のパス（ｉｓ−ｔｈｅ−Ｐｈｉｌｉｐｐｉｎｅｓ）については、総合スコア（総合スコア［０５］とする）は次の通りである。
ｌｏｇ［ｑ（＜文頭＞，ｉｓ，ｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ，＜文末＞）］
＝ｌｏｇ［αｉｓ，ｔｈｅ（Ｐｈｉｌｉｐｐｉｎｅｓ）］＋ｌｏｇ［βｔｈｅ（Ｐｈｉｌｉｐｐｉｎｅｓ）］
＝（−４）＋（−６）＝−１０  ・・・  総合スコア［０５］
計算された総合スコア［０５］は、上位２個の解には入らないため、単語列探索装置１０１は、総合スコア［０５］に対応する単語列をノード終了とする。よって、「−ｉｓ−ｔｈｅ−Ｐｈｉｌｉｐｐｉｎｅｓ−＜文末＞」の単語列については、単語「ｔｈｅ」およびそこから先の処理は行なわれない。
そして、このとき、上位解記憶部７のデータは、｛［０３，−６］，［０４，−７］｝のまま維持される。
【００８０】
次に、ノード番号８の「ｉｓｌａｎｄ」のノードに関して、後向きスコアは、次の通りである。
ｌｏｇ［βＭｉｎｄａｎａｏ(ｉｓｌａｎｄ)］
＝ｌｏｇ［βｉｓｌａｎｄ（＜文末＞）］＋ｌｏｇ[ｐ（＜文末＞｜Ｍｉｎｄａｎａｏ，ｉｓｌａｎｄ）]＋ｌｏｇ［ｑ（ｉｓｌａｎｄ）］
＝０＋（−３）＋２＝−１
【００８１】
従って、単語「ｉｓｌａｎｄ」のノードの総合スコア（総合スコア［０６］とする）は、次の通りである。
ｌｏｇ［ｑ（＜文頭＞，ｉｓ，Ｍｉｎｄａｎａｏ，ｉｓｌａｎｄ，＜文末＞）］
＝ｌｏｇ［αｉｓ，Ｍｉｎｄａｎａｏ（ｉｓｌａｎｄ）］＋ｌｏｇ［βＭｉｎｄａｎａｏ(ｉｓｌａｎｄ)］
=（−５）＋（−１）＝−６  ・・・  総合スコア［０６］
この結果に従い、総合スコア算出部６は、上位解記憶部７の中の［０３，−６］を［０６，−６］で置き換える。これにより上位解記憶部７のデータは、｛［０６，−６］，［０４，−７］｝となる。
【００８２】
次に、ノード番号７の「Ｍｉｎｄａｎａｏ」のノードに関して、後向きスコアは、次の通りである。
ｌｏｇ［βｉｓ（Ｍｉｎｄａｎａｏ）］
=ｌｏｇ［βＭｉｎｄａｎａｏ（ｉｓｌａｎｄ）］＋ｌｏｇ［ｐ（ｉｓｌａｎｄ｜ｉｓ，Ｍｉｎｄａｎａｏ）］＋ｌｏｇ［ｑ（Ｍｉｎｄａｎａｏ）］
＝（−１）＋（−３）＋２＝−２
【００８３】
従って、単語「Ｍｉｎｄａｎａｏ」のノードの総合スコア（総合スコア［０７］とする）は、次の通りである。
ｌｏｇ［ｑ（＜文頭＞，Ｉｔ，ｉｓ，Ｍｉｎｄａｎａｏ，ｉｓｌａｎｄ，＜文末＞）］
＝ｌｏｇ［αＩｔ, ｉｓ（Ｍｉｎｄａｎａｏ）］＋ｌｏｇ［βｉｓ（Ｍｉｎｄａｎａｏ）］
＝（−４）＋（−２）＝−６  ・・・  総合スコア［０７］
この結果に従い、総合スコア算出部６は、上位解記憶部７の中の［０６，−６］を［０７，−６］で置き換える。これにより上位解記憶部７のデータは、｛［０７，−６］，［０４，−７］｝となる。
【００８４】
次に、ノード番号２の「ｉｓ」のノードに関して、「ｉｓ−Ｍｉｎｄａｎａｏ−ｉｓｌａｎｄ−＜文末＞」のパスでの後向きスコアは、次の通りである。
ｌｏｇ［βＩｔ（ｉｓ）］
＝ｌｏｇ［βｉｓ（Ｍｉｎｄａｎａｏ）］＋ｌｏｇ［ｐ（Ｍｉｎｄａｎａｏ|Ｉｔ，ｉｓ）］＋ｌｏｇ［ｑ（ｉｓ）］
＝（−２）＋（−３）＋０＝−５
【００８５】
従って、単語「ｉｓ」のノードの総合スコア（総合スコア［０８］とする）は、次の通りである。
ｌｏｇ［ｑ（＜文頭＞，Ｉｔ，ｉｓ，Ｍｉｎｄａｎａｏ，ｉｓｌａｎｄ，＜文末＞）］
＝ｌｏｇ［α＜文頭＞，Ｉｔ（ｉｓ）］＋ｌｏｇ［βＩｔ（ｉｓ）］
＝（−１）＋（−５）＝−６  ・・・  総合スコア［０８］
この結果に従い、総合スコア算出部６は、上位解記憶部７の中の［０７，−６］を［０８，−６］で置き換える。これにより上位解記憶部７のデータは、｛［０８，−６］，［０４，−７］｝となる。
【００８６】
以降の処理についての詳細な説明は省略する。
なお、図７は、上記の後向きの探索と総合スコアの算出に関する理解を容易にするための概略図であり、図３に示した単語グラフ上において［０１］から［１０］までの各総合スコアに対応する位置を示したものである。また、同図において、破線の矢印は、後向きの探索の際の依存関係を示している。例えば、［０７］に対応する単語列「Ｉｔ−ｉｓ−Ｍｉｎｄａｎａｏ−ｉｓｌａｎｄ−＜文末＞」は、［０６］に対応する単語列「ｉｓ−Ｍｉｎｄａｎａｏ−ｉｓｌａｎｄ−＜文末＞」に依存しており、これはさらに［０３］に対応する単語列「Ｍｉｎｄａｎａｏ−ｉｓｌａｎｄ−＜文末＞」に依存している。
【００８７】
ノード番号が０のノードまで、後向きスコアおよび総合スコアの計算が完了した後、最終的に、総合スコアが上位２個の解が上位解記憶部７に書き込まれた状態で残る。上述した例では、１位の解として単語列｛＜文頭＞，Ｉｔ，ｉｓ，Ｍｉｎｄａｎａｏ，ｉｓｌａｎｄ，＜文末＞｝とその総合スコア「−６」が上位解記憶部７に記憶されている。また、２位の解として単語列｛＜文頭＞，ｔｈｅ，Ｐｈｉｌｉｐｐｉｎｅｓ，＜文末＞｝とその総合スコア「−７」が上位解記憶部７に記憶されている。
これら上位解記憶部７に記憶されているデータは、前述の手順におけるステップＳ９で、出力端子経由で出力される。
【００８８】
［第２の実施の形態］
図８は、第２の実施形態による単語列探索装置の機能構成を示すブロック図である。図示するように、本実施形態による単語列探索装置１０２は、単語ｎグラム記憶部１と、単語重要度記憶部２と、単語グラフ記憶部８と、前向きスコア計算部３と、前向きスコア記憶部４と、後向きスコア計算部５と、総合スコア計算部６と、上位解記憶部７に加えて、更に、入力文記憶部（言語Ａ）２１と、用例文記憶部（言語Ａ・Ｂ）２２と、解候補作成部２３と、単語重要度算出部２４とを含んで構成される。
なお、第１の実施形態において説明した事項についてはここでは説明を省略し、本実施形態特有の構成および動作等について以下で説明していく。
【００８９】
入力文記憶部２１と、用例文記憶部２２とは、例えば半導体メモリや磁気ハードディスク装置などの記憶手段を用いて実現される。また、解候補作成部２３と、単語重要度算出部２３とは、例えば、二値論理を扱う電子回路を用いて実現される。
【００９０】
入力文記憶部２１には、予め、自然言語による文を記憶させておく。ここで、入力文記憶部２１が記憶する文は、言語Ａ（第１言語：例えば日本語であるが、これに限定されない）で書かれているものである。用例文記憶部２２は、予め、自然言語による大量の用例文のペアを記憶させておく。用例文記憶部２２が記憶する文は、言語Ａで書かれた文と言語Ｂ（第２言語：例えば英語であるが、これに限定されない）で書かれた文のペアであり、この文のペアは互いに対訳となっている。
【００９１】
解候補作成部２３は、入力文記憶部２１に記憶されている言語Ａによる入力文のうちの一文を読み込むと、用例文記憶部２２に記憶されている大量の用例文のペアのうちの言語Ａで書かれた文を検索し、入力文と用例文との間の単言語内類似度を計算することによって、入力文のすべての単語を被覆するように類似用例を収集する。ここで、単言語類似度とは、入力文（言語Ａ）と用例文ペアのうちの言語Ａ（原言語）側との類似度であり、用例翻訳（ＳＤＭＴ，Similarity-Driven Machine Translation）一般によく使われるものである。
図９は、「ミンダナオ島の東の太平洋で熱帯低気圧が台風１号になりました」という入力文（言語Ａ）に対して、上述した処理によって、解候補作成部２３が収集した用例文のペアの集合の例を示す概略図である。図示するように、ここでは、３つのペアの用例文が収集されている。
【００９２】
解候補作成部２３は、次に、上の処理で収集された用例文における言語Ｂ（目的言語）側の単語を、マルチプルアライメント処理により整列させ、単語グラフを作成する。
図１０は、図９で示した用例文のペアのうちの言語Ｂの側の３つの文を基に、上述した処理によって、解候補作成部２３が作成した単語グラフの一例である。図示するように、言語Ｂによる３文がアライメントされている。
解候補作成部２３は、このように作成された単語グラフのデータを、解候補として、単語グラフ記憶部８に書き込む。
【００９３】
次に、単語重要度算出部２４は、入力文記憶部２１から言語Ａによる入力文を読み出し、その入力文および単語辞書データ（不図示）に基づき、言語Ｂの単語の重要度を算出する。単語重要度算出部２４は、言語Ｂの単語ｅｉについての重要度ｌｏｇ｛ｑ（ｅｉ）｝を下の式（１３）により計算する。なお、対数の底は１０である。
【００９４】
【数１３】
2010191809.tif 000015
【００９５】
ここで、ｑ１は所定の正定数（例えば２）であり、ｑ２は所定の負定数（例えば−３）である。また、ｊｉは、単語ｅｉに対応する言語Ａの単語である。単語ｊｉと単語ｅｉの関係は、前記の単語辞書データを参照することにより得られる。また、ｓＪは、言語Ａによる前記入力文である。
つまり、単語ｅｉが所定のクラスに属する単語であり、且つ単語ｅｉの訳語である単語ｊｉが入力文ｓＪに含まれる場合には、重要度ｌｏｇ｛ｑ（ｅｉ）｝は正の値ｑ１となり、これは単語ｅｉの重要性として正方向（加点方向）に作用する。また、単語ｅｉが前記所定のクラスに属する単語であり、且つ単語ｅｉの訳語である単語ｊｉが入力文ｓＪに含まれない場合には、重要度ｌｏｇ｛ｑ（ｅｉ）｝は負の値ｑ２となり、これは単語ｅｉの重要性として負方向（減点方向）に作用する。また、単語ｅｉが前記所定のクラスに属すさない場合（式（１３）におけるotherwise）、重要度ｌｏｇ｛ｑ（ｅｉ）｝は０となり、これは単語ｅｉの重要性として中立である。
なおここで、上記の「所定のクラス」とは、例えば、固有名詞や数量表現の固有表現のみに用いられる単語のクラスである。
【００９６】
そして、単語重要度２４は、上述した方法で算出した単語重要度のデータを、単語重要度記憶部２に書き込む。
【００９７】
なお、単語ｎグラム記憶部１には、第１の実施形態の場合と同様に、統計に基づくｎグラムのデータが予め書き込まれている。
このように単語ｎグラム記憶部１と単語重要度２と単語グラフ記憶部８にデータが書き込まれている状態で、前向きスコア計算部３と、後向きスコア計算部４と、総合スコア計算部６は、第１の実施形態の場合と同様に処理を行なう。その結果、上位解記憶部７には、入力文ｓＪの訳文として相応しい、つまり総合スコアの高い上位の所定個数の解（言語Ｂによる単語列）が記憶される状態となる。よって、単語列探索装置１０２は、入力文ｓＪの言語Ｂへの訳文の解候補のうちスコアの高いものを出力することができる。
【００９８】
本実施形態による単語探索装置１０２は、用例翻訳の処理における解候補の精度を上げる。その理由は次の通りである。
仮に本実施携帯を用いない場合には、まず言語モデル（ｎグラム）で解候補のＮベストを求め、次にその各各候補に対して二言語間類似度を計算し、両者を考慮して最適解を求める方法が考えられるが、このように言語モデルを先に適用して解候補を求めてしまうと、必要な訳語が解候補に入りにくいという問題が生じる。
それに対して、本実施形態による単語探索装置１０２は、言語モデルを適用する際に、原言語（言語Ａ）側からの情報、即ち、単語重要度の情報を与えているために、解として必要な単語が、解候補のＮベストに残りやすくなる。例えば、入力文に含まれる「ミンダナオ島」という表現の訳語として「Ｍｉｎｄａｎａｏ」および「ｉｓｌａｎｄ」に高い重要度が与えられ、その結果、翻訳の精度が上がる。
【００９９】
＜翻訳実験の結果＞
本実施形態による単語列探索装置１０２を用いて用例翻訳による日英翻訳の実験を行った結果を記す。対訳用例コーパス（用例文記憶部２２に記憶させるデータ）としては、ＮＨＫの日本語ニュース（言語Ａ）の中から気象・災害に関する記事を選択し、これらを人（翻訳者）が英訳して得られた文（言語Ｂ）を用いた。ここで、対訳用例は２４，４２９文であり、評価文は４１文である。そして、単語列探索装置１０２による出力結果を、最もよく使われている自動評価指標ＢＬＥＵ（参考文献：Kishore Papineniet他，「BLEU: a Method for Automatic Evaluation of Machine Translation.」，Procs. of ACL2002, pp.311-318, 2002.）で評価した。なお、ＢＬＥＵで利用した正解訳は1文のみである。また、この実験では、言語モデルには５−グラムを用い、その際Ｎ＝５０００としてＮベスト解を得た。そして、前記の式（１３）におけるｑ１およびｑ２を、パラメータとして変化させて実験を行った。
【０１００】
まず、それぞれのパラメータが単独でＢＬＥＵの改善に寄与するか否かを見るために、ｑ２＝０としてｑ１を変化させた場合と、ｑ１＝０としてｑ２を変化させた場合について、実験した。その結果、ｑ２＝０の場合にはｑ１＝５．０のときにＢＬＥＵ＝０．２６７７と最も高く、ｑ１を大きくすると逆にＢＬＥＵの値が低くなる傾向があることがわかった。一方、ｑ１＝０の場合には、ｑ２を小さくするとＢＬＥＵが向上する傾向があり、ｑ２＝−１０００．０のときにＢＬＥＵ＝０．２６３４と最も高く、それよりも小さい値ではほぼ一定となっている。
【０１０１】
次に、前の実験でＢＬＥＵの最高値が得られたパラメータｑ１＝５．０及びｑ２＝−１０００．０に対して、今度はそれぞれパラメータｑ２、ｑ１を変化させて実験を行なった。その結果、ｑ１を変化させた場合にはｑ２＝−１０００．０に対してｑ1＝４．０のときにＢＬＥＵ＝０．２７５８と最も高く、一方でｑ２を変化させた場合にはｑ１＝５．０に対してｑ２＝−５００．０のときにＢＬＥＵ＝０．２７５２と最も高い。つまり、このあたりにパラメータｑ１およびｑ２の最適値が存在すると推測される。なお、ベースライン（ｑ１＝ｑ２＝０）のときはＢＬＥＵ＝０．２４６７であるので、いずれの場合もＢＬＥＵ値が改善されており、本実施形態による構成の有効性が示されている。
【０１０２】
なお、上述した実施形態における単語列探索装置の一部又は全部の機能をコンピュータで実現するようにしても良い。その場合、この制御機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現しても良い。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時刻の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時刻プログラムを保持しているものも含んでも良い。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【０１０３】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
各実施形態では、ｎグラムとして３−グラムを用いる形態を具体的に説明した（但し、前述の実験では５−グラムを用いた）が、２−グラム、４−グラム、５−グラム、６−グラム等、任意のｎグラムを用いて、同様の処理を行なうようにしても良い。
また、単語グラフ記憶部や、単語ｎグラム記憶部や、単語重複度記憶部に記憶する各テーブルには、単語を直接格納する形態を説明したが、テーブルに単語そのものを格納する代わりに、単語の種類をユニークに識別する情報（番号など）を格納するようにしても良い。
また、各実施形態では、前向きスコア、後向きスコア、総合スコアのそれぞれについて、対数を取って計算を行なったが、対数を取らずに各スコアの値を計算してもよい。
【産業上の利用可能性】
【０１０４】
機械翻訳や音声認識や形態素解析など、所与の単語グラフから最適な単語列候補を探索する過程を含む自然言語処理に広く利用することができる。
【符号の説明】
【０１０５】
１  単語ｎグラム記憶部
２  単語重要度記憶部
３  前向きスコア計算部
４  前向きスコア記憶部
５  後向きスコア計算部
６  総合スコア計算部
７  上位解記憶部
８  単語グラフ記憶部
２１  入力文記憶部
２２  用例文記憶部
２３  解候補作成部
２４  単語重要度算出部
１０１，１０２  単語列探索装置
【図１】
2010191809.tif 000016
【図２】
2010191809.tif 000017
【図３】
2010191809.tif 000018
【図４】
2010191809.tif 000019
【図５】
2010191809.tif 000020
【図６】
2010191809.tif 000021
【図７】
2010191809.tif 000022
【図８】
2010191809.tif 000023
【図９】
2010191809.tif 000024
【図１０】
2010191809.tif 000025