JP5630863B2 - 構造化文書に含まれるノードの全順序関係を、ログ情報に基づいて決定して可視化する方法、装置及びコンピュータプログラム - Google Patents

Description

本発明は、構造化文書に含まれるノードの全順序関係を、ログ情報に基づいて決定して可視化する方法、装置及びコンピュータプログラムに関する。

近年、視覚障害者であってもネットサーフィン等を楽しめるよう、ユーザ操作の挙動を分析する必要性が高まっている。ウェブページのような構造化文書については、ユーザの操作に関するログ情報に基づいて、構造化文書に含まれるノード間の順序関係を正しく推定することが要求される。

ここで、ログ情報とは、例えばブラウザ機能を拡張して、ウェブページ内でのノード間の移動軌跡を記録した情報である。ログ情報には、ユーザの操作に関する情報、構造化文書においてユーザが指示するカーソルの現在位置に対応するノードと、カーソルが次に移動する位置に対応するノードとの間の相対的な位置関係に関する情報が含まれる。

また、例えばウェブページに記載してある文書の構造化は、ＨＴＭＬのソースで構造を示すタグを付与することで行われる。ウェブページ内の様々な文章、画像等に対して、この部分は「見出し」、この部分は「段落」、この部分は「強調して伝えたい部分」といった構造を示すタグを付与することで、文章を構造化している。

特開平０８−２６３５１８号公報 特開２００９−０４３１０２号公報 特許第３６１９０１５号公報 特開２００２−１８９５９５号公報 特開２００８−１７６５２８号公報 特開２００１−１３４３６０号公報 特開平０９−１６０８２１号公報 特開２００５−１１５４９８号公報 特開２００３−１５０２９６号公報 特開２００２−３３４０７０号公報

しかし、ログ情報に基づいて構造化文書に含まれるノード間の順序関係を推定しようとした場合、ノード間の半順序関係、すなわち構造化文書においてユーザが指示するカーソルの現在位置に対応するノードと、カーソルが次に移動する位置に対応するノードとの相対的位置関係を特定することはできるものの、対象とする構造化文書にいわゆる「正しい全順序」が存在すると仮定したときであっても、ノード間の順序関係を含む全順序関係を一義的に決定することは困難であるという問題点があった。

例えば構造化文書が木構造を有している場合、実際のノード間の順序関係と、ログ情報から推定されるノード間の順序関係とが矛盾しないように全順序関係を決定することは困難であり、特に動的にノードが追加又は削除される場合には、ノード間の順序関係を正しく推定すること自体も困難となる。

本発明は斯かる事情に鑑みてなされたものであり、構造化文書に含まれるノードの全順序関係を、ログ情報に基づいて正しく一義的に決定して可視化する方法、装置及びコンピュータプログラムを提供することを目的とする。

上記目的を達成するために第１発明に係る方法は、構造化文書に含まれるノードの全順序関係を、ノード間遷移に関するログ情報に基づいて決定して可視化する情報処理装置で実行することが可能な方法において、前記情報処理装置は、構造化文書に含まれるノード間の遷移に関する情報を時系列に記憶した、少なくともノードに対する操作の種類を含むログ情報を取得する工程と、取得したログ情報に基づいて、遷移するノード間の相対的位置関係を特定する工程と、特定したノード間の相対的位置関係を制約条件としてトポロジカルソートを実行して構造化文書に含まれるノードの全順序関係を決定する工程とを含み、前記構造化文書に含まれるノードが追加又は削除された場合、ノードのコンテンツに対応するデータに基づいてノードの全順序関係を決定する。

また、第２発明に係る方法は、第１発明において、前記情報処理装置は、決定したノードの全順序関係を表示する工程を含む。

また、第３発明に係る方法は、第１又は第２発明において、前記ログ情報は、少なくともノード間の移動量に関する情報を含み、前記情報処理装置は、該ノード間の移動量に関する情報に基づいて、前記相対的位置関係を特定する。

また、第４発明に係る方法は、第１乃至第３発明のいずれか１つにおいて、前記構造化文書は木構造を有し、前記ログ情報は、ノードを識別する識別情報、ノードに対する前記操作が行われた相対時刻、及びノードのコンテンツに対応するデータを少なくとも含み、前記情報処理装置は、前記識別情報及び前記コンテンツに対応するデータの組み合わせを一のキー情報として、同一であるノードの存否を確認してノードの全順序関係を決定する。

また、第５発明に係る方法は、第４発明において、前記情報処理装置は、前記ログ情報に含まれる前記ノードに対する操作の種類に基づいて、ノード間の移動量を特定する。

また、第６発明に係る方法は、第４又は第５発明において、前記情報処理装置は、同一であるノードの指定を受け付ける。

次に、上記目的を達成するために第７発明に係る装置は、構造化文書に含まれるノードの全順序関係を、ノード間遷移に関するログ情報に基づいて決定して可視化する装置において、構造化文書に含まれるノード間の遷移に関する情報を時系列に記憶した、少なくともノードに対する操作の種類を含むログ情報を取得するログ情報取得部と、取得したログ情報に基づいて、遷移するノード間の相対的位置関係を特定する位置関係特定部と、特定したノード間の相対的位置関係を制約条件としてトポロジカルソートを実行して構造化文書に含まれるノードの全順序関係を決定する全順序関係決定部とを備え、前記構造化文書に含まれるノードが追加又は削除された場合、ノードのコンテンツに対応するデータに基づいてノードの全順序関係を決定するようにしてある。

