Při návrhu vlastního zkracovače URL, obdoby služby bit.ly, jsem napsal jednoduchý algoritmus výpočtu zkrácené URL, o který bych se rád podělil.

Zkrácená URL mají smysl tam, kde:

  1. Je omezen prostor pro text, například na Twitteru, který poskytuje jen 140 znaků pro příspěvek
  2. Při generování QR kódů. Kratší URL bude mít jednodušší QR kód
  3. Chceme jednotný systém pro sdílení URL a monitorování jejich prokliků a refererů

Smyslem algoritmu je získat url ve tvaru velmi podobném jako využívá služba bit.ly, tedy například bit.ly/tvAskx, jako zkrácenina pro http://www.tomas-dvorak.cz.

Systém zkrácených URL jsem postavil na několika krocích:

  1. Vložení url ke zkrácení do databáze, získání unikátního ID, pomocí autoincrement pole v tabulce či jinak. Tabulka má jednoduchou strukturu o dvou sloupcích: _autoincrement-ID_ | _original-url_
  2. Převedení tohoto číselného ID na tvar obdobný službě bit.ly (funkce #toCode(long value) )
  3. Sdílení linku ve tvaru domena.tld/_hash_
  4. Po kliknutí na link a spuštění obslužného kódu (není zde uveden) převedení hashe zpět na číslo (funkce #fromCode(String hash) )
  5. Dohledání správné URL v databázi, která má ID odpovídající získanému číslu
  6. Redirect na zjištěnou kompletní URL
package com.ivitera.examples;

public class ShortUrlsUtils {
    public static final String ALPHABET =
            "0123456789" +
            "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
            "abcdefghijklmnopqrstuvwxyz";


    public static String toCode(long value) {
        int radix = ALPHABET.length();
        StringBuilder builder = new StringBuilder();
        do {
            builder.insert(0, ALPHABET.charAt((int) value % radix));
            value = value / radix;
        }
        while (value > 0);
        return builder.toString();
    }

    public static long fromCode(String s) {
        int radix = ALPHABET.length();
        s = s.trim();
        int pos = 0;
        long result = 0;
        while (pos < s.length() && !Character.isWhitespace(s.charAt(pos))) {
            String digit = s.substring(pos, pos + 1);
            int i = ALPHABET.indexOf(digit);
            if (i >= 0 && i < radix) {
                result *= radix;
                result += i;
                pos++;
            }
        }
        return result;
    }
}

Utilita tedy převádí číselnou hodnotu v desítkové soustavě do nové soustavy založené na definované abecedě. Pro představu několik vzorových převodů:

Hodnota v desítkové soustavě    Zkrácený kód
1234 Ju
555555 2KWZ
123456789 8M0kX

Úspora délky je výrazná, více ukáže tabulka pro různé délky kódů:

Délka kódu v nové soustavě (vypočtený hash)    Délka v původní desítkové soustavě    Počet ušetřených znaků    Počet všech kombinací znaků o této délce (jaké maximální číslo jde zakódovat na daný počet znaků hashe)
1 2 1 62
2 4 2 3844
3 6 3 238328
4 8 4 14776336
5 9 4 916132832
6 11 5 56800235584
7 13 6 3521614606208
8 15 7 218340105584896
9 17 8 13537086546263552
10 18 8 839299365868340224

Tedy pro ID 839299365868340224 v desítkové soustavě získáme kód zzzzzzzzzz. Ušetřili jsme tak 8 znaků.

Pokud bychom chtěli sledovat, odkud byla zkrácená URL prokliknuta a kolikrát, bylo by nutné před samotným přesměrováním na cílovou adresu (krok 6) provést záznam refereru a zvýšení počtu návštěv do nějakého systému pro záznam statistik.

Celý proces zkrácení URL a jejího použití by pak mohl vypadat takto:

  1. Chci zkrátit URL, například http://www.tomas-dvorak.cz/kategorie/Internet/. V databázi mám vloženo již 12577 adres, které byly zkráceny. Vložím tedy tuto a vím, že její ID je 12578.
  2. Převedu ID 12578 na zkrácenou formu, hash. Převodem metodou #toCode(12578) získám hash 3Gs
  3. Link, který budu dále sdílet je domena.tld/3Gs
  4. Po kliknutí na link a spuštění obslužného kódu (není zde uveden) převedu hash 3Gs zpět na ID, tedy zavolám funkci #fromCode(„3Gs“) a získám ID 12578.
  5. Dohledání správné URL v databázi, která má ID odpovídající získanému číslu 12578, výsledkem je původní adresa http://www.tomas-dvorak.cz/kategorie/Internet/
  6. Pošlu HTTP redirect na zjištěnou kompletní URL http://www.tomas-dvorak.cz/kategorie/Internet/