Born Too Late

MySQL と N-gram による高速な日本語全文検索の実装

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

この通り、 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