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