トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
著名ソーシャルメディアが使っているアルゴリズムを大公開！ | Moz - SEOとインバウンドマーケティングの実践情報
“アルゴリズム”は、もっとも非人間的なものの代表だともいえる。ソーシャルメディアにとって、そのアルゴリズムが不可欠だというのは、実に皮肉めいている。 僕はこの間、グーグルがどうやってユーザーデータを集めているかについて書いた記事を掲載した（前編、後編）。今回は、著名なソーシャルメディアサイトが、ユーザーデータを活用する上でどのようにアルゴリズムを用いているのか、白日の下にさらそう。 ソーシャルメディアを成り立たせているのは人間の力だが、ユーザーが入力したデータを利用できる状態にする仕組みは、アルゴリズムによって作られている。現在活動している無数のソーシャルメディアサイトで実証済みのことだが、ユーザーの関与とアルゴリズムによる処理ルールの上手いバランスを見出すことは、とても難しくなりがちだ。これから紹介するアルゴリズムは、悪意のないユーザーと結びついて初めてうまくいくものだ。 人気ソーシャル
404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1
404 Blog Not Found:アルゴリズム百選 - 配列を再発明する
2007年12月03日04:00 カテゴリアルゴリズム百選 アルゴリズム百選 - 配列を再発明する アルゴリズムを理解するのに最適な方法は、すでに当たり前のように使われている仕組みを、もう一度時分の手で作ってみることです。ここでは、配列に関するアルゴリズムを再実装してみます。 ここでは、MyArrayというオブジェクトを作って、それに配列としての機能を持たせることにします。まずは基本的な操作ができるようにしておきます。 残念ながらRubyなどと異なり、JavaScriptでは[]を演算子として再定義することは出来ないので、ここではget()メソッドとset()メソッドをその代わりとして用意することにします。また、利便性を考えて、組み込みのArrayに変換するtoArray()メソッドも用意しておくことにしましょう。 function MyArray(){ this.size = argum
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
ソート処理時間、選ぶアルゴリズムでこんな差が！ ― ＠IT自分戦略研究所
ソート処理時間、選ぶアルゴリズムでこんな差が！：いまから始めるアルゴリズム（2）（1/2 ページ） 連載第1回「『＋1』だけで四則演算をするには？」に引き続き、プログラミングにおけるアルゴリズムの重要性と面白さを紹介したいと思います。例としてプログラミングで頻繁に使われる並べ替えと検索のアルゴリズムを取り上げ、それぞれがどういった処理を行っているのか考えてみましょう。 同じ問題でも解き方（アルゴリズム）によってかなりの速度の違いが出てくる可能性があることは、前回紹介したとおりです。今回は代表的な並べ替えのアルゴリズムを基にプログラムを作成し、実行にかかった時間を測定して、具体的な処理速度の違いをお見せしようと試みています。 プログラミング言語では、すでに並べ替えの仕組みが用意されていることが多いので、このアルゴリズムをあまり意識していない人もいるのではないでしょうか。しかし、すべてのプログ
きまぐれ日記: 情報抽出アルゴリズムEspresso の謎、私の勘違いでした。
昨日のエントリーは私の完全な勘違いでした。大学数学やりなおします。orz 行列表現にはまちがいはないのですが、あの形はマルコフ連鎖そのものなので、 x_instance = A * x_instance の解は、x_instance = A^{n} * x_instance0 なので、x_instance0 の初期値 に依存します。A^{n} が収束し B になるとすれば、x_instance = B * x_instance0 となります。 A^{n} が収束することが条件ですが、相互情報量の最大値で正規化されているので、たぶん収束するでしょう。 しかし、Espresso のおもしろいところは, B が求まってしまえば、どんな初期値でもただ1回の行列のかけ算で 最終的な答えがでてしまうところです。 B は、全パターンと全インスタンスの類似度から生成される行列で、信頼度とは無関係です。相互
きまぐれ日記: 情報抽出アルゴリズム Espresso 最終章
Espresso を飲みながらさらに Espresso を考えていました。 r_instance = A^n * r_instance_0 となるのは間違いないと思います。A は P * P^{T}、さらに P = 1/|I||P| * pmi(i, p)/ maxpmi です。 A は、インスタンスどうしの類似度を表現した正方対称行列です。A_{i,j} はインスタンス i, j の類似度です。 類似度は、パターン個数次元からなるベクトルの内積で、各次元は pmi となります。 この形だと、r_instanc は r_instance_0 できまるので、初期値に依存してるように思えますが、A^n がいったい どういう意味を持つのかずっと考えていました。 A_{i,j} が 0, 1 の場合、A は無向グラフの接続行列となります。i,j がつながっている場合は A_{i,j} = 1となり
辞書不要の形態素解析エンジン「マリモ」とは − ＠IT
2007/08/15 検索サービスを提供するベンチャー企業のムーターは8月1日、辞書を必要としない形態素解析エンジン「マリモ」の提供を開始した。従来、形態素解析では品詞情報を含む日本語辞書を用意するのが常識だったが、マリモでは、そうした辞書を不要とした。新技術のアプローチと特性について、開発元のムーターに話を聞いた。 統計処理で単語部分を推定 形態素解析とは、与えられた文を、文法上意味のある最小の単位（形態素）に区切る処理。「今日は晴れています」なら、「今日（名詞）／は（助詞）／晴れ（動詞）／て（助詞）／い（助詞）／ます（助動詞）」と分ける。検索エンジンをはじめ、さまざまな自然言語処理の場面で必要となる基礎技術だ。 形態素解析を行うには、あらかじめ品詞情報が付加された数十万語からなる辞書を用意する必要がある。また、新語や造語、専門用語に対応するには、個別に人力で単語を登録する必要がある。
ワードサラダ技術について
後半部分が重要で、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である ということです。 さて、実例です。たとえば次の文章を考えてみます。 「通信販売大手セシールは９日、生命保険の販売に本格参入する方針を明らかにした。」 まず形態素解析するとこんな感じになります。 通信 名詞,サ変接続,*,*,*,*,通信,ツウシン,ツーシン 販売 名詞,サ変接続,*,*,*,*,販売,ハンバイ,ハンバイ 大手 名詞,一般,*,*,*,*,大手,オオテ,オーテ セシール 名詞,固有名詞,組織,*,*,*,セシール,セシール,セシール は 助詞,係助詞,*,*,*,*,は,ハ,ワ ９ 名詞,数,*,*,*,*,９,キュウ,キュー 日 名詞,接尾,助数詞,*,*,*,日,ニチ,ニチ 、 記号,読点,*,*,*,*,、,、,、 生命 名詞,一般,*,*,*,*,生命,セイメイ,セイメイ 保険 名詞,一般
データ圧縮法概説 目次
最終更新日：2001年7月2日 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
書評 - アルゴリズム・サイエンス (入口|出口)からの超入門 : 404 Blog Not Found
2007年05月30日04:00 カテゴリ書評/画評/品評 書評 - アルゴリズム・サイエンス (入口|出口)からの超入門 正三郎さんのお薦めという事で、手に入れてみた。 出口からの超入門 入口からの超入門 共立出版「アルゴリズム・サイエンスシリーズ」: ホットコーナーの舞台裏そのとき、見つけたのが、休刊したbit誌など我々コンピュータ業界ではおなじみの共立出版が新たに刊行を開始した「アルゴリズム・サイエンスシリーズ」。 本シリーズ「アルゴリズム・サイエンス」の嚆矢である「入口からの超入門」ならびに「出口からの超入門」は、読んで字のごとくアルゴリズムの入門である。入口と出口に分けているのがニクい。入口はまだアルゴリズムというものを意識していない人々のための、そして出口はすでにアルゴリズムの威力は知っていても、日々の業務に負われて仕様書をそのままプログラムに書き直すのに疲れ気味の人々にアピー
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
第6回 上手なアルゴリズムの見つけ方
図1に示すHTML形式のテキスト・データ（以下，HTMLデータ）があります。このHTMLデータをブラウザに表示させたときに「表示される文字列」と「その文字列に対して有効なタグ名」を対応付けるアルゴリズムを考えてください。結果は配列に格納して，画面に表示させるものとします（図2）。 見わたせば，世の中はアルゴリズムだらけです。私のようなプログラマは，日常生活でも「締め切り順に仕事をソートしてごらん」「仕事のスタックがたまっているからてんてこまい」など，いま置かれている状態をアルゴリズムやデータ構造になぞらえて会話することがよくあります。前回紹介した再帰処理と言えば，落語の演目の一つ，「頭山」です。自分の頭に生えた桜の木を引っこ抜いて，その跡にできた池に自分自身が身を投げる，という不思議な話ですが，これこそ再帰処理をよく言い表していると思います。 このように世の中には，ハッシュだってスタックだ
[P2P]位置情報を数値1つで表す手法「Z-ordering」 - Tomo’s HotLine
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 □はじめに ＤＨＴやＳｋｉｐｇｒａｐｈなどの技術が注目されるとともに、位置情報をP2Pで扱いたいという要望がでてきている。だがＤＨＴやＳｋｉｐｇｒａｐｈは1次元の数値で各ノードが扱う情報範囲を扱うため、位置情報など多次元の情報を扱うのには、当初は向いてないと見られていた。しかしあるテクニックを使うとそれは一発で解消する。それがZ-orderingである。なお、このZ-orderingは位置情報を扱えるP2PミドルウェアPIAXでも採用されている。 □簡単な例 多次元を1次元で表すにはどうすればよいのだろうか？まずここで一例を挙げてみる。 例えば、2次元空間においてｘ＝｛１
![[P2P]位置情報を数値1つで表す手法「Z-ordering」 - Tomo’s HotLine](https://cdn-ak-scissors.b.st-hatena.com/image/square/b4e38426fa9529bdb687a0c8ea1406a0f5bee683/height=288;version=1;width=512/http%3A%2F%2Ftoremoro.tea-nifty.com%2F.shared-cocolog%2Fnifty_managed%2Fimages%2Fweb%2Fogp%2Fdefault.png)
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