また、第８発明に係る装置は、第７発明において、決定したノードの全順序関係を表示する表示部を備える。

また、第９発明に係る装置は、第７又は第８発明において、前記ログ情報は、少なくともノード間の移動量に関する情報を含み、該ノード間の移動量に関する情報に基づいて、前記相対的位置関係を特定するようにしてある。

また、第１０発明に係る装置は、第７乃至第９発明のいずれか１つにおいて、前記構造化文書は木構造を有し、前記ログ情報は、ノードを識別する識別情報、ノードに対する前記操作が行われた相対時刻、及びノードのコンテンツに対応するデータを少なくとも含み、前記識別情報及び前記コンテンツに対応するデータの組み合わせを一のキー情報として、同一であるノードの存否を確認してノードの全順序関係を決定するようにしてある。

また、第１１発明に係る装置は、第１０発明において、前記ログ情報に含まれる前記ノードに対する操作の種類に基づいて、ノード間の移動量を特定するようにしてある。

また、第１２発明に係る装置は、第１０又は第１１発明において、同一であるノードの指定を受け付ける指定受付部を備える。

次に、上記目的を達成するために第１３発明に係るコンピュータプログラムは、構造化文書に含まれるノードの全順序関係を、ノード間遷移に関するログ情報に基づいて決定して可視化するコンピュータで実行することが可能なコンピュータプログラムにおいて、前記コンピュータを、構造化文書に含まれるノード間の遷移に関する情報を時系列に記憶した、少なくともノードに対する操作の種類を含むログ情報を取得するログ情報取得手段、取得したログ情報に基づいて、遷移するノード間の相対的位置関係を特定する位置関係特定手段、及び特定したノード間の相対的位置関係を制約条件としてトポロジカルソートを実行して構造化文書に含まれるノードの全順序関係を決定する全順序関係決定手段として機能させ、前記構造化文書に含まれるノードが追加又は削除された場合、前記全順序関係決定手段を、ノードのコンテンツに対応するデータに基づいてノードの全順序関係を決定する手段として機能させる。

また、第１４発明に係るコンピュータプログラムは、第１３発明において、前記コンピュータを、決定したノードの全順序関係を表示する表示手段として機能させる。

また、第１５発明に係るコンピュータプログラムは、第１３又は第１４発明において、前記ログ情報は、少なくともノード間の移動量に関する情報を含み、前記位置関係特定手段を、該ノード間の移動量に関する情報に基づいて、前記相対的位置関係を特定する手段として機能させる。

また、第１６発明に係るコンピュータプログラムは、第１３乃至第１５発明のいずれか１つにおいて、前記構造化文書は木構造を有し、前記ログ情報は、ノードを識別する識別情報、ノードに対する前記操作が行われた相対時刻、及びノードのコンテンツに対応するデータを少なくとも含み、前記全順序関係決定手段を、前記識別情報及び前記コンテンツに対応するデータの組み合わせを一のキー情報として、同一であるノードの存否を確認してノードの全順序関係を決定する手段として機能させる。

また、第１７発明に係るコンピュータプログラムは、第１６発明において、前記位置関係特定手段を、前記ログ情報に含まれる前記ノードに対する操作の種類に基づいて、ノード間の移動量を特定する手段として機能させる。

また、第１８発明に係るコンピュータプログラムは、第１６又は第１７発明において、前記コンピュータを、同一であるノードの指定を受け付ける指定受付手段として機能させる。

本発明によれば、構造化文書に含まれるノードの全順序関係を、ユーザの操作に関するログ情報に基づいて決定することができ、動的に構造化文書の構造が変化した場合であっても、ノードのコンテンツに対応するデータの一致／不一致を確認することでノード間の絶対的位置関係を一義的に推定して、ユーザの操作時の挙動を画面上に表示することが可能となる。

本発明の実施の形態に係る情報処理装置の構成を模式的に示すブロック図である。 本発明の実施の形態に係る情報処理装置の機能ブロック図である。 本発明の実施の形態に係る情報処理装置の相対的位置関係を特定する例示図である。 本発明の実施の形態に係る情報処理装置の全順序関係を決定する例示図である。 本発明の実施の形態に係る情報処理装置の決定した全順序関係をグラフィカルに表示した例示図である。 本発明の実施の形態に係る情報処理装置のＣＰＵの処理手順を示すフローチャートである。 構造化文書が木構造を有する場合のノードのパス情報の例示図である。 ノードのテキストデータのみが変化した場合であって、ループ状態が生じないときの例示図である。 ノードのパス情報のみが変化した場合であって、ループ状態が生じないときの例示図である。 ループ状態が生じる場合の例示図である。

以下、本発明の実施の形態に係る、構造化文書に含まれるノードの全順序関係を、ログ情報に基づいて決定して可視化する装置について、図面に基づいて具体的に説明する。以下の実施の形態は、特許請求の範囲に記載された発明を限定するものではなく、実施の形態の中で説明されている特徴的事項の組み合わせの全てが解決手段の必須事項であるとは限らないことは言うまでもない。

