推薦状のルール
私が書く米欧の大学院向けの推薦状について 林 文夫 2004年9月14日 (revised September 21, 2004; October 22, 2004) 毎年秋になると，米欧の大学院留学志望の学生や社会人から，推薦状を依頼されます。John Nash の指導教官は，「この学生は天才である」という推薦状を書いたそうですが，そこまで極端でなくとも，「今まで指導した学生の中で一番」という推薦状を私に書かせるのが神から与えられた権利だと，多数の学生が信じているようですが，大きな誤解です。私は Northwestern大学，Pennsylvania大学，Columbia大学で，大学院入学委員会（Graduate Admission Committee）の委員や委員長を勤めたことがあるので断言できますが，私の強い推薦状により入学した学生がカスだとわかれば，私の推薦状はそれ以降一切信用され
接尾辞配列(Suffix Array) - Shogo Computing Laboratory
接尾辞配列(Suffix Array)は，全文検索などに用いられるデータ構造です． それ以外にも，単語の出現回数を高速に求められたり， データ圧縮に使えたりなど，様々な応用例が提案されています． 2012年現在，SA-ISと呼ばれる手法がもっとも効率的に Suffix Array を求められるようです． その基礎となる考え方を１つずつ見ていくことにしましょう． Suffix Arrayとは Suffix Array とはどんなものなのでしょう？ 定義にそった，もっとも簡単なアルゴリズムを紹介します． バケットソート 基数ソートとバケットソートは，ソートする対象の種類が有限で範囲がはっきりしている場合に 非常に有効なソート手法です． これを使って Suffix Array を求めてみます． 2段階ソート 隣り合った接尾辞の比較は非常に簡単にできます． ことのことを利用してソートを高速化します
Suffix Array 構築方法の紹介
The document introduces two algorithms for constructing a suffix array: SA-IS and SA-DS. SA-IS uses induced sorting of longest common prefix substrings, while SA-DS uses radix sorting of fixed-length substrings. The document provides pseudocode for the algorithms and explains various terms and data structures used, including longest minimal suffixes, L-type and S-type characters, and buckets for s
昨年の論文をふりかえる - DO++
新年すっかりあけてました。 今年もよろしくお願いします。 年末年始はドタバタして昨年を振り返られなかったのですが、せっかくなので2008年に読んだ論文で私個人のベスト５を以下に列挙してみます。 D. Sontag, et. al. "Tightening LP Relaxations for MAP using Message Passing", UAI 2008 [pdf] Graphical ModelのMAP推定問題で従来解けなかった規模の複雑さの問題を高速にしかも最大であるという保障付きで解けるようにした。書いたメンバーはこの問題に関するオールスターのような感じ。解く問題は、n個の頂点からなるグラフで、各頂点には変数x1...xnがついていて、各頂点と各枝に対し関数gi(xi)、gij(xi,xj)が与えられた時、∑i gi(xi) + ∑ij gij(xi,xj)が最大となるよう
BWTとInduced Sorting - 気ままなブログ
BWT(Burrows Wheeler Transform)を行うプログラムをJavaで書いてみた。一応、Unicodeのサロゲートペアの範囲でも問題なく動くので、あらゆる言語に適応できる。 BWTは、Suffix Arrayから定義に従って構築している。なので、実質的なメモリ使用量や構築時間は、Suffix Arrayのメモリ使用量や構築時間に依存する。 Suffix Arrayの構築にInduced Sortingを使ってみた。参考にしたものを以下に示します。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 14人 クリック: 314回この商品を含むブログ (3件) を見る 原文: http://www.cs.sysu.edu.cn/nong/i
Suffix Array を作る - SA-IS の実装
Suffix Array は今若者の間で人気のデータ構造です． マイ suffix array を実装することで，オシャレ度がアップしてモテ系になり，女子力も上がると言われています． その中でも今特に，手軽でクールな SA-IS (アルファベットサイズ固定の下で線形時間で省メモリで suffix array が作れる今最強のアルゴリズム) の実装がブームです． 僕もブームに便乗して，実装してみました． ところで，SA-IS は流行っているので，日本語でもすでに様々なところで記事が書かれています (日付順)． SAIS(Suffix Array - Induced Sorting) - EchizenBlog-Zwei SA-IS: SuffixArray線形構築 - sileの日記 SA-IS - (iwi) ｛ 反省します - TopCoder部 接尾辞配列(Suffix Array)の
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
Suffix Array(接尾辞配列)を学びたい人のためのリンク集 - EchizenBlog-Zwei
私がCompressed Suffix Arrayを学ぶのに参考にした資料へのリンクをまとめてみた。 CSAだけじゃなく、これからSuffix Arrayを学ぶ人にも便利かもしれない。 解説記事 # ［を］ Perl による Suffix Array の実装] SUFARYの開発者、たつを氏による解説 perlで20行くらいでSuffix Arrayが作れる 入門用におすすめ # DO/Suffix Array 岡野原氏によるSuffix Arrayの解説記事 高速化などの高度な話題が豊富 中級者向け # white page Suffix Arrayのリンク集が充実 多くのライブラリが公開されている ツール・ライブラリ # SUFARY 臨時復旧ページ たつを氏によるSuffix Arrayライブラリ 非常に使い勝手が良い # sary: Suffix Arrayのライブラリとツール 高
Vol.26 No.6 (2011/11) 簡潔データ構造 – 人工知能学会 (The Japanese Society for Artificial Intelligence)
私のブックマーク 簡潔データ構造 田部井靖生（科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員) はじめに 近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、 しかし、圧縮するとランダムアクセスをすることができないという欠点があります。 簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。 近年、集合、文字列、木、グラフデータを扱うための簡潔データ構造が提案され注目を集めています。 私たちの身近なアプリケーションとして、Google日本語入力では簡潔木LOUDSの実装が使われ、実際に使われはじめています。 また、有志によるそれらを解説したサイトやライブラリなども利用可能になりつつあります。 そこで、このページでは簡潔データ構造を用いた研究開発のためのいろい
white page / 全文検索や圧縮に関するlinks集
Copyright © 2004-2008, Yuta Mori, All Rights Reserved. yiv01157 at nifty dot com http://homepage3.nifty.com/wpage/
PowerPoint Presentation
2006/07/05 Succinct Data Structure hillbig@is.s.u-tokyo.ac.jp z z z z z z zSuccinct Data Structure (SDS) z SDS z SDS z SDS zSDS zSuffix Arrays Burrow Wheelers zFM-index, Compressed Suffix Arrays z z zSuccinct Data Structure (SDS) z SDS z SDS z SDS zSDS zSuffix Arrays Burrow Wheelers zFM-index, Compressed Suffix Arrays z (1/2) z : word RAM z n log n z n 232 64 64bit z z D L L = log(D ) z D z n T L
libbzip2 の使い方
矢田 晋 Abstract: libbzip2 は bzip2 で採用されている圧縮アルゴリズムのライブラリです．Burrows-Wheeler Transform (BWT) を用いることが特徴の一つであり，gzip と比較すると，圧縮・伸長には時間がかかるものの，優れた圧縮率を示すことが多くなります．本記事は，C 言語から libbzip2 を利用する方法の解説になっています． はじめに libbzip2 のマニュアルは公式サイトで提供されています． http://www.bzip.org/（bzip2 : Home） bzip2, libbzip2 の公式サイトです．ソースコードとマニュアルがあります． libbzip2 では，bz_stream という構造体を用いる低水準インタフェースと，BZFILE という型を用いる高水準インタフェースが用意されています．低水準インタフェースはメ
2008-10-16
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
Linux Performance Analysis and Tools
Video: http://joyent.com/blog/linux-performance-analysis-and-tools-brendan-gregg-s-talk-at-scale-11x ; This talk for SCaLE11x covers system performance analysis methodologies and the Linux tools to support them, so that you can get the most out of your systems and solve performance issues quickly. This includes a wide variety of tools, including basics like top(1), advanced tools like perf, and ne
原因調査用Linuxコマンド | 外道父の匠
サーバの動作に異常が発生した際に原因を探るためのLinuxコマンドで、自分用のメモです。 全てmanとかググったら出てくるので説明は適当です。思いついたら後で追記していくかもです。 対象はDebian Squeezeになります。 全てパッケージインストールできるもので、パッケージ名は [in packagename] としてあります。 各所よりコメントありがとうございます。 良さ気なコマンドは追記していきます。 ＜追加したコマンド＞ * telnet (+コメント wget, netcat) * arp (+コメント arpwatch) * pstree * fdisk コメントに gdisk * host, dig * watch * reboot
Hadoop MapReduceで行列積を計算する（ケース２）（Dense Matrix Multiplication with Hadoop MapReduce: Case2) - tetsuya_odakaの日記
前回のログでは、Case1として行列積の演算プログラムを示した。 しかしながら、5000行5000列の行列同士の演算に6時間以上の時間がかかってしまい、これでは「ビッグデータ」の探索的な分析では使えないだろう。 これまで、再三引用している「エコノミスト誌（6/4号）」の分析では、変量の数は300であり、サンプルサイズは51であった（これについては、以前のログで述べた）から、オーダーとしては、Case1のプログラムでも間に合う可能性がある。 しかしながら、同誌に掲載されている「Yahoo! JAPAN 景気指数」では60万語（60万変量）と、CIとの相関を調べている。 Case2では、Case1のプログラムを改良することにより、実行速度の向上をはかる。 Case1のスケーラビリティー評価のところでも述べたが、Case1の実行時間は「単純な算術演算の回数の増加」では説明できない。 MapRed
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Parallel Programming: First Electronic Edition
https://xxxxxeeeee.hatenablog.com/entry/20110810/1312996441
Google Sites: Sign-in
サービス終了のお知らせ