読者です 読者をやめる 読者になる 読者になる

検索エンジンを作る 3: ページのランキング

さて、前回はインデクシングを行い、ページのランク付けの為に必要な情報をDBに保存しました。今回は実際にランク付けを行ってみます。

ランキングのアルゴリズム

ランキングのアルゴリズムとして、即座に思い浮かぶのは次の3つだと思います。

  1. 単語の出現頻度を利用したアルゴリズム
  2. 単語の出現位置を利用したアルゴリズム
  3. 単語間の距離を利用したアルゴリズム

それぞれ、書籍「集合知プログラミング」にて実際にコード付きで解説されており、それを参考に自分でも実装してみました。

書いたコード

  1 require './model.rb'
  2 require 'active_support/core_ext'
  3
  4 # words_queryは、検索単語を半角スペースで繋いだもの
  5 # ex. 'JavaScript ruby'
  6 def get_pages(words_query)
  7   words = words_query.split
  8   return [] if words == []
  9   words.map { |word| Word.first(word: word).try(:pages) || [] }.reduce(:&)
 10 end
 11
 12 def get_frequency_scores(words_query, pages = nil)
 13   page_ids = (pages || get_pages(words_query)).map(&:id)
 14   return {} if page_ids == []
 15   result = {}
 16   words_query.split.each do |word|
 17     # select page_id, count(*) group by page_id where word_id = (wordのid) の結果が返る
 18     WordLocation.aggregate(:page_id, :all.count, word: Word.first(word: word)).each do |page_id, count|
 19       result[page_id] = (result[page_id] || 0) + count if page_ids.include?(page_id)
 20     end
 21   end
 22   max_count = result.values.max.to_f
 23   result.map { |k, v| [k, v / max_count] }.to_h
 24 end
 25
 26 def get_location_scores(words_query, pages = nil)
 27   page_ids = (pages || get_pages(words_query)).map(&:id)
 28   return {} if page_ids == []
 29   locations = {}
 30   words_query.split.each do |word|
 31     WordLocation.all(word: Word.first(word: word)).each do |word_location|
 32       page_id = word_location.page_id
 33       next unless page_ids.include?(page_id)
 34       locations[page_id]       ||= {}
 35       locations[page_id][word] ||= Float::INFINITY
 36       locations[page_id][word] = word_location.location if word_location.location < locations[page_id][word]
 37     end
 38   end
 39   result = {}
 40   locations.each do |page_id, word_top_locations|
 41     result[page_id] = word_top_locations.values.inject(:+)
 42   end
 43   min_score = result.values.min.to_f
 44   result.map { |k, v| [k, (min_score + 1) / (v + 1)] }.to_h # 0除算を避けるための +1
 45 end
 46
 47 WEIGHTED_SCORING_METHODS = {
 48  :get_frequency_scores => 1.0,
 49  :get_location_scores  => 1.5
 50 }
 51
 52 def get_total_scores(words_query, pages = nil)
 53   pages ||= get_pages(words_query)
 54   total_scores = {}
 55   WEIGHTED_SCORING_METHODS.each do |method, weight|
 56     scores = Kernel.send(method, words_query, pages)
 57     scores.each do |page_id, score|
 58       total_scores[page_id] ||= 0
 59       total_scores[page_id] += weight * score
 60     end
 61   end
 62   total_scores
 63 end
 64
 65 def get_pages_with_score(words_query)
 66   pages = get_pages(words_query)
 67   total_scores = get_total_scores(words_query, pages)
 68   pages.map { |page| [page, total_scores[page.id]] }.sort_by { |_, score| score }.reverse
 69 end

簡単な解説

get_pages_with_scoreメソッドがスコアを利用して順序づけたpageの集合を返します。検索用クエリとしては、半角スベースで検索したい単語をつないだ文字列を使用します。

pry(main)> get_pages_with_score('JavaScript')
=> [[#<Page @id=1 @url="http://blog.manaten.net/entry/797" @created_at=Sun, 15 Jun 2014 23:10:40 +0900>,
  1.627659574468085],
 [#<Page @id=34 @url="http://be-hase.com/javascript/248/" @created_at=Sun, 15 Jun 2014 23:19:20 +0900>,
  1.0797872340425532],
 [#<Page @id=45 @url="http://www.nodebeginner.org/index-jp.html#javascript-and-nodejs" @created_at=Sun, 15 Jun 2014 23:21:41 +0900>,
  1.010204081632653],
 [#<Page @id=3 @url="http://www.buildinsider.net/web/quicktypescript/01" @created_at=Sun, 15 Jun 2014 23:10:57 +0900>,
  0.5379110251450676],
...
]