また、本発明は多くの異なる態様にて実施することが可能であり、実施の形態の記載内容に限定して解釈されるべきものではない。実施の形態を通じて同じ要素には同一の符号を付している。

以下の実施の形態では、コンピュータシステムにコンピュータプログラムを導入した装置について説明するが、当業者であれば明らかな通り、本発明はその一部をコンピュータで実行することが可能なコンピュータプログラムとして実施することができる。したがって、本発明は、構造化文書に含まれるノードの全順序関係を、ログ情報に基づいて決定して可視化する装置というハードウェアとしての実施の形態、ソフトウェアとしての実施の形態、又はソフトウェアとハードウェアとの組み合わせの実施の形態をとることができる。コンピュータプログラムは、ハードディスク、ＤＶＤ、ＣＤ、光記憶装置、磁気記憶装置等の任意のコンピュータで読み取ることが可能な記録媒体に記録することができる。

本発明の実施の形態によれば、構造化文書に含まれるノードの全順序関係を、ユーザの操作に関するログ情報に基づいて決定することができ、動的に構造化文書の構造が変化した場合であっても、ノードのコンテンツに対応するデータの一致／不一致を確認することでノード間の絶対的位置関係を一義的に推定して、ユーザの操作時の挙動を画面上に表示することが可能となる。

図１は、本発明の実施の形態に係る情報処理装置の構成を模式的に示すブロック図である。本発明の実施の形態に係る情報処理装置１は、少なくともＣＰＵ（中央演算装置）１１、メモリ１２、記憶装置１３、Ｉ／Ｏインタフェース１４、ビデオインタフェース１５、可搬型ディスクドライブ１６、通信インタフェース１７及び上述したハードウェアを接続する内部バス１８で構成されている。

ＣＰＵ１１は、内部バス１８を介して情報処理装置１の上述したようなハードウェア各部と接続されており、上述したハードウェア各部の動作を制御するとともに、記憶装置１３に記憶されたコンピュータプログラム１００に従って、種々のソフトウェア的機能を実行する。メモリ１２は、ＳＲＡＭ、ＳＤＲＡＭ等の揮発性メモリで構成され、コンピュータプログラム１００の実行時にロードモジュールが展開され、コンピュータプログラム１００の実行時に発生する一時的なデータ等を記憶する。

記憶装置１３は、内蔵される固定型記憶装置（ハードディスク）、ＲＯＭ等で構成されている。記憶装置１３に記憶されたコンピュータプログラム１００は、プログラム及びデータ等の情報を記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体９０から、可搬型ディスクドライブ１６によりダウンロードされ、実行時には記憶装置１３からメモリ１２へ展開して実行される。もちろん、通信インタフェース１７を介して接続されている外部コンピュータからダウンロードされたコンピュータプログラムであっても良い。

通信インタフェース１７は内部バス１８に接続されており、インターネット、ＬＡＮ、ＷＡＮ等の外部のネットワークに接続されることにより、外部コンピュータ等とデータ送受信を行うことが可能となっている。

Ｉ／Ｏインタフェース１４は、キーボード２１、マウス２２と接続され、データの入力を受け付ける。また、ビデオインタフェース１５は、表示装置２３と接続され、所定の画像を表示する。ユーザの、表示装置２３に表示されている画像に対する操作ログが、ログ情報として記憶される。

図２は、本発明の実施の形態に係る情報処理装置１の機能ブロック図である。図２において、情報処理装置１のログ情報取得部２０１は、構造化文書に含まれるノード間の遷移に関する情報を時系列に記憶したログ情報を取得する。

ログ情報は、構造化文書の行（エントリ）の集まりとして記憶される。ログ情報のフォーマットは（式１）で表すことができる。

ｅｎｔｒｙ：：＝（ｔｉｍｅ，ｏｐ，ｎｏｄｅＩＤ，ｔｅｘｔ）・・・（式１）

（式１）において、「ｔｉｍｅ」は、ログ情報の取得対象となるページの閲覧を開始した時点からの、操作が行われた相対時刻を表している。「ｏｐ」は、ユーザが行った操作の種類を表している。「ｎｏｄｅＩＤ」は、「ｏｐ」の操作により到達したノードを識別するノードＩＤを表している。したがって、「ｏｐ」の操作を行う前の「ｎｏｄｅＩＤ」は、「ｏｐ」の操作の種類に基づいて容易に特定することができる。すなわち、操作の種類に基づいてノード間の移動量を特定することができるので、特定した移動量に基づいて逆算すれば良い。

構造化文書は、ノード列として表すことができる。各ノードは、ノードのコンテンツに対応するデータ、例えば合成音声等で読み上げることが可能なテキストデータを有している。ノードのコンテンツに対応するデータとしては、テキストデータ、画像データ等、コンテンツを特定することが可能なデータであれば特に限定されるものではない。ノードの種類としては、テキストデータ自体であるテキストノード、ヘッダ、フッタ等を示すヘディングノード、リンク先を示すリンクノード、テキストボックス、ボタン等を示すフォームコントロールノード等がある。なお、画像ノードのような非テキストノードであっても、コンテンツの作成者が代替テキストデータを付与することにより、テキストデータを有することができる。

