140文字で書ききれなかったのでブログに殴り書き。 Heroku のアプリケーションを人に渡す 昨日、「naoyaさんが作ってるiOSアプリのバックエンドサーバーに相乗りさせてもらえないか」という話をいただいた。自分でも同じようなAndroidアプリを作っているけど、サーバーサイドは作ってないからということらしい。 対して「githubにコードあるからgit cloneしてheroku pushすれば動くし、自分で heroku にデプロイしてよ」と応えた。相乗りしてもらってもよかったのだけど、こちらでコードを書き換えたりメンテしたときに先方のアプリが停止することを考えると同じコードベースでサーバーは自分で立ててもらう方が何かと良い。 対象になったソフトウェアは Heroku で動かしていたので、Heroku Ready な形、つまり、必要な外部パッケージの一覧やサーバーの起動手順なんかは

This is why you shouldn't interrupt a programmer (なぜプログラマの作業に割り込むべきではないか) という4コマ漫画が話題になっていた。これは別にプログラマではなくても「わかるわかる」という感じの話。 コメントを見ると、だから作業を中断してもすぐ再開できるように自分の考えることをなるべく書き出すようにしているという人が結構多かった。なるほど。 今日は雨が降ったせいで予定が一つキャンセルになったことだし、ちょうどいい機会なので、文章で何かを書くということについて自分が思っていることを書いてみようとおもう。以前 Software Design のドキュメントの書き方特集みたいな号に似たような趣旨の話を寄稿したのだけど、「書く」というのは単に物事を忘れないようにするための行為に留まるものではなくて、自分の考えを整理するための道具なのだ、ということが

昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下

圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更

情報検索におけるベクトル空間モデルでは、文書をベクトルとみなして線形空間でそれを扱います。この文書ベクトルは、文書に含まれる単語の出現頻度などを成分に取ります。結果、以下のような単語文書行列 (term document matrix) が得られます。 d1 d2 d3 d4 Apple 3 0 0 0 Linux 0 1 0 1 MacOSX 2 0 0 0 Perl 0 1 0 0 Ruby 0 1 0 3 この単語文書行列に対して内積による類似度などの計算を行って、情報要求に適合する文書を探すのがベクトル空間モデルによる検索モデルです。 見ての通り、単語文書行列の次元数は索引語の総数です。文書が増えれば増えるほど次元は増加する傾向にあります。例えば索引語が100万語あって検索対象の文書が 1,000万件あると、100万次元 * 1,000万という大きさの行列を扱うことになりますが、単

圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;

,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ|　　　　　　　　　　あ…ありのまま 今日　起こった事を話すぜ！ |i i|　 　 }!　}} /／| |l､{　 　j}　/,,ｨ//｜　　　　　　　『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' }　 ,ﾉ　_,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ　, ﾀ人　　　　　　　　な…　何を言ってるのか　わからねーと思うが /' 　 ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ　　　　　　　　おれも何をされたのかわからなかった… ,ﾞ　 ／ )ヽ iLﾚ 　u' |　| ヾｌﾄﾊ〉 |／_／　 ﾊ !ニ⊇　'／:} 　V:::::ヽ　　　　　　　　頭がどうにかなりそうだった… /／ 二二二7'T'' ／u'　__ /:::::::/｀ヽ /'

先日のソーシャルブックマーク研究会では id:kanbayashi さんによる発表がありました。id:kanbayashi さんは Kikker や はてブまわりのひと などの開発をされている方です。最近情報検索理論に入門した自分にとっては、非常に面白い発表でした。 発表の中で Kikker の学習の仕組みについての解説もありました。Kikker は Cosine similarity で推薦するドキュメントを検索しているそうですが、ユーザーのクリックデータを使って、ユーザーごとに推薦対象を最適化するようにしているそうです。この学習は、ユーザーが見たページのベクトルを、そのユーザーの趣向ベクトルに足し込むことで実現している、とのことでした。 SBM研究会で発表した"私がチャレンジしたSBMデータマイニング"のスライド - Ryoの開発日記 Neo! 発表ではベクトルを加算することについて「