HTMLのドキュメントから繰り返し部分をみつける

RSSを生成していないページからRSSを生成するなんでもRSS 0.1bは、公開されているJSAI2005: なんでもRSS - HTML文書からのRSS自動生成によると、日付情報を目印にしてそのHTMLドキュメントの構造を推測して、各エントリ(item要素)のタイトルと本文を単語の統計的に処理して決定し、フィードを生成していると書かれています。

ウェブ上にあるHTMLドキュメントは Ask.jp ： "xml" Search results. のように、RSSのitem要素に相当する部分に日付が含まれていないものもあります。
その中でも、大量のデータを複数のページにわけて表示しているHTMLドキュメントを対象に、ドキュメント中に含まれる繰り返し部分のXPathを生成するブログラムをjavascriptで作りました。

アプローチ

大量のデータを複数のページわけて表示しているドキュメントを対象とするので、ふたつのページのドキュメントをとりだして差をとると、全てのページで共通しているヘッダやフッタ、ナビゲーション部分以外の本文に当たる部分(検索結果ページであれば、検索結果の一覧)が差分として出てくることが予想されます。

出てきた差分から、最も差分を多く持っている要素を繰り返し部分の親要素候補としてリストアップします。親要素候補に含まれる子要素に設定されているクラス名と、要素に含まれる文字列の長さをもとにして、ページに含まれる最も重要だと思われる繰り返し部分のXPathを生成します。

試してみる

bookmarkletもしくはJSActionsスクリプトとして使うことができます。

bookmarkletとして使う

bookmarkletとして使うときは iterationDetectorをブックマークしておためしください。ブックマークレットを実行したあと(みためは何も変わりません)、次のページへのリンクをクリックしてください。次のページを取得して差分を計算して繰り返し部分のXPathを下のような形式でFirebugのコンソールに出力します。

ページの複雑さとコンピュータの性能にもよりますが、結果が出るまでだいたい2~3秒ほどかかります。ただしbookmarkletとして使う場合、以下のときに問題が生じます。

ページでprototype.jsが使われているとき: Arrayオブジェクトのshiftメソッドが上書きされているのが原因でスクリプトがエラーを出して止まります。
次のページへのリンクが別ドメインになっているとき: Ask.jp ： "google" Search results.のように、次のページへのリンクが別ドメインになっている場合XMLHttpRequestでページを取得できないため機能しません

JSActionsコマンドとして使う

JSActionsはコンテキストメニューからお手軽にchrome特権付きでスクリプトを実行できるFirefox extensionです。なんとなく書かないままになってしまっていましたがjavascriptを拡張機能のコンテキストで実行できる Execute JS - bits and bytesより便利に使えると思います。詳しくはJavascript Actions - Mozilla Firefox まとめサイトで。 JSActionsのスクリプトとして使うときにはiterationDetector.jsをlinkディレクトリに入れて、次のページへのリンクを選択してiterationDetectorを実行してください。

実行結果例

いくつかのページで実行した結果を下に示します。

Ask.jp検索結果

上にも出てきた Ask.jp ： "google" Search results. ではこうなります。

ページに10回の繰り返しが含まれているのがうまく抽出できています。

ちなみにコンソールに出てきたDOMのエレメントを表している部分にマウスを持っていくと、その部分の色が変わるので期待通りにXPathが生成されているかどうか目で見て分かります。

mozillaZine

mozillaZine 日本語版は、比較的短い文章のエントリがページに5つ含まれています。

ask.jpの場合、繰り返し部分の親要素にidもユニークなクラス名もついていないのでpositionで記述されたXPathになっていましたが、mozillaZineは親要素にidがついているので、親要素をidで記述するようになっています。

はてなブックマーク

はてなブックマーク - ku0522のブックマークは、実行に5~10秒ほどかかります。 1ページに20のブックマークが表示されていて、右側に使用しているタグの一覧がタグクラウドで表示されています。自分の場合タグの数は320あります。繰り返しの回数ではタグクラウド部分が圧倒的に多いのですが、次のページと差分をとったときにタグクラウド部分はまったく同じなため、意味のある繰り返しとして見なされず、ブックマークのリスト部分が繰り返しとして抽出されます。

Google Groups

ディスカッション - mozilla.dev.security | Google グループは、左側に投稿のサマリが10件、右側に最近投稿があったトピック10件が表示されていますが、文字数の多さから左側が繰り返し部分として出力されます。

CPAN検索結果

The CPAN Search Site - search.cpan.orgはbodyの直下にPタグで各結果を表示するようになっています。

twitter

Twitter / kuは、左側に発言が19回、右側にfollowingがたくさん表示されていますが、following部分はページ間で変化がないので左側の発言リストが繰り返し部分として出力されます。

