Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
Google を支える技術 - naoyaのはてなダイアリー
Google を支える技術 を読みました。 Google のバックエンドで動いている各種分散処理システムに関しては Google 自身から論文がいくつも発表されています。それらの論文をはじめとする比較的最近の情報ソースをベースに、ある程度かみ砕いて要所要所を紹介するという内容でした。加えて著者の西田圭介さんは OpenCobol (COBOL を C 言語に変換しコンパイルする gcc のフロントエンド) を開発された、技術的なバックグラウンドがしっかりしている方であるようで、内容は信頼できると思います。 自分はこれまで Google のバックエンドの各種ソフトウェアについては方々で耳にしていましたが、漠然と何をするものか程度のことしか知りませんでした。 Web 検索の基本的な仕組みと それにまつわる Google が直面した問題、特に大規模処理 それを支えるために開発された各種ソフトウェ
「リーン」について : 「何を作るか」よりも「何を作らない」か - naoyaのはてなダイアリー
2013年に「リーン・スタートアップ」という書籍が出版されて、それからリーン (LEAN) という考え方に注目が集まるようになった。LEAN とは「無駄のない」とか「ぜいにくのない」とかそういう単語らしい。 書籍リーン・スタートアップには「スタートアップやその類が新しい事業を始めるときに普通にやってるとだいたい失敗するから、潜在顧客や顧客からのフィードバックをこまめに集めて軌道修正しながらゴールを見極めるやり方が良い」とか、雑にまとめるとそういうことが書いてる。 仮説を立ててフィードバックをもらって検証するということを短いイテレーションで繰り返す･･･というのを "フィードバックループ" と呼んでいて、それを細かくやる場合、製品を作り込んでからフィードバックをもらうのでは遅いし、例えばペーパープロトタイプをするとかそういう実験的なことで欲しいフィードバックが得られるならそれが一番いい ─
インターフェイス指向設計 - naoyaのはてなダイアリー
本を読むこととは、その本を読んだことに費やした時間の間、その書籍のテーマについて考えを巡らせることではないか、と近頃思います。本を読みながら集中して、ある特定のテーマについて考え続ける。本を読み終えた頃には、その思考の量的な価値が、自らの中で質的な価値に変換されているというのが理想であり、それが読書の醍醐味ではないかと思います。 インターフェイス指向設計 ―アジャイル手法によるオブジェクト指向設計の実践 を読みました。この書籍はシステム設計における「インターフェイス」(ユーザーインターフェイスではなく、プログラムインターフェイス) についての書籍です。インターフェイスについて考えを巡らせるにあたって、思考のための指針を与えてくれる良著だと思います。 プログラムインターフェイスというものをどのように捉えるか。ファイルをブロック単位で読むための手順であるとか、ソートのアルゴリズムであるとか、そ
日本語で読める IT名文書 三選 - naoyaのはてなダイアリー
pplog の方に書いたけど、別にブログに書けばいいかと思い直したので投稿。Slack でチャットしてて、なんとなくこれ面白いよ URL を共有する機会があったので適当に選んだもの。 伽藍、バザール、ノウアスフィア、おなべ(3) http://www.artonx.org/diary/20120411.html#p01 artonさんがノウアスフィアの開墾についてわかりやすく書いてるもの。原文はちょっと長くて読むのが大変だけど、こっちは分かりやすいし、面白い。OSS の構造がなんかわかったきになる、すごい。 Steve Yegge の Google とプラットフォームに関するぶっちゃけ話を訳した http://anond.hatelabo.jp/20111018190933 (前編) http://anond.hatelabo.jp/20111018192953 (中編) http://a
Github を使って雑誌原稿を書く - naoyaのはてなダイアリー
今日はこのあと Github の Tokyo Drinkup January 2014 に行くのだが、先方から、もしかしたら 10分ほど Github について話してもらうかも、と打診された。話すか話さないかわからないが、もし話すとしたらと仮定し内容の整理も兼ねて以下「Github を使って雑誌原稿を書く」ということについて書いてみようと思う。 「Github を使って雑誌原稿を書く」もしくは「Github を使った雑誌編集者とのコラボレーション」について、である。 Web+DB PRESS の連載 ご存知の方もいるかもしれないが、このところ技術評論社の Web+DB PRESS で連載をしている。連載を始めて、もう一年近く経った。以前にも Perl に関する連載をしていて、そのときも数年ぐらい続けたので、間があきつつも、なんだかんだでそれぐらいの付き合いになる。 最近は特にテーマは決めず
Cask - naoyaのはてなダイアリー
昨年 ELPA で elisp を管理 - naoyaのはてなダイアリー に書いたとおり、昨今は Emacs にもパッケージ管理システムが搭載されいて、どこからか elisp をコピペしてきてその後管理できなくなる･･･みたいなことはなくなった。 ただ、じゃあ ELPA で全て解決したかというとそんなことはなくて、ELPA はパッケージのインストール自体は簡単にしてくれるけれども、それだけだった。 elisp の管理も Bundler のように入れたいパッケージ一覧を書いて bundle install すれば全部まとめて入るみたいな、そういうのが欲しい･･･と常々思っていた。 と思っていたら、Cask というのを見つけた。これがずばりそのものだった。 (source gnu) (source melpa) (source marmalade) (depends-on "ag") (dep
Sqwiggle が良いという話、またはリモートでアジャイル開発をどう進めるか - naoyaのはてなダイアリー
KAIZEN platform Inc. は、新しい働き方をいろいろ試してみようという会社でそのひとつにリモートワークがある。リモートワークの良さあるいは良くないところについては、以前に Rebuild.fm の ep.32 でも話した。 ちかごろは、オンラインミーティングのための道具、情報共有のための道具もクラウドサービスがたくさんあるので、その辺を使って工夫すれば一昔前に比べてだいぶリモートワークも現実的になってきている。実際、KAIZEN には大阪からリモートワークしている人とか、最近リモートワークを前提に都内から鎌倉に引っ越したメンバーなんかもいる。 リモートワークとアジャイル開発 HipChat、Google Hangout や Qiita Team なんかを使うことで、日常の会話、ミーティングや情報共有についてはもともと特に困ったこともあまりなかった。特に Qiita Team
ELPA で elisp を管理 - naoyaのはてなダイアリー
「おれはEmacsをインストールしたと思ったら Emacs24 をインストールしていた。な、何が起こったかわからねーと思うが･･･」 「いいえ、わかります。」 気づけば Emacs を brew install で Emacs24 になっていたわけです。これまで何年も .emacs.d 以下に適当に集めてきた elisp を放り込んでは init.el をちまちまといじる日々でしたが、そういえば 24 には ELPA (Emacs Lisp Package Archive) が標準搭載されるとか聞いたなーと思いまして、年末のドラクエバージョン1.2に伴う怒濤のレベル上げや 忘年会、大掃除や新年会などで疲れた体を鞭打ち、elisp を整理する作業をしています。 ELPA は Perl で言うところの CPAN、Ruby で言うところの rubygems、vim で言うところのはしらないけど、
やる気と身体 - naoyaのはてなダイアリー
ひとたびフロー状態になると、それを維持するのは難しくない。私の一日の多くはこんな感じだ: (1) 仕事にとりかかる。(2) emailをチェックしたり、Webを見たり、そのほかのことをする。(3) 仕事に取りかかる前にランチを取ったほうがいいと判断する。(4) ランチから戻る。(5) emailをチェックしたり、Webを見たり、そのほかのことをする。(6) いい加減はじめたほうがいいと心を決める。(7) emailをチェックしたり、Webを見たり、そのほかのことをする。(8) 本当に始めなきゃいけないと、再び決心する。(9) くそエディタを立ち上げる。(10) ノンストップでコードを書いていると、いつのまにか午後7:30になっている。 ステップ8とステップ9の間のどこかにバグがあるようだ、私は必ずしもこの溝を飛び越えられないからだ。私にとっては、ただ始めることが唯一困難なことなのだ。静止状
宮川さんのポッドキャストと、昔話 - naoyaのはてなダイアリー
第１回はnaoyaさん(@naoya_ito)をゲストに迎えてポッドキャスト、LTSV、RubyMotion、Perlなどについて話しました。 もう昨晩のことになってしまいましたが @miyagawaさんのポッドキャストに出演しました。初めての経験でしたが、喋っている方としてもとても楽しめました。 話の内容的には、LTSV にはじまり RubyMotion、AWS など最近ブログに良く書いていたことと、宮川さん持ち出しネタの Ruby の Topaz、Perl の Moe などなど。1時間ほど、実装系の話をしてみましたがよくよく考えると1時間いろんな技術ネタについてじっくり対話する･･･という機会はあまりないですね。またやりたい。 今何でポッドキャストなのかとかその辺の背景は実際の番組内にあるので、興味のある方はぜひご試聴ください。なお、Ruby の話をいろいろしてたら matz が聴いて
prototype.js でデザインパターン - Singleton
次は「たった1つのインスタンス」Singleton パターンです。あるクラスがあって、そのクラスのインスタンスは実行アプリケーションのライフサイクルを通じて唯一に制限したい、何回生成しても同じインスタンスである、というものです。 var Main = Class.create(); Main.prototype = { initialize : function() {}, main : function() { document.writeln('Start.<br>'); var obj1 = Singleton.getInstance(); var obj2 = Singleton.getInstance(); if (obj1 == obj2) { document.writeln('obj1 と obj2 は同じインスタンスです。<br>'); } else { document
リアルグラフへの違和感 #補足 - naoyaのはてなダイアリー
リアルグラフへの違和感 (http://d.hatena.ne.jp/naoya/20120605/1338873268) ということを書いたら思った以上に反応がたくさんあっておもしろかった。数日経って冷静になってみると、もしかしたら居酒屋で飲みながら話す程度のことだったかもしれないと少し恥ずかしく思いつつも、だからこそ、それぞれ思っていることが反応として返ってきたのかもねと思うのであった。そりゃあ、poem タグもつくわけです。 実名匿名のような話題はまあ繰り返し話題になってはきたけど、facebook の話に関してひとつこれまでと話が違うのは、実名性と言われてきたもの、それが現実のものになったということじゃないかなと思います。 実名がいいんだ、いやそれじゃだめだという話があったときに、とはいえある時点まではその「実名インターネット」なるものが具体的に存在していなかったから、その対するも
HBFav というはてなブックマーク iPhone アプリを作りました - naoyaのはてなダイアリー
ちょこちょこと余暇の時間を使って、HBFav という iPhone アプリを作りました。 HBFav は、はてなブックマークの「お気に入り」機能を閲覧するためのアプリです。はてなブックマークの「お気に入り」は、気に入ったユーザーがブックマークしたブックマークを一覧する機能、つまり、Twitter で言うところのタイムラインです。それを見る専用のアプリがほしかった、ということで作ったものです。 ･･･ということで、繰り返すと、HBFav はタイムライン形式でソーシャル・ブックマークを楽しむためのアプリ。はてなブックマークのお気に入り機能を活用しているぜ! という方におすすめです。 HBFav は、App Store からインストールできます。 App Store - HBFav : http://itunes.apple.com/app/id477950722 Kindle とともに HBF
Mojolicious::Lite で WebSocket を使ったチャットを作る - naoyaのはてなダイアリー
node.jsの衝撃とWebSocketが拓く未来 (1/2)：WebSocketで目指せ！ リアルタイムWeb（1） - ＠IT という記事を読みました。node.js という V8 を用いたサーバーサイド JavaScript フレームワークを使うと簡単にイベント駆動のサーバが書ける、node-websocket-server.js を使うと node.js で WebSocket サーバが実装できる。Ajax による polling や Long Polling などと WebSocket のアーキテクチャ比較といった内容でした。 WebSocket を使うと手軽にサーバプッシュ的なアプリケーションが作れて嬉しいのですが、現時点では、HTTPサーバー側で WebSocket を処理する下地の実装をどう用意するかというところがひとつ課題でしょう。node.js はその回答のひとつとして
エンジニアの不安と壁 - naoyaのはてなダイアリー
このところ、KLab×はてな エンジニア応援ブログコンテストというのを開催していまして、エンジニア人生に関するちょっとした小話をブログに書いていただくと、内容によっては、シリコンバレーに行けたり、iPad が貰えるかもしれない。という企画です。「え、ブログ書くだけでシリコンバレー? 」 なかなか太っ腹な企画です。 よい機会なので、宣伝がてら、自分もちょっと、昔話をしてみたいと思います。 振り返ってみると、自分がエンジニアとして経験を積むなかで、「ここが壁だったな」と思うところがぼちぼちありました。それが何で壁に感じたのかといま改めて考えると、いずれも体系的な知識がなかったために、それを乗り越えるための指針がなかったというのが大きかったように思います。 きれいなコードを書くにはどうしたらいいんだろう? 負荷分散って、どうやるんだろう? 溜め込んだデータをうまく活用するには、どうしたらいいんだ
non-Negative Matrix Factorization (NMF) - naoyaのはてなダイアリー
以前に Latent Semantic Indexing (LSI) や HITS 絡みで SVD や主成分分析について少し書きました。 http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing http://d.hatena.ne.jp/naoya/20090301/hits LSI では SVD を使って単語文書行列を分解し、低階数近似を行います。これにより、似たような次元をまとめたりといった効果が得られるのでした。自分の考察では HITS も同様のことを行っているという認識でした。 さて、集合知プログラミングを読んでいたら、第10章で "non-Negative Matrix Factorization" (非負値行列因子分解, 以下NMF) という手法が出てきました。NMF も SVD や主成分分析に同じく行列を分解
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
第1回ウェブ学会シンポジウム - naoyaのはてなダイアリー
