(57)【要約】【課題】  項目リストを検出することに関する。【解決手段】  一実施形態では、所与のＷｅｂページに関連するユーザのＷｅｂブラウジング対話履歴が分析される。Ｗｅｂブラウジング対話履歴は、ユーザがＷｅｂページの少なくとも１つの要素と対話したことを示す。所与のＷｅｂページのドキュメント・オブジェクト・モデル（ＤＯＭ）  が構築される。Ｗｅｂページ内の要素に対応するＤＯＭ内のノードは、Ｗｅｂブラウジング対話履歴を分析することに基づいて識別される。その要素を含むＷｅｂページ内の項目リストに対応するノードの先祖ノードは、少なくともその先祖ノードの子タグの分布に基づいて識別される。【選択図】  図７
2014527235.tif 000002
【特許請求の範囲】
【請求項１】
項目リストの自動検出のための方法であって、
所与のＷｅｂページに関連するユーザのＷｅｂブラウジング対話履歴を分析することであって、前記Ｗｅｂブラウジング対話履歴が、前記ユーザが前記Ｗｅｂページの少なくとも１つの要素と対話したことを示すことと、
前記所与のＷｅｂページのドキュメント・オブジェクト・モデル（ＤＯＭ）を構築することと、
前記分析に基づいて、前記Ｗｅｂページに関連する前記要素に対応する前記ＤＯＭ内のノードを識別することと、
前記要素を含む前記Ｗｅｂページに関連する項目リストに対応する前記ノードの先祖ノードを、少なくとも前記先祖ノードの子タグの分布に基づいて識別することと
を含む、方法。
【請求項２】
前記ノードが、
前記Ｗｅｂブラウジング対話履歴に関連するポインタであって、前記ノードを指すものと、
前記Ｗｅｂブラウジング対話履歴に関連する前記要素のラベル
のうちの１つに基づいて識別される、請求項１記載の方法。
【請求項３】
前記先祖ノードを識別することが、
前記ノードの親ノードを識別することと、
前記親ノードの１組の子ノードに対応する１組の子タグの分布を決定することと、
前記分布に基づいて、一致子タグの数を決定することと、
前記一致子タグの数が所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つであるかどうかを判断することと、
少なくとも前記一致子タグの数が前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つであることに応答して、前記親ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する候補ノードとして識別することと
をさらに含む、請求項１または請求項２記載の方法。
【請求項４】
前記先祖ノードを識別することが、
前記親ノードの先祖ノードが、前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つである一致子タグの数を含み損なっていると判断することと、
前記親ノードを、前記Ｗｅｂページに関連する項目リストに対応する、前記ノードの前記先祖ノードとして識別することと
をさらに含む、請求項３記載の方法。
【請求項５】
少なくとも前記一致子タグの数が前記所与のしきい値未満であることに応答して、前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つである一致子タグの数を少なくとも含む前記親ノードの第１の先祖ノードについて前記ＤＯＭに関連するボトムアップ検索を実行することと、
前記第１の先祖ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する候補ノードとして識別することと
をさらに含む、請求項３または請求項４記載の方法。
【請求項６】
少なくとも前記第１の先祖ノードの第２の先祖ノードが、前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つである一致子タグの数を含み損なっていると判断することと、
前記第１の先祖ノードを、前記Ｗｅｂページに関連する項目リストに対応する、前記ノードの前記先祖ノードとして識別することと
をさらに含む、請求項５記載の方法。
【請求項７】
前記親ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する候補ノードとして識別することが、
前記１組の子ノードに関連する類似性測度を決定することと、
前記類似性測度を類似性しきい値と比較することと、
前記類似性測度が類似性しきい値に等しいものおよびそれを超えるもののうちの少なくとも１つであることに応答して、前記親ノードを、前記Ｗｅｂページ内の前記項目リストに対応する前記候補ノードとして識別することと
をさらに含む、請求項３ないし６のいずれか一項に記載の方法。
【請求項８】
前記類似性測度を決定することが、
それぞれの子ノードの構造を前記１組の子ノードに関連する他の子ノードと比較することと、
前記比較に基づいて、一致構造を含む前記１組の子ノードに関連する子ノードの数を決定することであって、前記類似性測度が一致構造を含む子ノードの数であることと
を含む、請求項７記載の方法。
【請求項９】
項目リストの自動検出のためのシステムであって、
所与のＷｅｂページに関連するユーザのＷｅｂブラウジング対話履歴を分析するための手段であって、前記Ｗｅｂブラウジング対話履歴が、前記ユーザが前記Ｗｅｂページの少なくとも１つの要素と対話したことを示すように動作可能である手段と、
前記所与のＷｅｂページのドキュメント・オブジェクト・モデル（ＤＯＭ）を構築するための手段と、
前記分析済みＷｅｂブラウジング対話履歴に基づいて、前記Ｗｅｂページに関連する前記要素に対応する前記ＤＯＭ内のノードを識別するための手段と、
前記要素を含む前記Ｗｅｂページに関連する項目リストに対応するように動作可能な前記ノードの先祖ノードを、少なくとも前記先祖ノードの子タグの分布に基づいて識別するための手段と
を含む、システム。
【請求項１０】
前記ノードが、
前記Ｗｅｂブラウジング対話履歴に関連するポインタであって、前記ノードを指すものと、
前記Ｗｅｂブラウジング対話履歴に関連する前記要素のラベル
のうちの１つに基づいて識別可能である、請求項９記載のシステム。
【請求項１１】
先祖ノードを識別するための前記手段が、
前記ノードの親ノードを識別するための手段と、
前記親ノードの１組の子ノードに対応する１組の子タグの分布を決定するための手段と、
前記分布に基づいて、一致子タグの数を決定するための手段と、
前記一致子タグの数が所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つであるかどうかを判断するための手段と、
少なくとも前記一致子タグの数が前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つであることに応答して、前記親ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する候補ノードとして識別するための手段と
をさらに含む、請求項９または請求項１０記載のシステム。
【請求項１２】
先祖ノードを識別するための前記手段が、
前記親ノードの先祖ノードが、前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つである一致子タグの数を含み損なっていると判断するための手段と、
前記親ノードを、前記Ｗｅｂページに関連する項目リストに対応する、前記ノードの前記先祖ノードとして識別するための手段と
をさらに含む、請求項１１記載のシステム。
【請求項１３】
少なくとも前記一致子タグの数が前記所与のしきい値未満であることに応答して、前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つである一致子タグの数を少なくとも含む前記親ノードの第１の先祖ノードについて前記ＤＯＭ内でボトムアップ検索を実行するための手段と、
前記第１の先祖ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する候補ノードとして識別するための手段と
をさらに含む、請求項１１または請求項１２記載のシステム。
【請求項１４】
少なくとも前記第１の先祖ノードの第２の先祖ノードが、前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つである一致子タグの数を含み損なっていると判断するための手段と、
前記第１の先祖ノードを、前記Ｗｅｂページに関連する項目リストに対応する、前記ノードの前記先祖ノードとして識別するための手段と
をさらに含む、請求項１３記載のシステム。
【請求項１５】
前記親ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する候補ノードとして識別するための前記手段が、
前記１組の子ノードに関連する類似性測度を決定するための手段と、
前記類似性測度を類似性しきい値と比較するための手段と、
前記類似性測度が類似性しきい値に等しいものおよびそれを超えるもののうちの少なくとも１つであることに応答して、前記親ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する前記候補ノードとして識別するための手段と
をさらに含む、請求項１１ないし１４のいずれか一項に記載のシステム。
【請求項１６】
前記類似性測度を決定するための前記手段が、
それぞれの子ノードの構造を前記１組の子ノードに関連する他の子ノードと比較するための手段と、
前記比較に基づいて、一致構造を含む前記１組の子ノードに関連する子ノードの数を決定するための手段であって、前記類似性測度が一致構造を含む子ノードの数である手段と
を含む、請求項１５記載のシステム。
【請求項１７】
コンピュータ・プログラムであって、請求項１ないし８のいずれか一項に記載の方法のすべての前記ステップを実行するようになっているコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、Ｗｅｂページに関し、詳細には、Ｗｅｂページ内の項目リスト（ｉｔｅｍ  ｌｉｓｔ）を自動的に検出することに関する。
【背景技術】
【０００２】
Ｗｅｂページは、典型的に、項目のリスト、たとえば、実行中の検索から得られた検索結果項目や、分類項目（ｔａｘｏｎｏｍｙ  ｉｔｅｍ）のリストを提示する。Ｗｅｂページからの項目リストの自動検出は、Ｗｅｂページの自動処理ならびにいくつかのその他の機能、たとえば、Ｗｅｂページの要約、Ｗｅｂページ・アクセシビリティ・ソリューション、および情報検索を支援する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｉａｎ  Ｌｉｅｔ他による「Ｈｅｒｅ’ｓ  ｗｈａｔ  Ｉ  ｄｉｄ：  ｓｈａｒｉｎｇ  ａｎｄ  ｒｅｕｓｉｎｇ  ｗｅｂ  ａｃｔｉｖｉｔｙ  ｗｉｔｈ  ＡｃｔｉｏｎＳｈｏｔ」（２０１０年のＣＨＩ  ２０１０：コンピューティング・システムにおけるヒューマン・ファクタに関する第２８回国際会議の議事録、７２３〜７３２ページ）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
自動項目リスト検出のための既存の解決策には欠点があり、すなわち、スケーラブルではなく、手動訓練を必要とし、常に有効であるわけではないヒューリスティックスを使用し、ドメイン固有の知識に依存し、正しい項目リストを明確に検出することができない。
【課題を解決するための手段】
【０００５】
一実施形態では、方法が開示される。この方法は、所与のＷｅｂページに関連するユーザのＷｅｂブラウジング対話履歴（ｗｅｂ  ｂｒｏｗｓｉｎｇ  ｉｎｔｅｒａｃｔｉｏｎ  ｈｉｓｔｏｒｙ）を分析することを含む。Ｗｅｂブラウジング対話履歴は、ユーザがＷｅｂページの少なくとも１つの要素と対話したことを示す。所与のＷｅｂページのドキュメント・オブジェクト・モデル（ＤＯＭ）  が構築される。Ｗｅｂページ内の要素に対応するＤＯＭ内のノードは、Ｗｅｂブラウジング対話履歴を分析することに基づいて識別される。その要素を含むＷｅｂページ内の項目リストに対応するノードの先祖ノード（ａｎｃｅｓｔｏｒ  ｎｏｄｅ）は、少なくともその先祖ノードの子タグ（ｃｈｉｌｄ  ｔａｇ）の分布に基づいて識別される。
【０００６】
他の実施形態では、システムが開示される。このシステムは、メモリと、メモリに通信可能に結合されたプロセッサとを含む。項目リスト検出器（ｉｔｅｍ  ｌｉｓｔ  ｄｅｔｅｃｔｏｒ）はメモリおよびプロセッサに通信可能に結合される。項目リスト検出器は、所与のＷｅｂページに関連するユーザのＷｅｂブラウジング対話履歴を分析するように構成される。Ｗｅｂブラウジング対話履歴は、ユーザがＷｅｂページの少なくとも１つの要素と対話したことを示す。所与のＷｅｂページのドキュメント・オブジェクト・モデル（ＤＯＭ）が構築される。Ｗｅｂページ内の要素に対応するＤＯＭ内のノードは、Ｗｅｂブラウジング対話履歴を分析することに基づいて識別される。その要素を含むＷｅｂページ内の項目リストに対応するノードの先祖ノードは、少なくともその先祖ノードの子タグの分布に基づいて識別される。
【０００７】
さらに他の実施形態では、それによりコンピュータ可読プログラム・コードが実施されているコンピュータ可読記憶媒体を含むコンピュータ・プログラム製品（ｃｏｍｐｕｔｅｒ  ｐｒｏｇｒａｍ  ｐｒｏｄｕｃｔ）が開示される。このコンピュータ可読プログラム・コードは、所与のＷｅｂページに関連するユーザのＷｅｂブラウジング対話履歴を分析するように構成されたコンピュータ可読プログラム・コードを含む。Ｗｅｂブラウジング対話履歴は、ユーザがＷｅｂページの少なくとも１つの要素と対話したことを示す。所与のＷｅｂページのドキュメント・オブジェクト・モデル（ＤＯＭ）が構築される。Ｗｅｂページ内の要素に対応するＤＯＭ内のノードは、Ｗｅｂブラウジング対話履歴を分析することに基づいて識別される。その要素を含むＷｅｂページ内の項目リストに対応するノードの先祖ノードは、少なくともその先祖ノードの子タグの分布に基づいて識別される。
【０００８】
同様の参照番号が個別の図面全体を通して同一または機能的に同様の要素を指しており、以下の詳細な説明とともに本明細書に組み込まれ、本明細書の一部を形成する添付図面は、様々な実施形態をさらに例示し、すべて本発明による様々な原理および利点を説明する働きをする。
【図面の簡単な説明】
【０００９】
【図１】本発明の一実施形態による動作環境の一例を示すブロック図である。
【図２】本発明の一実施形態によるブラウザ対話情報の一例を示す図である。
【図３】本発明の一実施形態によりユーザがＷｅｂページの要素と対話したことに応答してユーザに対して表示される検索結果の一例を示す図である。
【図４】本発明の一実施形態によりユーザが対話したリスト内の項目に対応する識別済みノードを強調表示するドキュメント・オブジェクト・モデル（ＤＯＭ）の一例を示す図である。
【図５】本発明の一実施形態により識別済みノードの親ノードが強調表示されている図４のＤＯＭを示す図である。
【図６】本発明の一実施形態により、識別済みノードの先祖ノードがＤＯＭに関連するＷｅｂページの項目リストに対応するノードとして識別されている図４のＤＯＭを示す図である。
【図７】本発明の一実施形態によりＷｅｂページ内の項目リストを自動的に検出するためのプロセスの一例を示す動作流れ図である。
【図８】本発明の一実施形態によりＷｅｂページ内の項目リストを自動的に検出するためのプロセスの一例を示す動作流れ図である。
【図９】本発明の一実施形態による情報処理システムの詳細図を示すブロック図である。
【発明を実施するための形態】
【００１０】
動作環境
図１は、本発明の様々な実施形態に適用可能な動作環境１００の一例を示している。図示の通り、１つまたは複数のユーザ・システム１０２は、１つまたは複数のネットワーク１０４に通信可能に結合される。さらに、Ｎ台のＷｅｂサーバ１０６、１０８は、ネットワーク（複数も可）１０４に通信可能に結合される。ネットワーク（複数も可）１０４は、この実施形態では、広域ネットワーク、ローカル・エリア・ネットワーク、有線ネットワーク、あるいは無線ネットワークなど、またはこれらの組み合わせである。それぞれのＷｅｂサーバ１０６、１０８は、Ｗｅｂブラウザ１１４などのアプリケーションを介してユーザ・システム１０２のユーザによってアクセス可能なＷｅｂサイトおよびそのＷｅｂページなどのＷｅｂコンテンツ１１０、１１２を含む。Ｗｅｂコンテンツ１１０、１１２はＷｅｂブラウザ１１４を介してユーザに対して表示可能な任意のコンテンツを指すことに留意されたい。Ｗｅｂコンテンツ１１０、１１２は、Ｗｅｂサーバ１０６、１０８内に常駐するかまたはＷｅｂサーバ１０６、１０８に結合されたシステム上に常駐することができる。ユーザ・システム（複数も可）１０２は、一実施形態では、パーソナル・コンピュータ、ノートブック・コンピュータ、ワークステーション、ＰＤＡ、インターネットをブラウズ可能な携帯電話、タブレット・コンピューティング・デバイスなどである。一実施形態によるネットワーク（複数も可）１１０は、ＬＡＮ、ＷＡＮ、Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ、無線ネットワークなどを含む。
【００１１】
ユーザ・システム１０２はＷｅｂブラウザ１１４と項目リスト検出器１１６とを含む。項目リスト検出器１１６は、ブラウジング・モニター１１８と、分布計算器１２０と、ドキュメント・オブジェクト・モデル（ＤＯＭ）発生器１２２と、ＤＯＭ分析器１２４と、ＤＯＭノード識別器１２６とを含む。これらのコンポーネントのそれぞれについては、以下により詳細に述べる。ユーザ・システム１０２は、ブラウジング履歴情報１２８（本明細書では「ブラウジング対話情報１２８」または「対話情報１２８」ともいう）と、Ｗｅｂページ１３０と、ＤＯＭ１３２も含む。項目リスト検出器１１６内に示されているこれらのコンポーネントのうちの１つまたは複数はＷｅｂブラウザ１１４内にも常駐できることに留意されたい。また、ユーザ・システム１０２のコンポーネントのうちの１つまたは複数はユーザ・システム１０２の外部に常駐できることにも留意されたい。
【００１２】
項目リスト検出器１１６は、一実施形態では、Ｗｅｂページ１３０内のユーザのアクションを記録することによって収集されたブラウジング履歴情報（対話ログ）１２８を活用することにより、Ｗｅｂページ１３０内の項目リスト１３４を自動的に検出する。項目リスト１３４は、一実施形態では、検索結果など、Ｗｅｂページ１３０内に提示された項目のリストである。項目リスト１３４はＷｅｂページ１３０内の項目の分類法である。項目リスト検出器１１６はブラウジング履歴情報１２８を使用して、いつユーザが項目リスト１３４の項目と対話したかを判断する。次に、項目リスト検出器１１６は、Ｗｅｂページ１３０のＤＯＭ１３２内のＤＯＭツリーからその対話した（たとえば、クリックした）項目を識別する。次に、項目リスト検出器１１６は、その項目の親要素の提示パターン・ベースの特徴を計算する。次に、それぞれのパターンがそのリスト内の１つの項目を表すような繰り返しパターンを備えたＤＯＭツリー・ノードを見つけるために、項目リスト検出器１１６によってボトムアップ・トラバーサル手法が使用される。次に、繰り返しパターンを備えた識別済みＤＯＭノードが項目リストとして識別される。
【００１３】
見て分かるように、項目リスト検出器１１６は、項目リスト１３４内の１つの項目の対話情報１２８である「ローカライズされた」手掛かりを使用して、リスト全体を検出する。したがって、項目リスト検出器１１６は、不正確さをもたらす可能性のある、いずれかの定義済みテンプレート、ドメイン知識、オントロジ、モデルを構築するための手作業、またはグローバル・サーチ戦略の使用を必要としない。項目リスト検出器１１６はブラウジング履歴情報（たとえば、対話ログ）からの「ローカライズされた」知識を使用し、項目リスト（複数も可）を明確に検出することができる。
【００１４】
Ｗｅｂページ内の項目リストの自動検出
Ｗｅｂページ内の項目リストを自動的に検出することに関するより詳細な考察を以下に示す。上述の通り、項目リスト検出器１１６はブラウジング履歴情報１２８を使用して、項目リスト１３４を自動的に検出する。ブラウジング履歴情報１２８はブラウジング・モニター１１８によって生成される。ブラウジング履歴モニター１１８は、Ｗｅｂブラウザ１１４を使用してＷｅｂコンテンツについてユーザによって行われた様々なアクションを含む、ユーザのブラウジング履歴をモニターするものである。ブラウジング・モニター１１８は、項目リスト１３４内の項目のクリック、書式フィールドへの値の入力、チェックボックスのターンオン、ボタンのクリックなど、対話のレベルでＷｅｂブラウジング履歴を継続的に記録する。これは、従来のＷｅｂ履歴インターフェースを超えるものであり、ページ・タイトルおよびＵＲＬを記録するだけである場合と比較して、訪問したすべてのＷｅｂページ上で実行されたアクションについてより完全なイメージをユーザに提供するものである。ブラウジング・モニター１１８によって記録された情報はブラウジング履歴情報１２８として保管される。このようなブラウジング履歴を記録するための方法は、Ｉａｎ  Ｌｉｅｔ  他による「Ｈｅｒｅ’ｓ  ｗｈａｔ  Ｉ  ｄｉｄ：  ｓｈａｒｉｎｇ  ａｎｄ  ｒｅｕｓｉｎｇ  ｗｅｂ  ａｃｔｉｖｉｔｙ  ｗｉｔｈ  ＡｃｔｉｏｎＳｈｏｔ」（２０１０年のＣＨＩ  ２０１０：コンピューティング・システムにおけるヒューマン・ファクタに関する第２８回国際会議の議事録、７２３〜７３２ページ）に記載されている。ユーザのＷｅｂブラウジングを記録するためのその他の方法を使用することもできる。
【００１５】
図２は、本発明の一実施形態で使用される模範的なＷｅｂブラウジング対話履歴２００を示している。ユーザ・インターフェース２０２はユーザのＷｅｂブラウジング対話履歴２００を表示する。この実施形態では、あるＷｅｂサイトのＷｅｂページで実行されたアクション２０４、時間情報２０６、Ｗｅｂページ・タイトル情報２０８、およびＷｅｂページＵＲＬ情報２１０がインターフェース２０２の１つまたは複数の領域に表示される。その他のタイプの情報もＷｅｂブラウジング対話履歴１２８に維持し表示することができる。
【００１６】
図２に示されているブラウジング対話履歴２００は、ローカル・ディレクトリ検索Ｗｅｂサイトとのユーザの対話に基づいて記録された対話ログを示している。特に、ブラウジング対話履歴２００は、ユーザが「商号またはカテゴリ」というテキストボックスに「ガソリンスタンド」という検索キーワードを入力したことを示す第１の記録済み対話（ｒｅｃｏｒｄｅｄ  ｉｎｔｅｒａｃｔｉｏｎ）２１４を含む。第２の記録済み対話２１６は、ユーザが「都市、州、または郵便番号」というテキストボックスに「サンノゼ、カリフォルニア州」を入力したことを示している。第３の記録済み対話２１８は、「検索」ボタンをクリックすることによりユーザが検索書式をサブミットしたことを示しており、その結果、ユーザの検索照会と一致する項目のリストを含む検索結果ページが表示されている。図３は、「サンノゼ、カリフォルニア州」の「ガソリンスタンド」というユーザの検索照会をＷｅｂサーバ１０６が受信したことに応答してユーザに対して表示された検索結果項目リスト３０４に関する第１の複数項目３０２を示している。図２に戻ると、ブラウジング対話履歴２００は、ユーザが「ガソリンスタンドＡ」というリンクをクリックしたことを示す第４の記録済み対話２２０をさらに含み、そのリンクは図３の項目３０２に示されている第１のリンク３０６である。
【００１７】
Ｗｅｂページ１３０に関するブラウジング対話履歴２００が識別されると、項目リスト検出器１１６のＤＯＭ発生器１２２はＷｅｂページ１３０のＤＯＭ１３２を生成／構築する。たとえば、図４は、図３に示されている項目リスト３０４を含むＷｅｂページに関するＤＯＭツリー・フラグメント４００の可視化を示している。次に、項目リスト検出器１１６は、各組の対話情報（たとえば、ログ）１２８について、Ｗｅｂページ１３０に関するＤＯＭ１３２を分析して、Ｗｅｂページ１３０内のある要素が繰り返しパターンを備えた先祖を有するような要素との対話の結果として対話情報が記録されたかどうかを判断する。
【００１８】
たとえば、項目リスト検出器１１６のＤＯＭ分析器１２４はＤＯＭ１３２を分析する。ＤＯＭノード識別器１２６は、ユーザが対話した要素に対応するＤＯＭノードを識別する。実施形態によっては、対話情報１２８は、ＤＯＭノードへのＸＰａｔｈなどの特定のポインタを含み、それにより、この識別プロセスが単純明快になっている。しかし、他の実施形態では、対話情報１２８に含まれる対話したＷｅｂページ要素（たとえば、「ガソリンスタンドＡ」）のラベルは、ＤＯＭツリーから特定のＤＯＭノードを見つけるための検索語として使用される。この識別済みＤＯＭノードはＮｉとして示すことができる。たとえば、図４では、ＤＯＭツリー４００内の強調表示されたノード４０２（「＜ａ」というタグによって識別される）は図３の検索結果リスト３０４内の第１の項目３０６に対応する。この強調表示されたＤＯＭツリー・ノード４０２は「ガソリンスタンドＡ」という項目３０６に対応する。
【００１９】
ＤＯＭノード４０２が識別されると、項目リスト検出器１１６は、分布計算器１２０を介して、Ｎｉの親が一様な子ノード・タグ分布を有するかどうかを計算する。たとえば、子ノードのうちの５つが「ｄｉｖ」タグであり、１つがｔａｂｌｅタグであり、１つが「ｈ２」タグである場合、子タグ分布は（ｄｉｖ：５，ｔａｂｌｅ：１，ｈ２：１）になる。図４は、リスト項目「ガソリンスタンドＡ」３０６の親ＤＯＭノード４０４を示している。唯一の子ノードはリンク・ノード４０２（ＨＴＭＬタグ「＜ａ」が付いている）であり、したがって、分布はａ：１になる。
【００２０】
子タグ分布の一様性を計算している間、分布計算器１２０はｔｅｘｔ、ｐ、ｓｃｒｉｐｔ、ｂｒ、およびｈｒスタイル・タグなど、構造に影響を及ぼさないタグを無視することに留意されたい。分布計算器１２０は、子タグのうちの少なくともＸ％が等しい場合およびその下のサブツリーも一様／類似構造を有する（たとえば、子タグのうちの少なくともＸ％が等しい）場合、子タグ分布が一様／類似であると判断する。この場合、Ｘ％は、所望の正確さに応じて変更することができるしきい値である。類似タグが付いている子ノードが類似構造を有するかどうかを計算するために、分布計算器１２０は、子ノードのそれぞれのタグ分布を計算し、その類似性を計算し（たとえば、類似性測度（ｓｉｍｉｌａｒｉｔｙ  ｍｅａｓｕｒｅ）を計算し）、類似性しきい値を使用して一致を宣言する。このプロセスは、子タグ分布に関して上述したプロセスと同様である。しかし、類似タグが付いている子ノードが類似構造を有するかどうかを判断している間、分布計算器１２０は、これらの子ノードのうちのいくつのタグが一致するかを探し、子タグのうちのＹ％が一致する場合に一致を宣言し、その場合、Ｙは類似性しきい値である。図４に示されている例では、親ノード４０４は１つの子ノードのみを有し、したがって、子タグ分布の類似性は必要ない。しかし、子タグ分布の類似性を計算するプロセスについては、この親ＤＯＭノード４０４の先祖ノードについてこの類似性テストを実行することに関して、以下にさらに述べる。
【００２１】
Ｎｉの親ノードの子タグ分布が一様／類似ではない（上述の一様分布を判断するためのプロセスに基づく）かまたはその分布が１つの子ノードのみを有する場合、項目リスト検出器１１６は、ボトムアップ方式でＤＯＭツリーを検索し続けて、類似性しきい値に関して上述した通り、一様／類似子サブツリー構造を備えた一様／類似子タグ分布を有するノードを識別する。このようなノードがまったく見つからない場合、項目リスト検出器１１６は、対話情報１２８に対応する対話した要素に関する項目リストを識別しない。
【００２２】
しかし、子タグ分布が一様／類似である場合、項目リスト検出器１１６は、ＤＯＭノード識別器１２６を介して、親ノード４０４を候補「項目リスト」ノードとして識別する。しかし、主要項目リストの代わりに、ある項目内のサブリストが識別されなかったことを保証するために、ボトムアップ検索が続行される。たとえば、項目リスト検出器１１６は、識別済み候補「項目リスト」ノードについて上述の技法を実行して、この候補「項目リスト」ノードの親も一様／類似タグ分布を有するかどうかを判断する。この新しい親ノードがこのような一様な（または実質的に類似の）子タグ分布を有する場合、項目リスト検出器１１６はこのノードを候補「項目リスト」として識別する。
【００２３】
たとえば、図５は、「シェル・ガソリンスタンド」というリンク・ノード４０２の先祖ノード５０２（たとえば、リンク・ノード４０２の親ノード４０４の親ノード５０２）の子タグ分布を示している。このノード５０２は、ＤＯＭ分析器１２４がリンク・ノード４０２の親ノード４０４からボトムアップに移動するときにテストされる。このノード５０２は、ｓｐａｎタイプのノードである３つの子ノード５０４、５０６、５０８（子ノードの５０％）を有する。この例では、５０％というこの数字は７５％というしきい値より低く、したがって、類似ノードの子ノード・タグ分布も類似であるかどうかを判断する第２のテストはここでは不要である。しかし、この場合、これらのｓｐａｎタグ・ノード５０４、５０６、５０８の子ノードは類似ではないので、このようなテストは失敗に終わるであろう。たとえば、ノード５０４、５０６、５０８は一致タグを有するので、潜在的類似ノードである。しかし、ＤＯＭ分析器１２４がその子ノード分布を計算する予定である場合、ＤＯＭ分析器１２４は、そのタグ分布が一致しないので、これらのノードは類似ではないと判断するであろう。一致タグが付いているノードの割合が５０％であり、この例ではしきい値７５％より低いので、この第２のテストはここでは不要である。
【００２４】
ＤＯＭ分析器１２４は、ボトムアップ方向にＤＯＭツリー内をトラバースし続け、図６に示されている先祖ＤＯＭノード６０２について上記の一様／類似性テストが成功したと判断する。ここでは、先祖ノード６０２の子タグ６０４、６０６、６０８、６１０、６１２、６１４、６１６、６１８はｄｉｖノードであり、その子タグ６２０、６２２、６２４、６２６の分布も一様／類似である。したがって、ＤＯＭノード識別器１２６は先祖ノード６０２を「項目リスト」ノードとして識別する。ＤＯＭ分析器１２４は、項目リスト１３４に対応する識別済みノード６０２の任意の先祖が、項目リスト１３４を識別するために使用されたものと同じプロパティを有するかどうかも判断することに留意されたい。そうである場合、項目リスト検出器１１６は、先祖ノード６０２に基づいて識別された項目リスト１３４が他のリストに含まれると判断する。図６に示されている現在の例では、「項目リスト」ノード６０２の親ＤＯＭノードは上記の一様性／類似性テストを満足せず、したがって、項目リスト・ノードとして識別されない。したがって、リスト検出器１１６は、一様性／類似性識別プロセスを完了し、項目リスト１３４に対応する識別済み「項目リスト」ノード６０２を返す。
【００２５】
上記の考察から分かるように、項目リスト検出器１１６はリストの１つの項目の対話情報である「ローカライズされた」手掛かりを使用して、リスト全体を検出する。したがって、項目リスト検出器１１６は、不正確さをもたらす可能性のある、いずれかの定義済みテンプレート、ドメイン知識、オントロジ、モデルを構築するための手作業、またはグローバル・サーチ戦略の使用を必要としない。項目リスト検出器１１６はブラウジング履歴情報（たとえば、対話ログ）からの「ローカライズされた」知識を使用し、項目リスト（複数も可）を明確に検出することができる。この解決策は、自動項目リスト検出が重要であって、Ｗｅｂ自動化アプリケーション、情報検索アプリケーション、およびＷｅｂアクセシビリティ・アプリケーションなどを含むがこれらに限定されない、様々なＷｅｂアプリケーションに統合することができる。
【００２６】
動作流れ図
次に、図７〜図８を参照すると、これらの図の流れ図およびブロック図は、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラム製品について可能な実現例のアーキテクチャ、機能、および動作を例示している。この点に関しては、流れ図またはブロック図内の各ブロックは、指定の論理機能（複数も可）を実現するための１つまたは複数の実行可能命令を含む、コードのモジュール、セグメント、または一部分を表すことができる。また、いくつかの代替実現例では、ブロック内に示された機能は図面内に示された順序から外れて行われる可能性があることに留意されたい。たとえば、連続して示されている２つのブロックは、関係する機能に応じて、実際にはほぼ同時に実行される場合もあれば、ときには逆の順序で実行される場合もある。また、ブロック図あるいは流れ図またはその両方の各ブロックおよびブロック図あるいは流れ図またはその両方内の複数ブロックの組み合わせは、指定の機能または行為を実行する特殊目的ハードウェアベースのシステムあるいは特殊目的ハードウェアとコンピュータ命令との組み合わせによって実現可能であることも留意されるであろう。
【００２７】
図７〜図８は、Ｗｅｂページ内の項目リストを自動的に検出するためのプロセスの概要を示す動作流れ図である。このプロセスに関するより詳細な考察は図２〜図６に関してすでに上記で示されていることに留意されたい。図７の動作の流れはステップ７０２から始まり、ステップ７０４に直接移行する。項目リスト検出器１１６は、ステップ７０４で、所与のＷｅｂページ１３０に関する１組のブラウザ対話情報１２８を識別する。この１組のブラウザ対話情報１２８は、ユーザがＷｅｂページ１３０の１つの要素と対話したことを示している。
【００２８】
項目リスト検出器１１６は、ステップ７０６で、所与のＷｅｂページ１３０に関するＤＯＭ１３２を構築する。項目リスト検出器１１６は、ステップ７０８で、ユーザが対話した要素に対応するＤＯＭノードを識別する。項目リスト検出器１１６は、ステップ７１０で、分析中の現在のノードの親ノードを識別し、この繰り返しはユーザが対話した要素に対応するＤＯＭノードである。項目リスト検出器１１６は、ステップ７１２で、上述の通り、親ノードが一様／類似子分布を含むかどうかを判断する。この判断の結果が否定である場合、項目リスト検出器１１６は、ステップ７１４で、先祖ノード（たとえば、現在の親ノードの親ノード）が存在するかどうかを判断する。この判断の結果が肯定である場合、制御の流れはステップ７１０に戻る。この判断の結果が否定である場合、制御の流れはステップ７１６で終了し、項目リストはＷｅｂページ１３０内で識別されない。
【００２９】
ステップ７１２の判断の結果が肯定である場合、項目リスト検出器１１６は、ステップ７１８で、その親ノードを候補「項目リスト」ノードとして識別する。次に、制御は図８の入口点Ａに移行し、同図では、項目リスト検出器１１６は、ステップ８０２で、候補「項目リスト」ノードとして識別された現在の親ノードの親ノードを識別する。項目リスト検出器１１６は、ステップ８０４で、上述の通り、この新しい親ノードが一様／類似子分布を含むかどうかを判断する。この判断の結果が否定である場合、項目リスト検出器１１６は、ステップ８０６で、前の親ノードを候補「項目リスト」ノードとして維持する。次に、制御はステップ８１６に移行する。
【００３０】
ステップ８０４の判断の結果が肯定である場合、項目リスト検出器１１６は、ステップ８０８で、新しい親ノードの子ノードが一様／類似子分布を有するかどうかを判断する。この判断の結果が否定である場合、項目リスト検出器１１６は、ステップ８１０で、前の親ノードを候補「項目リスト」ノードとして維持する。次に、制御はステップ８１６に移行する。この判断の結果が肯定である場合、項目リスト検出器１１６は、ステップ８１２で、新しい親ノードを候補「項目リスト」ノードとして識別する。項目リスト検出器１１６は、ステップ８１４で、任意の先祖ノードが存在するかどうかを判断する。この判断の結果が肯定である場合、制御の流れはステップ８０２に戻る。この判断の結果が否定である場合、項目リスト検出器１１６は、ステップ８１６で、現在の候補「項目リスト」ノードを「項目リスト」ノードとして識別する。次に、制御の流れはステップ８１８で終了する。
【００３１】
情報処理システム
次に、図９を参照すると、この図は本発明の諸実施形態で使用可能な情報処理システムを示すブロック図である。情報処理システム９００は、本発明の１つまたは複数の実施形態を実現するように適合され、適切に構成された処理システムに基づくものである（たとえば、図１のユーザ・システム１０２）。適切に構成された処理システムであれば、いずれでも、本発明の諸実施形態において情報処理システム９００として使用することができる。
【００３２】
情報処理システム９００はコンピュータ９０２を含む。コンピュータ９０２は、メイン・メモリ９０６、大容量記憶装置インターフェース９０８、およびネットワーク・アダプタ・ハードウェア９１０に接続されたプロセッサ（複数も可）９０４を有する。システム・バス９１２はこれらのシステム・コンポーネントを相互接続する。コンピュータ９０２についてＣＰＵ９０４が１つだけ示されているが、複数のＣＰＵを備えたコンピュータ・システムも同様に効果的に使用することができる。この実施形態のメイン・メモリ９０６は、項目リスト検出器１１６およびそのコンポーネント、Ｗｅｂブラウザ１１４、ブラウジング対話履歴１２８、Ｗｅｂページ１３０、ならびにＤＯＭ１３２を含む。
【００３３】
大容量記憶装置インターフェース９０８は、大容量記憶装置９１４などの大容量記憶装置を情報処理システム９００に接続するために使用される。１つの特定のタイプのデータ記憶装置はＣＤ／ＤＶＤドライブなどの光学ドライブであり、これは、ＣＤ／ＤＶＤ９１６など（ただし、これに限定されない）のコンピュータ可読媒体またはストレージ製品にデータを保管し、そこからデータを読み取るために使用することができる。他のタイプのデータ記憶装置は、たとえば、ＮＴＦＳタイプのファイル・システム動作をサポートするように構成されたデータ記憶装置である。
【００３４】
メイン・メモリに含まれているオペレーティング・システムは、Ｌｉｎｕｘ（Ｌｉｎｕｘは、米国、その他の国、あるいはその両方におけるＬｉｎｕｓ  Ｔｏｒｖａｌｄｓの登録商標である）、ＵＮＩＸ（ＵＮＩＸは米国およびその他の国におけるオープン・グループの登録商標である）、Ｗｉｎｄｏｗｓ（Ｍｉｃｒｏｓｏｆｔ、Ｗｉｎｄｏｗｓ、Ｗｉｎｄｏｅｗｓ  ＮＴ、およびＷｉｎｄｏｗｓのロゴは、米国、その他の国、あるいはその両方におけるＭｉｃｒｏｓｏｆｔ社の商標である）、ならびにＷｉｎｄｏｗｓ  Ｓｅｒｖｅｒベースのオペレーティング・システムのうちのいずれかなどの適切なマルチタスク・オペレーティング・システムである。また、本発明の諸実施形態は任意のその他の適切なオペレーティング・システムを使用することもできる。本発明のいくつかの実施形態は、情報処理システム９００内に位置する任意のプロセッサ上でオペレーティング・システムのコンポーネントの命令を実行できるようにする、オブジェクト指向フレームワーク・メカニズムなどのアーキテクチャを使用する。ネットワーク・アダプタ・ハードウェア９１０は、ネットワーク１０４へのインターフェースを提供するために使用される。本発明の諸実施形態は、現代のアナログあるいはデジタルまたはその両方の技術を含む任意のデータ通信接続によるかもしくは将来のネットワーキング・メカニズムを介して機能するように適合させることができる。
【００３５】
非制限的な例
本明細書で使用する用語は、特定の諸実施形態のみを記述するためのものであって、本発明を限定するためのものではない。本明細書で使用する「ａ」、「ａｎ」、および「ｔｈｅ」という単数形は、文脈が明らかにそうではない場合を示さない限り、複数形も含むためのものである。「ｃｏｍｐｒｉｓｅｓ」あるいは「ｃｏｍｐｒｉｓｉｎｇ」またはその両方の用語は、本明細書で使用する場合、所定の特徴、整数、ステップ、動作、要素、あるいはコンポーネント、またはこれらの組み合わせの存在を指定するが、１つまたは複数のその他の特徴、整数、ステップ、動作、要素、コンポーネント、あるいはそのグループ、またはこれらの組み合わせの存在または追加を排除しないことがさらに理解されるであろう。
【００３６】
以下の特許請求の範囲内のすべての手段またはステップならびに機能要素に対応する構造、材料、行為、およびそれと同等のものは、具体的に請求されている他の請求要素と組み合わせてその機能を実行するための任意の構造、材料、または行為を含むためのものである。本発明の説明は、例示および解説のために提示されたものであり、網羅するためまたは開示された形式に本発明を限定するためのものではない。多くの変更および変形は、本発明の範囲を逸脱せずに当業者にとって明白なものになる。この実施形態は、本発明の原理および実用的な適用例を最も良く説明するため、ならびにその他の当業者が企図された特定の用途に適した様々な変更を含む様々な実施形態について本発明を理解できるようにするために、選択され記載されたものである。
【図１】
2014527235.tif 000003
【図２】
2014527235.tif 000004
【図３】
2014527235.tif 000005
【図４】
2014527235.tif 000006
【図５】
2014527235.tif 000007
【図６】
2014527235.tif 000008
【図７】
2014527235.tif 000009
【図８】
2014527235.tif 000010
【図９】
2014527235.tif 000011
【手続補正書】
【提出日】平成26年3月20日(2014.3.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
項目リストの自動検出のための方法であって、
所与のＷｅｂページに関連するユーザのＷｅｂブラウジング対話履歴を分析することであって、前記Ｗｅｂブラウジング対話履歴が、前記ユーザが前記Ｗｅｂページの少なくとも１つの要素と対話したことを示すことと、
前記所与のＷｅｂページのドキュメント・オブジェクト・モデル（ＤＯＭ）を構築することと、
前記分析に基づいて、前記Ｗｅｂページに関連する前記要素に対応する前記ＤＯＭ内のノードを識別することと、
前記要素を含む前記Ｗｅｂページに関連する項目リストに対応する前記ノードの先祖ノードを、少なくとも前記先祖ノードの子タグの分布に基づいて識別することと
を含む、方法。
【請求項２】
前記ノードが、
前記Ｗｅｂブラウジング対話履歴に関連するポインタであって、前記ノードを指すものと、
前記Ｗｅｂブラウジング対話履歴に関連する前記要素のラベル
のうちの１つに基づいて識別される、請求項１記載の方法。
【請求項３】
前記先祖ノードを識別することが、
前記ノードの親ノードを識別することと、
前記親ノードの１組の子ノードに対応する１組の子タグの分布を決定することと、
前記分布に基づいて、一致子タグの数を決定することと、
前記一致子タグの数が所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つであるかどうかを判断することと、
少なくとも前記一致子タグの数が前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つであることに応答して、前記親ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する候補ノードとして識別することと
をさらに含む、請求項１または請求項２記載の方法。
【請求項４】
前記先祖ノードを識別することが、
前記親ノードの先祖ノードが、前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つである一致子タグの数を含み損なっていると判断することと、
前記親ノードを、前記Ｗｅｂページに関連する項目リストに対応する、前記ノードの前記先祖ノードとして識別することと
をさらに含む、請求項３記載の方法。
【請求項５】
少なくとも前記一致子タグの数が前記所与のしきい値未満であることに応答して、前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つである一致子タグの数を少なくとも含む前記親ノードの第１の先祖ノードについて前記ＤＯＭに関連するボトムアップ検索を実行することと、
前記第１の先祖ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する候補ノードとして識別することと
をさらに含む、請求項３または請求項４記載の方法。
【請求項６】
少なくとも前記第１の先祖ノードの第２の先祖ノードが、前記所与のしきい値に等しいものおよびそれを超えるもののうちの少なくとも１つである一致子タグの数を含み損なっていると判断することと、
前記第１の先祖ノードを、前記Ｗｅｂページに関連する項目リストに対応する、前記ノードの前記先祖ノードとして識別することと
をさらに含む、請求項５記載の方法。
【請求項７】
前記親ノードを、前記Ｗｅｂページに関連する前記項目リストに対応する候補ノードとして識別することが、
前記１組の子ノードに関連する類似性測度を決定することと、
前記類似性測度を類似性しきい値と比較することと、
前記類似性測度が類似性しきい値に等しいものおよびそれを超えるもののうちの少なくとも１つであることに応答して、前記親ノードを、前記Ｗｅｂページ内の前記項目リストに対応する前記候補ノードとして識別することと
をさらに含む、請求項３ないし６のいずれか一項に記載の方法。
【請求項８】
前記類似性測度を決定することが、
それぞれの子ノードの構造を前記１組の子ノードに関連する他の子ノードと比較することと、
前記比較に基づいて、一致構造を含む前記１組の子ノードに関連する子ノードの数を決定することであって、前記類似性測度が一致構造を含む子ノードの数であることと
を含む、請求項７記載の方法。
【請求項９】
項目リストの自動検出のためのシステムであって、請求項１ないし８のいずれか一項に記載の方法のすべての前記ステップを実行するよう構成された前記システム。
【請求項１０】
コンピュータ・プログラムであって、請求項１ないし８のいずれか一項に記載の方法のすべての前記ステップを実行するようになっているコンピュータ・プログラム。
【国際調査報告】
2014527235.tif 000012
2014527235.tif 000013