Burrows Wheeler TransformとLF mapping - Preferred Networks Research & Development
最近オープンウォーターダイバーのライセンスを取りました。徳永です。 今日はBurrows Wheeler Transform（BW変換もしくはBWT）の逆変換において用いられるLF mappingを説明します。 BWTはデータ圧縮の前処理などに使われるテクニックです。Burrows Wheeler Transformはとても簡単でわかりやすい（高速な実装は複雑ですが……）のですが、逆変換で用いられるLF mappingは、実装は簡単なものの、なぜそれでよいのかは少しわかりにくいところがあります。また、私はこれまで、LF mappingがなぜあれでうまくいくのか、わかりやすい説明を日本語でも英語でも見た記憶がありません。そこで今回はLF mappingを中心に説明します。なお余談ですが、BTWのMichael Burrowsは現在はGoogle勤務で、ChubbyやBigTableなどのソフ
bwtの圧縮率解析 - DO++
Burrows-Wheeler Transform (blocksortingと同じもの。以下bwt)はbzip2などで利用されている文字列に対する可逆変換です（詳細は勉強会資料とかググってください）。bwtを適用した後のテキストは同じ文字が連続しやすい圧縮しやすいデータとなり簡単な後処理（MTF変換+order-0圧縮）を加えることでLZ法よりも圧縮率は高く、PPM法に匹敵するぐらいに小さくなることは実験的に示されていました。 しかし、どのくらい小さくなるかの理論的解析はあまり進んでおらず、bwt後の処理に関してはもっといい方法があるはずだと研究が進んできました。 最近発表された話(compression boosting, The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compr
［TGS 2013］TGS会場で見つけた，寝転んでゲームができる夢のごろ寝クッション「goron」は想像以上の快適さだった
［TGS 2013］TGS会場で見つけた，寝転んでゲームができる夢のごろ寝クッション「goron」は想像以上の快適さだった ライター：箭本進一 東京ゲームショウ2013では，最新ソフトのほかにゲーム関連グッズも多数出展されている。そんな中で個人的に気になったのが，ごろ寝しながらゲームやタブレットが楽しめるという「goron」だ。 デジタルライフが多様化する現在，「寝転びながらゲームしたり，タブレットを使いたい」と考えている人も多いだろう。ここで問題となるのが，機器の向きだ。普通にテレビの前でごろ寝すると，画面が横向きになってしまう。スマートフォンやタブレットの場合だと，手に持って寝転ぶことができるが，どうしても腕が疲れてしまいがち。筋肉は鍛えられるかもしれないが，長時間のプレイに最適とは言い難い。筆者の場合，寝床に置いた文庫本にタブレットやスマートフォンを立てかけて動画やWebブラウズを楽
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
