Born Too Late

2010-11-08 10:45 追記
以下の記事中のベンチマークですが、 N-gram 検索時にクエリキャッシュが効いている疑惑が持ち上がりました。
よって、表の数値は、必ずしも検索それ自体の性能を示すものではないかもしれない、という点にご注意ください。
詳細についてはただいま調査中 & MyNA ML にて質問中です。

本編
先日も書きましたが、 Openpear に Text_Ngram というライブラリを公開しました。 GitHub にも公開しています。
PHP で N-gram を生成する

せっかくなので、これを利用したプログラムのサンプルを公開してみます。

Zip Code Search with N-gram
Text_Ngram を用いて N-gram インデックスを作成し、高速に全文検索を行う実験。

普通の LIKE 演算を用いた検索と比べて、実際にどれぐらいの差がでるのか計測してみましょう。「恵比寿ガーデンプレイス」という単語を検索した際のスピードは以下のようになりました。

	LIKE	N-gram
1	119.127 msec	34.683 msec
2	132.0829 msec	30.2732 msec
3	129.246 msec	31.822 msec
4	92.5341 msec	18.944 msec
5	114.574 msec	9.2828 msec
6	107.5969 msec	6.393 msec
7	101.4121 msec	8.9741 msec
8	140.8319 msec	7.3969 msec
9	145.6361 msec	8.6441 msec
10	127.3508 msec	9.9769 msec
Avg.	121.0392 msec	16.6390 msec

この通り、 7 倍近い性能を出すことに成功しています !

以下では、実装のために実際に行った手順と、実装の一部を紹介します。

動作環境

私の手元では以下のような環境で、動作を確認しております。基本的に、 Ubuntu 10.04 上でパッケージマネージャを用いただけの、簡単な LAMP (Linux / Apache / MySQL / PHP) 構成です。

# Linux
$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=10.04
DISTRIB_CODENAME=lucid
DISTRIB_DESCRIPTION="Ubuntu 10.04.1 LTS"

# Apache
$ apache2 -v
Server version: Apache/2.2.14 (Ubuntu)
Server built:   Sep 28 2010 12:52:38

# MySQL
$ mysqld -V
mysqld  Ver 5.1.41-3ubuntu12.6 for debian-linux-gnu on i486 ((Ubuntu))

# PHP
$ php -v
PHP 5.3.2-1ubuntu4.5 with Suhosin-Patch (cli) (built: Sep 17 2010 13:41:55)
Copyright (c) 1997-2009 The PHP Group
Zend Engine v2.3.0, Copyright (c) 1998-2010 Zend Technologies
    with Xdebug v2.0.5, Copyright (c) 2002-2008, by Derick Rethans

my.cnf の設定

[mysqld] セクションに、以下のような行を追加します。

[mysqld]
ft_min_word_len=1

これは、 MyISAM の FULLTEXT インデックスを作成する際の、単語の長さの最小値です。デフォルトでは 4 になっているので、ここを設定しないと、 2-gram を作成しても無視されることになります。

住所データの入手

日本郵政のサイトから CSV でダウンロードできます。
郵便番号データダウンロード

「読み仮名データの促音・拗音を小書きで表記するもの」→「全国一括」を選択して、ダウンロードします。

MySQL にテーブルを作成

以下のような定義でテーブルを作成します。 FULLTEXT インデックスによる検索が前提なので、 MyISAM であることが必須となります。
ただし、より高速にデータ投入を行えるよう、インデックスの作成は後回しにしています。

CREATE TABLE `addresses` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `zip` int(7) unsigned zerofill NOT NULL,
  `name` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `name_bigram` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  PRIMARY KEY (`id`),
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

郵便番号、住所の他に、 N-gram (今回は 2-gram) のデータを入れるカラムを作っています。

住所データを MySQL に投入

以下のスクリプトを使用します。 Text_Ngram に依存しています。

以下のように実行して使います。

$ php make_bigram_addresses.php [住所データ CSV へのパス]

私の手元の環境では、 約 12 万行の INSERT が 3 分ほどで完了します。

テーブルに FULLTEXT インデックスを作成する

先ほど作ったテーブルに以下のような ALTER 文を流しましょう。 name_bigram カラムに FULLTEXT インデックスを追加します。

ALTER TABLE `addresses`
ADD FULLTEXT INDEX `name_bigram` (`name_bigram` ASC)

最終的に、テーブルの DDL は以下のようになると思います。

