私のブックマーク 簡潔データ構造 田部井靖生(科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員) はじめに 近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、 しかし、圧縮するとランダムアクセスをすることができないという欠点があります。 簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。 近年、集合、文字列、木、グラフデータを扱うための簡潔データ構造が提案され注目を集めています。 私たちの身近なアプリケーションとして、Google日本語入力では簡潔木LOUDSの実装が使われ、実際に使われはじめています。 また、有志によるそれらを解説したサイトやライブラリなども利用可能になりつつあります。 そこで、このページでは簡潔データ構造を用いた研究開発のためのいろい
Copyright © 2004-2008, Yuta Mori, All Rights Reserved. yiv01157 at nifty dot com http://homepage3.nifty.com/wpage/
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
矢田 晋 Abstract: libbzip2 は bzip2 で採用されている圧縮アルゴリズムのライブラリです.Burrows-Wheeler Transform (BWT) を用いることが特徴の一つであり,gzip と比較すると,圧縮・伸長には時間がかかるものの,優れた圧縮率を示すことが多くなります.本記事は,C 言語から libbzip2 を利用する方法の解説になっています. はじめに libbzip2 のマニュアルは公式サイトで提供されています. http://www.bzip.org/(bzip2 : Home) bzip2, libbzip2 の公式サイトです.ソースコードとマニュアルがあります. libbzip2 では,bz_stream という構造体を用いる低水準インタフェースと,BZFILE という型を用いる高水準インタフェースが用意されています.低水準インタフェースはメ
,. -‐'''''""¨¨¨ヽ (.___,,,... -ァァフ| あ…ありのまま 今日 起こった事を話すぜ! |i i| }! }} //| |l、{ j} /,,ィ//| 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ、_ノ/ u {:}//ヘ |リ u' } ,ノ _,!V,ハ | /´fト、_{ル{,ィ'eラ , タ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽトiゝ おれも何をされたのかわからなかった… ,゙ / )ヽ iLレ u' | | ヾlトハ〉 |/_/ ハ !ニ⊇ '/:} V:::::ヽ 頭がどうにかなりそうだった… // 二二二7'T'' /u' __ /:::::::/`ヽ /'
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く