タグ

algorithmに関するsivadselimのブックマーク (33)

  • Quicksilverは如何にして鋭い検索を行っているのか? - ザリガニが見ていた...。

    Quicksilverの検索性能が、感性をくすぐってきた。 「apple」→「AppleScript Editor」 「ase」→「AppleScript Editor」 「prol」→「Property List Editor」 「im」と入力して、「Image Capture」を起動したいが、「iMove」がトップヒットになってしまう...。 そんな状況でも、候補リストから2回連続で「Image Capture」を選択すれば、3回目以降は「Image Capture」がトップヒットになる。 直近のユーザーの好みを学習してくれるのだ。 もちろん、「ima」まで入力すれば「Image Capture」がトップヒットになる。 「ase」「prol」のような、単純な前方一致でも、部分一致でもない検索には恐れ入る。しかも、シンプルだけど学習もしてくれる。使うほどに手に馴染んでくる仕組みは、この辺

    Quicksilverは如何にして鋭い検索を行っているのか? - ザリガニが見ていた...。
  • 何度見ても信じられない! 落書きから写真を合成!? PhotoSketch(動画あり)

    何度見ても信じられない! 落書きから写真を合成!? PhotoSketch(動画あり)2009.10.06 19:005,262 ネットの画像シーンに激震が走ろうとしています。 「PhotoSketch」はウェブベースの写真検索合成ツール。 いや、そんな言葉じゃ片付けられません。とにかくこの動画を見てください。 使い方はこんな感じ。まず、簡単にラフなスケッチを描きます。そして、それぞれのアイテムにラベル付けをします。上の図だと、「ボート」とか「結婚式のキス」とかですね。 そうとすると...! なんと! ネットからそれに合うイメージを検索、合成してくれるんです! いや何度見ても信じられませんよ。自分で描いた適当なラフ画を元に、どの写真が一番マッチするか選び出し、人、鳥、背景等、それぞれ違う写真からもってきたオブジェクトをうまいこと周りの背景に馴染ませて1枚の写真を作っています。 もちろん完璧

    何度見ても信じられない! 落書きから写真を合成!? PhotoSketch(動画あり)
  • Google検索アルゴリズムで生態系崩壊を予測 | WIRED VISION

    前の記事 「飛行機からレーザーで地上攻撃」実験に成功 Google検索アルゴリズムで生態系崩壊を予測 2009年9月 8日 Hadley Leggett 写真:Flickr/fusion68k、イラスト:PLOS Computational Biology。サイトトップの画像は海藻をべるマナティ。画像はWikimedia Commons 生物学者たちは、生態系を破壊する最も効率的な方法を見い出した――Google社の検索アルゴリズムに基づいてだ。 物網の要になる生物種が絶滅すると、生態系全体の崩壊を引き起こす危険性があるということは、以前から科学者の間では知られていた。だが、種の相互作用は無数ともいえるほど存在するため、どの動物や植物がいちばん重要なのかを推測することは難しい。 [現在の群集生態学では「物連鎖」という言葉より、物網という概念の方が現実的なものとして重視されてきている

  • 最強最速アルゴリズマー養成講座:あなたの論理的思考とコーディング力は3倍高められる (1/2) - ITmedia エンタープライズ

    全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」。稿では、アルゴリズム部門のSRMで取り上げられる問題を考えながら、論理的思考力およびコーディングのテクニックを養っていきます。 はじめに はじめまして。高橋直大です。連載「最強最速アルゴリズマー養成講座」では、全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」について、そこで出題される数学・アルゴリズムのパズルを考えることで、コーディングのテクニックおよび論理的思考力を磨くことを目的に開始するものです。ここで扱う技法は主にアルゴリズムのそれですが、その根底にはロジカルな思考術が存在します。そうした能力を養いたい方にとって少しでも役に立てれば幸いです。 なお、稿は必要に応じてコーディング例も紹介しますが、TopCoderで出題される問題の中から比較的やさしい問

    最強最速アルゴリズマー養成講座:あなたの論理的思考とコーディング力は3倍高められる (1/2) - ITmedia エンタープライズ
  • 7+6の計算をする時6=3+3だから7+3+3で13って求める奴ちょっと来い

    1 名前:以下、名無しにかわりましてVIPがお送りします:2009/08/26(水) 04:14:54.93 ID:P4/WG89F0 お前とはいい酒が飲めそうだ `¨ - 、     __      _,. -‐' ¨´ | `Tーて_,_` `ー<^ヽ |  !      `ヽ   ヽ ヽ r /      ヽ  ヽ  _Lj 、    /´ \     \ \_j/ヽ ` ー   ヽイ⌒r-、ヽ ヽ__j´   `¨´  ̄ー┴'^´ 118 名前:以下、名無しにかわりましてVIPがお送りします:2009/08/26(水) 04:47:34.61 ID:XxRcqydp0 丸暗記だろ なんでわざわざ分解するんだよ 4 名前:以下、名無しにかわりましてVIPがお送りします:2009/08/26(水) 04:16:59.21 ID:OPdj08zaO 2×7=14 14-1=13 もしくは

  • 人工脳の進化実験:「だます戦略」も進化 | WIRED VISION

    前の記事 「机や服を爪でこする音」を使った入力システム(動画) 人工脳の進化実験:「だます戦略」も進化 2009年8月20日 Brandon Keim Image: PNAS。サイトトップの画像は、人工呼吸の訓練用ダミーたち。Wikimedia Commons 映画『ターミネーター』シリーズのお蔵入りになったシーンだと言われたら信じてしまいそうな実験が行なわれた。ロボットたちに「人工脳」を搭載して動物たちのように生存競争を行なわせたところ、短期間のうちに進化し、互いをあざむく技を身につけたのだ。 これらのロボットはサッカーボールほどの大きさで、車輪とセンサー、点滅する信号ライトを組み合わせてあり[画像B]、デジタルの神経回路で制御されている。ロボットを設計した研究者らは、これらのロボットを1つのコートに入れて競わせた。コートの両端に、「物」「毒物」を示す紙製の円を置き、物を見つけてその

  • 一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録

    一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの?ってことになるので、

    一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
  • Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure

    画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。

    Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure
  • 3行でできる超お手軽全文検索 - mixi engineer blog

    梅雨。部屋干しした洗濯物による異臭騒ぎに苦しむmikioです。今回は、Tokyo Cabinetのテーブルデータベースで超お手軽に全文検索をする方法について説明します。 使い方 テーブルデータベースについてまずおさらいしておきましょう。PerlRubyのハッシュのようにコラム名とその値を関連づけた構造を、主キーを識別子として保存するデータベースです。例えばRubyからデータを保存するに以下のように行います。データベースであることをほとんど意識させないというのが素敵ポイントです。APIはCでもPerlでもRubyでもほとんど同じなので、言語にかかわらず同じようにレコードを操作できます。 require 'tokyocabinet' include TokyoCabinet # データベースを開く tdb = TDB::new tdb.open("casket", TDB::OWRITER

    3行でできる超お手軽全文検索 - mixi engineer blog
  • ガベージコレクションの実装法と評価

    1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい

  • 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で書き出す、というものです。検索エンジン

  • nobilog2: 好きなアルゴリズム:モンテカルロ法

    今週前半、小飼弾さんの「404 Blog not found」が「プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10」という記事を載せていたが、仕事も一段落間近かなので、その記事を見て以来、書きたいと思っていたことを書いてみようと思う。 nobilog2復活へのリハビリエントリーだ。 小飼さんの記事は、Hatena Questionの「あなたが一番好きなアルゴリズムを教えてください。また、その理由やどんな点が好きなのかも教えてください」がきっかけになった記事のようだ。 私はプログラマーではないが、まだパソコンが8ビットで「マイコン」と呼ばれていた時代に出会って衝撃を覚えたアルゴリズムがある。 もしかしたら一般に言うアルゴリズムとは別なのかもしれないが、Wikipediaでも"algorhythm"と書かれていたので許して欲しい(広義のアルゴリズムにはぎりぎり入るのではないだろ

  • ConsistentHashing - コンシステント・ハッシュ法

    ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R

  • ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40

    高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール(アルゴリズム)があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。(リンク先には、一部アルゴリズムと呼べないものも含まれています) 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書(リンク切れ) ドラクエの物理ダメージ計算式は質的にどれも同じだが、細かい部分で微妙に違う RPG INST

    ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
  • 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10

    2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズムの発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法

    404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
  • あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな

    あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。

  • はてなのCAPTCHAは簡単に破れる

    CAPTCHAをご存知でしょうか。 スパム防止のために歪んだ文字とかを入力させる、アレのことなのですが、 はてなのCAPTCHAの強度が妙に低く思えたので検証してみました。 CAPTCHAというのはいわゆる逆チューリングテストという奴で、 人間には可能だが機械には処理しにくいことをさせることで、 ロボットによる操作を弾こうというものです。 たとえば、Gmailのユーザ登録には以下のような画像が表示され、 表示されている文字を入力することが求められます。 CAPTCHAの強度 例えばスパムを送るために大量のGmailアカウントを得ようとしてる人がいたとします。 手作業でGmailを登録するのは骨が折れる。 そこでプログラムによる機械化を試みることになるわけです。 その際、障壁となるのがこのCAPTCHAなのです。 この画像から正解である文字列"vittac"を得ることは機械には難しい。 プロ

  • 形態素解析 - Wikipedia

    形態素解析(けいたいそかいせき、(英: morphological analysis)は自然言語の文字列を意味に基づく最小単位へ分割しその品詞を特定する処理である[1]。 形態素解析とは、対象言語の文法や単語の品詞等の情報[注 1]にもとづき、文法的な情報の注記の無い自然言語のテキストデータ(文)を単語の列に分割し、各単語の品詞や活用などを判別することで形態素(おおまかにいえば、言語で意味を持つ最小単位)の列を得る作業である[1]。 自然言語処理の分野における主要なテーマのひとつであり、機械翻訳やかな漢字変換など応用も多い(もちろん、かな漢字変換の場合は入力が通常の文と異なり全てひらがなであり、その先に続く文章もその時点では存在しないなどの理由で、内容は機械翻訳の場合とは異なったものになる)。 もっぱら言語学的な観点を主として言語学で研究されている文法にもとづく解析もあれば、コンピュータ上

    形態素解析 - Wikipedia
  • livedoor Developers Blog:String::Trigram でテキストの類似度を測る - livedoor Blog(ブログ)

    こんにちは。検索グループ解析チームの nabokov7 です。 今回は、livedoor キーワードでの事例より、テキストの類似度を測るのに便利な手法を紹介します。 livedoor キーワードは、livedoor ブログでその日その日で話題になった語をランキング表示するサービスです。 当初、はてなキーワードやWikipediaを足して2で割ったようなサービスを作れといった開き直った指示のもとで開発が開始されたともいう、分社化前の芸風の名残で、キーワードの検索結果にはユーザが自由に解説を書き込める Wikipedia 的スペースもついています。 で、この解説部分に、さまざまなサイトから文章をまる写ししちゃう人がとても多いのですね。 特に多いウィキペディア日語版からの剽窃を防止するために、livedoor キーワードでは以下のような対策を講じることにしました。 ウィキペディア日語版の解説

  • sparsetable - steps to phantasien t(2007-09-07)

    Matz日記 で紹介されている google-sparsehash を眺めてみた. ひさびさに Google 気分. :~/src/sparsehash-0.8 omo$ wc `find src/google/ -type f` 253 1348 10336 src/google//dense_hash_map 237 1309 9884 src/google//dense_hash_set 238 1244 9616 src/google//sparse_hash_map 223 1214 9245 src/google//sparse_hash_set 919 4776 37957 src/google//sparsehash/densehashtable.h 42 189 1187 src/google//sparsehash/sparseconfig.h 884 4642 371