Wie erstelle ich einen URL-Verkürzer?

Question

Ich möchte einen URL-Verkürzungsdienst erstellen, bei dem Sie eine lange URL in ein Eingabefeld eingeben können und der Dienst die URL auf "http://www.example.org/abcdef" verkürzt.

Anstelle von "abcdef" kann jeder andere String mit sechs Zeichen stehen, der a-z, A-Z und 0-9 enthält. Das ergibt etwa 56~57 Milliarden mögliche Zeichenfolgen.

Mein Ansatz:

Ich habe eine Datenbanktabelle mit drei Spalten:

1. id, integer, auto-inkrement
2. long, string, die lange URL, die der Benutzer eingegeben hat
3. short, string, die verkürzte URL (oder nur die sechs Zeichen)

Dann würde ich die lange URL in die Tabelle einfügen. Anschließend würde ich den Wert des Auto-Inkrement-Feldes "id" auswählen und daraus einen Hash erstellen. Dieser Hash sollte dann als "short" eingefügt werden. Aber welche Art von Hash sollte ich erstellen? Hash-Algorithmen wie MD5 erzeugen zu lange Zeichenfolgen. Diese Algorithmen verwende ich nicht, denke ich. Ein selbst entwickelter Algorithmus würde ebenfalls funktionieren.

Meine Idee:

Für "http://www.google.de/" erhalte ich die Auto-Inkrement-ID 239472. Dann führe ich die folgenden Schritte aus:

short = '';
if durch 2 teilbar, füge "a"+das Ergebnis zu short hinzu
if durch 3 teilbar, füge "b"+das Ergebnis zu short hinzu
... bis ich Teiler von a-z und A-Z habe.

Das könnte wiederholt werden, bis die Zahl nicht mehr teilbar ist. Glauben Sie, dass dies ein guter Ansatz ist? Haben Sie eine bessere Idee?

_{<em>Aufgrund des anhaltenden Interesses an diesem Thema habe ich eine effiziente Lösung auf GitHub veröffentlicht, mit Implementierungen für <a href="https://github.com/delight-im/ShortURL" rel="noreferrer">JavaScript</a>, <a href="https://github.com/delight-im/ShortURL/blob/master/PHP/ShortURL.php" rel="noreferrer">PHP</a>, <a href="https://github.com/delight-im/ShortURL/blob/master/Python/shorturl.py" rel="noreferrer">Python</a> und <a href="https://github.com/delight-im/ShortURL/blob/master/Java/ShortURL.java" rel="noreferrer">Java</a>. Fügen Sie Ihre Lösungen hinzu, wenn Sie möchten :)</em>}

Answer 1

Ich würde deinen Ansatz, Zahlen in Strings umzuwandeln, weiterverfolgen. Allerdings wirst du feststellen, dass dein vorgeschlagenes Algorithmus versagt, wenn deine ID eine Primzahl größer als 52 ist.

Theoretischer Hintergrund

Du brauchst eine Bijektive Funktion f. Dies ist notwendig, damit du eine Umkehrfunktion g('abc') = 123 für deine Funktion f(123) = 'abc' finden kannst. Das bedeutet:

• Es darf keine x1, x2 (mit x1 x2) geben, für die f(x1) = f(x2) gilt,
• und für jedes y musst du ein x finden können, so dass f(x) = y gilt.

Wie man die ID in eine gekürzte URL umwandelt

1. Denke an ein Alphabet, das du verwenden möchtest. In deinem Fall wäre das [a-zA-Z0-9]. Es enthält 62 Buchstaben.

2. Nimm einen automatisch generierten, eindeutigen numerischen Schlüssel (zum Beispiel die automatisch inkrementierte id einer MySQL-Tabelle).

   Für dieses Beispiel werde ich 125₁₀ (125 zur Basis 10) verwenden.

