4

它基本上只是霍夫曼编码算法的一个实现，但是当我检查结束 BinaryTree（队列中唯一的项目）的概率时，它非常高。

// Make a BinaryTree for each item in CharOccurrences and add as an entry in initialQueue
for (int i = 0; i < charOccurrences.size(); i++) {
  BinaryTree<CharProfile> bTree = new BinaryTree<CharProfile>();
  bTree.makeRoot(charOccurrences.get(i));
  initialQueue.add(bTree);
}

// Create the BinaryTree that we're adding to the resultQueue
BinaryTree<CharProfile> treeMerge = new BinaryTree<CharProfile>();

// Create the CharProfile that will hold the probability of the two merged trees
CharProfile data;

while (!initialQueue.isEmpty()) {
  // Check if the resultQueue is empty, in which case we only need to look at initialQueue
  if (resultQueue.isEmpty()) {
    treeMerge.setLeft(initialQueue.remove());
    treeMerge.setRight(initialQueue.remove());

    // Set treeMerge's data to be the sum of its two child trees' probabilities with a null char value
    data = new CharProfile('\0');
    data.setProbability(treeMerge.getLeft().getData().getProbability() + treeMerge.getRight().getData().getProbability());
    treeMerge.setData(data);
  }
  else {
    // Set the left part of treeMerge to the lowest of the front of the two queues
    if (initialQueue.peek().getData().getProbability() <= resultQueue.peek().getData().getProbability()) {
      treeMerge.setLeft(initialQueue.remove());
    }
    else {
      treeMerge.setLeft(resultQueue.remove());
    }

    if (!initialQueue.isEmpty()) {
      // Set the right part of treeMerge to the lowest of the front of the two queues
      if (initialQueue.peek().getData().getProbability() <= resultQueue.peek().getData().getProbability()) {
        treeMerge.setRight(initialQueue.remove());
      }
      else {
        treeMerge.setRight(resultQueue.remove());
      }
    }
    // In the case that initialQueue is now empty (as a result of just dequeuing the last element), simply make the right tree resultQueue's head
    else {
      treeMerge.setRight(resultQueue.remove());
    }

    // Set treeMerge's data to be the sum of its two child trees' probabilities with a null char value
    data = new CharProfile('\0');
    data.setProbability(treeMerge.getLeft().getData().getProbability() + treeMerge.getRight().getData().getProbability());
    treeMerge.setData(data);
  }

  // Add the new tree we create to the resultQueue
  resultQueue.add(treeMerge);
}

if (resultQueue.size() > 1) {
  while (resultQueue.size() != 1) {
    treeMerge.setLeft(resultQueue.remove());
    treeMerge.setRight(resultQueue.remove());

    data = new CharProfile('\0');
    data.setProbability(treeMerge.getLeft().getData().getProbability() + treeMerge.getRight().getData().getProbability());
    treeMerge.setData(data);

    resultQueue.add(treeMerge); 
  }
}

然后我最后有这个：

System.out.println("\nProbability of end tree: " 
    + resultQueue.peek().getData().getProbability());

这给了我：

结束树的概率：42728.31718061674

4

1 回答 1

4

在 while 循环内移动以下行：

// Create the BinaryTree that we're adding to the resultQueue
BinaryTree<CharProfile> treeMerge = new BinaryTree<CharProfile>();

否则，一次迭代会添加treeMerge到resultQueue，而下一次可能会添加treeMerge.setLeft(resultQueue.remove());，这使得treeMerge它自己成为一个孩子......

于 2012-11-04T18:28:37.570 回答