Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
BWT と PPM - naoyaのはてなダイアリー
Burrows Wheeler Transform (BWT, Block-sorting) と Prediction by partial matching (PPM) は本質的に同じ事をやっている、というお話です。 先日 Managing Gigabytes を読んでいたところ、P.69 で "block sorting is very closely related to the PPM* method, which is a variant of PPM that allows arbitrary-length contexts." という記述があり、どうにも気になったので調べてみました。 サマリとしては、BWT と PPM の一種である PPM* はいずれも文脈から次の1文字を一意に決定するという概念で見ると本質的に同じことをやっていると言える、というところです。 BWT のあら
PFIセミナー資料: 研究開発2009 - DO++
昨日ありました、PFIでのセミナーでの発表資料です。 研究開発のチームの紹介の後に、2009年サーベイした論文の中で面白かった論文を 機械学習、データ構造、画像処理で紹介してます 紹介した話は - Multi-class CW (Multi-class Confidence Weighted Learning,) - AROW (Adaptive Regularization Of Weight Vector) - Online-EM algorithm - 全備簡潔木 (Fully-functional Succinct Tree) - 圧縮連想配列 (compressed function) - PatchMatch です。 ＃資料中の簡潔木の表現方法のDFUDSの紹介でtxも使用と書いてあるのは、公開しているtxでは、 LOUDSのみをつかっていますので正確ではありませんでした。これ
機密データを安心してクラウドに預けられる暗号方式
米IBMの研究員クレイグ・ジェントリー氏が、暗号分野の数十年来の難問を解決した。専門家によると、このブレークスルーがクラウドコンピューティングにもたらす影響は極めて大きい。 ジェントリー氏は、「完全準同型暗号（fully homomorphic encryption）」を実現する方法を考案した。この方法は、暗号を復号したり、その機密性を損なったりすることなく、暗号化されたデータに対する複雑な数学的演算を可能にする。ただし、この方法には難点もある。膨大なコンピューティングパワーが必要なことだ。場合によっては現在の1兆倍ものレベルが必要になると推計されている。 ジェントリー氏の研究成果がうまく実用化されれば、例えば防衛関連業者や医薬品研究施設などが、セキュリティや規制コンプライアンスに不備が生じることを心配せずに、機密データを外部に送信して分析を受けるといったことが可能になる。現在はこうしたデ
天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
Post by @shyouhei
とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
GT Nitro: カーレーシング・ドラッグレーシングゲーム - Google Play のアプリ
GT Nitro: Car Game Drag Raceは、典型的なカーゲームではありません。これはスピード、パワー、スキル全開のカーレースゲームです。ブレーキは忘れて、これはドラッグレース、ベイビー！古典的なクラシックから未来的なビーストまで、最もクールで速い車とカーレースできます。スティックシフトをマスターし、ニトロを賢く使って競争を打ち破る必要があります。このカーレースゲームはそのリアルな物理学と素晴らしいグラフィックスであなたの心を爆発させます。これまでプレイしたことのないようなものです。 GT Nitroは、リフレックスとタイミングを試すカーレースゲームです。正しい瞬間にギアをシフトし、ガスを思い切り踏む必要があります。また、大物たちと競いつつ、車のチューニングとアップグレードも行わなければなりません。世界中で最高のドライバーと車とカーレースに挑むことになり、ドラッグレースの王冠
Introduction to Information Retrieval #18 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 輪読会 18章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_18.ppt 18章のテーマは "Matrix decompositions and latent semantic indexing" で、行列の特異値分解と Latent semantic indexing (LSI, 潜在的意味インデキシング) でした。ベクトル空間モデルの核である単語文書行列を特異値分解を用いて低階数近似し、計算量を下げながらも*1適合度を向上させるという LSI についての解説の章です。LSI に関しては http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing にて先日少し言及しました
HITS, 主成分分析, SVD - naoyaのはてなダイアリー
ウェブグラフのリンク解析によるページの評価と言えば PageRank が著名ですが、もうひとつ Jon Kleinberg による HITS (Hyperlink-induced topic search)も有名です。最初の論文 Authoritative Sources in a Hyperlinked Environment は 1999年です。IIR の 21章で、この PageRank と HITS についての解説がありました。 HITS HITS はウェブページの評価に二つの軸を用います。一つが authority スコア、もう一つが hub スコアです。 例えば「Perl の情報が欲しい」という検索要求に対しては CPAN や 開発者である Larry Wall のホームページなどが重要度の高いページかと思います。これらのページは「Perl に関して信頼できる情報源」ということ
潜在的意味インデキシング - download_takeshi’s diary
id:naoyaさんやたつをさんなどの超有名人な方々が以前から実施されている「IIR輪読会」というものがありまして、どうやら今回は第18章の "Matrix decompositions and latent semantic indexing"を輪読したようです。 http://d.hatena.ne.jp/naoya/20090208 http://chalow.net/2009-02-08-2.html Latent Semantic Indexingとは、通称LSIとかLSA（Latent Semantic Analysis）とかいいますが、日本語だと「潜在的意味インデキシング」なんて呼びますね。 簡単に言ってみると でっかいマトリックス（数万×数万とかの行列）をたとえば「数百×数万」ぐらいにまで、ぎゅぎゅっと横に押しつぶすように圧縮してみると、あら不思議、のこった行列はとても意味
C++TMPを使ってコンパイル時に多倍長フィボナッチ計算。 - 簡潔なQ
C++テンプレートメタプログラミング、つまりC++のテンプレート機能を使うと、静的に決定できる計算をコンパイル時にやってのけることができる。 あまりにすごすぎたのでフィボナッチ計算のプログラムを作ったのだが、unsigned long long intではすぐ桁あふれしてしまうので、テンプレート多倍長を組んでフィボナッチ計算。 ただし、FFT多倍長乗算とかまで実装する余裕はないので、行列を使った累乗の方法ではなく、普通の加算による線形時間計算の方法を使った。 今回はfib(700)を求めた。コンパイルには5分ほどかかった。 #include <iostream> using namespace std; namespace TMP { template<bool expr, typename IfTrue, typename IfFalse> struct select { typedef
Introduction to Information Retrieval #16 の復習資料 - naoyaのはてなダイアリー
しばらく間が空いてしまいました。Introduction to Information Retrieval 輪読会 16章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_16.ppt 16章のテーマは、"Flat Clustering" で話題はクラス分類からクラスタリングへと移ります。16章ではクラスタとクラスタの間に関係性がないフラットクラスタリングを扱い、続く 17章ではクラスタ間に階層的構造を見出す階層型クラスタリング (Hierachical clustering) を扱います。 クラスタリング 13章から15章までは Naive Bayes や SVM などによる "Classification" が話の主題でした。クラスタリングも同様に情報のグルーピングを行うものですが、Classification
Introduction to Information Retrieval #17 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 輪読会 17章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_17.ppt 17章のテーマは "Hierarchical clustering" で、前回 16 章の非階層型クラスタリングに続き、階層型クラスタリングの話です。 階層型クラスタリング 階層型クラスタリングはその名の通り、階層構造を伴ったクラスタリングの手法です。例えば「はてなダイアリー」に関するクラスタと、「はてなブックマーク」に関するクラスタは、二つが合わさって上位に「はてな」というクラスタを形成し、更に上位に「ウェブサービス」というクラスタを形成するかもしれません。こうして階層構造はデンドログラムと呼ばれる二分木を構成します。 ウェブサービス -+- はてな -+- は
第 7 回アルゴリズムイントロダクション輪講会資料: Days on the Moon
すでにニュースでも伝えられている通り、12 月 1 日に第 7 回アルゴリズムイントロダクション輪講会がありました。今回の担当は私だったので、その発表資料を公開します。 中央値と順序統計量 (その 1) 予定 順序統計量とは 選択問題とは 最小値と最大値 平均線形時間選択アルゴリズム 中央値と順序統計量 (その 2) 最悪線形時間選択アルゴリズム 3 つずつのグループに分割した場合 7 つずつのグループに分割した場合 参考文献 中央値と順序統計量 (補足) 4 つずつのグループに分割した場合 6 つずつのグループに分割した場合 Lazy-Select Randomized-Partition スタッフロール 「どうせ後から Web で公開するんだから、PDF とか見るのに手間がかかるものは使ってられないよね。やっぱ時代は XML 複合文書でしょ!」と、数式を表現するのに MathML を使
Wavelet Tree - naoyaのはてなダイアリー
圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
2log.net