Как сделать кодирование длины пробега?

Question

У меня есть длинная строка, например, это может быть "aaaaaabbccc". Нужно представить его как "a6b2c3". Какой лучший способ сделать это? Я мог бы сделать это за линейное время, сравнивая символы и увеличивая счетчики, а затем заменяя счетчики в массиве, используя два индекса за один проход. Ребята, вы можете придумать лучший способ, чем этот? Будут ли здесь работать какие-либо методы кодирования?

Answer 1

Распространенным решением для этого является RLE - кодирование длин серий , в статье Википедии есть пример кода реализации.

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

Я думаю, что вы спрашиваете: "Есть ли лучший, чем линейный, способ выполнить кодирование по длине прогона"? Если так, ответ - нет.