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などのソフ

[starpos]

とても分かりやすかった．社内勉強会で使わせていただきます．

[rishida]

最近オープンウォーターダイバーのライセンスを取りました。徳永です。 今日はBurrows Wheeler Transform（BW変換もしくはBWT）の逆変換において用いられるLF mappingを説明します。 BWTはデータ圧縮の前処理などに使われるテクニッ

[nakag0711]

説明されるべきことが説明されなかったので、理解されるべきことが理解されませんでした。

[ya--mada]

そういや、あれは？どうなったんだろ。yz2

[takeda25]

こういう記事は、よっぽどじっくり読み込まないとわからない。勉強会のネタ向き。