Efficient Tag Cloud Algorithm

Hey all - since tag clouds are so popular these days, I thought I'd make a quick post about the algorithm I'm using to generate my tag cloud. I found a few sample algorithms already out there, but many of them seemed either inefficient, or didn't return the size that I was expecting.

Considering that the algorithm I'm using for my blog is running on the client side, I wanted to make sure that it was especially efficient. Here's what I ended up coming up with.

First, let's define the variables that are being used:

maxPercent

The font size is set as a percentage. This is the font-size percentage that the largest (most frequent) tag should be set to.

minPercent

This is the font-size percentage that the smallest (least frequent) tag should be set to.

max

This is the number of occurences for the most frequent tag.

min

This is the number of occurences for the least frequent tag.

count

This variable should be set inside of the link iterator. It refers to the number of occurences for the current tag.

Before I show some sample code for this, let's look at the actual algorithm for calculating the size:

var size = minPercent + ((max-(max-(count-min)))*(maxPercent-minPercent)/(max-min));

Since count is the only variable that changes during each iteration, we can extract the expression (maxPercent-minPercent)/(max-min) into its own constant and define it outside of the loop. This will save us two subtractions and a division operation for every loop. This now yields the following algorithm:

var multiplier = (maxPercent-minPercent)/(max-min);
var size = minPercent + ((max-(max-(count-min)))*multiplier);

The mathematical brilliance (sorry) behind this simple function isn't immediately obvious by looking at it, but the size returned will adhere to the following rules:

1. The least occuring tag(s) will have a font-size of minPercent.
2. The most occuring tag(s) will have a font-size of maxPercent.
3. Tags with occurence counts in the middle will be scaled linearly.

Ok, let's look at this algorithm in action. The sample below uses a few jQuery methods (you all saw it coming), but this algorithm can certainly survive apart from any JS library. Notice that in the code below, I don't know min or max at the start. This means I have to loop through all of the tags twice, calculating these statistics the first time.

To give this code a real life context, I am generating a tag cloud out of the categories list that blogger generates. The markup that I am looping through is in the following format:

<div class="widget-content" id="categories">
 <ul>
  <li>
   <a dir="ltr" href="http://jmar777.blogspot.com/search/label/jQuery">jQuery</a>
   (<span dir="ltr">6</span>)
  </li>
  <li>
   <a dir="ltr" href="http://jmar777.blogspot.com/search/label/jTruncate">jTruncate</a>
   (<span dir="ltr">2</span>)
  </li>
  [etc...]
 </ul>
</div>

And here's the heavily commented javascript:

$().ready(function() {
 var catContainer = $('div#categories');
 // get an array of all the <li>'s
 var categories = catContainer.find('ul li');
 var cloudMarkup = '';
 // set maxPercent/minPercent preferences
 var maxPercent = 150, minPercent = 100;
 // note that max is initialized to a number that I know is lower than the max count
 // and that min is set to a number larger than the known min count
 var max = 1, min = 999, count = 0;
 // loop through each li and calculate statistics
 categories.each(function(i) {
  count = parseInt($(this).find('span').text());
  max = (count > max ? count : max);
  min = (min > count ? count : min);
 });
 var total, link, size;
 var multiplier = (maxPercent-minPercent)/(max-min);
 // loop through each li and generate the markup for the new tag cloud
 categories.each(function(i) {
  count = parseInt($(this).find('span').text());
  link = $(this).find('a');
  size = minPercent + ((max-(max-(count-min)))*multiplier) + '%';
  cloudMarkup += '<a class="cloud_link" style="font-size:' + size + '" href="' + link.attr('href') + '">' + link.text() + '</a> ';
 });
 // replace the html content of the parent container with the new tag cloud
 catContainer.html(cloudMarkup);
});

For you jQuery users out there - I am considering turning this into a plugin. I would like to hear from you what the expected markup should look like. For example, <a href="#" rel="[count]">tag</a> or <a href="#">tag ([count])</a>. Hopefully we can come up with something that doesn't completely violate the purpose of the rel tag, like that example! Thanks for your input!