こんにちは、ルーターアルバイトのkondoです。

スクレイピングというと、Web上のデータをクローラーで集めることを思い浮かべがちですが、クロールしたデータのパースや、集めたデータを集計することも忘れてはいけません。今回は、パース処理や集計の際に活用できる探索系のアルゴリズムを紹介します。

幅優先探索

幅優先探索とは、木構造などのグラフ形式のデータ構造を探索するアルゴリズムです。『要素を１つ選び、加工などをしたのち、その隣にある全ての要素についてこの『』の処理を適用する』、といったアルゴリズムで、グラフの全ての要素を探索できます。
HTMLは木構造なので、このアルゴリズムを活用することができます。始点の要素から始めて全ての子要素を見に行きたい、でも深さはまちまち、といったHTMLのパース処理に威力を発揮します。
具体的には、以下のような構造を便利にパースすることができるアルゴリズムです。図には探索する順番も書いておきました。

• 日本①
  • 東京都②
    • 渋谷区⑤
      • 代々木⑩
        • 4丁目⑬
        • 3丁目⑭
    • 北区⑥
      • 王子⑪
    • 足立区⑦
  • 埼玉県③
    • さいたま市⑧
      • 浦和⑫
    • 川口市⑨
  • 神奈川県④

幅優先探索の実装ですが、キュー(queue)を使う方法があるのでそれを紹介します。キューとは、要素を入れた順通りに取り出すことができるデータ構造で、Rubyでは配列をキューとして扱うことができるのでこれを利用します。再帰を使うやり方もあるのですが、処理の制御が難しいのでこのキューを使った方式です。
Array#prepend で配列先頭に要素を追加でき、Array#popで配列末尾から要素を取り出せます。

幅優先探索を利用して、先程のHTMLをいい感じにパースし、完全な地名に変換するコードを書いてみました。

<ul>
  <li>日本<ul>
      <li>東京都<ul>
          <li>渋谷区<ul>
              <li>代々木<ul>
                  <li>4丁目</li>
                  <li>3丁目</li>
                </ul>
              </li>
            </ul>
          </li>
          <li>北区<ul>
              <li>王子</li>
            </ul>
          </li>
          <li>足立区</li>
        </ul>
      </li>
      <li>埼玉県<ul>
          <li>さいたま市<ul>
              <li>浦和</li>
            </ul>
          </li>
          <li>川口市</li>
        </ul>
      </li>
      <li>神奈川県</li>
    </ul>
  </li>
</ul>

require 'nokogiri' # HTMLパーサーライブラリ
html = File.open('timei.html').read
doc  = Nokogiri::HTML.parse(html)

queue = [] # 配列をキューとして使えます
root_node = doc.at_css('li')
root_name = root_node.text.lines[0].chomp
queue << { element: root_node, name: root_name }

while node = queue.pop # 「ququeが空になるまで」はこのように書けます
  children = node[:element].css('> ul > li')
  if children.empty?
    p node[:name]
    next
  end
  children.each do |child|
    child_name = node[:name] + ' ' + child.text.lines[0].chomp
    queue.prepend(element: child, name: child_name) # queueに子要素を追加します
  end
end

結果はこのようになり、深さが浅い順に、全ての末端要素を見に行けていることが分かります。

$ ruby tansaku.rb
"日本 神奈川県"
"日本 東京都 足立区"
"日本 埼玉県 川口市"
"日本 東京都 北区 王子"
"日本 埼玉県 さいたま市 浦和"
"日本 東京都 渋谷区 代々木 4丁目"
"日本 東京都 渋谷区 代々木 3丁目"

二分探索

二分探索はパースのためのアルゴリズムというわけではなく、配列から目的の要素を短時間で検索することができるアルゴリズムです。

国語辞典での単語探しを例にこの方法を説明します。辞典から「ルーター」という単語を探したいとします。１ページ目から探して行く場合、辞書の分厚さに比例してページをめくる回数が増えていきます。「ル」は平仮名の後ろの方にあるのでなかなか見つからなそうです。
そうではなく、まず辞書の中央のページを開き、そこで出てきた「ナ」は「ル」よりも順序が小さい（ナ < ル）ため、次は「ナ 〜 ン」間の中央を探し、出てきた「レ」は「レ < ル」なので次は「ナ 〜 レ」を...
という具合に探していけば、ページは1/2づつ減っていくので、ページ数 N に対して log_2 N に比例する比較回数で探すことができます。例えば1024ページの場合は比較回数が10回になるわけで、とても高速です。
クロールしてきた大量のデータをrubyに読み込ませて、その中から探索を何度もする、といった状況のときに活用できるかと思います。

Rubyでの実装ですが、有り難いことにRubyには標準で二分探索をする Array#bsearch メソッドが備わっています。10^8 個のランダムな数字の配列からランダムに決めた別の値を探す処理を、ベンチマークテスト付きで書いてみました。

require 'benchmark'
arr = []
MAX = 10_000_000_000_000
10_000_000.times do
  arr << rand(MAX)
end
arr.sort! # 二分探索の前にはソートが必要です

Benchmark.bm 30 do |bench_mark|
  bench_mark.report 'bsearch' do
    arr.bsearch { |a| a > rand(MAX) }
  end
  bench_mark.report 'find' do
    arr.find { |a| a > rand(MAX) }
  end
end

$ ruby bsearch_test.rb
                                     user     system      total        real
bsearch                          0.000027   0.000004   0.000031 (  0.000023)
find                             0.001689   0.000001   0.001690 (  0.001696)

二分探索のほうが圧倒的に早いですね。注意点として、二分探索をする前に値のソートをする必要があります。このソートにかかる時間は、要素数 N に対して N log N に比例して増えていくので、少しの値を探すだけならfindメソッドの方が早いかと思います。

おわりに

普段気にしないで使っているモノの内側を知るのはなかなか楽しいです。紹介した探索方法がなにかのお役に立てば幸いです。