| @技術/プログラミング

MySQL だけでお手軽に全文検索ができるということを知らなかった。 MySQL 5.6 から入っていたようだった。 Tantivy および Tantiny を使ったやり方を以前記事に書いてサイトで実装しているが、 MeCab によるトークナイズでは二文字の熟語がセットになって四文字になっているようなパターンを取り逃すことがあった(「関連記事」は「関連」と「記事」に分割され、「関連」や「記事」というキーワードで検索したときにはヒットするが「関連記事」で検索するとヒットしない)し、記事追加時の検索インデックス更新処理が不要( MySQL にレコードが追加されたときに勝手に更新される)なので試してみることにした。

やり方は以下の記事を参考にした。

最初にデータベースに全文検索用のインデックスを作成した。

ALTER TABLE `entries` ADD FULLTEXT INDEX index_entry_fulltext(title, body) WITH PARSER ngram;

その後、検索部分のコードを書き換えて以下のようにした。

class Entry < ActiveRecord::Base
  scope :search,
        ->(words) {
          return all if words.blank?
          where('MATCH (entries.title, entries.body) AGAINST (? in BOOLEAN MODE)', words)
        }
end

めっちゃ簡単。

このブログは記事数が 1500 記事くらいなのでぶっちゃけ LIKE 検索でも実用的な速度( 100msec 以内)で結果を取得できるが、 FULLTEXT インデックスを使うと 10msec 程度で結果を取得できる。

ただし Tantivy と比べて劣る点もあって以下は注意が必要。

  1. なぜかわからないが Vim で検索すると何もヒットしない。また Rails で検索すると Rails について触れていない記事もヒットする。 ngram によるインデックスというのはこんなものなのかもしれない。検索ワードが日本語のときはいい感じに結果が表示される。
  2. 複数のテーブルにまたがるデータを一個の検索インデックスにまとめることができない。例えば Tantivy のインデックスは記事のタイトル、本文、カテゴリー、タグをインデックス対象としているが、 MySQL の FULLTEXT インデックスだとテーブルごとにしかインデックスを作れないので(当たり前)、複数のテーブルにまたがる検索をするときにはテーブルを JOIN するしかない。 OR マッパーを使っている場合には利用しづらい。

1 の問題に関しては、 MySQL 5.7 からインデックス生成時の PARSER に MeCab などを指定できるようになったのでそうすると回避できるかもしれない。ただし MeCab のインストールや設定を行う必要があるので要注意。

2 の問題に関しては全文検索システムを入れた方が良さげ。 Tantivy であれば非常に簡単に導入できる。

現状、このサイトでは右上の検索窓から検索したときのインクリメンタルサーチとアーカイブページでの絞り込みは Tantivy を、インクリメンタルサーチの結果で必要な情報が得られなかったときの「全文検索する」と 404 Not Found ページの検索は MySQL の全文検索を使うようにしている。

二つの検索

| @技術/プログラミング

Rust 製の全文検索システム Tantivy を Ruby から使える Tantiny を導入したことを書いた。

結構手軽に使えるのだがやはり日本語のトークナイズ(形態素解析)ができないのでいまいちなところがあった。 Tantivy には lindera-tantivy というものがあって、 Lindera は kuromoji のポートなので、これを使うと日本語や中国語、韓国語の形態素解析ができる。 Tantiny に導入できないか試してみたが、自分の Rust 力では到底無理だった。

ちなみに関連記事の表示でも日本語の形態素解析は行っている。

MeCab に neologd/mecab-ipadic-neologd を組み合わせてナウな日本語に対応させつつ形態素解析している。

この仕組みを作ってトークナイズは Ruby で自前で行い、 Tantiny および Tantivy にはトークナイズ済みの配列を食わせるだけにした( Tantiny はトークナイズ済みのテキストを受け付けることもできる)。トークナイズを自前で行うことで辞書ファイルで拾いきれないような固有名詞もカバーできる。例えば 山と道 なんかは MeCab と mecab-ipadic-neologd にトークナイズさせると に分割されてしまう。自前のトークナイザーで単語として認識させていている。おかげで「山と道」をちゃんと検索できるようになっている

なお、自前のトークナイザーはこんなコードになっている。

