Blog geekesque... ou pas

Principe de base

Le principe est extrèmement simple: les urls sont enregistrées dans une base de données et on encode leur id unique dans une base plus grande (base 10 => base 62) afin de diminuer la taille des urls.

Lors de l'accès à cette url, on décode le paramètre ce qui permet de retrouver l'id de l'url et donc de faire la redirection comme il faut.

base 62

En utilisant la base 62, on peut exploiter 62 caractères simples pour représenter une valeur, ce qui permet de réduire grandement la taille.

Par exemple, il faut 9 caractères pour afficher 537688254, alors qu'une fois converti on en a plus que 5 (Ao5hc). La plupart des systèmes de raccourcissement utilisent 6 caractères, ce qui permet d'aller jusqu'à l'id 56800235583 (11 caractères).

Conversion

La petite classe suivante permet de faire de l'encodage/décodage dans toutes les bases de 2 à 62.

<?php
/**
 * Base n encode /decode
 * @author CrazyCat
 * @package Mephisto::Maths
 */
class NBase {
 
    /**
     * Array of chars to use
     * @var array
     */
    private $vals = array(
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
        'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'
    );
 
    /*
     * Base to use
     * @var int
     */
    private $base = 10;
 
    /**
     * Constructor
     * @param int $n Base to use
     */
    public function __construct($n=10) {
        $this->setBase($n);
    }
 
    /**
     * Sets the destination base
     * @param int $n Base to use
     */
    public function setBase($n=10) {
        if ($n < 2 || $n > count($this->vals)) {
            $n = count($this->vals);
        }
        $this->base = $n;
    }
 
    /**
     * Gets the destination base
     * @return int
     */
    public function getBase() {
        return $this->base;
    }
 
    /**
     * Encodes integer to new base
     * @param integer $b10 Integer in base 10
     * @return string
     */
    public function encode($b10) {
        $bn = '';
        $current = $b10;
        while($current > 0) {
            $rest = $this->modulo($current, $this->base);
            $bn .= $this->vals[$rest];
            $current = floor($current/$this->base);
        }
        return strrev($bn);
    }
 
    /**
     * Decodes string from base
     * @param string $bn String in base n
     * @return integer
     */
    function decode($bn) {
        $bn = strrev($bn);
        $b10 = 0;
        for($i=0; $i<strlen($bn); $i++) {
            $item = substr($bn, $i, 1);
            $pos = array_search($item, $this->vals);
            $b10 += $pos * pow($this->base, $i);
        }
        return $b10;
    }
 
    /**
     * Calculates a modulus
     * To use because native "%" is buggy
     * for big values
     * @param integer $val
     * @param integer $div Divisor
     * @return integer remainder
     */
    function modulo($val, $div) {
        $r = $val - (floor($val/$div)*$div);
        return $r;
    }
}
?>

Fonction modulo

Il y a un souci de limites d'utilisation du calcul de modulo en php ($val%$div) qui retourne de mauvaises valeurs lorsqu'on traite de grands chiffres. C'est pourquoi la fonction est ajoutée dans la classe et est utilisée dans la fonction encode.

Utilisation

L'utilisation est fort simple:

<?php
// Test to get 'ZZZZZZ'
$test = 56800235583;
$bn = new NBase(62);
$try1 = $bn->encode($test);
$try2 = $bn->decode($try1);
echo $test, ' gives in base ', $bn->getBase(), ': ', $try1, ' decoded as ', $try2, '<br />';
// Another test, converting 4096 in bases 62, 16 (hexa) and 2 (binary)
$test = 4096;
$bn = new NBase(62);
$try1 = $bn->encode($test);
$try2 = $bn->decode($try1);
echo $test, ' gives in base ', $bn->getBase(), ': ', $try1, ' decoded as ', $try2, '<br />';
$bn->setBase(16);
$try1 = $bn->encode($test);
$try2 = $bn->decode($try1);
echo $test, ' gives in base ', $bn->getBase(), ': ', $try1, ' decoded as ', $try2, '<br />';
$bn->setBase(2);
$try1 = $bn->encode($test);
$try2 = $bn->decode($try1);
echo $test, ' gives in base ', $bn->getBase(), ': ', $try1, ' decoded as ', $try2, '<br />';
?>