33982


お世話になります。

今回、初めてGIFファイルの勉強をしようと、lzwの圧縮、解凍をC#で組んでみたのですが、  
どうもうまくいきません。

圧縮まではうまくいっているようなのですが、解凍しようとすると、余計なところに『0』が  
入ってしまい、正しく解凍されません。

ほかサイト様など、さまざまなところを拝見させていただいているのですが、どうも  
原因がわかりません。

原因と対策をお教えいただけますでしょうか。

尚、まだ勉強中のため、バイト単位でなく、0から255までのテキストデータの  
パターンで練習していますのでご了承ください。

下記にソースコードを記述します。

[code]

        private Dictionary<string, int> hsDic = new Dictionary<string, int>();
        private Dictionary<string,string > hsDec = new Dictionary< string,string>();
        private List<int> arch = new List<int>();
    
        private string[] stBuff = null;
    
        // 圧縮
        public int[] enc(string[] values)
        {
            for (int d0 = 0; d0 < 8; d0++)
            {
                this.hsDic.Add("" + d0, d0);
                this.hsDec.Add("" + d0,"" +  d0);
            }
            bool eof = false;
    
            this.stBuff = values;
    
            string w = "";
            string k = "";
    
            int skip = 0;
    
            int idx = 0;
    
            while (true)
            {
                //  idxで指定した文字を取得
                w = stBuff[idx];
    
                //  skipはidxの一文字後から開始
                skip = 0;
                if (this.hsDic.Count == 20)
                {
                    int a = 0;
                }
    
                while (true)
                {
                    skip++;
    
                    if(idx + skip >= stBuff.Length)
                    {
                        eof = true;
                        break;
                    }
                    k = stBuff[idx + skip];
                    if (this.hsDic.ContainsKey(w + "," + k))
                    {
                        w = w + "," + k;
                    }
                    else
                    {
                        break;
                    }
                }
    
                if(eof)
                {
                    break;
                }
                this.hsDic.Add(w + "," + k, this.hsDic.Count);
                this.arch.Add(this.hsDic[w]);
                idx += skip;
            }
            //  最後の一文字
    
            this.arch.Add(this.hsDic[w]);
            return this.arch.ToArray();
        }
    
        // 解凍
        public string[] dec2(int[] pattern)
        {
            for (int d0 = 0; d0 < 8; d0++)
            {
                this.hsDic.Add("" + d0, d0);
                this.hsDec.Add("" + d0,"" +  d0);
            }
    
            bool eof = false;
    
            int w = -1;
            int k = -1;
    
            string ww = "";
            string kk = "";
            int skip = 0;
    
            int idx = 0;
    
            List<string> lst = new List<string>();
    
            while (true)
            {
                //  idxで指定した文字を取得
                w = pattern[idx];
                ww = this.hsDec["" + w];
                //  skipはidxの一文字後から開始
                skip = 1;
    
                if (this.hsDec.Count == 20)
                {
                    int a = 0;
                }
    
                if (idx + skip >= pattern.Length)
                {
                    eof = true;
                    break;
                }
    
                k = pattern[idx + skip];
                kk = this.hsDec["" + k];
    
                this.hsDec.Add("" + this.hsDec.Count, ww + "," + kk);
                lst.Add(this.hsDec["" + w]);
                idx += skip;
            }
            ////  最後の一文字
    
            lst.Add(ww);
            return lst.ToArray();
        }
    
[/code]

テストパターン

[code]

    7,6,3,5,2,3,0,2,0,0,3,6,5,4,0,7,2,1,4,4,1,1,2,4,0,6,3,6,1,4,7,3,5,2,3,5,7,7,5,3,3,4,3,3,2,4,5,0,1,0,0,7,7,2,2,6,4,2,0,3,4,7,2,0,5,5,4,4,0,0,3,1,2,2,1,1,7,0,0,6,5,1,0,7,6,
    
[/code]

上記のパターンを使用しています。

ここまでですらうまくいっていないため、解凍時に辞書に登録されていないものは、  
wとwの最初の一文字を足したものを辞書に追加する…などといったこともまだ行っていません。

まだテスト中のため、コードも汚くて申し訳ありませんが、ぜひご教授いただけますよう、  
お願いいたします。


CC BY-SA 3.0
2017-04-13T07:09:19.333
33978
2017-04-13T08:47:52.257
2017-04-13T08:38:28.207
19110
9374
question
c# アルゴリズム
lzwの圧縮、解凍について


主要な原因として`dec2`の下記の個所に2点誤りがあります。

>
[code]

>           k = pattern[idx + skip];
>           kk = this.hsDec["" + k];
>           this.hsDec.Add("" + this.hsDec.Count, ww + "," + kk);
>  
[/code]

まず3行目で登録している値ですが、`kk`は先頭の文字のみを使用しなくてはなりません。ですので`kk[0]`のようにしてください。

次に2行目ですが、ここでキー`k`が登録されているとは限りません。

たとえば`0,0,0`というデータを圧縮すると、まずコード`8`に`0,0`が登録されて`0,8`が出力されます。これを復号しようとした場合、`0`の次のコード`8`が登録される前に`8`を参照しようとして例外が発生します。

このためディクショナリに後続のコードが登録されていない場合の処理を行わなくてはなりませんが、圧縮時に直前に追加したコードが使用されているため両コードは平文の先頭が一致していると判断できます。ですのでキーがない場合は`kk`として`ww`を使用します。

あともう一点あげると`ww`はカンマ区切りなので`lst.Add(ww)`
(二か所)は`lst.AddRange(ww.Split(','))`が正しいです。ここを直せば少なくとも質問のデータについてはラウンドトリップします。


CC BY-SA 3.0
2017-04-13T08:39:20.683
33982
2017-04-13T08:47:52.257
2017-04-13T08:47:52.257
5750
5750
33978
answer