06
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

MTF(MoveToFront)改造

MTFをちょこっと改造した物です。 MTFを実装してかなり処理速度が遅くなってしまったため 前に移動するのではなく前の値と交換することにしました どういう事かというと MTFだと(MTFはhttp://www.geocities.jp/m_hiroi/light/pyalgo48.html参照して下さい詳しく書かれています。)
吐き出すコードの配列が
a,b,c
読み込んだ文字がcだったら
c,a,b
に為る所を

a,b,c
→c,b,a

のように先頭の値と交換するだけにしました。(誰かやってるよな~きっと)
MoveToFrontならぬSwapToFrontですね~こっちのが実装楽

これをやると偏りは減ります。
なかなか多いデータが前に来ないから
だけど0の多さは健在です。
なんで0だけ連長かければMTFと圧縮率あんまりかわらんかった

組み込みをもくろんでいる僕としては展開はせめて1Mあたり0.1秒くらいで展開したいわけですが、これでクリアできました。
圧縮は、接尾辞配列の構築という問題で1Mあたり1秒と実用にならない…
(組み込みならブロックソートとかいらないよなぁとかもおもうけど)
そもそも圧縮とかってネイティブが基本だからなぁ~^^;
エンコードの引数が配列で、デコードがMemoryStreamなのは結構デコードだけいじくってたから
ちなみに以下のコードでは上記ページの記法でMTF-2を派生させています

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace BlockMoveLength
{

/*
MTF法変形(SwapToFront?)

©
まりも
2010/8/7
http://marimokobo.blog53.fc2.com/ 

ソースは2010/8/26現在のMIT Licenseでライセンスされます。

このコメントもしくは上記著作権表示をどっかに突っ込んでおくかwebの場合リンクしておいてください。
*/
    class MoveToFront
    {
       
        int Prev = 1;
        static MoveToFront()
        {
            FirstArray = new byte[256];
            for (int i = 1; i < 256; i++) FirstArray[i] = (byte)i;
        }



        static byte[] FirstArray;

        public byte[] Encode(byte[] data)
        {
            byte[] array = FirstArray.ToArray();

            int l = data.Length;
            byte b;
            int i;
            byte[] ret = new byte[l];
            for (int j = 0; j < l; j++)
            {
                b = data[j];
                for (i = 0; i < 256; i++) { if (array[i] == b)break; }
                    if (i == 1)
                    {
                        if (Prev != 0)
                        {
                            array[1] = array[0]; array[0] = b;
                        }
                    }
                    else if (i > 1)
                    {
                        b = array[i];
                        array[i] = array[1];
                        array[1] = b;

                    }
                Prev = i;
                ret[j] = (byte)i;
            }
            return ret;
        }

        public void Decode(MemoryStream ms)
        {
            byte[] array = FirstArray.ToArray();
            int f = (int)ms.Position;
            int l = (int)ms.Length;
            int b;

            for (int j = f; j < l; j++)
            {
                b = ms.ReadByte();
                ms.Position--;
                byte c = array[b];
                if (b == 1)
                {
                    if (Prev != 0)
                    {
                        array[1] = array[0];
                        array[0] = c;
                    }

                }
                else if (b > 1)
                {
                    array[b] = array[1];
                    array[1] = c;

                    
                }
                Prev = b;
                ms.WriteByte(c);
            }
            ms.Seek(f, SeekOrigin.Begin);
        }

    }




}


スポンサーサイト

Comment

Secret

検索フォーム

RSSリンクの表示

リンク

リンクというか個人的によく使うアルゴリズムの解説サイト… C#でなかったりする

ブロとも申請フォーム

この人とブロともになる

QRコード

QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。