Tree Edit Distanceアルゴリズムの応用と実装

今日はアドファイブの製品開発の中身について少し。

背景(実装を早く見たい方はここはスキップして次節へ)

バナー広告に代わる広告フォーマットとしてネイティブ広告というのが欧米を中心に盛り上がっています。TwitterFacebookのフィードに紛れ込んでくる広告もネイティブ広告の一種と言われています。

ネイティブ広告特有の技術として、サイトのデザインに自動的にフィットさせる技術を開発する必要があります。
例えば、このNativoというネイティブ広告プラットフォームベンダはWebサイトを自動的に解析してネイティブ広告をプレビューできるという技術を持っています。手動で色々とインタラクティブにデザインの定義や設定をするUIでも良いのですが、やはりNativo社のような自動化エンジンを開発したくなります。

TwitterFacebookのフィード広告のように、ネイティブ広告の代表例は「フィード型」です。フィードというのは、同じデザインが繰り返し現れる構造にフィットします。Pinterestのデザインもフィード型といえます。そこでWebサイト上で「フィード」とみなせる箇所を抽出することが課題となります。HTMLのマークアップ解析の出番です。

例えば以下のYahooトップページのニューストピックの欄を見てみましょう。

人間ならパッと見て繰り返し現れる構造にすぐ気づきますが、以下のように機械化する上での難しさがあります。

  • 階層構造の内部に埋め込まれているのを見つけられるか?
  • 弱冠の表記のゆれ(写真やNew!のアイコンの有無とか)に対応できるか?
  • 文字列やリンクの意味(この場合はタイトル)を抽出できるか?

実際、上図の箇所のマークアップを見てみると、以下のように揺れがあります。

<li><a href="f/topics/top/3/*-http://dailynews.yahoo.co.jp/fc/domestic/first_aid/?id=6098232">車で25m転落夫婦11日ぶ り救助</a></li>
<li><a href="f/topics/top/4/*-http://dailynews.yahoo.co.jp/fc/computer/search_engine/?id=6098224">NAVER、日本での検 索終了</a><span cla
ss="iconPhoto" title="写真">写真</span><span class="iconNew" title="NEW">NEW</span></li>
<li><a href="f/topics/top/5/*-http://dailynews.yahoo.co.jp/fc/domestic/bear/?id=6098235">クマがハチミツ手にワナ脱出</a><span class="iconPhoto"
 title="写真">写真</span></li>
(以下略)

やりたいことは以下です。

  • こうした揺れのあるマークアップから繰り返し現れる構造とその箇所を抽出する
  • それをなんらかのテンプレートエンジンの記法でHTMLテンプレート化する
  • テンプレートに与えるデータについての情報(メタデータ)を生成する

