Leo's Chronicle

2009年1月31日土曜日

Googleはコンピューターに損害を与える可能性があります

Googleの検索結果に「このサイトはコンピューターに損害を与える可能性があります」と付くので、不思議に思っていたら、Googleのサイトそのものも損害を与える可能性があるそうで。

まぁ、それなら仕方がないか(笑)

2009年1月27日火曜日

正規表現に見切りをつけるとき

Perl, Rubyなど手軽に使えるプログラミング言語に慣れてくると、あらゆるテキストデータの処理に正規表現(regular expression)を使ってしまいがちです。

けれど実は、正規表現の処理能力を超えるフォーマットというのが存在します。その典型的な例が、XMLやJSONのように、入れ子になったデータフォーマットです。

例えば、

(a, b, (c, d))
(a, b, (c, (d, e)))

というように、括弧がどんどん入れ子になっていく構造は、括弧のネストの深さを数えないと正しく解釈できません。正規表現でも、一番外側の括弧の対応をとらえるために、/\(.*\)/、/\([^)]*\)/ などとはは書けますが、常に正しい括弧の対応をとっているとは限りませんし、もしうまくいったとしても、さらに内部の括弧をとらえるために、外側の括弧を取り除き、また同様の正規表現を内部の文字列に対して繰り返して適用する必要があります。

そして問題なのが、

(a, (b, c)), d, (e, f)

という文字列の場合。/\(.*\)/という正規表現では、以下のように色のついた範囲を拾ってしまいます。

(a, (b, c)), d, (e, f)

正規表現では、このようにちょっとしたデータ構造すら上手く構文解析できません。したがって、正規表現だけで文字列を処理する場合は、何らかの方法で括弧が2重、3重にならないように工夫する必要があります。（あるいは括弧内を再帰的に処理するプログラムを書くなど。）バイオ系のデータフォーマットでも、この正規表現の能力の限界を知らないがために、正規表現で処理できない入れ子になったデータを平気で書いてしまう人が多いので、手軽に処理したい場合は要注意です。（他にも2重引用符で囲まれた文字列の扱いも、正規表現では面倒な例です）

構文解析

では、正規表現の能力を超えるデータはどう扱えばいいのか？一番のお勧めは、ANTLRを使って字句解析(lexer)、構文解析(parser)するプログラムを生成する方法です。一昔前なら、lex/yacc、flex/bison, JavaCCなどしか選択肢がなかったのですが、今は断然ANTLRが便利です。ここでは、JSONを例にとって説明します。以下は、JSONで書かれた配列の中に配列がある構造です。

[0, [1, 2]]

字句解析では、これを、

LBracket([), Number(0), Comma(,), LBracket([), Number(1), Comma(,), Number(2), RBracket(]), RBracket(])

というようにトークン（文字列の単位, lexer ruleとして記述）に分解していきます。そして、これらのトークンにマッチする文法（parser rule)を定義します（以下の例は、説明のために他のデータ型については省いて簡潔に書きました）

array: LBracket Value (Comma Value)* RBracket;
value: Number | array;

ここでは、括弧 [ ] の中に、ValueをComma(,)でつなげて複数個書けるルールを定義しています。Valueとしては、数字(Number)以外に配列(array)も使えるので、配列の中に配列があるような入れ子になったデータ構造もこれで解析できます。

参考までに、僕がANTLRで作成したJSONの文法を紹介します。ANTLRの記述を覚えるコストはかかりますが、1ページ分の記述量でJSONのように構文が複雑なものも処理できるようになります。以下に挙げるのは、ANTLRのリファレンス（英語）と、その背景にある理論の教科書で、コンピューターサイエンスの学科では講義によく使われていてどれもお勧めです。Aho, Ullman先生らのドラゴンブック第2版（Ullman先生の息子さんがCGで表紙を作ったとか）は読みごたえ十分ですし、Apel先生の本ではVisitorパターンの使いどころのような、実装に近い話題にも触れられていて読みやすいです。稲葉君絶賛のParsing Techniquesなどもあります。

