编程问题-传真压缩

Question

我正准备通过完成过去竞赛中的问题来参加计算机科学竞赛。 其中大多数都很简单，但这一个却困扰着我……看起来很简单，但我就是做不到。

如果您有一串 1 和 0：

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

这称为运行长度编码 (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

我真正寻找的是伪代码，甚至是关于如何做到这一点的想法。

以下是一些想法：

• 如何测试字节中的某个位是 1 还是 0：使用“按位与”运算屏蔽其他位
• 如何测试字节中的不同位是 1 还是 0：
  • 或者使用不同的位掩码
  • 或者，在屏蔽字节之前移位或旋转字节中的位

使用上述方法处理第一个字节中的 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
  }
}

当您编写代码时，不要忘记使用各种输入数据测试它，包括特殊情况（例如，包括一个字节中的所有位）具有相同的值）。