class Tokenizer
  attr_reader :text

  class << self
    def run(text)
      self.new(text).tokenize
    end
  end

  def initialize(text)
    @text = text
  end

  def cleansed_text
    @cleansed_ ||= text.
      gsub(/<.+?>/, '').
      gsub(/!?\[(.+)?\].+?\)/, '\1').
      gsub(%r{(?:```|<code>)(.+?)(?:```|</code>)}m, '\1')
  end

  def words_to_ignore
    @words_to_ignore ||= %w[
      これ こと とき よう そう やつ とこ ところ 用 もの はず みたい たち いま 後 確か 中 気 方
      頃 上 先 点 前 一 内 lt gt ここ なか どこ まま わけ ため 的 それ あと
    ]
  end

  def preserved_words
    @preserved_words ||= %w[
      山と道 ハイキング 縦走 散歩 プログラミング はてブ 鐘撞山 散財 はてなブックマーク はてな
    ]
  end

  def nm
    require 'natto'
    @nm ||= Natto::MeCab.new
  end

  def words
    @words ||= []
  end

  def tokenize
    preserved_words.each do |word|
      words << word if cleansed_text.match?(word)
    end

    nm.parse(cleansed_text) do |n|
      next unless n.feature.match?(/名詞/)
      next if n.feature.match?(/(サ変接続|数)/)
      next if n.surface.match?(/\A([a-z][0-9]|\p{hiragana}|\p{katakana})\Z/i)
      next if words_to_ignore.include?(n.surface)
      words << n.surface
    end

    words
  end
end

preserved_words が手製の辞書だ。 はてなはてブ も辞書登録しておかないと MeCab だとバラバラに分割されてしまって検索できなかった。

難点としては記事更新後に自動でインデックスの更新が行われず、 cron によるバッチ処理でインデックス更新を行っている[1]。なので検索インデックスにデータが反映されるまでにタイムラグがある。 Tantiny でやれれば記事作成・更新時のコールバックとして処理できるのでリアルタイムに変更を検索インデックスに反映させることができるが、個人の日記なのでタイムラグありでも大きな問題にはならない。

本当は Tantiny で lindera-tantivy を使えるようにして Pull Request がカッチョイイのだが、とりあえずは自分は目的が達成できたので満足してしまった。 5 年くらい前から Rust 勉強したいと思っているが、いつまでも経っても Rust を書けるようにはならない。