ユーザが行う操作の種類としては、例えばページ先頭への移動、ページ末尾への移動、次のノードへの移動、前のノードへの移動、１０ノード先への移動、１０ノード前への移動、次のリンクへの移動、前のリンクへの移動、次のヘディングノードへの移動、前のヘディングノードへの移動、ページ内リンクによるジャンプ等、ウェブページ内にて移動する任意の操作がある。単純なノード間の移動操作においては、操作の種類に基づいて、ノード間の移動量を容易に特定することができる。

ノードＩＤには、ノードのアドレス、ノードのパス、ノードのコンテンツに対応するデータ、又はこれらの組み合わせを用いる。もちろん、動的にノードが追加又は削除される場合には、ノードＩＤも動的に変化する。

そして、「ｔｅｘｔ」は、ノードのコンテンツに対応するデータとして、ノードのテキストデータを表している。本発明の実施の形態では、ログ情報にノードのテキストデータを含み、ノードＩＤとテキストデータとを組み合わせて一のキー情報として、同一であるノードを検索する。これにより、ノード間の相対的な位置関係だけからは決定することができないノードの全順序関係を、ノードＩＤとテキストデータとを組み合わせて同一のノードであるか否かを判断することにより特定することができる。例えばノードＩＤが一致しているものの、同一ではないノードをテキストデータの相違で区別する。

位置関係特定部２０２は、取得したログ情報に基づいて、遷移するノード間の相対的位置関係を特定する。例えばログ情報には、ユーザが行う操作の種類、及び到達したノードを識別するノードＩＤが含まれているので、操作の種類に基づくノード間の移動量に基づいて、ノード間の相対的位置関係を特定することができる。

図３は、本発明の実施の形態に係る情報処理装置１の相対的位置関係を特定する例示図である。図３（ａ）に示すようにノードＡからノードＢ（１）、Ｂ（２）に遷移し、ノードＢ（２）からはノードＣ（１）及びノードＣ（２）の２つのノードへ遷移する。

例えば、ノードＢ（２）からノードＣ（１）へ操作「次のノードへの移動」により遷移し、ノードＢ（２）からノードＣ（２）へは操作「１０ノード先への移動」により遷移したものとすると、Ｂ（２）＜Ｃ（１）、Ｂ（２）＜Ｃ（２）の２つの相対的位置関係を特定することができる。

ここで、図３（ｂ）に示すように、ノードＢ（１）と旧ノードＢ（２）との間に、新ノードＢ（２）を追加した場合、旧ノードＢ（２）は新ノードＢ（３）に変更される。この後、例えば新ノードＢ（２）からノードＣ（１）へ操作「次のノードへの移動」により遷移し、新ノードＢ（２）からノードＣ（２）へは操作「１０ノード先への移動」により遷移した場合、Ｂ（２）＜Ｃ（１）、Ｂ（２）＜Ｃ（２）の２つの相対的位置関係が特定される。しかし、ノードＢ（２）が旧ノードＢ（２）であるのか、追加された新ノードＢ（２）であるのか、区別することができず、ノードの全順序関係を決定することができない。

そこで、全順序関係決定部２０３は、特定したノード間の相対的位置関係を制約条件としてトポロジカルソートを実行して構造化文書に含まれるノードの全順序関係を決定する。構造化文書に含まれるノードが追加又は削除された場合、ノードＩＤに対応付けられたテキストデータに基づいて、ノードの全順序関係を決定する。

図４は、本発明の実施の形態に係る情報処理装置１の全順序関係を決定する例示図である。図３と同じく、ノードＢ（１）と旧ノードＢ（２）との間に、新ノードＢ（２）を追加した場合、旧ノードＢ（２）は新ノードＢ（３）に変更される。この後、例えば新ノードＢ（２）からノードＣ（１）へ操作「次のノードへの移動」により遷移し、新ノードＢ（２）からノードＣ（２）へは操作「１０ノード先への移動」により遷移した場合、Ｂ（２）＜Ｃ（１）、Ｂ（２）＜Ｃ（２）の２つの相対的位置関係が特定される。

このままでは、ノードＢ（２）が旧ノードＢ（２）であるのか、追加された新ノードＢ（２）であるのか、区別することができない。そこで、付与されているテキストデータの違いによってノードＢ（２）がいずれのノードであるかを特定する。まず、旧ノードＢ（２）又は新ノードＢ（３）は、テキストデータＴ１が付与されている。ノードＢ（２）が旧ノードＢ（２）である場合、旧ノードＢ（２）はテキストデータＴ１が付与されているので、相対的位置関係は（Ｂ（２）、Ｔ１）＜Ｃ（１）、（Ｂ（２）、Ｔ１）＜Ｃ（２）となる。しかし、新ノードＢ（２）は、異なるテキストデータが付与されているので、ノードＢ（２）が新ノードＢ（２）である場合には、相対的位置関係はＢ（２）＜Ｃ（１）、Ｂ（２）＜Ｃ（２）となる。本来、旧ノードＢ（２）に付与されているのはテキストデータＴ１であるので、テキストデータＴ１が付与されていないノードを削除することによりノードＢ（２）がいずれのノードであるか特定することができる。つまり、両方の相対的位置関係を比較することにより、ノードＢ（２）が旧ノードＢ（２）であると特定することができる。したがって、ノードの絶対的位置関係を一義的に推定することができ、ログ情報が十分に収集された場合、ノードの全順序関係を決定することができる。

