検索エンジンを作る 2: 実践!インデクシング

集合知プログラミング

集合知プログラミング

とりあえず前回の続きです。実際に手を動かして検索エンジンを作ってみます。

目的

僕のはてなブックマークしたサイト50個について、ページ内の単語での検索を行えるようにします。

インデクシング

検索エンジンを作る第一歩として、まず「インデクシング」を行います。その為に、情報を保存する用のDBを用意しましょう。

DBの用意

インデクシングの為に、ページの「url」、単語の「位置」と「種類」をDBに保存します。必要なテーブルはpagesテーブル、wordsテーブル、そしてword_locationsテーブルの3つです。word_locationsテーブルがpageとwordをつなく多対多の中間テーブルの役割をしながら、同時に単語のページ内での「出現位置」の情報も持ちます。「出現位置」としては、具体的にはページ内の文書を分かち書きしたときの、空白を挟んで何個目かという「数字」を用いる事にします。ページ内の文書は、テキストノードを全て集めたものとします。

今回は、ORMとしてDataMapperを使います。僕も初めて使うのでまだ何がすごいか良く分かってないですが、噂では何かすごいらしいです。

参考 http://d.hatena.ne.jp/kwatch/20080531/1212228883 http://krdlab.hatenablog.com/entry/20090517/1242564102

とりあえず、テーブルスキーマを設定しましょう。DataMapperでは、Modelの定義を書くだけで(!)スキーマの設定が完了します。migrationファイルを別途作らなくても、Modelの定義からスキーマを汲み取ってテーブルを作成してくれます。

require 'data_mapper'
require 'dm-timestamps'

DataMapper::Logger.new('log/dm.log', :debug)
DataMapper.setup(:default, 'postgres://(ユーザー名)@localhost/(ユーザー名)')

class Page
  include DataMapper::Resource

  property :id,         Serial
  property :url,        String, required: true, unique_index: true, length: 1..200
  property :created_at, DateTime

  has n, :word_locations
  has n, :words, through: :word_locations
end

class Word
  include DataMapper::Resource

  property :id,         Serial
  property :word,       String, required: true, unique_index: true, length: 1..50
  property :created_at, DateTime

  has n, :word_locations
  has n, :pages, through: :word_locations
end

class WordLocation
  include DataMapper::Resource

  property :id,         Serial
  property :location,   Integer
  property :created_at, DateTime

  belongs_to :page
  belongs_to :word
end

DataMapper.finalize
DataMapper.auto_upgrade!

DataMapperをsetupしてから、ModelクラスのUrl, Word, WordLocationを定義し、DataMapper.finalizeでModelの定義やロガー、接続先DBの設定を終了します。最後にDataMapper.auto_upgrade!でmigrationを行います。このファイルをrubyで実行するだけで、ちゃんとテーブルが作られます。

実際に、terminalからpostgresqlを起動してちゃんとテーブルが作られているか確認してみましょう。

$ psql
(ユーザー名)=# \d
                 List of relations
 Schema |         Name          |   Type   | Owner
--------+-----------------------+----------+--------
 public | pages                  | table    | (ユーザー名)
 public | pages_id_seq           | sequence | (ユーザー名)
 public | word_locations        | table    | (ユーザー名)
 public | word_locations_id_seq | sequence | (ユーザー名)
 public | words                 | table    | (ユーザー名)
 public | words_id_seq          | sequence | (ユーザー名)
(6 rows)

pages, word_locations, wordsテーブルがそれぞれつくられている事が分かります。(あと、auto incrementされるid用にテーブルも作られるっぽいですね)

素晴らしい!!

ページ内の単語を取得

次は、ページからの「単語の集合」の取得に挑戦しましょう。

get_words_from(url)は、渡されたurl内の文書に含まれる「単語の集合」を返す関数です。mechanizeを使って対象ページのHTMLをパースした形で取得し、get_text関数で再帰的にノードをたどってテキストノードを集めます。その際、scriptタグ内のjsコードは文書に含めたくないので、if分岐で弾くようにしています。 テキストノードを連結して一つの文書を作った後、MeCabでparseして分かち書き(単語を空白文字で区切った文書)の形をつくり、さらにsplitする事で単語の集合へと変換しています。

require 'mechanize'
require 'mecab'

def get_text(node)
  return ''        if node.name == 'script'
  return node.text if node.text?
  node.children.map { |child| get_text(child) }.join("\n")
end

def get_words_from(url)
  agent = Mechanize.new
  agent.get(url)
  text = get_text(agent.page.root)
  m = MeCab::Tagger.new('-O wakati')
  m.parse(text).split
