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 というシンプルな構成で、日本語対応の全文検索を実装してみました。

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

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

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

参考文献

PHP 用の N-gram 生成ライブラリ、 php5-Text_Ngram を Github に公開しました。
個人的な PHP 5.3 の練習ということで作ったので、 namespace 等を使っています。 5.3 未満では動きません。

yuya-takeyama’s php5-Text_Ngram at master – GitHub

プロダクションとしての利用は想定していませんので、利用者ご自身の責任においてご利用ください。

Text_Ngram

文字列を N-gram 形式に分割するためのライブラリです。

N-gram オブジェクトを生成し、配列のように扱うことができます。

動作環境

PHP5 (>= PHP 5.3)

インストール

Openpear 経由でインストールできます。

sudo pear channel-discover openpear.org
sudo pear install openpear/Text_Ngram-beta

N-gram とは

例えば全文検索システムを構築する場合、前処理としてインデックスの作成が必要となります。
しかし、欧米の言語と違って、日本語はスペース等の一定のデリミタで区切ることはできません。
そこで、文章的な意味に関わらず、 n 文字ごとの分割した形式を使い、これを N-gram といいます。

分かち書きの方法としては、形態素解析も挙げられますが、 N-gram では辞書のメンテナンスが不要、という利点があります。
また、 n 文字ごとに分割する、という単純なルールなため、言語にかかわらず適用することができます。

使い方

N-gram オブジェクトの生成

require_once '/path/to/Text/Ngram.php';
use Text\Ngram;
$ngram = new Ngram('こんにちは世界!', 2, 'UTF-8');

配列への変換

$ngramArray = $ngram->toArray();

N-gram オブジェクトを配列の要に扱う

echo $ngram[0];     // => こん
echo $ngram[1];     // => んに
echo count($ngram); // => 7

イテレーション

foreach ($ngram as $key => $value) {
    echo "{$key} : {$value}" . PHP_EOL;
}

まとめ

初めにも書きましたが、あくまでも利用者ご自身の責任においてご利用ください。

Pure PHP なので、速くないと思います。
機能も最小限ですが、小規模なサービスでは問題なく使えるとおもいます。

テストはしている & 書いていますが、バグ等見つけたら、フィードバックいただけるとありがたいです。

,

Markov Chain in JavaScript
2011-05-03 追記: 消えていたので別 URL にて作りなおしました.
Twitter につぶやく機能もつけてみたのでお試しあれ。

オブジェクト指向な上に、GUI アプリケーションも簡単に作れてしまう。JavaScript はやっぱり楽しいですね。

実装としては、前のエントリーの Ruby のものと特に変わりません。Ruby のコードを見ながら移植してほぼ終わり。ただ、Ruby 版では「改行コードをすっ飛ばす」仕様になっていたのを、すっ飛ばさないことにしています。

前のエントリーに載せた、『口辺筋肉感覚による叙情的作品』を、Chain length を 2 として実行すると、どっちが入力でどっちが出力なのか見分けがつかなくておもしろい。さて、次のうちどれが本物でしょうか?

A

ポポ

ヌルヌルヌルモナラミ

ヌルモモヌム

ギレッチョ

ヌム

ヌルヌルモモヌムヌムモナラミ

ギレッチョ

ズルマッチョ

ヌルモモヌム

ポエ

ポエ

ヌム

ヌムヌム

ギレッチョ

ズルマッチョ

ヌルヌルモモヌムヌム

ヌルモモヌム

ヌルモモヌムモナラミ

ヌルヌルヌルモモヌムモナラミ

ギレッチョ

ヌルヌルモモヌムヌム

ポエ

ズルマッチョ

ヌルヌルモモヌムモナラミ

ヌムヌムモナラミ

ポエ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

B

ポポ

ズルマッチョ

ヌルモモヌムモナラミ

ヌルヌルヌルヌルヌルヌルヌルヌルヌルモモヌムヌムモナラミ

ポエ

ギレッチョ

ヌルヌルモモヌムモナラミ

ヌルモモヌムモナラミ

ギレッチョ

ヌルモナラミ

ギレッチョ

ポエ

ヌルモモヌム

ズルマッチョ

ヌルモナラミ

ヌルヌルモナラミ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

C

ポポ

ヌルヌルモモヌム

ヌルヌルモモヌムヌムヌムモナラミ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

D

ポポ

ヌムヌムモナラミ

ヌルヌルモモヌム

ギレッチョ

ズルマッチョ

ヌルヌルモナラミ

ヌルヌルモモヌム

ズルマッチョ

ポエ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

E

ポポ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

, ,