ノードＩＤが異なっている場合には、このようにノードのテキストデータが一致しているか否かで同一のノードであるか否かを判断することができるが、相対的位置関係を特定する前に、ノードＩＤとテキストデータとの組み合わせを一のキー情報として、ノードＩＤが一致している、あるいはノードＩＤは異なるがテキストデータが一致しているノードを同一のノードとして抽出しておいても良い。これにより、事前に同一のノードの存否を確認しておくことができ、ノードの追加又は削除によりノードＩＤが変更された場合であっても異なるノードであると誤認することを未然に防止することができる。もちろん、指定受付部２０４を備えておき、事前に同一であるノードの指定を受け付けておいても良い。

表示部２０５は、全順序関係決定部２０３にて決定したノードの全順序関係を、グラフィカルに表示する。図５は、本発明の実施の形態に係る情報処理装置１の決定した全順序関係をグラフィカルに表示した例示図である。

図５は、縦軸に経過時間を、横軸にウェブページ内でのユーザが指示するカーソルの位置に対応するノードの位置を示しており、ユーザがどのような振る舞いで操作したかをグラフィカルに示している。図５の例では、左上を原点として、次第に画面右側のノードへと遷移し（これを順方向とする）、画面中央近傍で推移した後、一気に逆方向へジャンプしている。そして、画面左端近傍で推移した後、今度は一気に順方向へジャンプし、所望の位置を通り過ぎたと判断して逆方向へ遷移を開始し、その後戻りすぎたと判断して順方向へ遷移を開始している。このように、ノードの絶対的位置関係を一義的に推定することができ、ログ情報が十分に収集された場合、ノードの全順序関係が決定することにより、実際のユーザ操作の挙動を正しく表示することが可能となる。

図６は、本発明の実施の形態に係る情報処理装置１のＣＰＵ１１の処理手順を示すフローチャートである。図６の例では、構造化文書が木構造を有しており、木構造におけるノードのパス情報がノードＩＤとして付与されている場合について説明する。

図６において、情報処理装置１のＣＰＵ１１は、ログ情報を取得する（ステップＳ６０１）。取得するログ情報は、例えばノードを識別する識別情報であるノードＩＤ、ノードに対する操作の種類、操作が行われた相対時刻、及びノードのテキストデータを少なくとも含んでいる。

図７は、構造化文書が木構造を有する場合のノードのパス情報の例示図である。図７の例では、ルートノード「ｂｏｄｙ」から下位階層のノード「ｄｉｖ（１）」、「ｄｉｖ（２）」の２つのノードに分岐し、ノード「ｄｉｖ（２）」は、さらに下位階層のノード「ａ（１）」、「ａ（２）」の２つのノードに分岐している。ノード「ａ（２）」にはテキストデータ「ｔｅｘｔ」が付与されている。

この場合、ノード「ａ（２）」を示すパス情報は、いわゆるＸＰａｔｈ的な表現を用いて、（式２）のように表すことができる。

ＸＰａｔｈ＝／ｂｏｄｙ／ｄｉｖ（２）／ａ（２） ＜ｔｅｘｔ＞ ・・・（式２）

従来は、（式２）の右辺のうち、テキストデータを除いた部分をノードＩＤとすることにより、ノードが追加又は削除され、木構造が変動しない限り、木構造中のどのノードであるのかパスをたどることができた。しかし、ノードが追加又は削除され、木構造が変動する場合には、パスをたどることができない。

そこで、本実施の形態では、テキストデータを含めてノードＩＤとする。これにより、ノードが追加又は削除され、木構造が変動した場合であっても、テキストデータの一致／不一致を確認することにより、パス情報がノードの追加又は削除により変動した場合であっても、同一のノードであるか否かを容易に判断することができる。

図６に戻って、情報処理装置１のＣＰＵ１１は、取得したログ情報から、一のログ情報を選択し（ステップＳ６０２）、ログ情報に含まれるノードに対する操作の種類に基づいて、移動前のノードとの半順序制約を生成する（ステップＳ６０３）。ここで、半順序制約とは、ノードに対する操作の種類に基づいて特定される、ノードの相対的位置関係を意味する。

例えばノードｎ１、ｎ２に対して、ノードｎ１からノードｎ２へ順方向に移動する場合には、ｎ１＜ｎ２という相対的位置関係であることが特定される。同様にノードｎ２からノードｎ１へ順方向に移動する場合には、ｎ１＞ｎ２という相対的位置関係であることが特定される。特定された相対的位置関係を制約条件としてトポロジカルソートを実行してノードの全順序関係を決定することができる。

ＣＰＵ１１は、次のログ情報を選択する（ステップＳ６０４）、ログ情報に含まれるノードに対する操作の種類に基づいて、移動前のノードとの半順序制約を生成する（ステップＳ６０５）。ＣＰＵ１１は、全てのログ情報を選択したか否かを判断し（ステップＳ６０６）、ＣＰＵ１１が、まだ選択していないログ情報が存在すると判断した場合（ステップＳ６０６：ＮＯ）、ＣＰＵ１１は、処理をステップＳ６０４へ戻し、上述した処理を繰り返す。

