Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
Pixate - naoyaのはてなダイアリー
数日前に Pixate という iOS 向けミドルウェアがリリースされました。なんとiOSアプリの見た目を css で書けるという、全ウェブ開発者感涙のライブラリ。こりゃすげえ。ただし無料というわけにはいかず、18,000円くらいでこざいます。 2月9日 追記 トライアル版と、個人利用のための無料版が出たようです。 RubyMotion の teacupのように css チックな DSL で書ける、というものはありましたが Pixate はその辺とは次元が違ってて、普通に css ファイルに css を書くことができる。 button.blue { position: 60, 100; size: 200, 40; border-radius: 7px; font-family: 'Courier New'; font-size: 18pt; font-weight: bold; bord
iOS版Chrome リリースに見るiOSプラットフォームの制約 - naoyaのはてなダイアリー
iOS版の Chrome がリリースされましたね。 アプリとしての使い勝手どうこうというところよりも、JavaScript エンジン周りをどうしているのかに興味があったのだけど、TechCrunch の記事 (http://techcrunch.com/2012/06/28/hands-on-with-googles-chrome-for-ios-just-like-chrome-for-android-only-slower/) を見る限り v8エンジンは搭載されていないし、当然 UIWebView での JIT コンパイラも有効にはなっていないように見えました。つまり、JavaScript の実効速度に関して言えば、Mobile Safari のそれを上回ることはない。(厳密に言えば、純粋な JavaScrpit の実効速度以外のところの実装が良くてトータルとして速い、というようなこと
HBFav というはてなブックマーク iPhone アプリを作りました - naoyaのはてなダイアリー
ちょこちょこと余暇の時間を使って、HBFav という iPhone アプリを作りました。 HBFav は、はてなブックマークの「お気に入り」機能を閲覧するためのアプリです。はてなブックマークの「お気に入り」は、気に入ったユーザーがブックマークしたブックマークを一覧する機能、つまり、Twitter で言うところのタイムラインです。それを見る専用のアプリがほしかった、ということで作ったものです。 ･･･ということで、繰り返すと、HBFav はタイムライン形式でソーシャル・ブックマークを楽しむためのアプリ。はてなブックマークのお気に入り機能を活用しているぜ! という方におすすめです。 HBFav は、App Store からインストールできます。 App Store - HBFav : http://itunes.apple.com/app/id477950722 Kindle とともに HBF
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
エンジニアの不安と壁 - naoyaのはてなダイアリー
このところ、KLab×はてな エンジニア応援ブログコンテストというのを開催していまして、エンジニア人生に関するちょっとした小話をブログに書いていただくと、内容によっては、シリコンバレーに行けたり、iPad が貰えるかもしれない。という企画です。「え、ブログ書くだけでシリコンバレー? 」 なかなか太っ腹な企画です。 よい機会なので、宣伝がてら、自分もちょっと、昔話をしてみたいと思います。 振り返ってみると、自分がエンジニアとして経験を積むなかで、「ここが壁だったな」と思うところがぼちぼちありました。それが何で壁に感じたのかといま改めて考えると、いずれも体系的な知識がなかったために、それを乗り越えるための指針がなかったというのが大きかったように思います。 きれいなコードを書くにはどうしたらいいんだろう? 負荷分散って、どうやるんだろう? 溜め込んだデータをうまく活用するには、どうしたらいいんだ
第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー
昨日は第11回 Kansai.pm でした。 今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。 PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資料) は圧巻でした。伊奈さんの本文抽出の話 (発表資料)、はこべさんのコルーチンの話 (発表資料)、いずれも難解になりがちなところを凄く分かりやすく解説されていて、さすがだなと思いました。各々ショートトークも、いずれも良かったです。 スペルミス修正プログラムを作ろう 自分も 20 分ほど時間をいただいて、スペルミス修正プログラムの作り方について発表しました。 スペルミス修正プログラムを作ろうView more presentations from Naoya Ito. スペルミス修正プログラムについてはずばり スペル
ソフトウェアアーキテクトが知るべき97のこと / 池袋ジュンク堂で鈴木雄介さん、小野和俊さんとイベント - naoyaのはてなダイアリー
"97 Things Every Software Architect Should Know" という洋書の邦訳が、"ソフトウェアアーキテクトが知るべき97のこと" (www.oreilly.co.jp, www.amazon.co.jp)というタイトルで 10月5日、オライリーから発売です。 ソフトウェアアーキテクトが知るべき97のこと 作者: 鈴木雄介,Richard Monson-Haefel,長尾高弘出版社/メーカー: オライリージャパン発売日: 2009/10/05メディア: 単行本（ソフトカバー）購入: 17人 クリック: 362回この商品を含むブログ (82件) を見る 第一線で活躍するソフトウェア・アーキテクト達が、独自の視点でアーキテクトという職業やソフトウェア開発にまつわる事柄についてのエッセイをそれぞれ執筆、それが 97 本あるというコラム集です。 邦訳版では、日本
Canonical Huffman Codes - naoyaのはてなダイアリー
1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。 ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率が分かっているときに、その各シンボルに最適な符号長の接頭語符号を求めるものです。 通常のハフマン符号はポインタで結ばれたハフマン木を構築して、ツリーを辿りながら各シンボルに対する接頭語符号を計算します。このハフマン木には曖昧な箇所が残されています。ハフマン木は木の辺を右に辿るか左に辿るかで符号のビットが決まりますが、右が 0 で左が 1 などというのはどちらでも良いという点です。(曖昧だから駄目、という話ではありません。) 従って、ハフマン木から生成される符号は一意には決まりません。 ここで各シンボル
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
Wavelet Tree - naoyaのはてなダイアリー
圧縮全文索引の実装などでしばしば利用される 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;
WEB+DB PRESS Vol.49 はてなブックマーク構築ノウハウ大公開 - naoyaのはてなダイアリー
WEB+DB PRESS Vol.49 にて「はてなブックマーク構築ノウハウ大公開」という特集記事を執筆しました。 WEB+DB PRESS Vol.49 作者: arton,桑田誠,角田直行,和田卓人,伊藤直也,西田圭介,岡野原大輔,縣俊貴,大塚知洋,nanto_vi,徳永拓之,山本陽平,田中洋一郎,下岡秀幸,ミック,武者晶紀,高林哲,小飼弾,はまちや2,WEB+DB PRESS編集部出版社/メーカー: 技術評論社発売日: 2009/02/23メディア: 大型本購入: 10人 クリック: 373回この商品を含むブログ (45件) を見る 現在サービス中の新しいバージョンのはてなブックマークの開発には9ヶ月の期間を要しました。システムは一から作り直しを行っています。なぜシステムの作り直しを行う必要があったのか、どのような方法/設計でシステム再構築を行ったのか、新システムで利用しているソフト
はてなブックマークFirefox拡張, JavaScript で IS 法 による Suffix Array 構築 - naoyaのはてなダイアリー
昨日、はてなブックマークFirefox拡張をリリースしました。おかげさまでベータ版からダウンロード数は累積で1万ダウンロードを突破し、アクティブユーザー数も伸びています。 はてなブックマークFirefox拡張で新しいインターネットを体験しよう http://b.hatena.ne.jp/guide/firefox_addon 開発者の id:secondlife が g:subtech:id:secondlife:20090415:1239804170 で技術的な側面からのちょっとした TIPS なども紹介していますので、興味のある方はご一読ください。 検索では思いのほか SQLite の like 検索が高速なのに驚いた。はてブ検索では、検索ワードから URL, Title, コメント にマッチしたものを表示していて、それ専用の search_data だかかんらかの検索用カラムがある。
KOF 2008 の発表資料 - naoyaのはてなダイアリー
KOF 2008 での発表資料「はてな流大規模データ処理」を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/081108huge_data.ppt 一部参考文献からの引用 (Introduction to Information Retrieval から Vector space model の図、たつをの ChangeLog から転置インデックスの図) があります。この場を借りて感謝。 環境によってはおそらくフォントの表示がいまいちだと思いますが、ご了承ください。 追記 SlideShare にアップロードしました。 081108huge_data.pptView SlideShare presentation or Upload your own. (tags: linux mysql) 追記: メモリはディスクの 150 倍について
CodeZine にて KOF 2008 の記事と補足 - naoyaのはてなダイアリー
大阪南港ATCで開催された「関西オープンソース2008」の2日目（11月8日）午前中のセッションで、株式会社はてなCTOの伊藤直也氏が「はてな流大規模データ処理」と題した発表を行った。 CodeZine で先日の KOF 2008 (あらかじめ言っておきますが King of Fighters ではないですよ、関西オープンフォーラムです) の発表を記事にしていただきました。ありがとうございます。 発表資料は以下のエントリーにありますので一緒にご覧いただければと思います。 http://d.hatena.ne.jp/naoya/20081111/1226395400 さて、記事内容について少し補足をしておきたいと思います。 メモリとディスクの速度比較について 「メモリはディスクの 150 倍」という話ですが、その後知人と話して検索のインデックスをシークする場合などは ms 対 ns くらい違
第2回 アルゴリズムイントロダクション輪講 - naoyaのはてなダイアリー
今日は id:motemen 主催のアルゴリズムイントロダクション輪読会 第2回でした。 現在弊社では今年のインターンシップを 2回目(年に2回のうちの後半) 開催中ですが、先月まで来てくれていたインターン一期生も数名輪読会に参加し、東京オフィスからも数名参加、お客さんも増えて大変盛り上がりました。 輪講第2回の今日の発表は自分が担当で、内容は「第4章 漸化式」でした。アルゴリズム計算時間の漸近的限界を得るため、再帰アルゴリズムの計算時間の漸化式を解きます。4章では漸化式の解法として置き換え法、再帰木、分類法が紹介されています。 アルゴリズムイントロダクションの第一巻は、前半しばらく計算量の話が続きます。6章からようやくソートアルゴリズムの話に入ります。次回5章は「確率論的解析と乱択アルゴリズム」です。 数学的基礎とデータ構造 (アルゴリズムイントロダクション) 作者: T.コルメン,R.
アルゴリズムイントロダクション輪講@京都 - naoyaのはてなダイアリー
社内エンジニアの間に、計算機科学をマジメにやろうという機運が高まっています。それを受けはてな社内で計算機科学に関する教科書の輪講をやろうという話になりました。という訳でまずはアルゴリズムの教科書「アルゴリズムイントロダクション 第1巻 改訂2版 (1)」を輪講してみることにします。はてなスタッフだけでなく社外からの参加も募集しているので、京都オフィスに近い方はぜひご参加下さい。 id:motemen がコンピュータサイエンス関連書籍の輪講を開催するとのこと。もちろん自分も参加します。教科書は何が良いか色々考えたようですが、まずはアルゴリズムイントロダクションに決まったようです。アルゴリズムイントロダクション、ちょうど今日届いたのでざっと見てみた所、数学的な観点からアルゴリズム/データ構造についての基礎を論じている良い書籍だと思いました。 アルゴリズムとデータ構造は最も重要な基礎ですが、これ
はてなブックマークの関連エントリー機能開発、PFI さんとの合宿 - naoyaのはてなダイアリー
はてなブックマークに関連エントリーを配信する機能を追加しました。詳しくは 告知日記で。 この関連エントリーは、株式会社プリファードインフラストラクチャー (以下 PFI) の技術者のみなさんと一緒に開発しました。週末に2泊3日で京都で合宿をしてコア部分を作り、その後京都と東京に分かれてオンラインで連絡を取りながら2週間ほど作り込みをして、今日リリースです。 この合宿では何チームかに分かれて、今回の関連エントリーの機能以外の開発も行っています。その辺の成果はまた後日にリリースできるのではないかと思います。 はてなブックマークの一つの問題として、昔のエントリーがデータベースに埋もれてしまうという点がありました。その問題の解決策としての類似記事抽出、それから検索機能の強化を以前から考えていました。PFI のメンバーのみなさんは情報検索技術のスペシャリストです。アカデミックな研究の成果を製品化を通
MySQL Enterprise の今後についてのニュース - naoyaのはてなダイアリー
カリフォルニアで MySQL カンファレンスが開催されて、その中で Sun に買収された以降の MySQL の今後の方針についてアナウンスがあったようですが、以下のようなニュースとして報じられています。 MySQLは16日、米カリフォルニア州サンタクララで開催中のMySQLコンファレンスの席上で今後の新機能追加は有償版の「MySQL Enterprise」だけを対象としていく方針を明らかにした。 対してブックマークコメントに b:id:heppoko-san さんが元 MySQL AB CEO の Marten Mickos 氏が Slashdot に寄せたコメントの URL (http://developers.slashdot.org/comments.pl?sid=525246&cid=23098626) を貼っておられたので、そちらも見てみました。 中の人のコメントを見るに、そこま
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
