Scala中的Bitstream库

Question

我需要用旧的内部开发算法压缩/解压缩一些数据。在那里我有很多操作，例如：

if the next bit is 0 take the following 6 Bits and interpret them as an Int
if the next bits are 10 take the following 9 Bits and interpret them as an Int 
etc.

认识像Scala中的“ Bitstrem”类之类的人吗？ （我什么都没找到，希望我不必自己实施。）

谢谢

编辑：我将答案与 http://www.scala-lang.org/node/8413 （“ Scala Collections的架构”）如果有人需要派遣：

abstract class Bit
object Bit {
  val fromInt: Int => Bit = Array(Low, High)
  val toInt: Bit => Int = Map(Low -> 0, High -> 1)
}

case object High extends Bit
case object Low extends Bit

import collection.IndexedSeqLike
import collection.mutable.{Builder, ArrayBuffer}
import collection.generic.CanBuildFrom
import collection.IndexedSeq

// IndexedSeqLike implements all concrete methods of IndexedSeq
// with newBuilder. (methods like take, filter, drop)
final class BitSeq private (val bits: Array[Int], val length: Int)
         extends IndexedSeq[Bit]
         with IndexedSeqLike[Bit, BitSeq]
{
  import BitSeq._

  // Mandatory for IndexedSeqLike
  override protected[this] def newBuilder: Builder[Bit, BitSeq] =
    BitSeq.newBuilder

  //Mandatory for IndexedSeq
  def apply(idx: Int): Bit = {
    if(idx < 0 || length <= idx)
      throw new IndexOutOfBoundsException
    Bit.fromInt(bits(idx/N) >> (idx % N) & M)
  }


}

object BitSeq {

  // Bits per Int
  private val N = 32

  // Bitmask to isolate a bit
  private val M = 0x01


  def fromSeq(buf: Seq[Bit]): BitSeq = {
    val bits = new Array[Int]((buf.length + N - 1) / N)
    for(i <- 0 until buf.length) {
      bits(i/N) |= Bit.toInt(buf(i)) << (i % N)
    }
    new BitSeq(bits, buf.length)
  }

  def apply(bits: Bit*) = fromSeq(bits)

  def newBuilder: Builder[Bit, BitSeq] = new ArrayBuffer mapResult fromSeq

  // Needed for map etc. (BitSeq map {:Bit} should return a BitSeq)
  implicit def canBuilderFrom: CanBuildFrom[BitSeq, Bit, BitSeq] =
    new CanBuildFrom[BitSeq, Bit, BitSeq] {
      def apply(): Builder[Bit, BitSeq] = newBuilder
      def apply(from: BitSeq): Builder[Bit, BitSeq] = newBuilder
    }
}

Answer 1

我没有任何现有的课程，但是您可以利用现有类来帮助几乎所有困难的操作。诀窍是将您的数据转换为INT（如果没有足够的内存）的INT流（或字节）。然后，您可以使用所有方便的收集方法（例如 take），只剩下将位变成内存的问题。但是，如果您按MSB顺序打包位，这很容易。

object BitExample {
  def bitInt(ii: Iterator[Int]): Int = (0 /: ii)((i,b) => (i<<1)|b)
  def bitInt(ii: Iterable[Int]): Int = bitInt(ii.iterator)

  class ArrayBits(bytes: Array[Byte]) extends Iterator[Int] {
    private[this] var buffer = 0
    private[this] var index,shift = -1
    def hasNext = (shift > 0) || (index+1 < bytes.length)
    def next = {
      if (shift <= 0) {
        index += 1
        buffer = bytes(index) & 0xFF
        shift = 7
      }
      else shift -= 1
      (buffer >> shift) & 0x1
    }
  }
}

然后你做类似的事情

import BitExample._
val compressed = new ArrayBits( Array[Byte](14,29,126) ).toStream
val headless = compressed.dropWhile(_ == 0)
val (test,rest) = headless.splitAt(3)
if (bitInt(test) > 4) println(bitInt(rest.take(6)))

（您可以决定是否要直接使用迭代器，还是作为流，列表或其他方式使用。）