データ処理装置、方法、及びプログラム
【課題】データ入力の利便性を向上させる技術を提供する。
【解決手段】データ入力装置１０は、有向グラフのノード又はエッジに与えられた重みを保持する第１重み保持部４４と、特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、第１重み保持部４４に保持されている重みとは異なる重みが与えられる場合に、その重みを保持する第２重み保持部４５と、組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が対象経路に含まれるノードと、含まれないノードとが区別されるように、有向グラフを変形する有向グラフ変形部４２と、変形された有向グラフにおける第１ノードから第２ノードへ至る経路を、重みに基づいて評価する評価部４３と、を備える。
【解決手段】データ入力装置１０は、有向グラフのノード又はエッジに与えられた重みを保持する第１重み保持部４４と、特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、第１重み保持部４４に保持されている重みとは異なる重みが与えられる場合に、その重みを保持する第２重み保持部４５と、組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が対象経路に含まれるノードと、含まれないノードとが区別されるように、有向グラフを変形する有向グラフ変形部４２と、変形された有向グラフにおける第１ノードから第２ノードへ至る経路を、重みに基づいて評価する評価部４３と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理技術に関し、特に、重み付き有向グラフの経路を評価するデータ処理装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
日本語の文字列を入力する際に、ユーザが入力した読みを漢字に変換して入力するプログラムが広く利用されている（例えば、特許文献１参照）。
【特許文献１】特開２００４−１３９４０２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明者らは、ユーザから入力された文章の読みを漢字交じりの文章に変換する際の精度を向上させるために、漢字変換辞書を参照して、入力された文章の読みから漢字交じりの単語により構成される有向グラフを作成し、有向グラフのノード、すなわち単語と、ノード間のエッジ、すなわち単語のつながり方に対してスコアを付与し、重み付き有向グラフの最適経路問題を解くことにより最適な変換候補を選択する技術を開発している。
【０００４】
より早く、より精確な変換候補を選択するために、重み付き有向グラフの最適経路をより効率良く計算する技術が求められている。
【０００５】
本発明はこうした状況に鑑みてなされたものであり、その目的は、データ入力の利便性を向上させる技術を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は、データ処理装置に関する。このデータ処理装置は、有向グラフのノード又は２つのノードの間のエッジに与えられた重みを保持する第１重み保持部と、特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記第１重み保持部に保持されている重みとは異なる重みが与えられる場合に、前記組合せに含まれるノード又はエッジに与えられた重みを保持する第２重み保持部と、前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形する有向グラフ変形部と、前記有向グラフ変形部により変形された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記第１重み保持部及び前記第２重み保持部から読み出された重みに基づいて評価する評価部と、を備えることを特徴とする。
【０００７】
前記有向グラフ変形部は、複製したノードのうち一方のノードについては、そのノードに至るエッジのうち前記対象経路に含まれないエッジを削除し、他方のノードについては、そのノードに至るエッジのうち前記対象経路に含まれるエッジを削除してもよい。
【０００８】
前記第１重み保持部に保持されている重みとは異なる重みは、前記対象経路の最後のノードに与えられてもよい。
【０００９】
前記有向グラフ変形部は、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれるが、そのノードに続く経路が前記対象経路に含まれないノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形してもよい。
【００１０】
前記有向グラフ変形部は、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードを複製し、そのノードに続く経路が前記対象経路に含まれるノードと、そのノードに続く経路が前記対象経路に含まれるが、そのノードに至る経路が前記対象経路に含まれないノードと、そのノードに続く経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形してもよい。
【００１１】
本発明の別の態様は、データ処理方法に関する。このデータ処理方法は、有向グラフを取得するステップと、前記有向グラフのノード又は２つのノードの間のエッジに重みを付与するステップと、特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記付与するステップで与えられた重みとは異なる重みが与えられている場合、前記有向グラフに前記組合せが含まれるか否かを判定するステップと、前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形するステップと、経路が追加された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記重みに基づいて評価するステップと、を備えることを特徴とする。
【００１２】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１３】
本発明によれば、データ入力の利便性を向上させる技術を提供することができる。
【発明を実施するための最良の形態】
【００１４】
有向グラフのノードや、２つのノードの間のエッジに重みが与えられた重み付き有向グラフの最適経路問題は、乗物の乗換案内、ワークフローの管理、自然言語処理など、多くの分野で重要な技術的意義を有している。重み付き有向グラフの最適経路問題を解くためのアルゴリズムに、ビタビ（Viterbi）アルゴリズムがある。
【００１５】
図１は、有向グラフの例を示す。以降の説明を分かりやすくするために、図１に示した有向グラフは、出発駅である第１ノードＸから到着駅である第２ノードＹへ至る電車の経路を示し、ノードＡ〜Ｊは乗継駅を示すものとする。
【００１６】
図２は、図１に示した有向グラフの各ノード及び各エッジに与えられた重みを示す。この例では、各エッジの重みとして、駅間の所要時間が、各ノードの重みとして、乗継駅における乗り継ぎに要する時間が、それぞれ与えられている。ここで、出発駅Ｘから到着駅Ｙへ至る経路のうち、最も所要時間の短い最短経路を判別する方法について説明する。
【００１７】
図３は、図２に示した重み付き有向グラフの最適経路をビタビアルゴリズムにより解く方法について説明するための図である。ビタビアルゴリズムでは、出発駅に近いノードから順に、出発駅から各乗継駅へ至る最短経路を段階的に求めていく。
【００１８】
まず、出発駅であるＸ駅からＡ駅へ至る経路は１通りしかないので、Ｘ駅からＡ駅へ至る最短経路が決定される。この最短経路を通過したときのＸ駅からＡ駅までの所要時間は、「４」分である。同様に、Ｘ駅からＢ駅へ至る経路も１通りしかないので、Ｘ駅からＢ駅へ至る最短経路が決定され、所要時間は「３」分となる。
【００１９】
次に、Ｘ駅からＣ駅へ至る最短経路を算出する。Ｃ駅を終点とするエッジは、Ａ−ＣとＢ−Ｃの２本ある。Ｘ駅からＡ駅を経由してＣ駅へ至る経路の最短所要時間は、Ｘ駅からＡ駅までの最短所要時間「４」分に、Ａ駅での乗り継ぎ時間「１」分と、Ａ駅からＣ駅までの所要時間「８」分とを加算した「１３」分である。同様に、Ｘ駅からＢ駅を経由してＣ駅へ至る経路の最短所要時間は、Ｘ駅からＢ駅までの最短所要時間「３」分に、Ｂ駅での乗り継ぎ時間「２」分と、Ｂ駅からＣ駅までの所要時間「６」分を加算した「１１」分である。したがって、Ｘ駅からＣ駅へ至る最短経路は、Ｂ駅を経由する経路であり、その所要時間は「１１」分である。
【００２０】
Ｘ駅からＤ駅へ至る最短経路は、Ｄ駅を終点とするエッジが１本しかないので、そのエッジの始点であるＡ駅を経由する経路であり、その所要時間は「１１」分である。同様に、Ｘ駅からＥ駅へ至る最短経路は、Ｂ駅を経由する経路であり、その所要時間は「１２」分である。
【００２１】
このように、ある駅までの最短経路は、そのノードを終点とする１以上のエッジの中から、それぞれのエッジの始点の駅までの最短所要時間と、エッジの始点の駅における乗り継ぎ時間と、エッジの始点の駅から当該駅までの所要時間とを加算した所要時間が最も短いものを選択することにより得られる。
【００２２】
同様にして、到着駅Ｙまでの全ての駅について最短経路と最短所要時間を求めることができる。最後に、到着駅Ｙを終点とするエッジの中から最短経路を与えるエッジを求めると、直前の駅はＪ駅となるので、Ｊ駅、Ｈ駅、Ｇ駅、Ｅ駅、Ｂ駅、Ｘ駅と直前の駅を順に辿っていくことにより、最短経路が判明する。
【００２３】
以上のような方法により、Ｘ駅からＹ駅へ至る全ての経路の所要時間を算出して最短経路を判定する方法に比べて、計算量を飛躍的に低減することができる。特に、漢字変換や形態素解析などの自然言語処理の分野では、文章の長さが長くなると、文章を構成する単語の候補、すなわちノードの数が膨大になるので、このような方法を採用することによる計算量の低減が不可欠である。
【００２４】
ビタビアルゴリズムは、あるノードまでの最適経路は、そのノードの直前のノードまでの最適経路とは独立に決定可能であることを前提としている。つまり、あるノードまでの最適経路は、過去に遡ることなく、直前の最適結果に基づいて決まる場合に適用可能である。
【００２５】
ところが、現実には、ある特定のエッジやノードの組合せに対して、例外的な条件が設定される場合がある。例えば、Ｄ駅からＧ駅を経由してＨ駅へ至る路線には急行電車が運行されており、Ｄ駅からＧ駅を経由してＨ駅へ至る経路の所要時間は、Ｄ駅からＧ駅への所要時間とＧ駅からＨ駅への所要時間との単純な合計よりも短くなるという条件があるとする。このような例外的な条件は、図２に示した重み付き有向グラフでは表現できない。
【００２６】
このように、連続する２つのノードの組合せに対して、ノードやエッジの重みが与えられるだけでなく、３以上のノードの組合せなどに対して、例外的な重みが与えられる場合、その組合せに対する例外的な重みを設定可能とするために、その組合せを通過する経路を別に設ける必要がある。
【００２７】
図４は、連続する３つのノードの組合せに対して例外的な重みが与えられることを考慮して生成された有向グラフの例を示す。図２の有向グラフでは、例えばＦへ至る経路として、Ａ−Ｃ−Ｆという経路とＢ−Ｃ−Ｆという経路は区別しない。これは、Ｃまでは最短経路を通っていることが前提となっており、Ａを経由したかＢを経由したかは、Ｆまでの最短経路を決定する際に考慮しないからである。これに対し、図４の有向グラフでは、Ａ−Ｃ−Ｆという経路とＢ−Ｃ−Ｆという経路を別の経路として表現するために、Ｃ及びＦのノードを２つ設けている。これにより、Ａ及びＣを経由してＦへ至る経路と、Ｂ及びＣを経由してＦへ至る経路を区別し、異なる重みを与えることができる。同様にして、他のノードについても、２つ前のノードが異なる経路を区別するために複数のノードを設けている。
【００２８】
図５は、連続する４つのノードの組合せに対して例外的な重みが与えられることを考慮して生成された有向グラフの例を示す。図４の有向グラフでは、Ａ−Ｃ−Ｆ−ＨとＢ−Ｃ−Ｆ−Ｈという経路は区別していなかったが、図５の有向グラフでは、３つ前のノードが異なっている経路も区別するので、Ａ−Ｃ−Ｆ−Ｈに対応するＨとＢ−Ｃ−Ｆ−Ｈに対応するＨを設けている。
【００２９】
図４及び図５に示した有向グラフでは、連続する３以上のノードの組合せに対して与えられた例外的な重みを考慮して最適経路を求めることができるが、例外的な重みが与えられる組合せに、連続するいくつのノードが含まれるかが予め分かっていないと、有向グラフを生成することができない。例えば、連続する３つのノードの組合せを考慮すると、図５に示した有向グラフを生成すればよいが、連続する４つのノードの組合せに対して新たに例外的な重みが与えられた場合は、図５に示した有向グラフを生成し直す必要がある。
【００３０】
また、自然言語処理に応用する場合など、元の有向グラフの規模が大きい場合には、追加すべき経路の数が膨大になり、計算量が飛躍的に増大して、計算速度が低下するおそれがある。
【００３１】
本実施の形態では、重み付き有向グラフにおいて、２以上のエッジ、３以上のノード、連続しない２つのノードなどの組合せに対して例外的な重みが与えられる場合に、効率良く最適経路を求める技術を提案する。
【００３２】
図６は、図１に示した有向グラフにおいて、連続する３つのノードの組合せに対して例外的な重みが与えられた場合に、ビタビアルゴリズムにより最適経路を求めるための有向グラフを示す。図６では、Ｄ−Ｇ−Ｈという連続する３つのノードの組合せに対して例外的な重みを与えるために、Ｄ−Ｇ−Ｈという経路を有向グラフにもう１つ追加している。具体的には、Ｄ−Ｇ−Ｈという組合せの最初のノードＤから分岐して、途中のノードＧを経由し、最後のノードＨまで至る経路を複製する。
【００３３】
図７は、図６に示した有向グラフの各エッジ及びノードに重みを付与し、ビタビアルゴリズムにより最適経路を求めた様子を示す。図７では、Ｄ駅−Ｇ駅−Ｈ駅という経路には急行列車が運行されているため、Ｄ駅−Ｇ駅−Ｈ駅という経路を通過する場合には、Ｄ駅−Ｇ駅間の所要時間が４分から１分に短縮される例が示されている。図中、２つあるノードＨのうち、上側のノードＨは例外的な重みを考慮せずにノードＨまでの最適経路を求めた結果を示し、下側のノードＨは経路Ｄ−Ｇ−Ｈに対して与えられた例外的な重みを考慮した場合のノードＨまでの最適経路を求めた結果を示す。
【００３４】
図８は、２つのエッジの組合せに対して与えられた例外的な重みを考慮した有向グラフを示す。図８では、エッジＡ−ＤとエッジＨ−Ｊの組合せに対して例外的な重みが与えられている。例えば、Ａ駅からＤ駅までの路線とＨ駅からＪ駅までの路線が同一の主体により運営されているために、これらの路線を使うと割引料金が適用されるような例が想定される。この場合、エッジＡ−ＤとエッジＨ−Ｊを含む経路を元の有向グラフから抽出し、抽出した経路を有向グラフに追加する。これにより、エッジＡ−ＤとエッジＡ−Ｊの両方を通過する経路を有向グラフの中に新たに設け、その経路に対して例外的な重みを付与することができる。
【００３５】
図９は、連続しない２つのノードの組合せに対して与えられた例外的な重みを考慮した有向グラフを示す。図９では、ノードＤとノードＨの組合せに対して例外的な重みが与えられている。例えば、ひらがなで入力された文章を漢字仮名交じり文に変換するときに、「鳥」という単語が先行する場合は「とぶ」というひらがなに対応する変換候補として「飛ぶ」という候補のスコアを高くするなどといった共起用例が想定される。この場合、ノードＤとノードＨの間の経路を元の有向グラフから抽出し、抽出した経路を有向グラフに追加する。これにより、ノードＤの存在を考慮しないノードＨのスコアと、ノードＤが先行する場合のノードＨのスコアを区別して表現することができる。
【００３６】
このようにして、重み付き有向グラフに、例外的な重みが与えられた経路を追加することにより、計算量の増大を最小限に抑えつつ、直前のノードではなく過去のノードまで遡って参照しなければならないような例外的な条件をも考慮して最適経路を求めることができる。
【００３７】
上記の例では、例外的な重みが与えられた経路を有向グラフに追加したが、この場合、実質的に同じ経路が有向グラフ中に重複して存在することになる。最適経路を探索する際には、このことは問題にならないが、２番目以降の経路を算出する際に、実質的には同じ経路であるのに別の経路として報告してしまうことがあるため、ｎ−ベスト探索のアルゴリズムが破綻するおそれがある。したがって、ｎ−ベスト探索を行う際には、ノード又はエッジを追加しても、経路の総数を変えない経路の組み替えが必要となる。このようなアルゴリズムについて更に説明する。
【００３８】
有向グラフを変形する際に、述語論理に基づいたプログラミング言語等を利用してもよい。この場合、例外的な重みは、ノードに対する条件要請として与えられる。この条件要請は、ノードを引数として真偽値又は別の述語を返す手続き（述語）の形で与えられる。
【００３９】
例えば、図１０に示した重み付き有向グラフにおいて、「Ａ−Ｃ−Ｅ」という連続する３つのノードの組合せに対して例外的な重みが与えられるものとする。このとき、「「Ａ−Ｃ−Ｅ」というノードの並び」を検出するために、「「Ａ−Ｃ−Ｅ」の順に並んでいるノードであるか」という条件要請が与えられる。この条件要請は、ノードＥ以外のノードでは成立し得ないので、ノードＥ以外のノードは、この条件要請に対して偽を返す。ノードＥは、この条件要請に対して、「先行するノードは「Ａ−Ｃ」の順に並んでいるノードであるか」という別の述語を返す。ノードＥに先行するノードのうち、ノードＤはこの条件要請を満たさないので偽を返す。ノードＣはこの条件要請を満たし、この条件要請に対して、「先行するノードは「Ａ」の順に並んでいるノードであるか」という述語を返す。ノードＣに先行するノードのうち、ノードＡはこの条件要請を満たし、ノードＢは満たさない。
【００４０】
ノードＥが返した条件要請を満たしたノードＣは複製され、ノードＣ自身が返した述語の条件要請を満たすＣと、満たさないＣに区別される。すなわち、「Ａ」が先行するＣ（Ｃ１）と「Ａ」が先行しないＣ（Ｃ２）が区別される。このとき、ノードＣ１については、ノードＣ１に至るエッジのうち「Ａ」が先行しない「Ｂ−Ｃ１」が削除され、ノードＣ２については、「Ａ」が先行する「Ａ−Ｃ２」が削除される。さらに、同様にして、「Ａ−Ｃ」が先行するＥ（Ｅ１）と「Ａ−Ｃ」が先行しないＥ（Ｅ２）が区別される。このときも、ノードＥ１については、「Ａ−Ｃ」が先行しない「Ｄ−Ｅ１」が削除される。ノードＥ２については、「Ｃ２−Ｅ」も「Ｄ−Ｅ」も「Ａ−Ｃ」が先行しないので削除されない。こうして組み替えられた有向グラフを図１１に示す。
【００４１】
このようなアルゴリズムにより、経路の総数を変えることなく、「Ａ−Ｃ」が先行するＥと「Ａ−Ｃ」が先行しないＥを区別して、異なる重みを与えることができる。この場合、「Ａ−Ｃ−Ｅ」という連続する３つのノードの組合せに対して与えられる例外的な重みは、組合せの最後のノード「Ｅ２」の重みとして与えられる。
【００４２】
このようなアルゴリズムによれば、「Ａ−？−Ｅ」（ただし、？は任意の１ノード）という組合せに例外的な重みが与えられる場合も適切に有向グラフを組み替えることができる。この場合、ノードＥが「「Ａ−？−Ｅ」の順に並んでいるノードであるか」という条件要請に対して、「先行するノードは「Ａ−？」の順に並んでいるノードであるか」という述語を返し、この条件要請に対しては、Ｅに先行する任意のノードが「先行するノードは「Ａ」の順に並んでいるノードであるか」という述語を返すようにすればよい。
【００４３】
また、「Ａ−＊−Ｅ」（ただし、＊は任意の数のノード）という組合せに例外的な重みが与えられる場合、ノードＥが「「Ａ−＊−Ｅ」の順に並んでいるノードであるか」という条件要請に対して、「先行するノードは「Ａ−＊」の順に並んでいるノードであるか」という述語を返し、この条件要請に対しては、「Ａ」以外の任意のノードが「先行するノードは「Ａ−＊」の順に並んでいるノードであるか」という述語を再び返すようにすればよい。このようなワイルドカードを用いた条件要請は、結果として無限長の組合せを生み出すため、最初に一定の長さ限界を設定する従来の方法では扱うことができないが、本実施の形態の技術によれば、適切に扱うことができる。
【００４４】
上記の例では、先行する経路が条件を満たすか否かによってノードを区別したが、さらに、後続の経路が条件を満たすか否かによってノードを区別してもよい。すなわち、経路を順方向に解析する場合は、（１）先行する経路も後続の経路も条件を満たすノード、（２）先行する経路は条件を満たすが、後続の経路が条件を満たさないノード、（３）先行する経路が条件を満たさないノードの３つに区別し、経路を逆方向に解析する場合は、（１）後続の経路も先行する経路も条件を満たすノード、（２）後続の経路は条件を満たすが、先行する経路が条件を満たさないノード、（３）後続の経路が条件を満たさないノードの３つに区別する。
【００４５】
例えば、上記の例と同様に、図１０に示した有向グラフにおいて、「Ａ−Ｃ−Ｅ」という連続する３つのノードの組合せに対して例外的な重みが与えられる場合について考える。有向グラフの先頭から順方向に解析すると、まず、後続の経路がＣ−Ｅを含むＡ（Ａ１）と、後続の経路がＣ−Ｅを含まないＡ（Ａ２）が区別される。さらに、Ａが先行しＥが後続するＣ（Ｃ１）と、Ａが先行するがＥが後続しないＣ（Ｃ２）と、Ａが先行しないＣ（Ｃ３）が区別される。さらに、Ａ−Ｃが先行するＥ（Ｅ１）と、Ａ−Ｃが先行しないＥ（Ｅ３）が区別される。こうして組み替えられた有向グラフを図１２に示す。同様に、有向グラフの最後から逆方向に解析して組み替えられた有向グラフを図１３に示す。
【００４６】
このようなアルゴリズムにより、経路の総数を変えることなく、「Ａ−Ｃ−Ｅ」という経路を他の経路と分離して、異なる重みを与えることができる。この場合、「Ａ−Ｃ−Ｅ」という連続する３つのノードの組合せに対して与えられる例外的な重みは、組合せに含まれる任意のノード又はエッジに与えられてもよい。
【００４７】
図１４は、実施の形態に係るデータ入力装置１０の構成を示す。データ入力装置１０は、ユーザインタフェイス２０、想起ユニット３０、データ処理装置の一例である選択ユニット４０を備える。想起ユニット３０は、入力データ受付部３２、有向グラフ生成部３４、及び辞書保持部３６を含む。選択ユニット４０は、有向グラフ取得部４１、有向グラフ変形部４２、評価部４３、第１重み保持部４４、第２重み保持部４５、及び有向グラフ保持部４６を含む。これらの構成は、ハードウエアコンポーネントでいえば、任意のコンピュータのＣＰＵ、メモリ、メモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。
【００４８】
入力データ受付部３２は、ユーザがユーザインタフェイス２０を介して入力した文章の読みのデータを受け付ける。有向グラフ生成部３４は、入力データ受付部３２が受け付けた読みのデータから、辞書保持部３６に保持された辞書データを参照して、漢字仮名交じりの文章の有向グラフを生成する。辞書保持部３６は、単語の読み、品詞、対応する漢字があれば漢字を対応付けて格納した辞書を保持する。
【００４９】
図１５は、有向グラフ生成部３４が生成した有向グラフの例を示す。図１５は、「じんこうのあさがおせんせいのないしんそざいとして」という読みが入力されたときに生成される有向グラフの例を示す。実際には、もっと多くのノードを含むグラフが生成されることになるが、ここでは説明の簡略化のために省略している。
【００５０】
有向グラフ生成部３４は、入力された文章の読みの先頭から順に、「じ」、「じん」、「じんこ」、「じんこう」という読みで辞書を検索し、辞書に読みが登録されている単語を抽出してその単語の品詞を取得し、対応する漢字があれば漢字に変換して、ノードを生成する。この例では、「じんこう」という読みで、「人工」、「人口」、「沈香」、「神幸」の４つの名詞が登録されているため、それぞれに対応する４つのノードが生成される。つづいて、次の「の」という読みで、助詞の「の」が登録されているため、それに対応するノードが生成される。このようにして、先頭から順に単語を抽出してノードを生成していく。
【００５１】
ノードの重みとして、一般的な文章における単語の使用頻度に基づいたスコアが用いられてもよい。また、ユーザの変換履歴が反映されるように、ユーザが使用した単語のスコアを増加させてもよい。また、エッジの重みとして、一般的な文章における単語同士のつながり方の使用頻度に基づいたスコアが用いられてもよい。一般的な文章における品詞同士のつながり方の妥当性に基づいてスコアが与えられてもよい。
【００５２】
いったん有向グラフが生成されれば、あとは前述した最適経路問題を解けば、最適な変換候補を選択することができる。以降は、説明を分かりやすくするために、前述した電車の経路を示す有向グラフの例に戻って説明を続ける。
【００５３】
第１重み保持部４４は、有向グラフのノード又は２つのノードの間のエッジに与えられた重みを保持する。図１６は、第１重み保持部４４の内部データの例を示す。第１重み保持部４４には、エッジ欄７０、重み欄７１、ノード欄７２、重み欄７３が設けられており、エッジに与えられた重みと、ノードに与えられた重みが保持される。ノードやエッジの重みは、有向グラフが生成される際に与えられてもよい。この場合、ノードやエッジの重みは、辞書保持部３６などに保持されていてもよい。
【００５４】
第２重み保持部４５は、２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せに対して、第１重み保持部４４に保持されているそれぞれのノード又はエッジに与えられた重みから算出される重みとは異なる重みが与えられる場合に、その組合せに与えられた重みを保持する。図１７は、第２重み保持部４５の内部データの例を示す。第２重み保持部４５には、組合せ欄７４、重み欄７５が設けられており、ノードやエッジの組合せに対して例外的に与えられた重みが保持される。
【００５５】
有向グラフ取得部４１は、有向グラフ生成部３４により生成された有向グラフを取得する。有向グラフ保持部４６は、有向グラフ取得部４１が取得した有向グラフを保持する。図１８は、有向グラフ保持部４６の内部データの例を示す。有向グラフ保持部４６には、ノード欄８０、重み欄８１、入力エッジ欄８２、出力エッジ欄８３、及び最適経路欄８４が設けられている。ノード欄８０には、有向グラフを構成するノードを識別する情報が格納される。重み欄８１には、ノードに与えられた重みが格納される。入力エッジ欄８２は、始点欄８５と重み欄８６の組を複数含み、該当ノードを終点とするエッジの始点と、そのエッジの重みが格納される。出力エッジ欄８３は、終点欄８７と重み欄８８を複数含み、該当ノードを始点とするエッジの終点と、そのエッジの重みが格納される。前述したように、それぞれの重み欄には、有向グラフ生成部３４が有向グラフを生成したときに該当するノードやエッジの重みが格納されてもよいし、有向グラフ取得部４１が有向グラフ生成部３４から有向グラフを取得して有向グラフ保持部４６に格納するときに第１重み保持部４４を参照して該当するノードやエッジの重みを格納してもよい。最適経路欄８４は、始点欄８９及び重み欄９０を含み、評価部４３により選択された該当ノードまでの最適経路の直接先行ノードと、該当ノードまでの最適経路の重みが格納される。
【００５６】
有向グラフ変形部４２は、有向グラフ保持部４６に保持された有向グラフに、第２重み保持部４５に例外的な重みが保持されたノード又はエッジの組合せが含まれる場合、その組合せに含まれるノード又はエッジを経由する経路と、それ以外の経路とが区別されるように、有向グラフを変形する。有向グラフを変形するアルゴリズムは、上述した通りである。
【００５７】
評価部４３は、有向グラフ変形部４２により経路を追加された有向グラフにおける第１ノードから第２ノードへ至る経路を、第１重み保持部４４及び第２重み保持部４５から読み出された重みに基づいて評価する。評価部４３は、第１ノードから第２ノードへ至る複数の経路の中から、重みに基づいて最適な経路を選択する。
【００５８】
評価部４３は、図３で説明したように、ビタビアルゴリズムに基づき、第１ノードから第２ノードへ至る経路に含まれるそれぞれのノードについて、第１ノードに近いノードから順に、第１ノードからそのノードへ至る最適な経路を重みに基づいて選択していくことにより、第１ノードから第２ノードへ至る最適な経路を選択する。
【００５９】
評価部４３は、第１ノードからあるノードへ至る最適な経路を選択する際に、該当ノードを終点とする１以上のエッジの中から、それぞれのエッジに与えられた重みと、第１ノードからそれぞれのエッジの始点のノードへ至る最適な経路の重みとに基づいて、第１ノードから該当ノードへ至る最適な経路を与えるエッジを選択する。そして、第１ノードから選択されたエッジの始点のノードへ至る最適な経路の重みと、選択されたエッジ又は該当ノードに与えられた重みに基づいて、第１ノードから該当ノードへ至る最適な経路の重みを算出する。経路の重みは、例えば、その経路に含まれるエッジとノードに与えられた重みを加算したものであってもよい。また、その他の算術式により重みが算出されてもよい。
【００６０】
本実施の形態の方法によれば、有向グラフを生成した後であっても、例外的な重みが与えられたエッジやノードの組合せを有向グラフに追加することができるので、柔軟に条件を設定することができる。また、例外的な条件が与えられる場合であっても、ビタビアルゴリズムにより最適経路を求めることができるので、計算量や計算時間を大幅に軽減することができる。経路の変形は、有向グラフ生成部３４が有向グラフを生成している途中に行ってもよいし、評価部４３が経路の重みを評価している途中に行ってもよい。
【００６１】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【図面の簡単な説明】
【００６２】
【図１】有向グラフの例を示す図である。
【図２】図１に示した有向グラフの各ノード及び各エッジに与えられた重みを示す図である。
【図３】図２に示した重み付き有向グラフの最適経路をビタビアルゴリズムにより解く方法について説明するための図である。
【図４】連続する３つのノードの組合せに対して例外的な重みが与えられることを考慮して生成された有向グラフの例を示す図である。
【図５】連続する４つのノードの組合せに対して例外的な重みが与えられることを考慮して生成された有向グラフの例を示す図である。
【図６】図１に示した有向グラフにおいて、連続する３つのノードの組合せに対して例外的な重みが与えられた場合に、ビタビアルゴリズムにより最適経路を求めるための有向グラフを示す図である。
【図７】図６に示した有向グラフの各エッジ及びノードに重みを付与し、ビタビアルゴリズムにより最適経路を求めた様子を示す図である。
【図８】２つのエッジの組合せに対して与えられた例外的な重みを考慮した有向グラフを示す図である。
【図９】連続しない２つのノードの組合せに対して与えられた例外的な重みを考慮した有向グラフを示す図である。
【図１０】有向グラフの例を示す図である。
【図１１】実施の形態に係るアルゴリズムにより変形された有向グラフの例を示す図である。
【図１２】実施の形態に係るアルゴリズムにより変形された有向グラフの例を示す図である。
【図１３】実施の形態に係るアルゴリズムにより変形された有向グラフの例を示す図である。
【図１４】実施の形態に係るデータ入力装置の構成を示す図である。
【図１５】有向グラフ生成部が生成した有向グラフの例を示す図である。
【図１６】第１重み保持部の内部データの例を示す図である。
【図１７】第２重み保持部の内部データの例を示す図である。
【図１８】有向グラフ保持部の内部データの例を示す図である。
【符号の説明】
【００６３】
１０ データ入力装置、２０ ユーザインタフェイス、３０ 想起ユニット、３２ 入力データ受付部、３４ 有向グラフ生成部、３６ 辞書保持部、４０ 選択ユニット、４１ 有向グラフ取得部、４２ 有向グラフ変形部、４３ 評価部、４４ 第１重み保持部、４５ 第２重み保持部、４６ 有向グラフ保持部。
【技術分野】
【０００１】
本発明は、データ処理技術に関し、特に、重み付き有向グラフの経路を評価するデータ処理装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
日本語の文字列を入力する際に、ユーザが入力した読みを漢字に変換して入力するプログラムが広く利用されている（例えば、特許文献１参照）。
【特許文献１】特開２００４−１３９４０２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明者らは、ユーザから入力された文章の読みを漢字交じりの文章に変換する際の精度を向上させるために、漢字変換辞書を参照して、入力された文章の読みから漢字交じりの単語により構成される有向グラフを作成し、有向グラフのノード、すなわち単語と、ノード間のエッジ、すなわち単語のつながり方に対してスコアを付与し、重み付き有向グラフの最適経路問題を解くことにより最適な変換候補を選択する技術を開発している。
【０００４】
より早く、より精確な変換候補を選択するために、重み付き有向グラフの最適経路をより効率良く計算する技術が求められている。
【０００５】
本発明はこうした状況に鑑みてなされたものであり、その目的は、データ入力の利便性を向上させる技術を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は、データ処理装置に関する。このデータ処理装置は、有向グラフのノード又は２つのノードの間のエッジに与えられた重みを保持する第１重み保持部と、特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記第１重み保持部に保持されている重みとは異なる重みが与えられる場合に、前記組合せに含まれるノード又はエッジに与えられた重みを保持する第２重み保持部と、前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形する有向グラフ変形部と、前記有向グラフ変形部により変形された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記第１重み保持部及び前記第２重み保持部から読み出された重みに基づいて評価する評価部と、を備えることを特徴とする。
【０００７】
前記有向グラフ変形部は、複製したノードのうち一方のノードについては、そのノードに至るエッジのうち前記対象経路に含まれないエッジを削除し、他方のノードについては、そのノードに至るエッジのうち前記対象経路に含まれるエッジを削除してもよい。
【０００８】
前記第１重み保持部に保持されている重みとは異なる重みは、前記対象経路の最後のノードに与えられてもよい。
【０００９】
前記有向グラフ変形部は、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれるが、そのノードに続く経路が前記対象経路に含まれないノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形してもよい。
【００１０】
前記有向グラフ変形部は、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードを複製し、そのノードに続く経路が前記対象経路に含まれるノードと、そのノードに続く経路が前記対象経路に含まれるが、そのノードに至る経路が前記対象経路に含まれないノードと、そのノードに続く経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形してもよい。
【００１１】
本発明の別の態様は、データ処理方法に関する。このデータ処理方法は、有向グラフを取得するステップと、前記有向グラフのノード又は２つのノードの間のエッジに重みを付与するステップと、特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記付与するステップで与えられた重みとは異なる重みが与えられている場合、前記有向グラフに前記組合せが含まれるか否かを判定するステップと、前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形するステップと、経路が追加された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記重みに基づいて評価するステップと、を備えることを特徴とする。
【００１２】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１３】
本発明によれば、データ入力の利便性を向上させる技術を提供することができる。
【発明を実施するための最良の形態】
【００１４】
有向グラフのノードや、２つのノードの間のエッジに重みが与えられた重み付き有向グラフの最適経路問題は、乗物の乗換案内、ワークフローの管理、自然言語処理など、多くの分野で重要な技術的意義を有している。重み付き有向グラフの最適経路問題を解くためのアルゴリズムに、ビタビ（Viterbi）アルゴリズムがある。
【００１５】
図１は、有向グラフの例を示す。以降の説明を分かりやすくするために、図１に示した有向グラフは、出発駅である第１ノードＸから到着駅である第２ノードＹへ至る電車の経路を示し、ノードＡ〜Ｊは乗継駅を示すものとする。
【００１６】
図２は、図１に示した有向グラフの各ノード及び各エッジに与えられた重みを示す。この例では、各エッジの重みとして、駅間の所要時間が、各ノードの重みとして、乗継駅における乗り継ぎに要する時間が、それぞれ与えられている。ここで、出発駅Ｘから到着駅Ｙへ至る経路のうち、最も所要時間の短い最短経路を判別する方法について説明する。
【００１７】
図３は、図２に示した重み付き有向グラフの最適経路をビタビアルゴリズムにより解く方法について説明するための図である。ビタビアルゴリズムでは、出発駅に近いノードから順に、出発駅から各乗継駅へ至る最短経路を段階的に求めていく。
【００１８】
まず、出発駅であるＸ駅からＡ駅へ至る経路は１通りしかないので、Ｘ駅からＡ駅へ至る最短経路が決定される。この最短経路を通過したときのＸ駅からＡ駅までの所要時間は、「４」分である。同様に、Ｘ駅からＢ駅へ至る経路も１通りしかないので、Ｘ駅からＢ駅へ至る最短経路が決定され、所要時間は「３」分となる。
【００１９】
次に、Ｘ駅からＣ駅へ至る最短経路を算出する。Ｃ駅を終点とするエッジは、Ａ−ＣとＢ−Ｃの２本ある。Ｘ駅からＡ駅を経由してＣ駅へ至る経路の最短所要時間は、Ｘ駅からＡ駅までの最短所要時間「４」分に、Ａ駅での乗り継ぎ時間「１」分と、Ａ駅からＣ駅までの所要時間「８」分とを加算した「１３」分である。同様に、Ｘ駅からＢ駅を経由してＣ駅へ至る経路の最短所要時間は、Ｘ駅からＢ駅までの最短所要時間「３」分に、Ｂ駅での乗り継ぎ時間「２」分と、Ｂ駅からＣ駅までの所要時間「６」分を加算した「１１」分である。したがって、Ｘ駅からＣ駅へ至る最短経路は、Ｂ駅を経由する経路であり、その所要時間は「１１」分である。
【００２０】
Ｘ駅からＤ駅へ至る最短経路は、Ｄ駅を終点とするエッジが１本しかないので、そのエッジの始点であるＡ駅を経由する経路であり、その所要時間は「１１」分である。同様に、Ｘ駅からＥ駅へ至る最短経路は、Ｂ駅を経由する経路であり、その所要時間は「１２」分である。
【００２１】
このように、ある駅までの最短経路は、そのノードを終点とする１以上のエッジの中から、それぞれのエッジの始点の駅までの最短所要時間と、エッジの始点の駅における乗り継ぎ時間と、エッジの始点の駅から当該駅までの所要時間とを加算した所要時間が最も短いものを選択することにより得られる。
【００２２】
同様にして、到着駅Ｙまでの全ての駅について最短経路と最短所要時間を求めることができる。最後に、到着駅Ｙを終点とするエッジの中から最短経路を与えるエッジを求めると、直前の駅はＪ駅となるので、Ｊ駅、Ｈ駅、Ｇ駅、Ｅ駅、Ｂ駅、Ｘ駅と直前の駅を順に辿っていくことにより、最短経路が判明する。
【００２３】
以上のような方法により、Ｘ駅からＹ駅へ至る全ての経路の所要時間を算出して最短経路を判定する方法に比べて、計算量を飛躍的に低減することができる。特に、漢字変換や形態素解析などの自然言語処理の分野では、文章の長さが長くなると、文章を構成する単語の候補、すなわちノードの数が膨大になるので、このような方法を採用することによる計算量の低減が不可欠である。
【００２４】
ビタビアルゴリズムは、あるノードまでの最適経路は、そのノードの直前のノードまでの最適経路とは独立に決定可能であることを前提としている。つまり、あるノードまでの最適経路は、過去に遡ることなく、直前の最適結果に基づいて決まる場合に適用可能である。
【００２５】
ところが、現実には、ある特定のエッジやノードの組合せに対して、例外的な条件が設定される場合がある。例えば、Ｄ駅からＧ駅を経由してＨ駅へ至る路線には急行電車が運行されており、Ｄ駅からＧ駅を経由してＨ駅へ至る経路の所要時間は、Ｄ駅からＧ駅への所要時間とＧ駅からＨ駅への所要時間との単純な合計よりも短くなるという条件があるとする。このような例外的な条件は、図２に示した重み付き有向グラフでは表現できない。
【００２６】
このように、連続する２つのノードの組合せに対して、ノードやエッジの重みが与えられるだけでなく、３以上のノードの組合せなどに対して、例外的な重みが与えられる場合、その組合せに対する例外的な重みを設定可能とするために、その組合せを通過する経路を別に設ける必要がある。
【００２７】
図４は、連続する３つのノードの組合せに対して例外的な重みが与えられることを考慮して生成された有向グラフの例を示す。図２の有向グラフでは、例えばＦへ至る経路として、Ａ−Ｃ−Ｆという経路とＢ−Ｃ−Ｆという経路は区別しない。これは、Ｃまでは最短経路を通っていることが前提となっており、Ａを経由したかＢを経由したかは、Ｆまでの最短経路を決定する際に考慮しないからである。これに対し、図４の有向グラフでは、Ａ−Ｃ−Ｆという経路とＢ−Ｃ−Ｆという経路を別の経路として表現するために、Ｃ及びＦのノードを２つ設けている。これにより、Ａ及びＣを経由してＦへ至る経路と、Ｂ及びＣを経由してＦへ至る経路を区別し、異なる重みを与えることができる。同様にして、他のノードについても、２つ前のノードが異なる経路を区別するために複数のノードを設けている。
【００２８】
図５は、連続する４つのノードの組合せに対して例外的な重みが与えられることを考慮して生成された有向グラフの例を示す。図４の有向グラフでは、Ａ−Ｃ−Ｆ−ＨとＢ−Ｃ−Ｆ−Ｈという経路は区別していなかったが、図５の有向グラフでは、３つ前のノードが異なっている経路も区別するので、Ａ−Ｃ−Ｆ−Ｈに対応するＨとＢ−Ｃ−Ｆ−Ｈに対応するＨを設けている。
【００２９】
図４及び図５に示した有向グラフでは、連続する３以上のノードの組合せに対して与えられた例外的な重みを考慮して最適経路を求めることができるが、例外的な重みが与えられる組合せに、連続するいくつのノードが含まれるかが予め分かっていないと、有向グラフを生成することができない。例えば、連続する３つのノードの組合せを考慮すると、図５に示した有向グラフを生成すればよいが、連続する４つのノードの組合せに対して新たに例外的な重みが与えられた場合は、図５に示した有向グラフを生成し直す必要がある。
【００３０】
また、自然言語処理に応用する場合など、元の有向グラフの規模が大きい場合には、追加すべき経路の数が膨大になり、計算量が飛躍的に増大して、計算速度が低下するおそれがある。
【００３１】
本実施の形態では、重み付き有向グラフにおいて、２以上のエッジ、３以上のノード、連続しない２つのノードなどの組合せに対して例外的な重みが与えられる場合に、効率良く最適経路を求める技術を提案する。
【００３２】
図６は、図１に示した有向グラフにおいて、連続する３つのノードの組合せに対して例外的な重みが与えられた場合に、ビタビアルゴリズムにより最適経路を求めるための有向グラフを示す。図６では、Ｄ−Ｇ−Ｈという連続する３つのノードの組合せに対して例外的な重みを与えるために、Ｄ−Ｇ−Ｈという経路を有向グラフにもう１つ追加している。具体的には、Ｄ−Ｇ−Ｈという組合せの最初のノードＤから分岐して、途中のノードＧを経由し、最後のノードＨまで至る経路を複製する。
【００３３】
図７は、図６に示した有向グラフの各エッジ及びノードに重みを付与し、ビタビアルゴリズムにより最適経路を求めた様子を示す。図７では、Ｄ駅−Ｇ駅−Ｈ駅という経路には急行列車が運行されているため、Ｄ駅−Ｇ駅−Ｈ駅という経路を通過する場合には、Ｄ駅−Ｇ駅間の所要時間が４分から１分に短縮される例が示されている。図中、２つあるノードＨのうち、上側のノードＨは例外的な重みを考慮せずにノードＨまでの最適経路を求めた結果を示し、下側のノードＨは経路Ｄ−Ｇ−Ｈに対して与えられた例外的な重みを考慮した場合のノードＨまでの最適経路を求めた結果を示す。
【００３４】
図８は、２つのエッジの組合せに対して与えられた例外的な重みを考慮した有向グラフを示す。図８では、エッジＡ−ＤとエッジＨ−Ｊの組合せに対して例外的な重みが与えられている。例えば、Ａ駅からＤ駅までの路線とＨ駅からＪ駅までの路線が同一の主体により運営されているために、これらの路線を使うと割引料金が適用されるような例が想定される。この場合、エッジＡ−ＤとエッジＨ−Ｊを含む経路を元の有向グラフから抽出し、抽出した経路を有向グラフに追加する。これにより、エッジＡ−ＤとエッジＡ−Ｊの両方を通過する経路を有向グラフの中に新たに設け、その経路に対して例外的な重みを付与することができる。
【００３５】
図９は、連続しない２つのノードの組合せに対して与えられた例外的な重みを考慮した有向グラフを示す。図９では、ノードＤとノードＨの組合せに対して例外的な重みが与えられている。例えば、ひらがなで入力された文章を漢字仮名交じり文に変換するときに、「鳥」という単語が先行する場合は「とぶ」というひらがなに対応する変換候補として「飛ぶ」という候補のスコアを高くするなどといった共起用例が想定される。この場合、ノードＤとノードＨの間の経路を元の有向グラフから抽出し、抽出した経路を有向グラフに追加する。これにより、ノードＤの存在を考慮しないノードＨのスコアと、ノードＤが先行する場合のノードＨのスコアを区別して表現することができる。
【００３６】
このようにして、重み付き有向グラフに、例外的な重みが与えられた経路を追加することにより、計算量の増大を最小限に抑えつつ、直前のノードではなく過去のノードまで遡って参照しなければならないような例外的な条件をも考慮して最適経路を求めることができる。
【００３７】
上記の例では、例外的な重みが与えられた経路を有向グラフに追加したが、この場合、実質的に同じ経路が有向グラフ中に重複して存在することになる。最適経路を探索する際には、このことは問題にならないが、２番目以降の経路を算出する際に、実質的には同じ経路であるのに別の経路として報告してしまうことがあるため、ｎ−ベスト探索のアルゴリズムが破綻するおそれがある。したがって、ｎ−ベスト探索を行う際には、ノード又はエッジを追加しても、経路の総数を変えない経路の組み替えが必要となる。このようなアルゴリズムについて更に説明する。
【００３８】
有向グラフを変形する際に、述語論理に基づいたプログラミング言語等を利用してもよい。この場合、例外的な重みは、ノードに対する条件要請として与えられる。この条件要請は、ノードを引数として真偽値又は別の述語を返す手続き（述語）の形で与えられる。
【００３９】
例えば、図１０に示した重み付き有向グラフにおいて、「Ａ−Ｃ−Ｅ」という連続する３つのノードの組合せに対して例外的な重みが与えられるものとする。このとき、「「Ａ−Ｃ−Ｅ」というノードの並び」を検出するために、「「Ａ−Ｃ−Ｅ」の順に並んでいるノードであるか」という条件要請が与えられる。この条件要請は、ノードＥ以外のノードでは成立し得ないので、ノードＥ以外のノードは、この条件要請に対して偽を返す。ノードＥは、この条件要請に対して、「先行するノードは「Ａ−Ｃ」の順に並んでいるノードであるか」という別の述語を返す。ノードＥに先行するノードのうち、ノードＤはこの条件要請を満たさないので偽を返す。ノードＣはこの条件要請を満たし、この条件要請に対して、「先行するノードは「Ａ」の順に並んでいるノードであるか」という述語を返す。ノードＣに先行するノードのうち、ノードＡはこの条件要請を満たし、ノードＢは満たさない。
【００４０】
ノードＥが返した条件要請を満たしたノードＣは複製され、ノードＣ自身が返した述語の条件要請を満たすＣと、満たさないＣに区別される。すなわち、「Ａ」が先行するＣ（Ｃ１）と「Ａ」が先行しないＣ（Ｃ２）が区別される。このとき、ノードＣ１については、ノードＣ１に至るエッジのうち「Ａ」が先行しない「Ｂ−Ｃ１」が削除され、ノードＣ２については、「Ａ」が先行する「Ａ−Ｃ２」が削除される。さらに、同様にして、「Ａ−Ｃ」が先行するＥ（Ｅ１）と「Ａ−Ｃ」が先行しないＥ（Ｅ２）が区別される。このときも、ノードＥ１については、「Ａ−Ｃ」が先行しない「Ｄ−Ｅ１」が削除される。ノードＥ２については、「Ｃ２−Ｅ」も「Ｄ−Ｅ」も「Ａ−Ｃ」が先行しないので削除されない。こうして組み替えられた有向グラフを図１１に示す。
【００４１】
このようなアルゴリズムにより、経路の総数を変えることなく、「Ａ−Ｃ」が先行するＥと「Ａ−Ｃ」が先行しないＥを区別して、異なる重みを与えることができる。この場合、「Ａ−Ｃ−Ｅ」という連続する３つのノードの組合せに対して与えられる例外的な重みは、組合せの最後のノード「Ｅ２」の重みとして与えられる。
【００４２】
このようなアルゴリズムによれば、「Ａ−？−Ｅ」（ただし、？は任意の１ノード）という組合せに例外的な重みが与えられる場合も適切に有向グラフを組み替えることができる。この場合、ノードＥが「「Ａ−？−Ｅ」の順に並んでいるノードであるか」という条件要請に対して、「先行するノードは「Ａ−？」の順に並んでいるノードであるか」という述語を返し、この条件要請に対しては、Ｅに先行する任意のノードが「先行するノードは「Ａ」の順に並んでいるノードであるか」という述語を返すようにすればよい。
【００４３】
また、「Ａ−＊−Ｅ」（ただし、＊は任意の数のノード）という組合せに例外的な重みが与えられる場合、ノードＥが「「Ａ−＊−Ｅ」の順に並んでいるノードであるか」という条件要請に対して、「先行するノードは「Ａ−＊」の順に並んでいるノードであるか」という述語を返し、この条件要請に対しては、「Ａ」以外の任意のノードが「先行するノードは「Ａ−＊」の順に並んでいるノードであるか」という述語を再び返すようにすればよい。このようなワイルドカードを用いた条件要請は、結果として無限長の組合せを生み出すため、最初に一定の長さ限界を設定する従来の方法では扱うことができないが、本実施の形態の技術によれば、適切に扱うことができる。
【００４４】
上記の例では、先行する経路が条件を満たすか否かによってノードを区別したが、さらに、後続の経路が条件を満たすか否かによってノードを区別してもよい。すなわち、経路を順方向に解析する場合は、（１）先行する経路も後続の経路も条件を満たすノード、（２）先行する経路は条件を満たすが、後続の経路が条件を満たさないノード、（３）先行する経路が条件を満たさないノードの３つに区別し、経路を逆方向に解析する場合は、（１）後続の経路も先行する経路も条件を満たすノード、（２）後続の経路は条件を満たすが、先行する経路が条件を満たさないノード、（３）後続の経路が条件を満たさないノードの３つに区別する。
【００４５】
例えば、上記の例と同様に、図１０に示した有向グラフにおいて、「Ａ−Ｃ−Ｅ」という連続する３つのノードの組合せに対して例外的な重みが与えられる場合について考える。有向グラフの先頭から順方向に解析すると、まず、後続の経路がＣ−Ｅを含むＡ（Ａ１）と、後続の経路がＣ−Ｅを含まないＡ（Ａ２）が区別される。さらに、Ａが先行しＥが後続するＣ（Ｃ１）と、Ａが先行するがＥが後続しないＣ（Ｃ２）と、Ａが先行しないＣ（Ｃ３）が区別される。さらに、Ａ−Ｃが先行するＥ（Ｅ１）と、Ａ−Ｃが先行しないＥ（Ｅ３）が区別される。こうして組み替えられた有向グラフを図１２に示す。同様に、有向グラフの最後から逆方向に解析して組み替えられた有向グラフを図１３に示す。
【００４６】
このようなアルゴリズムにより、経路の総数を変えることなく、「Ａ−Ｃ−Ｅ」という経路を他の経路と分離して、異なる重みを与えることができる。この場合、「Ａ−Ｃ−Ｅ」という連続する３つのノードの組合せに対して与えられる例外的な重みは、組合せに含まれる任意のノード又はエッジに与えられてもよい。
【００４７】
図１４は、実施の形態に係るデータ入力装置１０の構成を示す。データ入力装置１０は、ユーザインタフェイス２０、想起ユニット３０、データ処理装置の一例である選択ユニット４０を備える。想起ユニット３０は、入力データ受付部３２、有向グラフ生成部３４、及び辞書保持部３６を含む。選択ユニット４０は、有向グラフ取得部４１、有向グラフ変形部４２、評価部４３、第１重み保持部４４、第２重み保持部４５、及び有向グラフ保持部４６を含む。これらの構成は、ハードウエアコンポーネントでいえば、任意のコンピュータのＣＰＵ、メモリ、メモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。
【００４８】
入力データ受付部３２は、ユーザがユーザインタフェイス２０を介して入力した文章の読みのデータを受け付ける。有向グラフ生成部３４は、入力データ受付部３２が受け付けた読みのデータから、辞書保持部３６に保持された辞書データを参照して、漢字仮名交じりの文章の有向グラフを生成する。辞書保持部３６は、単語の読み、品詞、対応する漢字があれば漢字を対応付けて格納した辞書を保持する。
【００４９】
図１５は、有向グラフ生成部３４が生成した有向グラフの例を示す。図１５は、「じんこうのあさがおせんせいのないしんそざいとして」という読みが入力されたときに生成される有向グラフの例を示す。実際には、もっと多くのノードを含むグラフが生成されることになるが、ここでは説明の簡略化のために省略している。
【００５０】
有向グラフ生成部３４は、入力された文章の読みの先頭から順に、「じ」、「じん」、「じんこ」、「じんこう」という読みで辞書を検索し、辞書に読みが登録されている単語を抽出してその単語の品詞を取得し、対応する漢字があれば漢字に変換して、ノードを生成する。この例では、「じんこう」という読みで、「人工」、「人口」、「沈香」、「神幸」の４つの名詞が登録されているため、それぞれに対応する４つのノードが生成される。つづいて、次の「の」という読みで、助詞の「の」が登録されているため、それに対応するノードが生成される。このようにして、先頭から順に単語を抽出してノードを生成していく。
【００５１】
ノードの重みとして、一般的な文章における単語の使用頻度に基づいたスコアが用いられてもよい。また、ユーザの変換履歴が反映されるように、ユーザが使用した単語のスコアを増加させてもよい。また、エッジの重みとして、一般的な文章における単語同士のつながり方の使用頻度に基づいたスコアが用いられてもよい。一般的な文章における品詞同士のつながり方の妥当性に基づいてスコアが与えられてもよい。
【００５２】
いったん有向グラフが生成されれば、あとは前述した最適経路問題を解けば、最適な変換候補を選択することができる。以降は、説明を分かりやすくするために、前述した電車の経路を示す有向グラフの例に戻って説明を続ける。
【００５３】
第１重み保持部４４は、有向グラフのノード又は２つのノードの間のエッジに与えられた重みを保持する。図１６は、第１重み保持部４４の内部データの例を示す。第１重み保持部４４には、エッジ欄７０、重み欄７１、ノード欄７２、重み欄７３が設けられており、エッジに与えられた重みと、ノードに与えられた重みが保持される。ノードやエッジの重みは、有向グラフが生成される際に与えられてもよい。この場合、ノードやエッジの重みは、辞書保持部３６などに保持されていてもよい。
【００５４】
第２重み保持部４５は、２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せに対して、第１重み保持部４４に保持されているそれぞれのノード又はエッジに与えられた重みから算出される重みとは異なる重みが与えられる場合に、その組合せに与えられた重みを保持する。図１７は、第２重み保持部４５の内部データの例を示す。第２重み保持部４５には、組合せ欄７４、重み欄７５が設けられており、ノードやエッジの組合せに対して例外的に与えられた重みが保持される。
【００５５】
有向グラフ取得部４１は、有向グラフ生成部３４により生成された有向グラフを取得する。有向グラフ保持部４６は、有向グラフ取得部４１が取得した有向グラフを保持する。図１８は、有向グラフ保持部４６の内部データの例を示す。有向グラフ保持部４６には、ノード欄８０、重み欄８１、入力エッジ欄８２、出力エッジ欄８３、及び最適経路欄８４が設けられている。ノード欄８０には、有向グラフを構成するノードを識別する情報が格納される。重み欄８１には、ノードに与えられた重みが格納される。入力エッジ欄８２は、始点欄８５と重み欄８６の組を複数含み、該当ノードを終点とするエッジの始点と、そのエッジの重みが格納される。出力エッジ欄８３は、終点欄８７と重み欄８８を複数含み、該当ノードを始点とするエッジの終点と、そのエッジの重みが格納される。前述したように、それぞれの重み欄には、有向グラフ生成部３４が有向グラフを生成したときに該当するノードやエッジの重みが格納されてもよいし、有向グラフ取得部４１が有向グラフ生成部３４から有向グラフを取得して有向グラフ保持部４６に格納するときに第１重み保持部４４を参照して該当するノードやエッジの重みを格納してもよい。最適経路欄８４は、始点欄８９及び重み欄９０を含み、評価部４３により選択された該当ノードまでの最適経路の直接先行ノードと、該当ノードまでの最適経路の重みが格納される。
【００５６】
有向グラフ変形部４２は、有向グラフ保持部４６に保持された有向グラフに、第２重み保持部４５に例外的な重みが保持されたノード又はエッジの組合せが含まれる場合、その組合せに含まれるノード又はエッジを経由する経路と、それ以外の経路とが区別されるように、有向グラフを変形する。有向グラフを変形するアルゴリズムは、上述した通りである。
【００５７】
評価部４３は、有向グラフ変形部４２により経路を追加された有向グラフにおける第１ノードから第２ノードへ至る経路を、第１重み保持部４４及び第２重み保持部４５から読み出された重みに基づいて評価する。評価部４３は、第１ノードから第２ノードへ至る複数の経路の中から、重みに基づいて最適な経路を選択する。
【００５８】
評価部４３は、図３で説明したように、ビタビアルゴリズムに基づき、第１ノードから第２ノードへ至る経路に含まれるそれぞれのノードについて、第１ノードに近いノードから順に、第１ノードからそのノードへ至る最適な経路を重みに基づいて選択していくことにより、第１ノードから第２ノードへ至る最適な経路を選択する。
【００５９】
評価部４３は、第１ノードからあるノードへ至る最適な経路を選択する際に、該当ノードを終点とする１以上のエッジの中から、それぞれのエッジに与えられた重みと、第１ノードからそれぞれのエッジの始点のノードへ至る最適な経路の重みとに基づいて、第１ノードから該当ノードへ至る最適な経路を与えるエッジを選択する。そして、第１ノードから選択されたエッジの始点のノードへ至る最適な経路の重みと、選択されたエッジ又は該当ノードに与えられた重みに基づいて、第１ノードから該当ノードへ至る最適な経路の重みを算出する。経路の重みは、例えば、その経路に含まれるエッジとノードに与えられた重みを加算したものであってもよい。また、その他の算術式により重みが算出されてもよい。
【００６０】
本実施の形態の方法によれば、有向グラフを生成した後であっても、例外的な重みが与えられたエッジやノードの組合せを有向グラフに追加することができるので、柔軟に条件を設定することができる。また、例外的な条件が与えられる場合であっても、ビタビアルゴリズムにより最適経路を求めることができるので、計算量や計算時間を大幅に軽減することができる。経路の変形は、有向グラフ生成部３４が有向グラフを生成している途中に行ってもよいし、評価部４３が経路の重みを評価している途中に行ってもよい。
【００６１】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【図面の簡単な説明】
【００６２】
【図１】有向グラフの例を示す図である。
【図２】図１に示した有向グラフの各ノード及び各エッジに与えられた重みを示す図である。
【図３】図２に示した重み付き有向グラフの最適経路をビタビアルゴリズムにより解く方法について説明するための図である。
【図４】連続する３つのノードの組合せに対して例外的な重みが与えられることを考慮して生成された有向グラフの例を示す図である。
【図５】連続する４つのノードの組合せに対して例外的な重みが与えられることを考慮して生成された有向グラフの例を示す図である。
【図６】図１に示した有向グラフにおいて、連続する３つのノードの組合せに対して例外的な重みが与えられた場合に、ビタビアルゴリズムにより最適経路を求めるための有向グラフを示す図である。
【図７】図６に示した有向グラフの各エッジ及びノードに重みを付与し、ビタビアルゴリズムにより最適経路を求めた様子を示す図である。
【図８】２つのエッジの組合せに対して与えられた例外的な重みを考慮した有向グラフを示す図である。
【図９】連続しない２つのノードの組合せに対して与えられた例外的な重みを考慮した有向グラフを示す図である。
【図１０】有向グラフの例を示す図である。
【図１１】実施の形態に係るアルゴリズムにより変形された有向グラフの例を示す図である。
【図１２】実施の形態に係るアルゴリズムにより変形された有向グラフの例を示す図である。
【図１３】実施の形態に係るアルゴリズムにより変形された有向グラフの例を示す図である。
【図１４】実施の形態に係るデータ入力装置の構成を示す図である。
【図１５】有向グラフ生成部が生成した有向グラフの例を示す図である。
【図１６】第１重み保持部の内部データの例を示す図である。
【図１７】第２重み保持部の内部データの例を示す図である。
【図１８】有向グラフ保持部の内部データの例を示す図である。
【符号の説明】
【００６３】
１０ データ入力装置、２０ ユーザインタフェイス、３０ 想起ユニット、３２ 入力データ受付部、３４ 有向グラフ生成部、３６ 辞書保持部、４０ 選択ユニット、４１ 有向グラフ取得部、４２ 有向グラフ変形部、４３ 評価部、４４ 第１重み保持部、４５ 第２重み保持部、４６ 有向グラフ保持部。
【特許請求の範囲】
【請求項１】
有向グラフのノード又は２つのノードの間のエッジに与えられた重みを保持する第１重み保持部と、
特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記第１重み保持部に保持されている重みとは異なる重みが与えられる場合に、前記組合せに含まれるノード又はエッジに与えられた重みを保持する第２重み保持部と、
前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形する有向グラフ変形部と、
前記有向グラフ変形部により変形された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記第１重み保持部及び前記第２重み保持部から読み出された重みに基づいて評価する評価部と、
を備えることを特徴とするデータ処理装置。
【請求項２】
前記有向グラフ変形部は、複製したノードのうち一方のノードについては、そのノードに至るエッジのうち前記対象経路に含まれないエッジを削除し、他方のノードについては、そのノードに至るエッジのうち前記対象経路に含まれるエッジを削除することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記第１重み保持部に保持されている重みとは異なる重みは、前記対象経路の最後のノードに与えられることを特徴とする請求項１又は２に記載のデータ処理装置。
【請求項４】
前記有向グラフ変形部は、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれるが、そのノードに続く経路が前記対象経路に含まれないノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形することを特徴とする請求項１又は２に記載のデータ処理装置。
【請求項５】
前記有向グラフ変形部は、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードを複製し、そのノードに続く経路が前記対象経路に含まれるノードと、そのノードに続く経路が前記対象経路に含まれるが、そのノードに至る経路が前記対象経路に含まれないノードと、そのノードに続く経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形することを特徴とする請求項１又は２に記載のデータ処理装置。
【請求項６】
有向グラフを取得するステップと、
前記有向グラフのノード又は２つのノードの間のエッジに重みを付与するステップと、
特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記付与するステップで与えられた重みとは異なる重みが与えられている場合、前記有向グラフに前記組合せが含まれるか否かを判定するステップと、
前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形するステップと、
経路が追加された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記重みに基づいて評価するステップと、
を備えることを特徴とするデータ処理方法。
【請求項７】
有向グラフを取得する機能と、
前記有向グラフのノード又は２つのノードの間のエッジに重みを付与する機能と、
特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記付与する機能で与えられた重みとは異なる重みが与えられている場合、前記有向グラフに前記組合せが含まれるか否かを判定する機能と、
前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形する機能と、
経路が追加された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記重みに基づいて評価する機能と、
をコンピュータに実現させることを特徴とするデータ処理プログラム。
【請求項１】
有向グラフのノード又は２つのノードの間のエッジに与えられた重みを保持する第１重み保持部と、
特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記第１重み保持部に保持されている重みとは異なる重みが与えられる場合に、前記組合せに含まれるノード又はエッジに与えられた重みを保持する第２重み保持部と、
前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形する有向グラフ変形部と、
前記有向グラフ変形部により変形された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記第１重み保持部及び前記第２重み保持部から読み出された重みに基づいて評価する評価部と、
を備えることを特徴とするデータ処理装置。
【請求項２】
前記有向グラフ変形部は、複製したノードのうち一方のノードについては、そのノードに至るエッジのうち前記対象経路に含まれないエッジを削除し、他方のノードについては、そのノードに至るエッジのうち前記対象経路に含まれるエッジを削除することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記第１重み保持部に保持されている重みとは異なる重みは、前記対象経路の最後のノードに与えられることを特徴とする請求項１又は２に記載のデータ処理装置。
【請求項４】
前記有向グラフ変形部は、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれるが、そのノードに続く経路が前記対象経路に含まれないノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形することを特徴とする請求項１又は２に記載のデータ処理装置。
【請求項５】
前記有向グラフ変形部は、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードを複製し、そのノードに続く経路が前記対象経路に含まれるノードと、そのノードに続く経路が前記対象経路に含まれるが、そのノードに至る経路が前記対象経路に含まれないノードと、そのノードに続く経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形することを特徴とする請求項１又は２に記載のデータ処理装置。
【請求項６】
有向グラフを取得するステップと、
前記有向グラフのノード又は２つのノードの間のエッジに重みを付与するステップと、
特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記付与するステップで与えられた重みとは異なる重みが与えられている場合、前記有向グラフに前記組合せが含まれるか否かを判定するステップと、
前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形するステップと、
経路が追加された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記重みに基づいて評価するステップと、
を備えることを特徴とするデータ処理方法。
【請求項７】
有向グラフを取得する機能と、
前記有向グラフのノード又は２つのノードの間のエッジに重みを付与する機能と、
特定の２以上のエッジ、３以上のノード、又は連続しない２つのノードの組合せについて、前記組合せに含まれるノード又はエッジのうち少なくとも１つに、前記付与する機能で与えられた重みとは異なる重みが与えられている場合、前記有向グラフに前記組合せが含まれるか否かを判定する機能と、
前記有向グラフに前記組合せが含まれる場合、前記組合せに含まれるノード又はエッジを全て含む対象経路に含まれるノードのうち、そのノードに至る経路として前記対象経路以外の経路が存在するノードを複製し、そのノードに至る経路が前記対象経路に含まれるノードと、そのノードに至る経路が前記対象経路に含まれないノードとが区別されるように、前記有向グラフを変形する機能と、
経路が追加された有向グラフにおける第１ノードから第２ノードへ至る経路を、前記重みに基づいて評価する機能と、
をコンピュータに実現させることを特徴とするデータ処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１０−４４６３７（Ｐ２０１０−４４６３７Ａ）
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願番号】特願２００８−２０８９１６（Ｐ２００８−２０８９１６）
【出願日】平成２０年８月１４日（２００８．８．１４）
【出願人】（３９００２４３５０）株式会社ジャストシステム (123)
【Ｆターム（参考）】
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願日】平成２０年８月１４日（２００８．８．１４）
【出願人】（３９００２４３５０）株式会社ジャストシステム (123)
【Ｆターム（参考）】
[ Back to top ]