ＣＰＵ１１が、全てのログ情報を選択したと判断した場合（ステップＳ６０６：ＹＥＳ）、ＣＰＵ１１は、生成した半順序制約を全て満たす全順序関係を決定するためにトポロジカルソートを実行する（ステップＳ６０７）。

ＣＰＵ１１は、トポロジカルソートの実行により、全順序関係が決定されたか否かを判断する（ステップＳ６０８）。ＣＰＵ１１が、全順序関係が決定されていないと判断した場合（ステップＳ６０８：ＮＯ）、ＣＰＵ１１は、半順序制約を一部削除し（ステップＳ６０９）、トポロジカルソートを再実行する（ステップＳ６１０）。従来のトポロジカルソートとは相違し、ノードＩＤにノードのテキストデータが含まれているので、木構造が変動した場合であっても、テキストデータの一致／不一致を確認することにより、パス情報がノードの追加又は削除により変動した場合であっても、同一のノードであるか否かを容易に判断することができる。具体的には、同一のノードについては、いずれかのノードＩＤに統一して、トポロジカルソートを再実行する。

ＣＰＵ１１は、トポロジカルソートの再実行により、全順序関係が決定されたか否かを判断する（ステップＳ６１１）。ＣＰＵ１１が、全順序関係が決定されていないと判断した場合（ステップＳ６１１：ＮＯ）、ＣＰＵ１１は、処理をステップＳ６０９へ戻して上述した処理を繰り返す。

ＣＰＵ１１が、全順序関係が決定されたと判断した場合（ステップＳ６０８：ＹＥＳ、ステップＳ６１１：ＹＥＳ）、ＣＰＵ１１は、処理を終了し、決定された全順序関係に基づいて、ノード遷移の絶対的位置関係を時系列に表示装置２３に表示する。具体的には図５に例示したような、ユーザ操作の振る舞い図として表示される。

なお、半順序制約によっては、ノード間の順序関係にループ状態が生じている可能性もある。ステップＳ６１１にて全順序関係が決定されていないと判断された場合の多くが、これに相当する。原因は、ノードのパス情報又はテキストデータが変化することにより、誤った半順序制約が生成されたからである。

図８は、ノードのテキストデータのみが変化した場合であって、ループ状態が生じないときの例示図である。図８では順序関係を矢印で示している。図８（ａ）に示すように、初期状態では、ノードの正しい順序はｎ１＜ｎ２＜ｎ３とする。ノードｎ１、ｎ２、ｎ３のパス情報は、それぞれｐ１、ｐ２、ｐ３とし、テキストデータは、それぞれｔｅｘｔ１、ｔｅｘｔ２、ｔｅｘｔ３とする。

ノードｎ１からノードｎ２、ノードｎ３と順に移動した時点で、ノードｎ２のテキストデータがｔｅｘｔ２’に変化し、その後ノードｎ３からノードｎ２、ノードｎ１と順に移動した場合、生成される半順序制約は、（式３）のようになる。なお、（式３）において、ノードは、（パス情報、テキストデータ）の組み合わせとして表しており、（ｐ２、ｔｅｘｔ２）と（ｐ２、ｔｅｘｔ２’）とは別のノードとして扱う。

（ｐ１、ｔｅｘｔ１）＜（ｐ２、ｔｅｘｔ２）
（ｐ２、ｔｅｘｔ２）＜（ｐ３、ｔｅｘｔ３）
（ｐ２、ｔｅｘｔ２’）＜（ｐ３、ｔｅｘｔ３）
（ｐ１、ｔｅｘｔ１）＜（ｐ２、ｔｅｘｔ２’） ・・・（式３）

（式３）に示す半順序制約を解くことにより、図８（ｂ）に示すような順序関係が生じる。すなわち、（式４）のように表すことができる。ただし、（式４）において記号「：」は、隣接する２つのノードの順序が確定していないことを意味している。

（ｐ１、ｔｅｘｔ１）＜（ｐ２、ｔｅｘｔ２）：（ｐ２、ｔｅｘｔ２’）
＜（ｐ３、ｔｅｘｔ３） ・・・（式４）

ノードのテキストデータのみが変化した場合、例えばノード（ｐ２、ｔｅｘｔ２）とノード（ｐ２、ｔｅｘｔ２’）とは、元来同一のノードである。したがって、順序関係が確定していなくても問題が生じることがない。

図９は、ノードのパス情報のみが変化した場合であって、ループ状態が生じないときの例示図である。図９でも順序関係を矢印で示している。図９（ａ）に示すように、初期状態では、ノードの正しい順序はｎ１＜ｎ２＜ｎ３とする。ノードｎ１、ｎ２、ｎ３のパス情報は、それぞれｐ１、ｐ２、ｐ３とし、テキストデータは、それぞれｔｅｘｔ１、ｔｅｘｔ２、ｔｅｘｔ３とする。

ノードｎ１からノードｎ２、ノードｎ３と順に移動した時点で、図９（ｂ）に示すようにノードｎ１とノードｎ２との間にテキストデータがｔｅｘｔ４であるノードｎ４が追加され、ノードｎ４のパス情報がｐ２、ノードｎ２のパス情報がｐ３、ノードｎ３のパス情報がｐ３’に変化したものとする。その後ノードｎ３からノードｎ２、ノードｎ４、ノードｎ１と順に移動した場合、生成される半順序制約は、（式５）のようになる。なお、（式５）においても、ノードは、（パス情報、テキストデータ）の組み合わせとして表しており、（ｐ３、ｔｅｘｔ２）と（ｐ３、ｔｅｘｔ３）とは別のノードとして扱う。