[1]: mecab-ipadic-neologd を VPS 上でインストールできず(めっちゃメモリを使う)、手元の Mac で Docker コンテナ化して Docker Hub 経由でコンテナイメージを Pull して VPS 上で Docker 経由で動かしている(その辺について書いてる記事: ブログのコンテナ化を試みたけどやめた

| @技術/プログラミング

ブログ過去記事の閲覧 UI にはこだわりがある。これまで何度か記事を書いた。

このブログの維持管理で一番時間を割いているのが Archives ページだ。しかしアクセスログを見ると自分以外はほとんど利用していない。完全に自己満なのだが、過去の自分を振り返ることができてとても自分には有意義なページだ。

過去記事を振り返るときには検索をしたくなる。タイトルのみであればページ内検索で探せるが、やっぱり本文込みで検索したい。 Lokka の検索はあるが、検索結果ページは 7 件ずつ(この値はカスタマイズできる)表示で全文表示される。自分は検索キーワードに関する記事が存在するか知りたい訳ではない。著者なのでキーワードに関連する記事があるかないかくらいわかってる。じゃなくて過去の自分がいつ頃どの密度でそのトピックについて書いていたかを知りたいのだ。

タグやカテゴリーで絞り込む手もある。しかしカテゴリーやタグは理想的な分類ではない。二つのカテゴリーを横断するような記事があるし、タグは設定し忘れていることが多い。全文検索が一番頼りになる。

SQL で全文検索的なことをやろうとするとパフォーマンスが良くないだろう。やっぱり全文検索システムが欲しい。

Tantivy と Tantiny

とはいえ、個人のブログで全文検索エンジンを導入するのはしんどい。確かに Apache Solr や Elasticsearch を個人ブログに入れるのはきつい。もっと手軽に使えるものはないか探していて、 Rust 製の全文検索システム Tantivy と、その Ruby クライアントの Tantiny を発見した。

これがめっちゃ簡単で昨日数時間サンデープログラミングをして導入できた。システム環境に適合するビルド済みのバイナリが GitHub にあれば Rust 環境のセットアップすら必要ない。 Gemfile に gem 'tantiny' と書いて bundle install するだけで使えてしまう。

うまくいかなかったもの

最初、同じ Rust 製で Wasm までセットで提供してくれる tinysearch を試した。 JSON 形式で全ファイルを書き出すだけで使えるやつだ。しかし残念なことに日本語では全く使えなかった。自然言語処理をやろうとしていてあるあるのパターンだ。日本語は MeCab などでトークナイズしてやる必要がある。

デフォルトのトークナイザーでもそこそこに優秀な Tantivy

Tantivy にもトークナイザーをカスタマイズできる仕組みはあるが、標準の Simple Tokenizer でもそこそこ精度が高い。固有名詞にちょっと弱いが、辞書ファイルがないので仕方ないだろう。

個人ブログでも全文検索できる時代

このブログは個人ブログだが、画像のリアルタイムリサイズサーバーを動かしている(おかげで S3 の転送量が安くて済んでいる)し、 TF-IDF で関連の高い記事も表示している。それに加えて全文検索まで入れてしまった。こういうのは大手のブログサービスを利用しないと使えない機能だったが、 OSS と新しいプログラミング言語( Go や Rust )のおかげで個人でもそこそこのスペックのサーバーでこれらを利用することができるようになってきた。 MovableType でサイトを構築していた時代から何も進歩していないようで実はとても進歩している。こういう文化の灯火が消えないようにしていきたい。

| @技術/プログラミング

Lokka の検索はキーワード一つにしか対応していなかった。例えば うどん ラーメン と入力すると、確実に うどん ラーメン という語順で検索が行われる仕様になっている。これはちょっと不便だと思ったので半角スペースでキーワードを分割して AND 検索するようにした。つまり確かに うどん ラーメン という語順で文章が書かれていなくても、 ラーメン うどん という語順だったり、そもそも うどんラーメン が離れたところに書いてあるような文章でもオッケーな仕様にした。 diff はこんな感じ。

一般的な検索システムだと入力された検索キーワードを品詞分解したりして半角スペース入れたりせずともいい感じに検索できるのだろうが、データベースから直接検索するシステムではこれくらいできれば十分かなと思ってる。どうせこのブログで検索してるの自分一人くらいだし。

| @技術/プログラミング

cho45 さんの以下の記事を参考に関連記事を表示するようにしてみた。

ほとんど cho45 さんの記事に書いてある SQL を実行しているだけだけど、関連記事の表示用に Lokka 側に Similarity というモデルを追加して、以下のようなスキーマにしてる。

similar-entries-erd.png

Similarity テーブルの更新は cho45 さんの記事にあるように SQLite で行った計算の結果を反映することで行う。以下のような Rake タスクを定義した。

desc "Detect and update similar entries"
task similar_entries: %i[similar_entries:extract_term similar_entries:vector_normalize similar_entries:export]

namespace :similar_entries do
  require 'sqlite3'
  desc "Extract term"
  task :extract_term do
    require 'natto'
    nm = Natto::MeCab.new
    db = SQLite3::Database.new('db/tfidf.sqlite3')
    create_table_sql =<<~SQL
      DROP TABLE IF EXISTS tfidf;
      CREATE TABLE tfidf (
        `id` INTEGER PRIMARY KEY,
        `term` TEXT NOT NULL,
        `entry_id` INTEGER NOT NULL,
        `term_count` INTEGER NOT NULL DEFAULT 0, -- エントリ内でのターム出現回数
        `tfidf` FLOAT NOT NULL DEFAULT 0, -- 正規化前の TF-IDF
        `tfidf_n` FLOAT NOT NULL DEFAULT 0 -- ベクトル正規化した TF-IDF
      );
      CREATE UNIQUE INDEX index_tf_term ON tfidf (`term`, `entry_id`);
      CREATE INDEX index_tf_entry_id ON tfidf (`entry_id`);
    SQL
    db.execute_batch(create_table_sql)

    entries = Entry.published.all(fields: [:id, :body])
    entry_frequencies = {}
    entries.each do |entry|
      words = []
      body_cleansed = entry.body.
        gsub(/<.+?>/, '').
        gsub(/!?\[.+?\)/, '').
        gsub(/(```|<code>).+?(```|<\/code>)/m, '')
      begin
        nm.parse(body_cleansed) do |n|
          next if !n.feature.match(/名詞/)
          next if n.feature.match(/(サ変接続|数)/)
          next if n.surface.match(/\A([a-z][0-9]|\p{hiragana}|\p{katakana})\Z/i)
          next if %w[これ こと とき よう そう やつ とこ ところ 用 もの はず みたい たち いま 後 確か 中 気 方 頃 上 先 点 前 一 内 lt gt ここ なか どこ まま わけ ため 的 それ あと].include?(n.surface)
          words << n.surface
        end
      rescue ArgumentError
        next
      end
      frequency = words.inject(Hash.new(0)) {|sum, word| sum[word] += 1; sum }
      entry_frequencies[entry.id] = frequency
    end
    entry_frequencies.each do |entry_id, frequency|
      frequency.each do |word, count|
        db.execute("INSERT INTO tfidf (`term`, `entry_id`, `term_count`) VALUES (?, ?, ?)", [word, entry_id, count])
      end
    end
  end

  desc "Vector Normalize"
  task :vector_normalize do
    db = SQLite3::Database.new('db/tfidf.sqlite3')

    load_extension_sql =<<~SQL
      -- SQRT や LOG を使いたいので
      SELECT load_extension('/usr/local/Cellar/sqlite/3.21.0/lib/libsqlitefunctions.dylib');
    SQL
    db.enable_load_extension(true)
    db.execute(load_extension_sql)

    update_tfidf_column_sql = <<~SQL
      -- エントリ数をカウントしておきます
      -- SQLite には変数がないので一時テーブルにいれます
      CREATE TEMPORARY TABLE entry_total AS
          SELECT CAST(COUNT(DISTINCT entry_id) AS REAL) AS value FROM tfidf;

      -- ワード(ターム)が出てくるエントリ数を数えておきます
      -- term と entry_id でユニークなテーブルなのでこれでエントリ数になります
      CREATE TEMPORARY TABLE term_counts AS
          SELECT term, CAST(COUNT(*) AS REAL) AS cnt FROM tfidf GROUP BY term;
      CREATE INDEX temp.term_counts_term ON term_counts (term);

      -- エントリごとの合計ワード数を数えておきます
      CREATE TEMPORARY TABLE entry_term_counts AS
          SELECT entry_id, LOG(CAST(SUM(term_count) AS REAL)) AS cnt FROM tfidf GROUP BY entry_id;
      CREATE INDEX temp.entry_term_counts_entry_id ON entry_term_counts (entry_id);

      -- TF-IDF を計算して埋めます
      -- ここまでで作った一時テーブルからひいて計算しています。
      UPDATE tfidf SET tfidf = IFNULL(
          -- tf (normalized with Harman method)
          (
              LOG(CAST(term_count AS REAL) + 1) -- term_count in an entry
              /
              (SELECT cnt FROM entry_term_counts WHERE entry_term_counts.entry_id = tfidf.entry_id) -- total term count in an entry
          )
          *
          -- idf (normalized with Sparck Jones method)
          (1 + LOG(
              (SELECT value FROM entry_total) -- total
              /
              (SELECT cnt FROM term_counts WHERE term_counts.term = tfidf.term) -- term entry count
          ))
      , 0.0);
    SQL
    db.execute_batch(update_tfidf_column_sql)

    vector_normalize_sql = <<~SQL
      -- エントリごとのTF-IDFのベクトルの大きさを求めておきます
      CREATE TEMPORARY TABLE tfidf_size AS
          SELECT entry_id, SQRT(SUM(tfidf * tfidf)) AS size FROM tfidf
          GROUP BY entry_id;
      CREATE INDEX temp.tfidf_size_entry_id ON tfidf_size (entry_id);

      -- 計算済みの TF-IDF をベクトルの大きさで割って正規化します
      UPDATE tfidf SET tfidf_n = IFNULL(tfidf / (SELECT size FROM tfidf_size WHERE entry_id = tfidf.entry_id), 0.0);
    SQL
    db.execute_batch(vector_normalize_sql)
  end

  desc "Export calculation result to MySQL"
  task :export do
    db = SQLite3::Database.new('db/tfidf.sqlite3')
    create_similar_candidate_sql = <<~SQL
      DROP TABLE IF EXISTS similar_candidate;
      DROP INDEX IF EXISTS index_sc_parent_id;
      DROP INDEX IF EXISTS index_sc_entry_id;
      DROP INDEX IF EXISTS index_sc_cnt;
      CREATE TABLE similar_candidate (
        `id` INTEGER PRIMARY KEY,
        `parent_id` INTEGER NOT NULL,
        `entry_id` INTEGER NOT NULL,
        `cnt` INTEGER NOT NULL DEFAULT 0
      );
      CREATE INDEX index_sc_parent_id ON similar_candidate (parent_id);
      CREATE INDEX index_sc_entry_id ON similar_candidate (entry_id);
      CREATE INDEX index_sc_cnt ON similar_candidate (cnt);
    SQL
    db.execute_batch(create_similar_candidate_sql)

    extract_similar_entries_sql = <<~SQL
      -- 類似していそうなエントリを共通語ベースでまず100エントリほど出します
      INSERT INTO similar_candidate (`parent_id`, `entry_id`, `cnt`)
          SELECT ? as parent_id, entry_id, COUNT(*) as cnt FROM tfidf
          WHERE
              entry_id <> ? AND
              term IN (
                  SELECT term FROM tfidf WHERE entry_id = ?
                  ORDER BY tfidf DESC
                  LIMIT 50
              )
          GROUP BY entry_id
          HAVING cnt > 3
          ORDER BY cnt DESC
          LIMIT 100;
    SQL

    search_similar_entries_sql = <<~SQL
      -- 該当する100件に対してスコアを計算してソートします
      SELECT
          ? AS entry_id,
          entry_id AS similar_entry_id,
          SUM(a.tfidf_n * b.tfidf_n) AS score
      FROM (
          (SELECT term, tfidf_n FROM tfidf WHERE entry_id = ? ORDER BY tfidf DESC LIMIT 50) as a
          INNER JOIN
          (SELECT entry_id, term, tfidf_n FROM tfidf WHERE entry_id IN (SELECT entry_id FROM similar_candidate WHERE parent_id = ?)) as b
          ON
          a.term = b.term
      )
      WHERE similar_entry_id <> ?
      GROUP BY entry_id
      ORDER BY score DESC
      LIMIT 10;
    SQL

    results = {}
    Entry.published.all(fields: [:id]).each do |entry|
      db.execute(extract_similar_entries_sql, [entry.id, entry.id, entry.id])
      db.results_as_hash = true
      similarities = db.execute(search_similar_entries_sql, [entry.id, entry.id, entry.id, entry.id])
      results[entry.id] = similarities
    end

    Similarity.destroy

    results.each do |entry_id, similarities|
      if similarities.present?
        similarities.each do |s|
          conditions = { entry_id: s["entry_id"], similar_entry_id: s["similar_entry_id"] }
          similarity = Similarity.new(conditions)
          similarity.score = s["score"]
          similarity.save
        end
      end
    end
  end
end

やってることとしては、全エントリーを拾ってきて本文を MeCab で品詞分解して名詞だけを取り出し記事ごとの term 一覧を作り、そこから TF-IDF を求めてベクトル正規化し、最後に関連していそうなエントリを探し出して similarities テーブル(こちらは SQLite のテーブルではない)を更新している。詳しいアルゴリズムはバカなのでわからないが、 cho45 さんが書いているやり方を Lokka のスキーマに素直に適用した感じ。

結構この処理は遅いので parallel.gem を使って高速化できないか試してみたが、スレッドによる並行処理ではあまり速くできなかった。 4 コアある CPU のうち一つが 100% で処理を実行してもまだ 3 コアは余っている。プロセスを増やして並列処理するのがよさそうだが、分散をプロセスレベルで行おうとすると MySQL server has gone というエラーが出る。 DataMapper が MySQL とのコネクションをロストするようである。 ActiveRecord であれば reconnect するだとか回避方法があるようなのだけど DataMapper は情報が少なく、対応方法が見つけられなかったので一旦並列処理はあきらめた。

何回か動かしてみて大体正しく関連記事を表示できてそうなのでさくらの VPS で稼働させたいところなのだけど、関連記事の更新はいまのところ手動でやっている。本番 DB の entries テーブルを dump してきて Mac に取り込み、 similarities テーブルを更新して今度はローカルで similarities テーブルを dump して本番にインポートするという手順をとっている。

これにはいろいろ理由があって、一つには利用している mecab-ipadic-neologd (新語にも対応している MeCab の辞書)が空きメモリ 1.5GB 以上でないとインストールできずさくらの VPS にインストールできなかったから。もう一つには cho45 さんのブログにもあるけど SQLite で LOGSQRT を使うためには libsqlitefunction.so の読み込みが必要で、 load_extension() できるようにしないといけないが、そのためには sqlite3 をソースからビルドする必要があり若干面倒だった( Mac では Homebrew で sqlite を入れた)。

関連記事の更新は自分が記事を書いたときにしか発生しないのでいまの手動運用でもまぁ問題ないが、このブログは Docker でも動くようにしてあるので Docker イメージを作ればさくら VPS でも問題なく動かせそうな気はする。正月休みにでもチャレンジしたい。

感想

関連記事表示、結構面白くてちゃんと関連性の高いエントリーが表示される。例えば人吉に SL に乗り行った記事の関連記事にはちゃんと山口に SL に乗りに行ったときの記事 が表示される。いまのところ Google Adsense の関連コンテンツよりも精度が高いようである。

無限に自分の黒歴史を掘り返すことができるのでおすすめです。