Canonical Huffman Codes - naoyaのはてなダイアリー
1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。 ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率が分かっているときに、その各シンボルに最適な符号長の接頭語符号を求めるものです。 通常のハフマン符号はポインタで結ばれたハフマン木を構築して、ツリーを辿りながら各シンボルに対する接頭語符号を計算します。このハフマン木には曖昧な箇所が残されています。ハフマン木は木の辺を右に辿るか左に辿るかで符号のビットが決まりますが、右が 0 で左が 1 などというのはどちらでも良いという点です。(曖昧だから駄目、という話ではありません。) 従って、ハフマン木から生成される符号は一意には決まりません。 ここで各シンボル
北海道を落とすとどう跳ねるのか？の裏側 - てっく煮ブログ
asおかげさまで大好評の 北海道を落とすとどう跳ねるのか？ ですが、どのように作ったか、製作過程を紹介することにします。1. 地図の素材を取ってくるまずは地図の素材が必要です。以下のサイトから拝借しました。白地図、世界地図、日本地図が無料pdf や eps 形式の地図データを無料で配布してくれているありがたいサイトです。2. 都道府県ごとに分割する上記の素材は県境もベクター形式で提供されていて大変ありがたかったのですが、島がどの都道府県に属しているかの情報がありませんでした。そこで、Google Maps と見比べながら、島を都道府県ごとに分類していきました。無事、全ての島を分類し終わって、こんな感じになりました。とても地味な作業でした…。3. 都道府県ごとに SVG で出力する次に、Illustrator 内で分類したデータをプログラムで扱える形式にしなければなりません。ここでは XML
各種マップ実装の性能比較 - mixi engineer blog
今回は小ネタのmikioです。key/valueのレコードを高速に格納・参照・削除する仕組みが連想配列とかマップとか呼ばれて親しまれていますが、Tokyo Cabinetのオンメモリマップの性能をC++の各種実装と比較してみました。 以下の実装を対象として、100万レコードの格納と検索にかかる時間を計測します。キーと値は各8バイトの文字列とします。 Tokyo Cabientのオンメモリマップ（TCMAP） STL（C++の標準テンプレートライブラリ）のmapとmulti mapとset GNU拡張テンプレートのハッシュマップ Googleのdense hashおよびsparse hash テストコードはこちらに挙げておきます。具体的な操作としては、マップオブジェクトを生成し、バケット配列の要素数をレコード数と同じにチューニングし、ループを回してレコード群を格納します。なお、STLのマップ
自然言語処理における半教師あり学習のテキスト - 武蔵野日記
最近移動続きであまり研究に時間は割けないのだが、本は読めるということで本を2冊、サーベイ的な記事を3本(うち2本はチュートリアルスライドつき)を紹介する。まず Semisupervised Learning for Computational Linguistics (Chapman & Hall/CRC Computer Science & Data Analysis) 作者: Steven Abney出版社/メーカー: Chapman and Hall/CRC発売日: 2007/09/17メディア: ハードカバーこの商品を含むブログ (4件) を見る を読む。この本の著者の Steven Abney はブートストラッピングの理論的解析をした人で、 Steven Abney. Bootstrapping. 40th Annual Meeting of the Association fo
シムシティーの仕組み
シムシティーを作り始めていちばん最初に考えたのは、街を一種の生き物のように表現できないかってことだった。 僕が街についてどう考えているかはすでに説明したけど、大事なのは街を構成する建物とか道路じゃなくって、そこでどんな活動が行なわれているかってことだと思うんだ。道路を車が走り、電車が動き、人々が動き回り、常に要素が変化し続ける“動きのある”システム。街を表現する方法っていうと誰でも地図を思い浮かべると思うけど、僕は動きがない地図じゃなくって、たとえば飛行機から眺めた街、動きのある世界をディスプレイに表現しようって考えた。それこそが僕の考える街の姿だからね。 それともう一つ考えたことは、プレイヤーに伝える情報をできるだけわかりやすく、それも“面白い”って思えるような形で表現しようってことだった。シミュレーション・ソフトっていうとたいてい数値や図表がたくさん出てくるけれど、数字が並んでいるのを
はてなブックマークFirefox拡張, JavaScript で IS 法 による Suffix Array 構築 - naoyaのはてなダイアリー
昨日、はてなブックマークFirefox拡張をリリースしました。おかげさまでベータ版からダウンロード数は累積で1万ダウンロードを突破し、アクティブユーザー数も伸びています。 はてなブックマークFirefox拡張で新しいインターネットを体験しよう http://b.hatena.ne.jp/guide/firefox_addon 開発者の id:secondlife が g:subtech:id:secondlife:20090415:1239804170 で技術的な側面からのちょっとした TIPS なども紹介していますので、興味のある方はご一読ください。 検索では思いのほか SQLite の like 検索が高速なのに驚いた。はてブ検索では、検索ワードから URL, Title, コメント にマッチしたものを表示していて、それ専用の search_data だかかんらかの検索用カラムがある。
オンラインEMアルゴリズム - DO++
EMアルゴリズム（Expectation Maximizationアルゴリズム、期待値最大化法、以下EMと呼ぶ）は、データに観測できない隠れ変数（潜在変数）がある場合のパラメータ推定を行う時に有用な手法である。 EMは何それという人のために簡単な説明を下の方に書いたので読んでみてください。 EMのきちんとした説明なら持橋さんによる解説「自然言語処理のための変分ベイズ法」や「計算統計 I―確率計算の新しい手法 統計科学のフロンティア 11」が丁寧でわかりやすい。 EMは教師無学習では中心的な手法であり、何か観測できない変数を含めた確率モデルを作ってその確率モデルの尤度を最大化するという枠組みで、観測できなかった変数はなんだったのかを推定する場合に用いられる。 例えば自然言語処理に限っていえば文書や単語クラスタリングから、文法推定、形態素解析、機械翻訳における単語アライメントなどで使われる。
mixi Engineers’ Blog » 圧縮データベースを使おう
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
MapReduce on Tyrant - mixi engineer blog
先日、隅田川の屋形船で花見と洒落込んだのですが、その日はまだ一分咲きも行ってなくて悲しい思いをしたmikioです。今回はTokyo Tyrant（TT）に格納したデータを対象としてMapReduceのモデルに基づく計算をする方法について述べます。 MapReduceとは Googleが使っているという分散処理の計算モデルおよびその実装のことだそうですが、詳しいことはググってください。Googleによる出自の論文やApacheプロジェクトによるHadoopなどのオープンソース実装にあたるのもよいでしょう（私は両者とも詳しく見ていませんが）。 今回の趣旨は、CouchDBがMapReduceと称してJavaScriptで実現しているデータ集計方法をTTとTCとLuaでやってみようじゃないかということです。簡単に言えば、以下の処理を実装します。 ユーザから計算開始が指示されると、TTは、DB内の
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
多Byte文字コードの圧縮 - シリコンの谷のゾンビ
ひょんなことから気になって調べてみたので結果を記録． Shift-JISやEUC-JPは日本語を2Byteで表現する．同じテキストをShift-JISで表現しようが，EUC-JPで表現しようがサイズは同じになる． けれど，多バイト文字コードのことなんて考えないASCIIな世界の人たちがLZ法のような辞書式アルゴリズムを実装した場合，1バイト単位で処理するから文字コードの差が出るのではないかとふと思った． そういうときは論よりRun． 同じテキストを異なる文字コードで表現した際の圧縮サイズを比較してみた． 対象テキストは，みんな大好き夏目漱石「こころ」 圧縮アルゴリズムはgzip (LZ77+Huffman) --bestオプション付き 元サイズ kokoro.txt.sjis 368051 byte kokoro.txt.euc 368051 byte 当然同じ． 圧縮後 kokoro.t
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー
昨日は第11回 Kansai.pm でした。 今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。 PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資料) は圧巻でした。伊奈さんの本文抽出の話 (発表資料)、はこべさんのコルーチンの話 (発表資料)、いずれも難解になりがちなところを凄く分かりやすく解説されていて、さすがだなと思いました。各々ショートトークも、いずれも良かったです。 スペルミス修正プログラムを作ろう 自分も 20 分ほど時間をいただいて、スペルミス修正プログラムの作り方について発表しました。 スペルミス修正プログラムを作ろうView more presentations from Naoya Ito. スペルミス修正プログラムについてはずばり スペル
ダイクストラ法, 貪欲アルゴリズム - naoyaのはてなダイアリー
現実逃避をしながらウェブを眺めていたら ダイクストラ法（最短経路問題） にたどり着きました。単一始点最短路問題におけるダイクストラ法の解説です。 何を思ったのか、図を眺めていたところ動かしたい衝動に駆られて、気付いたらパワポでアニメーションができていました。 http://bloghackers.net/~naoya/ppt/090319dijkstra_algorithm.ppt 実装もしてみました。隣接ノードの表現は、ここではリストを使いました。 #!/usr/bin/env perl use strict; use warnings; package Node; use base qw/Class::Accessor::Lvalue::Fast/; __PACKAGE__->mk_accessors(qw/id done cost edges_to prev/); package Q
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
