復号の手順
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/09/18 20:42 UTC 版)
復号は非常に単純かつ機械的に行えるが、「なぜ」きちんと復号されるかを直観的に理解するのは少し難しい。そこで理解のため、元の巡回行列を復元する事を考える。 まず、BWT系列の文字列「ccoaa」をソートすると行列 M {\displaystyle M} のA列が得られる。(A列とE列に含まれるアルファベットは同一であり, A列はソートされているため) 初期状態：（表1） ABCDE1 a ? ? ? c 2 a ? ? ? c 3 c ? ? ? o 4 c ? ? ? a 5 o ? ? ? a 各行は元の文字列を巡回シフトしたものであるため、各行のE列、A列の文字は元の文字列で連続しているか、先頭と末尾の文字であったはずである。この性質から、全列右シフトを行い、左端の列(ここではE列)をキーにソートすることでD列を得ることができる。このとき、左端の文字が同じ行については、他の列の文字によらず、元の表での順序を保ったままにする。すなわち、ソートは安定ソートでなければならない。 右シフトした状態:（表2） EABCD1 c a ? ? ? 2 c a ? ? ? 3 o c ? ? ? 4 a c ? ? ? 5 a o ? ? ? ソート後の状態:（表3） EABCD4 a c ? ? ? 5 a o ? ? ? 1 c a ? ? ? 2 c a ? ? ? 3 o c ? ? ? このときBWT系列の性質から、右端となったD列には表1の右端と同様にBWT系列の文字列「ccoaa」が順番に入ることになる。 右端を埋めた状態：（表4） EABCD4 a c ? ? c 5 a o ? ? c 1 c a ? ? o 2 c a ? ? a 3 o c ? ? a この操作を繰り返し行い順次C、Bと求めていくことで、最終的に行列 M {\displaystyle M} を得ることができる。
※この「復号の手順」の解説は、「ブロックソート」の解説の一部です。
「復号の手順」を含む「ブロックソート」の記事については、「ブロックソート」の概要を参照ください。
復号の手順
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/07/26 08:54 UTC 版)
変数 N を 1 にセットする。 符号語の最初を読み込む。 0 ならば、整数の 1 を表している。 1 ならば、それに続く N 桁と合わせてバイナリ符号となっているため、N をその値にセットする。 以降はこのステップを繰り返す。符号語の残りの先頭を読み込む。0 ならば、符号化された数値が N となることを表している。1 ならば、続く N 桁と合わせてバイナリ符号となっているため、 N をその値にセットする。 符号語 101100 を復号する例を示す。 まず N=1 として、先頭 1 記号を読み込む。値が 1 なので、続く N=1 記号を読み込んだ 10 をバイナリ符号とみなした 2 を、新たな N の値とする。すると、符号語の残りは、 1100 となる。先頭 1 記号を読み込む。値が 1 なので、続く N=2 記号を読み込んだ 110 をバイナリ符号とみなした 6 を、新たな N の値とする。すると、符号語の残りは、 0 となる。先頭 1 記号を読み込む。値が 0 なので、N=6 が求める整数値である。
※この「復号の手順」の解説は、「オメガ符号」の解説の一部です。
「復号の手順」を含む「オメガ符号」の記事については、「オメガ符号」の概要を参照ください。
- 復号の手順のページへのリンク
