木構造の距離を求めたいので Tree Edit Distance

Tree Edit Distance とは木構造同士の編集距離を求める手法です。
構文解析やhtml、ディレクトリ構造, URL など木構造として表せるデータ構造は多く、それらの構造がどのくらい近いか距離を求めたい時は多くあります。

今回はテンプレート的なhtmlページを自動的に判断してクローリングするために Tree Edit Distance が必要になりました。

google の検索結果やぐるナビの詳細ページなどあるテンプレートを元にしたページのみをクローリングしたいとします。確かに個別にそれらのページを正規表現などで判断することも可能ですが、**目的のテンプレートページとリンク先のhtmlの木構造がどのくらい近いかを比べることで汎用的かつ効率的に判断できそうです。**なぜならばテンプレートで生成されたページはhtmlノードの中に記述されているテキストの中身は違えど html の構造自体はほとんど同じことが多いからです。

そのためには木構造の距離同士を比較する必要があります。

テキストの系列を比較する $ Edit Distance $ の木構造が版があれば上手くいくのではないか？を調べたら丁度いいアルゴリズムがありましたので紹介します。

計算方法

基本的には PFI の技術ブログで書かれている手法 を踏襲します。Klein の方法というみたいです。

以下では上記の技術ブログを読者が読んだ前提で、自分が工夫した点を中心に説明します。

このアルゴリズムを簡潔に実装するためには少し工夫が必要になります。森を表すために左と右の範囲を表す2つの数値を記憶させて再帰的に距離を求めるのですが、この二つの距離を閉区間ではなく半閉区間として記憶すると比較的簡単に記述することができます。つまり数値を

$$
[A, B]
$$

ではなく

$$
[A, B)
$$

として記憶させておきます。このように記憶させる理由は $ [A, B) $ をその間の値 $ C $ に分けて記述する際

$$
[A, B) = [A, C) \cup [C, B)
$$

と同じ半閉区間という性質を持つ2つの集合に分割できるからです。**再帰的に記述する際にはこのように2つの同じ属性をもった集合に分割できると例外を記述しなくて済みます。**2分探索などを半閉区間で実装すると簡潔に書けるのはこれと同じ理由です。

アルゴリズムに入る前にいくつか用語の定義をしておきます。森のそれぞれの木を $ T_1, T_2, ... T_n $ とした時に再帰的に距離を計算する際に必要となるのは $ T_n $ の範囲だけです。そこで森 $ F = \{T_1, ..., T_n\} $ を入力として最も右端の木でルートを除いた森を返す関数を $ Rtf(F) $ とします。 $ Rtf $ は $ RightmostForest $ の略称です。また森は帰りがけで番号を振ると2つの範囲だけを記憶しておけばよいので、それを $ [F.L, F.R) $ でそれぞれ範囲を表すことにします。

今回必要なのは $ F, Rtf(F) $ から以下の数値の範囲を求めることです。

• 最も右端の木の子供の部分 $ Children(T_n) $
• 右端の木を除いた $ \{T_1, ..., T_{n-1} \} $
• 右端の木のルート部分のみを除いた $ \{T_1, ..., T_{n-1}, Children(T_n)\} $

これらは全て以下のように 2 つの数値の範囲で表せます。

• 最も右端の木の子供の部分 $ Children(T_n) $ は $ [Rtf(F).L,~ Rt(F).R) $
• $ \{T_1, ..., T_{n-1}\} $ は $ [F.L,~Rtf(F).R) $
• 右端の木のルートを除いた部分 $ F = \{T_1, ..., T_{n-1}, Children(T_n) \} $ は $ [F.L,~Rtf(F).R) $

このようにすると元のアルゴリズムは

$$
\begin{eqnarray}
child_{distance} & = & d(\{Rtf(F1).L,~ Rtf(F1).R\},~ \{Rtf(F2).L,~ Rtf(F2).R\}) \
tailforest_{distance} & = & d(\{F1.L,~ Rtf(F1).L\},~ \{F2.L,~ Rtf(F2).L\}) \
d(F1, F2) & = & min \{ child_{distance} + tailforest_{distance} + 1, \
& & d(\{F1.L,~ Rtf(F1).R\},~ F2), \
& & d(F1,~ \{F2.L,~ Rtf(F2).R\}) \} \
d(F1, \{\}) & = & F1.R - F1.L \
d(\{\}, F2) & = & F2.R - F2.L \
\end{eqnarray}
$$

となります。
実際に計算させる際は $ (F1.R, F1.L, F2.L, F2.R) $ に対してメモ化を行わないといけません。

ソースコード

参考までに ruby のソースコードを載せておきます。 木構造は hash で表し、葉かどうかは最後に $ :end $ のシンボルが存在しているかどうかで判断しています。

# coding: utf-8
require 'digest/md5'

