有向グラフ作成装置、有向グラフ作成方法、及び有向グラフ作成プログラム
【課題】複数のイベント連鎖が統合された有向グラフより元のイベント連鎖には存在しない経路を除去すること。
【解決手段】有向グラフ作成装置は、複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定する特定部と、特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成する複製部と、複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する削除部とを有する。
【解決手段】有向グラフ作成装置は、複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定する特定部と、特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成する複製部と、複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する削除部とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有向グラフ作成装置、有向グラフ作成方法、及び有向グラフ作成プログラムに関する。
【背景技術】
【０００２】
事故等に関するトラブル情報の分析においては、トラブルが起きるまでの経過又は過程を分析することが重要である。経過又は過程を示す情報は、報告書等においてテキスト情報として記述されていることが一般的である。したがって、テキストマイニング技術を利用することにより、トラブルが起きるまでの経過又は過程を示す情報を、イベントの順序情報（以下、「イベント連鎖」という。）としてテキスト情報より抽出することが可能である。
【０００３】
図１は、テキスト情報からのイベント連鎖の抽出例を示す図である。同図では、交通事故の報告書を示すテキスト情報から抽出されたイベント連鎖の例が示されている。
【０００４】
イベント連鎖の情報を複数の事例にわたってマージした結果を示す有向グラフ（以下、「イベントフロー」という。）を得ることにより、複数の事例に共通するトラブル発生シナリオの抽出や、根本原因等の特定等を行うことができる（図1）。
【０００５】
図２は、イベントフローの例を示す図である。同図には、交通事故に関する５００件のレポートから作成されたイベントフローが示されている。同図のイベントフローからは、例えば、雨によって路面が不良な状態となり、スリップしてハンドル操作をミスした結果、重傷となった、といったシナリオが読み取れる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００２−２３６６９２号公報
【特許文献２】特開２００４−１７８２７０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
イベント連鎖をマージしてイベントフローを作成する方法として、イベント連鎖をイベントの順序付きの二項関係に展開して、それを再構成する方法がある。
【０００８】
例えば、図３は、３つの事例に関するイベント連鎖の例を示す図である。同図には、事例Ａに関するイベント連鎖Ａ、事例Ｂに関するイベント連鎖Ｂ、及び事例Ｃに関するイベント連鎖Ｃが示されている。
【０００９】
図３における各イベント連鎖をそれぞれ二項関係に展開すると、図４に示されるようになる。図４は、３つのイベント連鎖を二項関係に展開した例を示す図である。同図には、イベント連鎖Ａ、イベント連鎖Ｂ、及びイベント連鎖Ｃごとに、二項関係に展開された例が示されている。
【００１０】
図４に示される各二項関係を、当該二項関係の一方のイベントと他の二項関係の他方のイベントとの一致に基づいて再編成すると、図５に示されるようなイベントフローｅＦ１が得られる。
【００１１】
図５は、３つのイベント連鎖に関する二項関係を再編成して得られるイベントフローの例を示す図である。同図では、当初別々であったイベント連鎖がマージされ、全てのノードが相互に直接的又は間接的に接続された一つのイベントフローｅＦ１が形成されている。
【００１２】
以上のようなイベントフローの作成方法は、簡便で効率的ではあるが、元々のイベント連鎖には存在しなかったパス（経路）が、イベントフローに作成されてしまうという問題がある。ここでいう、パスは、ノード間の直接的又は間接的な接続関係をいう。
【００１３】
図６は、元々のイベント連鎖には存在しなかったパスを示す図である。同図に示されるパスｐ１〜ｐ４は、図５に示されるイベントフローｅＦ１には含まれるパスであるが、図３に示されるイベント連鎖Ａ〜Ｃのいずれにも含まれていない。
【００１４】
独立して発生した事象が組み合わさることによって、重大なトラブルが発生するということも考えられる。したがって、トラブル分析という目的においては、「存在しないが組み合わせとして考えられるパス」を洗い出すことが重要な場合もある。しかし、実際に起きたことを分析することが目的である場合においては、「もともと存在していたパス」と「もともとは存在していなかったパス」とを切り分けて分析できる必要がある。
【００１５】
そこで、複数のイベント連鎖が統合された有向グラフより元のイベント連鎖には存在しない経路を除去することのできる有向グラフ作成装置、有向グラフ作成方法、及び有向グラフ作成プログラムの提供を目的とする。
【課題を解決するための手段】
【００１６】
上記課題を解決するため、有向グラフ作成装置は、複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定する特定部と、特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成する複製部と、複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する削除部とを有する。
【発明の効果】
【００１７】
複数のイベント連鎖が統合された有向グラフより元のイベント連鎖には存在しない経路を除去することができる。
【図面の簡単な説明】
【００１８】
【図１】テキスト情報からのイベント連鎖の抽出例を示す図である。
【図２】イベントフローの例を示す図である。
【図３】３つの事例に関するイベント連鎖を示す図である。
【図４】３つのイベント連鎖を二項関係に展開した例を示す図である。
【図５】３つのイベント連鎖に関する二項関係を再編成して得られるイベントフローの例を示す図である。
【図６】元々のイベント連鎖には存在しなかったパスを示す図である。
【図７】本発明の実施の形態におけるイベントフロー作成装置のハードウェア構成例を示す図である。
【図８】本発明の実施の形態におけるイベントフロー作成装置の機能構成例を示す図である。
【図９】イベントフローの作成処理の処理手順の一例を説明するためのフローチャートである。
【図１０】ノードの複製の第一の例を示す図である。
【図１１】複製に係るノードに接続する下流側の冗長エッジの第一の削除例を示す図である。
【図１２】複製に係るノードに接続する上流側の冗長エッジの第一の削除例を示す図である。
【図１３】ノードの複製の第二の例を示す図である。
【図１４】複製に係るノードに接続する下流側の冗長エッジの第二の削除例を示す図である。
【図１５】複製に係るノードに接続する上流側の冗長エッジの第二の削除例を示す図である。
【図１６】非存在パスの特定処理の処理手順の一例を説明するためのフローチャートである。
【図１７】イベント連鎖ごとの隣接行列及び可到達行列の例を示す図である。
【図１８】全ての可到達行列の論理和の例を示す図である。
【図１９】イベント連鎖ごとの隣接行列の論理和の例を示す図である。
【図２０】当初存在パスを示す可到達行列と二項関係の統合によって作成されたイベントフローを示す可到達行列との差分の例を示す図である。
【図２１】複製対象の選択処理の処理手順の一例を説明するためのフローチャートである。
【図２２】複製対象の選択処理を説明するためのデータ図の一例である。
【図２３】イベントの複製処理の処理手順の一例を説明するためのフローチャートである。
【図２４】複製対象のイベントに対応する行及び列の複製の例を示す図である。
【図２５】冗長エッジの削除処理の処理手順の一例を説明するためのフローチャートである。
【図２６】複製された各イベントに関する直接下流イベントとの関係の排他的な削除の例を示す図である。
【図２７】直接下流イベントの削除後の隣接行列に基づく可到達行列の例を示す図である。
【図２８】上流側の関係の削除を説明するための図である。
【図２９】上流側の関係の削除を説明するための図である。
【発明を実施するための形態】
【００１９】
以下、図面に基づいて本発明の実施の形態を説明する。図７は、本発明の実施の形態におけるイベントフロー作成装置のハードウェア構成例を示す図である。図７のイベントフロー作成装置１０は、それぞれバスBで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、表示装置１０５、及び入力装置１０６等を有する。
【００２０】
イベントフロー作成装置１０での処理を実現するプログラムは、記録媒体１０１によって提供される。プログラムを記録した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２１】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従ってイベントフロー作成装置１０に係る機能を実現する。表示装置１０５はプログラムによるＧＵＩ（Graphical User Interface）等を表示する。入力装置１０６はキーボード及びマウス等であり、様々な操作指示を入力させるために用いられる。
【００２２】
なお、記録媒体１０１の一例としては、ＣＤ−ＲＯＭ、ＤＶＤディスク、又はＵＳＢメモリ等の可搬型の記録媒体が挙げられる。また、補助記憶装置１０２の一例としては、ＨＤＤ（Hard Disk Drive）又はフラッシュメモリ等が挙げられる。記録媒体１０１及び補助記憶装置１０２のいずれについても、コンピュータ読み取り可能な記録媒体に相当する。
【００２３】
図８は、本発明の実施の形態におけるイベントフロー作成装置の機能構成例を示す図である。同図において、イベントフロー作成装置１０は、文書情報記憶部１１、イベント連鎖抽出部１２、イベント連鎖記憶部２１、展開部１３、二項関係記憶部１４、統合部１５、イベントフロー記憶部２２、非存在パス特定部１６、複製対象選択部１７、ノード複製部１８、及び冗長エッジ削除部１９等を有する。文書情報記憶部１１は、例えば、補助記憶装置１０２、又はイベントフロー作成装置１０とネットワークを介して接続される記憶装置若しくはコンピュータを用いて実現可能である。イベント連作記憶部２１、二項関係記憶部１４、及びイベントフロー記憶部２２は、メモリ装置１０３、補助記憶装置１０２、又はイベントフロー作成装置１０とネットワークを介して接続される記憶装置若しくはコンピュータを用いて実現可能である。等と用いて実現可能である。イベント連鎖抽出部１２、展開部１３、統合部１５、非存在パス特定部１６、複製対象選択部１７、ノード複製部１８、及び冗長エッジ削除部１９は、イベントフロー作成装置１０にインストールされたプログラムがＣＰＵ１０４に実行させる処理により実現される。
【００２４】
文書情報記憶部１１は、例えば、事故の報告書等の複数の文書情報群を記憶する。なお、文書情報は、必ずしもテキスト形式のデータでなくてもよい。所定のワープロソフト等によって作成された文書データであってもよい。文書情報は、最終的にテキスト情報を抽出可能なデータであればよい。
【００２５】
イベント連鎖抽出部１２は、文書情報に含まれているイベント（以下、「イベント」という。）の順序情報（以下、「イベント連鎖」という。）を、文書情報ごとに抽出する。イベント連鎖の抽出方法は、公知技術に従えばよい。イベント連鎖抽出部１２は、抽出されたイベント連鎖を、イベント連鎖記憶部２１に記録する。
【００２６】
展開部１３は、イベント連鎖抽出部１２によって抽出された各イベント連鎖を、イベントの順序付きの二項関係に展開する。二項関係とは、イベント連鎖において相互に直接的な関係を有する二つのイベントの組み合わせをいう。直接的な関係とは、順序情報において隣接している関係をいう。また、イベントの順序付きであるから、直接的な関係を有する二つのイベントの順序関係は、二項関係において維持される。
【００２７】
二項関係記憶部１４は、展開部１３によって展開された二項関係を示す情報を記憶する。
【００２８】
統合部１５は、二項関係記憶部１４が記憶する各二項関係を、当該二項関係の一方のイベントと他の二項関係の他方のイベントとの一致に基づいて統合（又は接続）することにより、有向グラフを作成する。当該有向グラフの各ノード（節点）は、イベントを示す。また、当該有向グラフのエッジ（枝）は、イベントの順序関係（又は前後関係若しくは因果関係等）を示す。以下、当該有向グラフを、「イベントフロー」という。なお、統合部１５は、作成されたイベントフローをイベントフロー記憶部２２に記録する。
【００２９】
非存在パス特定部１６は、イベントフローにおいて、各イベント連鎖においては存在していなかったパスを特定する。なお、イベントフローにおいて、任意のイベント間の経路（又は接続関係）を「パス」という。当該任意のイベントは、直接的に接続されていてもよいし、間接的に接続されていてもよい。また、イベント連鎖においては存在していなかったパスを「非存在パス」という。
【００３０】
複製対象選択部１７は、統合部１５によって作成されたイベントフローにおいて、複製対象とするノード（イベント）を選択する。ノード複製部１８は、複製対象選択部１７によって選択されたノードの複製を作成する。すなわち、ノードの複製とは、既存のノード及び当該ノードに接続する全てのエッジと同一のノード及びエッジを作成することをいう。したがって、ノードの複製によって、当該ノード及び当該ノードに接続する全てのエッジは２重化される。ノードの複製は、ノードの分割として解釈されてもよい。この場合、分割対象のノードに接続する全てのエッジも分割される。
【００３１】
なお、ノードが複製（又は２重化）されるのは、複数のイベント連鎖においては相互に独立していた、同一イベントに関する各ノードが、二項関係を統合する際に一つのノードに統合又は集約されたことが非存在パスの発生の原因であると考えるからである。したがって、一つに統合されたノードを複製によって改めて分割すれば、非存在パスを除去できると考えるからである。但し、闇雲にノードの複製が行われたのでは、元のイベント連鎖に戻ってしまいかねない。したがって、複製対象選択部１７は、複数のイベント連鎖に共通なシナリオを把握可能な状態が維持されるように、複製対象とするノードを選択する。
【００３２】
冗長エッジ削除部１９は、ノードの複製に伴って複製されたエッジのうち、当該エッジを削除したとしても、イベントフローにおいて、元のイベント連鎖が含む経路に影響しないエッジを削除する。元のイベント連鎖が含む経路に影響しないとは、元のイベント連鎖が含むいずれかのパスが失われないことをいう。
【００３３】
以下、イベントフロー作成装置１０の処理手順について説明する。図９は、イベントフローの作成処理の処理手順の一例を説明するためのフローチャートである。
【００３４】
例えば、入力装置１０６を介して入力される指示入力に応じ、イベント連鎖抽出部１２は、文書情報記憶部１１が記憶する文書情報ごとに、イベント連鎖を抽出し、抽出されたイベント連鎖をイベント連鎖記憶部２１に記録する（Ｓ１０）。文書情報からのイベント連鎖の抽出は、テキストマイニング技術等の公知技術を用いて行われればよい。例えば、特開２００２−２３６６９２号公報の段落番号００６６〜００６８に開示されている方法などを用いることにより、文書情報からイベントを抽出することが可能である。また、イベントが文書情報から抽出される順番（文書情報での出現位置）を用いることにより、イベント間の順序関係を特定することが可能である。この際、特定の接続詞が含まれる場合には、順序関係の逆転が行われてもよい。
【００３５】
なお、ここでは、便宜上、３つの文書情報から、図３に示されるイベント連鎖Ａ〜Ｃが抽出されたこととする。
【００３６】
続いて、展開部１３は、イベント連鎖記憶部２１に記録されたイベント連鎖Ａ〜Ｃのそれぞれを、二項関係に展開する（Ｓ２０）。すなわち、イベント連鎖Ａ〜Ｃのそれぞれから二項関係が抽出される。ここでは、図４に示される二項関係に抽出される。展開部１３は、抽出された二項関係を示す情報を二項関係記憶部１４に記録する。なお、二項関係を示す情報の記録形式は、所定のものに限定されない。上流側（原因側）のイベントを示す項目と、下流側（結果側又は終点側）のイベントを示す項目とを含むレコード群が構成するテーブル形式であってもよい。又は、ＸＭＬ（eXtensible Markup Language）形式等の構造化文書形式に当該情報が記録されてもよい。
【００３７】
続いて、統合部１５は、二項関係記憶部１４が記憶する各二項関係を、当該二項関係の一方のイベントと他の二項関係の他方のイベントとの一致に基づいて統合（又は接続）することにより、イベントフローを作成する（Ｓ３０）。統合部１５は、作成されたイベントフローをイベントフロー記憶部２２に記録する。ここでは、図５に示されるイベントフローｅＦ１が作成される。なお、二項関係からの有向グラフを作成は、例えば、特開２００４−１７８２７０号公報に開示されている方法を用いて行われてもよい。
【００３８】
続いて、非存在パス特定部１６は、イベントフロー記憶部２２及びイベント連鎖記憶部２１を参照して、イベントフローｅＦ１において、イベント連鎖Ａ、Ｂ、又はＣのいずれにも存在しないパス（非存在パス）を特定する（Ｓ４０）。非存在パスの特定は、イベントフローｅＦ１を、イベント連鎖Ａ、Ｂ、及びＣのそれぞれと比較することにより特定することができる。ここでは、図６に示される、パスｐ１〜ｐ４が、非存在パスとして特定される。
【００３９】
非存在パスが無い場合（Ｓ５０でＮｏ）、イベントフローｅＦ１が、最終的なイベントフローとして出力される。例えば、イベントフローｅＦ１を示すデータが補助記憶装置１０２に保存されてもよいし、表示装置１０５に表示されてもよい。
【００４０】
非存在パスが有る場合（Ｓ５０でＹｅｓ）、複製対象選択部１７は、特定された非存在パスのうちの任意の一つを選択して、当該非存在パス（以下、「カレント非存在パス」という。）上のノードの中から複製対象とするノード（イベント）を選択する（Ｓ６０）。ここで、複製対象の選択条件は、例えば、以下の通りである。
（１）カレント非存在パスの始点ノードと終点ノードとの間（すなわち、端点ノードの間）に挟まれているノードであること（したがって、当該始点ノード及び当該終点ノード等の端点ノードは選択対象から除かれる）。
（２）（１）に該当するノード群の中で、下流側のエッジが分岐している（下流側に複数のエッジが接続する）ノードのうち最も下流に位置すること。
（３）（２）に該当するノードが存在しない場合、（１）に該当するノード群の中で最も下流に位置すること。
【００４１】
例えば、図６のパスｐ１がカレント非存在パスである場合、複製対象は次のように選択される。
【００４２】
まず、パスｐ１において、始点ノードは「直進」であり、終点ノードは「センターオーバーライン」である。すなわち、この二つのノードは、イベント連鎖Ａ〜Ｃのいずれにおいても、直接的又は間接的に接続されていない。この二つのノードに挟まれるノードは、「急ブレーキ」及び「スリップ」である（条件（１））。「スリップ」の下流側には二つのノードが接続しており、かつ、「スリップ」は、「急ブレーキ」及び「スリップ」の中で最下流に位置する（条件（２））。したがって、「スリップ」が複製対象として選択される。
【００４３】
続いて、ノード複製部１８は、選択されたノード及び当該ノードに接続するエッジの複製を作成する（Ｓ７０）。
【００４４】
図１０は、ノードの複製の第一の例を示す図である。同図では、ノード「スリップ」の複製により、イベントフローｅＦ２が作成された例が示されている。イベントフローｅＦ２では、「スリップ」というイベントを示すノードが、「スリップｎ１ａ」と「スリップｎ１ｂ」との二つのノードに分割されている。また、ノード「スリップ」に接続する４つエッジ（ｅｄ１、ｅｄ２、ｅｄ３、ｅｄ４）の複製（ｅｄ１１、ｅｄ２１、ｅｄ３１、ｅｄ４１）も作成されている。なお、複製されたエッジは、複製元のエッジと同一の接続関係を維持する。
【００４５】
続いて冗長エッジ削除部１９は、イベントフローｅＦ２より、複製されたエッジの中から冗長なエッジを削除する（Ｓ８０）。まず、複製に係るノード（複製元及び複製先の双方を含む）の下流側のエッジに関して、冗長エッジ削除部１９は、カレント非存在パスに属するエッジとカレント非存在パスに属さないエッジとに分類する。冗長エッジ削除部１９は、複製元及び複製先のノードのいずれか一方からカレント非存在パスに属するエッジを削除し、他方からカレント非存在パスに属さないエッジを削除する。このことは、図上において、相互にクロスする二つのエッジ又は相互にクロスしない二つエッジを削除することに相当する。すなわち、重複するエッジのうち一方が冗長エッジとして削除される。重複するエッジとは、例えば、エッジｅｄ３及びエッジｅｄ３１のように、複製元ノード又は複製先ノードの区別をしない場合に同一のノード間（「スリップ」と「追突」）を接続するエッジである。
【００４６】
図１１は、複製に係るノードに接続する下流側の冗長エッジの第一の削除例を示す図である。同図では、イベントフローｅＦ２（図１０）において相互にクロスしていたエッジｅｄ３１及びｅｄ４１が冗長エッジとして削除され、イベントフローｅＦ３が作成された例が示されている。その結果、複製元又は複製先のノード「スリップｎ１ａ又はｎ１ｂ」は、それぞれ一つのエッジｅｄ３又はｅｄ４に接続されるようになる。但し、エッジｅｄ３及びｅｄ４が削除対象とされてもよい。
【００４７】
ここで、イベントフローｅＦ２（図１０）において、エッジｅｄ４及びｅｄ４１は、カレント非存在パス（パスｐ１）に属し、エッジｅｄ３及びｅｄ３１は、カレント非存在パスに属さない。複製元の「スリップｎ１ａ」からは、カレント非存在パスに属するエッジｅｄ４１が削除され、複製先の「スリップｎ１ｂ」からは、カレント非存在パスに属さないエッジｅｄ３１が削除された結果が、イベントフローｅＦ３（図１１）である。
【００４８】
なお、複製対象のノードが、複製前において下流側に３つ以上のノードと接続されている場合（下流側に３つ以上に分岐している場合）においても、複製後の下流側に接続するエッジの削除方法は基本的に上記した通りである。すなわち、冗長エッジ削除部１９は、カレント非存在パスに属するエッジとカレント非存在パスに属さないエッジとに分類する。冗長エッジ削除部１９は、複製元及び複製先のノードのいずれか一方からカレント非存在パスに属するエッジを削除し、他方からカレント非存在パスに属さないエッジを削除する。
【００４９】
複製ノードの下流側の冗長エッジの削除の後、上流側の冗長エッジの削除が行われる。複製に係るノードの上流側に接続するエッジに関しては、当該エッジを削除したことによって、イベント連鎖Ａ〜Ｃのいずれかにに含まれるパス（以下、「当初存在パス」という。）がイベントフローｅＦ３から失われない（除去されない）エッジのみが削除される。
【００５０】
例えば、「オーバースピード→スリップｎ１ａ」に関しては、当該関係を構成するエッジｅｄ２１が削除されても、当初存在パスのいずれかがが除去されることはない。イベント連鎖Ｃには、「オーバースピード→スリップ」を含むパスが存在するが、当該パスは、「オーバースピード→スリップｎ１ｂ」によって維持されるからである。したがって、「オーバースピード→スリップｎ１ａ」に係るエッジｅｄ２１は、冗長エッジとして削除される。一方、「急ブレーキ→スリップｎ１ｂ」に関しては、当該関係に係るエッジｅｄ１１が削除されてしまうと、「急ブレーキ→センターライン」という、当初存在パスが除去されてしまう。したがって、エッジｅｄ１１の削除は行われない。
【００５１】
図１２は、複製に係るノードに接続する上流側の冗長エッジの第一の削除例を示す図である。同図では、エッジｅｄ２１が削除され、イベントフローｅＦ４が作成された例が示されている。なお、同図と図６とを比較すると、イベントフローｅＦ４では、非存在パスｐ３及びｐ４が除去されていることが分かる。
【００５２】
ステップＳ４０以降は、非存在パスが特定されなくなるまで（非存在パスが無くなるまで）繰り返される。本実施の形態では、イベントフローｅＦ４に関して、非存在パスｐ１及びｐ２（図６参照）が存在する。したがって、イベントフローｅＦ４に関して、ステップＳ６０以降が実行される。ここでは、パスｐ１がカレント非存在パスとして選択されたこととする。この場合、イベントフローｅＦ４では、「急ブレーキ」が、ステップＳ６０の選択条件に合致する（Ｓ６０）。したがって、「急ブレーキ」、及び「急ブレーキ」に接続するエッジの複製が作成される（Ｓ７０）。
【００５３】
図１３は、ノードの複製の第二の例を示す図である。同図では、ノード「急ブレーキ」の複製により、イベントフローｅＦ５が作成された例が示されている。イベントフローｅＦ５では、「急ブレーキ」というイベントを示すノードが、「急ブレーキｎ２ａ」と「急ブレーキｎ２ｂ」との二つのノードに分割されている。また、ノード「スリップ」に接続する４つエッジ（ｅｄ５、ｅｄ６、ｅｄ１、ｅｄ１１）の複製（ｅｄ５１、ｅｄ６１、ｅｄ１ｃ、ｅｄ１１ｃ）も作成されている。
【００５４】
続いて、イベントフローｅＦ５に関して、冗長エッジが削除される（Ｓ８０）。まず、複製に係るノードの下流側に関して冗長エッジが削除される。
【００５５】
図１４は、複製に係るノードに接続する下流側の冗長エッジの第二の削除例を示す図である。同図では、イベントフローｅＦ５（図１３）において相互にクロスしていたエッジｅｄ１１及びｅｄ１ｃが冗長エッジとして削除され、イベントフローｅＦ６が作成された例が示されている。その結果、複製元又は複製先のノード「急ブレーキｎ２ａ又はｎ２ｂ」は、それぞれ一つのエッジｅｄ１又はｅｄ１１ｃに接続されるようになる。
【００５６】
一方、複製に係るノードの上流側に接続するエッジに関しては、当該エッジを削除したことによって、いずれかの当初存在パスがイベントフローｅＦ６から除去されないエッジのみが削除される。
【００５７】
図１５は、複製に係るノードに接続する上流側の冗長エッジの第二の削除例を示す図である。同図では、エッジｅｄ５１及びエッジｅｄ６１が削除され、イベントフローｅＦ７が作成された例外示されている。
【００５８】
ここで、図１５と図６とを比較すると、イベントフローｅＦ７では、非存在パスｐ１及びｐ２が更に除去されていることが分かる。したがって、イベントフローｅＦ７が、最終的なイベントフローとして出力される。
【００５９】
上述したように、本実施の形態によれば、二項関係に基づいて再編成されたイベントフローより、イベント連鎖には存在していなかったパスを除去又は排除することができる。た、複製対象が適切に選択されることにより、イベントフローの分割の程度を抑制することができる。その結果、複数のイベント連鎖に共通のシナリオを示すことができ、かつ、それぞれの文書情報に含まれていた順序関係又は因果関係等を示すイベントフローを作成することができる。
【００６０】
また、例えば、文書情報に含まれていた因果関係と、文書情報には含まれていなかった因果関係とを区別して分析することが可能となる。
【００６１】
ところで、上記において説明した処理手順において、非存在パスの特定、複製対象とするノードの選択、及び削除対象とする関係（冗長エッジ）を判定等に用いるデータのデータ形式は所定のものに限定されない。例えば、ＸＭＬ形式によってイベントフローを表現するデータであってもよいし、他のデータ形式が用いられてもよい。
【００６２】
以下においては、行列（マトリクス）を用いてステップＳ４０以降を実行する例を説明する。なお、以下の説明において作成される各行列は、例えば、メモリ装置１０３に記録される。
【００６３】
ステップＳ４０の詳細について説明する。図１６は、非存在パスの特定処理の処理手順の一例を説明するためのフローチャートである。
【００６４】
ステップＳ４０１〜Ｓ４０４は、イベント連鎖ごとに実行されるループ処理であるが、ここでは、便宜上、イベント連鎖Ａ、Ｂ、及びＣのそれぞれについて並列的に説明する。但し、実際に並列的に処理が行われてもよい。
【００６５】
ステップＳ４０１において、非存在パス特定部１６は、イベント連鎖Ａ、Ｂ、及びＣのそれぞれに関して隣接行列を作成する。
【００６６】
図１７は、イベント連鎖ごとの隣接行列及び可到達行列の例を示す図である。同図において、隣接行列ａＭＡ、ａＭＢ、及びａＭＣは、順番に、イベント連鎖Ａ、Ｂ、又はＣの隣接行列である。すなわち、各隣接行列には、対応するイベント連鎖において直接的な接続関係を有するイベントの組み合わせに対して「１」が記録されている。なお、行方向が上流側（原因側）のイベントであり、列方向が下流側（結果側）のイベントである。
【００６７】
隣接行列ａＭＡ、ａＭＢ、及びａＭＣは、イベント連鎖Ａ、Ｂ、又はＣのそれぞれの二項関係を示す行列であるともいえる。したがって、隣接行列ａＭＡ、ａＭＢ、及びａＭＣは、二項関係記憶部１４が記憶する情報に基づいて生成されてもよい。もちろん、隣接行列ａＭＡ、ａＭＢ、及びａＭＣは、イベント連鎖Ａ、Ｂ、又はＣより生成されてもよい。
【００６８】
続いて、非存在パス特定部１６は、隣接行列ａＭＡ、ａＭＢ、及びａＭＣを、それぞれに対応する新たな可到達行列ｒＭＡ、ｒＭＢ、又はｒＭＣに代入する（Ｓ４０２）。なお、図１７に示される可到達行列ｒＭＡ、ｒＭＢ、又はｒＭＣは、ステップＳ４０３及びＳ４０４の実行後の状態を示す。ここでは、３つの可到達行列が、隣接行列ａＭＡ、ａＭＢ、又はａＭＣによって初期化される。なお、可到達行列は、イベント連鎖において、直接的又は間接的な関係を有するイベントの組み合わせに「１」が記録される行列である。
【００６９】
続いて、非存在パス特定部１６は、各可到達行列に対して、隣接行列ａＭＡ、ａＭＢ、又はａＭＣを乗じ、新たな可到達行列を得る（Ｓ４０３）。ここで得られる可到達行列は、直接的な関係と、一つのイベントを間に挟む間接的な関係とを示す可到達行列である。各可到達行列に対する隣接行列ａＭＡ、ａＭＢ、又はａＭＣの乗算は、各可到達行列ｒＭＡ、ｒＭＢ、又はｒＭＣが変化しなくなるまで行われる（Ｓ４０４）。すなわち、演算結果が変化しなくなるまで、各隣接行列がＮ乗される。演算結果が変化しなくなった状態が、図１７に示される可到達行列ｒＭＡ、ｒＭＢ、及びｒＭＣである。したがって、可到達行列ｒＭＡ、ｒＭＢ、及びｒＭＣは、それぞれに対応するイベント連鎖において、各イベントの直接的又は間接的な全ての関係を示す可到達行列である。
【００７０】
可到達行列ｒＭＡ、ｒＭＢ、及びｒＭＣが得られると（Ｓ４０５でＹｅｓ）、非存在パス特定部１６は、全ての可到達行列（ｒＭＡ、ｒＭＢ、及びｒＭＣ）の論理和を算出する（Ｓ４０６）。
【００７１】
図１８は、全ての可到達行列の論理和の例を示す図である。同図に示される可到達行列Ｍ１は、可到達行列ｒＭＡ、ｒＭＢ、及びｒＭＣの論理和を示す。可到達行列Ｍ１は、イベント連鎖Ａ、Ｂ、又はＣにおいて、全ての当初存在パス（直接的又は間接的なものを含む。）を示す行列である。換言すれば、可到達行列Ｍ１において「１」が記録されていないパスは、非存在パスである。なお、可到達行列Ｍ１は、後段の処理において、当初存在パスを識別するために利用される。
【００７２】
続いて、非存在パス特定部１６は、イベント連鎖Ａ〜Ｃごとの隣接行列（ａＭＡ、ａＭＢ、及びａＭＣ）の論理和を算出する（Ｓ４０７）。
【００７３】
図１９は、イベント連鎖ごとの隣接行列の論理和の例を示す図である。同図において、隣接行列Ｍ２は、隣接行列ａＭＡ、ａＭＢ、及びａＭＣの論理和を示す。
【００７４】
続いて、非存在パス特定部１６は、隣接行列Ｍ２を、隣接行列Ｍ２に対応する新たな可到達行列Ｍ３に代入する（Ｓ４０８）。続いて、非存在パス特定部１６は、可到達行列Ｍ３に、隣接行列Ｍ２を乗じ、新たな可到達行列を得る（Ｓ４０９）。当該乗算は、可到達行列Ｍ３が変化しなくなるまで行われる（Ｓ４１０）。すなわち、演算結果が変化しなくなるまで、隣接行列Ｍ２がＮ乗される。演算結果が変化しなくなった状態が、図１９に示される可到達行列Ｍ３である。可到達行列Ｍ３は、二項関係の統合によって作成されるイベントフローｅＦ１における各イベントの直接的又は間接的な接続関係を示す可到達行列である。
【００７５】
ステップＳ４１１に進み、非存在パス特定部１６は、可到達行列Ｍ１（図１７）と、可到達行列Ｍ３（図１９）との差分を抽出する。すなわち、当初存在パスを示す可到達行列Ｍ１と、イベントフローｅＦ１を示す可到達行列との差分が抽出される。
【００７６】
図２０は、当初存在パスを示す可到達行列と二項関係の統合によって作成されたイベントフローを示す可到達行列との差分の例を示す図である。
【００７７】
同図では、可到達行列Ｍ３において、可到達行列Ｍ１との差分に係るセルは太枠で囲まれている。この差分は、図６に示されるパスｐ１〜ｐ４を示す。すなわち、「直進」と「センターラインオーバー」との組は、パスｐ１を示す。「直進」と「正面衝突」との組は、パスｐ２を示す。「カーブ」と「追突」との組は、パスｐ３を示す。「オーバースピード」と「追突」との組は、パスｐ４を示す。
【００７８】
このようにして、非存在パス特定部１６は、非存在パスを特定することができる。
【００７９】
続いて、図９のステップＳ６０の詳細について説明する。図２１は、複製対象の選択処理の処理手順の一例を説明するためのフローチャートである。
【００８０】
ステップＳ６０１において、複製対象選択部１７は、非存在パス特定部１６によって特定された非存在パスの中から一つの非存在パスを選択する。ここで、選択された非存在パスが、「カレント非存在パス」である。
【００８１】
図２２は、複製対象の選択処理を説明するためのデータ図の一例である。同図では、図１６との対応関係を示すステップ番号が記されている。図２２のステップＳ６０１では、可到達行列Ｍ３において、「直進→センターラインオーバー」に係るパスが選択された例が示されている。
【００８２】
続いて、複製対象選択部１７は、カレント非存在パスに含まれるイベントの中で、カレント非存在パスの始点のイベントより下流のイベント（以下、「下流イベント」という。）と、カレント非存在パスの終点のイベントより上流のイベント（以下、「上流イベント」という。）とを取得する（Ｓ６０２）。
【００８３】
カレント非存在パスの始点のイベントより下流のイベントに該当するイベントは、図２２のステップＳ６０２に対応する可到達行列Ｍ３ａにおいて、太枠で囲まれている列に係るイベントである。すなわち、カレント非存在パスに係る行において、「１」が記録されている列のうち、始点のイベント「直進」よりも右側の列に係るイベントである。
【００８４】
また、カレント非存在パスの終点のイベントより上流のイベントに該当するイベントは、図２２のステップＳ６０２に対応する可到達行列Ｍ３ｂにおいて、太枠で囲まれている行に係るイベントである。すなわち、カレント非存在パスに係る列において、「１」が記録されている行のうち、終点のイベント「センターラインオーバー」よりも上側に係るイベントである。
【００８５】
続いて、複製対象選択部１７は、下流イベント（急ブレーキ、スリップ、センターラインオーバー、正面衝突、追突）と、上流イベント（路面凍結、直進、カーブ、急ブレーキ、オーバースピード、スリップ）との論理積を算出する（Ｓ６０３）。当該論理積によって、カレント非存在パスにおいて始点のイベントと終点のイベントとに挟まれるイベント群が特定される。なお、ここでは、「急ブレーキ」及び「スリップ」が特定される。
【００８６】
続いて、複製対象選択部１７は、特定されたイベント群の中で、下流から順に未処理のイベントの一つを取得する（Ｓ６０４）。未処理とは、ステップＳ６０６以降の処理対象とされていないことをいう。下流から順であるから、最初は、当該イベント群の中で最下流のイベントが取得される。以下、取得されたイベントを「対象イベント」という。
【００８７】
対象イベントが取得された場合（Ｓ６０５でＹｅｓ）、複製対象選択部１７は、隣接行列Ｍ２を用いて、対象イベントの下流側に直接的に接続されるイベント（以下、「直接下流イベント」という。）を特定する（Ｓ６０６）。
【００８８】
図２２のステップＳ６０６では、隣接行列Ｍ２において、「急ブレーキ」と「スリップ」とのそれぞれの直接下流イベントの特定結果が示されている。図１９において説明したように、隣接行列Ｍ２は、隣接行列ａＭＡ、ａＭＢ、及びａＭＣの論理和である。したがって、隣接行列Ｍ２は、イベント間の直接的な関係のみを示す。よって、隣接行列Ｍ２において、「スリップ」又は「急ブレーキ」の行で「１」が記録されている列に係るイベントは、「急ブレーキ」又は「スリップ」の直接下流イベントということになる。同図では、「急ブレーキ」に関して１つの直接下流イベントと、「スリップ」に関して２つの直接下流イベントとが特定されている。なお、図２１のステップＳ６０６では、一つの対象イベントに関して直接下流イベントが特定されるが、図２２においては、便宜上、カレント非存在パスの始点と終点との間に挟まれる全てのイベントに関して、直接下流イベントが示されている。
【００８９】
続いて、複製対象選択部１７は、対象イベントに関する直接下流イベントの数は複数であるか否かを判定する（Ｓ６０７）。このことは、対象イベントの下流側のエッジが分岐しているか又は当該エッジが複数有るか否かの判定に相当する。対象イベントに関する直接下流イベントの数が複数である場合（Ｓ６０７でＹｅｓ）、複製対象選択部１７は、対象イベントを複製対象として選択する（Ｓ６０８）。対象イベントが「スリップ」であれば、直接下流イベントの数は複数である。したがって、「スリップ」が複製対象として選択される。なお、ステップＳ６０８は、図９のステップＳ６０において説明した選択条件の（２）に該当するケースである。
【００９０】
一方、直接下流イベントの数が複数でない場合（Ｓ６０７でＮｏ）、複製対象選択部１７は、ステップＳ６０４以降を繰り返す。ステップＳ６０３において特定されたイベント群の全てを処理しても複製対象が選択されなかった場合（Ｓ６０５でＮｏ）、複製対象選択部１７は、当該イベント群の中で、最下流のイベントを複製対象として選択する（Ｓ６０９）。なお、ステップＳ６０９は、図９のステップＳ６０において説明した選択条件の（３）に該当するケースである。
【００９１】
このようにして、複製対象選択部１７は、複製対象を選択することができる。
【００９２】
続いて、図９のステップＳ７０の詳細について説明する。図２３は、イベントの複製処理の処理手順の一例を説明するためのフローチャートである。
【００９３】
ステップＳ７０１において、ノード複製部１８は、複製対象のイベントに対応する行及び列の複製を隣接行列Ｍ２（図１９）に生成する。すなわち、当該行及び列が二重化される。
【００９４】
図２４は、複製対象のイベントに対応する行及び列の複製の例を示す図である。同図では、隣接行列Ｍ２にいて、複製対象として選択された「スリップ」に係る行及び列のそれぞれの複製の生成によって、隣接行列Ｍ４が作成された例が示されている。なお、隣接行列Ｍ４において、「スリップａ」、「スリップｂ」は、それぞれ、図１０等の「スリップｎ１ａ」、「スリップｎ１ｂ」に対応する。
【００９５】
続いて、図９のステップＳ８０の詳細について説明する。図２５は、冗長エッジの削除処理の処理手順の一例を説明するためのフローチャートである。
【００９６】
ステップＳ８０１において、冗長エッジ削除部１９は、隣接行列Ｍ４（図２４）において複製に係る各イベントについて、直接下流イベントとの関係を排他的に削除する。ここでいう複製に係る各イベントは、複製元及び複製先の双方を含む。排他的とは、複製元のイベントと直接下流イベントとの関係の中で削除される関係と、複製先のイベントと直接下流イベントとの関係の中で削除される関係とが重複しないことをいう。
【００９７】
例えば、図２６は、複製された各イベントに関する直接下流イベントとの関係の排他的な削除の例を示す図である。同図に示される隣接行列Ｍ４では、スリップａ及びｂが、複製された各イベントに相当する。
【００９８】
隣接行列Ｍ４より明らかなように、スリップａ及びｂの直接下流イベントは、「センターラインオーバー」及び「追突」である。ここで、スリップａに関して、「センターラインオーバー」との関係が削除され、スリップｂに関して「追突」との関係が削除される形態が、上記でいう排他的な削除に相当する。同図では、当該排他的な削除の結果、隣接行列Ｍ５が生成されている。なお、スリップａに関して、「追突」との関係が削除され、スリップｂに関して「センターラインオーバー」との関係が削除されてもよい。
【００９９】
すなわち、ここでいう排他的な削除は、複製元及び複製先のノードのいずれか一方からカレント非存在パスに属するエッジを削除し、他方からカレント非存在パスに属さないエッジを削除することに相当する。
【０１００】
なお、仮に、スリップａ及びｂに関して、直接下流イベントが３つ以上有る場合、冗長エッジ削除部１９は、当該直接下流イベントをカレント非存在パス上に有るイベントとそうでないイベントとのグループに分類する。冗長エッジ削除部１９は、一方のグループに属する各イベントとスリップａとの組み合わせに係るセルの値を「０」とし、他方のグループに属する各イベントとスリップｂとの組み合わせに係るセルの値を「０」とする。
【０１０１】
続いて、冗長エッジ削除部１９は、隣接行列Ｍ５を、隣接行列Ｍ５に対応する新たな可到達行列Ｍ６に代入する（Ｓ８０２）。続いて、冗長エッジ削除部１９は、可到達行列Ｍ６に、隣接行列Ｍ５を乗じ、新たな可到達行列を得る（Ｓ８０３）。当該乗算は、可到達行列Ｍ６が変化しなくなるまで行われる（Ｓ８０４）。すなわち、演算結果が変化しなくなるまで、隣接行列Ｍ５がＮ乗される。その結果、図２７に示される可到達行列Ｍ６が得られる。
【０１０２】
図２７は、直接下流イベントの削除後の隣接行列に基づく可到達行列の例を示す図である。同図には、隣接行列Ｍ５がＮ乗されて、可到達行列Ｍ６が生成された例が湿されている。
【０１０３】
ステップＳ８０５に進み、冗長エッジ削除部１９は、複製に係る各イベント（複製元及び複製先の双方を含む。）のいずれかの上流側の直接的な関係（エッジ）の一つを処理対象として選択する（Ｓ８０５）。
【０１０４】
続いて、冗長エッジ削除部１９は、選択された関係（以下、「選択関係」という。）を隣接行列Ｍ５より削除し、削除後の隣接行列に基づく可到達行列を再計算する（Ｓ８０６）。続いて、冗長エッジ削除部１９は、再計算された可到達行列と、当初存在パスのみを示す可到達行列Ｍ１（図１８）とを比較して、選択された関係の削除によって、当初存在パスが除去されたか否かを判定する（Ｓ８０７）。
【０１０５】
当初存在パスが除去されていない場合（Ｓ８０７でＮｏ）、冗長エッジ削除部１９は、選択関係を削除対象とする（Ｓ８０８）。一方、当初存在パスが除去された場合（Ｓ８０７でＹｅｓ）、選択関係は削除対象とされず、ステップＳ８０５以降が繰り返される。
【０１０６】
上記したステップＳ８０５〜Ｓ８０７について、図を用いて説明する。図２８及び図２９は、上流側の関係の削除を説明するための図である。
【０１０７】
図２８において、隣接行列Ｍ５ａは、隣接行列Ｍ５より、「急ブレーキ→スリップａ」に係る関係が削除された結果である。また、可到達行列Ｍ６ａは、隣接行列Ｍ５ａに基づいて再計算された可到達行列である。可到達行列Ｍ６ａと可到達行列Ｍ１（図１８）とを比較すると、可到達行列Ｍ６ａには、可到達行列Ｍ１に存在している「直進→追突」又は「急ブレーキ→追突」に係る関係（パス）が存在しない。すなわち、「急ブレーキ→スリップａ」に係る関係（エッジ）の削除は、当初存在パスの除去を招いてしまう。したがって、「急ブレーキ→スリップａ」に係る関係は削除対象とされない。なお、可到達行列Ｍ６ａには、「直進→スリップａ」、「急ブレーキ→スリップａ」に係る関係も存在しないが、「直進→スリップｂ」、「急ブレーキ→スリップｂ」が存在するため問題は無い。
【０１０８】
また、図２８において、隣接行列Ｍ５ｂは、隣接行列Ｍ５より、「急ブレーキ→スリップｂ」に係る関係が削除された結果である。また、可到達行列Ｍ６ｂは、隣接行列Ｍ５ｂに基づいて再計算された可到達行列である。可到達行列Ｍ６ｂと可到達行列Ｍ１（図１８）とを比較すると、可到達行列Ｍ６ｂには、可到達行列Ｍ１に存在している「急ブレーキ→センターラインオーバー」又は「急ブレーキ→正面衝突」に係る関係（パス）が存在しない。すなわち、「急ブレーキ→スリップｂ」に係る関係（エッジ）の削除は、当初存在パスの除去を招いてしまう。したがって、「急ブレーキ→スリップｂ」に係る関係は削除対象とされない。なお、可到達行列Ｍ６ｂには、「直進→スリップｂ」、「急ブレーキ→スリップｂ」に係る関係も存在しないが、「直進→スリップａ」、「急ブレーキ→スリップａ」が存在するため問題は無い。
【０１０９】
また、図２９において、隣接行列Ｍ５ｃは、隣接行列Ｍ５より、「オーバースピード→スリップａ」に係る関係が削除された結果である。また、可到達行列Ｍ６ｃは、隣接行列Ｍ５ｃに基づいて再計算された可到達行列である。可到達行列Ｍ６ｃと可到達行列Ｍ１（図１８）とを比較すると、可到達行列Ｍ６ｃには、可到達行列Ｍ１における「オーバースピード→スリップ」に対応する「オーバースピード→スリップａ」に係る関係（パス）が存在しないが、「オーバースピード→スリップｂ」に係る関係（パス）が存在するため問題は無い。すなわち、「オーバースピード→スリップａ」に係る関係（エッジ）の削除は、当初存在パスの除去を伴わない。したがって、「オーバースピード→スリップａ」は削除対象とされる。
【０１１０】
また、図２９において、隣接行列Ｍ５ｄは、隣接行列Ｍ５より、「オーバースピード→スリップｂ」に係る関係が削除された結果である。また、可到達行列Ｍ６ｄは、隣接行列Ｍ５ｄに基づいて再計算された可到達行列である。可到達行列Ｍ６ｄと可到達行列Ｍ１（図１８）とを比較すると、可到達行列Ｍ６ｄには、可到達行列Ｍ１に存在している「オーバースピード→スリップ」、「オーバースピード→センターラインオーバー」、又は「オーバースピード→正面衝突」に係る関係（パス）が存在しない。すなわち、「オーバースピード→スリップｂ」に係る関係（エッジ）の削除は、当初存在パの除去を招いてしまう。したがって、「オーバースピード→スリップｂ」に係る関係は削除対象とされない
なお、図２８及び図２９を用いて説明した削除対象の判定結果は、図１２と一致する。
【０１１１】
上述したように、イベント間の関係を示す行列に基づく処理によって、非存在パスの特定、複製対象とするノードの選択、及び削除対象とする関係（冗長エッジ）の判定等が行われてもよい。
【０１１２】
なお、本実施の形態において、非存在パス特定部１６は、特定部の一例である。冗長エッジ削除部１９は、削除部の一例である。イベントフロー記憶部２２は、有向グラフ記憶部の一例である。
【０１１３】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【０１１４】
以上の説明に関し、更に以下の項を開示する。
（付記１）
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定する特定部と、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成する複製部と、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する削除部とを有する有向グラフ作成装置。
（付記２）
前記削除部は、複製元のノード又は複製先のノードの下流側に接続するエッジの中で、前記特定された経路に属するエッジを複製元及び複製先のノードの一方より削除し、前記特定された経路に属さないエッジを複製元及び複製先のノードの他方より削除する付記１記載の有向グラフ作成装置。
（付記３）
前記削除部は、前記下流側に接続するエッジを削除した後に、複製元のノード又は複製先のノードの上流側に接続するエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する付記２記載の有向グラフ生成装置。
（付記４）
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定し、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成し、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する処理をコンピュータが実行する有向グラフ作成方法。
（付記５）
前記削除する処理は、複製元のノード又は複製先のノードの下流側に接続するエッジの中で、前記特定された経路に属するエッジを複製元及び複製先のノードの一方より削除し、前記特定された経路に属さないエッジを複製元及び複製先のノードの他方より削除する付記４記載の有向グラフ作成方法。
（付記６）
前記削除する処理は、前記下流側に接続するエッジを削除した後に、複製元のノード又は複製先のノードの上流側に接続するエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する付記５記載の有向グラフ生成方法。
（付記７）
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定し、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成し、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する処理をコンピュータに実行させる有向グラフ作成プログラム。
（付記８）
前記削除する処理は、複製元のノード又は複製先のノードの下流側に接続するエッジの中で、前記特定された経路に属するエッジを複製元及び複製先のノードの一方より削除し、前記特定された経路に属さないエッジを複製元及び複製先のノードの他方より削除する付記７記載の有向グラフ作成方法。
（付記９）
前記削除する処理は、前記下流側に接続するエッジを削除した後に、複製元のノード又は複製先のノードの上流側に接続するエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する付記８記載の有向グラフ生成方法。
【符号の説明】
【０１１５】
１０ イベントフロー作成装置
１１ 文書情報記憶部
１２ イベント連鎖抽出部
１３ 展開部
１４ 二項関係記憶部
１５ 統合部
１６ 非存在パス特定部
１７ 複製対象選択部
１８ ノード複製部
１９ 冗長エッジ削除部
２１ イベント連鎖記憶部
２２ イベントフロー記憶部
１００ ドライブ装置
１０１ 記録媒体
１０２ 補助記憶装置
１０３ メモリ装置
１０４ ＣＰＵ
１０５ 表示装置
１０６ 入力装置
Ｂ バス
【技術分野】
【０００１】
本発明は、有向グラフ作成装置、有向グラフ作成方法、及び有向グラフ作成プログラムに関する。
【背景技術】
【０００２】
事故等に関するトラブル情報の分析においては、トラブルが起きるまでの経過又は過程を分析することが重要である。経過又は過程を示す情報は、報告書等においてテキスト情報として記述されていることが一般的である。したがって、テキストマイニング技術を利用することにより、トラブルが起きるまでの経過又は過程を示す情報を、イベントの順序情報（以下、「イベント連鎖」という。）としてテキスト情報より抽出することが可能である。
【０００３】
図１は、テキスト情報からのイベント連鎖の抽出例を示す図である。同図では、交通事故の報告書を示すテキスト情報から抽出されたイベント連鎖の例が示されている。
【０００４】
イベント連鎖の情報を複数の事例にわたってマージした結果を示す有向グラフ（以下、「イベントフロー」という。）を得ることにより、複数の事例に共通するトラブル発生シナリオの抽出や、根本原因等の特定等を行うことができる（図1）。
【０００５】
図２は、イベントフローの例を示す図である。同図には、交通事故に関する５００件のレポートから作成されたイベントフローが示されている。同図のイベントフローからは、例えば、雨によって路面が不良な状態となり、スリップしてハンドル操作をミスした結果、重傷となった、といったシナリオが読み取れる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００２−２３６６９２号公報
【特許文献２】特開２００４−１７８２７０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
イベント連鎖をマージしてイベントフローを作成する方法として、イベント連鎖をイベントの順序付きの二項関係に展開して、それを再構成する方法がある。
【０００８】
例えば、図３は、３つの事例に関するイベント連鎖の例を示す図である。同図には、事例Ａに関するイベント連鎖Ａ、事例Ｂに関するイベント連鎖Ｂ、及び事例Ｃに関するイベント連鎖Ｃが示されている。
【０００９】
図３における各イベント連鎖をそれぞれ二項関係に展開すると、図４に示されるようになる。図４は、３つのイベント連鎖を二項関係に展開した例を示す図である。同図には、イベント連鎖Ａ、イベント連鎖Ｂ、及びイベント連鎖Ｃごとに、二項関係に展開された例が示されている。
【００１０】
図４に示される各二項関係を、当該二項関係の一方のイベントと他の二項関係の他方のイベントとの一致に基づいて再編成すると、図５に示されるようなイベントフローｅＦ１が得られる。
【００１１】
図５は、３つのイベント連鎖に関する二項関係を再編成して得られるイベントフローの例を示す図である。同図では、当初別々であったイベント連鎖がマージされ、全てのノードが相互に直接的又は間接的に接続された一つのイベントフローｅＦ１が形成されている。
【００１２】
以上のようなイベントフローの作成方法は、簡便で効率的ではあるが、元々のイベント連鎖には存在しなかったパス（経路）が、イベントフローに作成されてしまうという問題がある。ここでいう、パスは、ノード間の直接的又は間接的な接続関係をいう。
【００１３】
図６は、元々のイベント連鎖には存在しなかったパスを示す図である。同図に示されるパスｐ１〜ｐ４は、図５に示されるイベントフローｅＦ１には含まれるパスであるが、図３に示されるイベント連鎖Ａ〜Ｃのいずれにも含まれていない。
【００１４】
独立して発生した事象が組み合わさることによって、重大なトラブルが発生するということも考えられる。したがって、トラブル分析という目的においては、「存在しないが組み合わせとして考えられるパス」を洗い出すことが重要な場合もある。しかし、実際に起きたことを分析することが目的である場合においては、「もともと存在していたパス」と「もともとは存在していなかったパス」とを切り分けて分析できる必要がある。
【００１５】
そこで、複数のイベント連鎖が統合された有向グラフより元のイベント連鎖には存在しない経路を除去することのできる有向グラフ作成装置、有向グラフ作成方法、及び有向グラフ作成プログラムの提供を目的とする。
【課題を解決するための手段】
【００１６】
上記課題を解決するため、有向グラフ作成装置は、複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定する特定部と、特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成する複製部と、複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する削除部とを有する。
【発明の効果】
【００１７】
複数のイベント連鎖が統合された有向グラフより元のイベント連鎖には存在しない経路を除去することができる。
【図面の簡単な説明】
【００１８】
【図１】テキスト情報からのイベント連鎖の抽出例を示す図である。
【図２】イベントフローの例を示す図である。
【図３】３つの事例に関するイベント連鎖を示す図である。
【図４】３つのイベント連鎖を二項関係に展開した例を示す図である。
【図５】３つのイベント連鎖に関する二項関係を再編成して得られるイベントフローの例を示す図である。
【図６】元々のイベント連鎖には存在しなかったパスを示す図である。
【図７】本発明の実施の形態におけるイベントフロー作成装置のハードウェア構成例を示す図である。
【図８】本発明の実施の形態におけるイベントフロー作成装置の機能構成例を示す図である。
【図９】イベントフローの作成処理の処理手順の一例を説明するためのフローチャートである。
【図１０】ノードの複製の第一の例を示す図である。
【図１１】複製に係るノードに接続する下流側の冗長エッジの第一の削除例を示す図である。
【図１２】複製に係るノードに接続する上流側の冗長エッジの第一の削除例を示す図である。
【図１３】ノードの複製の第二の例を示す図である。
【図１４】複製に係るノードに接続する下流側の冗長エッジの第二の削除例を示す図である。
【図１５】複製に係るノードに接続する上流側の冗長エッジの第二の削除例を示す図である。
【図１６】非存在パスの特定処理の処理手順の一例を説明するためのフローチャートである。
【図１７】イベント連鎖ごとの隣接行列及び可到達行列の例を示す図である。
【図１８】全ての可到達行列の論理和の例を示す図である。
【図１９】イベント連鎖ごとの隣接行列の論理和の例を示す図である。
【図２０】当初存在パスを示す可到達行列と二項関係の統合によって作成されたイベントフローを示す可到達行列との差分の例を示す図である。
【図２１】複製対象の選択処理の処理手順の一例を説明するためのフローチャートである。
【図２２】複製対象の選択処理を説明するためのデータ図の一例である。
【図２３】イベントの複製処理の処理手順の一例を説明するためのフローチャートである。
【図２４】複製対象のイベントに対応する行及び列の複製の例を示す図である。
【図２５】冗長エッジの削除処理の処理手順の一例を説明するためのフローチャートである。
【図２６】複製された各イベントに関する直接下流イベントとの関係の排他的な削除の例を示す図である。
【図２７】直接下流イベントの削除後の隣接行列に基づく可到達行列の例を示す図である。
【図２８】上流側の関係の削除を説明するための図である。
【図２９】上流側の関係の削除を説明するための図である。
【発明を実施するための形態】
【００１９】
以下、図面に基づいて本発明の実施の形態を説明する。図７は、本発明の実施の形態におけるイベントフロー作成装置のハードウェア構成例を示す図である。図７のイベントフロー作成装置１０は、それぞれバスBで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、表示装置１０５、及び入力装置１０６等を有する。
【００２０】
イベントフロー作成装置１０での処理を実現するプログラムは、記録媒体１０１によって提供される。プログラムを記録した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２１】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従ってイベントフロー作成装置１０に係る機能を実現する。表示装置１０５はプログラムによるＧＵＩ（Graphical User Interface）等を表示する。入力装置１０６はキーボード及びマウス等であり、様々な操作指示を入力させるために用いられる。
【００２２】
なお、記録媒体１０１の一例としては、ＣＤ−ＲＯＭ、ＤＶＤディスク、又はＵＳＢメモリ等の可搬型の記録媒体が挙げられる。また、補助記憶装置１０２の一例としては、ＨＤＤ（Hard Disk Drive）又はフラッシュメモリ等が挙げられる。記録媒体１０１及び補助記憶装置１０２のいずれについても、コンピュータ読み取り可能な記録媒体に相当する。
【００２３】
図８は、本発明の実施の形態におけるイベントフロー作成装置の機能構成例を示す図である。同図において、イベントフロー作成装置１０は、文書情報記憶部１１、イベント連鎖抽出部１２、イベント連鎖記憶部２１、展開部１３、二項関係記憶部１４、統合部１５、イベントフロー記憶部２２、非存在パス特定部１６、複製対象選択部１７、ノード複製部１８、及び冗長エッジ削除部１９等を有する。文書情報記憶部１１は、例えば、補助記憶装置１０２、又はイベントフロー作成装置１０とネットワークを介して接続される記憶装置若しくはコンピュータを用いて実現可能である。イベント連作記憶部２１、二項関係記憶部１４、及びイベントフロー記憶部２２は、メモリ装置１０３、補助記憶装置１０２、又はイベントフロー作成装置１０とネットワークを介して接続される記憶装置若しくはコンピュータを用いて実現可能である。等と用いて実現可能である。イベント連鎖抽出部１２、展開部１３、統合部１５、非存在パス特定部１６、複製対象選択部１７、ノード複製部１８、及び冗長エッジ削除部１９は、イベントフロー作成装置１０にインストールされたプログラムがＣＰＵ１０４に実行させる処理により実現される。
【００２４】
文書情報記憶部１１は、例えば、事故の報告書等の複数の文書情報群を記憶する。なお、文書情報は、必ずしもテキスト形式のデータでなくてもよい。所定のワープロソフト等によって作成された文書データであってもよい。文書情報は、最終的にテキスト情報を抽出可能なデータであればよい。
【００２５】
イベント連鎖抽出部１２は、文書情報に含まれているイベント（以下、「イベント」という。）の順序情報（以下、「イベント連鎖」という。）を、文書情報ごとに抽出する。イベント連鎖の抽出方法は、公知技術に従えばよい。イベント連鎖抽出部１２は、抽出されたイベント連鎖を、イベント連鎖記憶部２１に記録する。
【００２６】
展開部１３は、イベント連鎖抽出部１２によって抽出された各イベント連鎖を、イベントの順序付きの二項関係に展開する。二項関係とは、イベント連鎖において相互に直接的な関係を有する二つのイベントの組み合わせをいう。直接的な関係とは、順序情報において隣接している関係をいう。また、イベントの順序付きであるから、直接的な関係を有する二つのイベントの順序関係は、二項関係において維持される。
【００２７】
二項関係記憶部１４は、展開部１３によって展開された二項関係を示す情報を記憶する。
【００２８】
統合部１５は、二項関係記憶部１４が記憶する各二項関係を、当該二項関係の一方のイベントと他の二項関係の他方のイベントとの一致に基づいて統合（又は接続）することにより、有向グラフを作成する。当該有向グラフの各ノード（節点）は、イベントを示す。また、当該有向グラフのエッジ（枝）は、イベントの順序関係（又は前後関係若しくは因果関係等）を示す。以下、当該有向グラフを、「イベントフロー」という。なお、統合部１５は、作成されたイベントフローをイベントフロー記憶部２２に記録する。
【００２９】
非存在パス特定部１６は、イベントフローにおいて、各イベント連鎖においては存在していなかったパスを特定する。なお、イベントフローにおいて、任意のイベント間の経路（又は接続関係）を「パス」という。当該任意のイベントは、直接的に接続されていてもよいし、間接的に接続されていてもよい。また、イベント連鎖においては存在していなかったパスを「非存在パス」という。
【００３０】
複製対象選択部１７は、統合部１５によって作成されたイベントフローにおいて、複製対象とするノード（イベント）を選択する。ノード複製部１８は、複製対象選択部１７によって選択されたノードの複製を作成する。すなわち、ノードの複製とは、既存のノード及び当該ノードに接続する全てのエッジと同一のノード及びエッジを作成することをいう。したがって、ノードの複製によって、当該ノード及び当該ノードに接続する全てのエッジは２重化される。ノードの複製は、ノードの分割として解釈されてもよい。この場合、分割対象のノードに接続する全てのエッジも分割される。
【００３１】
なお、ノードが複製（又は２重化）されるのは、複数のイベント連鎖においては相互に独立していた、同一イベントに関する各ノードが、二項関係を統合する際に一つのノードに統合又は集約されたことが非存在パスの発生の原因であると考えるからである。したがって、一つに統合されたノードを複製によって改めて分割すれば、非存在パスを除去できると考えるからである。但し、闇雲にノードの複製が行われたのでは、元のイベント連鎖に戻ってしまいかねない。したがって、複製対象選択部１７は、複数のイベント連鎖に共通なシナリオを把握可能な状態が維持されるように、複製対象とするノードを選択する。
【００３２】
冗長エッジ削除部１９は、ノードの複製に伴って複製されたエッジのうち、当該エッジを削除したとしても、イベントフローにおいて、元のイベント連鎖が含む経路に影響しないエッジを削除する。元のイベント連鎖が含む経路に影響しないとは、元のイベント連鎖が含むいずれかのパスが失われないことをいう。
【００３３】
以下、イベントフロー作成装置１０の処理手順について説明する。図９は、イベントフローの作成処理の処理手順の一例を説明するためのフローチャートである。
【００３４】
例えば、入力装置１０６を介して入力される指示入力に応じ、イベント連鎖抽出部１２は、文書情報記憶部１１が記憶する文書情報ごとに、イベント連鎖を抽出し、抽出されたイベント連鎖をイベント連鎖記憶部２１に記録する（Ｓ１０）。文書情報からのイベント連鎖の抽出は、テキストマイニング技術等の公知技術を用いて行われればよい。例えば、特開２００２−２３６６９２号公報の段落番号００６６〜００６８に開示されている方法などを用いることにより、文書情報からイベントを抽出することが可能である。また、イベントが文書情報から抽出される順番（文書情報での出現位置）を用いることにより、イベント間の順序関係を特定することが可能である。この際、特定の接続詞が含まれる場合には、順序関係の逆転が行われてもよい。
【００３５】
なお、ここでは、便宜上、３つの文書情報から、図３に示されるイベント連鎖Ａ〜Ｃが抽出されたこととする。
【００３６】
続いて、展開部１３は、イベント連鎖記憶部２１に記録されたイベント連鎖Ａ〜Ｃのそれぞれを、二項関係に展開する（Ｓ２０）。すなわち、イベント連鎖Ａ〜Ｃのそれぞれから二項関係が抽出される。ここでは、図４に示される二項関係に抽出される。展開部１３は、抽出された二項関係を示す情報を二項関係記憶部１４に記録する。なお、二項関係を示す情報の記録形式は、所定のものに限定されない。上流側（原因側）のイベントを示す項目と、下流側（結果側又は終点側）のイベントを示す項目とを含むレコード群が構成するテーブル形式であってもよい。又は、ＸＭＬ（eXtensible Markup Language）形式等の構造化文書形式に当該情報が記録されてもよい。
【００３７】
続いて、統合部１５は、二項関係記憶部１４が記憶する各二項関係を、当該二項関係の一方のイベントと他の二項関係の他方のイベントとの一致に基づいて統合（又は接続）することにより、イベントフローを作成する（Ｓ３０）。統合部１５は、作成されたイベントフローをイベントフロー記憶部２２に記録する。ここでは、図５に示されるイベントフローｅＦ１が作成される。なお、二項関係からの有向グラフを作成は、例えば、特開２００４−１７８２７０号公報に開示されている方法を用いて行われてもよい。
【００３８】
続いて、非存在パス特定部１６は、イベントフロー記憶部２２及びイベント連鎖記憶部２１を参照して、イベントフローｅＦ１において、イベント連鎖Ａ、Ｂ、又はＣのいずれにも存在しないパス（非存在パス）を特定する（Ｓ４０）。非存在パスの特定は、イベントフローｅＦ１を、イベント連鎖Ａ、Ｂ、及びＣのそれぞれと比較することにより特定することができる。ここでは、図６に示される、パスｐ１〜ｐ４が、非存在パスとして特定される。
【００３９】
非存在パスが無い場合（Ｓ５０でＮｏ）、イベントフローｅＦ１が、最終的なイベントフローとして出力される。例えば、イベントフローｅＦ１を示すデータが補助記憶装置１０２に保存されてもよいし、表示装置１０５に表示されてもよい。
【００４０】
非存在パスが有る場合（Ｓ５０でＹｅｓ）、複製対象選択部１７は、特定された非存在パスのうちの任意の一つを選択して、当該非存在パス（以下、「カレント非存在パス」という。）上のノードの中から複製対象とするノード（イベント）を選択する（Ｓ６０）。ここで、複製対象の選択条件は、例えば、以下の通りである。
（１）カレント非存在パスの始点ノードと終点ノードとの間（すなわち、端点ノードの間）に挟まれているノードであること（したがって、当該始点ノード及び当該終点ノード等の端点ノードは選択対象から除かれる）。
（２）（１）に該当するノード群の中で、下流側のエッジが分岐している（下流側に複数のエッジが接続する）ノードのうち最も下流に位置すること。
（３）（２）に該当するノードが存在しない場合、（１）に該当するノード群の中で最も下流に位置すること。
【００４１】
例えば、図６のパスｐ１がカレント非存在パスである場合、複製対象は次のように選択される。
【００４２】
まず、パスｐ１において、始点ノードは「直進」であり、終点ノードは「センターオーバーライン」である。すなわち、この二つのノードは、イベント連鎖Ａ〜Ｃのいずれにおいても、直接的又は間接的に接続されていない。この二つのノードに挟まれるノードは、「急ブレーキ」及び「スリップ」である（条件（１））。「スリップ」の下流側には二つのノードが接続しており、かつ、「スリップ」は、「急ブレーキ」及び「スリップ」の中で最下流に位置する（条件（２））。したがって、「スリップ」が複製対象として選択される。
【００４３】
続いて、ノード複製部１８は、選択されたノード及び当該ノードに接続するエッジの複製を作成する（Ｓ７０）。
【００４４】
図１０は、ノードの複製の第一の例を示す図である。同図では、ノード「スリップ」の複製により、イベントフローｅＦ２が作成された例が示されている。イベントフローｅＦ２では、「スリップ」というイベントを示すノードが、「スリップｎ１ａ」と「スリップｎ１ｂ」との二つのノードに分割されている。また、ノード「スリップ」に接続する４つエッジ（ｅｄ１、ｅｄ２、ｅｄ３、ｅｄ４）の複製（ｅｄ１１、ｅｄ２１、ｅｄ３１、ｅｄ４１）も作成されている。なお、複製されたエッジは、複製元のエッジと同一の接続関係を維持する。
【００４５】
続いて冗長エッジ削除部１９は、イベントフローｅＦ２より、複製されたエッジの中から冗長なエッジを削除する（Ｓ８０）。まず、複製に係るノード（複製元及び複製先の双方を含む）の下流側のエッジに関して、冗長エッジ削除部１９は、カレント非存在パスに属するエッジとカレント非存在パスに属さないエッジとに分類する。冗長エッジ削除部１９は、複製元及び複製先のノードのいずれか一方からカレント非存在パスに属するエッジを削除し、他方からカレント非存在パスに属さないエッジを削除する。このことは、図上において、相互にクロスする二つのエッジ又は相互にクロスしない二つエッジを削除することに相当する。すなわち、重複するエッジのうち一方が冗長エッジとして削除される。重複するエッジとは、例えば、エッジｅｄ３及びエッジｅｄ３１のように、複製元ノード又は複製先ノードの区別をしない場合に同一のノード間（「スリップ」と「追突」）を接続するエッジである。
【００４６】
図１１は、複製に係るノードに接続する下流側の冗長エッジの第一の削除例を示す図である。同図では、イベントフローｅＦ２（図１０）において相互にクロスしていたエッジｅｄ３１及びｅｄ４１が冗長エッジとして削除され、イベントフローｅＦ３が作成された例が示されている。その結果、複製元又は複製先のノード「スリップｎ１ａ又はｎ１ｂ」は、それぞれ一つのエッジｅｄ３又はｅｄ４に接続されるようになる。但し、エッジｅｄ３及びｅｄ４が削除対象とされてもよい。
【００４７】
ここで、イベントフローｅＦ２（図１０）において、エッジｅｄ４及びｅｄ４１は、カレント非存在パス（パスｐ１）に属し、エッジｅｄ３及びｅｄ３１は、カレント非存在パスに属さない。複製元の「スリップｎ１ａ」からは、カレント非存在パスに属するエッジｅｄ４１が削除され、複製先の「スリップｎ１ｂ」からは、カレント非存在パスに属さないエッジｅｄ３１が削除された結果が、イベントフローｅＦ３（図１１）である。
【００４８】
なお、複製対象のノードが、複製前において下流側に３つ以上のノードと接続されている場合（下流側に３つ以上に分岐している場合）においても、複製後の下流側に接続するエッジの削除方法は基本的に上記した通りである。すなわち、冗長エッジ削除部１９は、カレント非存在パスに属するエッジとカレント非存在パスに属さないエッジとに分類する。冗長エッジ削除部１９は、複製元及び複製先のノードのいずれか一方からカレント非存在パスに属するエッジを削除し、他方からカレント非存在パスに属さないエッジを削除する。
【００４９】
複製ノードの下流側の冗長エッジの削除の後、上流側の冗長エッジの削除が行われる。複製に係るノードの上流側に接続するエッジに関しては、当該エッジを削除したことによって、イベント連鎖Ａ〜Ｃのいずれかにに含まれるパス（以下、「当初存在パス」という。）がイベントフローｅＦ３から失われない（除去されない）エッジのみが削除される。
【００５０】
例えば、「オーバースピード→スリップｎ１ａ」に関しては、当該関係を構成するエッジｅｄ２１が削除されても、当初存在パスのいずれかがが除去されることはない。イベント連鎖Ｃには、「オーバースピード→スリップ」を含むパスが存在するが、当該パスは、「オーバースピード→スリップｎ１ｂ」によって維持されるからである。したがって、「オーバースピード→スリップｎ１ａ」に係るエッジｅｄ２１は、冗長エッジとして削除される。一方、「急ブレーキ→スリップｎ１ｂ」に関しては、当該関係に係るエッジｅｄ１１が削除されてしまうと、「急ブレーキ→センターライン」という、当初存在パスが除去されてしまう。したがって、エッジｅｄ１１の削除は行われない。
【００５１】
図１２は、複製に係るノードに接続する上流側の冗長エッジの第一の削除例を示す図である。同図では、エッジｅｄ２１が削除され、イベントフローｅＦ４が作成された例が示されている。なお、同図と図６とを比較すると、イベントフローｅＦ４では、非存在パスｐ３及びｐ４が除去されていることが分かる。
【００５２】
ステップＳ４０以降は、非存在パスが特定されなくなるまで（非存在パスが無くなるまで）繰り返される。本実施の形態では、イベントフローｅＦ４に関して、非存在パスｐ１及びｐ２（図６参照）が存在する。したがって、イベントフローｅＦ４に関して、ステップＳ６０以降が実行される。ここでは、パスｐ１がカレント非存在パスとして選択されたこととする。この場合、イベントフローｅＦ４では、「急ブレーキ」が、ステップＳ６０の選択条件に合致する（Ｓ６０）。したがって、「急ブレーキ」、及び「急ブレーキ」に接続するエッジの複製が作成される（Ｓ７０）。
【００５３】
図１３は、ノードの複製の第二の例を示す図である。同図では、ノード「急ブレーキ」の複製により、イベントフローｅＦ５が作成された例が示されている。イベントフローｅＦ５では、「急ブレーキ」というイベントを示すノードが、「急ブレーキｎ２ａ」と「急ブレーキｎ２ｂ」との二つのノードに分割されている。また、ノード「スリップ」に接続する４つエッジ（ｅｄ５、ｅｄ６、ｅｄ１、ｅｄ１１）の複製（ｅｄ５１、ｅｄ６１、ｅｄ１ｃ、ｅｄ１１ｃ）も作成されている。
【００５４】
続いて、イベントフローｅＦ５に関して、冗長エッジが削除される（Ｓ８０）。まず、複製に係るノードの下流側に関して冗長エッジが削除される。
【００５５】
図１４は、複製に係るノードに接続する下流側の冗長エッジの第二の削除例を示す図である。同図では、イベントフローｅＦ５（図１３）において相互にクロスしていたエッジｅｄ１１及びｅｄ１ｃが冗長エッジとして削除され、イベントフローｅＦ６が作成された例が示されている。その結果、複製元又は複製先のノード「急ブレーキｎ２ａ又はｎ２ｂ」は、それぞれ一つのエッジｅｄ１又はｅｄ１１ｃに接続されるようになる。
【００５６】
一方、複製に係るノードの上流側に接続するエッジに関しては、当該エッジを削除したことによって、いずれかの当初存在パスがイベントフローｅＦ６から除去されないエッジのみが削除される。
【００５７】
図１５は、複製に係るノードに接続する上流側の冗長エッジの第二の削除例を示す図である。同図では、エッジｅｄ５１及びエッジｅｄ６１が削除され、イベントフローｅＦ７が作成された例外示されている。
【００５８】
ここで、図１５と図６とを比較すると、イベントフローｅＦ７では、非存在パスｐ１及びｐ２が更に除去されていることが分かる。したがって、イベントフローｅＦ７が、最終的なイベントフローとして出力される。
【００５９】
上述したように、本実施の形態によれば、二項関係に基づいて再編成されたイベントフローより、イベント連鎖には存在していなかったパスを除去又は排除することができる。た、複製対象が適切に選択されることにより、イベントフローの分割の程度を抑制することができる。その結果、複数のイベント連鎖に共通のシナリオを示すことができ、かつ、それぞれの文書情報に含まれていた順序関係又は因果関係等を示すイベントフローを作成することができる。
【００６０】
また、例えば、文書情報に含まれていた因果関係と、文書情報には含まれていなかった因果関係とを区別して分析することが可能となる。
【００６１】
ところで、上記において説明した処理手順において、非存在パスの特定、複製対象とするノードの選択、及び削除対象とする関係（冗長エッジ）を判定等に用いるデータのデータ形式は所定のものに限定されない。例えば、ＸＭＬ形式によってイベントフローを表現するデータであってもよいし、他のデータ形式が用いられてもよい。
【００６２】
以下においては、行列（マトリクス）を用いてステップＳ４０以降を実行する例を説明する。なお、以下の説明において作成される各行列は、例えば、メモリ装置１０３に記録される。
【００６３】
ステップＳ４０の詳細について説明する。図１６は、非存在パスの特定処理の処理手順の一例を説明するためのフローチャートである。
【００６４】
ステップＳ４０１〜Ｓ４０４は、イベント連鎖ごとに実行されるループ処理であるが、ここでは、便宜上、イベント連鎖Ａ、Ｂ、及びＣのそれぞれについて並列的に説明する。但し、実際に並列的に処理が行われてもよい。
【００６５】
ステップＳ４０１において、非存在パス特定部１６は、イベント連鎖Ａ、Ｂ、及びＣのそれぞれに関して隣接行列を作成する。
【００６６】
図１７は、イベント連鎖ごとの隣接行列及び可到達行列の例を示す図である。同図において、隣接行列ａＭＡ、ａＭＢ、及びａＭＣは、順番に、イベント連鎖Ａ、Ｂ、又はＣの隣接行列である。すなわち、各隣接行列には、対応するイベント連鎖において直接的な接続関係を有するイベントの組み合わせに対して「１」が記録されている。なお、行方向が上流側（原因側）のイベントであり、列方向が下流側（結果側）のイベントである。
【００６７】
隣接行列ａＭＡ、ａＭＢ、及びａＭＣは、イベント連鎖Ａ、Ｂ、又はＣのそれぞれの二項関係を示す行列であるともいえる。したがって、隣接行列ａＭＡ、ａＭＢ、及びａＭＣは、二項関係記憶部１４が記憶する情報に基づいて生成されてもよい。もちろん、隣接行列ａＭＡ、ａＭＢ、及びａＭＣは、イベント連鎖Ａ、Ｂ、又はＣより生成されてもよい。
【００６８】
続いて、非存在パス特定部１６は、隣接行列ａＭＡ、ａＭＢ、及びａＭＣを、それぞれに対応する新たな可到達行列ｒＭＡ、ｒＭＢ、又はｒＭＣに代入する（Ｓ４０２）。なお、図１７に示される可到達行列ｒＭＡ、ｒＭＢ、又はｒＭＣは、ステップＳ４０３及びＳ４０４の実行後の状態を示す。ここでは、３つの可到達行列が、隣接行列ａＭＡ、ａＭＢ、又はａＭＣによって初期化される。なお、可到達行列は、イベント連鎖において、直接的又は間接的な関係を有するイベントの組み合わせに「１」が記録される行列である。
【００６９】
続いて、非存在パス特定部１６は、各可到達行列に対して、隣接行列ａＭＡ、ａＭＢ、又はａＭＣを乗じ、新たな可到達行列を得る（Ｓ４０３）。ここで得られる可到達行列は、直接的な関係と、一つのイベントを間に挟む間接的な関係とを示す可到達行列である。各可到達行列に対する隣接行列ａＭＡ、ａＭＢ、又はａＭＣの乗算は、各可到達行列ｒＭＡ、ｒＭＢ、又はｒＭＣが変化しなくなるまで行われる（Ｓ４０４）。すなわち、演算結果が変化しなくなるまで、各隣接行列がＮ乗される。演算結果が変化しなくなった状態が、図１７に示される可到達行列ｒＭＡ、ｒＭＢ、及びｒＭＣである。したがって、可到達行列ｒＭＡ、ｒＭＢ、及びｒＭＣは、それぞれに対応するイベント連鎖において、各イベントの直接的又は間接的な全ての関係を示す可到達行列である。
【００７０】
可到達行列ｒＭＡ、ｒＭＢ、及びｒＭＣが得られると（Ｓ４０５でＹｅｓ）、非存在パス特定部１６は、全ての可到達行列（ｒＭＡ、ｒＭＢ、及びｒＭＣ）の論理和を算出する（Ｓ４０６）。
【００７１】
図１８は、全ての可到達行列の論理和の例を示す図である。同図に示される可到達行列Ｍ１は、可到達行列ｒＭＡ、ｒＭＢ、及びｒＭＣの論理和を示す。可到達行列Ｍ１は、イベント連鎖Ａ、Ｂ、又はＣにおいて、全ての当初存在パス（直接的又は間接的なものを含む。）を示す行列である。換言すれば、可到達行列Ｍ１において「１」が記録されていないパスは、非存在パスである。なお、可到達行列Ｍ１は、後段の処理において、当初存在パスを識別するために利用される。
【００７２】
続いて、非存在パス特定部１６は、イベント連鎖Ａ〜Ｃごとの隣接行列（ａＭＡ、ａＭＢ、及びａＭＣ）の論理和を算出する（Ｓ４０７）。
【００７３】
図１９は、イベント連鎖ごとの隣接行列の論理和の例を示す図である。同図において、隣接行列Ｍ２は、隣接行列ａＭＡ、ａＭＢ、及びａＭＣの論理和を示す。
【００７４】
続いて、非存在パス特定部１６は、隣接行列Ｍ２を、隣接行列Ｍ２に対応する新たな可到達行列Ｍ３に代入する（Ｓ４０８）。続いて、非存在パス特定部１６は、可到達行列Ｍ３に、隣接行列Ｍ２を乗じ、新たな可到達行列を得る（Ｓ４０９）。当該乗算は、可到達行列Ｍ３が変化しなくなるまで行われる（Ｓ４１０）。すなわち、演算結果が変化しなくなるまで、隣接行列Ｍ２がＮ乗される。演算結果が変化しなくなった状態が、図１９に示される可到達行列Ｍ３である。可到達行列Ｍ３は、二項関係の統合によって作成されるイベントフローｅＦ１における各イベントの直接的又は間接的な接続関係を示す可到達行列である。
【００７５】
ステップＳ４１１に進み、非存在パス特定部１６は、可到達行列Ｍ１（図１７）と、可到達行列Ｍ３（図１９）との差分を抽出する。すなわち、当初存在パスを示す可到達行列Ｍ１と、イベントフローｅＦ１を示す可到達行列との差分が抽出される。
【００７６】
図２０は、当初存在パスを示す可到達行列と二項関係の統合によって作成されたイベントフローを示す可到達行列との差分の例を示す図である。
【００７７】
同図では、可到達行列Ｍ３において、可到達行列Ｍ１との差分に係るセルは太枠で囲まれている。この差分は、図６に示されるパスｐ１〜ｐ４を示す。すなわち、「直進」と「センターラインオーバー」との組は、パスｐ１を示す。「直進」と「正面衝突」との組は、パスｐ２を示す。「カーブ」と「追突」との組は、パスｐ３を示す。「オーバースピード」と「追突」との組は、パスｐ４を示す。
【００７８】
このようにして、非存在パス特定部１６は、非存在パスを特定することができる。
【００７９】
続いて、図９のステップＳ６０の詳細について説明する。図２１は、複製対象の選択処理の処理手順の一例を説明するためのフローチャートである。
【００８０】
ステップＳ６０１において、複製対象選択部１７は、非存在パス特定部１６によって特定された非存在パスの中から一つの非存在パスを選択する。ここで、選択された非存在パスが、「カレント非存在パス」である。
【００８１】
図２２は、複製対象の選択処理を説明するためのデータ図の一例である。同図では、図１６との対応関係を示すステップ番号が記されている。図２２のステップＳ６０１では、可到達行列Ｍ３において、「直進→センターラインオーバー」に係るパスが選択された例が示されている。
【００８２】
続いて、複製対象選択部１７は、カレント非存在パスに含まれるイベントの中で、カレント非存在パスの始点のイベントより下流のイベント（以下、「下流イベント」という。）と、カレント非存在パスの終点のイベントより上流のイベント（以下、「上流イベント」という。）とを取得する（Ｓ６０２）。
【００８３】
カレント非存在パスの始点のイベントより下流のイベントに該当するイベントは、図２２のステップＳ６０２に対応する可到達行列Ｍ３ａにおいて、太枠で囲まれている列に係るイベントである。すなわち、カレント非存在パスに係る行において、「１」が記録されている列のうち、始点のイベント「直進」よりも右側の列に係るイベントである。
【００８４】
また、カレント非存在パスの終点のイベントより上流のイベントに該当するイベントは、図２２のステップＳ６０２に対応する可到達行列Ｍ３ｂにおいて、太枠で囲まれている行に係るイベントである。すなわち、カレント非存在パスに係る列において、「１」が記録されている行のうち、終点のイベント「センターラインオーバー」よりも上側に係るイベントである。
【００８５】
続いて、複製対象選択部１７は、下流イベント（急ブレーキ、スリップ、センターラインオーバー、正面衝突、追突）と、上流イベント（路面凍結、直進、カーブ、急ブレーキ、オーバースピード、スリップ）との論理積を算出する（Ｓ６０３）。当該論理積によって、カレント非存在パスにおいて始点のイベントと終点のイベントとに挟まれるイベント群が特定される。なお、ここでは、「急ブレーキ」及び「スリップ」が特定される。
【００８６】
続いて、複製対象選択部１７は、特定されたイベント群の中で、下流から順に未処理のイベントの一つを取得する（Ｓ６０４）。未処理とは、ステップＳ６０６以降の処理対象とされていないことをいう。下流から順であるから、最初は、当該イベント群の中で最下流のイベントが取得される。以下、取得されたイベントを「対象イベント」という。
【００８７】
対象イベントが取得された場合（Ｓ６０５でＹｅｓ）、複製対象選択部１７は、隣接行列Ｍ２を用いて、対象イベントの下流側に直接的に接続されるイベント（以下、「直接下流イベント」という。）を特定する（Ｓ６０６）。
【００８８】
図２２のステップＳ６０６では、隣接行列Ｍ２において、「急ブレーキ」と「スリップ」とのそれぞれの直接下流イベントの特定結果が示されている。図１９において説明したように、隣接行列Ｍ２は、隣接行列ａＭＡ、ａＭＢ、及びａＭＣの論理和である。したがって、隣接行列Ｍ２は、イベント間の直接的な関係のみを示す。よって、隣接行列Ｍ２において、「スリップ」又は「急ブレーキ」の行で「１」が記録されている列に係るイベントは、「急ブレーキ」又は「スリップ」の直接下流イベントということになる。同図では、「急ブレーキ」に関して１つの直接下流イベントと、「スリップ」に関して２つの直接下流イベントとが特定されている。なお、図２１のステップＳ６０６では、一つの対象イベントに関して直接下流イベントが特定されるが、図２２においては、便宜上、カレント非存在パスの始点と終点との間に挟まれる全てのイベントに関して、直接下流イベントが示されている。
【００８９】
続いて、複製対象選択部１７は、対象イベントに関する直接下流イベントの数は複数であるか否かを判定する（Ｓ６０７）。このことは、対象イベントの下流側のエッジが分岐しているか又は当該エッジが複数有るか否かの判定に相当する。対象イベントに関する直接下流イベントの数が複数である場合（Ｓ６０７でＹｅｓ）、複製対象選択部１７は、対象イベントを複製対象として選択する（Ｓ６０８）。対象イベントが「スリップ」であれば、直接下流イベントの数は複数である。したがって、「スリップ」が複製対象として選択される。なお、ステップＳ６０８は、図９のステップＳ６０において説明した選択条件の（２）に該当するケースである。
【００９０】
一方、直接下流イベントの数が複数でない場合（Ｓ６０７でＮｏ）、複製対象選択部１７は、ステップＳ６０４以降を繰り返す。ステップＳ６０３において特定されたイベント群の全てを処理しても複製対象が選択されなかった場合（Ｓ６０５でＮｏ）、複製対象選択部１７は、当該イベント群の中で、最下流のイベントを複製対象として選択する（Ｓ６０９）。なお、ステップＳ６０９は、図９のステップＳ６０において説明した選択条件の（３）に該当するケースである。
【００９１】
このようにして、複製対象選択部１７は、複製対象を選択することができる。
【００９２】
続いて、図９のステップＳ７０の詳細について説明する。図２３は、イベントの複製処理の処理手順の一例を説明するためのフローチャートである。
【００９３】
ステップＳ７０１において、ノード複製部１８は、複製対象のイベントに対応する行及び列の複製を隣接行列Ｍ２（図１９）に生成する。すなわち、当該行及び列が二重化される。
【００９４】
図２４は、複製対象のイベントに対応する行及び列の複製の例を示す図である。同図では、隣接行列Ｍ２にいて、複製対象として選択された「スリップ」に係る行及び列のそれぞれの複製の生成によって、隣接行列Ｍ４が作成された例が示されている。なお、隣接行列Ｍ４において、「スリップａ」、「スリップｂ」は、それぞれ、図１０等の「スリップｎ１ａ」、「スリップｎ１ｂ」に対応する。
【００９５】
続いて、図９のステップＳ８０の詳細について説明する。図２５は、冗長エッジの削除処理の処理手順の一例を説明するためのフローチャートである。
【００９６】
ステップＳ８０１において、冗長エッジ削除部１９は、隣接行列Ｍ４（図２４）において複製に係る各イベントについて、直接下流イベントとの関係を排他的に削除する。ここでいう複製に係る各イベントは、複製元及び複製先の双方を含む。排他的とは、複製元のイベントと直接下流イベントとの関係の中で削除される関係と、複製先のイベントと直接下流イベントとの関係の中で削除される関係とが重複しないことをいう。
【００９７】
例えば、図２６は、複製された各イベントに関する直接下流イベントとの関係の排他的な削除の例を示す図である。同図に示される隣接行列Ｍ４では、スリップａ及びｂが、複製された各イベントに相当する。
【００９８】
隣接行列Ｍ４より明らかなように、スリップａ及びｂの直接下流イベントは、「センターラインオーバー」及び「追突」である。ここで、スリップａに関して、「センターラインオーバー」との関係が削除され、スリップｂに関して「追突」との関係が削除される形態が、上記でいう排他的な削除に相当する。同図では、当該排他的な削除の結果、隣接行列Ｍ５が生成されている。なお、スリップａに関して、「追突」との関係が削除され、スリップｂに関して「センターラインオーバー」との関係が削除されてもよい。
【００９９】
すなわち、ここでいう排他的な削除は、複製元及び複製先のノードのいずれか一方からカレント非存在パスに属するエッジを削除し、他方からカレント非存在パスに属さないエッジを削除することに相当する。
【０１００】
なお、仮に、スリップａ及びｂに関して、直接下流イベントが３つ以上有る場合、冗長エッジ削除部１９は、当該直接下流イベントをカレント非存在パス上に有るイベントとそうでないイベントとのグループに分類する。冗長エッジ削除部１９は、一方のグループに属する各イベントとスリップａとの組み合わせに係るセルの値を「０」とし、他方のグループに属する各イベントとスリップｂとの組み合わせに係るセルの値を「０」とする。
【０１０１】
続いて、冗長エッジ削除部１９は、隣接行列Ｍ５を、隣接行列Ｍ５に対応する新たな可到達行列Ｍ６に代入する（Ｓ８０２）。続いて、冗長エッジ削除部１９は、可到達行列Ｍ６に、隣接行列Ｍ５を乗じ、新たな可到達行列を得る（Ｓ８０３）。当該乗算は、可到達行列Ｍ６が変化しなくなるまで行われる（Ｓ８０４）。すなわち、演算結果が変化しなくなるまで、隣接行列Ｍ５がＮ乗される。その結果、図２７に示される可到達行列Ｍ６が得られる。
【０１０２】
図２７は、直接下流イベントの削除後の隣接行列に基づく可到達行列の例を示す図である。同図には、隣接行列Ｍ５がＮ乗されて、可到達行列Ｍ６が生成された例が湿されている。
【０１０３】
ステップＳ８０５に進み、冗長エッジ削除部１９は、複製に係る各イベント（複製元及び複製先の双方を含む。）のいずれかの上流側の直接的な関係（エッジ）の一つを処理対象として選択する（Ｓ８０５）。
【０１０４】
続いて、冗長エッジ削除部１９は、選択された関係（以下、「選択関係」という。）を隣接行列Ｍ５より削除し、削除後の隣接行列に基づく可到達行列を再計算する（Ｓ８０６）。続いて、冗長エッジ削除部１９は、再計算された可到達行列と、当初存在パスのみを示す可到達行列Ｍ１（図１８）とを比較して、選択された関係の削除によって、当初存在パスが除去されたか否かを判定する（Ｓ８０７）。
【０１０５】
当初存在パスが除去されていない場合（Ｓ８０７でＮｏ）、冗長エッジ削除部１９は、選択関係を削除対象とする（Ｓ８０８）。一方、当初存在パスが除去された場合（Ｓ８０７でＹｅｓ）、選択関係は削除対象とされず、ステップＳ８０５以降が繰り返される。
【０１０６】
上記したステップＳ８０５〜Ｓ８０７について、図を用いて説明する。図２８及び図２９は、上流側の関係の削除を説明するための図である。
【０１０７】
図２８において、隣接行列Ｍ５ａは、隣接行列Ｍ５より、「急ブレーキ→スリップａ」に係る関係が削除された結果である。また、可到達行列Ｍ６ａは、隣接行列Ｍ５ａに基づいて再計算された可到達行列である。可到達行列Ｍ６ａと可到達行列Ｍ１（図１８）とを比較すると、可到達行列Ｍ６ａには、可到達行列Ｍ１に存在している「直進→追突」又は「急ブレーキ→追突」に係る関係（パス）が存在しない。すなわち、「急ブレーキ→スリップａ」に係る関係（エッジ）の削除は、当初存在パスの除去を招いてしまう。したがって、「急ブレーキ→スリップａ」に係る関係は削除対象とされない。なお、可到達行列Ｍ６ａには、「直進→スリップａ」、「急ブレーキ→スリップａ」に係る関係も存在しないが、「直進→スリップｂ」、「急ブレーキ→スリップｂ」が存在するため問題は無い。
【０１０８】
また、図２８において、隣接行列Ｍ５ｂは、隣接行列Ｍ５より、「急ブレーキ→スリップｂ」に係る関係が削除された結果である。また、可到達行列Ｍ６ｂは、隣接行列Ｍ５ｂに基づいて再計算された可到達行列である。可到達行列Ｍ６ｂと可到達行列Ｍ１（図１８）とを比較すると、可到達行列Ｍ６ｂには、可到達行列Ｍ１に存在している「急ブレーキ→センターラインオーバー」又は「急ブレーキ→正面衝突」に係る関係（パス）が存在しない。すなわち、「急ブレーキ→スリップｂ」に係る関係（エッジ）の削除は、当初存在パスの除去を招いてしまう。したがって、「急ブレーキ→スリップｂ」に係る関係は削除対象とされない。なお、可到達行列Ｍ６ｂには、「直進→スリップｂ」、「急ブレーキ→スリップｂ」に係る関係も存在しないが、「直進→スリップａ」、「急ブレーキ→スリップａ」が存在するため問題は無い。
【０１０９】
また、図２９において、隣接行列Ｍ５ｃは、隣接行列Ｍ５より、「オーバースピード→スリップａ」に係る関係が削除された結果である。また、可到達行列Ｍ６ｃは、隣接行列Ｍ５ｃに基づいて再計算された可到達行列である。可到達行列Ｍ６ｃと可到達行列Ｍ１（図１８）とを比較すると、可到達行列Ｍ６ｃには、可到達行列Ｍ１における「オーバースピード→スリップ」に対応する「オーバースピード→スリップａ」に係る関係（パス）が存在しないが、「オーバースピード→スリップｂ」に係る関係（パス）が存在するため問題は無い。すなわち、「オーバースピード→スリップａ」に係る関係（エッジ）の削除は、当初存在パスの除去を伴わない。したがって、「オーバースピード→スリップａ」は削除対象とされる。
【０１１０】
また、図２９において、隣接行列Ｍ５ｄは、隣接行列Ｍ５より、「オーバースピード→スリップｂ」に係る関係が削除された結果である。また、可到達行列Ｍ６ｄは、隣接行列Ｍ５ｄに基づいて再計算された可到達行列である。可到達行列Ｍ６ｄと可到達行列Ｍ１（図１８）とを比較すると、可到達行列Ｍ６ｄには、可到達行列Ｍ１に存在している「オーバースピード→スリップ」、「オーバースピード→センターラインオーバー」、又は「オーバースピード→正面衝突」に係る関係（パス）が存在しない。すなわち、「オーバースピード→スリップｂ」に係る関係（エッジ）の削除は、当初存在パの除去を招いてしまう。したがって、「オーバースピード→スリップｂ」に係る関係は削除対象とされない
なお、図２８及び図２９を用いて説明した削除対象の判定結果は、図１２と一致する。
【０１１１】
上述したように、イベント間の関係を示す行列に基づく処理によって、非存在パスの特定、複製対象とするノードの選択、及び削除対象とする関係（冗長エッジ）の判定等が行われてもよい。
【０１１２】
なお、本実施の形態において、非存在パス特定部１６は、特定部の一例である。冗長エッジ削除部１９は、削除部の一例である。イベントフロー記憶部２２は、有向グラフ記憶部の一例である。
【０１１３】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【０１１４】
以上の説明に関し、更に以下の項を開示する。
（付記１）
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定する特定部と、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成する複製部と、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する削除部とを有する有向グラフ作成装置。
（付記２）
前記削除部は、複製元のノード又は複製先のノードの下流側に接続するエッジの中で、前記特定された経路に属するエッジを複製元及び複製先のノードの一方より削除し、前記特定された経路に属さないエッジを複製元及び複製先のノードの他方より削除する付記１記載の有向グラフ作成装置。
（付記３）
前記削除部は、前記下流側に接続するエッジを削除した後に、複製元のノード又は複製先のノードの上流側に接続するエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する付記２記載の有向グラフ生成装置。
（付記４）
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定し、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成し、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する処理をコンピュータが実行する有向グラフ作成方法。
（付記５）
前記削除する処理は、複製元のノード又は複製先のノードの下流側に接続するエッジの中で、前記特定された経路に属するエッジを複製元及び複製先のノードの一方より削除し、前記特定された経路に属さないエッジを複製元及び複製先のノードの他方より削除する付記４記載の有向グラフ作成方法。
（付記６）
前記削除する処理は、前記下流側に接続するエッジを削除した後に、複製元のノード又は複製先のノードの上流側に接続するエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する付記５記載の有向グラフ生成方法。
（付記７）
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定し、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成し、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する処理をコンピュータに実行させる有向グラフ作成プログラム。
（付記８）
前記削除する処理は、複製元のノード又は複製先のノードの下流側に接続するエッジの中で、前記特定された経路に属するエッジを複製元及び複製先のノードの一方より削除し、前記特定された経路に属さないエッジを複製元及び複製先のノードの他方より削除する付記７記載の有向グラフ作成方法。
（付記９）
前記削除する処理は、前記下流側に接続するエッジを削除した後に、複製元のノード又は複製先のノードの上流側に接続するエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する付記８記載の有向グラフ生成方法。
【符号の説明】
【０１１５】
１０ イベントフロー作成装置
１１ 文書情報記憶部
１２ イベント連鎖抽出部
１３ 展開部
１４ 二項関係記憶部
１５ 統合部
１６ 非存在パス特定部
１７ 複製対象選択部
１８ ノード複製部
１９ 冗長エッジ削除部
２１ イベント連鎖記憶部
２２ イベントフロー記憶部
１００ ドライブ装置
１０１ 記録媒体
１０２ 補助記憶装置
１０３ メモリ装置
１０４ ＣＰＵ
１０５ 表示装置
１０６ 入力装置
Ｂ バス
【特許請求の範囲】
【請求項１】
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定する特定部と、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成する複製部と、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する削除部とを有する有向グラフ作成装置。
【請求項２】
前記削除部は、複製元のノード又は複製先のノードの下流側に接続するエッジの中で、前記特定された経路に属するエッジを複製元及び複製先のノードの一方より削除し、前記特定された経路に属さないエッジを複製元及び複製先のノードの他方より削除する請求項１記載の有向グラフ作成装置。
【請求項３】
前記削除部は、前記下流側に接続するエッジを削除した後に、複製元のノード又は複製先のノードの上流側に接続するエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する請求項２記載の有向グラフ生成装置。
【請求項４】
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定し、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成し、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する処理をコンピュータが実行する有向グラフ作成方法。
【請求項５】
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定し、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成し、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する処理をコンピュータに実行させる有向グラフ作成プログラム。
【請求項１】
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定する特定部と、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成する複製部と、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する削除部とを有する有向グラフ作成装置。
【請求項２】
前記削除部は、複製元のノード又は複製先のノードの下流側に接続するエッジの中で、前記特定された経路に属するエッジを複製元及び複製先のノードの一方より削除し、前記特定された経路に属さないエッジを複製元及び複製先のノードの他方より削除する請求項１記載の有向グラフ作成装置。
【請求項３】
前記削除部は、前記下流側に接続するエッジを削除した後に、複製元のノード又は複製先のノードの上流側に接続するエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する請求項２記載の有向グラフ生成装置。
【請求項４】
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定し、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成し、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する処理をコンピュータが実行する有向グラフ作成方法。
【請求項５】
複数のイベント連鎖を記憶するイベント連鎖記憶部と、該複数のイベント連鎖を統合して作成された有向グラフを記憶する有向グラフ記憶部とを参照して、該有向グラフが含む経路の中で、該複数のイベント連鎖のいずれにも存在しない経路を特定し、
特定された経路において下流側に複数のエッジが接続するノードの中で該経路の端点ノードを除く最下流のノード及び該ノードに接続するエッジの複製を作成し、
複製されたエッジの中で、当該エッジを削除したとしても前記複数のイベント連鎖が含むいずれかの経路が前記有向グラフから除去されないエッジを削除する処理をコンピュータに実行させる有向グラフ作成プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【公開番号】特開２０１２−１９４７０８（Ｐ２０１２−１９４７０８Ａ）
【公開日】平成２４年１０月１１日（２０１２．１０．１１）
【国際特許分類】
【出願番号】特願２０１１−５７２６９（Ｐ２０１１−５７２６９）
【出願日】平成２３年３月１５日（２０１１．３．１５）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年１０月１１日（２０１２．１０．１１）
【国際特許分類】
【出願日】平成２３年３月１５日（２０１１．３．１５）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]