（ｐ１、ｔｅｘｔ１）＜（ｐ２、ｔｅｘｔ２）
（ｐ２、ｔｅｘｔ２）＜（ｐ３、ｔｅｘｔ３）
（ｐ３、ｔｅｘｔ２）＜（ｐ３’、ｔｅｘｔ３）
（ｐ２、ｔｅｘｔ４）＜（ｐ３、ｔｅｘｔ２）
（ｐ１、ｔｅｘｔ１）＜（ｐ２、ｔｅｘｔ４） ・・・（式５）

（式５）に示す半順序制約を解くことにより、図９（ｃ）に示すような順序関係が生じる。図９（ｃ）において、ノードｎ２とｎ２’とは、本来は同一のノードであることから、順序関係が確定していなくても問題が生じることがない。

図１０は、ループ状態が生じる場合の例示図である。図１０（ａ）に示すように、初期状態では、ノードの正しい順序はｎ１＜ｎ２＜ｎ３＜ｎ４とする。ノードｎ１、ｎ２、ｎ３、ｎ４のパス情報は、それぞれｐ１、ｐ２、ｐ３、ｐ４とし、テキストデータは、それぞれｔｅｘｔ１、ｔｅｘｔ２、ｔｅｘｔ１、ｔｅｘｔ４とする。つまり、ノードｎ１のテキストデータとノードｎ３のテキストデータが同一である。

ノードｎ１からノードｎ２、ノードｎ３、ノードｎ４と順に移動した時点で、図１０（ｂ）に示すようにノードｎ１が削除され、ノードｎ３のパス情報がｐ１に変化したものとする。その後ノードｎ４からノードｎ３、ノードｎ２と順に移動した場合、生成される半順序制約は、（式６）のようになる。なお、（式６）においても、ノードは、（パス情報、テキストデータ）の組み合わせとして表している。

（ｐ１、ｔｅｘｔ１）＜（ｐ２、ｔｅｘｔ２）
（ｐ２、ｔｅｘｔ２）＜（ｐ３、ｔｅｘｔ１）
（ｐ３、ｔｅｘｔ１）＜（ｐ４、ｔｅｘｔ４）
（ｐ４、ｔｅｘｔ４）＞（ｐ１、ｔｅｘｔ１）
（ｐ２、ｔｅｘｔ２）＜（ｐ１、ｔｅｘｔ１） ・・・（式６）

（式６）に示す半順序制約集合には、図１０（ｃ）に示すように、ノード（ｐ１、ｔｅｘｔ１）とノード（ｐ２、ｔｅｘｔ２）との間にループ状態が生じている。この場合、以下の手順で削除するべき半順序制約を、ループを構成する半順序制約の中から選択する。

まず時刻的に一番最後に追加された半順序制約を削除する。図１０（ｃ）では矢印１０１の半順序制約（ｐ２、ｔｅｘｔ２）＜（ｐ１、ｔｅｘｔ１）を削除することにより、ループ状態が解消する。

また、時刻的に一番最初に追加された半順序制約を削除しても良い。図１０（ｃ）では矢印１０２の半順序制約（ｐ１、ｔｅｘｔ１）＜（ｐ２、ｔｅｘｔ２）を削除した場合であっても、ループ状態が解消する。

もちろん、所定の時刻から一番経過した時刻の長い半順序制約を削除しても良い。これにより、所定の時刻においてループ状態が生じていない場合には、所定の時刻における半順序制約の集合へと近づけることができる。

いずれも、ループ状態が解消するまで、順次、上述した手順で半順序制約を削除し、ループ状態が解消した時点で、全順序関係を決定すれば良い。

以上のように本実施の形態によれば、構造化文書に含まれるノードの全順序関係を、ユーザの操作に関するログ情報に基づいて決定することができ、動的に構造化文書の構造が変化した場合であっても、ノードのコンテンツに対応するテキストデータの一致／不一致を確認することでノード間の絶対的位置関係を一義的に推定して、ユーザ操作時の挙動を画面上に表示することが可能となる。

なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨の範囲内であれば多種の変更、改良等が可能である。

１ 情報処理装置
１１ ＣＰＵ
１２ メモリ
１３ 記憶装置
１４ Ｉ／Ｏインタフェース
１５ ビデオインタフェース
１６ 可搬型ディスクドライブ
１７ 通信インタフェース
１８ 内部バス
２３ 表示装置
９０ 可搬型記録媒体
１００ コンピュータプログラム

Claims (18)

1. 構造化文書に含まれるノードの全順序関係を、ノード間遷移に関するログ情報に基づいて決定して可視化する情報処理装置で実行することが可能な方法において、
   前記情報処理装置は、
   構造化文書に含まれるノード間の遷移に関する情報を時系列に記憶した、少なくともノードに対する操作の種類を含むログ情報を取得する工程と、
   取得したログ情報に基づいて、遷移するノード間の相対的位置関係を特定する工程と、
   特定したノード間の相対的位置関係を制約条件としてトポロジカルソートを実行して構造化文書に含まれるノードの全順序関係を決定する工程と
   を含み、
   前記構造化文書に含まれるノードが追加又は削除された場合、ノードのコンテンツに対応するデータに基づいてノードの全順序関係を決定する方法。
