快速霍夫曼解码

Question

我用 Scala 写了一个 huffman compression/decompression。解码小文件需要几秒钟，但解码大文件需要很长时间。关于如何加快此过程的任何建议？

def lookup(list:List[Int],list2:List[(Char,List[Int])]): Option[String]={
  val mutableListBuffer = scala.collection.mutable.ArrayBuffer(list2: _*)
  var option:Option[String]= None
  for(i <- 0 until mutableListBuffer.length){  
    if(mutableListBuffer(i)._2 == list){
      option =  Some(mutableListBuffer(i)._1.toString)         
    }
  }
  option
}

/*
*Decode function for matching groups of bits in a list to characters    in     the HCodeMap
*@returns String
*/
def decode(acc:Int,s:String,list:(List[Int],List[(Char,List[Int])])):String ={
  var s = ""
  var accum = 1
  val listp1 = scala.collection.mutable.ArrayBuffer(list._1: _*)
  val listp2 = scala.collection.mutable.ArrayBuffer(list._2: _*)
  var tupList = (listp1,listp2)

  while(!tupList._1.isEmpty){
    if(lookup(tupList._1.take(accum).toList,tupList._2.toList).isDefined){
      println(accum)
      s = s ++ lookup(tupList._1.take(accum).toList,tupList._2.toList).getOrElse("a")
      Log.d("MyTAG", "de" + s)  
      tupList._1.remove(0,accum)
      accum = accum - accum + 1
    }
    else{
      accum =  accum + 1
    }        
  }
  s
}

代码在 Android 设备上执行，因此使用递归不是一个有效的选项，使用不可变列表也不是。任何建议将不胜感激。再次感谢。

Answer 1

这可能属于 codereview，但我认为这里的代码与您的代码直接等效，没有任何转换为 ArrayBuffers（这不是必需的）。列表操作相当有效，只是获取和删除以及列表遍历，所以我认为你在错误的方向上指责不可变列表。

def lookup(list: List[Int], list2: List[(Char, List[Int])]): Option[String] = 
 list2.find(_._2 == list).map(_._1.toString)

/*
*Decode function for matching groups of bits in a list to characters    in     the HCodeMap
*@returns String
*/

 def decode(s: String, list: (List[Int], List[(Char, List[Int])])): String = {

  var s = ""
  var accum = 1
  var listp1 = list._1
  val listp2 = list._2

  while (!listp1.isEmpty) {

    lookup(listp1.take(accum), listp2) match {
      case Some(m) =>
        println(accum)
        s = s ++ m
        Log.d("MyTAG", "de" + s)
        listp1 = listp1.drop(accum)
        accum = 1
      case None =>
        accum = accum + 1
    }
  }
  s
}

Answer 2

想要快，你的出发点就错了。您应该直接使用位流，而不是每个整数包含一位的整数列表。在某个地方，您正在浪费时间将传入的位转换为整数列表，然后浪费大量时间对该列表进行解码。

制作快速霍夫曼解码器的一种方法是构建允许直接索引查找的解码 table。选择一些位，n，这大约是一个统一代码的长度。例如。如果你有 256 个符号，让我们从 n 作为八个开始。（后面可以乱用n来优化速度。）

现在构建一个 256 条目 table，它由接下来的八位输入索引。每个条目指示 a) 下一个代码的长度为 8 位或更少，或者 b) 下一个代码的长度为 9 位或更多。对于 a)，table 告诉您代码中的位数及其解码的符号。在那种情况下，您从流中删除那么多位并发出符号。

对于 b) table 指向下一个 table 以索引后续位以及有多少位。然后您从流中丢弃八位并索引 subtable 这也将指示 a) 或 b)。虽然可能两级 tables 是最优的，所以 sub table 将始终指示 a)，完成解码并发出一个符号。在那种情况下，子 table 的大小，即索引中的位数是最长代码的长度，减去八，它具有索引主 table 的八位前缀.

tables 构建起来很简单，一次构建就可以多次使用，因此构建时间非常值得。 table 中的条目经常重复多次。例如。一个四位代码将在基本八位 table.

中重复 16 次

您将在位缓冲区（一个整数）上使用位操作，它根据需要从流中提取字节，以使其加载足够的位以形成下一个索引。简单的位移位会在使用时将位向下移动，而输入字节的位移位将在将它们输入位缓冲区之前完成。

一旦一切正常，您可以改变 n 并为具有代表性输入的解码器计时，以找到 n 的最佳值.

快速霍夫曼解码

Fast huffman decode

android

scala

huffman-code