如何进行游程编码？

Question

我有一个很长的字符串，例如它可能是“aaaaaabbccc”。需要将其表示为“a6b2c3”。最好的方法是什么？我可以通过比较字符和递增计数，然后在一次传递中使用两个索引替换数组中的计数，以线性时间完成此操作。你们能想出比这更好的办法吗？任何编码技术都适用于此吗？

Answer 1

常见的解决方案是 RLE - 运行长度编码，维基百科文章有示例实现代码。

Answer 2

我认为没有更快的方法来解决它。

非正式地，您可以认为次线性复杂度意味着进行的比较次数少于要压缩的字符串中的字符数。但是，通过如此小的比较，您无法确定某些字符，您无法知道它们包含什么，因为您没有足够的信息。这意味着您无法获得无损< /strong> 压缩。

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