HTMLテンプレートと、メタデータというのは例えばmustacheというテンプレートエンジンでしたら

  <li>
    <a href="{{url}}">{{title}}</a>
    {{#iconNew}}
    <span class="iconNew" title="NEW">NEW</span>
    {{/iconNew}}
    {{#iconPhoto}}
    <span class="iconPhoto" title="写真">写真</span>
    {{/iconPhoto}}
  </li>

というテンプレートと、定型的なフィード情報を揺れのあるテンプレートに結びつけるために

{
  "url": "{{feed_url}}",
  "title": "{{feed_title}}" ,
  "iconPhoto": "{{feed_has_photo}}",
  "iconNew": "{{feed_user_param1}}"
}

みたいなメタデータJSONを自動生成したいわけです。以上が出来れば

  1. 広告として与えられたフィード情報をこのメタデータを使ってJSONオブジェクト化する
  2. JSONとテンプレートをテンプレートエンジンに与えてHTMLスニペットを生成する
  3. 広告掲載先サイトに挿入した広告用Javascriptタグが対象箇所にスニペットを挿入する

という手順でアドサーバが実装できます。

そこでまずはアドホックな実装をでっち上げてそれなりに動くものは出来た(chiral's Gistに掲載)ですが、ロバストにしようとすればするほどアドホックさが増していくという良くない事態になったため、もっと本腰を入れてやることにしました。

Tree Edit Distanceアルゴリズム

HTMLのマークアップ木構造になるので、木どうしの距離を定量化できればマークアップ解析においてクラスタリング等の「ソフトなアルゴリズム」が色々適用できます。また距離を測るだけでなく木から木へ最小回数で変換する手順も得られるとうれしいところです。(最初は文脈自由文法の自動学習のような手法が使えないかと調べていたのですが、本タスクの場合はもっと基本的アルゴリズムがフィットしそうな感じです。)

ネットで調べたらPFI社のブログでTree Edit Distanceアルゴリズムについて紹介されているのを見つけました。これはバッチリ欲しいものそのものです。その記事を書いた海野さんがJavaで実装したコードがGithubに上がっていますが、本プロジェクトはスクレイピング等にnode.jsを使っているしアルゴリズム自体も簡単なのでjavascriptで実装しました(chiral's Gist)

あるノードのjqueryオブジェクトを与えると、その直下の子ノードどうしのマークアップを比較して編集距離と、最小の照合・編集手順を出力します。早速実行してみます。前節で上げたYahooニュースのマークアップの部分を食わせてみます。

var $=require("jquery");
var ted=require("./ted.js");
(中略)
fs.readFile('./yahoo.html', 'utf8', function (err, text) {
    var r=[];
    $(text).find(".emphasis").children().each(function(){
      r.push(this);
    });
    for (var i=0; i<r.length; i++) {
        for (var j=i; j<r.length; j++) {
            var ops=[];
            var result=ted.calc($,$(r[i]),$(r[j]),ops); // -- ノードのエンコーディング関数を指定できる(後述)
            console.log([i,j]);
            console.log(ops);
            console.log('result='+result);
            console.log();
        }
    }
});

実行結果:

[ 0, 1 ]
[ '<li>=<li>',
  '<a href>=<a href>',
  'del1:<span .iconPhoto title>']
result=1

(中略)

[ 5, 7 ]
[ '<li>=<li>',
  '<a href>=<a href>',
  '<span .iconPhoto title>=<span .iconPhoto title>',
  '<span .iconNew title>=<span .iconNew title>' ]
result=0

再掲図:

実行結果の一つ目([ 0,1 ])はニュースの1番目(猪瀬氏〜)と2番目(車〜)のマークアップの編集距離で、liタグ、aタグの2つは一致して、class=iconPhotoのspanタグが差分となっていることがちゃんと示されてます。その下はニュース6番目と8番目のマークアップ比較で、これはちゃんと一致(距離がゼロ)と判定されてます。

ノードどうしの一致判定の仕方によって、距離は変わってきます。例えばこの例ではaタグのhref属性に与えるURL(リンク先URL)は比較してないため、URLが異なっていても同一ノードだと判定されてます。実装したコードは、このノードの文字列にエンコーディングする関数をオプションとして与えることが出来るようになっていて、エンコーディング方法を変えることで距離計算の方法をカスタマイズできます。デフォルトではタグ名と属性名(classとid属性だけは特別に属性の値も含める)をエンコーディングに使っているため、何も指定しなければ上のような実行結果になります。

もう一つやってみます。いかにも繰り返しパターンという感じの「おすすめセレクション」のところ。

実行結果(該当箇所のセレクタは"#slcbd"):

[ 0, 1 ]
result=0
[ 0, 2 ]
result=0
[ 0, 3 ]
result=0
[ 1, 2 ]
result=0
[ 1, 3 ]
result=0
[ 2, 3 ]
result=0

上手くすべての組み合わせで距離ゼロと判定されました。

これを使って、まずは子ノードのクラスタリングを各ノードについて行って、クラスタの大きい順とかで並べれば「フィード」に相当する箇所は抜き出せそうです。またこのアルゴリズムは「編集手順」を出力してくれるので、それを加工すれば(前節で)上述したHTMLテンプレートやメタ情報も生成できそうです。

というわけで

続きはまた。これ以外にもネイティブ広告のプレビュー機能を実装するにあたってJSタグを入れずにプレビューするためのアドホックなミラーサーバや、流行りのパララックスデザインのようなマークアップでは解析しきれないパターンに対応するためのCasperJSを使ったサイト解析等を実装しているので機をみてご紹介したいと思います。