The world is not yet exhausted; let me see something tomorrow which I never saw before. – Samuel Johnson In all chaos there is a cosmos, in all disorder a secret order.– Carl Jung Introduction In mathematics, difficult problems can often be simplified by performing a transformation on a data set. For example, digital signal processing programs use the FFT to convert sets of sampled audio data poin
電通大の情報理論の 韓太舜先生 の最終講義が3月にあって, スライドが ここから 見られるのを知った。 院生のときに 『情報と符号化の数理』 (岩波書店 応用数学)を読んで, その明晰な内容と込められた哲学に感動した ので, 感慨深いです。 16ページ目の内容が本当なら, Weber-Fechnerの法則が理論から導けるという ことなのだろうか.. フルテキストは1975年なので, 閲覧制限がかかっていて見れないのが残念。 他も, 全体的に非常に興味深いのですが, とりあえず最後がワラタ。(笑) 論文の準備のためにPPM,PPM*,CTWなど圧縮関係の論文を(完璧ではないと 思いますが), 色々読んでみた。 PPMについては, 北先生のところで1998年に, PPM*を使った言語モデルの話 が出ています。 さて, PPMは岡野原君が 言語モデルと 似ている という話を書いているのですが,
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 のあら
研究紹介です。今夏の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
BlockSortingは、今までのデータ圧縮で有名な方法であるLZ法とは全く違う、ユニークな操作を用 いてデータを圧縮する方法であり、M.BurrowsさんとD.J.Wheelerさんが作者なので「BWTransform」 ともいいます。 このアルゴリズムは簡単に言ってしまえば、「データをぐるぐる回してソートして出力」というも のです。簡単すぎるかもしまいませんが、本当にそうなんです。 ちなみに、このBlockSorting、単体では全く圧縮しません。ただ可逆な形にデータを変換すると いうものです。しかし、BlockSorting後のデータは非常に圧縮されやすい状態になります。例える と、色々な形をしたスポンジ（データ）が箱にごちゃごちゃに入って山積みになっているとします 。 これをそのまま上からギューっと押しつぶすのがLZ法やHuffman法なのに対し、一度、形が似た も
近年の情報化社会において、インターネット、マルチメディア、分散ソフトウェア、をはじめとするコンピュータ技術の劇的な発展と普及により、システム間の通信情報量は増大の一途をたどっています。 データ圧縮技術は「サイズを減らす（同じサイズでより多くの情報を詰め込める）」という利点から、通信効率の改善、記憶装置の有効利用、に不可欠な基礎技術です。さらに「通信データ量を減らすことでCPUへの負荷を軽減しマルチタスク処理のレスポンスを改善する」という有用性もあり、その重要性は日に日に高まっています。 データ圧縮は本来、情報理論分野での「通信システムにおける情報量 の最小化の研究」の産物である「情報源符号化法」に端を発する技術であり、この分野では、工夫を凝らした様々な問題解決手法が提案されており、アルゴリズムを学ぶ上でたいへん興味深い分野の一つです。 代表的な例として、１８世紀頃から用いられていているモー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
