0

我的总体项目是创建一棵树并使用 Huffman 编码对给定文件进行编码和解码。我正需要解码我的文件。为此,我必须遍历我的霍夫曼树,直到到达最底部的叶子,然后返回由该叶子表示的字节。我根据给方法的位串遍历树。AKA 如果当前位为 1,我会转到树中的 childOne,依此类推。问题是我不断收到outOfMemory错误。有什么办法可以优化这段代码,使其不会使用太多的内存?

    public static int decode(List<Integer> bitArray, HuffmanNode root, int startingPosition,
                          ArrayList<Byte> finalArray)
    {
    HuffmanNode childOne;
    HuffmanNode childZero;
    int currentBit = bitArray.get(startPosition);
    byte newByte;

            childOne = root.getChildOne();
            childZero = root.getChildZero();
            if(childOne == null && childZero == null)
            {
               finalArray.add(root.getByteRepresented()); 
               return startPosition;
            } 
            else if(currentBit == 1)
            {
                startPosition++;
                startPosition = decode(bitArray,childOne,startPosition,finalArray);
            }
            else
            {
                startPosition++;
                startPosition = decode(bitArray,childZero,startPosition,finalArray);
            }

         return startPosition;

}

我需要知道它结束的位数组中的位置以及将指定的字节放入数组中,这就是为什么我将字节放入方法内的数组中并返回和 int。基本上,有没有更好的方法来完成这项工作?

4

5 回答 5

2

就在这里。将递归更改为迭代..

temp = root;
childOne = temp.getChildOne();
childZero = temp.getChildZero();
while(childOne != null && childZero != null) {
  currentBit = bitArray.get(startPosition++);
  if (currentBit == 1) {
    temp = childOne;
  } else {
    temp = childZero;
  }
  childOne = temp.getChildOne();
  childZero = temp.getChildZero();
}
于 2013-04-14T17:37:45.087 回答
0

我不知道事情有多大,但我认为你不需要递归。你不能用这样的循环做你需要的事情:

while (curNode.isNotLeaf())
{
  if (currentBit == 1) curNode = curNode.getChildOne();
  else curNode = curNode.getChildZero();
  currentBit = nextBit;
}

addByte(curNode, bigArray)

所以你在这个循环中遍历你的位,当你离开时添加表示的字节,然后继续 - 不需要所有的堆栈帧递归。

于 2013-04-14T17:46:53.367 回答
0

此外,请考虑使用较低级别的数据结构,例如java.util.BitSet代替List<Integer>java.io.ByteArrayOutputStream代替ArrayList<Byte>.

于 2013-04-14T17:50:49.993 回答
0

如果递归是您的问题,您很可能会遇到堆栈溢出错误。由于您的内存不足,我建议您查看:

  • 确保在每次通话后丢弃bitArray和。finalArray
  • 使用流输出到。
  • 使用 aBitSet作为位数组。
  • 确保您没有意外在树中制作循环。
于 2013-04-14T17:55:51.363 回答
-1

看看像 OpenBitSet (Lucene) 这样的压缩位集实现 http://code.google.com/p/javaewah/ http://www.censhare.com/en/aktuelles/censhare-labs/yet-another-compressed -bitset

于 2013-04-25T19:56:25.000 回答