ABL

Calculating the ABL

• The ABL of a prefix tree stands for the average number of bits required to represent a character in the tree.

• In our uncompressed prefix tree - we can see that we used 3 bits to represent each character. Then in our uncompressed tree, we expanded out this bits from low frequency characters and shrunkated it to high frequency characters. In the end, the average bits per character number of bits per character is the number of bits we used to represent each character in the uncompressed tree.

• In other words, within the compressed tree. The ABL would be the average depth of a leaf node.

• Another way to calculate the ABL is to do a traverse of the graph.

  • Assuming we have the frequency of a leaf node available to us, we can calculate the ABL by summing all the leafs nodes (frequency x depth).

  • Frequency, we will also assume is the ratio of same characters / total characters.

  • The depth is the height of a tree for a particular leaf node. We can use the depth to calculate the number of bits per particular leaf node, because each traversal down represents an additional bit.

  • Therefore, the frequency * depth implicitly calculates the average for us, since frequency already divided by the total number of characters.

  • A DFS traversal can calculate the ABL

DFS-abl(root, depth) {
  if (root.isleaf)
    return depth * root.frequency;
  else {
    return DFS-abl(root->left, depth+1) + DFS-abl(root->right, depth + 1);
  }
}

DFS-abl(root) {
  DFS-abl(root, 0);
}