(57)【要約】【課題】ユーザ嗜好解析に有効なWebページの閲覧履歴を高精度で抽出すること。【解決手段】ユーザ端末３とＷｅｂサーバ４との間のHTTPリクエストおよびHTTPレスポンスの組であるHTTPペア群が、トラフィック抽出部１１で抽出され、レスポンスフィルタ部１３でテキストデータの種別として特定された後、トラフィック抽出装置１のリクエストフィルタ部１４が、参照元ＵＲＬが抽出できなかった各HTTPペアと、連続するHTTPペア内に重複する同一参照元ＵＲＬが出現したとき、その参照元ＵＲＬを要求ＵＲＬとするHTTPペアとを特定し、データ抽出部１６が、リクエストフィルタ部１４の特定したHTTPペアから、キーワードの文字列を抽出する。【選択図】図１
2011170597.tif 000002
【特許請求の範囲】
【請求項１】
Ｗｅｂページを要求するためのHTTPリクエストと、そのHTTPリクエストへの応答であるHTTPレスポンスとの組であるHTTPペアからデータを抽出するデータ抽出装置であって、
前記データ抽出装置は、トラフィック抽出部と、レスポンスフィルタ部と、リクエストフィルタ部と、データ抽出部と、記憶手段とを備えており、
前記トラフィック抽出部は、入力されるHTTPペアから、そのHTTPペアの前記HTTPリクエストにテキスト以外の種別を示すキーワードが含まれているHTTPペアを除外した残りのHTTPペアを抽出し、
前記レスポンスフィルタ部は、前記トラフィック抽出部が抽出したHTTPペアから、そのHTTPペアの前記HTTPレスポンスにテキストの種別を示すキーワードが含まれているHTTPペアを抽出し、
前記リクエストフィルタ部は、前記レスポンスフィルタ部が抽出した各HTTPペアから、そのHTTPペアの前記HTTPリクエストに含まれるＷｅｂページの所在を示す要求ＵＲＬと、そのＷｅｂページの参照元であるＷｅｂページの所在を示す参照元ＵＲＬとを抽出し、
その抽出処理において、参照元ＵＲＬが抽出できなかった各HTTPペアと、
連続するHTTPペア内に重複する同一参照元ＵＲＬが出現したとき、その参照元ＵＲＬと一致する前記要求ＵＲＬを含むHTTPペア群のうちの先頭のHTTPペアとを特定し、
前記データ抽出部は、前記リクエストフィルタ部が特定したHTTPペアから、キーワードの文字列を抽出して、前記記憶手段に記憶することを特徴とする
データ抽出装置。
【請求項２】
前記データ抽出装置は、さらに、リストチェック部を備えており、
前記リストチェック部は、前記リクエストフィルタ部によって特定されなかった所定数のHTTPペア群それぞれの参照元ＵＲＬにおいて、所定メッセージ数内に重複する同一参照元ＵＲＬが出現しなかったとき、その参照元ＵＲＬが出現したHTTPペアを特定し、
前記データ抽出部は、前記リクエストフィルタ部および前記リストチェック部がそれぞれ特定したHTTPペアから、キーワードの文字列を抽出して、前記記憶手段に記憶することを特徴とする
請求項１に記載のデータ抽出装置。
【請求項３】
前記記憶手段には、複数のHTTPペアを格納するためのデータ構造として、１つのHTTPペアを１つのエントリとし、エントリの格納位置をハッシュ関数によって特定する前記ハッシュマップが格納され、
前記ハッシュ関数は、エントリに含まれるハッシュキーを入力パラメータとする関数であり、そのハッシュキーには、前記リクエストフィルタ部が抽出する前記要求ＵＲＬと参照元ＵＲＬとをそれぞれ用いることを特徴とする
請求項１または請求項２に記載のデータ抽出装置。
【請求項４】
Ｗｅｂページを要求するためのHTTPリクエストと、そのHTTPリクエストへの応答であるHTTPレスポンスとの組であるHTTPペアからデータを抽出するデータ抽出装置によるデータ抽出方法であって、
前記データ抽出装置は、トラフィック抽出部と、レスポンスフィルタ部と、リクエストフィルタ部と、データ抽出部と、記憶手段とを備えており、
前記トラフィック抽出部は、入力されるHTTPペアから、そのHTTPペアの前記HTTPリクエストにテキスト以外の種別を示すキーワードが含まれているHTTPペアを除外した残りのHTTPペアを抽出し、
前記レスポンスフィルタ部は、前記トラフィック抽出部が抽出したHTTPペアから、そのHTTPペアの前記HTTPレスポンスにテキストの種別を示すキーワードが含まれているHTTPペアを抽出し、
前記リクエストフィルタ部は、前記レスポンスフィルタ部が抽出した各HTTPペアから、そのHTTPペアの前記HTTPリクエストに含まれるＷｅｂページの所在を示す要求ＵＲＬと、そのＷｅｂページの参照元であるＷｅｂページの所在を示す参照元ＵＲＬとを抽出し、
その抽出処理において、参照元ＵＲＬが抽出できなかった各HTTPペアと、
連続するHTTPペア内に重複する同一参照元ＵＲＬが出現したとき、その参照元ＵＲＬと一致する前記要求ＵＲＬを含むHTTPペア群のうちの先頭のHTTPペアとを特定し、
前記データ抽出部は、前記リクエストフィルタ部が特定したHTTPペアから、キーワードの文字列を抽出して、前記記憶手段に記憶することを特徴とする
データ抽出方法。
【請求項５】
前記データ抽出装置は、さらに、リストチェック部を備えており、
前記リストチェック部は、前記リクエストフィルタ部によって特定されなかった所定数のHTTPペア群それぞれの参照元ＵＲＬにおいて、所定メッセージ数内に重複する同一参照元ＵＲＬが出現しなかったとき、その参照元ＵＲＬが出現したHTTPペアを特定し、
前記データ抽出部は、前記リクエストフィルタ部および前記リストチェック部がそれぞれ特定したHTTPペアから、キーワードの文字列を抽出して、前記記憶手段に記憶することを特徴とする
請求項４に記載のデータ抽出方法。
【請求項６】
前記記憶手段には、複数のHTTPペアを格納するためのデータ構造として、１つのHTTPペアを１つのエントリとし、エントリの格納位置をハッシュ関数によって特定する前記ハッシュマップが格納され、
前記ハッシュ関数は、エントリに含まれるハッシュキーを入力パラメータとする関数であり、そのハッシュキーには、前記リクエストフィルタ部が抽出する前記要求ＵＲＬと参照元ＵＲＬとをそれぞれ用いることを特徴とする
請求項４または請求項５に記載のデータ抽出方法。
【請求項７】
請求項４ないし請求項６のいずれか１項に記載のデータ抽出方法を、コンピュータである前記データ抽出装置に実行させるためのデータ抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ抽出装置、データ抽出方法、および、データ抽出プログラムに関する。
【背景技術】
【０００２】
近年、パケット内のペイロード部までを閲覧可能なフィルタリング製品が増加し、ネットワークトラフィック(以下トラフィック)などのリアルタイムに流れるデータの分析、抽出を高速に行うことが可能となっている。上記製品は、主にファイアウォールやProxyサーバなどで利用されており、トラフィックからユーザがアクセスしたWebページ、アクセス回数、時間、Webページ遷移情報など、様々な情報を分析することが可能である。
【０００３】
一方、ユーザの嗜好を解析する技術として、協調フィルタリングなどがあるが、予めストックされたデータを用いた分析が想定されており、リアルタイムに流れるトラフィックから嗜好解析を行うためには様々な課題が考えられる。また、ブラウザ側でWebアクセス情報を取得する方式もあるが、プラグインのインストールが必要であり、嗜好データのとれる範囲が限定されてしまう。
【０００４】
また、関連研究として、Proxyを用いたユーザのWebページの閲覧履歴からユーザの類似度を求める研究（非特許文献１参照）がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】丹英之他,「Proxy Logに基づいたコンテンツ自動推薦による知識共有支援システムの提案」,情報処理学会  第68回全国大会, 6C-2, 2006
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ユーザのWebページの閲覧履歴はHTTPのトラフィックから抽出可能である。しかし、HTTPのトラフィックからWebページの閲覧履歴に関する情報を高精度に抽出することは、従来の技術では不充分である。ここで、高精度な抽出処理とは、Webページの閲覧履歴ではないノイズを、Webページの閲覧履歴として誤抽出してしまう（いわゆる、false positive）事象と、Webページの閲覧履歴であるにもかかわらず、抽出を見逃してしまう（いわゆる、false negative）事象との双方を抑制することである。
【０００７】
例えば、非特許文献１では、参照先URLのドメイン名からWebページの概要を手動で一意に定めているため、htmlに含まれる広告用画像データなどのノイズ情報を、Webページの閲覧履歴として拾ってきてしまう。
また、HTTPリクエストURLの拡張子に対してフィルタリングを行ったとしても、近年増加しているAPIなどへのHTTPリクエストは、拡張子がないためフィルタリング条件をすり抜けてしまうため、Webページの閲覧履歴として抽出すべきHTTPリクエストを見逃してしまう。
【０００８】
そこで、本発明は、前記した問題を解決し、ユーザ嗜好解析に有効なWebページの閲覧履歴を高精度で抽出することを、主な目的とする。
【課題を解決するための手段】
【０００９】
前記課題を解決するために、本発明は、Ｗｅｂページを要求するためのHTTPリクエストと、そのHTTPリクエストへの応答であるHTTPレスポンスとの組であるHTTPペアからデータを抽出するデータ抽出装置であって、
前記データ抽出装置が、トラフィック抽出部と、レスポンスフィルタ部と、リクエストフィルタ部と、データ抽出部と、記憶手段とを備えており、
前記トラフィック抽出部が、入力されるHTTPペアから、そのHTTPペアの前記HTTPリクエストにテキスト以外の種別を示すキーワードが含まれているHTTPペアを除外した残りのHTTPペアを抽出し、
前記レスポンスフィルタ部が、前記トラフィック抽出部が抽出したHTTPペアから、そのHTTPペアの前記HTTPレスポンスにテキストの種別を示すキーワードが含まれているHTTPペアを抽出し、
前記リクエストフィルタ部が、
前記レスポンスフィルタ部が抽出した各HTTPペアから、そのHTTPペアの前記HTTPリクエストに含まれるＷｅｂページの所在を示す要求ＵＲＬと、そのＷｅｂページの参照元であるＷｅｂページの所在を示す参照元ＵＲＬとを抽出し、
その抽出処理において、参照元ＵＲＬが抽出できなかった各HTTPペアと、
連続するHTTPペア内に重複する同一参照元ＵＲＬが出現したとき、その参照元ＵＲＬと一致する前記要求ＵＲＬを含むHTTPペア群のうちの先頭のHTTPペアとを特定し、
前記データ抽出部が、前記リクエストフィルタ部の特定したHTTPペアから、キーワードの文字列を抽出して、前記記憶手段に記憶することを特徴とする。
【００１０】
これにより、ユーザ嗜好解析に有効なWebページの閲覧履歴を高精度で抽出することができる。
例えば、トラフィック抽出部は、広告用画像データなどのテキスト以外のHTTPリクエストを除去することで、ノイズの誤抽出（false positive）を抑制する。
次に、レスポンスフィルタ部は、テキストの種別を示すキーワードが含まれているHTTPレスポンスを抽出することで、正解抽出の見逃し（false negative）を抑制する。
そして、リクエストフィルタ部は、リファラ（参照元ＵＲＬ）が連続するHTTPペアを特定することで、APIへのHTTPリクエストなどの、トラフィック抽出部では除去できないHTTPリクエストを除去する。
【００１１】
本発明は、さらに、前記データ抽出装置がリストチェック部を備えており、
前記リストチェック部が、前記リクエストフィルタ部によって特定されなかった所定数のHTTPペア群それぞれの参照元ＵＲＬにおいて、所定メッセージ数内に重複する同一参照元ＵＲＬが出現しなかったとき、その参照元ＵＲＬが出現したHTTPペアを特定し、
前記データ抽出部は、前記リクエストフィルタ部および前記リストチェック部がそれぞれ特定したHTTPペアから、キーワードの文字列を抽出して、前記記憶手段に記憶することを特徴とする。
【００１２】
これにより、リストチェック部が、リクエストフィルタ部が抽出していない、リファラが連続しないHTTPペアを抽出することで、リストチェック部を設けない構成に対して、さらに、正解であるWebページの閲覧履歴の抽出率を高めることができる。
【００１３】
本発明は、さらに、前記記憶手段には、複数のHTTPペアを格納するためのデータ構造として、１つのHTTPペアを１つのエントリとし、エントリの格納位置をハッシュ関数によって特定する前記ハッシュマップが格納され、
前記ハッシュ関数は、エントリに含まれるハッシュキーを入力パラメータとする関数であり、そのハッシュキーには、前記リクエストフィルタ部が抽出する前記要求ＵＲＬと参照元ＵＲＬとをそれぞれ用いることを特徴とする。
【００１４】
これにより、特に多くのHTTPペアを扱うデータ抽出装置にとって、各HTTPペアへのデータアクセスの高速化を実現することができる。例えば、リクエストフィルタ部は、連続する複数のHTTPペアにアクセスするときには、それらのHTTPペアの格納位置を、ハッシュ関数によって高速に特定する。
【発明の効果】
【００１５】
本発明によれば、ユーザ嗜好解析に有効なWebページの閲覧履歴を高精度で抽出することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態に関するＷｅｂシステムを示す構成図である。
【図２】本発明の一実施形態に関する抽出情報データベースを示す構成図である。
【図３】本発明の一実施形態に関する嗜好情報データベースを示す構成図である。
【図４】本発明の一実施形態に関するトラフィック抽出装置における処理の概要である。
【図５】本発明の一実施形態に関するハッシュマップ（hashMap）のデータ構造を示す説明図である。
【図６】本発明の一実施形態に関するリクエストフィルタ部におけるフィルタリング手順を示すフローチャートである。
【図７】本発明の一実施形態に関するリストチェック部が実行する、HTTPリクエストチェック用処理を示すフローチャートである。
【図８】本発明の一実施形態に関するデータ抽出部が実行する、HTTPデータの抽出処理を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、本発明の一実施形態を、図面を参照して詳細に説明する。
【００１８】
図１（ａ）は、Ｗｅｂシステムの概要を示す構成図である。Ｗｅｂシステムは、トラフィック抽出装置１（データ抽出装置）と、嗜好情報分析装置２と、ユーザ端末３と、Ｗｅｂサーバ４とを含めて構成される。これらのＷｅｂシステムの各装置は、ＣＰＵとメモリとハードディスク（記憶手段）とネットワークインタフェースを有するコンピュータとして構成され、このコンピュータは、ＣＰＵが、メモリ上に読み込んだプログラムを実行することにより、各処理部を動作させる。
ユーザ端末３から入力されたＷｅｂサーバ４へのHTTPリクエストは、トラフィック抽出装置１に入り、Ｗｅｂサーバ４へ送信される。そして、HTTPリクエストへの応答としてのＷｅｂサーバ４からのHTTPレスポンスは、トラフィック抽出装置１に入り、ユーザ端末３へ送信される。以下、HTTPリクエストと、その応答としてのHTTPレスポンスとの組を、HTTPペアと表記する。
【００１９】
なお、HTTPペアが流れるネットワーク９は、例えば、インターネットサービスプロバイダのネットワークである。ここで、トラフィック抽出装置１を設置する場所として、ネットワーク９内だけでなく、社内Proxyなどを設置するインターネットゲートウェイなど、ユーザによるトラフィックを取得できる場所であればどこでもよい。
【００２０】
トラフィック抽出装置１は、ユーザ端末３によるＷｅｂサーバ４の利用トラフィックとして、Ｗｅｂサーバ４へのHTTPリクエストとHTTPレスポンスを抽出する。なお、トラフィック抽出装置１は、入力トラフィックとして、HTTP用トラフィック（HTTPペア）だけでなく、P2P用トラフィックなどの他のネットワークトラフィックを扱ってもよい。
嗜好情報分析装置２は、トラフィック抽出装置１によるトラフィックの抽出結果から取得される嗜好情報をもとに、その分析処理を実行する。
【００２１】
図１（ｂ）は、トラフィック抽出装置１の詳細を示す構成図である。トラフィック抽出装置１は、トラフィック抽出部１１と、嗜好情報抽出部１２と、抽出情報データベース５０と、嗜好情報データベース６０とを有する。
【００２２】
トラフィック抽出部１１は、ユーザ端末３とＷｅｂサーバ４との間に位置し、市販のProxyやファイアウォールなどに用いられるディープパケットインスペクション（DPI）製品などにより実現される。トラフィック抽出部１１は、ユーザ端末３とＷｅｂサーバ４との間のトラフィックに含まれる各パケットのペイロード内部までを展開し、そのフローパターンやパケットの振る舞いを分析することで、各パケットを扱うアプリケーションの識別を行う。
【００２３】
トラフィック抽出部１１は、文字情報（キーワード）をトラフィックから抽出するため、文字情報が記載されているＷｅｂページの通信に使用されるHTTPパケットを、ユーザ端末３とＷｅｂサーバ４との間のトラフィックから抽出する。トラフィック抽出部１１は、具体的には、以下の手順（１）〜（４）により、HTTPペアを抽出して、嗜好情報抽出部１２に出力する。
手順（１）：HTTPリクエストのGET_URLの拡張子を参照して、該当するHTTPリクエストを除外する処理。除外する拡張子は、テキストファイル以外の情報（画像データなど）を含む拡張子であり、例えば、「jpg jpeg gif flv swf css js jsp ico png xls」である。
手順（２）：HTTPリクエストのAcceptタグを参照して、該当するHTTPリクエストを除外する処理。Acceptに「image／*」が含まれるものを除外する。URLに.jpgなどの拡張子が無くても、Acceptタグにimage／pngなどと書かれている（htmlの<IMG src="url">をブラウザが実行するとAcceptタグを付けてHTTPリクエストを送信することを利用）。
手順（３）：HTTPリクエストのHTTPメソッドがGET／POST以外のHTTPリクエストは、ユーザの嗜好情報抽出に無関係であるため、フィルタリングし除外する。
手順（４）：前記の手順（１）〜手順（３）のいずれにも該当しない（除外されない）HTTPリクエストに対応するHTTPレスポンスを抽出する。例えば、HTTPリクエストのGET_URLの拡張子が無い場合や、拡張子「.cgi」や、拡張子「.html」は、キーワードが記載されている可能性があるトラフィックなので、除外しないようにする。
【００２４】
嗜好情報抽出部１２は、トラフィック抽出部１１から入力されるトラフィックデータ（HTTPペア）に含まれるＷｅｂページの通信履歴や閲覧履歴などから、嗜好分析用情報を抽出し、嗜好情報データベース６０（詳細は、図３参照）に書き出す。
なお、嗜好情報抽出部１２は、ユーザ端末３とＷｅｂサーバ４との間のトラフィックデータについて、複数のユーザ端末３による個々のトラフィックデータが同時に流れることを考慮して、ユーザごとにトラフィックデータを抽出したデータを、抽出情報データベース５０（詳細は、図２参照）へと書き出す。
嗜好情報データベース６０は、嗜好情報として、閲覧したＷｅｂページの概要となるキーワードの集合や、ユーザごとの閲覧したＷｅｂページの遷移履歴、検索キーワード、投稿文章などの嗜好分析用情報を時系列に格納するデータベースである。
【００２５】
嗜好情報抽出部１２は、レスポンスフィルタ部１３と、リクエストフィルタ部１４と、リストチェック部１５と、データ抽出部１６とを含めて構成される。
【００２６】
レスポンスフィルタ部１３は、HTTPペアのHTTPレスポンスを用いたフィルタリングを行う。具体的には、レスポンスフィルタ部１３は、HTTPレスポンスパケットのヘッダのContent-typeが「text／html」であるHTTPペアをリクエストフィルタ部１４へ出力し、それ以外のContent-typeであるパケットは破棄する。
【００２７】
リクエストフィルタ部１４は、HTTPペアのHTTPリクエストを用いたフィルタリングを行う。具体的には、リクエストフィルタ部１４は、ユーザが閲覧、遷移したURLを抽出するために、過去にHTTPリクエスト内のGETに含まれるリファラ（Referer）を抽出する。なお、リファラとは、「GET_URL」（要求ＵＲＬ）で指定されたＷｅｂページを参照している（指定されたＷｅｂページへリンクしている）ＷｅｂページのＵＲＬ（つまり、参照元ＵＲＬ）である。
そして、リクエストフィルタ部１４は、直後の所定期間内に同じリファラを有するHTTPリクエストが複数連続で出現した場合（API呼出があった場合、他のページへの遷移があった場合など）、そのリファラが示すURLへユーザの閲覧対象が遷移したと判定する。
さらに、リクエストフィルタ部１４は、リファラが無いHTTPペア（ブックマークなどからのアクセスを抽出するため）や、連続で出現したリファラが示すURLを「GET_URL」とするHTTPペア（複数のメッセージのうちの先頭のHTTPペア）を、嗜好情報データベース６０に保存する（データ抽出部１６に保存を指示する）。なお、本実施形態では「HTTPペア」のことを、適宜「メッセージ」とも呼ぶ。
そして、リクエストフィルタ部１４は、入力されたHTTPペアを、後段のリストチェック部１５へと出力する。
【００２８】
リストチェック部１５は、HTTPリクエストで同一リファラが複数して続かない場合でも、ユーザの閲覧対象が遷移したとみなすケースをチェックする。具体的には、リストチェック部１５は、所定メッセージ数内に重複する同一リファラが出現しなかった場合、そのリファラが出現したメッセージのHTTPペアを、嗜好情報データベース６０に保存する（データ抽出部１６に保存を指示する）。
【００２９】
データ抽出部１６は、リクエストフィルタ部１４およびリストチェック部１５からそれぞれ入力されるHTTPペアから抽出したデータを、嗜好情報データベース６０に保存する。
【００３０】
図２は、抽出情報データベース５０を示す構成図である。抽出情報データベース５０は、ユーザ管理用マップ５１と、ユーザ管理用構造体５２と、ＵＲＬマップ５３と、リファラマップ５４と、データ履歴構造体５５とを含めて構成される。
【００３１】
ユーザ管理用マップ５１は、システムで１つ作成されるハッシュマップであり、０個以上のユーザ管理用構造体５２をエントリとして格納する。ハッシュキーである「ユーザＩＤ」は、トラフィック抽出部１１により渡されたHTTPペアに含まれる「From IP」ごとに設定するか、トラフィック抽出部１１がユーザＩＤを設定し、嗜好情報抽出部１２に引き渡してもよい。
ユーザ管理用構造体５２は、システムのユーザごとに作成される構造体であり、２つのハッシュマップ（ＵＲＬマップ５３およびリファラマップ５４）それぞれへのポインタから構成される。
【００３２】
ＵＲＬマップ５３は、システムのユーザごとに作成されるハッシュマップであり、０個以上のデータ履歴構造体５５をエントリとして格納する。ＵＲＬマップ５３は、ハッシュキー（ＵＲＬ）の衝突が発生すると、衝突したエントリ間をチェインすることで、ハッシュキーが衝突する複数のエントリを共に登録することを許可するハッシュマップである。
リファラマップ５４は、システムのユーザごとに作成されるハッシュマップであり、０個以上のデータ履歴構造体５５をエントリとして格納する。リファラマップ５４は、エントリ間を前後それぞれのポインタで接続することにより、エントリ間の順序性を保持するハッシュマップである。
【００３３】
データ履歴構造体５５は、HTTPデータ（HTTPペア）を履歴情報として保持するための構造体であり、５つの要素（ＵＲＬ、リファラヘッダ、HTTPリクエスト、HTTPレスポンス、送信フラグ）から構成される構造体である。
「ＵＲＬ」は、HTTPリクエストからGETまたはPOSTで指定されるＵＲＬをパース（走査）したものである。
「リファラヘッダ」HTTPリクエストからリファラヘッダを取り出したものである。
「HTTPリクエスト」は、HTTPリクエストデータへのポインタである。
「HTTPレスポンス」は、HTTPレスポンスデータへのポインタである。
「送信フラグ」は、「0x00：未送信」または「0x01：送信済」のいずれかを示す。
【００３４】
図３は、嗜好情報データベース６０を示す構成図である。嗜好情報データベース６０は、ユーザ嗜好ベクトルマップ６１と、ユーザ嗜好ベクトル構造体６２とを含めて構成される。
ユーザ嗜好ベクトルマップ６１は、データ抽出部１６による各ユーザのデータ抽出処理ごとのユーザ嗜好ベクトル構造体６２をエントリとするハッシュマップであり、そのハッシュキーとしてHTTPリクエストのドメイン名から切り出したキーワードが設定される。
ユーザ嗜好ベクトル構造体６２は、項目として、ユーザＩＤと、時刻と、キーワードと、HTTPリクエストカウンタと、HTTPレスポンスカウンタとを含む構造体である。
項目「時刻」は、1970年1月1日からの秒形式で示されるデータであり、キーワードの抽出時刻を示す。
項目「HTTPリクエストカウンタ」は、HTTPリクエストにキーワードが含まれていた場合にインクリメントするカウンタである。
項目「HTTPレスポンスカウンタ」は、HTTPレスポンスにキーワードが含まれていた場合にインクリメントするカウンタである。
【００３５】
図４（ａ）は、トラフィック抽出装置１における処理の概要である。
以下の各手順が、図４（ａ）に記載されている丸数字で示されている。
手順（１）ユーザ（ユーザ端末３）が、ＷｅｂサイトＢをHTTPリクエストで要求する（Referer＝Ａ、GET_URL＝Ｂ）。
手順（２）ＷｅｂサイトＢのデータ（htmlファイル）が、HTTPレスポンスで応答される。
手順（３）ＷｅｂサイトＢのhtmlファイルに含まれている各種リンク（Webページの画像や広告情報などを取得するためのリンク）それぞれについてのHTTPリクエストが発行されるが、キーワード抽出には不要なデータであるので、トラフィック抽出部１１の抽出からは除外される（例えば、拡張子「jpg」の画像データなど）。
手順（４）ＷｅｂサイトＢのhtmlファイルに含まれているＷｅｂサイトＣへのリンクにより、ＷｅｂサイトＣをHTTPリクエストで要求する（Referer＝Ｂ、GET_URL＝Ｃ）。
【００３６】
リクエストフィルタ部１４は、手順（１）の「GET_URL＝Ｂ」の後に、手順（２）〜（４）の「Referer＝Ｂ」が複数連続で出現した場合、手順（１）の「GET_URL＝Ｂ」で指定される「ＷｅｂサイトＢ」へ遷移したものとし、手順（１）および手順（２）のHTTPペアを嗜好情報データベース６０に保存する。
【００３７】
図４（ｂ）は、嗜好情報抽出部１２の処理概要を示す説明図である。嗜好情報抽出部１２は、トラフィック抽出部１１から入力されるHTTPペア（図４（ｂ）の上の表に示すRequestメッセージとResponseメッセージとの組）のうちのRequestメッセージに着目する。
図４（ｂ）の左下の吹き出し内で示したRequestメッセージには、RefererとGET_URLとが含まれている。リクエストフィルタ部１４では、GET_URL「http://B.jp/」を含むHTTPペアの後に、Referer「http://B.jp/」を含むHTTPペアが複数回連続で出現しているので、GET_URL「http://B.jp/」を含むHTTPペアをデータ抽出対象とする。
なお、吹き出し内の表で示す例では、API呼出や、他のページへの遷移があった場合のみリファラが一致するため、最後に遷移したWebページは、抽出できない。そこで、同一のRefererが複数回連続で出現しない場合でも、以下に示す「抽出パケットの条件（３つの条件のうちのいずれかを満たす）」を設けることで、リクエストフィルタ部１４およびリストチェック部１５によるHTTPペアのデータ抽出対象とすることができる。
・Refererが無いメッセージ（ブックマークなどからのアクセス）
・Refererがある場合、かつ、所定メッセージ数内に同一Refererが出現した場合は先頭のメッセージのみ
・Refererがある場合、かつ、所定メッセージ数内にRefererが１つしかないメッセージ
一方、図４（ｂ）の右下の表（トラフィック抽出部１１に直接流入したリクエスト）においては、トラフィック抽出部１１が、「GET_URL」の拡張子が「a.jpg」などの画像データであるときには、そのHTTPペアを嗜好情報抽出部１２に出力しない旨が例示されている。
【００３８】
図５は、ハッシュマップ（hashMap）のデータ構造を示す説明図である。ハッシュマップのデータ構造は、ユーザ管理用マップ５１、ＵＲＬマップ５３、リファラマップ５４、および、ユーザ嗜好ベクトルマップ６１でそれぞれ用いられる。ハッシュマップのデータ構造を用いることにより、そのハッシュマップのエントリの検索処理や登録処理を、高速化することができる。
【００３９】
図５の左側の「ハッシュEntity／ハッシュサイズｎ」と表記されている配列は、ハッシュ関数h1（z）の計算結果の値を配列の添字とする。配列の内容は、h1（z）の値に対応するハッシュEntry（以下、単にエントリとする）があるときには、そのエントリへのポインタであり、h1（z）の値に対応するエントリが存在しないときには「null」が初期値として設定されている。つまり、ハッシュ関数h1（z）は、エントリの格納位置を算出するためのハッシュ関数である。
【００４０】
図５の右側の「ハッシュEntry」は、ハッシュマップに格納されるエントリを示す。１つのエントリは、「key_hash」、「key_data」、「time」、「value」、「next」、「before」、および、「after」の組み合わせとして定義される。
「key_hash」は、ハッシュ関数h2（z）により求められたハッシュ値である。
「key_data」は、ハッシュキーのデータであり、例えば、ＵＲＬやリファラである。
「time」は、格納した時刻である。
「value」は、登録データであり、例えば、ＵＲＬやリファラである。ＵＲＬマップ５３やリファラマップ５４では、データ履歴構造体５５を登録データとして格納する。
「next」は、次チェインへのポインタである。なお、key_hashの値が重複したときには、「next」を用いて、重複するエントリ間をポインタで接続することにより、key_hashの値が重複する複数のエントリを１つのハッシュマップに共存することを許可する。このチェインする特徴は、主に、ＵＲＬマップ５３にて使用される。
「before」は、前エントリへのポインタである。
「after」は、後エントリへのポインタである。なお、複数のエントリを、「before」と「after」とを用いて先頭から順に接続することにより、エントリの順序性を保持する。この順序性は、主に、リファラマップ５４にて使用される。また、「before」および「after」で規定されるエントリ間の前後関係は、ＵＲＬマップ５３でチェインしている場合には、一番古い（一番前に位置する）エントリを検索して削除するために使用される。
【００４１】
以下、嗜好情報抽出部１２による、各データベース（抽出情報データベース５０、嗜好情報データベース６０）のハッシュマップに対するデータアクセスの内容について、以下の順に説明する。
（１）HTTPデータの追加処理（ＵＲＬマップ５３およびリファラマップ５４に対して）
（２）HTTPデータの削除処理（ＵＲＬマップ５３およびリファラマップ５４に対して）
（３）エントリの検索処理
【００４２】
まず、（１）HTTPデータの追加処理を説明する。まず、２つのハッシュマップ（ＵＲＬマップ５３、リファラマップ５４）で共通する追加処理の概要を示す。
キーをz、登録データをvとするとき、エントリの格納位置をハッシュ値h1（z）として求める。
格納されている値がnullの場合、エントリを格納する。このとき、格納するエントリのkey_hashはハッシュ関数h2（z）によって求められ、key_dataにz、valueに登録データv、next、before、afterをnullで設定する。
新たにキーをz’、登録データをv’としたとき、ハッシュ値h1（z’）がハッシュ値h1（z）と衝突したときは、ハッシュ値h2（z）を求め、エントリのkey_hashと比較する。
key_hashが等しいエントリが存在した場合は、key_dataを直接比較し同一キーか判断する。キーが重複していない場合は、チェインしている最後のエントリのnextに、衝突したデータを登録する。
ただし、エントリのtimeが指定値以上離れていた場合、登録内容を差し替えてデータを登録する。timeの設定は、設定ファイルにより指定される。
また、衝突時のチェイン数に上限を設け、上限を超える場合はエラーとして登録を行わない。最大チェイン数は設定ファイルにより指定される。
【００４３】
以下が、ハッシュマップ個別の追加処理である。
ＵＲＬマップ５３へのデータ登録では、URLをkey_dataとし、ＵＲＬマップ５３へデータ履歴構造体５５を登録する。key_dataを引数としてハッシュ関数h1からハッシュ値を求め、ＵＲＬマップ５３に登録を行う。登録の差異、キー（h1）が重複した場合は、エントリをチェインして管理する。
リファラマップ５４へのデータ登録では、リファラをキーにリファラマップ５４へデータ履歴構造体５５を登録する。登録データは順序性を管理するため、前および後のエントリへのポインタをハッシュマップ内に保持する。キーが重複していた場合、エラーとして登録は行わない。
【００４４】
次に、（２）HTTPデータの削除処理を説明する。まず、２つのハッシュマップ（ＵＲＬマップ５３、リファラマップ５４）で共通する削除処理の概要を示す。
キーzの情報をハッシュマップから削除する場合、h1（z）によりエントリの格納位置を求め、格納されているエントリを解放し、nullを設定する。
ただし、エントリがチェインしている（衝突してエントリがリンクしている）場合は、h2（z）を求め、key_hashが等しいエントリを削除し、エントリのnextポインタを適切に再設定する。
【００４５】
以下が、ハッシュマップ個別の削除処理である。
ＵＲＬマップ５３からのデータ削除では、URLをキーにＵＲＬマップ５３を検索する。キーに該当するデータが存在した場合は、該当するエントリがチェインしているか判定する。チェインしていない場合は、そのエントリをそのまま削除する。そのエントリがチェインしている場合は、チェインしているエントリのより先頭に位置するエントリ（一番古い）の削除を行う。
リファラマップ５４からのデータ削除では、リファラをキーにデータを検索し、該当するデータがある場合は、該当のエントリを削除する。この際、削除対象エントリの前および後にて管理しているポインタを更新する。
【００４６】
そして、（３）エントリの検索処理を説明する。
キーをzとして検索を実行するとき、エントリの格納位置をハッシュ値h1（z）として求める。格納されている値がnull以外の場合は、エントリを求め、valueを返却する。ただし、エントリがチェインしている場合は、nextポインタのエントリを参照し、key_hashが等しいエントリが存在しないことを確認する。エントリが等しい場合は、key_data自体を比較し、正しいデータを判断する。
【００４７】
図６は、リクエストフィルタ部１４におけるフィルタリング手順を示すフローチャートである。
【００４８】
Ｓ１０１において、リクエストフィルタ部１４は、処理対象のユーザＩＤにおけるハッシュマップを特定する。具体的には、リクエストフィルタ部１４は、トラフィック抽出部１１より入力されたHTTPペアごとに設定されるユーザＩＤより、ユーザ管理用マップ５１を検索する。
該当するユーザＩＤが存在した場合は、検索したユーザ管理情報よりＵＲＬマップ５３とリファラマップ５４とを用いて以降の処理を行う。
該当するユーザＩＤが存在しない場合は、新規ユーザＩＤのユーザ管理用構造体５２と、そのユーザ管理用構造体５２に対応する空の２つのハッシュマップ（ＵＲＬマップ５３とリファラマップ５４）を生成し、ユーザ管理用マップ５１へ登録する。
【００４９】
Ｓ１０２において、トラフィック抽出部１１から入力されたHTTPペアのHTTPリクエストパケットから、入力ＵＲＬ（GET_URLまたはPOST_URL）および入力リファラを抽出する。
Ｓ１０３において、入力リファラが抽出できたか否かを判定する。Ｓ１０３でＹｅｓならＳ１０４へ進み、Ｎｏならデータ履歴構造体５５をデータ抽出部１６に受け渡してHTTPデータの抽出処理（後記する図８の処理）を呼び出してから、Ｓ１１０へ進む。
Ｓ１０４として、入力リファラをキーにＵＲＬマップ５３を検索する。つまり、ＵＲＬマップ５３のエントリであるデータ履歴構造体５５から、入力リファラと一致するデータ履歴構造体５５の「ＵＲＬ」項目を検索する。該当するデータ履歴構造体５５が存在するときには、Ｓ１０５へ進み、該当するデータ履歴構造体５５が存在しないときには、Ｓ１０７へ進む。
【００５０】
Ｓ１０５として、Ｓ１０４で検索したデータ履歴構造体５５の「送信フラグ」項目の値が「0x00：未送信」であるか否かを判定する。Ｓ１０５でＹｅｓならＳ１０６へ進み、ＮｏならＳ１０７へ進む。
Ｓ１０６として、Ｓ１０４で検索したデータ履歴構造体５５の「送信フラグ」項目の値を「0x01：送信済」に設定し、そのデータ履歴構造体５５をデータ抽出部１６に受け渡してHTTPデータの抽出処理（後記する図８の処理）を呼び出してから、Ｓ１０９へ進む。
【００５１】
Ｓ１０７として、入力リファラをキーにリファラマップ５４を検索する。つまり、リファラマップ５４のエントリであるデータ履歴構造体５５から、入力リファラと一致するデータ履歴構造体５５の「リファラヘッダ」項目を検索する。該当するデータ履歴構造体５５が存在するときには、Ｓ１０８へ進み、該当するデータ履歴構造体５５が存在しないときには、Ｓ１０９へ進む。
Ｓ１０８として、Ｓ１０７で検索したデータ履歴構造体５５をリファラマップ５４から削除する。また、Ｓ１０４と同様に、入力ＵＲＬをキーにＵＲＬマップ５３を検索し、合致するデータ履歴構造体５５をＵＲＬマップ５３から削除する。
【００５２】
Ｓ１０９として、トラフィック抽出部１１から入力されたHTTPデータを未送信データとして（「送信フラグ」項目の値に「0x00：未送信」を設定して）、ＵＲＬマップ５３およびリファラマップ５４へ登録し、リストチェック部１５の処理を実行し、フローチャートを終了する。
Ｓ１１０として、トラフィック抽出部１１から入力されたHTTPデータを送信済データとして（「送信フラグ」項目の値に「0x01：送信済」を設定して）、ＵＲＬマップ５３およびリファラマップ５４へ登録し、リストチェック部１５の処理を実行し、フローチャートを終了する。
【００５３】
図７は、リストチェック部１５が実行する、HTTPリクエストチェック用処理を示すフローチャートである。この処理では、同一リファラが複数続かない場合でも遷移を検出する。
【００５４】
Ｓ１２１として、リファラマップ５４のサイズ（格納するエントリ数）が最大リスト数を超過しているか否かを判定する。Ｓ１２１でＹｅｓならＳ１２２へ進み、Ｎｏならばなにもせずに本フローチャートを終了する（前記のように入力されたHTTPデータがリファラマップ５４へ登録される）。なお、最大リスト数は、あらかじめシステム管理者などにより、所定値が設定されている。
Ｓ１２２として、リファラマップ５４に格納されている最大リスト数を超過するHTTPデータ（データ履歴構造体５５）の送信フラグが「未送信」か否かを判定する。Ｓ１２２でＹｅｓならＳ１２３へ進み、ＮｏならＳ１２４へ進む。
Ｓ１２３として、未送信のHTTPデータをデータ抽出部１６（後記する図８の処理）へ受け渡す。
Ｓ１２４として、リファラマップ５４に格納されている最大リスト数を超過するHTTPデータを削除する。
【００５５】
図８は、データ抽出部１６が実行する、HTTPデータの抽出処理を示すフローチャートである。
【００５６】
Ｓ２０１として、データ抽出部１６は、リクエストフィルタ部１４およびリストチェック部１５からそれぞれ受け取ったHTTPリクエスト情報から、HTTPメソッドのHTTPリクエストURIを取得し、HTTPリクエストURIからドメイン情報（ドメイン名、キーワード）の抽出を行う。
例えば、HTTPリクエストURI「http://www.hogehoge.foo.co.jp/」からドメイン情報として、ドメイン名「hogehoge.foo」を抽出し、さらにそのドメインから２つのキーワード「hogehogeとfoo」）を抽出する。
まず、HTTPリクエストURIからドメイン名の切り出し処理として、あらかじめ設定ファイルに登録されている除外キーワード「http://www.」および「.co.jp/」をHTTPリクエストURIから抽出して除外する。
次に、ドメイン名からキーワードの切り出し処理は、ドメイン名を.（ドット）で分割したものをキーワードとすることで実現できる。
【００５７】
Ｓ２０２として、データ抽出部１６は、Ｓ２０１で抽出されたキーワードを、嗜好情報データベース６０（図３参照）に登録する。そのため、データ抽出部１６は、ユーザ嗜好ベクトルマップ６１を作成し、そのユーザ嗜好ベクトルマップ６１のエントリであるユーザ嗜好ベクトル構造体６２の「キーワード」項目に抽出されたキーワードに登録するとともに、同じユーザ嗜好ベクトル構造体６２の「HTTPレスポンスカウンタ」項目の数値をインクリメントする。
【００５８】
データ抽出部１６は、以下に示すＳ２１１〜Ｓ２１７の処理において、HTTPリクエストからキーワードを抽出して、嗜好情報データベース６０に登録する。
Ｓ２１１として、HTTPリクエストURIからクエリを抽出する。クエリの抽出処理は、具体的には、HTTPリクエストURIの先頭から’?’を探索し、その後に現れる文字列をクエリとすることで実現できる。
Ｓ２１２として、Ｓ２１１で抽出したクエリを「&」をキーにして分割する。これをarray[n-1]（nは分割数）の配列へ格納する。
Ｓ２１３として、array[]の配列要素を先頭から[n-1]番目まで１つずつ順に選択する。以下、現在選択している配列要素をarray[i]とする。
Ｓ２１４として、array[i]の文字列と、設定ファイルの文字列とが一致するか否かを判定する。一致しない場合は、Ｓ２１３に戻って、次の要素を選択する（iをインクリメント）。一致するときには、Ｓ２１５へ進む。
Ｓ２１５として、array[i]の文字列を「=」にて分割し、key（左辺）とvalue（右辺）との組とする。さらに、valueに「%」が含まれていた場合は、URLデコードを行う。
Ｓ２１６として、Ｓ２１５の文字列に対して、文字コード変換を行う。文字コード変換に失敗した場合は、失敗したキーワードは無効とする。
Ｓ２１７として、Ｓ２１６で得られたvalueをキーワードとして嗜好情報データベース６０に登録する。つまり、データ抽出部１６は、ユーザ嗜好ベクトルマップ６１からキー（得られたvalue）に該当するユーザ嗜好ベクトル構造体６２を検索する。検索できたときには、該当するユーザ嗜好ベクトル構造体６２のHTTPリクエストカウンタをインクリメントする。検索できないときには、ユーザ嗜好ベクトル構造体６２を生成しHTTPリクエストカウンタを「１」として、ユーザ嗜好ベクトルマップ６１に登録する。
【００５９】
データ抽出部１６は、以下に示すＳ２２１〜Ｓ２２２の処理において、HTTPレスポンスからキーワードを抽出して、嗜好情報データベース６０に登録する。
Ｓ２２１として、HTTPレスポンスのhtmlファイルに含まれるWebページの概要を把握するために、html内metaタグのkeywordに含まれる単語を抽出する。多くのWebページにはmetaタグのkeywordに、各Webページを検索エンジンの上位にするためのキーワードが人為的に埋め込まれており、これを抽出することで、Webページの概要を把握する。
Ｓ２２２として、Ｓ２２１で抽出したキーワードを嗜好情報データベース６０に登録する。つまり、データ抽出部１６は、ユーザ嗜好ベクトルマップ６１からキー（Ｓ２２１で抽出したキーワード）に該当するユーザ嗜好ベクトル構造体６２を検索する。検索できたときには、該当するユーザ嗜好ベクトル構造体６２のHTTPレスポンスカウンタをインクリメントする。検索できないときには、ユーザ嗜好ベクトル構造体６２を生成しHTTPレスポンスカウンタを「１」として、ユーザ嗜好ベクトルマップ６１に登録する。
【００６０】
以上説明した本実施形態では、トラフィック抽出装置１は、トラフィック（HTTPリクエスト、HTTPレスポンス）が入力されると、入力されたトラフィックからユーザの嗜好情報に必要な情報を高速にフィルタリング（抽出）する。
トラフィック抽出装置１は、ネットワークトラフィックに含まれる各種データ（P2P、FTP、メディアデータ、テキストデータ）から、HTTPによるサイトアクセスに含まれるテキストデータを取得する。テキストデータは、容易に取得できてデータ量も少ない上、意味情報として加工もしやすい。
つまり、トラフィック抽出装置１は、ユーザ端末３による一般的な検索行動やWebページのアクセスから、ユーザの嗜好情報を判別する前のトラフィックフィルタリングを行う。さらに、嗜好情報分析装置２は、トラフィック抽出装置１の抽出結果を分析する。
これにより、サービスプロバイダは、嗜好情報分析装置２の分析結果を参照することで、トラフィック抽出装置１のユーザに対するターゲッティング広告などのサービスに二次利用することができる。
【００６１】
ここで、トラフィック抽出装置１の各処理部（トラフィック抽出部１１、嗜好情報抽出部１２）は、HTTPの中でもユーザの嗜好に関係するWebページ遷移情報や、アクセス先Webページの概要を知るために、扱うトラフィックを削減する。そこで、ユーザのHTTPアクセスを抽出し、解析データを削減する。
まず、リクエストフィルタ部１４は、ユーザが遷移したURLを抽出するために、HTTPリクエスト発生時にGETに含まれる参照元URLを抽出し、直後にそのURLを参照元とするHTTPリクエストが複数連続で出現した場合、そのURLへ遷移したものとする。このことで、あるユーザが遷移したURLに絞ってHTTPペアを抽出することができる。
次に、リストチェック部１５は、同一リファラが複数続かない場合でも遷移したとみなすケースをチェックする。これにより、最後に遷移したWebページを抽出できるため、高速にユーザの試行に関連する情報を抽出することが可能となる。
【符号の説明】
【００６２】
１      トラフィック抽出装置（データ抽出装置）
２      嗜好情報分析装置
３      ユーザ端末
４      Ｗｅｂサーバ
１１    トラフィック抽出部
１２    嗜好情報抽出部
１３    レスポンスフィルタ部
１４    リクエストフィルタ部
１５    リストチェック部
１６    データ抽出部
５０    抽出情報データベース
５１    ユーザ管理用マップ
５２    ユーザ管理用構造体
５３    ＵＲＬマップ
５４    リファラマップ
５５    データ履歴構造体
６０    嗜好情報データベース
６１    ユーザ嗜好ベクトルマップ
６２    ユーザ嗜好ベクトル構造体
【図１】
2011170597.tif 000003
【図２】
2011170597.tif 000004
【図３】
2011170597.tif 000005
【図４】
2011170597.tif 000006
【図５】
2011170597.tif 000007
【図６】
2011170597.tif 000008
【図７】
2011170597.tif 000009
【図８】
2011170597.tif 000010