知識には2つのタイプがある。ひとつは物事を知っていること。 もうひとつはそれをどこで見つけるかを知っていることである。 -- サミュエル・ジョンソン
前号では、頼りない記憶力を補う手段として Unix のメモ技術を取 り上げた。しかし、いくらメモを取ったところで、いざというとき にメモから必要な情報を見つけ出せなければ意味がない。そこで、 今回は日本語のテキストをすばやくインクリメンタル検索するソフ トウェアMigemo を紹介する。
横着な上に短気な人間
私はものに対して -- 特に計算機に対して -- 短気である。といっ ても、怒り心頭してものを破壊するというわけではなく、文句を言 うだけである。「何なんだコイツは!!」などと計算機に向かって怒っ ていると、「お前こそ何なんだ!!」とよく周りの人間から白い目で 見られる。
それはさておき、私のような横着な上に短気な人間は、テキストを 検索するなどという計算機を使う上で基本的な行為に手間がかかっ てはイライラして気が狂いそうになる。今回紹介するMigemo は横 着と短気から生まれたソフトウェアである。
インクリメンタル検索
インクリメンタル検索とは、ユーザが 1文字入力するたびに検索を 進めるという検索手法である。インクリメンタル検索の手法は Emacs などのテキストエディタで広く用いられている。下の図は Emacs で ``scheme'' という単語をインクリメンタル検索する過程 を示している。
インクリメンタル検索1
インクリメンタル検索2
インクリメンタル検索3
インクリメンタル検索4
この例では、利用者は、 C-s s c h の 4打鍵で目的のテキスト位置に到達している*1。この時点で C-s を打つと ``sch'' で次の 候補が検索される。一方、通常のキーワード検索では最初にキーワー ド全体を入力する必要があるため、最低でも s c h e m e の 6 打鍵を要する。インクリ メンタル検索を用いれば``floccinaucinihilipilification'' のよ うな長い単語でも最初の数文字を打つだけで検索できる。
インクリメンタル検索は、テキスト内から目的の情報を探すという 情報検索の用途だけではなく、目的の位置にカーソルをすばやく移 動するというテキスト編集の用途にも広く用いられている。たとえ ば、テキストエディタでカーソルを遠くに移動したいときに、カー ソルキーを何回も叩くよりも、キーワードの数文字でインクリメン タル検索した方がすばやくカーソルを移動できることが多い。この ことから、インクリメンタル検索は快適なテキスト編集作業にとっ て必須の機能といえる。
日本語のインクリメンタル検索
しかし、日本語でインクリメンタル検索を行おうとすると、かな漢 字変換という壁につきあたる*2。イ ンクリメンタル検索では 1文字入力するごとに検索を進めていくと いう点が重要だが、かな漢字変換には、単語の読み全体を入力して から漢字に変換するという手順を踏むため、1文字入力単位でのイ ンクリメンタル検索は行えない。一方、英語の場合は、入力する文 字とキーボードが1対1に対応するため、このような不都合は起きな い。一般的に、かな漢字変換には次の 3つのステップを要する。
- 読みをローマ字として入力する
- 読みを漢字に変換する
- 変換候補から適切な単語を選択する
このように、日本語の入力にはかな漢字変換のステップを要するた め、たとえば「奇怪」を入力するためには、KANA k i k a i CONVERT SELECT SELECT RETURN KANA のようにかな漢字変換に 10打鍵以上を費さなければならない*3。このため、かな漢字変 換を伴う検索では、キーワードの最初の数文字を打つだけで検索で きるというインクリメンタル検索は行うことができない。これでは、 面倒くさくて頭がおかしくなりそうである。
Migemoとは
そこで、私はローマ字のまま日本語のインクリメンタル検索を実現 するシステムMigemo*4 を開発した。 私の場合、インクリメンタル検索を最も頻繁に行うのはテキストエ ディタ Emacs なので、Emacs用に実装を行った。
Migemo は、かな漢字変換のステップを省略して、ローマ字のまま の日本語のインクリメンタル検索を実現する。次の図は Migemo を 用いてキーワード「奇怪」をインクリメンタル検索する過程を示し ている。
インクリメンタル検索1
インクリメンタル検索2
インクリメンタル検索3
インクリメンタル検索4
この例では、ユーザは C-s k i k とい う 4打鍵で目的のテキスト位置に到達している。一方、かな漢字変 換を伴う検索では、前述の通り 10打鍵以上を要する。このように、 Migemo を使えば、かな漢字変換の入力作業に煩わされることなく、 スムーズな日本語のインクリメンタル検索が行える。
Migemoのインストール
Migemo は Emacs上で動くソフトウェアである。手元の環境では Emacs 20/21 で動くことを確認している。Migemoを使うには次のソ フトウェアをインストールする必要がある。
- Emacs*5: 原稿執筆時点での最新版は 21.1
- APEL*6: Emacs Lisp で移植性の高いプログラムを書くためのライブラリ
- Ruby 1.6以降*7: オブジェクト指向スクリプト言語
- Ruby/Bsearch*8: 配列を 2分探索する Ruby用のライブラリ
- Ruby/Romkan*9: ローマ字とひらがなを相互に変換する Ruby用のライブラリ
- Migemo*10: Migemo本体
Ruby/Bsearch と Ruby/Romkan は私が Migemo のために開発したラ イブラリである。インストール方法は次の通りである。
Ruby/Bsearch
% gzip -dc ruby-bsearch-1.5.tar.gz | tar xvf - % cd ruby-bsearch-1.5 % su Password: (rootのパスワードを入力) # cp bsearch.rb /usr/local/lib/ruby/site_ruby/1.6
Ruby/Romkan
% gzip -dc ruby-romkan-0.3.tar.gz | tar xvf - % cd ruby-romkan-0.3 % su Password: (rootのパスワードを入力) # cp romkan.rb /usr/local/lib/ruby/site_ruby/1.6
Migemo
% gzip -dc migemo-0.3.tar.gz | tar xvf - % cd migemo-0.3 % ./configure && make % su Password: (rootのパスワードを入力) # make install
Migemoの使い方
インストールが完了したら Emacs の設定ファイルである ~/.emacs *12に
(load "migemo.el")
という 1行を追加すれば Migemo が使えるようになる。 C-s (前方にインクリメンタル検索), C-r (後方にインクリメン タル検索) でローマ字のまま日本語をインクリメンタル検索ができ る。
Migemo の拡張を無効にして元のインクリメンタル検索に戻すには M-x migemo-toggle-isearch-enable を実行すればいい*13。 Migemo の使い方は以上でおしまいである。ほかに説明することが ないくらい単純なソフトウェアなのだ。
Migemoの実装
Migemo の実装の方針は
- 実用できる品質
- お手軽にプログラミング
である。この 2つの方針は Migemo に限らず、私がプログラミング するときにだいたいいつも心がけている。
実用できる品質
そもそも自分が使いたいソフトウェアを作るのだから、実用になら なければ意味がない。アイディアを検証する程度の実装は比較的、 短時間で行なえたが、日常的に使う品質にするには「chi/ti」「っ」 「ヴ」など、日本語の細かい扱いに注意を払う必要があり、それら の対応に時間がかかった。
また、せっかく便利なものを作ったなら他の人にも使ってもらいた い。他の人に使ってもらうとなると、ドキュメントを書いたり、イ ンストールしやすいようにパッケージを作ったりとずいぶん手間が かかるが、
- ソフトウェアを自慢できる
- ソフトウェアを仕上げて公開するという過程で品質が上がる
- 人から助言をもらえる
- 人から手伝ってもらえることもある
- マニアなお兄さんたちからちやほやされる (こともある)
というメリットがあるため、それだけの手間をかける価値はあると 私は思っている。実際、Emacs 21の lazy-highlight への対応は白 井秀行氏が自ら進んで行ってくれた。
lazy-highlight とは、入力中のキーワードにマッチする画面上の 文字列を強調表示する機能のことである。言葉ではわかりづらいが 写真を見れば一目瞭然である。この例では入力中のキーワード "mo" に対しテキストの「懶」や「目」「モ」「物」「も」「木」 などが強調表示されている。
lazy-highlight
お手軽にプログラミング
私はプログラミングが好きである。しかし、必要以上にプログラミ ングに手間をかけたくない。できれば、最小限のコストで手っ取り 早く仕上げたい。そこで、Migemo のエンジン部分はオブジェクト 指向スクリプト言語 Ruby で実装を行ない、 Emacs Lisp の部分を 最小限に押えた。私の場合は Emacs Lisp より Ruby の方が簡単に プログラムが書けるからだ。Emacs と Migemo エンジンは Unix双 方向パイプで通信する。
実は Migemo エンジンは以前はPerl*14 で実装していたのだが、木構造のデータを扱っているうちにプログ ラムがごちゃごちゃして修正が不可能になったため、あるとき Rubyで書き直すことにした。次のコードは Migemo で実際に使われ ているものの Perl版と Ruby版である。この例では大きな違いはな いが、Ruby 版では @_ や $_ といった記号的な変数 は使われていないところが異なる。
# (運 運動 運転 日本 日本語) => (運 日本)
sub optimize1 {
my @cand = @_;
my $prefixpat = undef;
grep {
if (defined $prefixpat && /^$prefixpat/) {
0;
} else {
$prefixpat = quotemeta($_);
1;
}
} sort @cand;
}
# (運 運動 運転 日本 日本語) => (運 日本)
def optimize1 (regex)
prefixpat = nil
regex.sort.find_all {|word|
if prefixpat && prefixpat.match(word)
false
else
prefixpat = Regexp.new("^" + Regexp.escape(word))
true
end
}
end
速度の面を考えると C言語で実装するという選択肢も考えられたが、 現在の計算機の性能なら Ruby でも十分な速度で動くので、わざわ ざ Cで書く必要性は感じなかった。Ruby を採用したおかげで、 Migemo のエンジンは全体で 740行と簡潔に書けた。
Migemoの仕組み
ローマ字のままの日本語のインクリメンタル検索を実現する方法を 考えたときに、真っ先に思いついたのはテキスト全体を内部的にロー マ字に変換して、そのローマ字に対して検索を行なうというものだっ た。日本語テキストのローマ字への変換は茶筌 *15などのソフトウェアを用い て行なえる。
しかし、インクリメンタル検索するたびにテキスト全体をローマ字 に変換するのでは、巨大なテキストを編集しているときに遅くて使 いものにならない。検索の進行に応じてテキストを部分的にローマ 字へ変換する方法も考えられるが、実装が難しそうである。そこで、 私はテキストではなくユーザが入力するキーワードを加工してロー マ字のままの日本語のインクリメンタル検索を実現することにした。
Migemoは、ユーザが 1文字入力するごとに動的に正規表現を生成し て指定した読みで始まる複数の言葉を同時かつ並列に検索する。た とえば、上の「奇怪」のインクリメンタル検索に対する正規表現の 展開は次の図のように行われる。
[kＫｋかきくけこっカキクケコッヵヶΚ哀愛旭扱絢袷暗闇鞍杏位囲 惟易畏異衣一溢因蔭陰隠烏窺臼渦嘘雲影越閲煙汚凹応横鴎黄岡乙下 化仮何伽価佳加可嘉夏嫁家寡科暇... [きキヶ衣窺汚黄乙牙階肝岸企伎危喜器基奇嬉寄岐希幾忌揮机旗既 期棋棄機帰毅気汽畿祈季稀紀徽規記貴起軌輝飢騎鬼亀妓掬菊鞠吉吃 喫桔橘詰砧杵黍究窮競極桐粁... [掬菊鞠樵效椈鞫]|kik|ｋｉｋ|き[かきくけこっ]|キ[カキクケコッ] |窺基|企[画劃]|危[機急険]|喜([々界気国]|歌劇|久[子治泉男雄]) |器[械官管機]...
最初の正規表現では「k」や「か」や「化」などの ``k'' にマッチ するテキストの位置へ、中央の正規表現では「き」や「黄」などの ``ki'' にマッチする位置へ、最後の正規表現では「菊」や「危険」 などの ``kik'' にマッチする位置へと、インクリメンタル検索が 進む。
実際の検索処理は正規表現エンジンによって行われるが、ユーザか らは正規表現を展開する過程は隠されているため、通常のインクリ メンタル検索とまったく同じように操作が行える。
正規表現の展開
正規表現の展開は、ヘボン式および訓令式のローマ字列をかな表記 に変換する規則と、ひらがなの読みがふられた単語辞書を用いて行 う。ローマ字の変換規則は ``k'' に対して次のような展開を行う。 この展開により、``k'' でマッチするすべての平仮名および片仮名 をカバーできる。
k → か|き|く|け|こ|っ|カ|キ|ク|ケ|コ|ッ
単語の展開は次の図のような辞書を用いて行う。現在は、かな漢字 変換システムSKK*16 の辞書を加工し て利用している。
=========================================
読み | 単語
---------------------+-------------------
きかい | 機械 機会 奇怪 器械
| 貴会 気塊 喜界
きかいあぶら | 機械油
きかいぶひん | 機械部品
きかいちのう | 機械知能
きかいがっかい | 機械学会
きかいがく | 機械学
きかいがくしゅう | 機械学習
-----------------------------------------
この辞書を用いることにより、指定された読みで始まるすべての単 語にマッチする正規表現を動的に生成できる。Migemo は、入力 k i k に対して、``きか'', ``きき'', ``きく'', ``きけ'', ``きこ'', ``きっ''に読みがマッチするすべての単語を 辞書から取り出して正規表現を生成する。取り出した単語を or 記号 | で連結すれば正規表現が出来上がる。
しかし、マッチする単語を単純に orで連結する手法では、 正規表現が巨大になりすぎるという問題がある。実際、Migemo で 利用している辞書には ``k'' にマッチする単語は 47,292 個が辞 書に登録されているため、単純に or 記号で結ぶと、実に 40 万文 字もの長さの正規表現が生成されることになり、Emacs の[Regular Expression too big] というエラーを引き起こす。
そこで、Migemoは冗長なパターンを統合して正規表現の簡単化を行 う。読み ``mour'' に対する正規表現の簡単化は次のように行なわ れる。
== 元の正規表現 mour|ｍｏｕｒ|もうっ|モウッ|もうら|モウラ|網羅|網羅性|網羅的 |網羅率|もうり|モウリ|毛利|魍魎|もうる|モウル|もうれ|モウレ| 猛烈|猛烈巨人|猛烈不況|猛練習|猛連荘|もうろ|モウロ|朦朧|耄碌 == 簡単化後の正規表現 mour|ｍｏｕｒ|もう[っらりるれろ]|モウ[ッラリルレロ]|毛利|猛 (烈|練習|連荘)|網羅|朦朧|耄碌|魍魎
上の例では、元の正規表現に含まれる「網羅」「網羅性」「網羅的」 といった、「網羅」から始まる候補は、長さが最小である「網羅」 ひとつにまとめられる。また「もうっ」「もうら」「もうり」など も文字クラスを用いて ``もう[っらりるれろ]'' とまとめられる。 さらに、「猛烈」「猛練習」「猛連荘」のように「猛」から始まる 単語は括弧でグループ化して「猛(烈|練習|連荘)」とまとめられる。 このようにして正規表現を簡単化することにより、``k'' のような 短い読みに対しても数千文字程度の正規表現に収められる。
正規表現展開の高速化
インクリメンタル検索では、ユーザにストレスを与えない高速な処 理が不可欠である。そこで、Migemo では、ユーザの入力に高速に 追従するために、 ``a'', ``k'', ``s'' などの短い文字列に対し ては、辞書から動的に正規表現を生成する代わりに、あらかじめコ ンパイルした正規表現を用いて、実用的な速度を実現している。具 体的には Ruby の Marshalモジュールを用いて、木構造で表現され ている正規表現のオブジェクトをシリアライズしてファイルに保存 したものをキャッシュとして利用している。
同音異義語の扱い
Migemoによる日本語のインクリメンタル検索では、``kikai'' で検 索をすると「機械」「機会」「奇怪」「器械」のすべてにマッチす るため、「奇怪」を検索しているときに「器械」にマッチしてしま うという問題が起きる。しかし、不適切なマッチは C-s で 即座にスキップできるため、大きな問題にはならない。一方、通常 のキーワード検索では「こんにちは」で検索をかけると「今日は」 は見つからないが、Migemo で ``konnnitiha'' で検索すれば両方 とも見つかるという利点がある。同様に、``interface'' で検索す れば「インターフェース」「インターフェイス」「インタフェース」 「インタフェイス」などの表記の揺れを無視して検索を行うことも できる。これらの表記はすべて辞書に定義されているためである。
Migemo の欠点
このように Migemo は辞書を利用して正規表現を生成するため、辞 書に載っていない言葉は検索できないという問題がある。また、現 在の実装では単語単位の検索にしか対応していないため、 ``genzainojissou'' で「現在の実装」を検索するような、複数の 単語にまたがる検索は行えない。
Migemoの仲間たち
Migemoには 私が実装した Ruby + Emacs版の他にも別の実装がある。
w3m用のMigemo
日台健一氏と平岡和幸氏はテキストWebブラウザw3m *17 の検索機能の強化として、 w3m への Migemoの組み込みを行なった *18。
w3m上のMigemo1
Web上の日台氏の言葉がおもしろいのでここに引用させていただく。
なぜそんなことするの？
「キーボード:マウスの操作比 = 99:1」を決して大げさな数値でな いと感じる強者キーボーダーにとって、カーソル移動目的の検索 （参照：Seven habits of effective text editing）は今日当然と され、むしろそれが操作をする上で非常に重要な要素となっている。 しかし我々日本人にとって、何らかのフロントエンドを介さねば日 本語の入力ができないことは避けられない現実であり、それが検索 キーワード入力の作業量の増加、つまりはカーソル移動を円滑に行 う事の障害となっている。 しかし、その障害を克服しようとする試みがMigemoによってなされ、 実用的な段階に達していることが明らかになった。しかしMigemoは Emacsで動作するもので、我々の愛するw3mやvimでは動作しない。 動作しなければ動くようにすればよい、という安易な理論に乗っ取 り、全てのソフトにローマ字検索の機能が実装される日を夢見て、 そのはじめの一歩をw3mで実現したのである。
この文章からも分かるように、日台氏はテキストエディタ VIM*20 の愛好家である。日台氏はEmacsプ ログラマばかりが集まった席で VIM のよさを孤軍奮闘してしきり に主張していた。このような熱血な人物に Migemo を気に入っても らえたのは嬉しい限りである。
V!I!M!
と踊る
日台氏
C言語版Migemo
村岡太郎氏は Migemo をC言語で再実装し、テキストエディタVIMを 拡張するライブラリとして公開している *21。ライブラリ自体は VIM 以外からも使えると思われるため、他のソフトウェアへの応用が期 待できる。
VIMでMigemo
Q-Pocket
増井俊之氏が開発した個人情報管理システム Q-Pocket *22 は全 文検索の機能に Migemo を応用している。このシステムでは、予測 入力システム POBox*23 の辞書をそのまま Migemo 検索でも利用している。テキスト入力と テキスト検索に同じ辞書を用いることにより、POBox で入力できる 単語は Migemo で必ず検索できるという一貫したテキスト処理を実 現している。次の図では「委員会」に関するメモを検索するために iink と入力しているところである。
Q-Pocket
Migemoの名前の由来
Migemo の名前の由来をよく訊ねられる。本当のことを言うと恥ず かしいのだが、友人と雑談をしているときの「にゃんマゲ *24みたいにポ ケモンにマゲをつけてマゲモンはどうだろうか」という発言が発端 となって
マゲモン → マゲモ → Magemo → Migemo
と変形したのである。Magemo はなかなかいいと思ったが、 google.comで検索して 100件以上ヒットしたので採用を見送った。 一方、Migemoは 0件であった。ソフトウェアの名前を決めるときに、 検索エンジンで見つけやすいという特徴はなかなか重要だと思う。
余談: ビデオ作成地獄
ある日、Migemoのプロモーションビデオを作ろうと思い立ち、本紙 連載でおなじみの増井さんに手伝ってもらって作業を始めた。2 分 くらいのビデオならすぐに作れると高を括っていたのだが、作業は 難航し、結局、徹夜になってしまった。ビデオ作成に使った計算機 の性能が悪かったため、プレビューの表示にすら待たされるのであ る。動画ファイルの出力にはさらに待たされた。
ちょっと修正してファイルを保存してまた修正して…、を延々に繰 り返すという不毛な作業を続けていると、ふと気づくと、手元に x.avi, xx.avi, xxx.avi, monkey.avi, cat.avi, final.avi, final2,avi, dog.avi などとわけのわからない名前のファイルがた くさん作られていた。動物の名前にはまったく意味はなく、思いつ いた言葉でファイル名をつけていっただけである。朦朧としつつも ビデオは明け方にはなんとか完成した。
ビデオが完成したその翌々日くらいに人に見せることになったのだ が、どれが最新のファイルなのか覚えていない。仕方なくタイムス タンプを調べるとなんと dog.avi が最新ということが判明した。 final.avi, final2.avi というそれらしい名前のファイルは一体何 だったのだろうか。
教訓: いい加減なファイル名をつけてはいけない
とはいうものの、ファイルのバージョン管理が簡単にできるなら、 xxx.avi やら final2.avi などという余計なファイルを作る必要は ないはずである。アプリケーションが異常終了すると、保存してい ない作業内容が失われるというのも困りものである。と、わけのわ からないファイルの山を前にして、まだまだ計算機は使いにくい、 と (自分の不手際を棚に上げて) 思うのであった。
ところで、この話を知人にしたところ、 final.tmp.01.last とい うとんでもない名前のファイルを見かけたことがあると教えてくれ た。まさにファイル名地獄である。
ビデオは Webサイト*25に置 いてあるので興味のある方はご覧いただきたい。
おわりに
私は「Migemo はなんて画期的なんだ!」と我ながら興奮したのだが、 共感してくれる人は思ったより少なかった。なんだか寂しいと感じ たのだが、よくよく考えてみれば、
- Emacs を使っていて
- インクリメンタル検索を活用していて
- 日本語のインクリメンタル検索に不満を感じていて
- Migemo の存在を知って
- Migemo のインストール & 設定の手間を惜しまず
- 「Migemoはなんて画期的なんだ!」と感じる
という人はそうたくさんはいないのである。あらゆるソフトウェア、 特に Windows の Internet Explorer や Word などで Migemo検索 ができるようになれば世の中へのインパクトが大きいのではないか と考えている。Windows プログラミングの得意な方が協力してくれ ることを期待している。