Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
スパムコメント、スパムブログ対策を強化しました - はてなダイアリー日記
本日、はてなダイアリーのスパムコメント、およびスパムブログ対策を強化いたしました。詳細は以下の通りです。 ゲストコメント投稿時の確認画像を改善 コメント許可が「ゲスト」、かつ「スパムコメント・トラックバックを拒否する」設定を有効にしている場合に表示される確認画像（captcha）を改善いたしました。 この確認画像は自動投稿プログラムによるスパムコメントを防止する目的で表示しておりますが、この対策が突破されたためスパムコメントが増えている状況となっておりました。機械的に解読しにくく改善することで、これまでよりもスパムコメントが書き込まれにくくなるよう対策いたしました。 スパムコメントの自動判定機能 付けられたコメントを自動判定して、スパムと疑われるコメントを「承認待ち」状態として管理者のみが確認できる機能を追加いたしました。スパム判定されたコメントはすぐには読者の目につかず、管理画面の「コメ
pLSIを試してみた - のんびり読書日記
これまでにK-means++とfuzzy c-meansを使用したクラスタリングを試してきましたが、今回はpLSI(probabilistic latent semantic indexing, 潜在的意味インデキシング)によるクラスタリングを試してみようと思います。 pLSIは確率・統計的な枠組みで次元縮約を行う枠組みで、なかなか精度がよいらしく色々な論文で見かけます。Google NewsのレコメンドでもpLSIを使用しており、MapReduceで処理を並列化させて高速に実行しているそうです(論文読んでないので間違っているかも)。また入力ベクトルをあらかじめ重み付けしておく必要がなく、文書であれば単語の頻度をそのまま入力として使用できるのもうれしいところです。 より詳しくは以下のWikipediaのエントリか、書籍をご参照下さい。(書籍は処理結果の表8.4が並びがグチャグチャになってる
APR素数判定 - 落書き、時々落学
多分当っている． コード長いです． Miller Rabin はやはり非常にシンプル． それに比べ，APRは… まぁ，実装がヘタなんだよと，言われればそれまでだが． しかし，綺麗なコードがあれば見てみたいが，すくなくとも簡単にはwebでは見つからなかった． 100桁とかの素数判定を10分とか20分あれば，やってくれると思います（計算機のパワーに依存）． ちなみに，10^123の次の素数を求めるのに約3分＠Desktop PC． module APR where import Data.List (sort, genericTake, genericSplitAt, genericReplicate) import Data.Array.IArray (Array, array, (!)) import Modulo (powMod, primitiveRoots, congruence)
数列データベース：On-Line Encyclopedia of Integer Sequences - 発声練習
みなさん、あるアルゴリズムの計算量の上限値や下限値を考えているときに自分で数列の一般式を求めることありませんか？そんなあなたにJohn H. Conway and Richard K. Guy著, 根上 生也訳：数の本に紹介されていました、数列データベースをご紹介いたします。 On-Line Encyclopedia of Integer Sequences この数列データベースはキーワードや数列を検索キーとして登録されているデータベースの中から検索をしてくれます。 例えば、深さnのラベルなし二分木の種類数は、`1, 3, 21, 651, 457653'という数列になります。これを検索キーとして検索すると以下のような検索結果がでます。 Number of binary trees of height n; or products (ways to insert parentheses)
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
Burrows-Wheeler変換の線形時間アルゴリズム - DO++
研究紹介です。今夏のSPIRE 2009という学会で "A Linear-Time Burrows-Wheeler Transform using Induced Sorting", D. Okanohara, K. Sadakane, SPIRE 2009 pdf(draft) というのを発表します。これは与えられた文字列に対し接尾辞配列を経ないでBurrows-Wheeler変換を直接行うというもので、アルファベットサイズによらず入力長に対して線形時間で行えます。基本的なアイディアは昨年のInduced Sortingによる接尾辞配列の線形時間構築アルゴリズム（いわゆるSAIS）を接尾辞配列を使わないでシミュレートするものです。pushとpop操作だけからなり、そのまま外部記憶上での構築とかにも対応できるようになっています。 Burrows-Wheeler変換（BWT, Block S
ダイクストラ法 - Bug's Groove
前回のアルゴリズムイントロダクション輪講の話題、単一始点最短路問題から。詳しくは アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー へ。その中で丁度前回 書いたプリム法と同じく、ダイクストラ法が最小優先度付きキューを使うので、ちょっといじったらかけるのでは？と思って書いてみました。(相変わらずの乱プログラムご容赦...)。対象のグラフは教科書通り。 実装的には、minheap クラスは前回のプリム法と全く一緒。MinPriorityQueue は前回と使い方が違うので一部実装し直し。(といっても relax の周り)。実行するとこんな感じになるはずです。 s -> y -> t (8) s -> y -> t -> x (9) s -> y (5) s -> y -> z (7) 教科書のヒープソート (6章) にもあったように、優先度付きキュー
適切なクラスタ数を推定するX-means法 - kaisehのブログ
K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。 これに対して、X-means法というK-means法の拡張が提案されていることを知りました。X-means法を使うと、データに応じて最適なクラスタ数を推定できます。 K-means and X-means implementations http://www-2.cs.cmu.edu/~dpelleg/download/xmeans.pdf X-means法の考え方は、K=2で再帰的にK-means法を実行していくというもので、クラスタの分割前と分割後でBIC（ベイズ情報量規準）を比較し、値が改善しなくなるまで分割を続けます。 調べたところ、Javaのデータマイニングツー
アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー
アルゴリズムイントロダクションの輪講で、第24章の単一始点最短路問題を担当しました。発表に使った資料を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/090622_shortest_paths.ppt SlideShare はこちら。フォントの関係でグラフが崩れたりしているので、ppt で参照した方が見やすいかと思います。 Introduction to Algorithms#24 Shortest-Paths ProblemView more OpenOffice presentations from Naoya Ito. 単一始点最短路問題は、重み付き有向グラフの最短路木を求める問題です。各頂点に最短路重みを記録するのですが、はじめに各頂点の重みを∞として、「緩和」と呼ばれる操作により徐々に頂点の重みを最短路重みに近づけていく、というの
Erlang による Skip Graph の実装 - kyeeva blog!
参考： Skip Graph の論文 http://www.cs.yale.edu/homes/aspnes/skip-graphs-journal.pdf ソースコードはこちら Skip Graph in Erlang · GitHub 特徴 ・Erlangによる完全なSkip Graphの実装 ・複数マシンを利用してスケールアウト可能 ・boot/4関数内のLevel_Maxの値を大きくすることにより、Levelの階層を増やすことができる ＝＞ スケールアウトしてエントリ数が増えても、検索効率が落ちない ・keyにatomを指定することもできるので、柔軟な範囲検索を行うことができる ・コードの行数は200行未満 実際の動作（Erlangを知っている人向け） 起動(分散) <ノードjohn@asus> $ erl -sname john Eshell V5.7 (abort with ^
アルゴリズムと計算量
金庫破りと計算量膨張 n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 〜 99 の 100 個の正解があるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。 99 が正解とは限らないので、平均的にはこれより早く解き終わります。 0 であるときの確率は 1/100 で、このときの手数は 1 手です。 1 であるときの確率は 1/100 で、このときの手数は 2 手です。 2 であるときの確率は 1/100 で、このときの手数は 3 手です。 3 であるときの確率は 1/100 で、このときの手数は 4 手です。 : 99 であるときの確率は 1/100 で、このときの手数は 100 手です。 つまり、平均手数は により、100 手目の約半分です。 ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計
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 のあら
PHP で Google 第一回 Google の PageRank を PHP で実装 - 横転プログラミング
Google の検索エンジンがページのランク付けのために PageRank という指標を使っているというのは聞いたことがあるかと思います。 今日はそのアルゴリズムを PHP で軽めに実装してみました。 ちなみに PHP で実装しても何もいいことがないので、やめたほうがいいでしょう。 まず PageRank というのは簡単に説明すると、 Google が考案したページのランク付けアルゴリズムでページへリンクがそのサイトの評価だという視点でランク付けを行うために作られたものです。 詳細については Google の秘密 - PageRank 徹底解説 を参考にしてみて下さい。 その内部アルゴリムですが、おおざっぱにいえば下の箇条書きにあるよう生成された確率行列の、最大固有値（確率行列はだいたいの場合において1）の固有ベクトルをべき乗法で求めることになります。 なぜ確率行列の主固有ベクトルを求める
【文献調査】BFGSの基礎
【文献調査】BFGSの基礎 細江 則彰, 廣安 知之, 三木 光範 ISDL Report No. 20060807008 2006年 9月 20日 Abstract 本報告は，連続最適化問題かつ非線形計画問題に適用できる，準ニュートン法の代表的な手法であるBFGS法について文献調査を行う．BFGS法は，Broyden，Fletcher，Goldfarb，Shanno の4人によって発表された手法であり，ニュートン法の問題点である「Hesse行列の計算に多くの計算量が必要」を解決するアルゴリズムである． 1 はじめに 本報告では，準ニュートン法の代表的な手法であるBFGS法について文献調査を行う．BFGS法は，Broyden，Fletcher，Goldfarb，Shanno の4人によって発表された手法であり，ニュートン法の問題点である「Hesse行列の計算に多くの計算量が必要」を解
SPIRE 2009 ACCEPTED PAPERS
========================== SPIRE 2009/ACCEPTED PAPERS ========================== 22 LONG PAPERS: 68. Travis Gagie, Simon Puglisi and Andrew Turpin. Range Quantile Queries: Another Virtue of Wavelet Trees 54. Shanu Sushmita, Hideo Joho and Mounia Lalmas. A Task-Based Evaluation of an Aggregated Search Interface 75. Wing Kai Hon, Rahul Shah and Shih Bin Wu. Efficient Index for Retrieving Top-$k$
Hidetoshi Yokoo's Home Page
横 尾 英 俊 English / Japanese 氏名: 横尾 英俊 (よこお ひでとし) 所属: 群馬大学大学院 工学研究科 情報工学専攻 住所: 376-8515 桐生市天神町 1-5-1 電話: 0277-30-1805 (直通) Fax: 0277-30-1801 Office: ２号館 ３階 ３０２−１号室 研究分野 データ圧縮 とその応用 講義科目 : 情報理論，数値解析など 講義（学部）関係の情報 著書紹介 LaTeX ユーザのためのレポート・論文作成入門 （共立出版 刊） Links 当研究室のホームページ 情報工学科ホームページ 群馬大学工学部ホームページ 群馬大学ホームページ 国立大学法人等 文部科学省 横尾英俊 ／ yokoo@cs.gunma-u.ac.jp
クラスカルのアルゴリズム - naoyaのはてなダイアリー
昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
講座 情報幾何とその応用-I : 情報幾何とは何か-入門編 | CiNii Research
Large-scale graph computing at Google