end

MeCabの動きは、以下のコードが分かり易いかもです。parseメソッド分かち書きした結果が返されるのが分かるかと思います。

require 'mecab'

m = MeCab::Tagger.new('-O wakati')
p m.parse('今日もこれをやらないと')
# >> "今日 も これ を やら ない と \n"

インデクシングを行う

それでは、上記までの準備を経て、いよいよインデクシングを行いたいと思います。といっても、urlから単語を取得するところまでは出来ているので、後はそれをDBに保存していくだけです。

require './get_words_from_url.rb'
require './model_and_migrate.rb'

def save_page_with(url)
  page = Page.first_or_create(url: url)
  return nil if page.word_locations != []
  get_words_from(url).each_with_index do |w, i|
    WordLocation.create(
      page:     page,
      word:     Word.first_or_create(word: w),
      location: i
    )
  end
rescue => e
  p "[ERROR]: #{e.message}"
end

def save_all_page
  YAML.load_file('./south37.yaml').each do |url|
    save_page_with url
    p url
  end
end

save_all_page

save_page_with(url)メソッドが、渡されたurlのページのインデクシングを行うメソッドです。

DataMapperもActiveRecordと似た感じでfirst_or_createメソッドを使ってDBへの保存を行えるようです。first_or_createメソッドは一度keyでの検索を行ってDBに存在しなければ新しくDBにデータを保存してくれるというもので、かなり使い勝手の良いメソッドです。上記の例ではurlをkeyにしたPageオブジェクトの保存と、wordをkeyにしたWordオブジェクトの保存を行っています。

このスクリプトを実行する事で、インデクシングは完了です。

結果

とりあえず、何か適当な単語で検索してみましょう。"JavaScript"という単語で検索してみます。

pry(main)> word = Word.first(word: 'JavaScript')
=> #<Word @id=1 @word="JavaScript" @created_at=#<DateTime: 2014-06-15T08:38:08+09:00 ((2456823j,85088s,0n),+32400s,2299161j)>>
pry(main)> word.pages.map { |page| page.url }
=> ["http://blog.manaten.net/entry/797",
 "http://www.webcreatorbox.com/tech/basic-wireframe/",
 "http://www.buildinsider.net/web/quicktypescript/01",
 "http://starzero.hatenablog.com/entry/2014/04/27/123217",
 "http://manimani-rider.com/book-before-startup/",
 "http://next.rikunabi.com/tech/docs/ct_s03600.jsp?p=002133",
 "http://beatsync.net/main/log20130428.html",
 "http://shin.hateblo.jp/entry/2013/01/22/175926",
 "http://hamalog.tumblr.com/post/33224067076/coffeescript-2",
 "http://team-work.jp/feature/2662.html",
 "http://www.eisbahn.jp/yoichiro/2012/11/ruby_rails_dojo_web_app_design_pattern.html",
 "http://d.hatena.ne.jp/maeharin/20131226/backbone_js_rails_initialize_rule",
 "http://d.hatena.ne.jp/h_mori/20120626/1340682681",
 "http://qiita.com/atskimura/items/60e9cc6638ca1d0754df",
 "http://nantokaworks.com/p1047/",
 "http://be-hase.com/javascript/248/",
 "http://appkitbox.com/knowledge/category/javascript",
 "http://engineering.crocos.jp/post/26950144374/failed-to-get-access-token-by-using-fbsr",
 "http://www.msng.info/archives/2012/10/facebook-login-with-php.php",
 "http://qiita.com/alpaca_taichou/items/ab2ad83ddbaf2f6ce7fb",
 "http://qiita.com/joker1007/items/9c114a37560d6a29fe81",
 "http://www.nodebeginner.org/index-jp.html#javascript-and-nodejs",
 "http://qiita.com/mrkn/items/d2fa3f3eabedb7d9a332",
 "http://qiita.com/taiki45/items/b46a2f32248720ec2bae"]
pry(main)> word.pages.size
=> 24

JavaScriptという単語を含むpageの集合をちゃんと取得出来てますね。そういったpageが24個ある事も分かります。まあ、これを検索と呼ぶかどうかはかなり微妙ですが、とりあえず足がかりは出来ました。第一歩としてはいいんじゃ無いでしょうか!!!

次からは、ランキングのアルゴリズムを用いる事で、関連性の強いページが検索結果の上位に現れるようにしてみようと思います。また、今回はただURLを並べるだけになっちゃいましたが、Googleの検索結果っぽくキーワードの前後の文章が見えるようにするなど結果の表示方法に工夫を凝らすのも面白いかもしれません。