検索エンジンを作る 3: ページのランキング
さて、前回はインデクシングを行い、ページのランク付けの為に必要な情報をDBに保存しました。今回は実際にランク付けを行ってみます。
ランキングのアルゴリズム
ランキングのアルゴリズムとして、即座に思い浮かぶのは次の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_idが1と2の二つの単語をクエリとして用いた検索で、page_idが一致するようなword_locationの組み合わせを片っ端から取得します。
fromで2つのword_locationsテーブルから検索を行っており、Nの2乗個の要素から条件に合致するものを見つけ出してきている事が分かります。検索用の単語が3個、4個と増えていけばこれが3乗、4乗と増えて行く事になります。実際にはpage_idやword_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
