run-length-encoding - 如何进行游程编码？

Question

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

Answer 1

常见的解决方案是RLE - Run-length encoding，维基百科文章有示例实现代码。

Answer 2

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

非正式地，您可以认为次线性复杂性意味着对要压缩的字符串中的字符数进行较少的比较。但是，由于您没有足够的信息，因此您无法确定某些字符，因此无法确定它们包含的内容。这意味着您无法获得无损压缩。

Answer 3

我已经实现了字节编码。希望能帮助到你。

 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

Answer 4

我想您是在问，“有没有比线性方式更好的游程编码方式”？如果是这样，答案是否定的。