おひっこし
ブログを引越します。こっちは別の用途に再利用するかも。
新URL → http://tkng.org/b/
"高速文字列解析の世界"を読んだ
高速文字列解析の世界というタイトルからは、どんな中身なのかあまり伝わってこないので、どんなことが書いてある本なのか、中身をちょっと紹介してみる。
1章、2章は概観や準備であり、3章からが本番なのだが、Burrows Wheeler Transform、簡潔データ構造、ウェーブレットツリー、データ圧縮、全文検索、テキストマイニングのためのデータ構造、という章題になっている。
何に使うのかという目的ベースで考えると、この本に載っているのは、データ圧縮、情報検索とテキストマイニングの基盤技術である（データ圧縮については基盤と言うよりはそのものだが）。ただ、この本には本当に基盤技術の話しか載っていないので、「この本で情報検索はバッチリだぜ！！」というような訳にはいかない。テキストマイニングに関しても同様である。別途入門書を読むなりしないと、より高次元（ここでの高低は技術の積み重ねの高低であり、難しさの高低ではない）の知識を手に入れることはできない。
というわけで、全くの初心者にこの本をおすすめするというわけには行かない（基盤側の技術についてから上側の機能を推測できるようなレベルの人ならば話は別で、そういう人もいっぱいいるとは思うけれど）のだが、初心者向けの本、例えば 情報検索の基礎とか検索エンジンはなぜ見つけるのか ―知っておきたいウェブ情報検索の基礎知識のような本を読んだけど、次に何を読めばいいのだろう、というような人に、これまではThe Burrows-wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching のような洋書を薦めるしかなかった（もしくは「SIGIRの論文とか読むといいよ？」と言うぐらいか）のだが、これからは多少ハードルを下げ、日本語の本を薦めることができるというわけだ。あと、The Burrows-wheeler Transformの方は読んでないけど、たぶんこっちの方が新しいことが書いてある。Wavelet Matrixとか。
というのが一般的な話だと思うのだが、個人的には前から読みたかった話が色々と書いてある。以下にまとまりのない感じで感想を述べる。
XBWはとりあえず理解した。XBWのアイデアは賢い。BWTの拡張になっていてLF-mappingが成り立つのである。賢い。賢いがLOUDSと比べてどれぐらい速いんだろうか。ちょっと気になる。あと、marisa-trieで使ってる再帰的Trie分解と組み合わせることができるし、パトリシア化もできそうなのだが、実装するとものすごく辛いだろうなぁ……。
透過的符号の話とかも面白い。透過的符号というのは、ランダムな位置から効率よく復元できる符号化方法で、書籍のほうで紹介されている手法では、ほとんどの値が小さくてたまにおっきな数字が混ざってる、みたいな配列をこれで符号化するとサイズが小さくなって速度もあんまり落ちない。実装も簡単そう。
ウェーブレットツリーはどういうデータ構造なのかはだいたい知ってるのだが、いろいろな操作ができるという事はよく知らないのでこれから勉強したい。
接尾辞配列をInduced Sortingで作る話は難しい。寝る前にちょろちょろ読んでるのでは理解できなさそうだ。紙と鉛筆で自分で配列書いてみないとしんどい。
まとめると、情報検索やテキストマイニングなどの新しい基盤技術に興味のある人、データ圧縮に興味のある人におすすめの本であると言える。
高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)
posted with amazlet at 13.01.08
なぜあなたがウェブサイトをHTTPS化するとサイトが遅くなってユーザーが逃げていくのか
完全に釣りタイトルですけど中身は真面目に書くよ。
近年、ウェブサイトのHTTPS化が流行のようになっている。私の知る限り、Googleの各種サービスやTwitter、Facebookなどが完全にHTTPSで通信を行うようになっている。HTTPS、つまりSSLによる通信の暗号化によって、ユーザにこれまでよりも安全なウェブサイトを提供できる。
しかし、あなたが作っているサイトをふと思いつきでHTTPS化してしまうと、たぶん、これまでよりもサイトが遅くなる。ここでは、HTTPSで通信する場合の問題を解説する。
なぜ遅くなるのか
HTTPで通信する場合、クライアントがサーバへと接続するためにはTCP/IPの3ウェイハンドシェイクという手順が必要になる。めんどくさいのでここでは詳しくは説明しないが、要するにクライアントがリクエストを投げる前にパケットを１往復させないといけないのである。パケットの往復にどれぐらい時間がかかるかはpingコマンドで簡単に確認できる。たとえば、ping www.kyoto-u.ac.jpとかコマンドを打つと、おそらくは京都にサーバがあるであろう京都大学のサイトにパケットが行って戻ってくる時間が計測できる。1往復で約30msぐらいだった。東京-京都間（500kmぐらい？）で30msということを覚えておきたい。
30ms、つまり0.03秒であればそんなに大したことのない数字である。
実は、HTTPSでは通信をはじめる前に必要なパケットのやり取りが3往復になる。3往復するとなると0.09秒、もうほとんど0.1秒待たされることになる。ちょっとそろそろ人間が知覚できるぐらいの時間になってきた。
他にも悪いニュースがある。SSLの証明書にはOCSP(Online Certificate Status Protocol)という証明書を失効させるための仕組みがあるのだがこれが遅いのである。この仕組みを要約すると、証明書を受け取ったら実際に通信を始める前にOCSPレスポンダと呼ばれる失効情報を管理するサーバに対して、証明書が失効していないかどうかを確認する、というものである。別のサーバに問い合わせが発生するため、DNSで名前を解決したり、サーバにリクエストを飛ばしたり、といった手順が必要になり、通信の開始が遅れるわけである。安いSSL証明書を使うとOCSPレスポンダが海外にしかなかったりして悪影響が大きい。OCSPは最近のブラウザであればほぼ確実に対応している。
なんでOCSPのような仕組みが必要なのか。証明書というのは技術的には公開鍵暗号の公開鍵側なので、対応する秘密鍵が漏れた場合には悪用を防ぐために失効させる仕組みがほしい、ということでこんな状況になっている。以前は失効した鍵のデータベース（Certification Revocation List）をダウンロードするという方式だったようだが、最近のブラウザは全部OCSPに移行したみたいだ。
ここまでの説明を繰り返すと、HTTPSで通信を行うことになると、TCP/IPの分で1往復、SSLの分で2往復の遅れが発生し、OCSPチェックで2往復から4往復程度はパケットの往復が発生する。4往復、というのは、安い証明書だと中間証明書というものが入っており、中間証明書にもOCSPチェックが必要だからである。OCSPチェックで海外にリクエストが行く場合はこの往復は30msとかそんなかわいい数字ではなく、1往復で200msぐらいかかったりする。実際にはOCSPには300ms程度はかかるのがふつうみたいだ。
という訳で、SSLを使うと通信が始まるまで、HTTPの場合と比べ、最低でも120ms程度の遅延が発生することを覚悟しないといけないのである。
Googleでは0.4秒レスポンスが遅くなるとクエリ件数が0.6%程度減少するそうなので、うん、120ms程度だとそんなに気にするほどじゃないかな……。ただ、OCSPチェックで0.5秒とかかかると、ちょっと無視できない感じになってくる。
速くする方法はあるのか
というわけで、SSLを使うと、レイテンシがある程度増えることは仕方がない。しかし、多少の対策は取り様がある。以下ではいくつかを解説する。
1つめはSSL False Startと呼ばれるSSLの通信開始方式である。これはSSLで必要なパケットの往復回数を2回から1回に減らしてくれる。ただ、ブラウザ側がサポートしていないと使えない。Google Chromeではデフォルトで有効化されている。Firefoxでは実装されているがデフォルト設定では無効になっている。ユーザがGoogle Chromeを使っていることを祈るだけなので、対策とは呼べないが、有効ではある。
2つめは、OCSPステープリングと呼ばれるTLSの拡張である。これは、OCSPレスポンダの返答をあらかじめサーバ側がキャッシュし、通信時に証明書と一緒にクライアントに送りつけることで、クライアントではOCSPのチェックを省略できる、というものである。証明書と一緒にホチキス留めしてしまうイメージなのでステープリングと言うのだろう。自分で自分の使ってる証明書が正しいと言ってるだけで安心できないのでは、と一瞬思ってしまうのだが、OCSPレスポンダの返答は改竄できないようになっているので、これでも大丈夫である。これを使うとOCSPチェックが省略できる。Apacheであれば2.4系列であれば対応している。Nginxはまだ安定版ではサポートしてないようだ。開発版ではサポートしている。OCSPステープリングは強力だが、1つの証明書に対してしかステープリングできない。このため、中間証明書が使われている場合、OSCPチェックを完全に省略できるわけではない。
この他に有効な対策としてはKeepAliveの秒数や同時接続数の設定を見直すことが挙げられる。HTTPセッションを使いまわすことができたら、上記のぐちゃぐちゃとしたパケットの往復は全部すっ飛ばすことができるからである。ただし、初回接続時には効かない。
蛇足
OCSP staplingについて調べると、たぶん上の方にCloudflareとGlobalSignの提携でSSLが速くなるよ〜、みたいな話がtechcrunchに載っていたがのが出てくるのだが、あの記事には間違いがいくつかある。というか、2つの話をごっちゃにしてしまって、結果として間違いが生じている。1つめはCloudflareがSSL経由でファイルをデリバリーする際にOCSP staplingを行うようにして高速に配信できるようになったよという話で、これにはGlobalSign側のシステムには何ら変更は生じていない。2つめはGlobalSignがCloudFlareを使ってOCSPサーバを世界中に配備したよという話で、こちらはOCSP staplingとは関係がない。（OCSP staplingを使うならばOCSPサーバは多少遅くても問題はない。いや、実際には中間証明書の問題があるから遅いと問題なんだけど。メジャーな中間証明書ってあんまり多くないはずなので比較的問題は少ない……はず……。）時系列が非常に近く、話も複雑なので仕方がないと思う。CloudFlareのブログ記事の冒頭にOCSP staplingの話が載っていたので誰かが勘違いしたのだろう。
調べていて最初は理屈が通らずに混乱したので、同じ道を通る人が減るようにここに書いておく。
参考URL
- http://www.imperialviolet.org/2010/06/25/overclocking-ssl.html
- http://blog.cloudflare.com/ocsp-stapling-how-cloudflare-just-made-ssl-30
- cloudflareがOCSP staplingを有効にした時のブログ記事。実際どれぐらい速くなるかが書いてある。
2012年振り返り
- 本を出した
- 2年ぐらい書いてた本が出版された。
- 本が出たらもっとこう素敵なことがあるかと思ったけど、特になかった。
- でも、読みましたよっていろんな人に言われて嬉しかった。
- あんまり情報系をきちんと勉強してないという引け目をずっと感じてたんだけど、本も出せたし、やっと吹っ切れてきた。
- 痩せた
- 5kg太って5kg痩せた。プラマイゼロ。
- ACLに行った
- サッカーではなく自然言語処理の学会の方。会社の宣伝ブースを出しに行ってきた。
- DYKSA事件、Good Water事件などいくつかの事件に遭遇したが、無事に帰ってくることができた。
- 世界最高峰の学会レベルを感じることができて勉強になった。
- ホテルは@unnonounoと相部屋だったのだが、マジックミラーではないのだが、部屋から風呂場が微妙に見えるのがやや気まずかった。
- NIPSに行った
2012年にやった仕事は公開されてるものが1つもないので、仕事面では書けることは特にないのだが、会社ブログのCentroid Path Decompositionの記事とBWTとLF-mappingの記事は、だいぶ気合を入れて書いた。どちらもあんまり注目を集められなくて悲しかった。
2012年は本を出したあとはずっと燃え尽きてた感じ（そろそろ復活しないと、と思ったあたりで祖母がなくなったり愛犬がなくなったりでなかなか立ち直れなかった、これらに関しては色々後悔がある）だったので、2013年はそろそろ再起動して、インプットとアウトプットと、バランスよくやっていけたらいいなと思っている。
RethinkDBが良さそうな気がしたので調べてみた
日記書くの数カ月ぶりだけど、以下、何事もなかったかのように再開します。
HackerNewsでRethinkDBのニュース記事が上位入賞していたのでちょっと調べてみた。MongoDBライクな感じで、独自のクエリ言語で使えるみたいだ。
RethinkDBは元々はSSDに特化したMySQL用のストレージエンジンだったのが、方向転換してMemcached互換なサーバになった（そしてSSD特化という特徴を捨てた）というところまでは知っていたのだが、いつの間にこんなクエリ言語を備えていたのか。方向転換のニュースを見た時にはふーんぐらいにしか思わずオフィシャルサイトはチェックしなかったので、実は去年の時点ですでにクエリ言語とかも備えていたのかもしれないけど、githubとかで調べた感じだと1.2.0がThis is the first release of the productと書いてあるところからすると、最近大幅に変わったバージョンが公開されたばっかりっぽい。
HackerNewsへのCEOの書き込みから引用すると、MongoDBと比べて
- 分散joinとかサブクエリとかできるよ
- MVCCだよ
- クエリが並列で実行されるよ
というあたりがウリらしい。分散joinができるのは珍しい気がする。joinはマイニングしてると結構ほしくなるので、分散環境でデフォルトでできるのはポイント高い。
あと、v8を使っていて、サーバ側でコードを実行できるみたい。この機能は面白いし、いろんなことができそう。（v8は別プロセスで実行されるそうだ。）
現状だとそもそもprimary key以外にインデックスが張れないということでちょっと試しに使ってみる分にも辛そうな感じだが、しばらくは今後の推移を追いかけたい。
日本語入力を支える技術 振り返り、もしくは技術書を書きたい人へ
本を書いてからこっち、年度末で忙しかったり、体調がずっと悪かったりしていますが、そろそろ本気出します。正誤表も大幅にアップデートします。今書いてる。
今日は、本を書いてみてどうだったか、ということをふり返る。たぶんこれで本について触れるのは最後かな。宣伝はたまにすると思いますが。
※思いがけず大量にアクセスがあったから、最後に追記を書いたので、そっちも読んでね！
本を書いたきっかけ
会社の方でPFIセミナーという勉強会のようなものをやっており、なぜかそれがUStreamでインターネットに中継されているのだが、そこで日本語入力の話をしたら「本書かない？」って話が来た。編集さんとは、その前年に会社に来たWEB+DB Pressの記事執筆依頼で記事を書いた際に知り合ったので、そういう意味では貪欲にチャンスを掴みに行った結果であると言えなくもない。
PFIセミナーがUSTで中継されるようになったのは本当にたまたまで、前週の担当だった当時バイトの@sotarokが「USTは嫌だ」って返事してたらたぶんこの本の著者は私ではなかっただろう。人生は偶然に大きく左右される。しかし偶然とはいえ、USTの動画が公開してあったから依頼がきた訳で、情報を公開しておくことの重要性も伺える。
以下、本を書くときに自分がやってよかったこと、悪かったことを振り返る。
書くためにやって良かったこと
- 最初に書きたい内容をリストアップした。
- どんな本にするかイメージが湧く。
- ReVIEWを使ってPDFを自動生成できるようにした。
- 文字数をカウントしてグラフ化した。
- 残り文字数がどれぐらいなのか、一応の目安になった。最終的には当初予定文字数を大幅にオーバーしたのであんまり目安になってなかったけど…。
- 原稿をgitで管理した。
- チケット管理システムを使った。
- 作業忘れの可能性をだいぶ減らせた。（今残ってるチケットも実際には目を通して対応はしてある、はず…。）チケットの粒度は細かいほうがいいんだけど、そうするとチケットを切るときの手間が増えるとかそういう問題があって、そこら辺はうまく解決できなかった。
- 単著で書いた。
- 共著だと、自分だけが書き上がっている状態も、逆に自分だけが書きあがってない状態もどちらもかなり辛い。共著はお互いに強い信頼で結びついた人がやるか、もしくは人数を多くして誰かがサボってもなんとかなるような状態でないとうまくいかないと思う。
- 割と多くの人にレビューしてもらった。
- 非コミュの自分としてはびっくりするぐらいの人数にレビューをお願いできた。レビューによって間違いも大幅に減ったし、分かりにくい部分もかなり減らせた。
- 何人かにはピンポイントで見てもらいたいところをお願いした。これによって1章、2章にレビューが集中しがちであるという問題もかなり解消されたと思う。（小町さんが後ろ側からレビューしてくださったというのもある。結局小町さんには全体を相当詳しくレビューしていただいたけど…。）
- 30インチのディスプレイを買った
- 地味だが作業効率にムチャクチャ効いた。PDF見ながら校正のテキストを書くとか、これがないとどうなっていたことか。20万弱だったけどそんだけの価値は十分にあった。
失敗したこと
- 書きたい内容をより詳細にブレークダウンして見積もるべきであった。
- ページ数が100ページ近く膨らんだ。
- 書くのに時間がかかりすぎた。具体的には2年近くかかっている。ボツとか書きなおしを入れると4倍ぐらいは書いてると思うので、スピード的にはこんなもんかという気もするのだが、とにかく絶対的な時間がかかり過ぎである。
- チケット管理システムを他の人に使ってもらう体制にした。
- 操作が煩雑で負担をかけてよくなかった。（redmineだったというのも良くなかったと思う。）チケットの入力と処理は一人でやって、他の人は進捗だけ見れるような感じにしたほうが良かった。
- レビューの目的を明確化したほうが良かった。
- 音引きとか全角半角等の統一に関しては編集さんのチェックが後で入ります、とか。レビューにかけてもらえる時間には限りがある訳で、情報が後出しになるようなことはできる限りさけるべきだった（結構努力はしたつもりだったけど、振り返ってみると足りなかった）。
- 最後の方はかなり煮詰まった。
- 最後というか、後半はずっと煮詰まりながら作業していた。見積もりが甘かったせいで、ラストスパートの精神的な負担がかなりきつかった。
失敗と言うほどではないが何とかしたほうが良かったこと
- LinuxだとAcrobat Readerの注釈機能が重すぎて辛かった。Windowsも使えるようにしておけば良かった。
- 商用のフォントを買えば良かった。
- 印刷に使うような類のフォントでPDFを見た方が、脳の違う部分を使うためか問題を見つけやすい。リュウミンかなにかを買えば良かった。
- 書き上がる前に定期的に相談できる人を先に作っておいたほうが良かった。こういう人を監修者と言うのかな。強制的にミーティングの機会とか設けないと、人には出来上がってから見せようという気持ちが強くはたらく（この辺りは修論書いてた頃からあまり進歩してないな…）。目次を細かくブレークダウンしたぐらいの状態で定期的に議論をしていく人がいたら、主に速度面で良かったと思う。
全体的に見てどうだったか
締め切りを破ったせいなので自業自得なのだが、後半はかなり辛かった。それ以外の点は初めての書籍執筆としてはまぁまぁうまく行ったのではないか、と思いたい。
追記：自分で追い込まれていただけで、編集さんは豆腐メンタルな技術者のことをよく理解しており（さすが社名に技術と入っているだけある）、適切な対応をとっていただいた。自分にはあんな丁寧な対応はできないと思う。
売れ行き
けっこうよく聞かれるので改めて書いておく。技術書としては多分、割と売れている（そもそもWEB+DB Press Plusシリーズという時点で結構下駄を履かせてもらってる感がある）方である。しかし、実際のところ、印税生活どころではない（そしてもちろんおごるどころの話ではない、君が遊んでた時にも俺は死んだような目をしながら執筆してたんだよ！）し、技術書というのは一般論として本当に売れないものなのだなということをあらためて実感させられている。
これから自分の専門書を見る目はだいぶ変わるというか、温かい視線になると思う。出しただけでもとりあえずよく頑張ったよね、的な…。
嬉しかったこと
当たり前だが、読んでくれた人、実装してみた人の存在が一番嬉しい。書いた甲斐があったなと感じる。本を読んでダブル配列作ってみたという人も既に2,3人見かけた。
文章にするとほんの一文でしかないけれども、読者の存在が一番の理由なのだということが、書いてみて実感できた。読者がいなければ、たとえ印税が10倍になったとしても、技術書を書く人なんてこの世からいなくなるだろう。
他の人に本を書くことをすすめるか？
自分と同じ経験をするのであれば、勧めない。ただ、自分は明らかに失敗したところがあるので、もっと効率よく執筆できるのならば本を書くのは良いと思う。自分自身があやふやに理解しているところは全部勉強し直すことになるし、こんな長文を書く能力を磨く機会は滅多にない。
ひとつアドバイスがあるとしたら、編集さんが最初に勧めてくるページ数は過去のいろいろを踏まえて計算されているから、そのページ数に書きたい内容が収まらないなら、内容の方を減らすべきである、と過去の自分に言いたい。
その他
自分はプログラミングを始めたのは遅いし、プログラミング適性も普通程度でしかないことも自覚している。そもそも大学の出身学部は情報系ではないし、査読付き論文を採択率の低い学会に通したこともないまま修士も卒業してきた。ちゃんと大学院を卒業できた気がしておらず、喉に小骨が刺さったような不愉快な感じがあったのだけれど、本も書けた（世間様の評価はどうあれ、自分としては本の出来には満足している、レビュア様のおかげであるけれども。）し、そろそろ自分の中でも卒業としていいかな、というよい区切りになった。
追記：強調しておきたいこと
- 日本語入力を支える技術自体は平均よりは売れているはずだよ！ 絶対的な技術書市場自体が小さいという話だよ！
- 技術書は売れない、というのは個人の意見だよ！ 他の人の意見はわからないよ！ あと、日本の技術者人口を考えるとしょうがないとも思ってるよ！
- 他の人に勧めないのは書くのが長期間になると本当に辛いからだよ！ でもサンプルコードが出てくるような本だと、内容がふくらむと執筆が長期化するのはたぶん普通の人には避けられないよ！ 普通の人はあらかじめ守れる執筆計画を立ててから書き始めたほうがいいよ！ そういうのがなくてもすごいスピードで書ける天才もいる（某A先生は2週間で執筆するらしいという噂を聞いたことがあるよ！）けどそういう人のことはここでは考えていないよ！
rubyでpythonのdefaultdictっぽいものを実現する
Pythonのハッシュテーブル（Pythonではdictと言いますね）には、初期値が設定できる亜種としてdefaultdictというものがある。Rubyの場合、Hashクラスには初期値が設定できるが、初期値としては整数か文字列、シンボルぐらいしか使えない。初期値として配列とかハッシュテーブルを使えないのである。
そこで、Pythonのdefaultdictっぽいものを作ってみた。以下にコードを示す。
class DefaultHash < Hash def initialize(init) @init = init end def [](k) v = super k if v v else self[k] = @init.clone end end end a = [1,2,3,4,5,4,3] h = DefaultHash.new(Array.new) a.each{|k| h[k].push 1 } p hash
DefaultHash.newの部分をHash.newに変えると、嬉しい場合があまり思いつかない感じの挙動になっていることがわかると思う。
作ってみたもなにも、[]メソッドを上書きしただけであるし、nilやfalseを値として使った時のことを全く考えていないのだが、とりあえず動くので満足している。
このコードを書いた動機は、以下のようなコードを書きたくない、というものである。
if h.has_key? k h[k].push 1 else h[k] = [1] end
この例ぐらいなら場合分けを書いてもいいんだけど、ちょっと複雑な数え上げがしたくなるとハッシュがネストしたりすることがよくあって、そうなると場合分けの中に場合分けを書くことになって、やりたいことの割にコードが長いというか大仰になってしまってなんだか悲しい、ということがよくあるのだ。
デフォルトのHashでもHash.new(0)みたいに初期値を設定できるのだけど、前述の通り、Array.newみたいなのを引数に渡すとうまくいかないのである。これは同じオブジェクトを使う（ここでの同じ、という言葉はメモリアドレスが同じという意味だと考えてもらいたい。値が同じ、とかではなく、同じ物を指しているのである）のが原因である。
なぜデフォルトの挙動では初期値として同じオブジェクトを使っているのかというと、が呼ばれる度に新しいオブジェクトを作っていたのでは、存在しないキーに対してを呼ぶ度に新しいオブジェクトを作ることになるからだ。これでは、場合によってはリークに近い挙動を示すことになってしまう。という訳で、Hashクラスでは初期値（デフォルトオブジェクトと言い換えたほうがわかりやすいかな）は共有されるのである。
valueが初期値であるようなkeyはGCみたいな感じで定期的にdeleteすればいいのかなーと思うが、面倒なのでそこまでは実装してない。10000回ぐらい[]が呼ばれたらスイープする、みたいな実装だったらパフォーマンス的にも我慢できるぐらいになるんではなかろうかと思うんだけど。
