読者です 読者をやめる 読者になる 読者になる

モノノフ日記

普通の日記です

タグクラウドのアルゴリズム

php

タグクラウドを生成する際のアルゴリズムをオープンソースのコードを参考にして現在考えてます。

symfony公式サイトで見つけたアルゴリズム

<?php
  while ($rs->next())
  {
    if (!$max_popularity)
    {
      $max_popularity = $rs->getInt('count');
    }
 
    $tags[$rs->getString('tag')] = floor(($rs->getInt('count') / $max_popularity * 3) + 1);
  }

すごいシンプルでびっくり。

処理の流れ

  1. タグの最大カウント数をmax_popularityとする
  2. 各タグのカウント数をmax_popularityで割り、タグクラウドの範囲から1引いた値をかける(ここでは3)
  3. 算出された値を切り上げて、0が無くなるように+1

この算出アルゴリズムだと最大の大きさを持つタグは1つだけで、それに小さいタグが群がる感じになります。
ただカウント数の差が大きいと最大の大きさのタグに最小のタグがわらわらと群がるので見た目のバランスが悪くなりました。

もっと平均的に振り分ける方法ないのかなと探してたら、タグクラウドのアルゴリズム (それなりブログ)を発見。

【最も基本的なアルゴリズム】

* 最終的に、各タグの大きさは25段階の範囲で区分される。ソース内ではこれを level と読んでおり、0-24の範囲で指定している。
* level算出方法は以下の通り
1. 最もタグ付けされている回数が多いタグの回数を取得し、それの平方根を求める。以後この値を max と呼ぶ。
2. 最もタグ付けされている回数が少ないタグの回数を取得し、それの平方根を求める。以後この値を min と呼ぶ。
3. max - min の間を均等に 25段階に分け、各タグのタグ付け回数の平方根の値が、その範囲のどこに位置するのかを求め、それが level となる。

http://kjirou.sakura.ne.jp/mt/2007/09/post_57.html

そうか、平方根使えばよかったのかと納得。

追記

PEARのHTML_Tagcloudのソースも見てみた。htmlタグを生成してるところだけ抜粋。

<?php
    private function _buidHTMLTags($param)
    {
        $this->total = count($this->_elements);
        // no tags elements
        if($this->total == 0){
            return array();
        }elseif($this->total == 1){
            $tag = $this->_elements[0];
            return $this->_createHTMLTag($tag, 'latest', $this->baseFontSize);
        }

        $limit = array_key_exists('limit', $param) ? $param['limit'] : 0;
        $this->_sortTags($limit);
        $this->_calcMumCount();
        $this->_calcMumEpoc();

        $range = $this->maxFontSize - $this->minFontSize;
        if($this->_max != $this->_min){
            $this->_factor = $range / (sqrt($this->_max) - sqrt($this->_min));
        }else{
            $this->_factor = 1;
        }

        if($this->_maxEpoc != $this->_minEpoc){
            $this->_epocFactor = count($this->epocLevel)
                                    / (sqrt($this->_maxEpoc) - sqrt($this->_minEpoc));
        }else{
        $rtn = array();
        foreach ($this->_elements as $tag) {
            $countLv = $this->_getCountLevel($tag['count']);
            if (! isset($tag['timestamp']) || empty($tag['timestamp'])) {
                $epocLv = count($this->epocLevel) - 1;
            } else {
                $epocLv  = $this->_getEpocLevel($tag['timestamp']);
            }
            $colorType = $this->epocLevel[$epocLv];
            $fontSize  = $this->minFontSize + $countLv;
            $rtn[] = $this->_createHTMLTag($tag, key($colorType), $fontSize);
        }
        return implode("", $rtn);
    }

やっぱ最大値/最小値の平方根の差を使って係数出してますね。
ただ最大値/最小値の値がタグのカウント数以外に、タイムスタンプも使ってるのが興味深い。タグの新鮮度でもレベル付けできるよってことですね。

しかし、_buidHTMLTagsってのはtypoだよね。すごい気になったw