CREATE TABLE `addresses` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `zip` int(7) unsigned zerofill NOT NULL,
  `name` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `name_bigram` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  PRIMARY KEY (`id`),
  FULLTEXT KEY `name_bigram` (`name_bigram`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

以上で、高速な検索を行うための準備は完了です。

検索してみる

検索の際は、以下のような SQL を使用します。

SELECT SQL_NO_CACHE SQL_CALC_FOUND_ROWS *
FROM addresses
WHERE MATCH (name_bigram) AGAINST ('+恵比 +比寿 +寿ガ +ガー +ーデ +デン +ンプ +プレ +レイ +イス' IN BOOLEAN MODE)
LIMIT 3

このように、検索ワードも N-gram 形式にして検索する必要があります。

また、今回は計測が目的のため、 SQL_NO_CACHE オプションを用い、クエリキャッシュを無効化しています。

まとめ

今回は LAMP というシンプルな構成で、日本語対応の全文検索を実装してみました。

日本語での高速な全文検索を実現するソフトウェアには Tritonn や groonga, Hyper Estraier といった便利なソフトウェアも数多く存在するので、実際はそれらを使った方が簡単に実現できると思います。
しかし、実際にプロダクションとして運用するとなると、それらのソフトウェアについてのノウハウが必要となるため、なかなかそういった選択を採り辛いこともあるでしょう。

しかし、今回の方法であれば、 LAMP 以外のノウハウを特に必要としないので、比較的簡単に導入できるのではないでしょうか。

というわけで、皆さんも是非 Text_Ngram を使ってみてください !

参考文献

• MySQL FULLTEXT + Ngram : LIKE検索より数十倍高速な、お手軽 日本語全文検索 について たたみらぼ
  実装については、ほとんどこのページを参考にしています。
• 転置ファイル Wikipedia
• 二分探索 Wikipedia

N-gram

これまでは XREA の有料ホスティングを利用していましたが、さくら VPS に移行しました。

この移転にあたって、大体以下のような作業を行っています。

• さくら VPS 契約
• OS は Ubuntu 10.04 (32bit) をインストール
• ログインを公開鍵方式に限定して sshd を起動
• ufw でファイアウォールの構築
• aptitude や tasksel などで LAMP 環境の構築
• WordPress 最新版をインストールし、テスト環境に
• Git をインストール
• テスト環境を Git リポジトリにチェックイン
• RVM をインストール
• WordPress 用とは別に Redmine 用ユーザーを作成し
• Redmine 用ユーザーに RVM で Ruby 1.8.7 をインストール
• Redmine 用ユーザーに Redmine をインストール
• Redmine にブログ用のプロジェクトを作成
• Redmine に、ブログ移転のために必要なタスクをチケットとして登録
• Git リポジトリを Redmine と連携
• Postfix をインストール
• Redmine の更新が、Postfix を通じてメール通知されるように変更
• 必要そうな WordPress プラグインをインストール
• Apache を mod_proxy でリバースプロキシ化
• munin をインストール
• Mysql にスロークエリログが出力されるよう設定
• 旧サーバーから WordPress の記事をエクスポート
• 新サーバーに WordPress の記事をインポート
• 本番環境用の VirtualHost を作成
• テスト環境から git pull し、本番環境の構築
• /etc/hosts を書き換え、擬似本番テスト
• DNS の A レコードをさくら VPS のものに切り替え

大体こんな感じです。順番は必ずしもこの通りではありませんが。

さくら VPS では root 権限がもらえるので、いろいろインストールできるし、 Apache や MySQL についても細かく設定・監視ができるので楽しいです。 XREA のときにはできなかったような、より実践的なサーバー運用を学んで、このブログにも残していければと思います。

以下のような、メールアドレス等の情報を保持したテーブルがあるとします。

mysql> SELECT * FROM users;
+----+---------+------------------+
| id | name    | mail             |
+----+---------+------------------+
|  1 | foo     | foo@yuyat.jp     |
|  2 | bar     | bar@yuyat.jp     |
|  3 | baz     | baz@example.com  |
|  4 | hoge    | hoge@example.org |
|  5 | moge    | moge@example.com |
|  6 | foobar  | foobar@yuyat.jp  |
|  7 | test    | test@example.net |
|  8 | example | example@yuyat.jp |
|  9 | mage    | mage@example.org |
| 10 | huga    | huga@example.com |
| 11 | piyo    | piyo@yuyat.jp    |
| 12 | hige    | hige@yuyat.jp    |
+----+---------+------------------+
12 rows in set (0.00 sec)

ここで、以下のような SQL を用意します。

SELECT
  SUBSTRING_INDEX(mail, '@', -1) AS domain
FROM
  users

すると、このような結果が得られます。

mysql> SELECT SUBSTRING_INDEX(mail, '@', -1) AS domain FROM users;
+-------------+
| domain      |
+-------------+
| yuyat.jp    |
| yuyat.jp    |
| example.com |
| example.org |
| example.com |
| yuyat.jp    |
| example.net |
| yuyat.jp    |
| example.org |
| example.com |
| yuyat.jp    |
| yuyat.jp    |
+-------------+
12 rows in set (0.00 sec)

また、以下の用にグルーピングすることで、ドメイン数順にソートすることも簡単です。

SELECT
  SUBSTRING_INDEX(mail, '@', -1) AS domain,
  COUNT(id) AS count
FROM
  users
GROUP BY
  domain
ORDER BY
  count DESC

mysql> SELECT SUBSTRING_INDEX(mail, '@', -1) AS domain, COUNT(id) AS count FROM users GROUP BY domain ORDER BY count DESC;
+-------------+-------+
| domain      | count |
+-------------+-------+
| yuyat.jp    |     6 |
| example.com |     3 |
| example.org |     2 |
| example.net |     1 |
+-------------+-------+
4 rows in set (0.00 sec)

これらの SQL で重要なのは SUBSTRING_INDEX という関数です。この関数は、ある文字列をデリミタで区切り、その n 番目を取得する というものなのですが、n に負の数を与えることで、末尾の要素を取得しています。

MySQL