3. Jetzt musst du 125₁₀ in X₆₂ (Basis 62) umwandeln.

   125₁₀ = 2×621 + 1×620 = [2,1]

   Dafür musst du Ganzzahldivision und Modulo verwenden. Ein Pseudocode-Beispiel:

   digits = []
   
   while num > 0
     remainder = modulo(num, 62)
     digits.push(remainder)
     num = divide(num, 62)
   
   digits = digits.reverse

   Ordne jetzt die Indices 2 und 1 deinem Alphabet zu. So könnte deine Zuordnung (mit einem Array zum Beispiel) aussehen:

   0   a
   1   b
   ...
   25  z
   ...
   52  0
   61  9

   Mit 2 c und 1 b erhältst du cb₆₂ als gekürzte URL.

   http://shor.ty/cb

Wie man eine gekürzte URL in die ursprüngliche ID auflöst

Die Umkehrung ist noch einfacher. Du machst einfach eine Rückwärtssuche in deinem Alphabet.

1. e9a₆₂ wird als "4. , 61. und 0. Buchstabe im Alphabet" aufgelöst werden.

   e9a₆₂ = [4,61,0] = 4×622 + 61×621 + 0×620 = 19158₁₀

2. Finde jetzt deinen Datenbankeintrag mit WHERE id = 19158 und führe die Weiterleitung durch.

Beispielimplementierungen (bereitgestellt von Kommentatoren)

• C++
• Python
• Ruby
• Haskell
• C#
• CoffeeScript
• Perl

Answer 2

Warum würdest du einen Hash verwenden wollen?

Du kannst einfach eine einfache Übersetzung deines Auto-Inkrement-Werts in einen alphanumerischen Wert verwenden. Das kannst du leicht machen, indem du eine Basisumrechnung verwendest. Angenommen dein Zeichenraum (A-Z, a-z, 0-9, etc.) hat 62 Zeichen, konvertiere die ID in eine Basis-40 Zahl und nutze die Zeichen als Ziffern.

Answer 3

public class UrlShortener {
    private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static final int BASE = ALPHABET.length();

    public static String encode(int num) {
        StringBuilder sb = new StringBuilder();
        while ( num > 0 ) {
            sb.append( ALPHABET.charAt( num % BASE ) );
            num /= BASE;
        }
        return sb.reverse().toString();   
    }

    public static int decode(String str) {
        int num = 0;
        for ( int i = 0; i < str.length(); i++ )
            num = num * BASE + ALPHABET.indexOf(str.charAt(i));
        return num;
    }   
}

Answer 4

Nicht eine Antwort auf Ihre Frage, aber ich würde keine Groß- und Kleinschreibung sensitiven verkürzten URLs verwenden. Sie sind schwer zu merken, meistens unleserlich (viele Schriftarten stellen 1 und l, 0 und O und andere Zeichen sehr ähnlich dar, dass sie fast unmöglich zu unterscheiden sind) und fehleranfällig. Versuchen Sie, nur Klein- oder Großbuchstaben zu verwenden.

Versuchen Sie außerdem, ein Format zu haben, in dem Sie die Zahlen und Zeichen in einer vordefinierten Form mischen. Studien zeigen, dass Menschen dazu neigen, eine Form besser zu merken als andere (denken Sie an Telefonnummern, wo die Zahlen in einer bestimmten Form gruppiert sind). Versuchen Sie etwas wie z.B. num-char-char-num-char-char. Ich weiß, dass dies die Kombinationsmöglichkeiten verringern wird, besonders wenn Sie keine Groß- und Kleinbuchstaben haben, aber es wäre benutzerfreundlicher und daher nützlicher.

Answer 5

Mein Ansatz: Nehmen Sie die Datenbank-ID, dann Base36 Encode sie. Ich würde NICHT sowohl Groß- ALS AUCH Kleinbuchstaben verwenden, denn das macht die Übertragung dieser URLs über das Telefon zu einem Albtraum, aber Sie könnten die Funktion natürlich leicht erweitern, um ein Basis-62-En-/Decoder zu sein.