Tumblr
「JPEG Tilt」というページを公開しました。MotionJPEG Builder を作った時に、JPEG のヘッダを読み込む処理を作ったので（結局これは使わなかったんですが）圧縮データの読み込み部分も作ってみようか、という気になって作ったのがこれです。JPEG ファイルで画像が圧縮される様子を視覚的に表現する…… という目標だったのですが、どうでしょうか。まあ内容が内容なので説明無しではさすがに意味が分からないと思います。 ということで、JPEG Tilt の見方を以下で簡単に説明します。 図1は、JPEG Tilt の画面です。画像が iTunes の CoverFlow のように並んでいますが、これの左側は画像の低周波成分のみを抜き出した物で、右に行くとより高周波の成分も含めるように並んでいます（低周波、高周波という言葉の意味はこの先で出てきます） 画像の上にマウスカーソルを乗せ
物理モデルのガンダムを遺伝的アルゴリズムで歩かせたムービーがすごい
3Dと物理エンジンを使っていろいろな実験を行っているむにむにさんが、「ガンダムを遺伝的アルゴリズムで歩かせた」というムービーをニコニコ動画とYouTubeにアップしています。そもそも遺伝的アルゴリズムというのが何かわからなくても、それを説明してくれるムービーも用意されているので、いったいどれだけすごいことを試行錯誤しているのかがわかるようになっています。 YouTubeでのアカウントは「3D Creature Physics(99munimuni)」という名前になっています。 ガンダムを遺伝的アルゴリズムで歩かせた。walked the Gundam By genetic algorithm - YouTube すでに物理エンジンでガンダムを歩行させることに成功したむにむにさんが挑戦したのが、遺伝的アルゴリズムで歩行を改善していくということ。 このザクっぽい単純モデルだとたくさんのモデルを
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
緯度経度を文字列で表すGeoHash - @masuidrive blog
なんか世間的に位置情報アプリが流行ってるらしいし、Google App Engine(GAE)も楽しそう。どうせだから、GAEでなんか位置情報アプリでも作ってみよう！と思ってTwitterに書き込んだところ、Geohashという、位置情報のプロトコル？を教えてもらいました。 これは、その名の通り、位置情報をハッシュで表す規格なのですが、いろいろおもしろい特徴があり、調べているうちに楽しくなってきたので、勢い余ってPure Rubyのライブラリまで書いちゃいました。 そのあと、結局ライブラリを作ったところで満足して、アプリは何も作らなかったので、せめてGeohashの解説でも書いておこうと思います。 位置情報は通常、緯度経度で表します。たとえば東京タワーの緯度経度は35.65861, 139.745447です。 北を上にした地図でいうと、緯度がY座標で経度がX座標です。英語では緯度をlati
Wheren っていうのを作ってる話 - soh335 memo
最近 Wheren っていうのを作っていて簡単に言うと GeoHash に時間を縦軸に加えたものです。いつどこを扱うので where + when を足して wheren です。 緯度経度時刻の範囲をハッシュ化出来るので、その３つの範囲で検索する時に、わりと力を発揮してくれるんじゃないかと思います。下にも書いてあるんですけど、割りと狭い範囲で効いてくる感じなのですれ違い通信とかで使えそうかなぁという感じがしています。 前方一致の仕組みはGeoHash同様に入っています。 soh335/p5-Data-Wheren · GitHub コードはこちら。perlモジュールの書き方がちょっとまだ掴めてないので間違ってたら教えて下さい。 仕組み GeoHash 自体は Z-order っていうのがベースになっていて、それを３次元に展開してるって事です。 GeoHash はハッシュ化する文字列の長さに
データマイニングで使われるトップ10アルゴリズム - 『企業成長の方程式 ― AIDグロースコミットによる成長戦略』
2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。 必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。 データマイニングの基礎 View more presentations from Issei Kurahashi 1. C4.5 C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。 CARTは2分岐しかできないがC4.5は3分岐以上もできる C
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
random()とrandom()*random()はどっちがランダムか？ | TRIVIAL TECHNOLOGIES 4 @ats のイクメン日記
みんなのIoT/みんなのPythonの著者。二子玉近く160平米の庭付き一戸建てに嫁/息子/娘/わんこと暮らしてます。月間1000万PV/150万UUのWebサービス運営中。 免責事項 プライバシーポリシー stackoverflowで見つけた乱数に関する質問「乱数のランダムさって？」に対する解答が面白かったので紹介します。 乱数のランダムさというのは，沢山標本をとったときに，標本値がまんべんなく均等に分布する，ということ。プログラミング言語などに組み込まれた乱数を発生する仕組みが返す値が均等に分布してないと，テトリスでなかなか長い棒が落っこちてこなかったりするわけです。 数学的な詳細はともかく，こういう知識はプログラミングをする上で知って置いた方がよいと思います。 さて，質問の内容は random()とrandom()×random()のどっちがランダムなの？ というもの。後者はrand
システム工学基礎
HMM:隠れマルコフモデル 電子情報工学科 伊庭 斉志 一次マルコフ連鎖 状態集合 S={1,2,…n} 遷移確率(k→ｌ) akl 隠れマルコフモデル（Hidden MM:HMM） 出力記号集合Σ 出力確率(状態から出力記号への写像) ek(b) : S → Σ マルコフモデルと 隠れマルコフモデル HMM≒有限オートマトン＋確率 定義 出力記号集合Σ 状態集合 S={1,2,…n} 遷移確率(k→ｌ) akl 出力確率 ek(b) 開始状態 終了状態 0.4 0.6 0.3 0.7 0.5 0.5 1 2 3A: 0.2 B: 0.8 A: 0.7 B: 0.3 A: 0.1 B: 0.9 隠れマルコフモデル(HMM) Rain Dry 0.70.3 0.2 0.8 • ２つの状態: ‘Rain’ と ‘Dry’. • 推移確率:
エラー率わずか0.00000625％、驚異のインド式昼食配達システム「ダッバーワーラー」
日本の物流システムのものすごさはよく知られたところ。徹底的なコンピューター化による管理と、そして日本の道路・通信インフラの優秀さによって高速かつ精密な輸送を可能にしているわけですが、これにまさるとも劣らないシステムがインドにもありました。社会的なインフラがまだまだ未整備なのにも関わらず、伝票もPOS端末も携帯電話も一切なんにも使わずに毎日20万食の昼食を時間通りに届ける「ダッバワーラー」という驚異のシステムが存在しているのです。一体どんな人達なのでしょうか。 目次 ダッバーワーラーとは ミスは1600万回に1回、驚異の低エラー率 超複雑なネットワークを人力で運営するダッバーワーラー達 なぜダッバーワーラーは超低料金で超優良サービスを提供できるのか？ ダッバーワーラーと組織の社会貢献 ダッバーワーラーとは インドの人達には、3食きちんと調理した温かい物を食べる、という食文化があります。これは
この機会にマスターしようぜ、正規表現、構文図、オートマトン - 檜山正幸のキマイラ飼育記 (はてなBlog)
正規表現と構文図について解説します。オートマトンについても詳しく述べます。オートマトン・スゴロクで遊びましょう！ 世間でよく知られている／使われている概念・方法にはこだわらず、僕（檜山）の感覚で一番わかりやすいと思われる筋書きと用語法／図式法を使って説明します。この記事に目を通して“感じ”が掴めたら、形式言語理論の教科書を読み始めることが出来るでしょう。 [追記]この記事の内容に対する具体例は、「正規表現とオートマトン：なんだ簡単じゃん、JavaScriptによる実装」にあります。[/追記] 内容： 正規表現 正規表現の例 構文図 基本記号 連接 選択 省略可能 繰り返し ストレートワイヤーによるレイアウト調整 有限状態オートマトン 有限状態オートマトンの実行 バックトラックと先読み スゴロクとオートマトン コマをたくさん使うスゴロクと並列処理 非決定性オートマトンと決定性オートマトン 正
実用的な同時並行ソートを実装する話 - akihiro4chawonの日記
scala の parallel collection は、普通の collection を使うように使っているだけで、並列計算の恩恵を受けられる場合も多いのですが、そうではない場合も多いです。 その典型例が、ソートです。実は、並列のソートは、まだ実装されていません。 じゃあ、自分で実装すればいいのか、というと、これは半分正しくて半分間違いです。 どういう事かというと、シングルスレッドの java.util.Arrays.sort がとても高速なので、これより速いソートを自前で実装するのは難しいのです。Arrays.sort が速いのは、単にアルゴリズムだけの問題ではありません。自分で Array の整列処理を書くとすると、当然、配列の要素に添字でアクセスしますよね。すると、JVMは配列の範囲内かどうかをチェックしますよね。このオーバヘッドがあるために、java.util.Arrays.s
MinHashによる高速な類似検索 - Preferred Networks Tech Blog
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
NTTデータのHadoop報告書がすごかった - 科学と非科学の迷宮
業界トップ のエンタープライズ Hadoop 企業 Cloudera に入社しました http://www.cloudera.co.jp/ 今年の6月に、「平成２１年度 産学連携ソフトウェア工学実践事業報告書」というドキュメント群が経産省から公表されました。 そのうちの一つに、NTTデータに委託されたHadoopに関する実証実験の報告書がありましたので、今更ながら読んでみることにしました。 Hadoop界隈の人はもうみんなとっくに読んでるのかもしれませんけど。 http://www.meti.go.jp/policy/mono_info_service/joho/downloadfiles/2010software_research/clou_dist_software.pdf 「高信頼クラウド実現用ソフトウェア開発（分散制御処理技術等に係るデータセンター高信頼化に向けた実証事業）」という
２ちゃんねるのログをスクリプトで処理するためのアルゴリズム
２ちゃんねる過去ログ倉庫 ２ちゃんねるのログをスクリプトで処理するためのアルゴリズム2008/05/05調査 1. スレッドが現役であるかdat落ち・削除済みであるかの判別 ～単数篇～ 下記URLにてHEAD Methodでデータを取得 http://ホスト名/板のフォルダ名/dat/スレッドキー.dat このときHTTPヘッダーの全てを取得する必要はなく、先頭12バイトのみでよい 取得した12バイトの文字列から末尾の3バイトを抽出すれば それがHTTPステータス・コードとなる 鯖からのレスポンスについては、鯖がread.soとpastdat.soを実装しているか否か User-AgentがMonazilla互換(2ch専用ブラウザ)であるか否か という二点の組み合わせによって相違する a. 鯖がread.soとpastdat.soを実装＋User-AgentがMonazilla非互換 ち
Girvan–Newman algorithm - Wikipedia
The Girvan–Newman algorithm (named after Michelle Girvan and Mark Newman) is a hierarchical method used to detect communities in complex systems.[1] The Girvan–Newman algorithm detects communities by progressively removing edges from the original network. The connected components of the remaining network are the communities. Instead of trying to construct a measure that tells us which edges are th
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
JPEG Tilt
衝突判定編
機械学習論 マルコフ連鎖、隠れマルコフモデル（１） マルコフ連鎖と 隠れマルコフモデルのBN マルコフ連鎖モデル 隠れマルコフモデル(HMM) HMMの応用分野 音声認識、情報通信、信号処 理、