(57)【要約】【課題】グラフにおけるノードの通過回数を安定に求め、かつ、通過回数を決定する処理の処理時間を低減する。【解決手段】ノード通過回数決定装置１０は、有向グラフと各ノードに与えられた最小通過回数とを受け付ける入力部３０と、有向グラフの分岐の開始を判定する分岐開始判定部５１と、有向グラフの分岐のマージを判定する分岐マージ判定部５２と、有向グラフの分岐状態と最小通過回数とに基づいてルートノードの通過回数を最小にするように各ノードの通過回数を始点から終点に向けて逐次的に暫定値として決定し、ルートノードの通過回数を確定するルートノード通過回数決定部５３と、分岐前後の差分値を共用通過回数として記憶部４０に保持して管理する共用通過回数管理部５５と、有向グラフの分岐状態と通過回数の暫定値とルートノードの通過回数とに基づいて各ノードの通過回数を終点から始点に向けて逐次的に確定するトレースバック部５６とを備える。【選択図】図２
2010033461.tif 000002
【特許請求の範囲】
【請求項１】
グラフのルートノードを示す始点と前記グラフの単独の終点との間を中継する複数のノードと前記ノード間において分岐および合流が可能なエッジとから構成された構造のグラフであって、前記グラフの構造を維持したまま始点から終点までを接続する経路においてノードで示される内容を置換して各ノードを接続するときに各ノードをそれぞれ通過する回数の最小値を示す最小通過回数が各ノードに与えられた有向グラフに対して、前記ルートノードの通過回数と各ノードの通過回数とを決定するノード通過回数決定装置において、
前記有向グラフと当該有向グラフにおける各ノードに与えられた最小通過回数との入力を受け付ける入力手段と、
前記入力された有向グラフと前記各ノードに与えられた最小通過回数とを記憶する記憶手段と、
前記入力された有向グラフの構造を解析して当該有向グラフにおける分岐の開始を判定する分岐開始判定手段と、
前記入力された有向グラフの構造を解析して当該有向グラフにおける分岐のマージを判定する分岐マージ判定手段と、
前記分岐開始判定手段の判定結果と、前記分岐マージ判定手段の判定結果とから得られる前記有向グラフにおける始点から終点に向けての分岐の状態と、前記入力された有向グラフにおける各ノードに与えられた最小通過回数とに基づいて、前記ルートノードの通過回数を最小にするように各ノードの通過回数を前記有向グラフの始点から終点に向けて逐次的に暫定的な値として決定し、前記終点において決定した暫定的な値を前記ルートノードの通過回数として確定するルートノード通過回数決定手段と、
前記有向グラフにおけるルートノードおよび各ノードに対して決定された通過回数を前記記憶手段に保持して管理するノード通過回数管理手段と、
前記有向グラフの始点から終点に向けての分岐において分岐前のノードの通過回数から分岐後の各ノードに与えられた最小通過回数の和を差し引いた差分値を、分岐後の各ノードおよび当該分岐のマージ前後に係る各ノードの暫定的な通過回数を決定するまで共用するための共用通過回数として前記記憶手段に保持し、前記共用通過回数の増減を管理する共用通過回数管理手段と、
前記分岐開始判定手段の判定結果と、前記分岐マージ判定手段の判定結果とから得られる前記有向グラフにおける終点から始点に向けての分岐の状態と、前記確定されたルートノードの通過回数と、前記暫定的な値として決定された各ノードの通過回数とに基づいて、前記有向グラフの終点の通過回数を前記ルートノードの通過回数と同じ値として、前記ルートノードの通過回数を最小値に維持しながら、各ノードの通過回数を前記有向グラフの終点から始点に向けて逐次的に確定するトレースバック手段と、
を備えることを特徴とするノード通過回数決定装置。
【請求項２】
前記ルートノード通過回数決定手段は、
前記有向グラフにおいて隣り合うノード間に始点から終点に向けての分岐がない場合に、始点側のノードの通過回数と終点側のノードの最小通過回数とを比較し、どちらか大きい方の値を、終点側のノードの通過回数として暫定的に決定し、終点側のノードに与えられた最小通過回数の方が大きく、かつ、前記記憶手段に当該隣り合うノードの始点側ノードに係る前記共用通過回数の値が１以上であれば、前記共用通過回数管理手段に対して、終点側のノードに与えられた最小通過回数から始点側のノードの通過回数を差し引いた差分だけ前記共用通過回数の値を減算するように指示し、
前記共用通過回数管理手段は、前記指示に従うことを特徴とする請求項１に記載のノード通過回数決定装置。
【請求項３】
前記ルートノード通過回数決定手段は、
前記有向グラフにおいて始点から終点に向けての分岐がある場合に、分岐後の各ノードに与えられた最小通過回数を、分岐後の各ノードの通過回数として暫定的に決定し、かつ、分岐前のノードの通過回数と分岐後のノードの通過回数の和とを比較し、分岐前のノードの通過回数の方が大きければ、前記共用通過回数管理手段に対して、分岐前のノードの通過回数から分岐後のノードの通過回数の和を差し引いた差分を当該分岐に係る前記共用通過回数として前記記憶手段に保持するように指示し、
前記共用通過回数管理手段は、前記指示に従うことを特徴とする請求項１または請求項２に記載のノード通過回数決定装置。
【請求項４】
前記ルートノード通過回数決定手段は、
前記有向グラフにおいて始点から終点に向けてのマージがある場合に、マージ前の各ノードの通過回数の和とマージ後のノードに与えられた最小通過回数とを比較し、
比較の結果、マージ前の各ノードの通過回数の和がマージ後のノードに与えられた最小通過回数よりも小さければ、マージ後のノードに与えられた最小通過回数をマージ後のノードの通過回数として暫定的に決定し、
比較の結果、マージ前の各ノードの通過回数の和がマージ後のノードに与えられた最小通過回数以上であれば、マージ前の各ノードの通過回数の和をマージ後のノードの通過回数として暫定的に決定すると共に、マージ前の各ノードにおいて前記共用通過回数が共用されていた場合には当該共用されている共用通過回数を削除するように前記共用通過回数管理手段に対して指示し、
前記共用通過回数管理手段は、前記指示に従うことを特徴とする請求項１ないし請求項３のいずれか一項に記載のノード通過回数決定装置。
【請求項５】
前記トレースバック手段は、
前記有向グラフにおいて隣り合うノード間に終点から始点に向けての分岐がない場合に、終点側のノードの通過回数を確定し、前記確定した終点側の通過回数と同じ値を始点側のノードの通過回数として確定し、
前記有向グラフにおいて終点から始点に向けての分岐がある場合に、分岐前のノードの通過回数を確定し、前記確定した分岐前の通過回数を、分岐後の各ノードの暫定的な通過回数の和で除した比率を求め、前記求めた比率を、分岐後の各ノードの暫定的な通過回数に掛けた値を、分岐後の各ノードの通過回数として確定し、
前記有向グラフにおいて終点から始点に向けてのマージがある場合に、マージ前の各ノードの通過回数の和を、マージ後のノードの通過回数として確定する、
ことを特徴とする請求項１ないし請求項４のいずれか一項に記載のノード通過回数決定装置。
【請求項６】
グラフのルートノードを示す始点と前記グラフの単独の終点との間を中継する複数のノードと前記ノード間において分岐および合流が可能なエッジとから構成された構造のグラフであって、前記グラフの構造を維持したまま始点から終点までを接続する経路においてノードで示される内容を置換して各ノードを接続するときに各ノードをそれぞれ通過する回数の最小値を示す最小通過回数が各ノードに与えられた有向グラフに対して、前記ルートノードの通過回数と各ノードの通過回数とを決定するために、コンピュータを、
入力された有向グラフの構造を解析して当該有向グラフにおける分岐の開始を判定する分岐開始判定手段、
前記入力された有向グラフの構造を解析して当該有向グラフにおける分岐のマージを判定する分岐マージ判定手段、
前記分岐開始判定手段の判定結果と、前記分岐マージ判定手段の判定結果とから得られる前記有向グラフにおける始点から終点に向けての分岐の状態と、前記入力された有向グラフにおける各ノードに与えられた最小通過回数とに基づいて、前記ルートノードの通過回数を最小にするように各ノードの通過回数を前記有向グラフの始点から終点に向けて逐次的に暫定的な値として決定し、前記終点において決定した暫定的な値を前記ルートノードの通過回数として確定するルートノード通過回数決定手段、
前記有向グラフにおけるルートノードおよび各ノードに対して決定された通過回数を前記記憶手段に保持して管理するノード通過回数管理手段、
前記有向グラフの始点から終点に向けての分岐において分岐前のノードの通過回数から分岐後の各ノードに与えられた最小通過回数の和を差し引いた差分値を、分岐後の各ノードおよび当該分岐のマージ前後に係る各ノードの暫定的な通過回数を決定するまで共用するための共用通過回数として前記記憶手段に保持し、前記共用通過回数の増減を管理する共用通過回数管理手段、
前記分岐開始判定手段の判定結果と、前記分岐マージ判定手段の判定結果とから得られる前記有向グラフにおける終点から始点に向けての分岐の状態と、前記確定されたルートノードの通過回数と、前記暫定的な値として決定された各ノードの通過回数とに基づいて、前記有向グラフの終点の通過回数を前記ルートノードの通過回数と同じ値として、前記ルートノードの通過回数を最小値に維持しながら、各ノードの通過回数を前記有向グラフの終点から始点に向けて逐次的に確定するトレースバック手段、
として機能させるためのノード通過回数決定プログラム。
【請求項７】
音声合成装置が合成音声を生成するために用いる音声データを集めた音声合成用データベースを作成するために文章として読み上げられるテキストデータを示す音声合成用読上げ文章を生成する音声合成用読上げ文章生成装置であって、
請求項１ないし請求項５のいずれか一項に記載のノード通過回数決定装置と、
前記ノード通過回数決定装置に入力される有向グラフにおけるノードで示される内容としての語句のリストと、前記有向グラフと、前記ノード通過回数決定装置で決定された前記有向グラフにおけるルートノードおよび各ノードの通過回数の確定値とを入力として受け付け、前記有向グラフの各ノードに置換可能な語句を割り当て、前記割り当てられた語句を前記有向グラフの始点から終点に向けて接続することで前記音声合成用読上げ文章を構築する読上げ文章構築装置と、
を備えることを特徴とする音声合成用読上げ文章生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフのルートノードを示す始点とグラフの単独の終点との間にノードとエッジとを備えた有向グラフにおける各ノードのそれぞれの最小通過回数が決まっているときに、ルートノードの通過回数が最小となるときの各ノードの通過回数を決定するノード通過回数決定装置およびそのプログラムに関し、特に、有向グラフを音声合成用読上げ文章の構造を指定するときの情報として入力するノード通過回数決定装置およびそのプログラム、並びにノード通過回数決定装置を備えた音声合成用読上げ文章生成装置に関するものである。
【背景技術】
【０００２】
従来、ノードと、ノード間を接続するエッジとを備えたグラフにおけるノードの通過回数を決定する方法として、シンプレックス法を用いる決定方法が知られている（例えば、非特許文献１参照）。シンプレックス法では、条件式が一次関数もしくは一次不等式で記述でき、各未定数は正である場合において、目的関数（一次関数）を最小にする解を得ることができる。ここで、ノードの通過回数とは、グラフにおけるノードとエッジの構造を維持したまま始点から単独の終点までを接続する経路においてノードで示される内容を置換して各ノードを接続するときに各ノードを通過する回数のことを指す。そして、始点から終点までを接続したときのグラフの内容が、例えば１つの文章（テキストデータ）を示す場合には、各ノードの内容は、例えば文節や単語を意味する。単純な具体例としては、「現在の  時刻は  ○○です」という文章の各文節をノードで表す場合に、「○○です」の文節の中で、「○○」を、「正午、午後１時、…、午前１１時」のように置換する場合には、「○○です」の文節を示すノードの通過回数「２４」をルートノードの通過回数にすることも可能である。
【０００３】
また、従来、このような文章（テキストデータ）として音声合成用の読上げ文章を生成する技術が知られている（特許文献１参照）。例えば、特許文献１に記載された音声合成用読上げテキストデータ作成装置は、音声合成装置が、ニュース原稿や株価等の数値を読み上げるための合成音声を生成するために用いる音声データを集めた音声合成用データベースを作成するために文章として読み上げられるテキストデータを入力として受け付ける。そして、この音声合成用読上げテキストデータ作成装置は、入力されたテキストデータを、音声合成する際に合成単位となる音声データ単位に分割して、文章を構成する音声データ単位の各部分の音声として読み上げられる部分的なテキストデータを選択的に生成することで音声合成用の読上げ文章を生成する。
【特許文献１】特開２００６−３０８９２号公報
【非特許文献１】William H. Press, et al. 、丹慶 勝市ほか訳、ニューメリカル・レシピ・イン・シー、”シンプレックス法”、技術評論社、1993、p.317−330
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、グラフにおけるノードの通過回数を決定する方法にシンプレックス法を採用する場合には、シンプレックス法では、条件式を必ず記述してから解を求めるため、処理に時間がかかってしまう。また、特許文献１に記載された音声合成用読上げテキストデータ作成装置は、音声合成用の読上げ文章を生成するためにグラフを利用するものではない。例えば、音声合成用の読上げ文章を生成するためにグラフを利用しようとするときには、比較的単純な構造のグラフが想定されるが、このような単純な構造のグラフにおけるノードの通過回数を決定する処理において、シンプレックス法を用いることなく処理時間を短縮することが要望されている。また、シンプレックス法では、解の収束性に関して全ての場合に保証されるものではないため、安定性にも問題がある。
【０００５】
本発明は、以上のような問題点に鑑みてなされたものであり、グラフにおけるノードの通過回数を解として安定に求め、かつ、通過回数を決定する処理の処理時間を低減することのできる技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、前記目的を達成するために創案されたものであり、まず、請求項１に記載のノード通過回数決定装置は、グラフのルートノードを示す始点と前記グラフの単独の終点との間を中継する複数のノードと前記ノード間において分岐および合流が可能なエッジとから構成された構造のグラフであって、前記グラフの構造を維持したまま始点から終点までを接続する経路においてノードで示される内容を置換して各ノードを接続するときに各ノードをそれぞれ通過する回数の最小値を示す最小通過回数が各ノードに与えられた有向グラフに対して、前記ルートノードの通過回数と各ノードの通過回数とを決定するノード通過回数決定装置において、入力手段と、記憶手段と、分岐開始判定手段と、分岐マージ判定手段と、ルートノード通過回数決定手段と、ノード通過回数管理手段と、共用通過回数管理手段と、トレースバック手段とを備えることとした。
【０００７】
かかる構成によれば、ノード通過回数決定装置は、入力手段によって、前記有向グラフと当該有向グラフにおける各ノードに与えられた最小通過回数との入力を受け付け、前記入力された有向グラフと前記各ノードに与えられた最小通過回数とを記憶手段に記憶する。そして、ノード通過回数決定装置は、分岐開始判定手段によって、前記入力された有向グラフの構造を解析して当該有向グラフにおける分岐の開始を判定し、分岐マージ判定手段によって、前記入力された有向グラフの構造を解析して当該有向グラフにおける分岐のマージを判定する。そして、ノード通過回数決定装置は、ルートノード通過回数決定手段によって、前記分岐開始判定手段の判定結果と、前記分岐マージ判定手段の判定結果とから得られる前記有向グラフにおける始点から終点に向けての分岐の状態と、前記入力された有向グラフにおける各ノードに与えられた最小通過回数とに基づいて、前記ルートノードの通過回数を最小にするように各ノードの通過回数を前記有向グラフの始点から終点に向けて逐次的に暫定的な値として決定し、前記終点において決定した暫定的な値を前記ルートノードの通過回数として確定する。これにより、ルートノードの通過回数を確定することができる。
【０００８】
また、かかる構成によれば、ノード通過回数決定装置は、ノード通過回数管理手段によって、前記有向グラフにおけるルートノードおよび各ノードに対して決定された通過回数を前記記憶手段に保持して管理する。また、ノード通過回数決定装置は、共用通過回数管理手段によって、前記有向グラフの始点から終点に向けての分岐において分岐前のノードの通過回数から分岐後の各ノードに与えられた最小通過回数の和を差し引いた差分値を、分岐後の各ノードおよび当該分岐のマージ前後に係る各ノードの暫定的な通過回数を決定するまで共用するための共用通過回数として前記記憶手段に保持し、前記共用通過回数の増減を管理する。そして、ノード通過回数決定装置は、トレースバック手段によって、前記分岐開始判定手段の判定結果と、前記分岐マージ判定手段の判定結果とから得られる前記有向グラフにおける終点から始点に向けての分岐の状態と、前記確定されたルートノードの通過回数と、前記暫定的な値として決定された各ノードの通過回数とに基づいて、前記有向グラフの終点の通過回数を前記ルートノードの通過回数と同じ値として、前記ルートノードの通過回数を最小値に維持しながら、各ノードの通過回数を前記有向グラフの終点から始点に向けて逐次的に確定する。これにより、ルートノード以外の各ノードの通過回数も確定できる。
【０００９】
また、請求項２に記載のノード通過回数決定装置は、請求項１に記載のノード通過回数決定装置において、前記ルートノード通過回数決定手段が、前記有向グラフにおいて隣り合うノード間に始点から終点に向けての分岐がない場合に、始点側のノードの通過回数と終点側のノードの最小通過回数とを比較し、どちらか大きい方の値を、終点側のノードの通過回数として暫定的に決定し、終点側のノードに与えられた最小通過回数の方が大きく、かつ、前記記憶手段に当該隣り合うノードの始点側ノードに係る前記共用通過回数の値が１以上であれば、前記共用通過回数管理手段に対して、終点側のノードに与えられた最小通過回数から始点側のノードの通過回数を差し引いた差分だけ前記共用通過回数の値を減算するように指示し、前記共用通過回数管理手段が、前記指示に従うこととした。
【００１０】
かかる構成によれば、ノード通過回数決定装置は、始点側のノードの通過回数と終点側のノードに与えられた最小通過回数のうち、どちらか大きい方の値を、終点側のノードの通過回数として暫定的に決定する。これにより、有向グラフにおいて隣り合うノード間に始点から終点に向けての分岐がない場合に、ルートノードの通過回数を最小にすることができる。また、ノード通過回数決定装置は、この隣り合うノードの始点側ノードに係る共用通過回数が保持されていれば、すなわち、第１の分岐後の隣り合うノード間に第２の分岐がない場合には、第１の分岐後の隣り合うノードの終点側のノードに与えられた最小通過回数の方が大きければ、その差分だけ共用通過回数の値を減算する。したがって、第１の分岐後のノードに隣り合う終点側のノードの通過回数を暫定的に決定したときに、第１の分岐後の分岐毎の各ノードの通過回数の暫定的な値に、暫定的な値を決定したときの共用通過回数を加算した値を、有向グラフにおいて第１の分岐後にマージするまで一定値として維持することができる。これにより、有向グラフにおいて第１の分岐後の隣り合うノード間に始点から終点に向けての第２の分岐がない場合に、ルートノードの通過回数を最小にすることができる。
【００１１】
また、請求項３に記載のノード通過回数決定装置は、請求項１または請求項２に記載のノード通過回数決定装置において、前記ルートノード通過回数決定手段が、前記有向グラフにおいて始点から終点に向けての分岐がある場合に、分岐後の各ノードに与えられた最小通過回数を、分岐後の各ノードの通過回数として暫定的に決定し、かつ、分岐前のノードの通過回数と分岐後のノードの通過回数の和とを比較し、分岐前のノードの通過回数の方が大きければ、前記共用通過回数管理手段に対して、分岐前のノードの通過回数から分岐後のノードの通過回数の和を差し引いた差分を当該分岐に係る前記共用通過回数として前記記憶手段に保持するように指示し、前記共用通過回数管理手段が、前記指示に従うこととした。
【００１２】
かかる構成によれば、ノード通過回数決定装置は、分岐後の各ノードに与えられた最小通過回数を、分岐後の各ノードの通過回数として暫定的に決定し、かつ、分岐前のノードの通過回数の方が分岐後のノードの通過回数の和よりも大きければ、その差分を、共用通過回数として記憶手段に保持することができる。したがって、この場合には、ノード通過回数決定装置は、有向グラフにおいて分岐後にマージするまでの間、共用通過回数を、分岐後の各ノード全体をまとめて管理したときの通過回数の余剰分として一括して管理することができる。これにより、この共用通過回数が分岐後にマージするまでの間に０以上の値を維持していれば、マージ後のノードの通過回数を、マージ前の各ノードの通過回数の和と同じ値にすることができる。また、この共用通過回数が分岐後にマージするまでの間に負の値に減少した場合には、マージ後のノードの通過回数は、分岐前のノードの通過回数よりも大きな値にすることができるので、負の値に減少した時点で共用通過回数を破棄することができる。
【００１３】
また、請求項４に記載のノード通過回数決定装置は、請求項１ないし請求項３のいずれか一項に記載のノード通過回数決定装置において、前記ルートノード通過回数決定手段が、前記有向グラフにおいて始点から終点に向けてのマージがある場合に、マージ前の各ノードの通過回数の和とマージ後のノードに与えられた最小通過回数とを比較し、比較の結果、マージ前の各ノードの通過回数の和がマージ後のノードに与えられた最小通過回数よりも小さければ、マージ後のノードに与えられた最小通過回数をマージ後のノードの通過回数として暫定的に決定し、比較の結果、マージ前の各ノードの通過回数の和がマージ後のノードに与えられた最小通過回数以上であれば、マージ前の各ノードの通過回数の和をマージ後のノードの通過回数として暫定的に決定すると共に、マージ前の各ノードにおいて前記共用通過回数が共用されていた場合には当該共用されている共用通過回数を削除するように前記共用通過回数管理手段に対して指示し、前記共用通過回数管理手段が、前記指示に従うこととした。
【００１４】
かかる構成によれば、ノード通過回数決定装置は、マージ前の各ノードの通過回数の和と、マージ後のノードに与えられた最小通過回数との大小関係に応じて、どちらか大きい方の値を、マージ後のノードの通過回数として暫定的に決定する。これにより、有向グラフにおいて始点から終点に向けてのマージがある場合に、ルートノードの通過回数を最小にすることができる。また、ノード通過回数決定装置は、マージ前に共用通過回数が保持されていれば、マージ後のノードの通過回数を暫定的に決定した後で、共用通過回数を削除するので、マージ後のノードの通過回数を暫定的に決定した後では、マージ前の各ノードに保持された暫定的な通過回数（その時点での最小通過回数）の和を振り返ってみれば、そのときには、共用通過回数の値を考慮しない分だけ、当該マージを生じせしめる各分岐が行われる以前のノードの暫定的な通過回数の値よりも小さいものとなる。したがって、トレースバックする際に、一括して管理していた共用通過回数を考慮するのではなく、マージ前の各ノードの通過回数（ただし各ノードはトレースバック時には分岐後の各ノードを示す）を、各ノードに保持された暫定的な最小通過回数に基づいて確定することが可能となる。
【００１５】
また、請求項５に記載のノード通過回数決定装置は、請求項１ないし請求項４のいずれか一項に記載のノード通過回数決定装置において、前記トレースバック手段が、前記有向グラフにおいて隣り合うノード間に終点から始点に向けての分岐がない場合に、終点側のノードの通過回数を確定し、前記確定した終点側の通過回数と同じ値を始点側のノードの通過回数として確定し、前記有向グラフにおいて終点から始点に向けての分岐がある場合に、分岐前のノードの通過回数を確定し、前記確定した分岐前の通過回数を、分岐後の各ノードの暫定的な通過回数の和で除した比率を求め、前記求めた比率を、分岐後の各ノードの暫定的な通過回数に掛けた値を、分岐後の各ノードの通過回数として確定し、前記有向グラフにおいて終点から始点に向けてのマージがある場合に、マージ前の各ノードの通過回数の和を、マージ後のノードの通過回数として確定することとした。
【００１６】
かかる構成によれば、ノード通過回数決定装置は、有向グラフの終点でルートノードの通過回数を確定した後、終点から始点に向けてトレースバックする際に、分岐がない場合には、終点側の通過回数と同じ値を始点側のノードの通過回数として確定する。また、ノード通過回数決定装置は、トレースバックする際に分岐がある場合には、分岐前の通過回数を分岐後の通過回数に比例配分できるように、分岐後の暫定的な通過回数に比率を掛ける。さらに、ノード通過回数決定装置は、トレースバックする際にマージがある場合に、マージ前の各ノードの通過回数の和を、マージ後のノードの通過回数として確定する。これにより、有向グラフにおいてルートノードの通過回数を最小にすると共に、ルートノード間を接続する各ノードの通過回数を確実に決定することができる。
【００１７】
また、請求項６に記載のノード通過回数決定プログラムは、グラフのルートノードを示す始点と前記グラフの単独の終点との間を中継する複数のノードと前記ノード間において分岐および合流が可能なエッジとから構成された構造のグラフであって、前記グラフの構造を維持したまま始点から終点までを接続する経路においてノードで示される内容を置換して各ノードを接続するときに各ノードをそれぞれ通過する回数の最小値を示す最小通過回数が各ノードに与えられた有向グラフに対して、前記ルートノードの通過回数と各ノードの通過回数とを決定するために、コンピュータを、分岐開始判定手段、分岐マージ判定手段、ルートノード通過回数決定手段、ノード通過回数管理手段、共用通過回数管理手段、トレースバック手段として機能させることとした。
【００１８】
かかる構成によれば、ノード通過回数決定プログラムは、分岐開始判定手段によって、入力された有向グラフの構造を解析して当該有向グラフにおける分岐の開始を判定し、分岐マージ判定手段によって、前記入力された有向グラフの構造を解析して当該有向グラフにおける分岐のマージを判定する。そして、ノード通過回数決定プログラムは、ルートノード通過回数決定手段によって、前記分岐開始判定手段の判定結果と、前記分岐マージ判定手段の判定結果とから得られる前記有向グラフにおける始点から終点に向けての分岐の状態と、前記入力された有向グラフにおける各ノードに与えられた最小通過回数とに基づいて、前記ルートノードの通過回数を最小にするように各ノードの通過回数を前記有向グラフの始点から終点に向けて逐次的に暫定的な値として決定し、前記終点において決定した暫定的な値を前記ルートノードの通過回数として確定する。そして、ノード通過回数決定プログラムは、ノード通過回数管理手段によって、前記有向グラフにおけるルートノードおよび各ノードに対して決定された通過回数を前記記憶手段に保持して管理し、共用通過回数管理手段によって、前記有向グラフの始点から終点に向けての分岐において分岐前のノードの通過回数から分岐後の各ノードに与えられた最小通過回数の和を差し引いた差分値を、分岐後の各ノードおよび当該分岐のマージ前後に係る各ノードの暫定的な通過回数を決定するまで共用するための共用通過回数として前記記憶手段に保持し、前記共用通過回数の増減を管理する。そして、ノード通過回数決定プログラムは、トレースバック手段によって、前記分岐開始判定手段の判定結果と、前記分岐マージ判定手段の判定結果とから得られる前記有向グラフにおける終点から始点に向けての分岐の状態と、前記確定されたルートノードの通過回数と、前記暫定的な値として決定された各ノードの通過回数とに基づいて、前記有向グラフの終点の通過回数を前記ルートノードの通過回数と同じ値として、前記ルートノードの通過回数を最小値に維持しながら、各ノードの通過回数を前記有向グラフの終点から始点に向けて逐次的に確定する。
【００１９】
また、請求項７に記載の音声合成用読上げ文章生成装置は、音声合成装置が合成音声を生成するために用いる音声データを集めた音声合成用データベースを作成するために文章として読み上げられるテキストデータを示す音声合成用読上げ文章を生成する音声合成用読上げ文章生成装置であって、請求項１ないし請求項５のいずれか一項に記載のノード通過回数決定装置と、読上げ文章構築装置とを備えることとした。
【００２０】
かかる構成によれば、音声合成用読上げ文章生成装置は、読上げ文章構築装置によって、前記ノード通過回数決定装置に入力される有向グラフにおけるノードで示される内容としての語句のリストと、前記有向グラフと、前記ノード通過回数決定装置で決定された前記有向グラフにおけるルートノードおよび各ノードの通過回数の確定値とを入力として受け付け、前記有向グラフの各ノードに置換可能な語句を割り当て、前記割り当てられた語句を前記有向グラフの始点から終点に向けて接続することで前記音声合成用読上げ文章を構築する。
【発明の効果】
【００２１】
請求項１または請求項６に係る発明によれば、有向グラフにおいて、始点から終点に向けて、各ノードに与えられた最小通過回数を利用してルートノードの通過回数を最小にするように各ノードの通過回数を暫定的に決定し、有向グラフの終点でルートノードの通過回数を確定した後、終点から始点に向けてトレースバックすることにより、各ノードでの通過回数を確定していくことができる。したがって、請求項１または請求項６に係る発明によれば、シンプレックス法のように条件式を記述する必要がなく、有向グラフにおけるノードの通過回数を解として安定に求め、かつ、通過回数を決定する処理の処理時間を低減することができる。
【００２２】
請求項２に係る発明によれば、始点側のノードの通過回数と終点側のノードに与えられた最小通過回数のうち、どちらか大きい方の値を、終点側のノードの通過回数として暫定的に決定することで、有向グラフにおいて隣り合うノード間に始点から終点に向けての分岐がない場合に、ルートノードの通過回数を最小にすることができる。したがって、ノード通過回数を決定するための処理時間を確実に低減できる。
【００２３】
請求項３に係る発明によれば、分岐前のノードの通過回数の方が分岐後のノードの通過回数の和よりも大きいときにその差分を共用通過回数として記憶手段に保持するので、この場合に共用通過回数を用いることで、有向グラフにおいて、始点から終点に向けて、各ノードに与えられた最小通過回数を利用してルートノードの通過回数を最小にするように各ノードの通過回数を暫定的に決定することができる。したがって、ノード通過回数を決定するための処理時間を確実に低減できる。
【００２４】
請求項４に係る発明によれば、マージ前の各ノードの通過回数の和と、マージ後のノードに与えられた最小通過回数との大小関係に応じて、どちらか大きい方の値を、マージ後のノードの通過回数として暫定的に決定することで、有向グラフにおいて、始点から終点に向けて、各ノードに与えられた最小通過回数を利用してルートノードの通過回数を最小にするように各ノードの通過回数を暫定的に決定することができる。したがって、ノード通過回数を決定するための処理時間を確実に低減できる。
【００２５】
請求項５に係る発明によれば、有向グラフの終点でルートノードの通過回数を最小にするように確定した後、トレースバックする際に、終点から始点へ向けての分岐の有無およびマージの有無に応じて、ルートノード間を接続する各ノードの通過回数を確定することができる。したがって、ノード通過回数を決定するための処理時間を確実に低減できる。
【００２６】
請求項７に係る発明によれば、音声合成用読上げ文章生成装置は、ノード通過回数決定装置を備えており、有向グラフと、ノードで示される内容としての語句のリストとを入力として受け付け、ルートノードおよび各ノードの通過回数の確定値とを決定したときに、有向グラフの各ノードに置換可能な語句を割り当てることで音声合成用読上げ文章を構築することができる。その結果、音声合成用読上げ文章生成装置は、有向グラフにおけるノードの通過回数を解として安定に求め、かつ、通過回数を決定する処理の処理時間を低減することができる。
【発明を実施するための最良の形態】
【００２７】
以下、図面を参照して本発明の実施形態に係るノード通過回数決定装置および音声合成用読上げ文章生成装置を実施するための最良の形態（以下「実施形態」という）について詳細に説明する。
【００２８】
［音声合成用データベース作成システム］
図１は、本発明の実施形態に係るノード通過回数決定装置を備えた音声合成用データベース作成システムを模式的に示す構成図である。
音声合成用データベース作成システム１は、音声合成用読上げ文章生成装置２と、音声合成用データベース作成装置４とを備えている。
【００２９】
（音声合成用読上げ文章生成装置）
音声合成用読上げ文章生成装置２は、音声合成装置６が合成音声を生成するために用いる音声データを集めた音声合成用データベース５を作成するために文章として読み上げられるテキストデータを示す音声合成用読上げ文章を生成するものであって、図１に示すように、ノード通過回数決定装置１０と、読上げ文章構築装置２０とを備えることとした。
【００３０】
ノード通過回数決定装置１０は、ノードとエッジとを備えた有向グラフと、その有向グラフにおけるノードに与えられた最小通過回数とを入力として受け付け、ノードにおける通過回数を決定し、読上げ文章構築装置２０に出力するものである。なお、詳細は後記する。
【００３１】
読上げ文章構築装置２０は、有向グラフの各ノードに置換可能な語句を割り当て、割り当てられた語句を有向グラフの始点から終点に向けて接続することで音声合成用読上げ文章（テキストデータ）を構築するものである。このために、読上げ文章構築装置２０は、ノード通過回数決定装置１０に入力される有向グラフにおけるノードで示される内容としての語句のリスト（テキストデータ）と有向グラフとを入力として受け付けると共に、ノード通過回数決定装置１０で決定されたノードにおける通過回数を取得する。構築された音声合成用読上げ文章（テキストデータ）を示す原稿は、図示しない表示装置やプリンタ等の出力装置により音声合成用読上げ文章生成装置２から出力される。
【００３２】
音声合成用データベース作成装置４は、音声合成用読上げ文章生成装置２で生成された原稿についての読み上げ音声をマイク３で受け付け、音声データを、音声合成用データベース５としてハードディスク等の図示しない記憶手段に記憶する。これにより、音声合成装置６は、例えば、合成音声を指定する音声合成用テキストデータの入力を受け付けたときに、音声合成用データベース５を参照して、指定された音声データを連結して合成音声をスピーカ７から出力することができる。
【００３３】
［ノード通過回数決定装置の構成］
図２は、本発明の実施形態に係るノード通過回数決定装置およびそれを備えた音声合成用読上げ文章生成装置の構成を模式的に示すブロック図である。
ノード通過回数決定装置１０は、最小通過回数が各ノードに与えられた有向グラフに対して、有向グラフのルートノードの通過回数と各ノードの通過回数とを決定するものであって、ＣＰＵ（Central Processing Unit）等の演算装置と、メモリ、ハードディスク等の記憶装置（記憶手段）と、マウスやキーボード等の外部から情報の入力を検出する入力装置と、インタフェース装置等を備えたコンピュータと、このコンピュータにインストールされたプログラムとから構成される。
【００３４】
（有向グラフ）
ここで、ノード通過回数決定装置１０に入力される有向グラフについて図３を参照して説明する。図３は、本発明の実施形態に係るノード通過回数決定装置に入力される有向グラフの説明図であって、（ａ）は有向グラフの構造の一例、（ｂ）は有向グラフのノードに割り当てられたテキストデータの一例をそれぞれ示している。有向グラフは、図３（ａ）に示すように、グラフのルートノードを示す始点（ＳＴＡＲＴノード）とグラフの単独の終点（ＥＮＤノード）との間を中継する複数のノードＮ１〜Ｎ１０と、ノードＮ間において分岐および合流が可能なエッジＥとから構成された構造のグラフである。有向グラフは一定の向きを有している。図３（ａ）においては、エッジＥの先の矢印で有向グラフの向きを表すことにして、ＳＴＡＲＴノード（始点）側を有向グラフの「前」、ＥＮＤノード（終点）側を有向グラフの「後」と呼ぶこととした。また、ルートノードを示すＳＴＡＲＴノードと有向グラフの単独の終点を示すＥＮＤノード以外は、単にノードと呼び、特に区別しない場合にはＮと表記する。なお、単にグラフと呼ぶ場合も有向グラフを指す。
【００３５】
図３（ａ）にｂで示す破線で囲まれた領域は、ノードの分岐を示している。すなわち、ノードＮ１の「後」には、ノードＮ２とノードＮ４とがそれぞれエッジＥを介してノードＮ１に隣り合って接続されている。以下、単に分岐という場合、ノードの分岐ｂを示す。なお、分岐数は、特に限定されるものではない。
【００３６】
図３（ａ）にｍで示す破線で囲まれた領域は、ノードのマージを示している。ノードＮ１０の「前」には、ノードＮ７とノードＮ９とがそれぞれエッジＥを介してノードＮ１０に隣り合って接続されている。以下、単にマージという場合、ノードのマージｍを示す。なお、マージ数は、マージに対応した分岐の数と同じである。
【００３７】
本実施形態では、有向グラフにおけるノードで示される内容は語句（テキストデータ）である。図３（ｂ）にノードで示される内容の一例を示す。ここでは、各ノードＮの形状をブロックで示した。図３（ｂ）に示す一例は、ラジオの気象通報で読み上げられるデータを想定したものである。各ノードＮに記載された語句は、有向グラフにおけるそのノードＮの位置に割り当てられる置換可能な語句の項目名を表している。例えば、ノードＮ１に記載された「場所の」という項目名に対応して、図４（ａ）のリストＬ１が予め用意されている。リストＬ１は、「日本海の」、「東シナ海の」、「太平洋の」等の場所に関連する語句を格納する。同様に、ノードＮ４に記載された「緯度分」という項目名に対応して、図４（ｂ）のリストＬ４が予め用意されている。リストＬ４は、「北緯０度」、「北緯１度」、「南緯９０度」等の緯度分に関連する語句を格納する。以下では、リストを区別しないで説明する場合、単にリストＬと表記する。リストＬは、ノードＮ毎に、文章を構成する語句を１以上格納するものであって、読上げ文章構築装置２０において用いられる。
【００３８】
（各部の構成）
図２を参照して、ノード通過回数決定装置１０の各部の構成を説明する。
ノード通過回数決定装置１０は、ハードウェア装置とソフトウェアとが協働することによって、前記したハードウェア資源がプログラムによって制御されることにより、図２に示す入力部３０と、記憶部４０と、処理部５０とが実現される。
【００３９】
入力部（入力手段）３０は、有向グラフと当該有向グラフにおける各ノードに与えられた最小通過回数との入力を受け付けるものであり、例えば、キーボード、マウス、ディスクドライブ装置などから構成される。入力部３０から入力された情報は、記憶部４０に格納される。また、本実施形態では、入力部３０は、リストＬも入力として受け付けることとした（図２参照）。なお、リストＬについては、読上げ文章構築装置２０に直接入力するように構成してもよい（図１参照）。
【００４０】
記憶部（記憶手段）４０は、例えば、一般的なハードディスク等から構成され、入力部３０から入力された情報、演算処理結果、処理部５０を機能させるためのプログラム等を記憶するものである。記憶部４０は、例えば、入力部３０から入力された情報として、有向グラフ４１と、最小通過回数４２と、リスト４３とを記憶し、演算処理結果として、ノード通過回数４４と、共用通過回数４５とを記憶する。
【００４１】
なお、図２において、記憶部４０に示した有向グラフ４１、最小通過回数４２、リスト４３、ノード通過回数４４および共用通過回数４５は、情報の種類を区別するために１つずつ符号を付して記述されているが、各情報が１つずつ存在しているものではなく、複数の情報を総称している。ただし、共用通過回数４５については単数の場合もありうる。また、有向グラフ４１、最小通過回数４２、リスト４３、ノード通過回数４４、共用通過回数４５は、ノードＮの識別情報を介して相互に関連している。
【００４２】
有向グラフ４１は、例えば、ノードＮの識別情報や個数、分岐情報やマージ情報、エッジの情報を含む。
最小通過回数４２は、有向グラフの各ノードＮにそれぞれ与えられており、有向グラフの構造を維持したままＳＴＡＲＴノード（始点）からＥＮＤノード（終点）までを接続する経路においてノードＮで示される内容を置換して各ノードＮを接続するときに各ノードＮをそれぞれ通過する回数の最小値を示す。
【００４３】
リスト４３は、有向グラフの各ノードＮにそれぞれ与えられており、例えば、図４に例示した構造を有する。
ノード通過回数４４は、有向グラフの各ノードＮにそれぞれ与えられており、処理部５０の演算結果としての暫定値または確定値を表す。
共用通過回数４５は、有向グラフにおいてノードＮの分岐があって後記する特定の条件が満たされた場合に、処理部５０の演算結果としてメモリされて利用される通過回数の所定値を表す。
【００４４】
処理部５０は、例えば、ＣＰＵおよびＲＡＭ（Random Access Memory）から構成され、図２に示すように、分岐開始判定部５１と、分岐マージ判定部５２と、ルートノード通過回数決定部５３と、ノード通過回数管理部５４と、共用通過回数管理部５５と、トレースバック部５６とを備えている。
【００４５】
分岐開始判定部（分岐開始判定手段）５１は、有向グラフの構造を解析して当該有向グラフにおける分岐の開始を判定するものである。判定結果は、ルートノード通過回数決定部５３に出力される。
分岐マージ判定部（分岐マージ判定手段）５２は、有向グラフの構造を解析して当該有向グラフにおける分岐のマージを判定するものである。判定結果は、ルートノード通過回数決定部５３に出力される。
【００４６】
ルートノード通過回数決定部（ルートノード通過回数決定手段）５３は、有向グラフのルートノードの通過回数を最小にするように各ノードＮの通過回数を有向グラフのＳＴＡＲＴノード（始点）からＥＮＤノード（終点）に向けて逐次的に暫定的な値として決定し、ＥＮＤノードにおいて決定した暫定的な値をルートノードの通過回数として確定するものである。このために、ルートノード通過回数決定部５３は、分岐開始判定部５１の判定結果と、分岐マージ判定部５２の判定結果とから得られる有向グラフにおけるＳＴＡＲＴノードからＥＮＤノードに向けての分岐の状態と、有向グラフにおける各ノードＮに与えられた最小通過回数とを取得し、これらに基づいて、各ノードＮの通過回数の暫定値を決定する。このルートノード通過回数決定部５３は、有向グラフにおけるＳＴＡＲＴノードからＥＮＤノードに向けての分岐の状態によって処理が異なる。ルートノード通過回数決定部５３の処理の詳細については、ノード通過回数決定装置１０の動作を示すフローチャートとその具体例を用いて後記する。
【００４７】
ノード通過回数管理部（ノード通過回数管理手段）５４は、有向グラフにおけるルートノード（ＳＴＡＲＴノード）、終点（ＥＮＤノード）および各ノードＮに対してルートノード通過回数決定部５３で決定される通過回数の暫定値、または、トレースバック部５６で決定される通過回数の確定値を、ノード通過回数４４として記憶部４０に保持して管理するものである。
【００４８】
共用通過回数管理部（共用通過回数管理手段）５５は、有向グラフのＳＴＡＲＴノードからＥＮＤノードに向けての分岐において分岐前のノードの通過回数（暫定値）から分岐後の各ノードに与えられた最小通過回数（設定値）の和を差し引いた差分値を、分岐後の各ノードおよび当該分岐のマージ前後に係る各ノードの暫定的な通過回数を決定するまで共用するための共用通過回数４５として記憶部４０に保持し、共用通過回数４５の増減を管理するものである。本実施形態では、共用通過回数管理部５５は、ルートノード通過回数決定部５３からの指示により、記憶部４０への共用通過回数４５の保持およびその増減を行う。共用通過回数管理部５５は、処理の結果、共用通過回数が０または負になった場合には、その共用通過回数を削除する（クリアする）。なお、共用通過回数管理部５５の処理の詳細については、ノード通過回数決定装置１０の動作を示すフローチャートとその具体例を用いて後記する。
【００４９】
トレースバック部（トレースバック手段）５６は、有向グラフのＥＮＤノード（終点）の通過回数を、ルートノード通過回数決定部５３で確定されたルートノードの通過回数と同じ値として、ルートノードの通過回数を最小値に維持しながら、各ノードの通過回数を、有向グラフのＥＮＤノード（終点）からＳＴＡＲＴノード（始点）に向けて逐次的に確定するものである。このために、トレースバック部５６は、分岐開始判定部５１の判定結果と、分岐マージ判定部５２の判定結果とから得られる有向グラフにおけるＥＮＤノードからＳＴＡＲＴノードに向けての分岐の状態と、暫定的な値として決定された各ノードＮの通過回数と、確定されたルートノードの通過回数とを取得し、これらに基づいて、各ノードＮの通過回数の確定値を決定する。このトレースバック部５６は、有向グラフにおけるＥＮＤノードからＳＴＡＲＴノードに向けての分岐の状態によって処理が異なる。トレースバック部５６の処理の詳細については、ノード通過回数決定装置１０の動作を示すフローチャートとその具体例を用いて後記する。
【００５０】
なお、ノード通過回数決定装置１０は、一般的なコンピュータを、前記した各手段（分岐開始判定部５１、分岐マージ判定部５２、ルートノード通過回数決定部５３、ノード通過回数管理部５４、共用通過回数管理部５５およびトレースバック部５６）として機能させるプログラムにより動作させることで実現することができる。このプログラム（ノード通過回数決定プログラム）は、通信回線を介して提供することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００５１】
［ノード通過回数決定装置の動作］
次に、図５ないし図７を参照（適宜図２参照）して、ノード通過回数決定装置１０の動作について説明する。図５および図６は、本発明の実施形態に係るノード通過回数決定装置の処理部の全体動作を示すフローチャートであり、図７は、図５に示したトレースバック処理の詳細を示すフローチャートである。
【００５２】
まず、図５および図６を参照する。ノード通過回数決定装置１０は、ルートノード通過回数決定部５３によって、有向グラフのＳＴＡＲＴノードから処理を開始して、ＥＮＤノードに到達したか否かを判別する（ステップＳ１）。ＥＮＤノードに到達していない場合（ステップＳ１：Ｎｏ）、ルートノード通過回数決定部５３は、分岐開始判定部５１の判定結果により、現在のステータスにおいて、ＳＴＡＲＴノードからＥＮＤノードに向けての分岐がないか否かを判別する（ステップＳ２）。現在のステータスにおいて、分岐がないという状態ではない場合（ステップＳ２：Ｎｏ）、ルートノード通過回数決定部５３は、分岐開始判定部５１の判定結果により、現在のステータスが分岐開始であるか否かを判別する（ステップＳ３）。現在のステータスが分岐開始であるという状態ではない場合（ステップＳ３：Ｎｏ）、ルートノード通過回数決定部５３は、分岐マージ判定部５２の判定結果により、現在のステータスにおいて分岐マージがあるか否かを判別する（ステップＳ４）。現在のステータスにおいて分岐マージがあるという状態ではないと判別された場合（ステップＳ４：Ｎｏ）、現在のステータスにおいて、「分岐」、「マージ」、「分岐がない」という３状態のいずれでもないという判定結果なので、ノード通過回数決定装置１０は、エラー終了する。以下、ステップＳ１でＮｏの場合であって、エラー終了にならない各状態を個別に説明する。
【００５３】
＜隣り合うノード間で分岐がない状態＞
前記したステップＳ２において、現在のステータスにおいて分岐がない場合（ステップＳ２：Ｙｅｓ）、ルートノード通過回数決定部５３は、「後のノード（次ノード）に与えられた最小通過回数」が「前のノード（現ノード）の通過回数（暫定値）」よりも小さいか否か判別する（ステップＳ５）。「次ノードに与えられた最小通過回数」が「現ノードの通過回数」よりも小さい場合（ステップＳ５：Ｙｅｓ）、ノード通過回数決定装置１０は、ルートノード通過回数決定部５３によって、大きい方の値である「現ノードの通過回数」を、「次ノードの通過回数」の暫定値として決定し（ステップＳ６）、ステップＳ１に戻る。一方、前記したステップＳ５において、「次ノードに与えられた最小通過回数」が「現ノードの通過回数」以上である場合（ステップＳ５：Ｎｏ）、ノード通過回数決定装置１０は、ルートノード通過回数決定部５３によって、大きい方の値である「次ノードに与えられた最小通過回数」を、そのまま「次ノードの通過回数」の暫定値として決定し（ステップＳ７）、引き続いて、後記するステップＳ１２の処理結果として、現ノードに係る共用通過回数が記憶部４０に保持されているか否かを判別する（ステップＳ８）。現ノードに係る共用通過回数が保持されていない場合（ステップＳ８：Ｎｏ）、ノード通過回数決定装置１０は、ステップＳ１に戻る。一方、現ノードに係る共用通過回数が保持されている場合（ステップＳ８：Ｙｅｓ）、ルートノード通過回数決定部５３は、「次ノードの通過回数」と「現ノードの通過回数」との差分を、現ノードに係る共用通過回数から減算するように共用通過回数管理部５５に指示する。これにより、ノード通過回数決定装置１０は、共用通過回数管理部５５によって、記憶部４０に記憶された現ノードに係る共用通過回数から、「次ノードの通過回数」と「現ノードの通過回数」との差分を減算し（ステップＳ９）、ステップＳ１に戻る。
【００５４】
つまり、ルートノード通過回数決定部５３は、有向グラフにおいて隣り合うノード間にＳＴＡＲＴノードからＥＮＤノードに向けての分岐がない場合には、ステップＳ５〜ステップＳ９に示すように、「ＳＴＡＲＴノード側のノードの通過回数」と、「ＥＮＤノード側のノードに与えられた最小通過回数」とを比較し、どちらか大きい方の値を、「ＥＮＤノード側のノードの通過回数」として暫定的に決定し、「ＥＮＤノード側のノードに与えられた最小通過回数」の方が大きく、かつ、記憶部４０に、当該隣り合うノードの始点側ノードに係る共用通過回数が保持されていれば、共用通過回数管理部５５に対して、「ＥＮＤノード側のノードに与えられた最小通過回数」から「ＳＴＡＲＴノード側のノードの通過回数」を差し引いた差分だけ共用通過回数４５の値を減算するように指示する。
【００５５】
＜隣り合うノード間で分岐がある状態＞
前記したステップＳ３において、現在のステータスが分岐開始であると判定された場合（ステップＳ３：Ｙｅｓ）、ルートノード通過回数決定部５３は、「分岐後の各ノードに与えられた最小通過回数」を「分岐後の各ノードの通過回数」の暫定値として決定し（ステップＳ１０）、「分岐後の各ノードに与えられた最小通過回数の和」が、「現ノード（分岐前のノード）の通過回数（暫定値）」よりも小さいか否か判別する（ステップＳ１１）。「現ノードの通過回数」が、「分岐後の各ノードに与えられた最小通過回数の和」以上である場合（ステップＳ１１：Ｎｏ）、ノード通過回数決定装置１０は、ステップＳ１に戻る。一方、「分岐後の各ノードに与えられた最小通過回数の和」が、「現ノードの通過回数」よりも小さい場合（ステップＳ１１：Ｙｅｓ）、ノード通過回数決定装置１０は、ルートノード通過回数決定部５３によって、「分岐後の各ノードに与えられた最小通過回数の和（分岐の各ノードの通過回数の合計）」と「現ノード（分岐前のノード）の通過回数（暫定値）」との差分を、当該分岐に係る共用通過回数とするように共用通過回数管理部５５に指示する。これにより、ノード通過回数決定装置１０は、共用通過回数管理部５５によって、「分岐の各ノードの通過回数の合計」と「現ノードの通過回数との差分を、当該分岐に係る共用通過回数として記憶部４０に保存し（ステップＳ１２）、ステップＳ１に戻る。
【００５６】
つまり、ルートノード通過回数決定部５３は、有向グラフにおいてＳＴＡＲＴノードからＥＮＤノードに向けての分岐がある場合には、ステップＳ１０〜ステップＳ１２に示すように、「分岐後の各ノードに与えられた最小通過回数」を、「分岐後の各ノードの通過回数」として暫定的に決定し、かつ、「分岐前のノードの通過回数」と「分岐後のノードの通過回数の和と」を比較し、「分岐前のノードの通過回数」の方が大きければ、共用通過回数管理部５５に対して、「分岐前のノードの通過回数」から「分岐後のノードの通過回数の和」を差し引いた差分を当該分岐に係る共用通過回数として記憶部４０に保持するように指示する。
【００５７】
＜隣り合うノード間でマージがある状態＞
前記したステップＳ４において、現在のステータスにおいて分岐マージがあると判定された場合（ステップＳ４：Ｙｅｓ）、ルートノード通過回数決定部５３は、「各分岐のノード（マージ前の各ノード）の通過回数（暫定値）の和」が「マージ後のノードに与えられた最小通過回数」よりも小さいか否か判別する（ステップＳ１３）。「各分岐のノードの通過回数の和」が、「マージ後のノードに与えられた最小通過回数」より小さい場合（ステップＳ１３：Ｙｅｓ）、ルートノード通過回数決定部５３は、「マージ後のノードに与えられた最小通過回数」を「マージ後のノードの通過回数」の暫定値として決定し（ステップＳ１４）、ステップＳ１に戻る。一方、「各分岐のノードの通過回数の和」が、「マージ後のノードに与えられた最小通過回数」以上である場合（ステップＳ１３：Ｎｏ）、ルートノード通過回数決定部５３は、「各分岐のノードの通過回数の和」を「マージ後のノードの通過回数」の暫定値として決定し（ステップＳ１５）、引き続いて、前記したステップＳ１２の処理結果としてマージ前の各ノードにおいて共用された共用通過回数が記憶部４０に保持されているか否かを判別する（ステップＳ１６）。マージ前の各ノードにおいて共用された共用通過回数が保持されていない場合（ステップＳ１６：Ｎｏ）、ノード通過回数決定装置１０は、ステップＳ１に戻る。一方、マージ前の各ノードにおいて共用された共用通過回数が保持されている場合（ステップＳ１６：Ｙｅｓ）、ルートノード通過回数決定部５３は、マージ前の各ノードにおいて共用された共用通過回数を削除するように共用通過回数管理部５５に指示する。これにより、ノード通過回数決定装置１０は、共用通過回数管理部５５によって、記憶部４０に記憶された共用通過回数（マージ前の各ノードにおいて共用された共用通過回数）を削除（クリア）し（ステップＳ１７）、ステップＳ１に戻る。
【００５８】
つまり、ルートノード通過回数決定部５３は、有向グラフにおいてＳＴＡＲＴノードからＥＮＤノードに向けてのマージがある場合には、ステップＳ１３〜ステップＳ１７に示すように、「マージ前の各ノードの通過回数の和」と「マージ後のノードに与えられた最小通過回数」とを比較し、比較の結果、「マージ前の各ノードの通過回数の和」が「マージ後のノードに与えられた最小通過回数」よりも小さければ、「マージ後のノードに与えられた最小通過回数」を「マージ後のノードの通過回数」として暫定的に決定する。一方、比較の結果、「マージ前の各ノードの通過回数の和」が「マージ後のノードに与えられた最小通過回数」以上であれば、ルートノード通過回数決定部５３は、「マージ前の各ノードの通過回数の和」を「マージ後のノードの通過回数」として暫定的に決定すると共に、マージ前の各ノードにおいて共用通過回数が共用されていた場合には当該共用されている共用通過回数を削除するように共用通過回数管理部５５に対して指示する。
【００５９】
＜トレースバック処理＞
次に、ステップＳ１でＹｅｓの場合の動作について説明する。ノード通過回数決定装置１０は、ルートノード通過回数決定部５３によって、有向グラフのＳＴＡＲＴノードから処理を開始してＥＮＤノードに到達したと判別した場合（ステップＳ１：Ｙｅｓ）、トレースバック部５６によって、トレースバック処理を行う（ステップＳ２０）。ここで、図７を参照する。ノード通過回数決定装置１０は、トレースバック部５６によって、有向グラフのＥＮＤノードから処理を開始してＳＴＡＲＴノードに到達したか否かを判別する（ステップＳ２１）。ＳＴＡＲＴノードに到達していない場合（ステップＳ２１：Ｎｏ）、トレースバック部５６は、現在のステータスにおいて、ＥＮＤノードからＳＴＡＲＴノードに向けての分岐がないか否かを判別する（ステップＳ２２）。
【００６０】
現在のステータスにおいて分岐がない場合（ステップＳ２２：Ｙｅｓ）、トレースバック部５６は、「後のノード（ＥＮＤノード側のノード）の通過回数（暫定値）」を確定し、確定した「後のノードの通過回数（確定値）」を、「前のノード（ＳＴＡＲＴノード側のノード）の通過回数（確定値）」として決定する（ステップＳ２３）。
【００６１】
前記したステップＳ２２において、現在のステータスにおいて分岐がないという状態ではない場合（ステップＳ２２：Ｎｏ）、トレースバック部５６は、分岐開始判定部５１の判定結果により、現在のステータスが分岐開始であるか否かを判別する（ステップＳ２４）。分岐開始である場合（ステップＳ２４：Ｙｅｓ）、トレースバック部５６は、「後のノード（ＥＮＤノード側のノード）の通過回数（暫定値）」を確定し、確定した「後のノードの通過回数（確定値）」を、「各分岐のノード（ＳＴＡＲＴノード側の各ノード）の通過回数（暫定値）の和」で除した比率を算出し、「各分岐のノードの通過回数（暫定値）」に対してこの比率を乗算した結果を新たな通過回数（確定値）として決定する（ステップＳ２５）。
【００６２】
前記したステップＳ２４において、現在のステータスが分岐開始であるという状態ではない場合（ステップＳ２４：Ｎｏ）、トレースバック部５６は、分岐マージ判定部５２の判定結果により、現在のステータスに分岐マージがあるか否かを判別する（ステップＳ２６）。現在のステータスに分岐マージがある場合（ステップＳ２６：Ｙｅｓ）、トレースバック部５６は、「各分岐のノード（ＥＮＤノード側のノード）の通過回数（確定値）の和」を、「前のノード（ＳＴＡＲＴノード側のノード）の通過回数（確定値）」として決定する（ステップＳ２７）。
【００６３】
前記したステップＳ２６において、現在のステータスにおいて分岐マージがあるという状態ではないと判別された場合（ステップＳ２６：Ｎｏ）、現在のステータスが、「分岐」、「マージ」、「分岐がない」という３状態のいずれでもないという判定結果なので、ノード通過回数決定装置１０は、エラー終了する。また、前記したステップＳ２１において、ＳＴＡＲＴノードに到達した場合（ステップＳ２１：Ｙｅｓ）、ノード通過回数決定装置１０は、処理を終了する。
【００６４】
つまり、トレースバック部５６は、有向グラフにおいて隣り合うノード間にＥＮＤノードからＳＴＡＲＴノードに向けての分岐がない場合には、ステップＳ２３に示すように、「後（ＥＮＤノード側）のノードの通過回数」を確定し、確定した「後のノードの通過回数」と同じ値を「前（ＳＴＡＲＴノード側）のノードの通過回数」として確定する。
また、トレースバック部５６は、有向グラフにおいてＥＮＤノードからＳＴＡＲＴノードに向けての分岐がある場合には、ステップＳ２５に示すように、「分岐後の各ノードの暫定的な通過回数の和」で除した比率を求め、この求めた比率を、「分岐後の各ノードの暫定的な通過回数」に掛けた値を、「分岐後の各ノードの通過回数」として確定する。
さらに、トレースバック部５６は、有向グラフにおいてＥＮＤノードからＳＴＡＲＴノードに向けてのマージがある場合には、ステップＳ２７に示すように、「各分岐のノード（マージ前の各ノード）の通過回数の和」を、「前のノード（マージ後のノード）の通過回数」として確定する。
【００６５】
［ノードの通過回数の決定方法の具体例１］
次に、本実施形態の「ノードの通過回数」の決定方法の具体例について説明する。
＜前提条件＞
ここでは、一例として、図８（ａ）に示すグラフ構造を有した有向グラフを想定する。ここでは、ノード識別子が、Ｎ１〜Ｎ１２で表されるものとする。また、ノードとエッジで構成された有向グラフを、説明の都合上、例えば、式（１）のように数式化することとする。この式（１）において、［START］はＳＴＡＲＴノード、［END］はＥＮＤノード、［Ａ］はノードＡを示す。また、「，」は「エッジの分岐」または「エッジの合流」を示す。また、［Ａ］［Ｂ］は、ノードＡから分岐せずにノードＢに接続することを示す。さらに、「Ａ，（Ｂ｜Ｃ），Ｄ」は、ノードＡからノードＢとノードＣとに分岐し、ノードＢとノードＣとがマージしてノードＤとなることを示す。
【００６６】
【数１】
2010033461.tif 000003
【００６７】
また、図８（ａ）は、有向グラフの構造を示しつつ、各ノードＮ１〜Ｎ１２に関連付けられて予め設定されている（与えられた）最小通過回数の値を合わせて示している。図８（ａ）は、有向グラフを単純に示しているものではなく、記憶部４０に記憶された有向グラフ４１と最小通過回数４２とを関連付けて表現したものである。この意味でノードの形状を円ではなく二重の同心円とした。このときの有向グラフ４１と最小通過回数４２との関連付けを、前記した式（１）と同様な記法を用いて式（２）のように数式化することとする。ただし、式（２）では、ノードの位置にノード識別子ではなく、対応する最小通過回数を記述した。つまり、［100］は、その位置のノードの最小通過回数が１００回であることを示す。
【００６８】
【数２】
2010033461.tif 000004
【００６９】
また、図８（ｂ）および図８（ｃ）は、有向グラフそのものではなく、グラフの構造に対応させつつ、記憶部４０に記憶された有向グラフ４１とノード通過回数４４とを関連付けて表現したものである。つまり記憶部４０のノードに対応した記憶領域（メモリ）の意味でノードの形状を円ではなくブロックとした。また、図８（ｂ）では、ルートノード通過回数決定部５３による処理を示す。そこで、図８（ｂ）のブロックで示すメモリには、ノードの通過回数の暫定値Ｘが記憶され、図８（ｂ）のブロック間の矢印は処理方向を示している。また、図８（ｃ）では、トレースバック部５６による処理を示す。そこで、図８（ｃ）のブロックで示すメモリには、ノードの通過回数の確定値Ｙが記憶される。図８（ｃ）のブロック間の矢印は処理の方向を示している。
【００７０】
＜ルートノード通過回数決定部５３による通過回数の暫定値の決定方法＞
ここでは、図８（ａ）および図８（ｂ）を参照する（適宜図２、図５、図６参照）。
ルートノード通過回数決定部５３は、まず、ＳＴＡＲＴノードに対応したメモリ（ノード通過回数４４）に、図８（ｂ）に示すように「０」をセットする。これが現ノードの通過回数である。次ノードであるノードＮ１に対応したメモリＸ１には、通過回数として「１００」がセットされる。続いて、分岐開始となる。分岐後の各ノードに与えられた最小通過回数の和は、「６００＋１８０＝７８０」となり、「現ノードの通過回数（１００）」よりも大きい。したがって、各分岐では、与えられた最小通過回数を通過回数として保持することとなる。ここでは、ノードＮ２に対応したメモリＸ２には、通過回数として「６００」がセットされ、ノードＮ４に対応したメモリＸ４には、通過回数として「１８０」がセットされる。
【００７１】
分岐の一方であるノードＮ２の後には分岐がないので、与えられた最小通過回数の大小比較から、ノードＮ３に対応したメモリＸ３には、ノードＮ２の通過回数（６００）が保持される。同様に、分岐の他方であるノードＮ５に対応したメモリＸ５には、ノードＮ４の通過回数（１８０）が保持される。次いで、ノードＮ３とノードＮ５との分岐マージになる。ここで、各分岐の通過回数の和（７８０）が、次ノードであるノードＮ６に与えられた最小通過回数（２００）よりも大きいので、ノードＮ６に対応したメモリＸ６には、通過回数として「７８０」が保持される。次の分岐開始では、分岐後の各ノードに与えられた最小通過回数の和は「９９＋７＋１０３＝２０９」となる。この値は、現ノードの通過回数（７８０）よりも小さい。したがって、各分岐では、与えられた最小通過回数をノード通過回数４４として記憶部４０のメモリに保持し、かつ、「７８０−２０９＝５７１」を、共用通過回数４５として記憶部４０のメモリに格納する。ここで、図９（ａ）を参照する。
【００７２】
図９（ａ）に示すように、各分岐では、ノードＮ７に対応したメモリＸ７には、通過回数として「９９」が保持され、ノードＮ９に対応したメモリＸ９には、通過回数として「７」が保持され、ノードＮ１１に対応したメモリＸ１１には、通過回数として「１０３」が保持されている。一方、分岐前のノードＮ６に対応したメモリＸ６には、通過回数として「７８０」が保持されている。ルートノード通過回数決定部５３は、ルートノードの通過回数を最小にするように各ノードの通過回数を決定していくので、「分岐前の通過回数」が「分岐後の通過回数」と一致しないことは不都合である。理想的には、各分岐の通過回数を「９９＋α」、「７＋β」、「１０３＋γ」のように決定できることが好ましい。しかしながら、ルートノード通過回数決定部５３は、未決定の値として共用通過回数を用いることで、分岐前後の通過回数の不一致を解消することが可能である。また、ルートノード通過回数決定部５３は、ノードの通過回数の暫定値を決定するものであり、α、β、γを個別に特定する必要がなく、一括して管理することができる。
【００７３】
次に、図９（ｂ）に示すように、ノードＮ８に対応したメモリＸ８には、通過回数として「１００」が保持される。なお、これは、図８（ａ）に示すようにノードＮ７の後には分岐がないので、ノードＮ７に与えられた最小通過回数（９９）と、ノードＮ８に与えられた最小通過回数（１００）との大小比較を行った結果である。ノードＮ８に対応したメモリＸ８に「１００」が保持されたときに、図９（ｂ）に示すように、各分岐のノードに対応したメモリにおいて、共用通過回数と共有する合計の通過回数を「１００＋α1」、「７＋β」、「１０３＋γ」のように考えることができる。ただし、この時点では、α1、β、γは未決定であり、各分岐の各ノードに対して決定されている通過回数（ノード通過回数４４として記憶部４０のメモリに保持した値）は、「９９」、「７」、「１０３」である。このとき、記憶部４０のメモリでは、共用通過回数４５が、暫定値として決定された通過回数の差分（１００−９９＝１）だけ減算される。
【００７４】
次に、図９（ｃ）に示すように、ノードＮ１０に対応したメモリＸ１０には、通過回数として「５８０」が保持される。なお、これは、図８（ａ）に示すようにノードＮ９の後には分岐がないので、ノードＮ９に与えられた最小通過回数（７）と、ノードＮ１０に与えられた最小通過回数（５８０）との大小比較を行った結果である。ノードＮ１０に対応したメモリＸ１０に「５８０」が保持されたときに、図９（ｃ）に示すように、各分岐のノードに対応したメモリにおいて、共用通過回数と共有する合計の通過回数を「１００＋α1」、「５８０＋β1」、「１０３＋γ」のように考えることができる。なお、α1、β1、γは未決定であり、各分岐の各ノードに対して決定されている通過回数（ノード通過回数４４として記憶部４０のメモリに保持した値）は、「１００」、「５８０」、「１０３」である。このとき、共用通過回数４５として記憶部４０のメモリでは、暫定値として決定された通過回数の差分（５８０−７＝５７３）が減算される。この直前には、共用通過回数４５は「５７０」であったので、「５７３」を差し引くことで、共用通過回数の値は負（−３）になる。そこで、各分岐に係る共用通過回数のメモリ自体が破棄される。この結果、この時点では、α1、β1、γ自体が破棄され、最終的に、各分岐の各ノードに対して決定されている通過回数（ノード通過回数４４として記憶部４０のメモリに保持した値）は、「１００」、「５８０」、「１０３」となる。そして、最後の分岐マージでは、各分岐のノードの暫定的な通過回数の和（１００＋５８０＋１０３＝７８３）が、ノードＮ１２に与えられた最小通過回数（１００）よりも大きい。そのため、ノードＮ１２に対応したメモリＸ１２には、図８（ｂ）に示すように、通過回数として「７８３」が保持される。最後に、ＥＮＤノードに対応したメモリに「７８３」をセットする。これにより、「７８３」がルートノードの通過回数の最小値（算出された最小通過回数）として確定する。
【００７５】
＜トレースバック部５６による通過回数の確定値の決定方法＞
ここでは、図８（ａ）〜図８（ｃ）を参照する（適宜図２、図７参照）。
トレースバック部５６は、まず、ＥＮＤノードで確定した通過回数「７８３」を、現ノードの通過回数（確定値）とする。そして、ＥＮＤノードの前のノードＮ１２に対応したメモリＹ１２には、通過回数として「７８３」がセットされる。次の３分岐では、分岐後の各ノードＮ８，Ｎ１０，Ｎ１１の通過回数（暫定値）の和は、図８（ｂ）に示すように、最小となっていたので、これらの暫定値を確定させる。つまり、ノードＮ８に対応したメモリＹ８、ノードＮ１０に対応したメモリＹ１０、ノードＮ１１に対応したメモリＹ１１には、図８（ｂ）に示したメモリＸ８，Ｘ１０，Ｘ１１に記憶された値が設定される。各分岐のうち、ノードＮ８の前のノードＮ７に対応したメモリＹ７には、通過回数として「１００」がセットされ、同様に、ノードＮ１０の前のノードＮ９に対応したメモリＹ９には、通過回数として「５８０」がセットされる。
【００７６】
続いて分岐マージになるため、マージ前の通過回数の和（１００＋５８０＋１０３＝７８３）が、分岐マージ後の通過回数として確定する。すなわち、ノードＮ６に対応したメモリＹ６には、通過回数として「７８３」がセットされる。続いて分岐開始になる。次の分岐では、分岐後の各ノードＮ３，Ｎ４の通過回数（暫定値）の和は、図８（ｂ）に示すように、最小となっていたが、それらの和（６００＋１８０）は、メモリＹ６に記憶された通過回数（７８３）よりも小さい。したがって、トレースバック部５６は、７８３／（６００＋１８０）の比率を求め、分岐後の各ノードＮ３，Ｎ４の通過回数（暫定値）にこの比率を掛ける。これにより、ノードＮ３に対応したメモリＹ３には、通過回数として「６０２」がセットされ、同様に、ノードＮ５に対応したメモリＹ５には、通過回数として「１８１」がセットされる。なお、１つずつ比率を掛けて整数にした上で、その結果を合計値から差し引くことで残りを順番に求めることもできる。次にノードＮ３の前のノードＮ２に対応したメモリＹ２の値は、メモリＹ３の値（６０２）として確定し、ノードＮ５の前のノードＮ４に対応したメモリＹ４の値は、メモリＹ５の値（１８１）として確定する。続いて分岐マージになるため、マージ前の通過回数の和（６０２＋１８１＝７８３）が、分岐マージ後の通過回数として確定する。すなわち、ノードＮ１に対応したメモリＹ１には、通過回数として「７８３」がセットされる。最後に、ＳＴＡＲＴノードに対応したメモリに「７８３」をセットする。これにより、「７８３」がＳＴＡＲＴノードの通過回数として確定する。なお、これは、既に確定しているルートノードの通過回数である。
【００７７】
［ノードの通過回数の決定方法の具体例２］
具体例１では、図９（ｃ）を参照して説明したように、各分岐に係る共用通過回数の値が負の値となったためにメモリを破棄した。以下では、共用通過回数が負の値にならない場合を具体例２として図１０および図１１を参照して説明する。なお、具体例２において、具体例１と同じ条件については説明を省略し相違点について説明する。図１０（ａ）は、ノードＮ１０に与えられた最小通過回数が「８０」に設定されている点を除いて、図８（ａ）と同じである。このため、図１０（ｂ）は、ノードＮ１０に対応したメモリＸ１０の通過回数が「８０」に設定される。この処理の説明のため図１１を参照する。図１１（ａ）および図１１（ｂ）は、図９（ａ）および図９（ｂ）と同じである。
【００７８】
＜ルートノード通過回数決定部５３による通過回数の暫定値の決定方法＞
図１１（ｃ）に示すように、ノードＮ１０に対応したメモリＸ１０には、通過回数として「８０」が保持される。このとき、各分岐のノードに対応したメモリで共用通過回数と共有する合計の通過回数を「１００＋α1」、「８０＋β2」、「１０３＋γ」のように考えることができる。ただし、この時点では、α1、β2、γは未決定であり、各分岐の各ノードに対して決定されている通過回数（ノード通過回数４４として記憶部４０のメモリに保持した値）は、「１００」、「８０」、「１０３」である。このとき、共用通過回数４５として記憶部４０のメモリでは、暫定値として決定された通過回数の差分（８０−７＝７３）が減算される。この直前には、共用通過回数４５は「５７０」であったので、「７３」を差し引くことで、共用通過回数の値は「４９７」になる。
【００７９】
次に最後のマージがある。このマージを考慮した時点で、あらためて、マージ前の各分岐のノードＮ８、Ｎ１０，Ｎ１１の通過回数をそれぞれ「１００＋α1」、「８０＋β2」、「１０３＋γ」として暫定的に決定する。つまり、ノードＮ８、Ｎ１０，Ｎ１１を同じく考慮していたとしても、分岐後の状態あるいは分岐がない状態としての観点（前からの続きで考える観点）に立脚するのか、マージ前の状態としての観点（先を考える観点）に立脚するのかの相違がある。ここでは、具体例１とは異なり、マージ前の状態において記憶部４０のメモリに共用通過回数４５が残っていたので、マージ前の状態としての観点に立脚することで、ノードＮ８の通過回数を「１００＋α1」、ノードＮ１０の通過回数を「８０＋β2」、ノードＮ１１の通過回数を「１０３＋γ」として暫定的に決定する。なお、記憶部４０において、α1、β2、γ自体は、「１００、８０、１０３」とそれぞれ分離されて記憶されている。また、α1、β2、γは未決定のままであるが個別に求めることはしない。それは、最後の分岐マージでは、「各分岐のノード（マージ前の各ノード）の通過回数の和」と、「マージ後のノードに与えられた最小通過回数」との比較を行うからである。なお、「各分岐のノードの通過回数の和」は式（３）で求められる。
【００８０】
（１００＋α1）＋（８０＋β2）＋（１０３＋γ）
＝２８３＋（α1＋β2＋γ）＝２８３＋４９７＝７８０  …  式（３）
【００８１】
そして、最後の分岐マージでは、「各分岐のノードの暫定的な通過回数の和（７８０）」が、「ノードＮ１２に与えられた最小通過回数（１００）」よりも大きい。そのため、ノードＮ１２に対応したメモリＸ１２には、図１０（ｂ）に示すように、通過回数として「７８０」が保持される。マージ後のノードであるノードＮ１２の通過回数（暫定値）が決定したので、各分岐に係る共用通過回数は不要となり、記憶部４０に共用通過回数４５として記憶されていた値（４９７）を削除する。最後に、ＥＮＤノードに対応したメモリに「７８０」をセットする。これにより、「７８０」がルートノードの通過回数の最小値（算出された最小通過回数）として確定する。
【００８２】
＜トレースバック部５６による通過回数の確定値の決定方法＞
前記したように、図１０（ｂ）において、ノードＮ１０に対応したメモリＸ１０の通過回数が「８０」に設定されるため、図１０（ｃ）の各数値は、図８（ｃ）の各数値とは相違する。ここでは、図１０（ａ）〜図１０（ｃ）を参照する（適宜図２、図７参照）。
トレースバック部５６は、まず、ＥＮＤノードで確定した通過回数「７８０」を、現ノードの通過回数（確定値）とする。そして、ＥＮＤノードの前のノードＮ１２に対応したメモリＹ１２には、通過回数として「７８０」がセットされる。
【００８３】
次の３分岐では、分岐後の各ノードＮ８，Ｎ１０，Ｎ１１に対応したメモリＸ８、Ｘ１０，Ｘ１１に記憶された通過回数（暫定値）の和（１００＋８０＋１０）は、共用通過回数を含んでいない。つまり、通過回数（暫定値）は、ノード通過回数４４として記憶部４０のメモリに保持した値のみである。したがって、通過回数（暫定値）の和（１００＋８０＋１０）は、ノードＮ１２に確定された通過回数（７８０）よりも小さい。そのため、トレースバック部５６は、７８０／（１００＋８０＋１０）の比率を求め、分岐後の各ノードＮ８，Ｎ１０，Ｎ１１の通過回数（暫定値）にこの比率を掛ける。これにより、ノードＮ８に対応したメモリＹ８には、通過回数として「２７６」がセットされ、ノードＮ１０に対応したメモリＹ１０には、通過回数として「２２０」がセットされ、ノードＮ１１に対応したメモリＹ１１には、通過回数として「２８４」がセットされる。以降の処理は、数値が異なるだけで具体例１と同様に行うことができる。
【００８４】
［シンプレックス法を適用する場合との比較］
具体的には、前記した式（２）のように数式化されて各ノードに予め最小通過回数が設定された有向グラフにおける各ノードの通過回数およびルートノードの通過回数を求めるために、シンプレックス法を適用する場合には、図８（ａ）に示した有向グラフのような単純なグラフ構造であっても条件式として、以下の一次方程式および一次不等式を列挙する必要がある。
【００８５】
【表１】
2010033461.tif 000005
【００８６】
ここで、Ｘ１〜Ｘ１２は、ノードＮ１〜Ｎ１２にそれぞれ対応して求めようとしている通過回数（変数）を示し、同様に、ＸＳ，ＸＥは、ＳＴＡＲＴノード、ＥＮＤノードにそれぞれ対応する通過回数（変数）示す。なお、各変数Ｘ１〜Ｘ１２、ＸＳ，ＸＥは非負である。有向グラフにおける各ノードの通過回数およびルートノードの通過回数を求めるということは、この条件式において、−ＸＳを最大化する問題に帰着することができる。このためにシンプレックス法を用いて解くことができる。この結果ＸＳ＝７８３（正解）が得られる。しかしながら、グラフにおけるノードの通過回数を決定する方法にシンプレックス法を採用する場合には、シンプレックス法では、条件式を必ず記述してから解を求めるため、処理に時間がかかってしまう。
【００８７】
以上のように、本実施形態のノード通過回数決定装置１０によれば、有向グラフにおいて、ＳＴＡＲＴノードからＥＮＤノードに向けて、各ノードに与えられた最小通過回数を利用してルートノードの通過回数を最小にするように各ノードの通過回数を暫定的に決定することでルートノードの通過回数を求めることができる。そして、ノード通過回数決定装置１０は、有向グラフのＥＮＤノードでルートノードの通過回数を確定した後、ＥＮＤノードからＳＴＡＲＴノードに向けてトレースバックすることにより、各ノードでの通過回数を確定していくことができる。したがって、シンプレックス法のように条件式を記述する必要がなく、有向グラフにおけるノードの通過回数を解として安定に求め、かつ、通過回数を決定する処理の処理時間を低減することができる。
【００８８】
また、本実施形態の音声合成用読上げ文章生成装置２は、ノード通過回数決定装置１０を備えているので、有向グラフと、ノードで示される内容としての語句のリストＬとの入力を受け付け、かつ、ルートノードおよび各ノードの通過回数の確定値を決定したときに、有向グラフの各ノードに置換可能な語句を割り当てることで音声合成用読上げ文章を構築することができる。その結果、音声合成用読上げ文章生成装置２は、有向グラフにおけるノードの通過回数を解として安定に求め、かつ、通過回数を決定する処理の処理時間を低減することができる。
【００８９】
以上、本発明の実施形態について説明したが、本発明は、この実施形態には限定されない。例えば、有向グラフとして図３のグラフ構造や図８（ａ）のグラフ構造を示したが、有向グラフの構造は、これらに限定されるものではない。本発明では、グラフのＳＴＡＲＴノード（始点）からＥＮＤノード（終点）に向けて、途中でＳＴＡＲＴノード（始点）側へ戻るようなループバックがなければ様々なバリエーションのグラフ構造を有した有向グラフに適用可能である。例えば、ＳＴＡＲＴノード（始点）の直後に分岐するようにしてもよいし、ＥＮＤノード（終点）の直前の分岐がＥＮＤノードでマージするようにしてもよい。図１２に、有向グラフの構造の他の例をそれぞれ示す。
【００９０】
図１２（ａ）に示す有向グラフは、図３（ａ）に示した有向グラフにおいて、１つのノード（ノードＮ６）を取り除いたグラフ構造を有している。図１２（ａ）に示すように、ノードＮ３から出力するエッジＥ１は、ノードＮ５から出力するエッジＥ２と合流し、合流後に、ノードＮ７に入力するエッジＥ３と、ノードＮ８に入力するエッジＥ４とに分岐する。このグラフ構造を、前記した式（１）のように数式化すると式（４）で表すことができる。
【００９１】
【数３】
2010033461.tif 000006
【００９２】
この場合、エッジＥ１とエッジＥ２との合流については図３（ａ）に示した有向グラフのノードＮ６に対応したメモリＸ６を代用することができる。この場合、代用されるメモリＸ６には、最小通過回数として「０」を予め設定すればよい。
【００９３】
図１２（ｂ）に示す有向グラフは、第１の分岐としてノードＮ１からノードＮ２，Ｎ３への分岐を有し、ノードＮ２，Ｎ３の分岐がマージする前に、第２の分岐としてノードＮ２からノードＮ４，Ｎ５への分岐を有し、ノードＮ４，Ｎ５の分岐がノードＮ６にマージする。また、第１の分岐後のノードＮ３に接続されたノードＮ７は、第２の分岐がマージしたノードＮ６との間で、第１の分岐に対応してマージしてノードＮ８に接続される。この場合にも本発明のノード通過回数決定装置によるノード通過回数決定方法を用いることが可能である。このグラフ構造を、前記した式（１）のように数式化すると式（５）で表すことができる。
【００９４】
【数４】
2010033461.tif 000007
【００９５】
ただし、図１２（ｃ）に示す有向グラフは、本発明のノード通過回数決定装置によるノード通過回数決定方法の対象としてはいない。図１２（ｃ）に示す有向グラフは、図１２（ａ）に示した有向グラフを変形したものである。具体的には、図１２（ｃ）に示す有向グラフは、第１に、図１２（ａ）に示した有向グラフにおいてノードＮ８を、エッジＥ１とエッジＥ２との合流地点に移動した。これにより、ノードＮ３，Ｎ５からノードＮ８へのマージと、ノードＮ８からノードＮ７，Ｎ９への分岐を形成した。第２に、ノードＮ３からノード７へのエッジＥ５を追加した。このエッジＥ５が存在するため、ノードＮ３の位置では、「分岐がある」と判定することも可能であるし、「マージがある」と判定することも可能であり、１通りに判定することはできない。
【図面の簡単な説明】
【００９６】
【図１】本発明の実施形態に係るノード通過回数決定装置を備えた音声合成用データベース作成システムを模式的に示す構成図である。
【図２】本発明の実施形態に係るノード通過回数決定装置およびそれを備えた音声合成用読上げ文章生成装置の構成を模式的に示すブロック図である。
【図３】本発明の実施形態に係るノード通過回数決定装置に入力される有向グラフの説明図であって、（ａ）は有向グラフの構造の一例、（ｂ）は有向グラフのノードに割り当てられたテキストデータの一例をそれぞれ示している。
【図４】図３（ｂ）に例示した有向グラフにおけるノードに対応する語句のリストの説明図であって、（ａ）はノードＮ１に対応するリストの一例、（ｂ）はノードＮ４に対応するリストの一例をそれぞれ示している。
【図５】本発明の実施形態に係るノード通過回数決定装置の処理部の全体動作（その１）を示すフローチャートである。
【図６】本発明の実施形態に係るノード通過回数決定装置の処理部の全体動作（その２）を示すフローチャートである。
【図７】図５に示したトレースバック処理の詳細を示すフローチャートである。
【図８】本発明の実施形態に係るノード通過回数決定装置の処理の一例を示す説明図であって、（ａ）は有向グラフの各ノードに予め設定されたノードを通過するときの最小通過回数、（ｂ）は有向グラフのＳＴＡＲＴノードからＥＮＤノードへ向けて決定された各ノードの暫定通過回数、（ｃ）は有向グラフのＥＮＤノードからＳＴＡＲＴノードへ向けて確定された各ノードの通過回数をそれぞれ示している。
【図９】図８（ｂ）に示したメモリＸ６の値からメモリＸ１２の値が決定されるまでの処理の遷移状態とそのときの共用通過回数をそれぞれ示している。
【図１０】本発明の実施形態に係るノード通過回数決定装置の処理の他の一例を示す説明図であって、（ａ）は与えられた最小通過回数、（ｂ）は暫定通過回数、（ｃ）は各ノードの通過回数をそれぞれ示している。
【図１１】図９（ｂ）に示したメモリＸ６の値からメモリＸ１２の値が決定されるまでの処理の遷移状態とそのときの共用通過回数をそれぞれ示している。
【図１２】有向グラフの構造の他の例をそれぞれ示している。
【符号の説明】
【００９７】
１      音声合成用データベース作成システム
２      音声合成用読上げ文章生成装置
４      音声合成用データベース作成装置
５      音声合成用データベース
６      音声合成装置
１０    ノード通過回数決定装置
２０    読上げ文章構築装置
３０    入力部（入力手段）
４０    記憶部（記憶手段）
４１    有向グラフ
４２    最小通過回数
４３    リスト
４４    ノード通過回数
４５    共用通過回数
５０    処理部
５１    分岐開始判定部（分岐開始判定手段）
５２    分岐マージ判定部（分岐マージ判定手段）
５３    ルートノード通過回数決定部（ルートノード通過回数決定手段）
５４    ノード通過回数管理部（ノード通過回数管理手段）
５５    共用通過回数管理部（共用通過回数管理手段）
５６    トレースバック部（トレースバック手段）
【図１】
2010033461.tif 000008
【図２】
2010033461.tif 000009
【図３】
2010033461.tif 000010
【図４】
2010033461.tif 000011
【図５】
2010033461.tif 000012
【図６】
2010033461.tif 000013
【図７】
2010033461.tif 000014
【図８】
2010033461.tif 000015
【図９】
2010033461.tif 000016
【図１０】
2010033461.tif 000017
【図１１】
2010033461.tif 000018
【図１２】
2010033461.tif 000019