mixi Engineers’ Blog » Inside Tokyo Cabinet その弐
予定を立てた途端にやりたくなくなる症候群に堪えて連載を続けるmikioです（こんな私でもエアーマンくらいは倒せます）。前回はDBMの基本について説明しましたが、それを忠実に実装しても実際には使いものにはならないことにも触れました。今回は、実用的なDBMに進化すべく、Tokyo Cabinet（およびその前身のQDBM）で考えた工夫についてお話します。 ハッシュ関数についてもう少し 前回の記事に関して、「ハッシュ関数はビットシフト使って実装した方が早いよ」という旨のお便りをいただきました（ありがとうございます）。まさにその通りで、乗算命令（ここではimull）より左シフト命令（ここではsall）の方が速いみたいです（Intelの資料によると、mulが15から18で、salが4とのこと）。しかし、DBMの場合はファイルI/Oにかかる時間が支配的になるというのが重要な点です。したがって、ハッシュ
生年月日から年齢を計算する簡単な計算式：ITpro
私の個人ブログに掲載したら好評でしたので、こちらでもご紹介してみます。 最近知ったんですが、生年月日から年齢を計算する簡単な計算式というのがあるそうです。 (今日の日付-誕生日)/10000の小数点以下切捨て。 PHPで書くと echo (int)((20070823 - 19850101)/10000); Perlで書くと print int ((20070823 - 19850101)/10000); JAVAで書くと System.out.println( (int)((20070823 - 19850101)/10000) ); という感じになります。 日本の法律を確認してみました。誕生日の前日が終了する瞬間（すなわち誕生日をむかえる午前0時00分の直前）に1歳を加えることになる。ただしうるう年など、年によって期間を定めた場合において最後の月に応当する日がないときは、その月の末日を
Web2.0時代の画像補完技術 － ＠IT
2007/08/29 1万枚の写真を使ってできないことで、200万枚の写真ならできることがある。それは熟練したPhotoshopの使い手が1時間かかってやる写真加工の作業を、コンピュータ処理で自動化してしまうこと――。8月初頭に米国サンディエゴで開催された画像処理技術の祭典、SIGGRAPH 2007で発表されたシーン補完技術は、何百万枚もの写真をネットで集められるWeb2.0時代の画像処理技術だ。 写っている邪魔な対象物を自然に置換 「数百万枚の写真を使ったシーン補完」と題した論文と、その成果を発表したのは、カーネギーメロン大学のジェームズ・ヘイズ（James Hays）氏とアレクセイ・A・エフロス（Alexei A. Efros）氏。この補完技術のアイデアは、元となる写真に似た構図や配色の写真を、ネット上で集めた膨大な数の写真データベースから探し出し、元の写真の消したい部分、あるいは復
Inside Tokyo Cabinet その壱 - mixi engineer blog
約半年間の沈黙を破ってOSSの世界に戻ってきつつあるmikioです。先日、Tokyo Cabinet（以下「TC」と呼びます）というデータベースライブラリをリリースしました。今回から数回に分けて、TCの設計と苦労話について連載してみます。 DBMとは TCは、いわゆるDBMの系譜のデータベースライブラリで、単純なハッシュテーブルをファイル上で永続化するだけの機能を提供します。DBMはAT&Tの古代UNIXの時代から受け継がれる伝統芸能なのですが、私はそういう枯れた技術が大好きなのです。 プログラマの皆さんは、PerlやRubyではハッシュ（連想配列）と呼ばれ、JavaやC++ではmapと呼ばれるような、何らかのキーに関連づけてなんらかの値を記録するデータ構造って実によく使いますよね。例えばmixiでは、ユーザアカウントに関連する情報（名前とかニックネームとか）は、ユーザIDをキーにしたハッ
ニコニコ動画の運営はミスを犯した？ - LEMON IN THE BOOKSTORE
自作自演祭り。 ニコニコ動画の歌ってみたタグなどを中心に自分で「ｗｗｗｗうますぎｗｗ」みたいなことを書いている人が意外とたくさんいたよって話題で一時期騒然となった。 運営の過ち そもそもニコニコ動画は匿名制ではない、記名制だ。 メッセージのXMLは ｗｗｗうますぎｗ のような形になっていて、一部のユーザはオミトロンなどのプロキシソフトを使ってユーザＩＤをコメント中に表示するなどの工夫をして記名制として利用したり、NGIDなどの設定を行うなど していた。 ところがこの自作自演祭りの結果、 ｗｗｗうますぎｗ このようなハッシュ値に変わってしまった。 この対応によって、作者によるコメントであるかどうかがわからなくなった。 これ自体が悪いわけじゃない。 だけど、この出来事はちょっとしたわだかまりを残すかも。 NGIDに指定することを妨げるわけではないし、単純に動画製作者保護の観点からは十分なことを
リコメンドの裏側 : LINE Corporation ディレクターブログ
『livedoor グルメ』の根岸です。今日はlivedoor グルメにも実装されている「リコメンド（＝お勧め）」機能の話です。 マクドナルドの「ご一緒にポテトもいかがですか？」という店員の接客コメントは、誰もが知っている典型的な決まり文句ですよね。でも、誰にでもポテトをオススメするのは、芸がない。「俺はイモが嫌いなんだ！」っていう人だって絶対にいます。 インターネットでOne-to-Oneマーケティングの時代になると、ユーザーの動向を分析し、各ユーザーごとに興味を持ちそうな商品を予想して、お勧めするようになりました。たとえば、『Amazon』にログインして「マイストア」を選ぶと、それまでの購買履歴をもとにお勧め商品がリストアップされます。 僕のマイストアだと、 『笑う大天使（ミカエル）』 『ウォーターボーイズ』 『リンダリンダリンダ』 などのDVDが、リストアップされています。上記はいず
Benford's Law -- from Wolfram MathWorld
A phenomenological law also called the first digit law, first digit phenomenon, or leading digit phenomenon. Benford's law states that in listings, tables of statistics, etc., the digit 1 tends to occur with probability , much greater than the expected 11.1% (i.e., one digit out of 9). Benford's law can be observed, for instance, by examining tables of logarithms and noting that the first pages ar
エレベータとHDDヘッダの動きに共通するもの － ＠IT
個人的に気になったのは、2位の「辞書不要の形態素解析エンジン『マリモ』とは」だ。事前に人が作成した辞書を使うのではなく、動的にネット上から集めたテキストを解析して辞書を生成するという新しいアプローチの形態素解析エンジンだ。新語や未知語に強いという特徴があるという。 ヒューリスティクスと統計的アプローチ 自然言語を計算機で処理するには、統計的アプローチだけでは難しいというのが常識的な見方だろう。ある程度、機械的に処理をして、そこからは特定の語彙をキーに、たくさんの例外ルールを適用するといったことを行わないと、精度が上がらない。 経験的に付け加えられていくルールやアルゴリズムは、「ヒューリスティクス」と呼ばれ、自然言語処理には欠かせないアプローチだと認識している。 今回取材したマリモでは、1000語ほどの予備的な語彙があるだけで、基本的にすべて統計処理だけを行う。それで十分な性能や精度が出ると
全文検索エンジン FlexSearch - グニャラくんのグニャグニャ備忘録@はてな
全文検索エンジン FlexSearchというものがあるようだ。 違いを吸収した検索 | 傀儡師の館.Python - 楽天ブログ 特徴は以下のとおり。 「FlexSearch」は、文字間をラバーバンドで連結して 伸縮させるように類似文字列を検出する、 Rubber Band Matching(RBM -ラバーバンドマッチング) アルゴリズムを採用しています。 RBMアルゴリズムを採用することで、 表現の差違を吸収して検索対象を抽出できます。 例えば・・・ 部分文字列（文字の部分一致で検索） 「高齢化問題」 将来の「高齢化」社会において・・・ 文字の挿入（キーワードに文字を追加して検索） 「ゴミリサイクル」 ゴミのリサイクル問題が・・・ 文字の欠落（キーワードから文字を削除して検索） 「女子中高生」 女子高生に人気の・・・ 文字の置換（キーワードを置換えて検索） 「ドボルザーク」 ドヴォルザ
辞書不要の形態素解析エンジン「マリモ」とは − ＠IT
2007/08/15 検索サービスを提供するベンチャー企業のムーターは8月1日、辞書を必要としない形態素解析エンジン「マリモ」の提供を開始した。従来、形態素解析では品詞情報を含む日本語辞書を用意するのが常識だったが、マリモでは、そうした辞書を不要とした。新技術のアプローチと特性について、開発元のムーターに話を聞いた。 統計処理で単語部分を推定 形態素解析とは、与えられた文を、文法上意味のある最小の単位（形態素）に区切る処理。「今日は晴れています」なら、「今日（名詞）／は（助詞）／晴れ（動詞）／て（助詞）／い（助詞）／ます（助動詞）」と分ける。検索エンジンをはじめ、さまざまな自然言語処理の場面で必要となる基礎技術だ。 形態素解析を行うには、あらかじめ品詞情報が付加された数十万語からなる辞書を用意する必要がある。また、新語や造語、専門用語に対応するには、個別に人力で単語を登録する必要がある。
ポストSVM候補 - アルゴリズムマニア2.0
電子情報通信学会情報・システムソサイエティ誌第12巻第２号超平面のオンライン学習における近年の展開畑埜 晃平より超平面の学習と言えば、PerceptronやSVMが代表的ですが、Perceptronと並ぶ基本アルゴリズムにWinnowというのがあるそうです。で、PerceptronとWinnowの中間にp-norm Perceptronというのがあるそうです。このp-normPにはBregmanダイバージェンスという概念が登場するみたいです。このBregmanDはユークリッド距離やKLダイバージェンスの一般化らしいです。p-NormPの拡張にALMAがあるそうです。ALMAはp-normマージン最大超平面の近似解を計算できるそうです。SVMは２次計画を解く必用がありますが、これに対してALMAは計算量のアドバンテージがあるみたいです。以下、ALMAの文献。O. L. Mangasarian
Execute Around Method - Standing on the shoulder of giants
必ず対で実行しなければならない処理がある場合は、ブロックを受け取るメソッドを定義しましょう。 振る舞いの実現に関するパターンです。 ファイルをオープンしたら最後に必ずクローズしなければいけないといった、必ず対で実行しなければならない処理を実現したい場合、最も単純な実現方法は対の処理をそれぞれ独立したメソッドとして公開することです。 class File def open ... end def close ... end end f = File.new f.open ... f.close しかし、この実現方法だと、インタフェースとして以下のような問題が残ります。 対で実行する必要があることを利用者が知らなければならない どのようなケースでも処理が対で実行されることをそれぞれの利用者が保証しなければいけない このような問題は、対の処理の間で実行したい処理をブロックとして受け取るメソッドを
最速インターフェース研究会 :: HTMLドキュメントを解析して特徴的なループを見つけるBookmarklet
- 全てのDOMノードを列挙する - ノードは次のように文字列化される。 0: /html[0]/body[0]/div 1: /html[0]/body[0]/div[0]/div 2: /html[0]/body[0]/div[0]/div[0]/ul[0]/li 3: /html[0]/body[0]/div[0]/div[0]/ul[0]/li 4: /html[0]/body[0]/div[0]/div[0]/ul[0]/li 5: /html[0]/body[0]/div[0]/div[0]/ul[0]/li 直前の階層までは添え字つき、最後のノードはタグ名のみにする。 class名、id名は排除する。各々のサイトのルールで記述されたruleよりも タグのネスト構造の方が変化に強いし機械的に抽出しやすいのではないか？ 出現回数でソートする。li要素2-5はループであることが分か
きまぐれ日記: IMEにおける「文節」とは何ぞや
とあるIME開発者と仮名漢字変換(IME)における「文節」についてディスカッションする 機会がありました。今まであまり真剣に考えたことなかったのですが、 この「IME文節」、いろんな意味で興味深いということを改めて認識しました。 学校文法や自然言語処理におけるいわゆる「文節」とは 統語的な性質からほぼ一意に決定できる単位です。 簡単には 自立語連続＋付属語 と言えるでしょう。 たとえば、 「東京特許許可局で工藤は講演をした。」 は 東京特許許可局で｜工藤は｜講演した。 の3文節になります。小学校のときに「～ね」を挿入できる単位として 習ったかと思います。 しかし、IMEで上記の文を変換してみると。 東京|特許|許可局で|工藤は｜講演した|。 と分割されます。(WinXP) あきらかにNLP業界の文節と単位が異なるようです。 このIMEが使っている分割の単位を「IME文節」と呼ぶことにしまし
レビュー検索あれこれ - mixi engineer blog
こんにちは。夏休みが待ち遠しくって、夜なべしては旅行関係のサイトを巡っているmikioです。休みといえば、お出かけして美味しいランチ食べたり映画見たり、あるいは家で本読んだりゲームしたり音楽聞いたりしますよね。そんなあなたにお薦めしたいのがレビュー検索です。今回は、そこでのtipsや開発裏話などをお届けします。 mixiレビューとは、amazon.co.jpやぐるなびなどにある商品や店舗などについてユーザの皆さんがレビューを投稿できる機能です。気に入ったり気に入らなかったりする商品などについて一言言いたくなるのが人情というものですが、普通のmixi日記で言及するよりもレビューを書く方が後で読んだ時に有用です。レビュー機能の特徴は、1点から5点までの満足度をつけられることと、写真や説明などの関連情報が参照できることと、そして何より、他のユーザがその商品につけたレビューと比較できることです。
mixi Engineers’ Blog » Mixi::Music->recommend_music();
ミクシィ開発部アプリ開発チームのk_joeです。今回は先日『極秘裏に』改善されたmixiミュージックのアルゴリズムについて紹介したいと思います。 このブログを読んでる方々はmixiミュージックって使ったことあるのでしょうか？僕は心配症なので使ったことない人のために(宣伝ついでに)軽く説明からさせていただきたいと思います。mixiミュージックは「音楽で人をつなぐ by mixiミュージック担当」を理念として、個人が聞いた音楽をベースにいろいろな繋がり・関連性を生み出そうというサービスです。自分の聞いてる音楽についての情報をみんなで共有できて、その繋がりから新しい音楽との出会いがあるってすばらしいことですよね。(/宣伝終) mixiミュージックには自分の聞いている音楽からお勧めの音楽を提示するサービスとアーティストのリスナーがよく聴いている他のアーティストを提示するサービスがあります。ユーザが
『コンピュータを使わない情報教育 アンプラグドコンピュータサイエンス』
『コンピュータを使わない情報教育 アンプラグドコンピュータサイエンス』 監訳者：兼宗進 翻訳者：正田良、鎌田敏之、紅林秀治 翻訳協力者：西田知博、井戸坂幸男、保福やよい 追補執筆者：久野靖 ISBN978-4-904013-00-7 C3037 \1,500E 2007年9月1日第２刷 ★ご購入方法 ジュンク堂池袋本店に常備しております。 JUNKUDO BOOK WEBからご購入できるようになりました。 ※お問い合わせ ご購入、仕入れに関してはkyutaro@urap.orgにメールでお問い合わせください。 原著者たちは普段、コンピュータアルゴリズムの専門家として数式に囲まれながら研究を進めているはずですが、この本では10年以上前に、ティム・ベル博士が当時小学生だったお嬢さんに教えたときの体験を元に書かれているため、とても楽しく、わかりやすい内容
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
生きあたりまったりブログ
TechCrunch | Startup and Technology News
IBM Developer
