改善された類似文書検出方法、装置、及びコンピュータ読み取り可能な記録媒体
【課題】本発明は、改善された類似文書検出方法に関するものである。
【解決手段】類似文書検出装置で行われる方法であって、複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティを抽出し、算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算し、算出された加重値に基づいて複数のウェブ文書が類似文書であるか否かを検出すること、を含むことを特徴とする。本発明によると、類似文書である可能性のある文書において、文書中の核心となる部分と核心ではない部分とを区別し、これにより互いに異なる加重値を与えることにより、より改善された方式で類似文書を判別して検索エンジンの精度を向上させることができる。
【解決手段】類似文書検出装置で行われる方法であって、複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティを抽出し、算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算し、算出された加重値に基づいて複数のウェブ文書が類似文書であるか否かを検出すること、を含むことを特徴とする。本発明によると、類似文書である可能性のある文書において、文書中の核心となる部分と核心ではない部分とを区別し、これにより互いに異なる加重値を与えることにより、より改善された方式で類似文書を判別して検索エンジンの精度を向上させることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、改善された類似文書検出方法、装置、及びコンピュータ読み取り可能な記録媒体に関し、より具体的には、収集されたウェブ文書のうち類似文書を検出する際に文書内で核心となる部分及び核心ではない部分を区別し、これにより互いに異なる加重値を与えて、類似文書を検出するためのより正確で改善された方法、装置及びコンピュータ読み取り可能な媒体に関する。
【背景技術】
【０００２】
最近、インターネットの使用が普及するにつれて、ユーザはインターネット検索を介して多様な情報を取得できるようになった。すなわち、ユーザはインターネットへのアクセスが可能なパソコンなどの端末装置を介してウェブブラウザのアドレスバーにＵＲＬのような識別子を入力することにより、インターネット検索サイトにアクセスして、自分が確認しようとする検索キーワードを入力して、ニュース、知識、ゲーム、コミュニティ、ウェブ文書などの多様な分野に係わる検索結果を見ることができるようになった。
【０００３】
上述のように、ユーザが検索しようとする内容を適切に示すために、インターネット検索サイト提供者はウェブ文書などを収集し、収集されたウェブ文書などに索引（ｉｎｄｅｘ）を構成して、これに基づいて検索結果をユーザに提供する機能を有する検索エンジンを設計して構成することが一般的であり、その中でもインターネット上に存在するウェブ文書を組織的かつ自動化した方法で探索及び収集する機能を有するウェブクローラ（Ｗｅｂ Ｃｒａｗｌｅｒ）は大きな役割を果たしている。
【０００４】
このようなウェブクローラの動作方式の一つとして、シード（ｓｅｅｄ）と呼ばれるＵＲＬリストから始めて、シードに含まれる全てのハイパーリンク（Ｈｙｐｅｒｌｉｎｋ）を認識してＵＲＬリストを更新（ｕｐｄａｔｅ）し、更新されたＵＲＬリストに該当するウェブ文書を再帰的に再び訪問する方式が用いられている。
【０００５】
しかし、一般的に収集対象となるウェブ文書の中には、その内容が大同小異であり、強いて別個に収集する必要性のないものが多いにもかかわらず、基本的なウェブクローラの動作方式に従ってウェブ文書の検索及び収集を行う場合には、ＵＲＬリストに含まれる全てのウェブ文書を訪問及び収集することになり、収集されたウェブ文書を保存する保存領域の問題、及び、これによる検索エンジンの性能及び効率性の低下などの様々な問題が現れた。
【０００６】
そこで、このような問題を解決するために、従来は、類似文書の検出技術を導入し、類似したウェブ文書が検出された場合、収集された重複する類似文書を保存領域から削除したり、当該文書が発見された経路（ｐａｔｈ）の収集速度を減少させたりするなどの作業を行っていた。
【０００７】
しかし、従来の類似文書検出技術の場合、同一または類似する領域の大きさに応じて類似文書であるか否かを検出するため、ウェブ文書におけるほとんどの領域が同一であっても核心となる部分が相違すれば、実際には類似文書ではないにもかかわらず、同一の部分が多いということにより一律に類似文書であると判断されるため、正常な文書の収集作業が妨害されることになり、その結果、検索精度が低下するという問題が存在する。
【０００８】
図１ａ及び図１ｂは、従来技術における類似文書検出技術によって類似文書と認められる場合の例を例示的に示した図である。図１を参照して、従来技術における類似文書検出技術の問題点について説明する。
【０００９】
図１ａ及び図１ｂに示された一例は、ウェブクローラによって収集される互いに異なるＵＲＬを有するそれぞれのウェブ文書を示す。ウェブ文書において核心となる部分である商品名、商品コードなど（図１ａのＡ領域及び図１ｂのＡ´領域）は相違しているが、相違する領域がウェブ文書全体のうちの小さな領域のみを占めており、メニュー、オプション、商品の詳細情報など多くの領域（図１ａ及び図１ｂにおけるＢ領域、Ｃ領域など）において同一の部分が存在するため、従来の類似文書の検出技術では、同一の領域がどれほど多いかに応じて類似文書であるか否かを判断する。しかし、当該ページにおいて最も核心的な部分である商品名や商品コードが相違する、すなわち、相違する商品に対する相違するウェブ文書であるため、類似文書であるとは認められないにもかかわらず、従来技術によると類似文書であると判断され、このうち一方が保存領域から削除されるため、検索エンジンのユーザに提供されなくなり、検索精度低下の問題が生じる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】韓国公開特許第１９９９―００８８６７８号公報
【特許文献２】韓国公開特許第１９９９―００４８７１４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、前記の従来技術の問題点を解決することを目的とする。
【００１２】
また、本発明は、類似文書である可能性のあるウェブ文書において、ウェブ文書中の核心となる部分と核心ではない部分とを区別し、これにより互いに異なる加重値を与えることにより、より改善された方式で類似文書を判別して検索エンジンの精度を向上させることを他の目的とする。
【００１３】
また、本発明は、類似文書検出結果に応じて、重複する類似文書をウェブ文書保存領域から削除して保存領域の無駄使いを防ぎ、これにより検索エンジンの性能を向上させることをさらに他の目的とする。
【課題を解決するための手段】
【００１４】
前記のような本発明の目的を達成して、後述する本発明に特有の効果を奏するための本発明の特徴的な構成は以下のとおりである。
【００１５】
本発明の一実施形態によると、改善された類似文書検出方法において、類似文書検出装置で行われる各ステップは、複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティを抽出し、算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算し、算出された加重値に基づいて複数のウェブ文書が類似文書であるか否かを検出すること、を含む。
【００１６】
本発明の他の実施形態によると、改善された類似文書検出装置は、複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティ抽出手段と、算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算する加重値計算手段と、算出された加重値に基づいて複数のウェブ文書が類似文書であるか否かを検出する類似文書検出手段と、を含む。
【発明の効果】
【００１７】
前記のように本発明によると、類似文書である可能性のある文書において、文書中の核心となる部分と核心ではない部分とを区別し、これにより互いに異なる加重値を与えることにより、より改善された方式で類似文書を判別して検索エンジンの精度を向上させることができる。
【００１８】
また、本発明によると、類似文書検出結果に応じて、重複する類似文書をウェブ文書保存領域から削除して保存領域の無駄使いを防ぎ、これによる検索エンジンの性能を向上させることができる。
【図面の簡単な説明】
【００１９】
【図１ａ】従来技術における類似文書検出技術により類似文書であると判断される場合の例を例示的に示した図である。
【図１ｂ】従来技術における類似文書検出技術により類似文書であると判断される場合の例を例示的に示した図である。
【図２】本発明の一実施形態における検索結果提供装置を含む全体システムを概略的に示した図である。
【図３】本発明の一実施形態における検索結果提供装置の詳細な構成を示した図である。
【図４】本発明の一実施形態における類似文書検出部の詳細な構成を示した図である。
【図５】本発明の一実施形態における類似文書検出方法を説明するためのフローチャートである。
【図６】本発明の一実施形態において、ウェブ文書のシムハッシュを計算する方式を説明するための図である。
【図７ａ】本発明の一実施形態におけるウェブ文書のＤＯＭ構造を抽出する方式を説明するための図である。
【図７ｂ】本発明の一実施形態におけるウェブ文書のＤＯＭ構造を抽出する方式を説明するための図である。
【図８ａ】本発明の一実施形態におけるウェブ文書のエンティティ及びその関連値の抽出を説明するための図である。
【図８ｂ】本発明の一実施形態におけるウェブ文書のエンティティ及びその関連値の抽出を説明するための図である。
【図８ｃ】本発明の一実施形態におけるウェブ文書のエンティティ及びその関連値の抽出を説明するための図である。
【図９ａ】本発明の一実施形態におけるエンティティごとの加重値計算を説明するための図である。
【図９ｂ】本発明の一実施形態におけるエンティティごとの加重値計算を説明するための図である。
【図１０】本発明の一実施形態において加重値が適用されたシムハッシュを計算する方式を説明するための図である。
【発明を実施するための形態】
【００２０】
後述する本発明の詳細な説明において、本発明を実施することができる特定の実施形態を例として示す添付の図面を参照する。これらの実施例は、当業者が本発明を十分に実施することができるように詳細に説明される。本発明の多様な実施例は互いに異なるが相互に排他的である必要はないということが理解されるべきである。例えば、本明細書に記載されている特定の形状、構造及び特性は、一実施例にすぎず、本発明の思想及び範囲を外れない限り他の実施例において実現されてもよい。また、開示された各実施例中の個別の構成要素の位置または配置は、本発明の思想及び範囲を外れない限り変更されてもよいということが理解されるべきである。従って、後述する詳細な説明は、限定的な意味に制限するものではない。本発明の範囲は、適切に説明されれば、その特許請求の範囲に記載されたものと均等な全ての範囲とともに添付の特許請求の範囲の記載によってのみ限定される。図面において類似する参照符号は様々な側面に亘って同一または類似する機能を指称する。
【００２１】
以下、本発明が属する技術分野における通常の知識を有する者が本発明を容易に実施することができるように、本発明の好ましい実施例について添付の図面を参照して詳細に説明する。
【００２２】
本発明の実施形態における「ウェブ文書」という用語は、インターネットエクスプローラなどのウェブブラウザプログラムを用いて読み込み可能な受動的または能動的な文書形式を全て含む広い意味で解釈されなければならず、ウェブ文書の文書形式として、主にＨＴＭＬ（ＨｙｐｅｒＴｅｘｔ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）が用いられるが、必ずしもこれに限定されず、ＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）、ＳＧＭＬ（Ｓｔａｎｄａｒｄ Ｇｅｎｅｒａｌｉｚｅｄ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）を含み、ウェブブラウザプログラムを用いて読み込み可能な文書形式であれば全てウェブ文書に該当する。ウェブブラウザプログラムを用いてウェブ文書を読み込むためには、一般的にウェブ文書が位置するアドレスをＵＲＬとして入力し、そのアドレス形式としてＨＴＴＰ（ＨｙｐｅｒＴｅｘｔ Ｔｒａｎｓｆｅｒ Ｐｒｏｔｏｃｏｌ）が多く用いられるが、必ずしもこれに限定されるものではない。
【００２３】
一方、本発明の実施形態における「ＵＲＬ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｌｏｃａｔｏｒ）」という用語は、ウェブ上でサービスを提供する各サーバに存在するファイルの位置を明示するためのものであって、アクセスすべきサービスの種類、サーバの位置（ドメインネーム）、ファイルの位置を含む。ＵＲＬの一般的な体系（ｓｙｎｔａｘ）は、「プロトコル：／／ホスト名／経路（ｐａｔｈ）／ファイル名？パラメータ」のような形式で構成されてもよい。ここで経路は、複数の経路を含んでもよく、パラメータも複数のパラメータを含んでもよい。例えば、ｈｔｔｐ：／／ｗｗｗ．ｘｘｘ．ｃｏｍ／ａ／ｂ／ｃ．ｈｔｍｌ？ｘ＝１＆ｙ＝２のようなＵＲＬにおいて、プロトコルはｈｔｔｐであり、ホスト名はｗｗｗ．ｘｘｘ．ｃｏｍであり、経路は／ａ／ｂ／であり、ファイル名はｃ．ｈｔｍｌであり、パラメータはｘ及びｙの２つであって、その値はそれぞれ１及び２である。
【００２４】
一方、本発明の実施形態における「類似文書」という用語は、その内容が同一であるかその内容の核心を含むほとんどが同一である複数のウェブ文書を示す広い意味で用いられる。検索エンジンの効率性を考慮して、類似文書を検出する際に基本となるウェブ文書以外のこれと重複する類似文書は、収集された保存領域から削除されて検索エンジンにより検索されないようにする。
【００２５】
［装置の全体構成］
図２は、本発明の一実施形態において検出された重複する類似文書を削除した検索データベースを用いた検索結果提供装置を含む全体装置を概略的に示した図である。
【００２６】
図２に示されているように、本発明の一実施形態における全体装置は、検索データベースを有する検索結果提供装置１００が通信網２００を介して複数のユーザ端末装置３００及び複数のウェブ文書サーバ４００に接続されてもよい。
【００２７】
まず、本発明の一実施形態によると、検索結果提供装置１００は、ユーザ端末装置３００から探索キーワード、すなわち、問い合わせ言語を受信し、これに基づいて検索を行った後、その結果として出力される検索結果をユーザ端末装置３００に伝送する機能を行う。また、検索結果提供装置１００は、収集部１２０（図３参照）を用いて一つ以上のウェブ文書サーバ４００から収集したウェブ文書において類似文書が存在する可能性のあるクラスタを生成し、生成されたクラスタから類似文書であるか否かを検出して、検出結果検索データベースに類似文書が保存された場合には、重複する類似文書を削除する機能を行ってもよい。
【００２８】
また、本発明の一実施形態によると、通信網２００は、有線・無線などのような通信状態を問わずに構成されてもよく、パーソナルエリアネットワーク（ＰＡＮ；Ｐｅｒｓｏｎａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ローカルエリアネットワーク（ＬＡＮ；Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、メトロポリタンエリアネットワーク（ＭＡＮ；Ｍｅｔｒｏｐｏｌｉｔａｎ Ａｒｅａ Ｎｅｔｗｏｒｋ）、広域ネットワーク（ＷＡＮ；Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）など、多様な通信網で構成されてもよい。
【００２９】
一方、本発明の一実施形態におけるユーザ端末装置３００は、ユーザが所定の問い合わせ言語に対する検索結果を提供されるように、通信網２００を介して検索結果提供装置１００に接続するための機能を含む入出力装置を意味し、デスクトップパソコンだけでなく、ノートパソコン、ワークステーション、パームトップ（ｐａｌｍｔｏｐ）パソコン、個人携帯情報端末（ｐｅｒｓｏｎａｌ ｄｉｇｉｔａｌ ａｓｓｉｓｔａｎｔ；ＰＤＡ）、ウェブパッド、スマートフォンを含む移動通信端末などのようにメモリ手段を備え、マイクロプロセッサを搭載して演算能力を備えたデジタル機器であればいずれも本発明におけるユーザ端末装置３００として採用され得る。好ましくは、ユーザ端末装置３００は、検索結果提供装置１００に接続し、問い合わせ言語を入力して検索結果を提供されるために、ユーザ端末装置３００内のウェブブラウザを実行して用いられてもよいが、必ずしもこれに限定されるものではない。
【００３０】
一方、本発明の一実施形態におけるウェブ文書サーバ４００は、検索結果提供装置１００内の収集部が収集するウェブ文書を含むウェブサーバの通称であり、物理的に特定のサーバや特定の内容／形式のウェブ文書に限定されるものではない。収集部が通信網２００を介してアクセスしてウェブ文書を収集することができるウェブサーバは全てウェブ文書サーバ４００に含まれると認められる。
【００３１】
［検索結果提供装置］
図３は、本発明の一実施形態における検索結果提供装置１００の詳細な構成図である。
【００３２】
図２を参照すると、本発明の一実施形態における検索結果提供装置１００は、検索部１１０、収集部１２０、類似文書検出部１３０、及び検索データベース１４０を含んでもよい。
【００３３】
検索部１１０は、ユーザ端末装置３００から受信した問い合わせ言語に対応する情報を検索データベース１４０から検索する。検索により抽出される検索結果はユーザ端末装置３００に伝送される。
【００３４】
収集部１２０は、ウェブ文書サーバ４００に保存されたウェブ文書をウェブクローラなどの公知の組織的な自動化された方法により検索及び収集して検索データベース１４０に保存する機能を行う。
【００３５】
類似文書検出部１３０は、収集部１２０を介して収集されるウェブ文書を多様な方法を用いて生成され得るクラスタに統合した後、ウェブ文書中のそれぞれのエンティティ（ｅｎｔｉｔｙ）がウェブ文書中の核心となる部分であるか否かに応じてその加重値を計算し、加重値を適用した類似文書を検出して類似文書が検出された場合、この結果を検索データベース１４０に保存されたウェブ文書に適用して重複して保存された類似したウェブ文書の削除を行うようにしてもよい。類似文書検出部１３０の各構成要素の詳細な機能については後述する。
【００３６】
検索データベース１４０は、検索結果を提供するために収集されたり保存されたりする各種情報を含んでもよく、その他にも収集部１２０が収集したウェブ文書を保存してもよい。また、類似文書検出部１３０の動作によって検索データベース１４０内に既に収集されたウェブ文書が重複して保存されている場合、その一部または全部が削除されてもよい。
【００３７】
図３には、検索データベース１４０のみを図示したが、本発明の一実施形態においいて収集部１２０が収集、検出したウェブ文書を保存するデータベースを別に構築し、そのうち類似文書検出部１３０によって検出された類似文書結果に基づいて重複するウェブ文書が削除された残りのみを検索データベース１４０に保存してもよい。また、図面において検索部１１０、収集部１２０、及び類似文書検出部１３０は、それぞれ別のブロックで示したが、これらは物理的に一つの装置において実現されてもよく、これらの一部またはそれぞれが物理的に異なる装置において実現されてもよく、同一の機能を行う複数の装置に物理的に並列的に実現されてもよい。このように、本発明は、各構成部分が設けられた機械またはデータベースの物理的な個数及び配置に限定されず、様々な方式によって設計、変更されてもよいことは、本発明の属する技術分野における通常の知識を有する者にとって自明である。
【００３８】
［類似文書検出部］
図４を参照して、本発明の一実施形態における検索結果提供装置１００の類似文書検出部１３０についてより詳細に説明すると、類似文書検出部１３０は、クラスタリング（ｃｌｕｓｔｅｒｉｎｇ）手段１３１、エンティティ（ｅｎｔｉｔｙ）抽出手段１３２、加重値計算手段１３３、及び類似文書検出手段１３４を含んでもよい。
【００３９】
ここで、本発明の一実施形態におけるクラスタリング手段１３１は、検索データベース１４０または別のデータベースに保存されている収集部１２０によって収集されたウェブ文書の中に類似文書が存在する可能性のあるクラスタを所定の方法によって生成する機能を行ってもよい。
【００４０】
本発明の一実施形態におけるクラスタリング手段１３１がクラスタを生成するために適用できる所定の方法は、例えば、ホスト（Ｈｏｓｔ）クラスタリング、パス（Ｐａｔｈ）クラスタリング、クエリ（Ｑｕｅｒｙ）クラスタリング、サイズ（Ｓｉｚｅ）クラスタリング、シムハッシュ（ＳｉｍＨａｓｈ）クラスタリング、ＤＯＭ（Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ Ｍｏｄｅｌ）クラスタリングなどを含んでもよく、クラスタリング手段１３１は、例示されていない他の方法を用いてクラスタを生成してもよく、または例示されたクラスタリング方法及び例示されていない他の方法のうちのいずれか一つ以上を様々な順序で組み合わせて適用してもよく、類似文書が存在する可能性のあるクラスタを生成するために様々な方法を取捨選択してもよいということは当業者にとって自明であろう。
【００４１】
前記例示されたそれぞれのクラスタリング方法について詳述すると、まず、ホストクラスタリングは、ウェブ文書の出処であるＵＲＬのうちホスト名が一致するＵＲＬを有するウェブ文書を一つのクラスタとして生成する方式を意味する。例えば、一つのウェブ文書がｈｔｔｐ：／／ｗｗｗ．ｘｘｘ．ｃｏｍ／ａ／ｂ／ｃ．ｈｔｍｌ？ｘ＝１＆ｙ＝２というＵＲＬを有する場合、当該ウェブ文書をホストクラスタリングにより一つのクラスタを生成すると、当該ウェブ文書のホスト名であるｗｗｗ．ｘｘｘ．ｃｏｍと一致するウェブ文書を一つのクラスタとして生成する。
【００４２】
次に、パスクラスタリングは、ウェブ文書の出処であるＵＲＬのうちホスト名とその経路まで一致するＵＲＬを有するウェブ文書を一つのクラスタとして生成する方式を意味する。前記例において、ホスト名とその経路であるｗｗｗ．ｘｘｘ．ｃｏｍ／ａ／ｂ／まで一致するウェブ文書を一つのクラスタとして生成する場合、これをパスクラスタリングという。
【００４３】
また、クエリクラスタリングは、ウェブ文書の出処であるＵＲＬのうちホスト名、経路、及びファイル名まで一致するか、またはファイル名に加えてパラメータまで一致するＵＲＬを有するウェブ文書を一つのクラスタとして生成する方式を意味する。前記例に続いて、ホスト名と経路、及びファイル名まで含むｗｗｗ．ｘｘｘ．ｃｏｍ／ａ／ｂ／ｃ．ｈｔｍｌが一致するＵＲＬを有するウェブ文書を一つのクラスタとして生成するか、またはこれに加えてパラメータまで一致する、すなわちパラメータとしてｘ及びｙを含むＵＲＬを有するウェブ文書を一つのクラスタとして生成する場合、これをクエリクラスタリングと呼ぶ。
【００４４】
前記ホストクラスタリング、パスクラスタリング及びクエリクラスタリングは、全てウェブ文書の出処であるＵＲＬに基づくクラスタ生成方法であって、一つのクラスタに含まれるウェブ文書の個数に基づき、一つ以上の最も適したクラスタリング方式が選択されてもよい。
【００４５】
次に、サイズクラスタリングは、ウェブ文書の大きさ（ｓｉｚｅ）に基づいて類似の大きさを有するウェブ文書を一つのクラスタとして生成する方式を意味する。例えば、ウェブ文書の大きさが１６００ｂｙｔｅから１６１５ｂｙｔｅに該当する場合に、一つのクラスタとして生成すると定義されている場合、その大きさが１６００ｂｙｔｅ、１６０８ｂｙｔｅ、１６１２ｂｙｔｅであるウェブ文書は、サイズクラスタリングによって全て一つのクラスタとして生成される。
【００４６】
一方、シムハッシュ（ＳｉｍＨａｓｈ）クラスタリングは、各ウェブ文書別に抽出され得るシムハッシュ値が類似するウェブ文書を一つのクラスタとして生成する方式を意味する。シムハッシュとは、Ｓｉｍｉｌａｒｉｔｙ Ｈａｓｈ基盤の技術であって、互いに異なるキーの値が入力された場合、互いに異なるハッシュ値を与える一般的なハッシング機能を維持すると共に、類似するキーの値が入力された場合、類似したハッシュ値を有するハッシュ関数を意味し、このようなシムハッシュ抽出方式を例にとって以下で説明する。
【００４７】
一つのウェブ文書は、ワード単位でパーシングされて分離されてもよく、分離されたそれぞれのワードは、所定のハッシングアルゴリズムを適用したハッシュ関数を用いて特定のハッシュ値に計算されてもよく、計算された特定のハッシュ値は二進数で表現されてもよい。ハッシュ関数に用いることができるハッシングアルゴリズムは、標準アルゴリズムであるＳＨＡ−１、ＨＡＳ−１６０などの既に公知されたアルゴリズムを含み、特定のキーに対する唯一の値を提供するハッシュ関数の機能を有するアルゴリズムであれば、本発明の一実施形態におけるシムハッシュクラスタリングに用いることができるということは当業者にとって自明である。シムハッシュ抽出方式により抽出されるシムハッシュは、このように一つのウェブ文書から分離された各ワード別に抽出されたハッシュ値をビット単位で計算した最終のハッシュ値を意味する。ビット単位で計算する際に特定の位置のビット値が１である場合は１に、０である場合は−１に変換した後、ハッシュ値別にビット単位の演算を行ってビット単位の最終値が正数である場合は１に、負数である場合は０に、再度変換する方式によりウェブ文書のシムハッシュを抽出してもよい。例えば、一つのウェブ文書をワード単位でパーシングした結果、合計３個のワードに分離され、各ワードに対するハッシュ値を二進数で表現した内容がそれぞれ１１０００１０１，０１１０１１１０、及び１００１００１０である場合、当該ウェブ文書のシムハッシュは、図６に示されるように、各ワードのハッシュ値でビット単位別に計算するために、１１０００１０１は、１，１，−１，−１，−１，１，−１，１に、０１１０１１１０は、−１，１、１，−１，１、１，１，−１に、また１００１００１０は、１，−１，−１，１，−１，−１，１，−１に変換された後、ハッシュ値別にビット単位の計算結果である１，１，−１，−１，−１，１、１，−１からハッシュ値をさらに変換すると、シムハッシュ１１０００１１０を抽出することができる。このように抽出されたシムハッシュは、複数のウェブ文書においてほとんどの内容が同一であれば、一部の内容が異なっていてもウェブ文書別に類似したシムハッシュを有する。
【００４８】
シムハッシュクラスタリングは、このように各ウェブ文書に対して抽出されたシムハッシュが類似するウェブ文書を一つのクラスタとして生成してもよいが、ここでシムハッシュが類似するか否かを判断するためには、シムハッシュ間のハミング距離（ｈａｍｍｉｎｇ ｄｉｓｔａｎｃｅ）が所定数値以下、例えば、シムハッシュが８ビットであると仮定した場合には１である場合を類似したウェブ文書として判断してもよい。ハミング距離は、同一のビット数を有する二進数の間に対応するビット値が一致しない個数を意味し、例えば、シムハッシュが１１０００１０１であるウェブ文書とシムハッシュが１００１０１０１であるウェブ文書との間のハミング距離は、合計８個のビットのうち、２番目のビット及び４番目の対応ビットが一致しないため、２であり、上述したように、例示的な類似基準である１よりハミング距離が小さいため、二つのウェブ文書は類似しないと判断されてもよい。また他の例として、シムハッシュが１１０００１０１であるウェブ文書と１１０１０１０１であるウェブ文書との間のハミング距離は、合計８個のビットのうち４番目の対応ビットのみが一致しないため、１に該当し、従って、前記例示的な類似基準である１以下に対応するため、二つのウェブ文書は類似していると判断されてもよい。
【００４９】
また、ＤＯＭ（Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ Ｍｏｄｅｌ）クラスタリングは、各ウェブ文書別に抽出され得るＤＯＭ構造が類似したウェブ文書を一つのクラスタとして生成する方式を意味する。ＤＯＭ構造とは、所定のウェブ文書の内容を抽出して、ツリー型に概念化した文書構造ツリーの一例であって、ウェブ文書のソースコードが図７ａであると仮定した場合、当該ウェブ文書から図７ｂのような形式のＤＯＭ構造を抽出してもよいが、必ずしも図７ｂに例示されたような形式に限らず、ウェブ文書の内容を概念化できる所定の形式の文書構造であればいずれも本発明におけるＤＯＭ構造に含まれてもよい。
【００５０】
ＤＯＭクラスタリングは、このように各ウェブ文書に対して抽出したＤＯＭ構造が類似するウェブ文書を一つのクラスタとして生成してもよいが、ここでＤＯＭ構造が類似するか否かを判断するためには、ＤＯＭ構造間に共通するノードが特定の数値、例えば、８０％以上である場合を類似したＤＯＭ構造を有するウェブ文書として判断してもよい。
【００５１】
本発明の一実施形態におけるクラスタリング手段１３１は、前記例示した様々なクラスタリング方法、またこれと異なる公知のクラスタリング方法のうちの一つ以上を任意の順序で組み合わせることにより類似文書が存在する可能性のあるクラスタを生成してもよく、例えば、ホストクラスタリングを行った後、シムハッシュクラスタリングによりクラスタを生成したり、ホストクラスタリング、ＤＯＭクラスタリング、及びサイズクラスタリングによりクラスタを生成してもよく、様々な応用が可能である。
【００５２】
本発明の一実施形態におけるクラスタリング手段１３１は、クラスタを生成した後、クラスタ内に属するウェブ文書の個数が特定の数値より小さい場合、その正確性のために当該クラスタを廃棄する機能をさらに行ってもよい。
【００５３】
次に、本発明の一実施形態におけるエンティティ抽出手段１３２は、クラスタリング手段１３１によって生成されたクラスタに含まれるウェブ文書からエンティティを抽出し、加重値計算手段１３３で各エンティティがウェブ文書中で核心となる部分であるか否かに基づいて計算された加重値を用いるように各エンティティのハッシュ値、クラスタ内の全体ウェブ文書のうち当該エンティティが登場した回数あるいは頻度などの数値を含む各エンティティに対する重要度寄与要素を計算する機能を行う。
【００５４】
本発明におけるエンティティとは、類似文書の検出のために比較され得る、ウェブ文書を構成している特徴的な構成要素を含む広義の概念であって、基本的にウェブ文書からパーシングされて分離され得るテキストを含んでもよく、その他にもウェブ文書中のタグ（ｔａｇ）のうち類似文書の検出のために用いられるアンカー（ａｎｃｈｏｒ）、エンベッド（ｅｍｂｅｄ）、イメージ（ｉｍｇ）タグなどに含まれる値をさらに含んでもよいが、必ずしもこれに限定されるものではない。抽出された各エンティティは、類似文書であるか否かを判断する際に寄与してもよく、すなわち核心となる部分であるか否かに基づく加重値がともに計算されてもよく、加重値は、上述したように、各エンティティに対する重要度寄与要素に基づいて計算される。ウェブ文書中のエンティティを抽出するためにエンティティ抽出手段１３２は、ウェブ文書から抽出されたＤＯＭ構造に基づき、このうちテキスト、アンカー、エンベッド、及びイメージタグが含まれたノード（ｎｏｄｅ）を抽出してウェブ文書のエンティティとして用いてもよい。特に、テキストの場合には、ウェブ文書のどの位置で登場するかによって、同一の文書でも類似文書であるか否かに大きな影響を及ぼす可能性のある、すなわち核心となる部分に該当し得るため、テキストが登場した位置または属性を示す値をさらに含んでもよく、例えば、テキストノードの上位ノード（例えば、ＤＩＶノードなど）に存在するＩＤ値を当該テキストのＩＤ値として当該テキストと結合してエンティティとして使用してもよく、また、テキストの場合、これを空白スペース単位で分けて、そのそれぞれをエンティティとして処理してもよい。その他にアンカーの場合、エンベッドノードとイメージノードは、タグ内に含まれるｓｒｃ属性値をそのエンティティとして用いてもよい。
【００５５】
例えば、一つのウェブ文書のソースコードが図８ａとおりであると仮定した場合、本発明の一実施形態におけるエンティティ抽出手段１３２によって抽出され得るエンティティは、図８ｂの左側のようにイメージノードに含まれるｓｒｃ属性から１個、またテキストノードに含まれるテキストを空白スペース単位で分けて、それぞれに属性を示すＩＤ値を結合した３個を含む合計４個に該当する。エンティティ抽出手段１３２は、抽出された各エンティティに対してハッシュ値をさらに求めてもよく、図８ｂの左側に抽出された４個のエンティティに対するハッシュ値は、図８ｂの右側に示されてもよい。
【００５６】
また、本発明の一実施形態におけるエンティティ抽出手段１３２は、前記例のように、一つのウェブ文書で同一のエンティティが複数個存在する場合、重複するエンティティを除去して一つのウェブ文書で重複するエンティティが存在しないようにする方式により同一のクラスタに含まれた各ウェブ文書から全体エンティティを抽出し、これに基づいて各エンティティがクラスタ内の全体ウェブ文書のうち何個のウェブ文書に重複して登場したのかその重複回数もさらに計算する。前記図８の例に続いて、クラスタ内にウェブ文書が合計１０個存在し、このうち図８ｂの左側に該当する各エンティティが重複するウェブ文書の回数を計算した結果を図８ｃのように示してもよい。
【００５７】
次に、本発明の一実施形態における加重値計算手段１３３は、前記エンティティ抽出手段１３２から抽出された各エンティティ、及び重要度寄与要素に基づいて各エンティティごとの加重値を計算する機能を行う。通常、所定ウェブ文書で重要度の高い、すなわち核心となる部分であるほどクラスタ内の複数のウェブ文書で重複する回数が少なく、ウェブ文書でよく用いられる基本形式であるテンプレート（ｔｅｍｐｌａｔｅ）として用いられるワードやリンクなどの場合、すなわちその重要度が低く核心とならない部分であるほどクラスタ内の複数のウェブ文書で重複する回数が多いという点に注目した文献出現頻度の逆数（ＩＤＦ；Ｉｎｖｅｒｔｅｄ Ｄｏｃｕｍｅｎｔ Ｆｒｅｑｕｅｎｃｙ）を用いることにより、クラスタ内のウェブ文書に多数重複して登場するエンティティの場合、その重要度が低く核心となる部分ではないと判断して加重値を低く与え、クラスタ内のウェブ文書に重複する回数が少ないほどその重要度が高く核心となる部分であると判断し、エンティティの加重値を高く与えるという概念を適用して抽出された各エンティティごとの加重値を計算する。
【００５８】
各エンティティごとの加重値を計算する際に用いられる計算式は、前記概念に基づく様々な式を適用してもよく、例えば、図９ａに示されたグラフが挙げられる。図９ａのグラフにおいて、横軸は重要度寄与要素のうちエンティティの重複頻度（クラスタ内の全体ウェブ文書のうち当該エンティティが登場したウェブ文書の割合）を示し、縦軸はエンティティの加重値を示し、エンティティの重複頻度が１に近いほど、すなわちエンティティがクラスタ内のウェブ文書で重複する回数が多いほど、エンティティの加重値は０に近くなって類似文書を検出する際に当該エンティティの影響が少なくなるため、当該エンティティは核心となる部分に該当しないと認められ、エンティティの重複頻度が０に近いほど、すなわちエンティティがクラスタ内のウェブ文書で重複する回数が少ないほど、エンティティの加重値は１に近くなって類似文書を検出する際に当該エンティティの影響が大きくなるため、当該エンティティは核心となる部分に該当すると認められることが分かる。前記図８ｃで抽出された４個のエンティティに対して図９ａのグラフを用いてその加重値を求めた結果は図９ｂの表のように示すことができる。
【００５９】
最後に、本発明の一実施形態における類似文書検出手段１３４は、加重値計算手段１３３によって計算された各エンティティごとの加重値を適用して、クラスタ内の各ウェブ文書に対して加重値が与えられた特性指数を計算し、これに基づいて類似文書を検出する機能を行う。ここで特性指数とは、一つのウェブ文書を他のウェブ文書と区分するために用いることができる所定の数値または文字列などを含む広い意味で解釈されなければならないが、以下では説明の便宜上、特性指数をその一例であるシムハッシュであると仮定して説明する。但し、特性指数をシムハッシュに限定して解釈してはならず、一つのウェブ文書を他のウェブ文書と区分するために用いられるものであればいずれも本発明における特性指数に該当し得る。
【００６０】
特性指数の一例であるシムハッシュを計算するために、類似文書検出手段１３４は、クラスタ内の各ウェブ文書からエンティティを抽出し、抽出されたエンティティに対するハッシュ値を計算する。シムハッシュ計算に用いることができる各ウェブ文書ごとのエンティティ及びこれに対するハッシュ値は、エンティティ抽出手段１３２から抽出された値をそのまま用いてもよい。次に、類似文書検出手段１３４は、各エンティティに対するハッシュ値を二進数で表現した後、ビット単位で加重値計算手段１３３によって計算された加重値を適用し、ビット単位で計算した最終のハッシュ値を計算してこれを当該ウェブ文書のシムハッシュとして用いてもよい。ビット単位を計算する際に特定の位置のビット値が１である場合には１に、０である場合には−１に変換した後、ビット別に各エンティティの加重値を乗じた値で再度演算し、全体エンティティに対してビット単位の演算を行いビット単位の最終値が正数である場合には１に、負数である場合には０に再変換する方式によりシムハッシュを抽出してもよい。例えば、上述した図６の例と類似して、一つのウェブ文書が合計３個のエンティティに分離され、各エンティティに対するハッシュ値を二進数で表現した内容がそれぞれ１１０００１０１、０１１０１１１０、１００１００１０であり、各エンティティに対する加重値が順に０．３、０．７、０．２である場合、当該ウェブ文書のエンティティは、図１０に示されたように、各エンティティのハッシュ値でビット単位別に計算するために各ビット別に並べて各エンティティの加重値である０．３、０．７、０．２を適用すると、１１０００１０１は、０．３、０．３、−０．３、−０．３、−０．３、０．３、−０．３、０．３に、０１１０１１１０は、−０．７、０．７、０．７、−０．７、０．７、０．７、０．７、−０．７に、また、１００１００１０は、０．２、−０．２、−０．２、０．２、−０．２、−０．２、０．２、−０．２に並べられ、全体エンティティをビット単位別に計算すると、その結果は、−０．２、０．８、０．２、−０．８、０．２、０．８、０．６、−０．６に該当するため、これからシムハッシュ０１１０１１１０を抽出してもよい。このように各エンティティのハッシュ値に加重値を適用する場合、各エンティティのウェブ文書中の重要度に応じて同一のエンティティのハッシュ値を有するウェブ文書でも互いに異なるシムハッシュが計算されてもよい。
【００６１】
このようにクラスタリング内の各ウェブ文書に対して加重値が適用された特性指数が計算された後、本発明の一実施形態における類似文書検出手段１３４は、特性指数に基づいて類似文書であるか否かを検出してもよいが、ここで類似文書であるか否かの検出に用いることができる方法の一例として、特性指数がシムハッシュである場合、計算されたシムハッシュ間のハミング距離が所定数値以下、例えばシムハッシュが８ビットであると仮定した場合には１である場合を類似文書と判断してもよい。
【００６２】
また、本発明の一実施形態における類似文書検出手段１３４は、類似文書として判断された重複するウェブ文書を検索データベース１４０から削除する機能をさらに含んでもよい。一方、類似文書検出手段１３４による検出結果、一つのクラスタ内における類似文書の割合が所定の数値、例えば５０％以上に該当したり、類似文書が所定の個数、例えば１００個以上存在したりする場合、類似文書検出手段１３４は、当該クラスタの生成方式及び各エンティティに対する加重値、また類似文書と判定されたウェブ文書の全ての加重値が適用された特性指数などを保存した後、その後クラスタリング手段１３１によって当該クラスタに属するウェブ文書が存在する場合、保存された各エンティティ及びその加重値を当該ウェブ文書に適用して特性指数を計算し、ハミング距離などの類似文書の判断に必要な別の数値を計算することなく当該クラスタに一致する特性指数がある場合すぐに当該ウェブ文書もまた類似文書であると判断して、類似文書検出速度を向上させてもよい。この場合、当該ウェブ文書のエンティティのうち予め保存されなかったエンティティが存在する場合には予め決定された所定の加重値、例えば０．５を適用して特性指数を計算してもよい。
【００６３】
次に、図５を参照して、本発明の一実施形態における改善された類似文書検出方法について説明する。
【００６４】
本発明の一実施形態によると、ユーザは、自分のユーザ端末装置３００を用いて問い合わせ言語を検索結果提供装置１００に伝送してもよく、検索結果提供装置１００は、受信した問い合わせ言語に基づいて検索データベース１４０を参照して検索を行った後、その結果として出力される検索結果をユーザ端末装置３００に伝送してもよい。但し、検索結果提供装置１００は、前記した通常の動作の他にも、収集部１２０を介して収集したウェブ文書のうち類似文書を検出するために類似文書が存在する可能性のあるクラスタを生成し、生成されたクラスタに属するそれぞれのウェブ文書に対してエンティティ、及びエンティティに対する重要度寄与要素を抽出して、各エンティティに対する加重値を計算し、計算された加重値を用いてクラスタ内の各ウェブ文書に対して加重値が適用された特性指数を計算した後、計算された各ウェブ文書の特性指数を比較して類似文書であるか否かを検出する。また、検出された類似文書結果に基づいて検索データベース１４０または別のデータベースに保存された、収集されたウェブ文書から重複するウェブ文書を削除する機能を行ってもよく、図５は、このような作業の各ステップをフローチャートとして表現した図である。
【００６５】
図５を参照すると、検索結果提供装置１００（または、その内部の類似文書検出部１３０のうちクラスタリング手段１３１）は、検索データベースに保存されたウェブ文書から類似文書が存在する可能性のあるクラスタを生成する（ステップＳ５１０）。上述した具体的な実施形態のように、クラスタ生成に適用され得る方法は、ホストクラスタリング、パスクラスタリング、クエリクラスタリング、サイズクラスタリング、シムハッシュクラスタリング、ＤＯＭクラスタリングまたは他の公知のクラスタリング方式のうちいずれか一つ以上を任意の順序で組み合わせることにより適用してもよい。
【００６６】
その後、類似文書検出部１３０のエンティティ抽出手段１３２は、クラスタリング手段１３１で生成されたクラスタ内のウェブ文書からエンティティ、及びエンティティの重要度寄与要素を抽出する機能を行ってもよい（ステップＳ５２０）。上述したように、エンティティは、ウェブ文書からパーシングされて分離され得るテキストを含んでもよく、その他にもアンカーに含まれるｈｒｅｆ属性やエンベッド、イメージタグなどに含まれるｓｒｃ属性値などをさらに含んでもよい。また、重要度寄与要素には各エンティティのハッシュ値の他にも各エンティティがクラスタ内の全体ウェブ文書のうち何個のウェブ文書に重複するかに対する回数あるいは頻度などの数値が含まれてもよい。
【００６７】
その後、類似文書検出部１３０の加重値計算手段１３３は、エンティティ抽出手段１３２から抽出された内容に基づいてクラスタ内の各エンティティに対する加重値を計算する機能を行ってもよい（ステップＳ５３０）。各エンティティに対する加重値は、当該エンティティがウェブ文書中で核心となる部分に該当するか否かに基づいて計算されてもよく、その具体的な一例として、文献出現頻度の逆数（ＩＤＦ）を用いてクラスタ内のウェブ文書に重複する回数が多いほどその加重値が増加し、クラスタ内のウェブ文書に重複する回数が少ないほどその加重値が減少する概念に基づく様々な式を適用して計算されてもよい。
【００６８】
その後、類似文書検出部１３０の類似文書検出手段１３４は、加重値計算手段１３３で計算された、クラスタ内のウェブ文書から抽出された各エンティティに対して加重値を適用したウェブ文書の特性指数を計算し、計算された各ウェブ文書の特性指数同士を比較して（例えば、特性指数がシムハッシュである場合、シムハッシュ間のハミング距離が特定数値以下であるか否かなどを計算して）類似文書であるか否かを検出する機能を行ってもよい（ステップＳ５４０）。また、類似文書検出手段１３４は、類似文書として検出された重複するウェブ文書を検索データベース１４０から削除する機能をさらに含んでもよい。
【００６９】
本発明による実施形態は、多様なコンピュータ手段によって行われるプログラム命令語の形態で実現され、コンピュータ読み取り可能な媒体に記録されてもよい。コンピュータ読み取り可能な媒体は、プログラム命令語、データファイル、データ構造などを単独で、または組み合わせて含んでもよい。前記媒体に記録されるプログラム命令語は、本発明のために特に設計及び構成されたものであってもよく、コンピュータソフトウェア分野の当業者に公知であって使用可能なものであってもよい。コンピュータ読み取り可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク及び磁気テープのような磁気媒体（ｍａｇｎｅｔｉｃ ｍｅｄｉａ）、ＣＤ−ＲＯＭ、ＤＶＤなどのような光記録媒体（ｏｐｔｉｃａｌ ｍｅｄｉａ）、フロプティカルディスク（ｆｌｏｐｔｉｃａｌ ｄｉｓｋ）のような磁気−光媒体（ｍａｇｎｅｔｏ−ｏｐｔｉｃａｌ ｍｅｄｉａ）及びＲＯＭ、ＲＡＭ、フラッシュメモリなどのような、プログラム命令語を保存及び実行するように特に構成されたハードウェア装置が含まれる。プログラム命令語の例としては、コンパイラによって作成されるような機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行することができる高級言語コードも含まれる。ハードウェア装置は、本発明における動作を行うために一つ以上のソフトウェアモジュールとして動作するように構成されてもよく、その逆も同様である。
【００７０】
以上、本発明を具体的な構成要素などのような特定の事項と限定された実施例及び図面を参照して説明したが、これは本発明のより全体的な理解を容易にするために提供されたものにすぎず、本発明は前記実施例によって限定されず、本発明が属する分野における通常の知識を有する者であれば、このような記載から多様な修正及び変形が可能である。
【００７１】
従って、本発明の思想は前記実施例に限定されて決まってはならず、添付する特許請求の範囲の記載だけでなく、特許請求の範囲の記載と均等または等価的に変形された全てのものは、本発明の思想の範疇に属すると理解するべきであろう。
【符号の説明】
【００７２】
１００ 検索結果提供装置
１３０ 類似文書検出部
１３１ クラスタリング手段
１３２ エンティティ抽出手段
１３３ 加重値計算手段
１３４ 類似文書検出手段
【技術分野】
【０００１】
本発明は、改善された類似文書検出方法、装置、及びコンピュータ読み取り可能な記録媒体に関し、より具体的には、収集されたウェブ文書のうち類似文書を検出する際に文書内で核心となる部分及び核心ではない部分を区別し、これにより互いに異なる加重値を与えて、類似文書を検出するためのより正確で改善された方法、装置及びコンピュータ読み取り可能な媒体に関する。
【背景技術】
【０００２】
最近、インターネットの使用が普及するにつれて、ユーザはインターネット検索を介して多様な情報を取得できるようになった。すなわち、ユーザはインターネットへのアクセスが可能なパソコンなどの端末装置を介してウェブブラウザのアドレスバーにＵＲＬのような識別子を入力することにより、インターネット検索サイトにアクセスして、自分が確認しようとする検索キーワードを入力して、ニュース、知識、ゲーム、コミュニティ、ウェブ文書などの多様な分野に係わる検索結果を見ることができるようになった。
【０００３】
上述のように、ユーザが検索しようとする内容を適切に示すために、インターネット検索サイト提供者はウェブ文書などを収集し、収集されたウェブ文書などに索引（ｉｎｄｅｘ）を構成して、これに基づいて検索結果をユーザに提供する機能を有する検索エンジンを設計して構成することが一般的であり、その中でもインターネット上に存在するウェブ文書を組織的かつ自動化した方法で探索及び収集する機能を有するウェブクローラ（Ｗｅｂ Ｃｒａｗｌｅｒ）は大きな役割を果たしている。
【０００４】
このようなウェブクローラの動作方式の一つとして、シード（ｓｅｅｄ）と呼ばれるＵＲＬリストから始めて、シードに含まれる全てのハイパーリンク（Ｈｙｐｅｒｌｉｎｋ）を認識してＵＲＬリストを更新（ｕｐｄａｔｅ）し、更新されたＵＲＬリストに該当するウェブ文書を再帰的に再び訪問する方式が用いられている。
【０００５】
しかし、一般的に収集対象となるウェブ文書の中には、その内容が大同小異であり、強いて別個に収集する必要性のないものが多いにもかかわらず、基本的なウェブクローラの動作方式に従ってウェブ文書の検索及び収集を行う場合には、ＵＲＬリストに含まれる全てのウェブ文書を訪問及び収集することになり、収集されたウェブ文書を保存する保存領域の問題、及び、これによる検索エンジンの性能及び効率性の低下などの様々な問題が現れた。
【０００６】
そこで、このような問題を解決するために、従来は、類似文書の検出技術を導入し、類似したウェブ文書が検出された場合、収集された重複する類似文書を保存領域から削除したり、当該文書が発見された経路（ｐａｔｈ）の収集速度を減少させたりするなどの作業を行っていた。
【０００７】
しかし、従来の類似文書検出技術の場合、同一または類似する領域の大きさに応じて類似文書であるか否かを検出するため、ウェブ文書におけるほとんどの領域が同一であっても核心となる部分が相違すれば、実際には類似文書ではないにもかかわらず、同一の部分が多いということにより一律に類似文書であると判断されるため、正常な文書の収集作業が妨害されることになり、その結果、検索精度が低下するという問題が存在する。
【０００８】
図１ａ及び図１ｂは、従来技術における類似文書検出技術によって類似文書と認められる場合の例を例示的に示した図である。図１を参照して、従来技術における類似文書検出技術の問題点について説明する。
【０００９】
図１ａ及び図１ｂに示された一例は、ウェブクローラによって収集される互いに異なるＵＲＬを有するそれぞれのウェブ文書を示す。ウェブ文書において核心となる部分である商品名、商品コードなど（図１ａのＡ領域及び図１ｂのＡ´領域）は相違しているが、相違する領域がウェブ文書全体のうちの小さな領域のみを占めており、メニュー、オプション、商品の詳細情報など多くの領域（図１ａ及び図１ｂにおけるＢ領域、Ｃ領域など）において同一の部分が存在するため、従来の類似文書の検出技術では、同一の領域がどれほど多いかに応じて類似文書であるか否かを判断する。しかし、当該ページにおいて最も核心的な部分である商品名や商品コードが相違する、すなわち、相違する商品に対する相違するウェブ文書であるため、類似文書であるとは認められないにもかかわらず、従来技術によると類似文書であると判断され、このうち一方が保存領域から削除されるため、検索エンジンのユーザに提供されなくなり、検索精度低下の問題が生じる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】韓国公開特許第１９９９―００８８６７８号公報
【特許文献２】韓国公開特許第１９９９―００４８７１４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、前記の従来技術の問題点を解決することを目的とする。
【００１２】
また、本発明は、類似文書である可能性のあるウェブ文書において、ウェブ文書中の核心となる部分と核心ではない部分とを区別し、これにより互いに異なる加重値を与えることにより、より改善された方式で類似文書を判別して検索エンジンの精度を向上させることを他の目的とする。
【００１３】
また、本発明は、類似文書検出結果に応じて、重複する類似文書をウェブ文書保存領域から削除して保存領域の無駄使いを防ぎ、これにより検索エンジンの性能を向上させることをさらに他の目的とする。
【課題を解決するための手段】
【００１４】
前記のような本発明の目的を達成して、後述する本発明に特有の効果を奏するための本発明の特徴的な構成は以下のとおりである。
【００１５】
本発明の一実施形態によると、改善された類似文書検出方法において、類似文書検出装置で行われる各ステップは、複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティを抽出し、算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算し、算出された加重値に基づいて複数のウェブ文書が類似文書であるか否かを検出すること、を含む。
【００１６】
本発明の他の実施形態によると、改善された類似文書検出装置は、複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティ抽出手段と、算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算する加重値計算手段と、算出された加重値に基づいて複数のウェブ文書が類似文書であるか否かを検出する類似文書検出手段と、を含む。
【発明の効果】
【００１７】
前記のように本発明によると、類似文書である可能性のある文書において、文書中の核心となる部分と核心ではない部分とを区別し、これにより互いに異なる加重値を与えることにより、より改善された方式で類似文書を判別して検索エンジンの精度を向上させることができる。
【００１８】
また、本発明によると、類似文書検出結果に応じて、重複する類似文書をウェブ文書保存領域から削除して保存領域の無駄使いを防ぎ、これによる検索エンジンの性能を向上させることができる。
【図面の簡単な説明】
【００１９】
【図１ａ】従来技術における類似文書検出技術により類似文書であると判断される場合の例を例示的に示した図である。
【図１ｂ】従来技術における類似文書検出技術により類似文書であると判断される場合の例を例示的に示した図である。
【図２】本発明の一実施形態における検索結果提供装置を含む全体システムを概略的に示した図である。
【図３】本発明の一実施形態における検索結果提供装置の詳細な構成を示した図である。
【図４】本発明の一実施形態における類似文書検出部の詳細な構成を示した図である。
【図５】本発明の一実施形態における類似文書検出方法を説明するためのフローチャートである。
【図６】本発明の一実施形態において、ウェブ文書のシムハッシュを計算する方式を説明するための図である。
【図７ａ】本発明の一実施形態におけるウェブ文書のＤＯＭ構造を抽出する方式を説明するための図である。
【図７ｂ】本発明の一実施形態におけるウェブ文書のＤＯＭ構造を抽出する方式を説明するための図である。
【図８ａ】本発明の一実施形態におけるウェブ文書のエンティティ及びその関連値の抽出を説明するための図である。
【図８ｂ】本発明の一実施形態におけるウェブ文書のエンティティ及びその関連値の抽出を説明するための図である。
【図８ｃ】本発明の一実施形態におけるウェブ文書のエンティティ及びその関連値の抽出を説明するための図である。
【図９ａ】本発明の一実施形態におけるエンティティごとの加重値計算を説明するための図である。
【図９ｂ】本発明の一実施形態におけるエンティティごとの加重値計算を説明するための図である。
【図１０】本発明の一実施形態において加重値が適用されたシムハッシュを計算する方式を説明するための図である。
【発明を実施するための形態】
【００２０】
後述する本発明の詳細な説明において、本発明を実施することができる特定の実施形態を例として示す添付の図面を参照する。これらの実施例は、当業者が本発明を十分に実施することができるように詳細に説明される。本発明の多様な実施例は互いに異なるが相互に排他的である必要はないということが理解されるべきである。例えば、本明細書に記載されている特定の形状、構造及び特性は、一実施例にすぎず、本発明の思想及び範囲を外れない限り他の実施例において実現されてもよい。また、開示された各実施例中の個別の構成要素の位置または配置は、本発明の思想及び範囲を外れない限り変更されてもよいということが理解されるべきである。従って、後述する詳細な説明は、限定的な意味に制限するものではない。本発明の範囲は、適切に説明されれば、その特許請求の範囲に記載されたものと均等な全ての範囲とともに添付の特許請求の範囲の記載によってのみ限定される。図面において類似する参照符号は様々な側面に亘って同一または類似する機能を指称する。
【００２１】
以下、本発明が属する技術分野における通常の知識を有する者が本発明を容易に実施することができるように、本発明の好ましい実施例について添付の図面を参照して詳細に説明する。
【００２２】
本発明の実施形態における「ウェブ文書」という用語は、インターネットエクスプローラなどのウェブブラウザプログラムを用いて読み込み可能な受動的または能動的な文書形式を全て含む広い意味で解釈されなければならず、ウェブ文書の文書形式として、主にＨＴＭＬ（ＨｙｐｅｒＴｅｘｔ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）が用いられるが、必ずしもこれに限定されず、ＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）、ＳＧＭＬ（Ｓｔａｎｄａｒｄ Ｇｅｎｅｒａｌｉｚｅｄ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）を含み、ウェブブラウザプログラムを用いて読み込み可能な文書形式であれば全てウェブ文書に該当する。ウェブブラウザプログラムを用いてウェブ文書を読み込むためには、一般的にウェブ文書が位置するアドレスをＵＲＬとして入力し、そのアドレス形式としてＨＴＴＰ（ＨｙｐｅｒＴｅｘｔ Ｔｒａｎｓｆｅｒ Ｐｒｏｔｏｃｏｌ）が多く用いられるが、必ずしもこれに限定されるものではない。
【００２３】
一方、本発明の実施形態における「ＵＲＬ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｌｏｃａｔｏｒ）」という用語は、ウェブ上でサービスを提供する各サーバに存在するファイルの位置を明示するためのものであって、アクセスすべきサービスの種類、サーバの位置（ドメインネーム）、ファイルの位置を含む。ＵＲＬの一般的な体系（ｓｙｎｔａｘ）は、「プロトコル：／／ホスト名／経路（ｐａｔｈ）／ファイル名？パラメータ」のような形式で構成されてもよい。ここで経路は、複数の経路を含んでもよく、パラメータも複数のパラメータを含んでもよい。例えば、ｈｔｔｐ：／／ｗｗｗ．ｘｘｘ．ｃｏｍ／ａ／ｂ／ｃ．ｈｔｍｌ？ｘ＝１＆ｙ＝２のようなＵＲＬにおいて、プロトコルはｈｔｔｐであり、ホスト名はｗｗｗ．ｘｘｘ．ｃｏｍであり、経路は／ａ／ｂ／であり、ファイル名はｃ．ｈｔｍｌであり、パラメータはｘ及びｙの２つであって、その値はそれぞれ１及び２である。
【００２４】
一方、本発明の実施形態における「類似文書」という用語は、その内容が同一であるかその内容の核心を含むほとんどが同一である複数のウェブ文書を示す広い意味で用いられる。検索エンジンの効率性を考慮して、類似文書を検出する際に基本となるウェブ文書以外のこれと重複する類似文書は、収集された保存領域から削除されて検索エンジンにより検索されないようにする。
【００２５】
［装置の全体構成］
図２は、本発明の一実施形態において検出された重複する類似文書を削除した検索データベースを用いた検索結果提供装置を含む全体装置を概略的に示した図である。
【００２６】
図２に示されているように、本発明の一実施形態における全体装置は、検索データベースを有する検索結果提供装置１００が通信網２００を介して複数のユーザ端末装置３００及び複数のウェブ文書サーバ４００に接続されてもよい。
【００２７】
まず、本発明の一実施形態によると、検索結果提供装置１００は、ユーザ端末装置３００から探索キーワード、すなわち、問い合わせ言語を受信し、これに基づいて検索を行った後、その結果として出力される検索結果をユーザ端末装置３００に伝送する機能を行う。また、検索結果提供装置１００は、収集部１２０（図３参照）を用いて一つ以上のウェブ文書サーバ４００から収集したウェブ文書において類似文書が存在する可能性のあるクラスタを生成し、生成されたクラスタから類似文書であるか否かを検出して、検出結果検索データベースに類似文書が保存された場合には、重複する類似文書を削除する機能を行ってもよい。
【００２８】
また、本発明の一実施形態によると、通信網２００は、有線・無線などのような通信状態を問わずに構成されてもよく、パーソナルエリアネットワーク（ＰＡＮ；Ｐｅｒｓｏｎａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ローカルエリアネットワーク（ＬＡＮ；Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、メトロポリタンエリアネットワーク（ＭＡＮ；Ｍｅｔｒｏｐｏｌｉｔａｎ Ａｒｅａ Ｎｅｔｗｏｒｋ）、広域ネットワーク（ＷＡＮ；Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）など、多様な通信網で構成されてもよい。
【００２９】
一方、本発明の一実施形態におけるユーザ端末装置３００は、ユーザが所定の問い合わせ言語に対する検索結果を提供されるように、通信網２００を介して検索結果提供装置１００に接続するための機能を含む入出力装置を意味し、デスクトップパソコンだけでなく、ノートパソコン、ワークステーション、パームトップ（ｐａｌｍｔｏｐ）パソコン、個人携帯情報端末（ｐｅｒｓｏｎａｌ ｄｉｇｉｔａｌ ａｓｓｉｓｔａｎｔ；ＰＤＡ）、ウェブパッド、スマートフォンを含む移動通信端末などのようにメモリ手段を備え、マイクロプロセッサを搭載して演算能力を備えたデジタル機器であればいずれも本発明におけるユーザ端末装置３００として採用され得る。好ましくは、ユーザ端末装置３００は、検索結果提供装置１００に接続し、問い合わせ言語を入力して検索結果を提供されるために、ユーザ端末装置３００内のウェブブラウザを実行して用いられてもよいが、必ずしもこれに限定されるものではない。
【００３０】
一方、本発明の一実施形態におけるウェブ文書サーバ４００は、検索結果提供装置１００内の収集部が収集するウェブ文書を含むウェブサーバの通称であり、物理的に特定のサーバや特定の内容／形式のウェブ文書に限定されるものではない。収集部が通信網２００を介してアクセスしてウェブ文書を収集することができるウェブサーバは全てウェブ文書サーバ４００に含まれると認められる。
【００３１】
［検索結果提供装置］
図３は、本発明の一実施形態における検索結果提供装置１００の詳細な構成図である。
【００３２】
図２を参照すると、本発明の一実施形態における検索結果提供装置１００は、検索部１１０、収集部１２０、類似文書検出部１３０、及び検索データベース１４０を含んでもよい。
【００３３】
検索部１１０は、ユーザ端末装置３００から受信した問い合わせ言語に対応する情報を検索データベース１４０から検索する。検索により抽出される検索結果はユーザ端末装置３００に伝送される。
【００３４】
収集部１２０は、ウェブ文書サーバ４００に保存されたウェブ文書をウェブクローラなどの公知の組織的な自動化された方法により検索及び収集して検索データベース１４０に保存する機能を行う。
【００３５】
類似文書検出部１３０は、収集部１２０を介して収集されるウェブ文書を多様な方法を用いて生成され得るクラスタに統合した後、ウェブ文書中のそれぞれのエンティティ（ｅｎｔｉｔｙ）がウェブ文書中の核心となる部分であるか否かに応じてその加重値を計算し、加重値を適用した類似文書を検出して類似文書が検出された場合、この結果を検索データベース１４０に保存されたウェブ文書に適用して重複して保存された類似したウェブ文書の削除を行うようにしてもよい。類似文書検出部１３０の各構成要素の詳細な機能については後述する。
【００３６】
検索データベース１４０は、検索結果を提供するために収集されたり保存されたりする各種情報を含んでもよく、その他にも収集部１２０が収集したウェブ文書を保存してもよい。また、類似文書検出部１３０の動作によって検索データベース１４０内に既に収集されたウェブ文書が重複して保存されている場合、その一部または全部が削除されてもよい。
【００３７】
図３には、検索データベース１４０のみを図示したが、本発明の一実施形態においいて収集部１２０が収集、検出したウェブ文書を保存するデータベースを別に構築し、そのうち類似文書検出部１３０によって検出された類似文書結果に基づいて重複するウェブ文書が削除された残りのみを検索データベース１４０に保存してもよい。また、図面において検索部１１０、収集部１２０、及び類似文書検出部１３０は、それぞれ別のブロックで示したが、これらは物理的に一つの装置において実現されてもよく、これらの一部またはそれぞれが物理的に異なる装置において実現されてもよく、同一の機能を行う複数の装置に物理的に並列的に実現されてもよい。このように、本発明は、各構成部分が設けられた機械またはデータベースの物理的な個数及び配置に限定されず、様々な方式によって設計、変更されてもよいことは、本発明の属する技術分野における通常の知識を有する者にとって自明である。
【００３８】
［類似文書検出部］
図４を参照して、本発明の一実施形態における検索結果提供装置１００の類似文書検出部１３０についてより詳細に説明すると、類似文書検出部１３０は、クラスタリング（ｃｌｕｓｔｅｒｉｎｇ）手段１３１、エンティティ（ｅｎｔｉｔｙ）抽出手段１３２、加重値計算手段１３３、及び類似文書検出手段１３４を含んでもよい。
【００３９】
ここで、本発明の一実施形態におけるクラスタリング手段１３１は、検索データベース１４０または別のデータベースに保存されている収集部１２０によって収集されたウェブ文書の中に類似文書が存在する可能性のあるクラスタを所定の方法によって生成する機能を行ってもよい。
【００４０】
本発明の一実施形態におけるクラスタリング手段１３１がクラスタを生成するために適用できる所定の方法は、例えば、ホスト（Ｈｏｓｔ）クラスタリング、パス（Ｐａｔｈ）クラスタリング、クエリ（Ｑｕｅｒｙ）クラスタリング、サイズ（Ｓｉｚｅ）クラスタリング、シムハッシュ（ＳｉｍＨａｓｈ）クラスタリング、ＤＯＭ（Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ Ｍｏｄｅｌ）クラスタリングなどを含んでもよく、クラスタリング手段１３１は、例示されていない他の方法を用いてクラスタを生成してもよく、または例示されたクラスタリング方法及び例示されていない他の方法のうちのいずれか一つ以上を様々な順序で組み合わせて適用してもよく、類似文書が存在する可能性のあるクラスタを生成するために様々な方法を取捨選択してもよいということは当業者にとって自明であろう。
【００４１】
前記例示されたそれぞれのクラスタリング方法について詳述すると、まず、ホストクラスタリングは、ウェブ文書の出処であるＵＲＬのうちホスト名が一致するＵＲＬを有するウェブ文書を一つのクラスタとして生成する方式を意味する。例えば、一つのウェブ文書がｈｔｔｐ：／／ｗｗｗ．ｘｘｘ．ｃｏｍ／ａ／ｂ／ｃ．ｈｔｍｌ？ｘ＝１＆ｙ＝２というＵＲＬを有する場合、当該ウェブ文書をホストクラスタリングにより一つのクラスタを生成すると、当該ウェブ文書のホスト名であるｗｗｗ．ｘｘｘ．ｃｏｍと一致するウェブ文書を一つのクラスタとして生成する。
【００４２】
次に、パスクラスタリングは、ウェブ文書の出処であるＵＲＬのうちホスト名とその経路まで一致するＵＲＬを有するウェブ文書を一つのクラスタとして生成する方式を意味する。前記例において、ホスト名とその経路であるｗｗｗ．ｘｘｘ．ｃｏｍ／ａ／ｂ／まで一致するウェブ文書を一つのクラスタとして生成する場合、これをパスクラスタリングという。
【００４３】
また、クエリクラスタリングは、ウェブ文書の出処であるＵＲＬのうちホスト名、経路、及びファイル名まで一致するか、またはファイル名に加えてパラメータまで一致するＵＲＬを有するウェブ文書を一つのクラスタとして生成する方式を意味する。前記例に続いて、ホスト名と経路、及びファイル名まで含むｗｗｗ．ｘｘｘ．ｃｏｍ／ａ／ｂ／ｃ．ｈｔｍｌが一致するＵＲＬを有するウェブ文書を一つのクラスタとして生成するか、またはこれに加えてパラメータまで一致する、すなわちパラメータとしてｘ及びｙを含むＵＲＬを有するウェブ文書を一つのクラスタとして生成する場合、これをクエリクラスタリングと呼ぶ。
【００４４】
前記ホストクラスタリング、パスクラスタリング及びクエリクラスタリングは、全てウェブ文書の出処であるＵＲＬに基づくクラスタ生成方法であって、一つのクラスタに含まれるウェブ文書の個数に基づき、一つ以上の最も適したクラスタリング方式が選択されてもよい。
【００４５】
次に、サイズクラスタリングは、ウェブ文書の大きさ（ｓｉｚｅ）に基づいて類似の大きさを有するウェブ文書を一つのクラスタとして生成する方式を意味する。例えば、ウェブ文書の大きさが１６００ｂｙｔｅから１６１５ｂｙｔｅに該当する場合に、一つのクラスタとして生成すると定義されている場合、その大きさが１６００ｂｙｔｅ、１６０８ｂｙｔｅ、１６１２ｂｙｔｅであるウェブ文書は、サイズクラスタリングによって全て一つのクラスタとして生成される。
【００４６】
一方、シムハッシュ（ＳｉｍＨａｓｈ）クラスタリングは、各ウェブ文書別に抽出され得るシムハッシュ値が類似するウェブ文書を一つのクラスタとして生成する方式を意味する。シムハッシュとは、Ｓｉｍｉｌａｒｉｔｙ Ｈａｓｈ基盤の技術であって、互いに異なるキーの値が入力された場合、互いに異なるハッシュ値を与える一般的なハッシング機能を維持すると共に、類似するキーの値が入力された場合、類似したハッシュ値を有するハッシュ関数を意味し、このようなシムハッシュ抽出方式を例にとって以下で説明する。
【００４７】
一つのウェブ文書は、ワード単位でパーシングされて分離されてもよく、分離されたそれぞれのワードは、所定のハッシングアルゴリズムを適用したハッシュ関数を用いて特定のハッシュ値に計算されてもよく、計算された特定のハッシュ値は二進数で表現されてもよい。ハッシュ関数に用いることができるハッシングアルゴリズムは、標準アルゴリズムであるＳＨＡ−１、ＨＡＳ−１６０などの既に公知されたアルゴリズムを含み、特定のキーに対する唯一の値を提供するハッシュ関数の機能を有するアルゴリズムであれば、本発明の一実施形態におけるシムハッシュクラスタリングに用いることができるということは当業者にとって自明である。シムハッシュ抽出方式により抽出されるシムハッシュは、このように一つのウェブ文書から分離された各ワード別に抽出されたハッシュ値をビット単位で計算した最終のハッシュ値を意味する。ビット単位で計算する際に特定の位置のビット値が１である場合は１に、０である場合は−１に変換した後、ハッシュ値別にビット単位の演算を行ってビット単位の最終値が正数である場合は１に、負数である場合は０に、再度変換する方式によりウェブ文書のシムハッシュを抽出してもよい。例えば、一つのウェブ文書をワード単位でパーシングした結果、合計３個のワードに分離され、各ワードに対するハッシュ値を二進数で表現した内容がそれぞれ１１０００１０１，０１１０１１１０、及び１００１００１０である場合、当該ウェブ文書のシムハッシュは、図６に示されるように、各ワードのハッシュ値でビット単位別に計算するために、１１０００１０１は、１，１，−１，−１，−１，１，−１，１に、０１１０１１１０は、−１，１、１，−１，１、１，１，−１に、また１００１００１０は、１，−１，−１，１，−１，−１，１，−１に変換された後、ハッシュ値別にビット単位の計算結果である１，１，−１，−１，−１，１、１，−１からハッシュ値をさらに変換すると、シムハッシュ１１０００１１０を抽出することができる。このように抽出されたシムハッシュは、複数のウェブ文書においてほとんどの内容が同一であれば、一部の内容が異なっていてもウェブ文書別に類似したシムハッシュを有する。
【００４８】
シムハッシュクラスタリングは、このように各ウェブ文書に対して抽出されたシムハッシュが類似するウェブ文書を一つのクラスタとして生成してもよいが、ここでシムハッシュが類似するか否かを判断するためには、シムハッシュ間のハミング距離（ｈａｍｍｉｎｇ ｄｉｓｔａｎｃｅ）が所定数値以下、例えば、シムハッシュが８ビットであると仮定した場合には１である場合を類似したウェブ文書として判断してもよい。ハミング距離は、同一のビット数を有する二進数の間に対応するビット値が一致しない個数を意味し、例えば、シムハッシュが１１０００１０１であるウェブ文書とシムハッシュが１００１０１０１であるウェブ文書との間のハミング距離は、合計８個のビットのうち、２番目のビット及び４番目の対応ビットが一致しないため、２であり、上述したように、例示的な類似基準である１よりハミング距離が小さいため、二つのウェブ文書は類似しないと判断されてもよい。また他の例として、シムハッシュが１１０００１０１であるウェブ文書と１１０１０１０１であるウェブ文書との間のハミング距離は、合計８個のビットのうち４番目の対応ビットのみが一致しないため、１に該当し、従って、前記例示的な類似基準である１以下に対応するため、二つのウェブ文書は類似していると判断されてもよい。
【００４９】
また、ＤＯＭ（Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ Ｍｏｄｅｌ）クラスタリングは、各ウェブ文書別に抽出され得るＤＯＭ構造が類似したウェブ文書を一つのクラスタとして生成する方式を意味する。ＤＯＭ構造とは、所定のウェブ文書の内容を抽出して、ツリー型に概念化した文書構造ツリーの一例であって、ウェブ文書のソースコードが図７ａであると仮定した場合、当該ウェブ文書から図７ｂのような形式のＤＯＭ構造を抽出してもよいが、必ずしも図７ｂに例示されたような形式に限らず、ウェブ文書の内容を概念化できる所定の形式の文書構造であればいずれも本発明におけるＤＯＭ構造に含まれてもよい。
【００５０】
ＤＯＭクラスタリングは、このように各ウェブ文書に対して抽出したＤＯＭ構造が類似するウェブ文書を一つのクラスタとして生成してもよいが、ここでＤＯＭ構造が類似するか否かを判断するためには、ＤＯＭ構造間に共通するノードが特定の数値、例えば、８０％以上である場合を類似したＤＯＭ構造を有するウェブ文書として判断してもよい。
【００５１】
本発明の一実施形態におけるクラスタリング手段１３１は、前記例示した様々なクラスタリング方法、またこれと異なる公知のクラスタリング方法のうちの一つ以上を任意の順序で組み合わせることにより類似文書が存在する可能性のあるクラスタを生成してもよく、例えば、ホストクラスタリングを行った後、シムハッシュクラスタリングによりクラスタを生成したり、ホストクラスタリング、ＤＯＭクラスタリング、及びサイズクラスタリングによりクラスタを生成してもよく、様々な応用が可能である。
【００５２】
本発明の一実施形態におけるクラスタリング手段１３１は、クラスタを生成した後、クラスタ内に属するウェブ文書の個数が特定の数値より小さい場合、その正確性のために当該クラスタを廃棄する機能をさらに行ってもよい。
【００５３】
次に、本発明の一実施形態におけるエンティティ抽出手段１３２は、クラスタリング手段１３１によって生成されたクラスタに含まれるウェブ文書からエンティティを抽出し、加重値計算手段１３３で各エンティティがウェブ文書中で核心となる部分であるか否かに基づいて計算された加重値を用いるように各エンティティのハッシュ値、クラスタ内の全体ウェブ文書のうち当該エンティティが登場した回数あるいは頻度などの数値を含む各エンティティに対する重要度寄与要素を計算する機能を行う。
【００５４】
本発明におけるエンティティとは、類似文書の検出のために比較され得る、ウェブ文書を構成している特徴的な構成要素を含む広義の概念であって、基本的にウェブ文書からパーシングされて分離され得るテキストを含んでもよく、その他にもウェブ文書中のタグ（ｔａｇ）のうち類似文書の検出のために用いられるアンカー（ａｎｃｈｏｒ）、エンベッド（ｅｍｂｅｄ）、イメージ（ｉｍｇ）タグなどに含まれる値をさらに含んでもよいが、必ずしもこれに限定されるものではない。抽出された各エンティティは、類似文書であるか否かを判断する際に寄与してもよく、すなわち核心となる部分であるか否かに基づく加重値がともに計算されてもよく、加重値は、上述したように、各エンティティに対する重要度寄与要素に基づいて計算される。ウェブ文書中のエンティティを抽出するためにエンティティ抽出手段１３２は、ウェブ文書から抽出されたＤＯＭ構造に基づき、このうちテキスト、アンカー、エンベッド、及びイメージタグが含まれたノード（ｎｏｄｅ）を抽出してウェブ文書のエンティティとして用いてもよい。特に、テキストの場合には、ウェブ文書のどの位置で登場するかによって、同一の文書でも類似文書であるか否かに大きな影響を及ぼす可能性のある、すなわち核心となる部分に該当し得るため、テキストが登場した位置または属性を示す値をさらに含んでもよく、例えば、テキストノードの上位ノード（例えば、ＤＩＶノードなど）に存在するＩＤ値を当該テキストのＩＤ値として当該テキストと結合してエンティティとして使用してもよく、また、テキストの場合、これを空白スペース単位で分けて、そのそれぞれをエンティティとして処理してもよい。その他にアンカーの場合、エンベッドノードとイメージノードは、タグ内に含まれるｓｒｃ属性値をそのエンティティとして用いてもよい。
【００５５】
例えば、一つのウェブ文書のソースコードが図８ａとおりであると仮定した場合、本発明の一実施形態におけるエンティティ抽出手段１３２によって抽出され得るエンティティは、図８ｂの左側のようにイメージノードに含まれるｓｒｃ属性から１個、またテキストノードに含まれるテキストを空白スペース単位で分けて、それぞれに属性を示すＩＤ値を結合した３個を含む合計４個に該当する。エンティティ抽出手段１３２は、抽出された各エンティティに対してハッシュ値をさらに求めてもよく、図８ｂの左側に抽出された４個のエンティティに対するハッシュ値は、図８ｂの右側に示されてもよい。
【００５６】
また、本発明の一実施形態におけるエンティティ抽出手段１３２は、前記例のように、一つのウェブ文書で同一のエンティティが複数個存在する場合、重複するエンティティを除去して一つのウェブ文書で重複するエンティティが存在しないようにする方式により同一のクラスタに含まれた各ウェブ文書から全体エンティティを抽出し、これに基づいて各エンティティがクラスタ内の全体ウェブ文書のうち何個のウェブ文書に重複して登場したのかその重複回数もさらに計算する。前記図８の例に続いて、クラスタ内にウェブ文書が合計１０個存在し、このうち図８ｂの左側に該当する各エンティティが重複するウェブ文書の回数を計算した結果を図８ｃのように示してもよい。
【００５７】
次に、本発明の一実施形態における加重値計算手段１３３は、前記エンティティ抽出手段１３２から抽出された各エンティティ、及び重要度寄与要素に基づいて各エンティティごとの加重値を計算する機能を行う。通常、所定ウェブ文書で重要度の高い、すなわち核心となる部分であるほどクラスタ内の複数のウェブ文書で重複する回数が少なく、ウェブ文書でよく用いられる基本形式であるテンプレート（ｔｅｍｐｌａｔｅ）として用いられるワードやリンクなどの場合、すなわちその重要度が低く核心とならない部分であるほどクラスタ内の複数のウェブ文書で重複する回数が多いという点に注目した文献出現頻度の逆数（ＩＤＦ；Ｉｎｖｅｒｔｅｄ Ｄｏｃｕｍｅｎｔ Ｆｒｅｑｕｅｎｃｙ）を用いることにより、クラスタ内のウェブ文書に多数重複して登場するエンティティの場合、その重要度が低く核心となる部分ではないと判断して加重値を低く与え、クラスタ内のウェブ文書に重複する回数が少ないほどその重要度が高く核心となる部分であると判断し、エンティティの加重値を高く与えるという概念を適用して抽出された各エンティティごとの加重値を計算する。
【００５８】
各エンティティごとの加重値を計算する際に用いられる計算式は、前記概念に基づく様々な式を適用してもよく、例えば、図９ａに示されたグラフが挙げられる。図９ａのグラフにおいて、横軸は重要度寄与要素のうちエンティティの重複頻度（クラスタ内の全体ウェブ文書のうち当該エンティティが登場したウェブ文書の割合）を示し、縦軸はエンティティの加重値を示し、エンティティの重複頻度が１に近いほど、すなわちエンティティがクラスタ内のウェブ文書で重複する回数が多いほど、エンティティの加重値は０に近くなって類似文書を検出する際に当該エンティティの影響が少なくなるため、当該エンティティは核心となる部分に該当しないと認められ、エンティティの重複頻度が０に近いほど、すなわちエンティティがクラスタ内のウェブ文書で重複する回数が少ないほど、エンティティの加重値は１に近くなって類似文書を検出する際に当該エンティティの影響が大きくなるため、当該エンティティは核心となる部分に該当すると認められることが分かる。前記図８ｃで抽出された４個のエンティティに対して図９ａのグラフを用いてその加重値を求めた結果は図９ｂの表のように示すことができる。
【００５９】
最後に、本発明の一実施形態における類似文書検出手段１３４は、加重値計算手段１３３によって計算された各エンティティごとの加重値を適用して、クラスタ内の各ウェブ文書に対して加重値が与えられた特性指数を計算し、これに基づいて類似文書を検出する機能を行う。ここで特性指数とは、一つのウェブ文書を他のウェブ文書と区分するために用いることができる所定の数値または文字列などを含む広い意味で解釈されなければならないが、以下では説明の便宜上、特性指数をその一例であるシムハッシュであると仮定して説明する。但し、特性指数をシムハッシュに限定して解釈してはならず、一つのウェブ文書を他のウェブ文書と区分するために用いられるものであればいずれも本発明における特性指数に該当し得る。
【００６０】
特性指数の一例であるシムハッシュを計算するために、類似文書検出手段１３４は、クラスタ内の各ウェブ文書からエンティティを抽出し、抽出されたエンティティに対するハッシュ値を計算する。シムハッシュ計算に用いることができる各ウェブ文書ごとのエンティティ及びこれに対するハッシュ値は、エンティティ抽出手段１３２から抽出された値をそのまま用いてもよい。次に、類似文書検出手段１３４は、各エンティティに対するハッシュ値を二進数で表現した後、ビット単位で加重値計算手段１３３によって計算された加重値を適用し、ビット単位で計算した最終のハッシュ値を計算してこれを当該ウェブ文書のシムハッシュとして用いてもよい。ビット単位を計算する際に特定の位置のビット値が１である場合には１に、０である場合には−１に変換した後、ビット別に各エンティティの加重値を乗じた値で再度演算し、全体エンティティに対してビット単位の演算を行いビット単位の最終値が正数である場合には１に、負数である場合には０に再変換する方式によりシムハッシュを抽出してもよい。例えば、上述した図６の例と類似して、一つのウェブ文書が合計３個のエンティティに分離され、各エンティティに対するハッシュ値を二進数で表現した内容がそれぞれ１１０００１０１、０１１０１１１０、１００１００１０であり、各エンティティに対する加重値が順に０．３、０．７、０．２である場合、当該ウェブ文書のエンティティは、図１０に示されたように、各エンティティのハッシュ値でビット単位別に計算するために各ビット別に並べて各エンティティの加重値である０．３、０．７、０．２を適用すると、１１０００１０１は、０．３、０．３、−０．３、−０．３、−０．３、０．３、−０．３、０．３に、０１１０１１１０は、−０．７、０．７、０．７、−０．７、０．７、０．７、０．７、−０．７に、また、１００１００１０は、０．２、−０．２、−０．２、０．２、−０．２、−０．２、０．２、−０．２に並べられ、全体エンティティをビット単位別に計算すると、その結果は、−０．２、０．８、０．２、−０．８、０．２、０．８、０．６、−０．６に該当するため、これからシムハッシュ０１１０１１１０を抽出してもよい。このように各エンティティのハッシュ値に加重値を適用する場合、各エンティティのウェブ文書中の重要度に応じて同一のエンティティのハッシュ値を有するウェブ文書でも互いに異なるシムハッシュが計算されてもよい。
【００６１】
このようにクラスタリング内の各ウェブ文書に対して加重値が適用された特性指数が計算された後、本発明の一実施形態における類似文書検出手段１３４は、特性指数に基づいて類似文書であるか否かを検出してもよいが、ここで類似文書であるか否かの検出に用いることができる方法の一例として、特性指数がシムハッシュである場合、計算されたシムハッシュ間のハミング距離が所定数値以下、例えばシムハッシュが８ビットであると仮定した場合には１である場合を類似文書と判断してもよい。
【００６２】
また、本発明の一実施形態における類似文書検出手段１３４は、類似文書として判断された重複するウェブ文書を検索データベース１４０から削除する機能をさらに含んでもよい。一方、類似文書検出手段１３４による検出結果、一つのクラスタ内における類似文書の割合が所定の数値、例えば５０％以上に該当したり、類似文書が所定の個数、例えば１００個以上存在したりする場合、類似文書検出手段１３４は、当該クラスタの生成方式及び各エンティティに対する加重値、また類似文書と判定されたウェブ文書の全ての加重値が適用された特性指数などを保存した後、その後クラスタリング手段１３１によって当該クラスタに属するウェブ文書が存在する場合、保存された各エンティティ及びその加重値を当該ウェブ文書に適用して特性指数を計算し、ハミング距離などの類似文書の判断に必要な別の数値を計算することなく当該クラスタに一致する特性指数がある場合すぐに当該ウェブ文書もまた類似文書であると判断して、類似文書検出速度を向上させてもよい。この場合、当該ウェブ文書のエンティティのうち予め保存されなかったエンティティが存在する場合には予め決定された所定の加重値、例えば０．５を適用して特性指数を計算してもよい。
【００６３】
次に、図５を参照して、本発明の一実施形態における改善された類似文書検出方法について説明する。
【００６４】
本発明の一実施形態によると、ユーザは、自分のユーザ端末装置３００を用いて問い合わせ言語を検索結果提供装置１００に伝送してもよく、検索結果提供装置１００は、受信した問い合わせ言語に基づいて検索データベース１４０を参照して検索を行った後、その結果として出力される検索結果をユーザ端末装置３００に伝送してもよい。但し、検索結果提供装置１００は、前記した通常の動作の他にも、収集部１２０を介して収集したウェブ文書のうち類似文書を検出するために類似文書が存在する可能性のあるクラスタを生成し、生成されたクラスタに属するそれぞれのウェブ文書に対してエンティティ、及びエンティティに対する重要度寄与要素を抽出して、各エンティティに対する加重値を計算し、計算された加重値を用いてクラスタ内の各ウェブ文書に対して加重値が適用された特性指数を計算した後、計算された各ウェブ文書の特性指数を比較して類似文書であるか否かを検出する。また、検出された類似文書結果に基づいて検索データベース１４０または別のデータベースに保存された、収集されたウェブ文書から重複するウェブ文書を削除する機能を行ってもよく、図５は、このような作業の各ステップをフローチャートとして表現した図である。
【００６５】
図５を参照すると、検索結果提供装置１００（または、その内部の類似文書検出部１３０のうちクラスタリング手段１３１）は、検索データベースに保存されたウェブ文書から類似文書が存在する可能性のあるクラスタを生成する（ステップＳ５１０）。上述した具体的な実施形態のように、クラスタ生成に適用され得る方法は、ホストクラスタリング、パスクラスタリング、クエリクラスタリング、サイズクラスタリング、シムハッシュクラスタリング、ＤＯＭクラスタリングまたは他の公知のクラスタリング方式のうちいずれか一つ以上を任意の順序で組み合わせることにより適用してもよい。
【００６６】
その後、類似文書検出部１３０のエンティティ抽出手段１３２は、クラスタリング手段１３１で生成されたクラスタ内のウェブ文書からエンティティ、及びエンティティの重要度寄与要素を抽出する機能を行ってもよい（ステップＳ５２０）。上述したように、エンティティは、ウェブ文書からパーシングされて分離され得るテキストを含んでもよく、その他にもアンカーに含まれるｈｒｅｆ属性やエンベッド、イメージタグなどに含まれるｓｒｃ属性値などをさらに含んでもよい。また、重要度寄与要素には各エンティティのハッシュ値の他にも各エンティティがクラスタ内の全体ウェブ文書のうち何個のウェブ文書に重複するかに対する回数あるいは頻度などの数値が含まれてもよい。
【００６７】
その後、類似文書検出部１３０の加重値計算手段１３３は、エンティティ抽出手段１３２から抽出された内容に基づいてクラスタ内の各エンティティに対する加重値を計算する機能を行ってもよい（ステップＳ５３０）。各エンティティに対する加重値は、当該エンティティがウェブ文書中で核心となる部分に該当するか否かに基づいて計算されてもよく、その具体的な一例として、文献出現頻度の逆数（ＩＤＦ）を用いてクラスタ内のウェブ文書に重複する回数が多いほどその加重値が増加し、クラスタ内のウェブ文書に重複する回数が少ないほどその加重値が減少する概念に基づく様々な式を適用して計算されてもよい。
【００６８】
その後、類似文書検出部１３０の類似文書検出手段１３４は、加重値計算手段１３３で計算された、クラスタ内のウェブ文書から抽出された各エンティティに対して加重値を適用したウェブ文書の特性指数を計算し、計算された各ウェブ文書の特性指数同士を比較して（例えば、特性指数がシムハッシュである場合、シムハッシュ間のハミング距離が特定数値以下であるか否かなどを計算して）類似文書であるか否かを検出する機能を行ってもよい（ステップＳ５４０）。また、類似文書検出手段１３４は、類似文書として検出された重複するウェブ文書を検索データベース１４０から削除する機能をさらに含んでもよい。
【００６９】
本発明による実施形態は、多様なコンピュータ手段によって行われるプログラム命令語の形態で実現され、コンピュータ読み取り可能な媒体に記録されてもよい。コンピュータ読み取り可能な媒体は、プログラム命令語、データファイル、データ構造などを単独で、または組み合わせて含んでもよい。前記媒体に記録されるプログラム命令語は、本発明のために特に設計及び構成されたものであってもよく、コンピュータソフトウェア分野の当業者に公知であって使用可能なものであってもよい。コンピュータ読み取り可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク及び磁気テープのような磁気媒体（ｍａｇｎｅｔｉｃ ｍｅｄｉａ）、ＣＤ−ＲＯＭ、ＤＶＤなどのような光記録媒体（ｏｐｔｉｃａｌ ｍｅｄｉａ）、フロプティカルディスク（ｆｌｏｐｔｉｃａｌ ｄｉｓｋ）のような磁気−光媒体（ｍａｇｎｅｔｏ−ｏｐｔｉｃａｌ ｍｅｄｉａ）及びＲＯＭ、ＲＡＭ、フラッシュメモリなどのような、プログラム命令語を保存及び実行するように特に構成されたハードウェア装置が含まれる。プログラム命令語の例としては、コンパイラによって作成されるような機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行することができる高級言語コードも含まれる。ハードウェア装置は、本発明における動作を行うために一つ以上のソフトウェアモジュールとして動作するように構成されてもよく、その逆も同様である。
【００７０】
以上、本発明を具体的な構成要素などのような特定の事項と限定された実施例及び図面を参照して説明したが、これは本発明のより全体的な理解を容易にするために提供されたものにすぎず、本発明は前記実施例によって限定されず、本発明が属する分野における通常の知識を有する者であれば、このような記載から多様な修正及び変形が可能である。
【００７１】
従って、本発明の思想は前記実施例に限定されて決まってはならず、添付する特許請求の範囲の記載だけでなく、特許請求の範囲の記載と均等または等価的に変形された全てのものは、本発明の思想の範疇に属すると理解するべきであろう。
【符号の説明】
【００７２】
１００ 検索結果提供装置
１３０ 類似文書検出部
１３１ クラスタリング手段
１３２ エンティティ抽出手段
１３３ 加重値計算手段
１３４ 類似文書検出手段
【特許請求の範囲】
【請求項１】
類似文書検出装置で行われる方法であって、
複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティを抽出し、
前記算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算し、
前記算出された加重値に基づいて前記複数のウェブ文書が類似文書であるか否かを検出すること、を含むことを特徴とする改善された類似文書検出方法。
【請求項２】
前記複数のウェブ文書を所定の方式により一つのクラスタに統合するクラスタリングすることをさらに含むことを特徴とする請求項１に記載の改善された類似文書検出方法。
【請求項３】
前記所定の方式は、ホスト（Ｈｏｓｔ）クラスタリング、パス（Ｐａｔｈ）クラスタリング、クエリ（Ｑｕｅｒｙ）クラスタリング、サイズ（Ｓｉｚｅ）クラスタリング、シムハッシュ（Ｓｉｍｈａｓｈ）クラスタリングまたはＤＯＭ（Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ Ｍｏｄｅｌ）クラスタリングのうち少なくとも一つ以上を任意の順序で組み合わせたものであることを特徴とする請求項２に記載の改善された類似文書検出方法。
【請求項４】
前記エンティティを抽出することは、
前記複数のウェブ文書のうちいずれか一つから文書構造を抽出し、
前記抽出された文書構造に基づいてエンティティを抽出すること、を前記複数のウェブ文書全てに対して繰り返すことにより行われ、
前記エンティティは、前記文書構造のテキストノード、アンカー（ａｎｃｈｏｒ）ノード、エンベッド（ｅｍｂｅｄ）ノードまたはイメージ（ｉｍｇ）ノードのうちいずれか一つ以上のノードから抽出されることを特徴とする請求項１から３のいずれか一項に記載の改善された類似文書検出方法。
【請求項５】
前記エンティティがテキストノードから抽出される場合、
前記テキストノードの上位ノードの中に存在するＩＤ値を前記エンティティに結合して使用することを特徴とする請求項４に記載の改善された類似文書検出方法。
【請求項６】
前記重要度寄与要素は、
前記エンティティが前記複数のウェブ文書中で核心となる程度の重要度を反映するものであることを特徴とする請求項１から５のいずれか一項に記載の改善された類似文書検出方法。
【請求項７】
前記重要度寄与要素は、前記エンティティのハッシュ値、または前記エンティティが前記複数のウェブ文書中で重複する回数や頻度のうちいずれか一つ以上を含む値であることを特徴とする請求項６に記載の改善された類似文書検出方法。
【請求項８】
前記加重値は、前記算出されたエンティティの重複する回数や頻度に反比例する文献出現頻度の逆数（Ｉｎｖｅｒｔｅｄ Ｄｏｃｕｍｅｎｔ Ｆｒｅｑｕｅｎｃｙ）を用いて計算されることを特徴とする請求項７に記載の改善された類似文書検出方法。
【請求項９】
前記類似文書を検出することは、
前記複数のウェブ文書それぞれに含まれるエンティティ及び前記エンティティの加重値に基づいて前記複数のウェブ文書それぞれの特性指数を計算し、
前記計算されたそれぞれの特性指数に基づいて前記複数のウェブ文書が類似文書であるか否かを検出すること、を含むことを特徴とする請求項１から８のいずれか一項に記載の改善された類似文書検出方法。
【請求項１０】
前記特性指数はシムハッシュ（Ｓｉｍｈａｓｈ）であることを特徴とする請求項９に記載の改善された類似文書検出方法。
【請求項１１】
前記特性指数に基づいて類似文書であるか否かを検出することは、
前記複数のウェブ文書それぞれが有する特性指数であるシムハッシュ間のハミング距離（ｈａｍｍｉｎｇ ｄｉｓｔａｎｃｅ）が所定数値以下である場合、類似文書として検出されることを特徴とする請求項９又は１０に記載の改善された類似文書検出方法。
【請求項１２】
前記類似文書検出結果に基づいて前記複数のウェブ文書のうち重複する類似文書を削除する類似文書を削除することをさらに含むことを特徴とする請求項１から１１のいずれか一項に記載の類似文書検出方法。
【請求項１３】
請求項１から１２のいずれか一項に記載の方法の各ステップをコンピュータ上で行うためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１４】
複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティ抽出手段と、
前記算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算する加重値計算手段と、
前記算出された加重値に基づいて前記複数のウェブ文書が類似文書であるか否かを検出する類似文書検出手段と、を含むことを特徴とする改善された類似文書検出装置。
【請求項１５】
前記複数のウェブ文書を所定の方式により一つのクラスタに統合し、統合した前記クラスタを前記複数のウェブ文書として前記エンティティ抽出手段に提供するクラスタリング手段をさらに含むことを特徴とする請求項１４に記載の改善された類似文書検出装置。
【請求項１６】
前記所定の方式は、ホスト（Ｈｏｓｔ）クラスタリング、パス（Ｐａｔｈ）クラスタリング、クエリ（Ｑｕｅｒｙ）クラスタリング、サイズ（Ｓｉｚｅ）クラスタリング、シムハッシュ（Ｓｉｍｈａｓｈ）クラスタリングまたはＤＯＭ（Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ ＭｏｄｅＬ）クラスタリングのうち少なくとも一つ以上を任意の順序で組み合わせたものであることを特徴とする請求項１５に記載の改善された類似文書検出装置。
【請求項１７】
前記エンティティ抽出手段は、
前記複数のウェブ文書のうちいずれか一つから文書構造を抽出し、前記抽出された文書構造に基づいてエンティティを抽出することを前記複数のウェブ文書全てに対して繰り返して行い、
前記エンティティは、前記文書構造のテキストノード、アンカー（ａｎｃｈｏｒ）ノード、エンベッド（ｅｍｂｅｄ）ノードまたはイメージ（ｉｍｇ）ノードのうちいずれか一つ以上のノードから抽出されることを特徴とする請求項１４から１６のいずれか一項に記載の改善された類似文書検出装置。
【請求項１８】
前記エンティティがテキストノードから抽出される場合、
前記テキストノードの上位ノードの中に存在するＩＤ値を前記エンティティに結合して使用することを特徴とする請求項１７に記載の改善された類似文書検出装置。
【請求項１９】
前記重要度寄与要素は、
前記エンティティが前記複数のウェブ文書中で核心となる程度の重要度を反映するものであることを特徴とする請求項１４から１８のいずれか一項に記載の改善された類似文書検出装置。
【請求項２０】
前記重要度寄与要素は、前記エンティティのハッシュ値、または前記エンティティが前記複数のウェブ文書中で重複する回数や頻度のうちいずれか一つ以上を含む値であることを特徴とする請求項１９に記載の改善された類似文書検出装置。
【請求項２１】
前記加重値は、前記算出されたエンティティの重複する回数や頻度に反比例する文献出現頻度の逆数（Ｉｎｖｅｒｔｅｄ Ｄｏｃｕｍｅｎｔ Ｆｒｅｑｕｅｎｃｙ）を用いて計算されることを特徴とする請求項２０に記載の改善された類似文書検出装置。
【請求項２２】
前記類似文書検出手段は、
前記複数のウェブ文書それぞれに含まれるエンティティ及び前記エンティティの加重値に基づいて前記複数のウェブ文書それぞれの特性指数を計算し、前記計算されたそれぞれの特性指数に基づいて前記複数のウェブ文書が類似文書であるか否かを検出するものであることを特徴とする請求項１４から２１のいずれか一項に記載の改善された類似文書検出装置。
【請求項２３】
前記特性指数はシムハッシュ（Ｓｉｍｈａｓｈ）であることを特徴とする請求項２２に記載の改善された類似文書検出装置。
【請求項２４】
前記特性指数に基づいて類似文書であるか否かを検出することは、
前記複数のウェブ文書それぞれが有する特性指数であるシムハッシュ間のハミング距離（ｈａｍｍｉｎｇ ｄｉｓｔａｎｃｅ）が所定数値以下である場合、類似文書として検出されることを特徴とする請求項２３に記載の改善された類似文書検出装置。
【請求項２５】
前記類似文書検出手段は、前記類似文書検出結果に基づいて前記複数のウェブ文書のうち重複する類似文書を削除することをさらに含むことを特徴とする請求項１４から２４のいずれか一項に記載の改善された類似文書検出装置。
【請求項１】
類似文書検出装置で行われる方法であって、
複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティを抽出し、
前記算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算し、
前記算出された加重値に基づいて前記複数のウェブ文書が類似文書であるか否かを検出すること、を含むことを特徴とする改善された類似文書検出方法。
【請求項２】
前記複数のウェブ文書を所定の方式により一つのクラスタに統合するクラスタリングすることをさらに含むことを特徴とする請求項１に記載の改善された類似文書検出方法。
【請求項３】
前記所定の方式は、ホスト（Ｈｏｓｔ）クラスタリング、パス（Ｐａｔｈ）クラスタリング、クエリ（Ｑｕｅｒｙ）クラスタリング、サイズ（Ｓｉｚｅ）クラスタリング、シムハッシュ（Ｓｉｍｈａｓｈ）クラスタリングまたはＤＯＭ（Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ Ｍｏｄｅｌ）クラスタリングのうち少なくとも一つ以上を任意の順序で組み合わせたものであることを特徴とする請求項２に記載の改善された類似文書検出方法。
【請求項４】
前記エンティティを抽出することは、
前記複数のウェブ文書のうちいずれか一つから文書構造を抽出し、
前記抽出された文書構造に基づいてエンティティを抽出すること、を前記複数のウェブ文書全てに対して繰り返すことにより行われ、
前記エンティティは、前記文書構造のテキストノード、アンカー（ａｎｃｈｏｒ）ノード、エンベッド（ｅｍｂｅｄ）ノードまたはイメージ（ｉｍｇ）ノードのうちいずれか一つ以上のノードから抽出されることを特徴とする請求項１から３のいずれか一項に記載の改善された類似文書検出方法。
【請求項５】
前記エンティティがテキストノードから抽出される場合、
前記テキストノードの上位ノードの中に存在するＩＤ値を前記エンティティに結合して使用することを特徴とする請求項４に記載の改善された類似文書検出方法。
【請求項６】
前記重要度寄与要素は、
前記エンティティが前記複数のウェブ文書中で核心となる程度の重要度を反映するものであることを特徴とする請求項１から５のいずれか一項に記載の改善された類似文書検出方法。
【請求項７】
前記重要度寄与要素は、前記エンティティのハッシュ値、または前記エンティティが前記複数のウェブ文書中で重複する回数や頻度のうちいずれか一つ以上を含む値であることを特徴とする請求項６に記載の改善された類似文書検出方法。
【請求項８】
前記加重値は、前記算出されたエンティティの重複する回数や頻度に反比例する文献出現頻度の逆数（Ｉｎｖｅｒｔｅｄ Ｄｏｃｕｍｅｎｔ Ｆｒｅｑｕｅｎｃｙ）を用いて計算されることを特徴とする請求項７に記載の改善された類似文書検出方法。
【請求項９】
前記類似文書を検出することは、
前記複数のウェブ文書それぞれに含まれるエンティティ及び前記エンティティの加重値に基づいて前記複数のウェブ文書それぞれの特性指数を計算し、
前記計算されたそれぞれの特性指数に基づいて前記複数のウェブ文書が類似文書であるか否かを検出すること、を含むことを特徴とする請求項１から８のいずれか一項に記載の改善された類似文書検出方法。
【請求項１０】
前記特性指数はシムハッシュ（Ｓｉｍｈａｓｈ）であることを特徴とする請求項９に記載の改善された類似文書検出方法。
【請求項１１】
前記特性指数に基づいて類似文書であるか否かを検出することは、
前記複数のウェブ文書それぞれが有する特性指数であるシムハッシュ間のハミング距離（ｈａｍｍｉｎｇ ｄｉｓｔａｎｃｅ）が所定数値以下である場合、類似文書として検出されることを特徴とする請求項９又は１０に記載の改善された類似文書検出方法。
【請求項１２】
前記類似文書検出結果に基づいて前記複数のウェブ文書のうち重複する類似文書を削除する類似文書を削除することをさらに含むことを特徴とする請求項１から１１のいずれか一項に記載の類似文書検出方法。
【請求項１３】
請求項１から１２のいずれか一項に記載の方法の各ステップをコンピュータ上で行うためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１４】
複数のウェブ文書それぞれからエンティティ（ｅｎｔｉｔｙ）及び重要度寄与要素を算出するエンティティ抽出手段と、
前記算出された重要度寄与要素に基づいて各エンティティに対する加重値を計算する加重値計算手段と、
前記算出された加重値に基づいて前記複数のウェブ文書が類似文書であるか否かを検出する類似文書検出手段と、を含むことを特徴とする改善された類似文書検出装置。
【請求項１５】
前記複数のウェブ文書を所定の方式により一つのクラスタに統合し、統合した前記クラスタを前記複数のウェブ文書として前記エンティティ抽出手段に提供するクラスタリング手段をさらに含むことを特徴とする請求項１４に記載の改善された類似文書検出装置。
【請求項１６】
前記所定の方式は、ホスト（Ｈｏｓｔ）クラスタリング、パス（Ｐａｔｈ）クラスタリング、クエリ（Ｑｕｅｒｙ）クラスタリング、サイズ（Ｓｉｚｅ）クラスタリング、シムハッシュ（Ｓｉｍｈａｓｈ）クラスタリングまたはＤＯＭ（Ｄｏｃｕｍｅｎｔ Ｏｂｊｅｃｔ ＭｏｄｅＬ）クラスタリングのうち少なくとも一つ以上を任意の順序で組み合わせたものであることを特徴とする請求項１５に記載の改善された類似文書検出装置。
【請求項１７】
前記エンティティ抽出手段は、
前記複数のウェブ文書のうちいずれか一つから文書構造を抽出し、前記抽出された文書構造に基づいてエンティティを抽出することを前記複数のウェブ文書全てに対して繰り返して行い、
前記エンティティは、前記文書構造のテキストノード、アンカー（ａｎｃｈｏｒ）ノード、エンベッド（ｅｍｂｅｄ）ノードまたはイメージ（ｉｍｇ）ノードのうちいずれか一つ以上のノードから抽出されることを特徴とする請求項１４から１６のいずれか一項に記載の改善された類似文書検出装置。
【請求項１８】
前記エンティティがテキストノードから抽出される場合、
前記テキストノードの上位ノードの中に存在するＩＤ値を前記エンティティに結合して使用することを特徴とする請求項１７に記載の改善された類似文書検出装置。
【請求項１９】
前記重要度寄与要素は、
前記エンティティが前記複数のウェブ文書中で核心となる程度の重要度を反映するものであることを特徴とする請求項１４から１８のいずれか一項に記載の改善された類似文書検出装置。
【請求項２０】
前記重要度寄与要素は、前記エンティティのハッシュ値、または前記エンティティが前記複数のウェブ文書中で重複する回数や頻度のうちいずれか一つ以上を含む値であることを特徴とする請求項１９に記載の改善された類似文書検出装置。
【請求項２１】
前記加重値は、前記算出されたエンティティの重複する回数や頻度に反比例する文献出現頻度の逆数（Ｉｎｖｅｒｔｅｄ Ｄｏｃｕｍｅｎｔ Ｆｒｅｑｕｅｎｃｙ）を用いて計算されることを特徴とする請求項２０に記載の改善された類似文書検出装置。
【請求項２２】
前記類似文書検出手段は、
前記複数のウェブ文書それぞれに含まれるエンティティ及び前記エンティティの加重値に基づいて前記複数のウェブ文書それぞれの特性指数を計算し、前記計算されたそれぞれの特性指数に基づいて前記複数のウェブ文書が類似文書であるか否かを検出するものであることを特徴とする請求項１４から２１のいずれか一項に記載の改善された類似文書検出装置。
【請求項２３】
前記特性指数はシムハッシュ（Ｓｉｍｈａｓｈ）であることを特徴とする請求項２２に記載の改善された類似文書検出装置。
【請求項２４】
前記特性指数に基づいて類似文書であるか否かを検出することは、
前記複数のウェブ文書それぞれが有する特性指数であるシムハッシュ間のハミング距離（ｈａｍｍｉｎｇ ｄｉｓｔａｎｃｅ）が所定数値以下である場合、類似文書として検出されることを特徴とする請求項２３に記載の改善された類似文書検出装置。
【請求項２５】
前記類似文書検出手段は、前記類似文書検出結果に基づいて前記複数のウェブ文書のうち重複する類似文書を削除することをさらに含むことを特徴とする請求項１４から２４のいずれか一項に記載の改善された類似文書検出装置。
【図１ａ】
【図１ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７ａ】
【図７ｂ】
【図８ａ】
【図８ｂ】
【図８ｃ】
【図９ａ】
【図９ｂ】
【図１０】
【図１ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７ａ】
【図７ｂ】
【図８ａ】
【図８ｂ】
【図８ｃ】
【図９ａ】
【図９ｂ】
【図１０】
【公開番号】特開２０１２−２３４５２２（Ｐ２０１２−２３４５２２Ａ）
【公開日】平成２４年１１月２９日（２０１２．１１．２９）
【国際特許分類】
【出願番号】特願２０１２−６３３５８（Ｐ２０１２−６３３５８）
【出願日】平成２４年３月２１日（２０１２．３．２１）
【出願人】（５０５２０５８１２）エヌエイチエヌ コーポレーション (408)
【公開日】平成２４年１１月２９日（２０１２．１１．２９）
【国際特許分類】
【出願日】平成２４年３月２１日（２０１２．３．２１）
【出願人】（５０５２０５８１２）エヌエイチエヌ コーポレーション (408)
[ Back to top ]