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>();

それ以外の場合、1 つの反復で が追加treeMergeされresultQueue、次の反復で が追加され、それ自体の子がtreeMerge.setLeft(resultQueue.remove());作成されます...treeMerge

于 2012-11-04T18:28:37.570 に答える