スコアとしては、単語の出現頻度によるスコア(get_frequency_scoresで取得)と単語の出現位置によるスコア(get_position_scoresで取得)を重み付きで足し合わせたものを利用しています。用いるスコア付けメソッドと重みはWEIGHTED_SCORING_METHODS定数で指定しています。

検索結果は悪く無い気がします!!

ちょっと問題点

出現頻度と出現位置によるスコア付けはこれでOKなのですが、単語間の距離を用いた実装で詰まってしまいました。 今はDataMapperというORM越しに、検索に用いたwordごとにword_locationの集合を取得するとった方法をとっているのですが、その場合に全ての単語間の距離を求めようとするとO(取得したword_location数word数乗)という計算量の計算が必要になってしまいます。 ruby側でこういった計算はあまりやりたくないです...

集合知プログラミング」のアプローチ

ちなみに、「集合知プログラミング」では最初にword_locationの集合を取得する時に、一気に計算を行っています。こんな感じのSQL文を発行するようです。

select w0.page_id, w0.location, w1.location
from word_locations w0, word_locations w1
where w0.page_id = w1.page_id
and w0.word_id = 1
and w1.word_id = 2

これはword_id12の二つの単語をクエリとして用いた検索で、page_idが一致するようなword_locationの組み合わせを片っ端から取得します。

fromで2つのword_locationsテーブルから検索を行っており、Nの2乗個の要素から条件に合致するものを見つけ出してきている事が分かります。検索用の単語が3個、4個と増えていけばこれが3乗、4乗と増えて行く事になります。実際にはpage_idword_idにはindexが貼られているため、Nの何乗みたいな事にはなりません。

ただ、取得したword_location同士でのpage_idの一致判定は避けられず、同じ事をrubyでやるのはしんどい気がします。

じゃあ同じ様なSQL使えばいいって話になるんですが、せっかくORM使ってるんでこういったSQL文を文字列で組み立てる様な事はしたくなくて、ちょっと詰まっています。このへん、スッキリ解決したらまた追記しとこうと思います。

まとめ

インデクシングでDBに保存したデータを使う事で、ランク付けされた検索結果が返せるようになりました。単語の出現頻度や出現位置といった単純な評価基準によるアルゴリズムでも、そこそこ悪く無い結果が出る事が分かりました。

シンプルな方法でもそこそこ良い結果が得られて、素晴らしいですね!!

追記

単語間の距離からのscore算出もしてみました。結局、DataMappe越しで複雑なSQL発行するのは諦めて、ruby側でループする感じにしていますw

 47 def get_distance_scores(words_query, pages = nil)
 48   page_ids = (pages || get_pages(words_query)).map(&:id)
 49   return {} if page_ids == []
 50   locations = {}
 51   words = words_query.split
 52   return page_ids.map { |page_id| [page_id, 1.0] }.to_h if words.size < 2
 53   words.each do |word|
 54     WordLocation.all(word: Word.first(word: word)).each do |word_location|
 55       page_id = word_location.page_id
 56       next unless page_ids.include?(page_id)
 57       locations[page_id]       ||= {}
 58       locations[page_id][word] ||= []
 59       locations[page_id][word] << word_location.location
 60     end
 61   end
 62   result = {}
 63   page_ids.each do |page_id|
 64     # page_idごとに、word_locationの組み合わせの集合を作る
 65     # [[word1_location, word2_location, word3_location], ...]
 66     locations[page_id].values.inject(:product).map(&:flatten).each do |word_locations|
 67       distance = word_locations.each_cons(2).map { |a, b| (a - b).abs }.reduce(:+)
 68       result[page_id] ||= distance
 69       result[page_id] = distance if distance < result[page_id]
 70     end
 71   end
 72   min_score = result.values.min.to_f
 73   result.map { |k, v| [k, (min_score + 1) / (v + 1)] }.to_h # 0除算を避けるための +1
 74 end