サクサク読めて、アプリ限定の機能も多数！
トップへ戻る
ドラクエ3
llamerada.hatenadiary.org
Googleで利用されている分散データ処理言語SawzallのOSS実装 szl が公開されました。 公開されたソースの中にはSawzallの実行環境の他に大規模データ向けの統計ライブラリが含まれています。この統計ライブラリには高度なアルゴリズムが実装されているので、これを他の言語からも利用できると便利だなと思い、C++, Ruby, Pythonから利用できるようにしました。 便利な統計アルゴリズムの1つに出現回数が上位のN件の要素の抽出(top-N)があります。 top-Nを求める具体例としては、自然言語処理でよく使う、出現回数上位の単語を求める処理があります。この処理の単純な実装では、まず全単語の出現回数を求めておき、次に各単語を出現回数の降順でソートして出現回数上位の単語を求めます。しかし、この実装ではユニークな単語数K（数十万から数百万）に比例したメモリと計算量が必要となります。
GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドの翻訳の最終回です。Googleの検索システムの10年間の進化の軌跡が紹介されており、今回は将来の課題についての紹介となります。イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。 第1回：Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（１） - llameradaの日記 第2回：Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（２） - llameradaの日記 第3回：Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（３） -
flickrの写真をクリック履歴から自動的に推薦するサービス「フォト見る」を数日前にリリースしました。さいわい、気に入って頂いた方もいるようです（Route 477(2009-03-12)）。「フォト見る」をリリースしてみて思ったのですが、レコメンド（推薦）を軸としたサービスでは初心者ユーザにいかに使ってもらえるかが一番大切だなと思いました。 ユーザに何かを推薦するには、当たり前ですが、そのユーザの好みを知っている必要があります。例えば、「フォト見る」では、ユーザが過去にクリックした写真から好みを推定しています。ところが、初めてページを訪れたユーザの好みは全く分かりません。1つでも写真をクリックしてくれれば、ユーザの好みが少しでも分かります。ところが、ユーザの好みが分からない状態では推薦は無理なので、初めてのユーザに対してはどうでもよい写真が表示されやすく、写真をクリックしてもらうのがなか
GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドの翻訳の第3回です。Googleの検索システムの10年間の進化の軌跡が紹介されており、今回は2004年から2007年ぐらいまでの検索システムの紹介とインデックスの符号化方式、検索精度を向上させるための実験環境についての紹介となります。個人的には分岐処理を徹底的に排除したGoogleの最新の符号化方式が興味深かったです。イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。 第1回：Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（１） - llameradaの日記 第2回：Google WSDM
GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドの翻訳の第2回です。Googleの検索システムの10年間の進化の軌跡が紹介されており、今回は2000年から2001年ぐらいまでの検索システムの一部の紹介となっています。個人的には転置インデックスの詳細な符号化方式が公開されているのが印象に残りました。Googleにとっては過去のインデックス構造でしょうが、商用の全文検索エンジンの詳細な仕様が公開されるのは珍しい気がします。なお、イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。 第1回：Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（１）
GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドを翻訳してみました。Googleの検索システムの10年間の進化の軌跡が紹介されており、興味深い話が満載です。個人的にはディスクの外周部と内周部を使い分けている話がツボでした。なお、イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。 スライドの入手元：Jeffrey Dean – Google AI 検索システムに取り組む理由 チャレンジングなサイエンスとエンジリアニングのブレンド 多くの魅力的な未解決な問題が存在する。 CS（コンピュータサイエンス）の多数の領域にまたがる。 アーキテクチャ、分散システム、アルゴリズム、圧
検索キーワードの入力がいらない、「フォト見る」というflickrの写真を検索するサービスを作りました。気に入った写真をクリックしていくと、クリックされた写真と同じタグの写真が次々と表示されます。例えば、「海」の写真をクリックすると「夕日」や「ビーチ」の写真が表示されるようになります。なにも考えずにクリックしていくだけで、自然と自分の好みにあった写真が出てくる、らくちんな検索サービスを目指しています。 flickrのタグは英語ばかりなので、ちょうどよい検索キーワードを見つけるのは日本人には難しいのですが、「フォト見る」では写真をクリックするだけなので単語の意味が分からなくても大丈夫です。スペイン語やイタリア語・アラビア語のタグがついた写真もかんたんに検索できます。 仕組みは単純なサービスですが、検索キーワードによる検索では、なかなか出会うことのできない写真が見つかるのが楽しいです。 技術的に
とても楽しかった。ミドルウェア系の勉強会が一番自分の関心に近いみたい。印象に残ったことを何点か。 Masterがあるタイプの分散ソフトウェアで、障害時のMaster選択に苦労した話を聞いて、Chubbyが便利な理由が改めてよくわかった。 Key Value Store だとランダム・リードが主なユースケースなので分散ハッシュのアプローチが有効みたいで、分散システム系はだいたいそうだった。全文検索みたいなユースケースだとシーケンシャル・リードが大事なので、BigTableのようなB-Treeのアプローチの方が有効だが、そのあたりはあまり開拓されていないみたい。 TokyoCabinetを最下層のストレージに使っているケースが多かった。
Mixiがマイミクにたいして住所が分からなくても年賀状を郵送できるミクシィ年賀状を開始した。 このサービスは前のエントリ「Googleストリートビューと郵便システムの問題点」で妄想した郵便システムとほぼ同じであり、「住所」を「ネット上のID」に置き換え可能なサービスである。普通は「妄想」レベルで終わる発想を、実サービスとして、しかも、日本郵便を巻き込んで実現させるミクシィはすごいと思った。 前のエントリでも書いたが、Googleストリートビューは「住所」を重要な個人情報に変えてしまうサービスである。 今後、Googleストリートビュー的なサービスは増えていくだろうから、「住所」を第三者に公開するのが嫌われる流れは変わらないだろう。したがって、「住所」を公開しないでも郵便を受け取れるミクシィ年賀状が一般の郵便システムとして拡大していく可能性は十分に高いと思う。
Googleストリートビューによって明らかになったことの１つに、「住所」を他人に気軽に公開してはならないということがある。「住所」とGoogleストリートビューを組み合わせれば、「家族構成」や「年収」・「車の車種」などの重要な個人情報が推定できる。つまり、「家族構成」「年収」と同程度の慎重さをもって、「住所」という個人情報は扱わなければならない。 ところが、多くの人は「住所」を様々な相手に公開している。それはなぜだろうか？１つの理由は、「住所」から「家族構成」などを推定するには、現地に出向く必要があり多大なコストがかかるので、あまり問題となる例が少なかった点である。だが、Googleストリートビューにより、このコストは非常に小さくなった。もう１つの理由は、「住所」を公開しないと生活を送る上で非常に不便なためである。 人が「住所」を公開する目的の多くは料金表や年賀状などの郵送物を受け取るため
はじめに TagGridでは16000毎のFlickrの写真を、写真のタグにしたがって格子状に配置しています。この配置アルゴリズムについて簡単に説明したいと思います。 基本的なアイデア まず、入力となるのはN個のタグ付きデータとします。また、K種類のタグがあるとします。 TagGridでは、このN個のデータとK種類のタグがそれぞれ平面上に配置されるとします。 データだけでなく、タグも2次元平面上に配置するのが大事な点です。 基本的な考え方としては、あるデータのタグが例えばseaとsunの場合、このデータの位置がseaタグと sunタグの近くになるようにデータとタグを配置します。データは複数のタグを持つので、一番良い配置方法というのは簡単には決定できません。そこで、なるだけ良さそうな配置を求めてみます。 フォーマルな問題定義 基本的なアイデアを、もう少しフォーマルに定義します。 n番目のデー
はじめに 先日公開したTagGridは比較的好評だったようでAsiajinにもとりあげて頂きました。 Flickr mashup on Google App Engine from Japan – Asiajin TagGridでは、画面全体を埋めつくすように75x75のサムネイル画像を表示しています。1024x768と比較的小さいウィンドウサイズの場合でも、表示される写真の数は70枚くらいになります。 TagGridでは、これらのサムネイル画像を一度に全部表示するのではなく、マウスを移動させるごとに、マウスでなぞった箇所の写真を表示するようにしています。このUIは個人的にもかなり気に入っているのですが、はてなブックマークでのコメントでも「気持ちいい」との評価を頂けているようです。そこで、このUIをなぜ「気持ちいい」と感じるのか理由を考えてみました。 はてなブックマーク - 16000枚の
はじめに Flickrには綺麗な写真がたくさんありますが、写真を探すには検索キーワードの入力や、それりのクリック操作が必要で、ものぐさな私には少々面倒でした。また、Flickrは日本から遠いので、画面切替に時間がかかります。そこで、画面切替とクリック操作のあまりいらない、気楽に写真を探すためのインターフェイスを作ってみました。 http://taggrid.appspot.com/flickr/popular.html スクリーンショットの一部です。 アイデア 基本的なアイデアは次の3点です。 16000枚の写真を格子上に配置 Google Maps風のAjaxインターフェイス 似ている写真を近くに配置 1. の16000枚の写真はPopular Tags on Flickr | Flickrを起点にしてFlickr APIを使って取得しました。 2. のAjaxインターフェイスは自分でゴ
東京都で賢い借金返済方法を教えます！では、MySQLに格納したWikipedia記事をランダムに表示している。速度を気にしないなら、 SELECT * FROM docs ORDER BY RAND() LIMIT 10; で良いのだけど、レコード数が多いと遅くて使いものにならない。そこで、記事IDを1から始まる連番になるようにDBに格納している。このようにすると、アプリケーション側でDBに格納されている文書IDが全て分かるので、ランダムに文書IDを10個選択して、その文書IDのレコードを表示することで、ランダム表示を実現している。 例えば、IDは10個選択するRubyコードは、 ids = Array.new(10){ rand(num_docs) + 1 } で、DBに発行するSQLはこんな感じになる。 SELECT * FROM docs where ID in (id1,id2,.
http://xpath.kayac.com/を使って、Amazonでの売り上げランキングの変化をグラフにしてみました。グラフにすることで、売り上げランキングの変化を簡単に見ることができます。 まず、XPathGraphにユーザ登録します。ユーザ登録した後、「新しくグラフを作成する」のボタンをクリックします。すると、グラフ作成画面になるので、次のパラメータを入力します。 タイトル、説明：適当なタイトル、説明をいれます。 URL：詳細ページのURLです。次のURLの_asin_のところに、ASINを入れたURLにしてもらえると、私がちょっとうれしいです。 http://www.amazon.co.jp/exec/obidos/ASIN/_asin_/diaryofllamer-22/XPath：次のXPathを入力します。 //li[@id="SalesRank"]/text()タグ：適当な
Google App Engine]のチュートリアルを試したみた。 pythonは殆んど知らないが、Railsに似たフレームワーク構成になっているので、だいたいなんとかなった。 Google App. Engineの特長をまとめるとこんな感じだろうか。第一印象なので、間違っているところはあると思うが、大筋ははずしていないと思う。 インストールが楽 一瞬で開発環境が整う。インストール後、コンソールでコマンドを叩けば、すぐに開発にかかれる。必要なのはエディタとWebブラウザとアイデアだけ。 デブロイが楽 ローカル環境とサーバ環境の差を意識する必要がない。コマンド一発で、ローカルの開発環境がサーバ環境にアップされる。アプリケーションにバージョン番号があって、古いバージョンに戻せるなど、周辺ツールも整っているみたい。 サービス公開が楽 信頼性（リライアビリティ）や拡張性（スケーラビリティ）を（基本
twitterでのid:fromdusktildawnとid:malaのやり取り*1をみて考えてみたが、「はてなダイアリー」は、「はてな」の収益に凄い貢献していると思う。多分、ブログサービスの中では例外的に儲かっている気がする。特に、無料ユーザをお金に結びつける点ではピカイチかも。 もちろん、「はてなダイアリー」では（他のブログサービスと違って）無料ユーザのダイアリーでも広告は表示されない。なので、一見、無料ユーザは収益に全然貢献しないように思える。 ヒントは有料オプションにある。有料ユーザはキーワード自動リンクをオフにすることができる。つまり、逆にいえば、無料ユーザにはダイアリー内のキーワードを「はてなキーワード」にリンクしてもらう必要があるのだ。 無料ユーザが記事をアップする毎に「はてなキーワード」へのリンクが増える。検索エンジン対策で最も有効なのは、優良な被リンクを増やすことである。
Javascriptだけで書かれたコンパクトな分かち書きソフトウェアであるTinySegmenterをRubyに移植しました。移植してから別実装があるのに気がつきましたが、気にせず公開することにします。 Codereposにアップしてありますので、下記のURLよりダウンロードできます。 http://svn.coderepos.org/share/lang/ruby/ruby_tiny_segmenter/ MeCabに対するTinySegmenterの利点は、Ruby だけで書かれているので、どんな環境でも簡単に動作する点です。インストールも簡単です。Windows環境でMeCabをRubyから扱うのは少し面倒ですが、TinySegmenterならば殆んど問題ありません。 実行例はこんな感じです。 require "tiny_segmenter" words = TinySegmente
GoogleのBigTableの特長の1つはエンジンとストレージが疎結合であることである。 MySQLやPostgreSQLではSQLクエリを受け付けるマシン(エンジン)と、実際にデータを格納するマシン(ストレージ)は同じである。つまり、エンジンとストレージが密結合である。 エンジンとストレージが密結合である利点は、ストレージへのアクセスが、ネットワーク越しの場合に比べて高速なことである。 しかし、この利点は薄れつつある。ディスクへのアクセスはメモリへのアクセスに比べれば遥かに低速である。そのため、ストレージをメモリにキャッシュして運用することが多い。そして、常にストレージをメモリにキャッシュするならば、ストレージがローカルディスクにあるが、ネットワーク越しの別マシンにあろうが大差ない。必要に応じてメモリに読み込むだけである。 GoogleのBigTableではストレージはGFS上に格納さ
for 文を setTimeout に変換する - IT戦記が楽しそうだったので、久しぶりにJavaScriptを書いてみた。 継続風に書くと、通常のforループとsetTimeout付きforループが同じようになります。 JavaScriptも楽しいなぁ。また、書きたい。 // 通常版 forloop(0, 3, 1)(function(i, cont){ forloop(0, 7 ,1)(function(j, cont){ console.log('a' + i + "-" + j); cont(); }, cont); }, function(){}); // timeout版 to_forloop(0, 3, 1)(function(i, cont){ to_forloop(0, 7 ,1)(function(j, cont){ console.log('a' + i + "-"
ニコニコ動画は動画検索におけるGoogleになり得ると思う。GoogleがWebページ検索において革命的であったのは、重要なのはページそのもの内容ではなく、Webページに対するアノテーション、つまり、リンクであることに気が付いた点である。そして、ニコニコ動画のコメントは、Webページのリンクと同じ性質を持っている。 ニコニコ動画のコメントとWebページのリンクで類似している点は次の3点である。 アノテーションの内容は不定形のテキスト（リンクの場合はアンカーテキスト）である。その為、キーワード検索で利用出来る。 人気のあるコンテンツに対してはアノテーションの数が多い。その為、アノテーション数を人気度の指標に出来る。 アノテーションを作成する動機は自分の楽しみ・利益の為である。その為、アノテーションの数はほっておいても自然に増大する。 これらの3つの特徴をリンクが持つため、Web検索ではページ
JavaScriptによる全文検索エンジンの最初のバージョンはAjaxではなく、Sjaxであった。その為、サーバへのリクエストが発生する毎にブラウザが固まってしまい、応答性が悪かった。なぜ、Sjaxで記述したかというと、連続してサーバへリクエストを送り、しかも、サーバからのレスポンスに応じてリクエストを変更するようなAjaxプログラミングが面倒だった為である。このようなSjaxのコード例を次に示す（prototype.jsを使用）。 // (Sjax)サーバからpathのデータをoffsetの位置からlengthバイト取得 function fetch(path, length, offset){ var range = ["bytes=" + offset + "-" + (offset + length - 1)].join(""); var options = { method: "
UTF-8文字列の圧縮ライブラリを作っている。いまさら圧縮ライブラリをなぜ作るのかというと、JavaScriptによる全文検索エンジンで、インデックスの圧縮を行いたいからである。検索結果に概要文を出すには、インデックスが元テキスト全てを含む必要がある。従って、インデックスサイズの肥大化を避けるには、圧縮が必要不可欠である。ところが、次の条件を満たすライブラリを見つけられなかった。 圧縮後のデータがUTF-8文字列 JavaScriptで復元可能 前者の条件が必要なのは、JavaScriptでバイナリが扱えない為、圧縮後のデータがUTF-8文字列である必要がある為である。後者の条件は当たり前であるが、意外に該当するライブラリは少なかった。JavaScriptによるzipの解凍ライブラリは公開されているが、ライセンスが不明であった。 しょうがないので、LZSS符号をベースに、自分でライブラリを
JavaScriptでインデックス型の全文検索エンジンを作ってみた。全文検索エンジンを作る際に問題となるのは、インデックスデータを部分的に読み込む方法である。通常はmmapやpreadなどを使ってファイルの一部を部分的に読み込むのだが、もちろん、ブラウザには使えない。ブラウザでファイルの一部分を読み込むには2通りの方法がある。1つは、ファイルを多数のファイルに分割する方法であり、もう1つはHTTPリクエストのRangeヘッダを利用して、ファイルの一部を取得する方法である。前者の利点は、ブラウザのキャッシュが効くことや、対応ブラウザが多いことである。後者の利点は、ファイル数が少なくなるので、インデックスの管理が容易になることである。今回はRangeヘッダの実用性にも興味があったので、後者の方法を用いた。 参考ページ：最速インターフェース研究会 :: Ajaxを使ったシンプルなチャット 転置イ
単語をクラスタリングするサービスを作りました。 http://llamerada.sakura.ne.jp/clustord/cluster.cgi 入力された単語を似た意味のグループの分割します。例えば、「トマト」「りんご」「みかん」「なす」を入力した場合、「トマト なす」と「りんご みかん」に分類します。 検索キーワードなどは多種多様で、そのまま眺めても全体を把握しづらいことがありますが、単語をクラスタリングすることで概要がつかみやすくなります。また、私のdel.icio.usのタグを分類してみたところ次のようになりました。なんとなく合っているようです。 http://llamerada.sakura.ne.jp/clustord/cluster.cgi?id=5 精度はそれなりですが、使いどころはあるのかなと思います。向上の余地はまだまだあるので、少しずつ手を入れていきたいと思います
BlogRanger APIを使ってページの関連ブログを表示させてみた。 BlogRanger APIではブログ検索結果をJSONP風のAPIで取得できる。そこで、関連ブログを表示させたいページのキーワードを抽出して、そのキーワードでのブログ検索結果を、事前に用意したテンプレートに埋め込んだ。 キーワード抽出には、tf-idf法や、Web APIを利用する方法があるが、今回はMeCabで形態素解析した結果から、ランダムに1つの名詞を選択することにした。 下記のサービスで動いています。 DOMAIN ERROR コードはこんな感じです。 JavaScriptコード var BlogSearch = Class.create(); BlogSearch.prototype = { initialize: function(keyword){ this.keyword = keyword; th
JavaScriptによりサーバと非同期通信する際の手段にはXMLHTTPRequest(XHR)とIFRAMEがある。Ajaxと言えば普通はXHRだが、IFRAMEを使うことによってもサーバとの非同期通信が可能である。IFRAMEの場合、サーバと通信するタイミングでIFRAMEのsrcを変更し、IFRAMEを再読み込みする。そして、IFRAMEの読み込みが終了したら、親ページのコールバック関数に、IFRAMEのデータを渡すことで非同期通信が実現できる。たしか、初期のGoogle MapsはXHRでなくIFRAMEをAjaxに使っていたと思う。 XHRとIFRAMEのユーザビリティにおける最大の違いは、サーバとの通信処理のユーザへの見え方である。XHRの場合、ブラウザはサーバとの通信を画像の読み込みと同じように扱う。一方、IFRAMEの場合、ブラウザはサーバとの通信はリンクのクリックと同じ
HTML要素を抜き出す正規表現を自動生成するプログラム html2regexp を作ったので公開します。 札幌市で賢い借金返済方法を教えます！ 使い方は簡単で、HTMLファイル中の抜き出したいHTML要素の先頭タグの末尾にh2rと書き加えるだけです。例えば次のように指定します。 <ul> <li><a href="hoge" class="h" h2r>hoge</a></li> <li><a href="huga" class="h" h2r>huga</a></li> </ul> <div> <a href="f">f</a> </div>すると、html2regexpは、2つのa要素を抜き出す次の正規表現を生成します。 (<(\w*?)\s*([^>]*?" class="h"[^>]*?)>(.*?)<\/\2>)HTMLを抜き出して利用したり、Webアプリケーションのテストなどの
BLOGRANGER APIのリンク抽出機能を使って、あるブログサービスでのブログから、別のブログサービスへのブログのリンク関係を求めてみた。 求めてみた結果はこちら。 ブログサービス間のリンク関係 同じブログサービス内でリンクされる傾向が強かったり、「はてな」から「livedoorブログ」へのリンクは「2chブログ」が多いことが分かる。 BLOGRANGER APIはprototype.jsベースなので、prototype.jsに慣れていれば使うのは簡単だと思う。上の例だと下記のようなコードになる。 // d.hatena.ne.jp 内からの blog.livedoor.jp へのリンクを求める場合 // オブジェクトの作成 this.ls = new Ranger.LinkMining(); // コールバック関数の登録 this.ls.successHandler(this.onS
次のページ
このページを最初にブックマークしてみませんか？
『llameradaの日記』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
