lucille development blog » Blog Archive » Xorshift RNGs
This domain may be for sale!
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
地球にやさしいアルゴリズム---目次 - 地球にやさしいアルゴリズム：ITpro
アルゴリズムを構成している楽しい仕組みを紹介しながら，あなたに「おおっ」と言わせることが，本連載の最初の目的です。興味を持てたなら，アルゴリズムに関する文献や情報を抵抗なく読めるようになるはずです。アルゴリズムを使いこなしたり，作ることも無理なくできるようになるでしょう。 まずはいろいろなアルゴリズムの面白いところを見て，楽しんでみましょう 第1回 ナンプレを解いてみよう 第2回 パズルみたいに楽しいデータ圧縮 第3回 「場面」の移り変わりに注目する 第4回 できるだけ短いルートでゴールに到達する 第5回 隣の区画と異なる色で地図を四色に塗り分ける 第6回 上手なアルゴリズムの見つけ方 第7回 多対多の関係を賢く扱う 第8回 倉庫番を解くアルゴリズム 第9回 プロトコルを実現するアルゴリズム 第10回 麻雀の役を判定する 第11回 プログラム同士の対戦ゲーム 第12回 対戦ゲームの戦略を考
[を] Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 DP はいわゆる「類似文字列検索（あいまい検索）」に使うと 便利なアルゴリズム。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二
僻地 - Bayesian Setの種明かし
Bayesian Setとは集合D_Cが与えられたとき、そこから「類推」して、元の集合C⊃D_Cに入る元xを(「自信」の度合いを表す数値つきで)求めるというもの。ただし、D_Cの元やxは特徴データ{c_i}をもっているとする。で、原論文を読むとΓ関数がずらずらでてきておどろおどろしいのだけれど、実はやっていることは簡単だということに気がついたので、書いてみる。簡単のために、特徴はあるかないかの2値的とする。(一般的には連続量も扱える。)すると、Bayesian Setのアルゴリズムがやっていることは、xについて観測された特徴c毎に重みwを足していくだけである。重みwはハイパーパラメーターα、βを使って,と書ける。ハイパーパラメータというと難しいそうだが、α_t = (Nc:D_Cでcをもつ元の数) + α、β_t = (N-Nc:D_Cでcを持たない元の数) + βと定めるので、α、βは先
西尾泰和のブログ: 一般化したハノイの塔問題にひそむ規則性
これは2006年冬のプログラミングシンポジウムの GPCCの会議で出た「棒の本数が4本以上のハノイの塔はどうなるのだろう」という疑問について、 1月15日に走り書きして放置していた結果( 西尾泰和の日記(2006-01-16) )を清書したものです。 ハノイの塔問題を知らない方は ハノイの塔 - Wikipedia を参考にしてください。 従来のハノイの塔問題では、棒の数は3本でした。 この場合、板が1枚ならば1手で動かせますが、 2枚の場合は1枚目を脇にどけて2枚目を動かし1枚目を2枚目の上に戻す、 という3手がかかります。 これを、板の枚数2とスタートとゴールをのぞいた 「一時待避用の棒」の本数1とを用いて 「hanoi(2, 1) == 3」と表現します。 また、この待避用の棒が1本あることを 「スペースが1個ある」と表現します。 スペースが1個のハノイの塔問題に関しては 「hano
Pythonでアルゴリズム - Konnichiwa, A doumo
これはなんですか？ 奥村晴彦氏の著書「C言語による最新アルゴリズム事典」をPythonでやろうと決意。Rubyに翻訳されていたので、Pythonでもやってみようと。でも実は書籍はもっていなくてCとRubyのソースを見つつ翻訳しています。１日１個ペースで進んでいます。 やっているうちにこの本が欲しくなってきました。 個人のPython力を高めるために始めましたので、間違いが含まれているかもしれません。ご指摘等ございましたら連絡[syobosyobo at gmail dot com]ください。 ちょっと方針をかえて、ctopyで訳すことにした。またまた方針をかえて、、、ctopyはあまりつかえない。ちょっといじってやらないと、出力がよくない。コメントとか入ってると、うまく変換してくれないし。 で、そのあとPythonらしい書き方で書いていこう、かと。どうなるかわかりませんが。
どうなっているの？あのソフトの仕組み - 今からでも遅くない！アルゴリズム入門：selfup
Webの全体像を効率よく取り込み，分類する 「YSTのシステムは大まかに三つの機能に分かれます（図2）。最初は世界中のWebページをYSTのシステムに取り込む『クローリング（crawling）』という機能です」（Yahoo! JAPAN，リスティング事業部 検索企画室の宮崎光世氏，以下同）。 取り込むと簡単に言っても，Webページの数は膨大なうえ，更新の頻度や情報の質などがまちまちです。すべてのページに同じようにアクセスしていると非効率なことこの上ありません。そこで，限られた時間で質の良い検索ができるようにするための工夫をしています。例えば，クローリングを繰り返すうちに頻繁に更新されることがわかったページは短いサイクルでチェックし，ほとんど更新のないページはチェックの頻度を落とす，といったことをしているそうです。 ただ，更新の頻度が単に高いだけではダメです。重要性が高いと考えられるWebサ
Bayesian Sets - mots quotidiens.
Bayesian Sets (Ghahramani and Heller, NIPS 2005)は Google Sets と同じようなことをベイズ的に行うアルゴリズムです。 いくつかアイテムを入れると, それを「補完する」ようなアイテムを 返してくれます。 これは NIPS の accepted papers が出た去年の8月から気になっていて, 本会議ではオーラルの発表もあって大体のやっていることはわかった ものの, 何と(本会議の時も!)論文がなく, 直接Hellerに連絡して もらえるように頼んでいたところ, Online proceedings の締切りがあった 時に連絡があって, 読めるようになりました。(リンクは下のページ参照) 岡野原君に先に 紹介 されてしまいましたが, 以下は, 岡野原君が書いていない話。 Bayesian Sets は, アイテム集合 D に対して,
横着プログラミング 第6回: chatty: 小うるさい端末
最終更新日: 2002-09-18 (公開日: 2002-09-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 才気に富んだことは個人が行うのが通例であり、信じがたきバカ さ加減は大抵組織に帰されるものである。 -- Jon Bentley *1 役に立たないソフトウェアを作るのが好きだ。面倒な作業を楽にす る横着ソフトウェアもいいが、たまには人を呆れさせるくだらない ソフトウェアを作るのも楽しい。 以前に私が開発した cdbiff*2というソフト ウェアは、メールが届くと PC の CD-ROMドライブが開いてメール の到着を通知するという役に立たないものであったが、そのくだら なさが受けて予想外の好評を得た。今回は、そうした役に立たない ソフトウェアの 1つである、小うるさい端末 chatty*3 を紹介する。
きまぐれ日記: Schwartzian Transform でランダムシャッフル
Schwartzian Transform を使って配列をシャッフルする話をみて、なるほどな～と思いつつも、よくよく考えてみるとこれは2つの意味で駄目です。 1. 計算量が O(n * log(n)) であること。 2. ランダムにシャッフルできない。 1. は説明するまでもないので、2の理由を考えてみます。 まず、rand() が 0..k-1 までの k種類の整数から 1 つ数値を返すものとします。配列のサイズが n の場合、 weightの並びの場合の数は k^n 通り存在します。ところが、配列の順列の場合の数は n! です。 ここで何か矛盾点があるように思えてきます。 実際に k = 2, n = 2 の場合を考えて見ましょう。この場合、サイズ2の配列をシャッフルするんですから、 要素を入れ替える場合と入れ替えない場合が 1/2 の確率で出現するのが正しいシャッフルです。 k =
Ｃ プログラミング(基礎と応用)
WindowsXPの基礎 ●WindowsXPの基礎(pdfファイル) １．起動と終了 １．１ 起動法 １．２ 終了法 ２．ウィンドウの基本操作 ２．１ ウィンドウの各部名称 ２．２ ウィンドウの移動 ２．３ ウィンドウ・サイズの変更 ２．４ ウィンドウの重なり ２．５ ウィンドウのスクロール ２．６ ウィンドウを閉じる ３．USBメモリ ４．トラブル対処法 ４．１ 強制終了 ５．メモ帳の使い方 ５．１ 新規ファイルの作成 ５．２ ファイルの修正 ５．３ 文書の編集 ５．４ ファイルの印刷 ６．ファイル管理 ６．１ 階層構造 ６．２ エクスプローラの使い方 ６．３ ファイルの圧縮と展開 ＵＮＩＸの基礎 ●ＵＮＩＸの基礎(pdfファイル) １．ログイン・ログアウト １．１ 端末エミュレータ １．２ Ｘサーバエミュレータ ２．簡単なコマンド ３．ファイル処理 ３．１ ファイル操作法 ３．２
はてなブログ | 無料ブログを作成しよう
はじめまして新潟 隣の県なのになんとなく遠いイメージがあった新潟。休日出勤の振休と夫の休暇（上司から取れと言われたらしい、かわいそ…）が合ったので久々に遠出しよう！となり新潟へ。このあたりで隣の県を選ぶあたり我々の出不精具合が現れていますね。 1日目 行くぜ新潟 まずはへ…
Hough変換による画像からの直線や円の検出：CodeZine
はじめに Hough変換は、画像から直線や円を検出する技法として知られています。通常の直交座標上の画像を、極座標の二次元空間（直線検出の場合）に変換したり、三次元の空間（円検出の場合）に変換したりして、そこで最も頻度の高い位置を求め、それを逆変換して、直線や円を検出します。 Hough変換は数学的に興味深く、プログラムの対象として面白いため、多くの論文が見られますが、実用化には多くの問題点もあります。 ここでは最初に、一般的なHough変換の基本プログラムを紹介し、次に交通標識認識への応用に特化したプログラムについて述べます。 基本図形認識版アプレットを見る 交通標識認識版アプレットを見る 対象読者 画像から直線や円を検出する方法に興味を持ち、その一つであるHough変換の仕組みを学びたい人。 必要な環境 J2SE 5.0を使っていますが、J2SE 1.4.2でも大丈夫で
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://ja.doukaku.org/
Amazon.co.jp: 計算困難問題に対するアルゴリズム理論: J.ホロムコヴィッチ (著), 和田幸一 (翻訳), 増澤利光 (翻訳), 元木光雄 (翻訳): 本
vincent krutler
NaokiTakahashiの日記 - 乱数について
きまぐれ日記: はてなキーワードを高速に付与