Проблема программирования - сжатие факса

Question

Я готовлюсь к конкурсу информатики, выполняя задачи прошлых конкурсов. Большинство из них довольно просты, но этот вызывает у меня сомнения ... кажется простым, но я просто не могу этого сделать.

Если у вас есть строка из нулей и единиц:

100111010001111100101010

Какой будет код, который будет принимать это в качестве входных данных, а затем выводить это:

1:1 2:0 3:1 1:0 1:1 3:0 5:1 2:0 1:1 1:0 1:1 1:0

Где цифра слева от каждого двоеточия - это число раз, которое появляется цифра после двоеточия.

Итак, еще один пример ... ввод:

1100011

Будет выводить:

2:1 3:0 2:1

В зависимости от проблемы это похоже на алгоритм, используемый для сжатия факсимильных сообщений.

Ответ на java был бы лучшим, но все, что я действительно ищу, это псевдокод или даже мысли о том, как это сделать.

Заранее спасибо.

Answer 1

Это называется Run-Length-Encoding (RLE) и используется в ряде вещей (например, формат файла растрового изображения Windows), чтобы обеспечить очень простое сжатие (особенно, если оригинал содержит много повторяющихся значений (например, растровое изображение или факс), содержащие длинную полосу одного цвета).

int[] array = { ........ }; // your values...
for ( int i=0; i < array.Length; i++ )
{
   int count = 1;
   int value = array[i];

   // Consume until different..
   while ( i+1 < array.Length && array[i] == array[i+1] )
   { 
       count++; 
       i++ 
   }

   Console.WriteLine("{0}:{1}", count, value);
}

// OR, as suggested by @jon  [done in my head, so could probably be improved a lot...]
int count = 0;
int oldValue = -1;
for ( int i=0; i<array.Length; i++ )
{
   int newValue = array[i];
   count = ( newValue != oldValue ) ? 1 : count+1;

   if ( i+1 >= array.Length || array[i+1] != newValue)
   {
      Console.WriteLine("{0}:{1}", count, newValue);
   }

   oldValue = newValue;
}

Answer 2

Так же, как мысль: зачем вам беспокоиться о числе справа? Он всегда будет чередоваться от 1 до 0, не так ли, поэтому просто предположите, что он начинается с 1, и закодируйте начальный 0, если фактическая последовательность начинается с 0. Другими словами, вы в конечном итоге получите:

1 2 3 1 1 3 5 2 1 1 1 1

Но в основном вам нужно следить за тем, "на что я сейчас смотрю?" и "сколько их я видел"? Если это изменится, запишите то, на что вы смотрели, и количество, а затем обновите «то, на что я смотрю», указав новое значение и счет до 1, затем продолжайте. Не забудьте также записать последнее значение в конце данных.

(Я не давал псевдокод или Java, так как я думаю, что вы узнаете больше, взяв небольшие подсказки, а не представившись с рабочим кодом. Если вам нужны дополнительные подсказки, просто скажите.)

Answer 3

Все, что я действительно ищу, это псевдокод или даже мысли о том, как это сделать.

Вот несколько мыслей:

• Как проверить, равен ли бит в байте единице или нулю: используйте операцию «побитовое И» для маскировки других битов
• Как проверить, равен ли один бит в байте единице или нулю:
  • Либо используйте другую битовую маску
  • Или сдвиньте или поверните биты в байте, прежде чем его замаскировать

Используйте описанные выше методы для обработки 8 битов в первом байте. Затем повторите это для обработки следующих 8 битов в следующем байте.

Некоторый псевдокод может выглядеть примерно так:

main()
{
  Encoder encoder = new Encoder;
  foreach (byte b in inputStream)
  {
    encoder.input(b);
  }
  //tell the encoder that the stream is finished
  //that there will be no subsequent bytes
  ///and that the final bits should be flushed now
  encoder.finished();
}

class Encoder
{
  //member data
  bool m_b; //value of the most-recently-processed bit
  int m_n; //number of the most-recently-processed bits

  //public methods
  void finished()
  {
    //TODO format and write the {m_n}:{m_b} value to output
    //and reset m_n to zero
  }

  void input(byte b)
  {
    for int (i = 0; i < 8; ++i)
    {
      //get the bit value
      bool bit = getbit(b, i);
      //see whether we can append it
      bool canAppend =
        (bit == m_b) || //new bit is same as previous bit
        (0 == m_n); //no previous bit
      //flush previous bits if can't append
      if (!canAppend)
        finished();
      //append current bit
      m_b = bit;
      ++m_n;
    }
  }

  //private helper method
  bool getbit(byte b, int i)
  {
    //TODO return the bit value using a mask
  }
}

Когда вы пишете свой код, не забудьте также проверить его, используя различные входные данные , включая особые случаи (включая, например, все биты в байте, имеющие одинаковое значение).