def intern(a, b)
  Digest::MD5.hexdigest("#{a}:#{b}")
end

class Node
  attr_accessor :children, :parent, :v
  def initialize(v, children)
    @v = v
    @children = children
    @parent = self
  end
  def allnodes
    [@parent] + @children
  end
  def count
    return 1 if self.children == []
    return @children.map {|x| x.count }.reduce(&:+) + 1
  end
  def dfs
    return self.v if self.children == []
    return self.children[0].dfs
  end
  def to_s
    v = "#{self.v[:index]}-#{self.v[:value]}"
    return v if self.children == []
    return "(#{v} [" + self.children.map {|x| x.to_s}.join(" ") + "])"
  end
end

def makeNode(parent)
  return [] if parent == :end
  parent.map do |k, child|
    Node.new(k, makeNode(child))
  end
end

def linkParent(node)
  return if node.children == :end
  node.children.each do |child|
    child.parent = node
    linkParent(child)
  end
end

def index(tree)
  @index_to_tree = []
  def inner(subtree, index)
    return index if subtree.children == :end
    subtree.children.each do |x|
      index = inner(x, index)
    end
    name = subtree.v
    subtree.v = {}
    subtree.v[:value] = name
    subtree.v[:index] = index
    @index_to_tree[index] = subtree
    return index + 1
  end
  inner(tree, 0)
  return tree, @index_to_tree
end

def makeTree(node)
  t, index = index(makeNode(node)[0])
  linkParent(t)
  return t, index
end

class Forest
  attr_accessor :index, :r, :l
  def initialize(l:, r:, index:)
    raise "error: l:#{l} > r:#{r}" if l > r
    @l = l
    @r = r
    @index = index
  end
  def rightmost_forest
    r = @r - 1
    trace = {r => true}
    t = r - 1
    loop do
      if t == -1
        break
      end
      parent = index[t].parent.v[:index]
      if trace.include? parent
        trace[t] = true
      else
        break
      end
      t -= 1
    end
    return {:l => (t + 1), :r => r}
  end
  def root
    @index[@r-1].v
  end
  def count
    @r - @l
  end
  def empty?
    @l == @r
  end
end

# xforest = [A, B)
def calc_ted_distance(xforest, yforest)
  x = intern(xforest.l, xforest.r)
  y = intern(yforest.l, yforest.r)

  @memo ||= {}
  @memo[x] ||= {}
  return @memo[x][y] if @memo[x].include? y
  
  return yforest.count if xforest.empty?
  return xforest.count if yforest.empty?

  xrtree = xforest.rightmost_forest
  yrtree = yforest.rightmost_forest
  
  a = calc_ted_distance(
    Forest.new(l: xrtree[:l],
               r: xrtree[:r],
               index: xforest.index),
    Forest.new(l: yrtree[:l],
               r: yrtree[:r],
               index: yforest.index)) # child 
  b = calc_ted_distance(
    Forest.new(l: xforest.l,
               r: xrtree[:l],
               index: xforest.index),
    Forest.new(l: yforest.l,
               r: yrtree[:l],
               index: yforest.index)) # neighbor
  p = if xforest.root[:value] == yforest.root[:value] then 0 else 1 end
  v1 = a + b + p
  v2 = calc_ted_distance(
    xforest,
    Forest.new(l: yforest.l,
               r: yrtree[:r],
               index: yforest.index)) + 1 # remove
  v3 = calc_ted_distance(
    Forest.new(l: xforest.l,
               r: xrtree[:r],
               index: xforest.index), # add
    yforest) + 1
  v = [v1, v2, v3].min
  p "(#{xforest.root[:value]} #{yforest.root[:value]})" +
    " #{xforest.l}:#{xforest.r}" +
    " #{yforest.l}:#{yforest.r}" +
    " #{v} [#{v1} #{v2} #{v3}] [#{a} #{b} #{p}]"
  return @memo[x][y] = v
end

def calc_ted(tree1, tree2)
  t1, i1 = makeTree(tree1)
  t2, i2 = makeTree(tree2)
  calc_ted_distance(
    Forest.new(l: 0, r: t1.count, index: i1),
    Forest.new(l: 0, r: t2.count, index: i2))
end

tree1 = {:a =>
         {:b =>
          {:d => {:l => {:m => :end, :n => :end}},
           :f => :end,
           :e => {:i => :end, :j => :end}},
          :c => {
            :g => {:o => {:p => {:q => :end}}, :r => :end},
            :s => :end,
            :h => {:k => :end,
                   :t => {:u => :end}}}}}

tree2 = {:a =>
         {:b =>
          {:d => :end,
           :f => :end,
           :x => :end,
           :e => {:i => :end, :j => :end}},
          :c => {
            :g => :end,
            :h => {:k => :end}}}}
p calc_ted(tree1, tree2)