2. 前記情報処理装置は、
   決定したノードの全順序関係を表示する工程を含む請求項１記載の方法。
3. 前記ログ情報は、少なくともノード間の移動量に関する情報を含み、
   前記情報処理装置は、該ノード間の移動量に関する情報に基づいて、前記相対的位置関係を特定する請求項１又は２記載の方法。
4. 前記構造化文書は木構造を有し、
   前記ログ情報は、ノードを識別する識別情報、ノードに対する前記操作が行われた相対時刻、及びノードのコンテンツに対応するデータを少なくとも含み、
   前記情報処理装置は、前記識別情報及び前記コンテンツに対応するデータの組み合わせを一のキー情報として、同一であるノードの存否を確認してノードの全順序関係を決定する請求項１乃至３のいずれか一項に記載の方法。
5. 前記情報処理装置は、前記ログ情報に含まれる前記ノードに対する操作の種類に基づいて、ノード間の移動量を特定する請求項４記載の方法。
6. 前記情報処理装置は、同一であるノードの指定を受け付ける請求項４又は５記載の方法。
7. 構造化文書に含まれるノードの全順序関係を、ノード間遷移に関するログ情報に基づいて決定して可視化する装置において、
   構造化文書に含まれるノード間の遷移に関する情報を時系列に記憶した、少なくともノードに対する操作の種類を含むログ情報を取得するログ情報取得部と、
   取得したログ情報に基づいて、遷移するノード間の相対的位置関係を特定する位置関係特定部と、
   特定したノード間の相対的位置関係を制約条件としてトポロジカルソートを実行して構造化文書に含まれるノードの全順序関係を決定する全順序関係決定部と
   を備え、
   前記構造化文書に含まれるノードが追加又は削除された場合、ノードのコンテンツに対応するデータに基づいてノードの全順序関係を決定するようにしてある装置。
8. 決定したノードの全順序関係を表示する表示部を備える請求項７記載の装置。
9. 前記ログ情報は、少なくともノード間の移動量に関する情報を含み、
   該ノード間の移動量に関する情報に基づいて、前記相対的位置関係を特定するようにしてある請求項７又は８記載の装置。
10. 前記構造化文書は木構造を有し、
    前記ログ情報は、ノードを識別する識別情報、ノードに対する前記操作が行われた相対時刻、及びノードのコンテンツに対応するデータを少なくとも含み、
    前記識別情報及び前記コンテンツに対応するデータの組み合わせを一のキー情報として、同一であるノードの存否を確認してノードの全順序関係を決定するようにしてある請求項７乃至９のいずれか一項に記載の装置。
11. 前記ログ情報に含まれる前記ノードに対する操作の種類に基づいて、ノード間の移動量を特定するようにしてある請求項１０記載の装置。
12. 同一であるノードの指定を受け付ける指定受付部を備える請求項１０又は１１記載の装置。
13. 構造化文書に含まれるノードの全順序関係を、ノード間遷移に関するログ情報に基づいて決定して可視化するコンピュータで実行することが可能なコンピュータプログラムにおいて、
    前記コンピュータを、
    構造化文書に含まれるノード間の遷移に関する情報を時系列に記憶した、少なくともノードに対する操作の種類を含むログ情報を取得するログ情報取得手段、
    取得したログ情報に基づいて、遷移するノード間の相対的位置関係を特定する位置関係特定手段、及び
    特定したノード間の相対的位置関係を制約条件としてトポロジカルソートを実行して構造化文書に含まれるノードの全順序関係を決定する全順序関係決定手段
    として機能させ、
    前記構造化文書に含まれるノードが追加又は削除された場合、前記全順序関係決定手段を、ノードのコンテンツに対応するデータに基づいてノードの全順序関係を決定する手段として機能させるコンピュータプログラム。
14. 前記コンピュータを、決定したノードの全順序関係を表示する表示手段として機能させる請求項１３記載のコンピュータプログラム。
15. 前記ログ情報は、少なくともノード間の移動量に関する情報を含み、
    前記位置関係特定手段を、該ノード間の移動量に関する情報に基づいて、前記相対的位置関係を特定する手段として機能させる請求項１３又は１４記載のコンピュータプログラム。
16. 前記構造化文書は木構造を有し、
    前記ログ情報は、ノードを識別する識別情報、ノードに対する前記操作が行われた相対時刻、及びノードのコンテンツに対応するデータを少なくとも含み、
    前記全順序関係決定手段を、前記識別情報及び前記コンテンツに対応するデータの組み合わせを一のキー情報として、同一であるノードの存否を確認してノードの全順序関係を決定する手段として機能させる請求項１３乃至１５のいずれか一項に記載のコンピュータプログラム。
17. 前記位置関係特定手段を、前記ログ情報に含まれる前記ノードに対する操作の種類に基づいて、ノード間の移動量を特定する手段として機能させる請求項１６記載のコンピュータプログラム。
18. 前記コンピュータを、同一であるノードの指定を受け付ける指定受付手段として機能させる請求項１６又は１７記載のコンピュータプログラム。