類似画像検索システムを作ろう - 人工知能に関する断創録
C++版のOpenCVを使ってカラーヒストグラムを用いた類似画像検索を実験してみました。バッチ処理などのスクリプトはPythonを使ってますが、PerlでもRubyでも似たような感じでできます。 指定した画像と類似した画像を検索するシステムは類似画像検索システムと言います。GoogleやYahoo!のイメージ検索は、クエリにキーワードを入れてキーワードに関連した画像を検索しますが、類似画像検索ではクエリに画像を与えるのが特徴的です。この分野は、Content-Based Image Retrieval (CBIR)と呼ばれており、最新のサーベイ論文（Datta,2008）を読むと1990年代前半とけっこう昔から研究されてます。 最新の手法では、色、形状、テクスチャ、特徴点などさまざまな特徴量を用いて類似度を判定するそうですが、今回は、もっとも簡単な「色」を用いた類似画像検索を実験してみます
オレオレ検索窓を設置しよう - mixi engineer blog
まだピクミン2をクリアしてないのでケジメ的に新作ゲームを買えないmikioです。今回は、Tokyo Cabinetを使って激烈簡単に特定サイトの専用の検索機能を設置する方法について説明します。クローリングから検索までを10分くらいの作業で可能にします。 特定サイトの検索エンジン Web全体の検索機能を作るのは、途方もない技術力と設備を持っているGoogleやMicrosoftなどのビッグプレーヤでないと難しいのが現実です。でも、自分が気に入っているいくつかのサイトを対象とした検索エンジンを作るのであれば個人だってできます。また、インターネットから手が届かないイントラネットのコンテンツの検索機能は自分達で手がけないと構築できません。 ということで、企業用の検索システムが数多く売られていますし、LuceneやGroongaやHyper Estraierなどのオープンソース製品も世に多数存在しま
クローラーを作るためのフレームワーク·Anemone MOONGIFT
RSSフィードやWeb API、Mashupなどの単語が注目を集める中、Webクローラーを通じて外部のWebサイトにあるデータをかき集め、それを解析して別な形にするというのはよく見られるものになってきた。 あるURLを指定し、そこからリンクされているURLを一覧表示できる そうした数々のシステムの中で、クローラーとなる基盤は大きな違いはない。Webサイトのデータを取得し、次のリンクを洗い出して取得していくようなものだ。そうした共通動作部分を切り出したフレームワークがAnemoneだ。 今回紹介するオープンソース・ソフトウェアはAnemone、Webクローラを開発するためのフレームワークだ。 Anemoneは任意のWebサイトにアクセスし、その内容を解析するWebクローラーだ。例えばあるURLに付けられているリンクを一覧で取得するようなことも簡単にできる。外部サイトなのかどうかも区別できるの
「ぽ地図」をダシに考えるウェブ地図の明後日
LatLongLabでデザイン等を担当しているinuroこと河合 太郎です。今日も座り心地の悪いイスに座ってモニターを眺めてる皆様、少し背伸びをして体をほぐしてみてはいかがでしょうか。 今回はLatLongLabの提供するサービスのひとつ「ぽ地図」を紹介させていただこうと思います。 何ですかそれは？ 「ぽ地図」という名前の由来はぽちっと押せる地図です。ではよく分かりませんね。 地図には「六本木ヒルズ」「ホテルアイビス」といったように建物の名前が書き込まれています。これらを地図用語では注記と呼びますが、通常は注記は単なる「絵」です。さわってもたたいても何も起こりません。 「ぽ地図」はこれら地図上の注記を直接クリック可能にしたインタラクティブな地図です。注記の上にマウスカーソルが重なると青くハイライトされ、クリックすると左側の情報ペインに建物や店舗の詳細情報が表示されます。情報ペインには店舗の
Logarithmic merging - naoyaのはてなダイアリー
IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったので、改めて復習してみました。 Dynamic indexing 頻繁に検索対象の文書群に更新が発生する場合の問題点は、(postings ファイルはディスク上にあるので) 転置インデックスをその都度構築し直すコストが高くなってしまうというところです。かといって更新をしないと、検索結果が古いままでヒットすべきものがヒットしなくなってしまいます。そこで Dynamic indexing の戦略を採ります。ディスク上の大きなインデックスであるメインのインデックスに加えて、インメモリの小さな補助インデックスを用意し、更
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
1日で作る全文検索エンジン - Building a full-text search engine in "ONE" day - - とあるはてな社員の日記
最近、「Introduction to Information Retrieval」というStanfordの大学院向け教科書のドラフトを読んでいます。id:naoyaあたりが勉強会で読んでいる教科書です。この教科書には、効率のいい全文検索システムを作るにはどうすればいいか、という(まさに)教科書的手法が網羅的に書いてあり、そのあたりに興味がある人には、非常に興味深く読めるお勧めの本です。 ただ、面白い面白いと言っているだけでは、エンジニアとしては価値半減ですので、GW中にrubyで一日かけて実装してみました。 さすがに実装は、一日で作ったものですから、非常に素朴です。マルチバイト文字はbi-gramで、シングルバイトはスペースなどの区切り記号で認識しています。インデックスは、rubyの処理系のHashやArrayで保持しており、外部にMarshallで書き出す、というものです。検索エンジン
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
JavaScriptとPHPでつくるAjaxインクリメンタル検索：CodeZine
はじめに Ajax（エイジャックス：Asynchronous JavaScript＋XMLの略称）はウェブ上のサービスを中心に普及してきました。 皆さんの開発現場でAjaxは活用されているでしょうか？ 最近はいろいろなJavaScriptフレームワークが出てきているため、Ajaxのサンプルもウェブ上に多く掲載されています。しかし、特定のJavaScriptフレームワークやWebアプリケーションフレームワークに依存したサンプルは制約も多いため、活用を躊躇しているITエンジニアも多いのではないでしょうか？ この記事では、特定のフレームワークを利用せずにAjaxによるインクリメンタル検索を実装してみることで、Webアプリケーションの基礎を振り返ってみたいと思います。 今回作成するインクリメンタル検索アプリは、蔵書の検索です。完成イメージを以下に示します。 本記事は、以下の順序で進みます。 全体の
OSS Message Pedia
さあ、始めよう オープンソースプロダクトのメッセージを検索できます。あなたが使用しているソフトウェアのエラーメッセージの対処方法が分かります。 調査して欲しいメッセージ 153(ja) [4] Debug: sleeping function called from invalid context at : [1 month ago] 84(ja) [3] request_module: runaway loop modprobe [18 days ago] 5356(ja) [3] : VFS is out of sync with lock manager! [1 month ago] 22473(ja) [3] : dma_timer_expiry: dma status == 0x [3 months ago] 13057(ja) [3] tty_check_change: tty
Geekなぺーじ：Google Code Searchの危険な使われ方
「Fun With Google Code Search」によると、 Google Code Searchを使って脆弱なソフトウェアを見つけられてしまうそうです。 実際に、Google Code Search経由で発見されてサーバを乗っ取られた事例が「How Hackers Are Using Google To Pwn Your Site」という記事で紹介されています。 ShoeMoneyが乗っ取られた事例では、恐らくWebサーバの設定ミスで.phpファイルの関連付けを行わない状態で、Google Sitemapsに登録してしまったため、Google Code Searchに自作コードが載ってしまい、それを見たクラッカーがサイトを乗っ取ったのであろうと思われます。 バッファオーバーフロー strcpy : strcpy\((\w+,\w+) lang:c sprintf : (sprin
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
gotAPI.com :: documentation search engine
Krugle - Transform Code into Profit.