run-length-encoding - ランレングスエンコーディングを行うには?

Question

たとえば、「aaaaaabbccc」などの長い文字列があります。「a6b2c3」として表す必要があります。これを行う最善の方法は何ですか？文字を比較してカウントをインクリメントし、1 回のパスで 2 つのインデックスを使用して配列内のカウントを置き換えることで、線形時間でこれを行うことができます。これよりも良い方法を考えられますか？ここで機能するエンコード技術はありますか?

Answer 1

これに対する一般的な解決策はRLE - Run-length encodingです。ウィキペディアの記事にはサンプルの実装コードがあります。

Answer 2

それを解決するためのより速い方法はないと思います。

非公式には、準線形の複雑さは、圧縮したい文字列内の文字数よりも少ない比較を行うことを意味すると考えることができます。しかし、比較の数が非常に少ないと、特定の文字を確認できず、十分な情報がないため、何が含まれているかを知ることができません..これは、ロスレス圧縮を取得できないことを意味します.

Answer 3

「ランレングス エンコーディングを行う線形よりも優れた方法はありますか」と尋ねていると思いますか? もしそうなら、答えはノーです。

Answer 4

ただし、バイトのエンコーディングを実装しました。それが役に立てば幸い。

 public byte[] Encode(byte[] original)
            {
                // TODO: Write your encoder here
                if (original==null || original.Count() == 0) // Check for invalid inputs
                    return new byte[0];

                var encodedBytes = new List<byte>();         // Byte list to be returned
                byte run = 0x01;

                for (int i = 1; i < original.Length; i++)
                {
                    if (original[i] == original[i - 1])     // Keep counting the occurences till this condition is true
                        run++;
                    else                                    // Once false,  
                    {
                        encodedBytes.Add(run);              // add the total occurences followed by the 
                        encodedBytes.Add(original[i - 1]);  // actual element to the Byte List 
                        run = 0x01;                         // Reset the Occurence Counter  
                    }
                    if (i == original.Length - 1)          
                    {
                        encodedBytes.Add(run);
                        encodedBytes.Add(original[i]);
                    }
                }

               return  encodedBytes.Count()==0 ? new byte[0] : encodedBytes.ToArray<byte>();
            }

var a = new byte[]{0x01, 0x02, 0x03, 0x04};
var b = new byte[]{0x01, 0x01, 0x01, 0x02, 0x01, 0x03, 0x01, 0x04};
var EncodedA =  Encode(a);
var isAEqualB = EncodedA.SequenceEqual(b); should return true