このアプローチの問題点

最後にうまくいかない例を挙げ、このアプローチの限界を示します。

TechCrunch Japanese

TechCrunch JapaneseもmozillaZineに似て、比較的短い文章がのエントリが5つ含まれています。

まずわかりやすいところでmozillaZineと違うのは、ページの右側にswickiと書かれたタグクラウドの部分があるところです。このタグクラウドにはタグの数だけ繰り返し構造が含まれていて、さらになぜかランダムに表示されているため、ページ間で差分をとると異なる部分として判断されます。

当初繰り返している回数が多い部分を、ページを構成している繰り返し部分と判定していたため、このswicki部分が抽出されていました。

ここでひとつ気がついたのが、人間にとって意味のある部分はページの中で(ふつうは)最も大きなピクセル数を持っているということでした。HTMLは人がブラウザでそこに書かれている情報を読みやすいように書かれているはずなので、多くのピクセル数が割り当てられている部分がページを構成している主要な繰り返し部分だと考えられます。そして要素のピクセル数は要素に含まれているテキストの長さに比例して大きくなるので、要素に含まれている文字数に応じて重み付けをしたところ、期待する動作をするようになりました。

一見うまく抽出できているように見えますが、HTMLを見てみるとひとつのエントリがh2タグとdivタグとで構成されていることが分かります。

これがもうひとつの困ったところで、このように繰り返し部分の最小単位が複数の要素から成っていると(この場合h2とdiv)、XPathではひとつひとつの繰り返し部分を表現できません。

ひとつの繰り返しという単位を複数の要素で記述しているtechCrunchのHTMLがよくない、と主張することもできそうですが、よく考えると
Lists in HTML documents (ja)を見て分かる通り、dlタグはdtとddをひとつの繰り返しの単位として記述することができるようになっています。

Mozilla Developer Center検索結果

そしてMozilla Developer Centerの検索結果は、実際にdtとddを繰り返しの単位として表示しています。Nutch Mediawiki Search: createdocument - MDCは、1ページに8件の検索結果を表示します。その構造はdlタグの中にdtとddで各項目をリストしていくようになっています。

iterationDetectorはこの場合を想定していないので、好ましくない結果を返します。

HTMLの仕様に、ひとつの繰り返しという単位を複数のタグで表すことが含まれている以上、何らかの方法でひとつの繰り返しがどこからどこまでなのかを推測し、それを表現する方法を考える必要がありそうです。

そのほかの問題点

そのほかにも、実装中に遭遇した細かい問題点についてあげておきます。

HTMLの解釈の差

次のページをXMLHttpRequestで読み込んだあと、DOMDocumentオブジェクトにするときHTMLDocumentを(かなり無理矢理)生成する方法がわかったのでGM_xmlhttpRequestでwell-formedじゃないHTMLのコードを取ってきて新しく生成したHTMLDocumentでパースしてみるよに記述された方法を使っています。しかしこの方法で生成されるDOMツリーはwell-formedへの変換方法がブラウザのウインドウ内でHTMLを表示するときは違うようです。 well-formed - Google 検索を見ると、昔formの前後に空白ができてしまうのを避けるために使われていたtrとtdの間にformを入れる方法が使われています。

<table class=tb style=clear:left width=100%><tr><form name=gs method=GET action=/search><td

これがウインドウで開くときと上記の方法を使うときとで違う部分として出力されました。

....もうひとつあった気がしたのですが思い出せないので思い出せたら追記します。

まとめ

ページ間の差分をとって繰り返しを抽出する方法を試してみました。 OperaのFast Forwardはどうやって次のページを決定しているのか - bits and bytesのような次のページへのリンクを判別する仕組みと組み合わせることで、自動的に繰り返し部分のXPathを抽出することが可能になります。

XPathで繰り返し部分を表現するため表現可能なページ構造が限られているため、Mozilla Developer Centerの検索結果ページ等は表現できません。しかし表現できないページの割合は高くないでしょう。

反省点

ブラウザ上で実行できれば、次のページを表すリンクの選択が容易で使いやすいという点、繰り返し部分と判定されたところが期待する部分かどうかをすぐに視覚的に確認できるという点、レンダリングされたときにブラウザ上でどれくらいの大きさを占めるかという情報を得ることができ、重み付けに利用できるという点でjavascriptで実装することにしました。

しかし、まだjavascriptで重い計算処理をやるのはつらく、またスクリプトで自動的に実行することができず毎回手作業でリンクを選択する、ページを切り替える、ことが必要で、さらにレンダリングされるサイズはだいたい文字数に比例するので文字数で代替可能というのがわかりました。perl等で実装していれば、自動化して多数のページを対象に調整を行って精度を高めやすかったかなと思います。