Create unique string from id to build an link shortening system

Question

I want to build my own link shortening system. Therefore I need a way to create unique strings from the record ids stored in my database table.

So far I came up with this. I wonder if you now a faster or better idea? Or are there any caveats to my method?

// generate unique alphanumeric string from id with map
function idToString($id) { 
    $map = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; # 62 characters (a-z;A-Z;0-9)
    $string='';
    if ($id<62) return $map[$id]; // return immediately
    while ($id>0) { 
        if ($id%62>=0) {
            $string=$string.$map[$id%62];
            $id=intval($id/62); 
        }
    } 
    $string=strrev($string);     // Reverse string to emulate human reading
    return $string; 
}

// get integer ID back from a String
function stringToID($string) { 
    $map = str_split("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"); # same map as above of course
    $string=strrev($string);
    $string_array=str_split($string);
    $id=0;
    foreach ($string_array as $k=>$c) {
        $id=$id+(array_keys($map, $c)[0])*pow(62, $k);
    }
    return $id;
}

echo idToString(247698); // bcBi
echo stringToID('bcBi'); // 247698

Answer 1

I played with your code for a while, declared constants for your functions to use so that the static values didn't need to be regenerated with each call, added spacing around operators, curly braces for condition blocks, simplified expressions, reduced the total number of function calls, and generally made things more direct.

One point of concern is that you are using arithmetic to translate the values -- for this reason you will need to be wary of the upper limit for your system. It would be a good idea to throw an exception when your calculation breaks the int max limit. Also, scientific notation can monkey wrench things too. I used number_format() to prevent scientific notation while I was testing -- I don't know how much extra mileage this will grant you. This has been a fun rabbit hole to go down.

define('ALNUM_MAP', str_split('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'));
define('DIGIT_MAP', array_flip(ALNUM_MAP));

function idToString($id) {
    if ($id < 62) {
        return ALNUM_MAP[$id];
    }
    $string = '';
    while ($id) {
        $id = number_format($id, 0, '', '');
        $string = ALNUM_MAP[$id % 62] . $string;
        $id = (int)($id / 62); 
    }
    return $string;
}

function stringToID($string) {
    $id = 0;
    for ($i = strlen($string) - 1, $pow = 0; $i >= 0; --$i, ++$pow) {
        $id += DIGIT_MAP[$string[$i]] * (62 ** $pow);
    }
    return number_format($id, 0, '', '');
}

echo idToString(247698); // bcBi
echo "\n---\n";
echo stringToID('bcBi'); // 247698
echo "\n---\n";
//echo idToString(32611315596050636800); // M1ckM4ckUS4
//echo "\n---\n";
//echo stringToID('M1ckM4ckUS4'); // 32611315596050636800
//echo "\n---\n";
echo idToString(8483692923010050); // M1ckM4ckU
echo "\n---\n";
echo stringToID('M1ckM4ckU'); // 8483692923010050

---

That said, since you are starting with fully numeric values and you want to reduce their character count by converting to an alphanumeric string, then I have a far simpler way based on this answer that I post on Stack Overflow a couple years back. (Be sure that the incoming values are string-type, not integer-type.)

Code: (Demo)

define('ALNUM_MAP', str_split('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'));
define('DIGIT_MAP', array_flip(ALNUM_MAP));

function numToAlnum($num) {
    return strtr($num, ALNUM_MAP);
}

function alnumToNum($alphaNum) {
    return strtr($alphaNum, DIGIT_MAP);
}

$ids = ['4440', '464426', '43304441302845', '262018191701180', '273381111186152545352'];
foreach ($ids as $id) {
    $idLength = strlen($id);
    $alphaNum = numToAlnum($id);
    $alNumLength = strlen($alphaNum);
    $backToId = alnumToNum($alphaNum);
    var_export(['original' => $id, 'encoded' => $alphaNum, 'decoded' => $backToId, 'reduction' => $idLength - $alNumLength]);
    echo "\n---\n";
}

As stated in my SO post, using strtr() is a fantastic technique because it is designed to translate the longest substring that it can find as it traverses the input string. This translation operates on a different algorithm, so it will not give exactly the same length reduction as your technique, but it will not suffer from any numeric/math-based side-effects either.

Answer 2

Just for NIH (not invented here), have you considered using PHP implementations of base36 (case insensitive), base58 (avoids letters that can be confusing), or base64 implementations?

I'd probably have a check to avoid overflows (to avoid someone giving you "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb").

Likewise, what if someone gives you "_"? Or any other character not on the list.

You can avoid the strrev call by just using a for that starts at the back and goes back. That will avoid a string allocation and the str_split call also.

Answer 3

For generate random strings you can use the following function

function randomString($length = 20){
  return substr(str_shuffle("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"), 0, $length);
}
$length = 50;
echo randomString($length);
#output: mS0BVDsPYOo8qJEFtb14AlgQfM2puhUed7nvW3icaN5LTyZjXG

But this method, according with your volume, this kind of "unique string" could be repet, so to avoid this you could implement some method with uniqid() and rand() that will be using the internal clock of your server with a random number like:

echo uniqid(rand());
#output: 226705f222d686f83c

Answer 4

I came up with the idea to combine this with a small three digits checksum and a random map to stop others to just guess around with the shortlinks.

// generate unique alphanumeric string fom id with random map
function idToString($id) { 
    $map = "hV1gytRjWauClZ8EcKAsn0JpPeYwOHNv7dqiomT2fMxI5LFr93b4zkXGBU6SQD"; # 62 (a-z;A-Z;0-9) shuffled characters
    $string='';
    if ($id<62) return $map[$id].myChecksum($map[$id]); // return immediately
    while ($id>0) { 
        if ($id%62>=0) {
            $string=$string.$map[$id%62];
            $id=intval($id/62); 
        }
    } 
    $string=strrev($string);     // Reverse String to emulate human reading
    return $string.myChecksum($string); // add a checksum
}

// Function to get integer ID back from a String
function stringToID($string) {
    $map = str_split("hV1gytRjWauClZ8EcKAsn0JpPeYwOHNv7dqiomT2fMxI5LFr93b4zkXGBU6SQD"); #same map as above of course
    $positions=3; // how long are the checksum figures?
    $checksum=substr($string, -($positions), $positions); // last X character(s) is a checksum
    $string=substr($string, 0, -($positions));
    if ($checksum<>myChecksum($string)) return false; // checksums don't match
    $string=strrev($string);
    $string_array=str_split($string);
    $id=0;
    foreach ($string_array as $k=>$c) {
        $id=$id+(array_keys($map, $c)[0])*pow(62, $k);
    }
    return $id;
} 

// checksum
function myChecksum($string) {
    $positions=3; // how long are the checksum figures
    return substr(md5($string), 10, $positions); # just starting with the 10th position
}

echo idToString(10001); // 1msf22
echo stringToID('1msf22'); // 10001