BlockSorting
BlockSortingは、今までのデータ圧縮で有名な方法であるLZ法とは全く違う、ユニークな操作を用 いてデータを圧縮する方法であり、M.BurrowsさんとD.J.Wheelerさんが作者なので「BWTransform」 ともいいます。 このアルゴリズムは簡単に言ってしまえば、「データをぐるぐる回してソートして出力」というも のです。簡単すぎるかもしまいませんが、本当にそうなんです。 ちなみに、このBlockSorting、単体では全く圧縮しません。ただ可逆な形にデータを変換すると いうものです。しかし、BlockSorting後のデータは非常に圧縮されやすい状態になります。例える と、色々な形をしたスポンジ（データ）が箱にごちゃごちゃに入って山積みになっているとします 。 これをそのまま上からギューっと押しつぶすのがLZ法やHuffman法なのに対し、一度、形が似た も
圧縮/伸張技術の解説-ＢＷＴ(1)
近年の情報化社会において、インターネット、マルチメディア、分散ソフトウェア、をはじめとするコンピュータ技術の劇的な発展と普及により、システム間の通信情報量は増大の一途をたどっています。 データ圧縮技術は「サイズを減らす（同じサイズでより多くの情報を詰め込める）」という利点から、通信効率の改善、記憶装置の有効利用、に不可欠な基礎技術です。さらに「通信データ量を減らすことでCPUへの負荷を軽減しマルチタスク処理のレスポンスを改善する」という有用性もあり、その重要性は日に日に高まっています。 データ圧縮は本来、情報理論分野での「通信システムにおける情報量 の最小化の研究」の産物である「情報源符号化法」に端を発する技術であり、この分野では、工夫を凝らした様々な問題解決手法が提案されており、アルゴリズムを学ぶ上でたいへん興味深い分野の一つです。 代表的な例として、１８世紀頃から用いられていているモー
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |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ページを開く
