前方移動講座

Revised : 2006/05/06
Since : 2006/05/01


Home  圧縮 ∥ 前方移動 | 改良 | その1 | その2 | その3

前方移動(Move To Front)

先頭移動ともいう。
出現文字テーブルを作成し、出現した文字コードを常に先頭に移動(登録)する方法である。
つまり、出現した文字コードを出現文字テーブルのインデックス値に変換するアルゴリズムである。
そのまま変換すればただの写像だが、先頭に移動することにより次回出現時のインデックス値が小さくなるようにしている。

元のデータ テーブル 出力 出力後のテーブル
A ABC ABC
C ABC CAB
B CAB BCA
A BCA ABC
B ABC BAC
C BAC CBA
A CBA ACB
A ABC ABC
A ABC ABC
ACBABCAAA <- 元のデータ 022212200 <- 出力データ
ページの上部へ

改良

出現した文字コードを出現文字テーブルのインデックス値に変換することは同じであるが、
前方に移動する時に、常に先頭に移動するのではなく移動する位置を工夫することにより、
必要以上に出現文字テーブルを乱さないようにし、出力データの偏りを大きくする。
以下に示す方法は、経験的に良い結果が得られることが知られているが、入力データに依存している。
ページの上部へ

その1

出現文字テーブルのインデックス1より後方の文字コードが入力された場合は、
そのインデックス値を出力し、インデックス1に移動する。
インデックス1にある文字コードが入力された場合は、1を出力し、インデックス0に移動する。
インデックス0にある文字コードが入力された場合は、0を出力し、インデックス値も0のままとする。

元のデータ テーブル 出力 出力後のテーブル
A ABC ABC
C ABC ACB
B ACB ABC
A ABC ABC
B ABC BAC
C BAC BCA
A BCA BAC
A BAC ABC
A ABC ABC
ACBABCAAA <- 元のデータ 022012210 <- 出力データ
ページの上部へ

その2

上記その1と同様の方法だが、出現文字テーブルのインデックス1にある文字コードが入力された場合が異なる。
この場合、直前に出力されたインデックス値が0の場合は、1を出力し、インデックス値も1のままとする。
直前に出力されたインデックス値が0以外の場合は、1を出力し、インデックス0に移動する。

元のデータ テーブル 出力 出力後のテーブル
A ABC ABC
C ABC ACB
B ACB ABC
A ABC ABC
B ABC ABC
C ABC ACB
A ACB ACB
A ACB ACB
A ACB ACB
ACBABCAAA <- 元のデータ 022012000 <- 出力データ
ページの上部へ

その3

出力するインデックス値が、直前に出力されたインデックス値より大きければ、インデックス1に移動する。
それ以外は、インデックス0に移動する。

元のデータ テーブル 出力 出力後のテーブル
A ABC ABC
C ABC ACB
B ACB BAC
A BAC ABC
B ABC BAC
C BAC BCA
A BCA ABC
A ABC ABC
A ABC ABC
ACBABCAAA <- 元のデータ 022112200 <- 出力データ
ページの上部へ
容量300MB、月額125円、高性能なサーバが日本最大級のバックボーンに直結。
さくらのレンタルサーバ
ロリポップのドメインが65種類 → 85種類に!!
きっとお好みのドメインが見つかるはず!
アフィリエイトならリンクシェア