構文解析の実践としては、ANTLRをダウンロードするとサンプルの文法がたくさん付いてくるので、それを真似して書くのも習得への早道かと思います。一度ANTLRで文法を書くと、Perl/Ruby/C/C#/Javaなどの言語用のlexer/parserを生成できるようになるので、どの言語を使っている人にもお勧めです。しかし、まだ日本語のリファレンスがないのが構文解析の敷居を高くしている原因でしょう。この記事が素晴らしき構文解析の世界への足がかりになればいいなと思います。

（実用上の補足）

正規表現の中に自己を含めて循環定義できるRubyやPerlなどの処理系なら、入れ子もなんとか処理できるみたいです。以下はPerlのコード例。(「詳細正規表現第3版」を参考にしました）


$str = "(a (b, c)), (d), (e, f)";
$paren = qr/\([^()]*(?:(??{$paren})[^()]*)*\)/;
while ($str =~ /($paren)/g) {
print $1, "\n";
}

実行結果

(a (b, c))
(d)
(e, f)

括弧のパターンにマッチすると、その都度中身の正規表現がlazyに変わっていくというトリッキーな技です。このような正規表現は以下に述べるような形式言語理論上の正規表現の定義には含まれないのでご注意あれ。ただ、Perlで処理できるとしても、二重引用符とか、様々な括弧の種類に対応するように再帰型正規表現を書いていくと、ANTLRのparser ruleを書くのと似た状況になるとは思います。(追記）Perl6のRulesという機能では、ANTLRのような文法定義を書けるとか！入れ子が必要なときは、これを使いましょう、ということですね。

(コンピューターサイエンス的な補足）

細かい話をすると、正規表現は文脈自由文法というクラスのサブセットで、入れ子の構造をもった文法は、文脈自由だけれど正規表現ではありません。これは、pumping lemmaを使って証明できます。情報系の学科なら、計算量理論などの講義で習うはず。オートマトンにスタックをつけたプッシュダウンオートマトン（文脈自由文法と同じ表現能力を持つ）なら、このような入れ子をうまく処理できます。このあたりの話は「計算理論の基礎」という教科書に丁寧に書かれてあって（大学院入試の勉強のときにかなりお世話になりました）、コンピュータサイエンスの基礎のうち、オートマトン、NP完全問題など計算量にかかわる部分について学ぶのに優れた本です。（最近は第2版もでているようですが、3冊に分かれてしまって少々買いにくくなってしまいました。分けた方が持ちやすいのかな？）

2009年1月16日金曜日

Top 5 Database Research Topics in 2008

岡野原君が自然言語処理関連で2008年に読んだ論文のベスト5を紹介しています。それに倣って、僕も個人的にインパクトのあった2008年のデータベース研究のベスト５を集めてみました。

Michael J. Cahill, Uwe Röhm and Alan D. Fekete. Serializable Isolation for Snapshot Databases. SIGMOD 2008. (ACM DOI)

真っ先に思い浮かんできたのがこの論文。SIGMOD2008のベストペーパーでもあります。僕自身、トランザクション処理を長く研究していた経験から、Serializability（ディスクのread/writeの順番をあるプロトコルに従って入れ替えても、データベースの検索・更新結果に影響を与えない）を保障しつつ、一秒間あたりに処理できるトランザクションの数（つまりスループット）を上げるのは、ものすごく難しいことを実感していました。ロックの粒度、デッドロックの回避、インデックスのconcurrency(同時読み書き）管理などなど、同時に考えないといけない要素が多すぎるのです。

では、現在の商用DBMSではどう高速化しているかというと、snapshot isolationと言って、データベースのある時点での状態(これをsnapshotと呼ぶ）を保持し、readerはsnapshotを参照し、writerは新しいsnapshotを作るようにして、読み書きが衝突しないようにしています。これは確かに性能が出るのですが、特定のread-writeパターンで、serializabilityが崩れてしまい、トランザクションをやり直す（rollbackする) か、あるいは、rollbackが起こらないように検索・更新のworkloadを設計するのが大変でした。

この論文は、そんなsnapshot isolationを、性能をほとんど落とさずserializableにする話で、実装も簡単にできるという素晴らしさ。著者に会ったときにソースコードが欲しいと話したらBerkeleyDB上での実装を公開してくれました。（この話は「PFIに行きました」のエントリでも言及しています)。First AuthorのCahillさんは、Sleepycat (BerkeleyDBの開発元、現在はOracleに買収）で七年働いていたBerkeleyDBの開発者で、こんな改良を施すのもお手のものだとか。どうりでこんな研究ができるわけだと納得。

今後、トランザクションの教科書に一節が追加されるような非常にインパクトのある研究です。各種DBベンダーもこの方式を実装し始めているのではないかな、と思っています。（複雑なトランザクションの処理で新たなボトルネックが出てくる可能性はありますが）

参考文献：Alan Fekete , Dimitrios Liarokapis , Elizabeth O'Neil , Patrick O'Neil , Dennis Shasha, Making snapshot isolation serializable. ACM Transactions on Database Systems (TODS), June 2005　(なぜsnapshot isolationをserializableにできるか、という証明部分。こちらも面白い）

S Harizopoulos, DJ Abadi, S Madden and M. Stonebraker. OLTP Through the Looking Glass, And What We Found There. SIGMOD 2008.

もう一つもトランザクション関連。MITのStonebraker教授(PostgreSQLを作った先生）のお弟子さんたちの研究ですが、現在主流のrow-oriented storage（テーブル行単位でディスクに配置していくもの）で、ロックマネージャーを外し、ログを外し、、、とやっても、トランザクションで100倍の性能を上げるのは難しい、ということを示した論文。近年、彼らの研究は面白くて、C-Store (列ごとにテーブルを分割して圧縮。性能抜群）や、 H-Store(トランザクションの意味を考えて、仕事の単位を分割、sequentialに処理して速度を稼ぐもの)など、One-size doesn't fit all (DBMSも用途に応じたものが必要）という時代の流れをリードしていく存在で、要注目です。

Taro L. Saito and Shinichi Morishita. Relational-Style XML Query. SIGMOD 2008.　(ACM DOI)

手前味噌で申し訳ないのですが、XMLで表現されるデータ構造を「そのまま保持することに価値がある」と錯覚していた時代に区切りをつけるために、どうしてもこの研究が必要でした。ポイントは、XMLの構造そのものが重要なのではなく、XMLが含んでいるデータモデル(スキーマ）の方が大事で、「XMLの木構造はそのデータモデルの一表現にすぎない」、と示したことです。（参考：「Leo's Chronicle: XML時代の終焉 ~ XMLから再びCoddへ」）木をそのまま維持しなくてもよいようになると、XPath, XQueryなどの問い合わせ言語、インデックス、ストレージなど、従来のXML研究を見直していくことができ、木構造に捕らわれていては難しかったもの（例えば、木構造を保持した索引で、サイズが小さくかつ、更新しやすいものは、未だに作られていません）でも、木構造を捨てることで様々な最適化が期待できるようになりました。

C. Olston, B. Reed, U. Srivastava, R. Kumar and A. Tomkins. Pig Latin: A Not-So-Foreign Language for Data Processing SIGMOD 2008.

Yahoo!のグループによる、分散計算と、構造化データを意識した新しい問い合わせ言語の設計、実装です。GoogleのMap-Reduceでは、分散計算を手軽に書けるのが特徴ですが、key, valueのペアでデータを出力するという枠組みは低レベルすぎで、構造を持ったデータをどんどん組み立てて処理を続けていくプログラムを書くには大変でした。

Yahoo!のPig Latinでは、データをグループ化したり、ネストさせたりする処理を導入して、プログラマの負担を軽減することを狙っています。似たような例として、フラットなSQLでは書きにくいのだけれど、XQueryだと階層をたどってデータを出力するプログラムが書きやすいという話があります。言語の能力的にはどちらが上ということもないのですが、「書きやすさ」は歴然と違う。SQLやkey->valueだけでは不便だったことを改善していく試みは、Relational-Style XML Query(XQueryでも不便だった階層を持ったデータの扱いを簡単にする）にも通じるところがあって、非常に関心を持ってウォッチしています。

Remembering Jim Gray. Communications of the ACM 2008, Vol 51. No. 11.

最後は論文ではなく、雑誌記事の紹介です。1998年にTuring Award（コンピュータ系での言わばノーベル賞）を受賞し、 2007年にボートに乗って遭難してしまったJim Gray。トランザクション処理で大きな功績を残した、そんな彼に寄せられた記事を集めた特集号です。一人の研究者にこれほどのtributeが集まるのはすごいことです。Jim Grayは、ロックの粒度（テーブル単位、レコード単位のロックなど）を織り交ぜて使う手法を開発するなど、今なおその技術はDBMSの実装に使われています。トランザクション処理は非常に身近な存在です。銀行しかり、駅の改札もしかり。現代社会でJim Grayの恩恵を受けていない人はいないと断言しても良いです。

僕自身、Jim Grayとは巨大な生物データの扱いについてメールで議論したこともあり（駆け出しの研究者の僕にも、丁寧に返事をしてくれるような優しい人でした）、そんな彼が遭難したと聞いたときは、心にぽっかり穴があいたような、そんな気持ちになりました。僕だけでなく、やはり、これだけ多くの研究者に慕われているこの人の話題は外せない、ということで。2008年は彼の功績を振り返ってみるよい機会になった年でした。

以上、僕個人としてのトップ５研究でした。データベースは領域が広いので、興味が違えば、まったく別のランキングになるとは思います。SIGMOD, VLDB, ICDEなど国際会議もいくつかあるのですが、実際に会議に参加して雰囲気を肌で感じることができたのはSIGMODだけなので、とても偏ってますね。他の研究者による別の切り口での紹介も欲しいな、と思います。

2009年1月14日水曜日

なぜIEはFirefoxより優れているか？

Firefoxでこんなことできる？

(Diggで見つけました）

2009年1月13日火曜日

TOEIC990点より大事なこと

ごめんなさい。タイトルは釣りです。TOEICは受けたことすらないので、990点がいったいどんなレベルなのか想像もつきません。ただ、「英語を使う」のが目的なら、そんな点数を上げるための努力はしなくていいだろうなとは思ったので、英語を使う、特に「話す」ための要点をまとめてみます。

この記事を書くきっかけとなったのは、「英語の発音」というエントリが注目を集めているのを見て。英語の発音を気にしている人が多いことに驚きました。

僕自身、国際学会などで海外に行く機会は年に何回かありますが、そこでのトークを聞くと、中国系の人、インド系の人、東南アジア系の人、ヨーロッパ系の人とで、それぞれ発音の仕方が全然違うことがわかります。中でもインド系の人の発音はあまりブレス音を使わないせいか、慣れないうちは本当に英語を話しているのか？と耳を疑うほどです。日本語の方言をイメージすると、この状況がわかりやすいと思います。東北弁などは、聞き慣れない人にとってはまるで外国語のように聞こえますよね。

発音は違えど、皆、英語という共通語を通して、コミュニケーションをとっている。ただ、方言と違うのは、使っている言葉は書いてみるとほとんど同じだというところ。論文など研究の世界の「普遍語」としての書き言葉を見るだけでは想像もつかないほど、実際の英語の発音の仕方は多様です。その様子を肌で感じると、「発音」などはさほど気にするべきことではなく、むしろ淀みなく話す「流暢さ」に重きを置く学習の方が、実践で役に立つことがわかると思います。

「発音」に関しては、日本の学校教育の中で触れられることがないのが不思議ですが、フォニックスという小学校低学年前後くらいの子供のための、英語の発音の学習法があります（親が英語教師だったので、子供の頃に教材で遊んでいました）。綴りと発音の関係、舌、息などをどのように使うか、ということを学び、以下の「英語、好きですか？アメリカの子供たちは、こうしてＡＢＣを覚えます」というフォニックスの本では、子供が読めるように発音についてやさしく丁寧に説明されています。簡単な内容ですが、それでも発音に関しては、この本で十分なことを学べると思います。

一昔前と違って、英語の音声はPodCastや、Talking Issuesなどでも、簡単に手に入るようになりました。もう、10年前とは時代がすっかり変わっていることに世の中も気付くべきでしょう。英語で授業ができなかったり、生の英語を聞き慣れていないためにカタカナ発音になってしまう英語の先生よりも、今やインターネットの方が相当いい先生になり得ます。生徒の方が先生よりも流暢な英語を話す、なんてことも十分あるので、先生のコンプレックスが、そんな生徒にぶつけられないことを祈るばかり。電子辞書もあるし、インターネットも辞書代わりになるので意味・用例を調べるのも簡単とは、なんていい時代！

そんな生の教材を使って、音声の後に続けて実際に声を出してみるシャドーイングを続けていくだけで、「話す」だけでなく「聞く」力もついてきます。これは、こどもの言葉の学習法と同じ。わからなくても、聞き取れなくても、とりあえず聞いたことを繰り返す。ただ、状況に応じた言葉を聞く機会が無い、というのが、日本で英語を学ぶ難しさではありますが。

そして「流暢さ」に必要なのは、お願いや質問の仕方、意見の言うときの決まり文句など、中学校の教科書に出てくるくらい簡単なフレーズが、口をついて出てくるかがポイントです。英語の学習用教材など、市販の本もいくつか漁ってみたのですが、難しい文章の読解向けで会話には役立たなかったり、単語、熟語の羅列で継続して学習するには飽きやすい本とか、会話用のテキストでもストーリーを重視しすぎてフレーズの絶対量が少ない、などそれぞれいろいろ難があります。そんな中で一番役に立ったのは「英会話 Make It!」という小さな本。

こんなことが言いたいのだけれど、英語で出てこない。そんなかゆいところに手が届く表現が状況ごとにまとめられているので本当に助かっています。慣用句など洒落た表現ではなく、2、3回繰り返して発音して練習するだけで、明日話すためにすぐ使える（くらい本当に基礎的な）フレーズを効率よく学べるのが良いです。

英語でディスカッションを始めて、言葉に詰まってしまう日本人を見ると、この本にあるくらい簡単な表現すら自分で話した経験がないのだろうな、といつも感じています。Whatで始まる質問ができない、とか。本当にそんな程度のことです。でも、それを自信を持って話せるのとそうでないのとで、会話が成立するかどうか、さらには、有益な情報を相手から引き出し、メッセージをきちんと相手に伝えられるかどうかが決まります。

まとめ

世界中でバラバラなんだから発音なんて気にしない。練習したければ、小学生から使えるフォニックス教材で発音の仕方を学んで、インターネット上の先生（ニュース、PodCastなど。自分の好きな話が良い）に倣ってシャドーイングを続けること
本当に簡単なフレーズを練習して、自分の意見を話したり、質問するときの英語に自信を持つこと。

これだけで、そこいらの東大生より確実に英語が上手に話せるようになります。。。（悲しいことに、これは本当の話です。でも、これが英語での会話を教えない（教えられない）日本の英語教育の現実）

Leo's Chronicle: 英語コンプレックスなんて些細なこと（もうちょっと上のレベルに達したときに感じる英語の壁について）
Leo's Chronicle: 良い論文を書くために知っておくべき５つのこと (論文を書くときには、英語力以外の要素も要るという話）

登録: 投稿 (Atom)