Как мне создать сокращатель URL? - PullRequest
Новая
       38

Как мне создать сокращатель URL?

625 голосов
/ 12 апреля 2009

Я хочу создать службу сокращения URL-адресов, в которой вы можете записать длинный URL-адрес в поле ввода, а служба сокращает URL-адрес до «http://www.example.org/abcdef».

Вместо "abcdef" может быть любая другая строка из шести символов, содержащая a-z, A-Z and 0-9. Это составляет 56 ~ 57 миллиардов возможных строк.

Мой подход:

У меня есть таблица базы данных с тремя столбцами:

  1. идентификатор, целое число, автоинкремент
  2. long, string, long URL, введенный пользователем
  3. short, string, сокращенный URL (или только шесть символов)

Я бы тогда вставил длинный URL в таблицу. Затем я выбрал бы значение автоинкремента для "id" и построил его хеш. Этот хэш должен быть вставлен как "short". Но какой хеш я должен создать? Алгоритмы хеширования, такие как MD5, создают слишком длинные строки. Я не использую эти алгоритмы, я думаю. Будет работать и самосозданный алгоритм.

Моя идея:

Для "http://www.google.de/" я получаю идентификатор автоинкремента 239472. Затем я делаю следующие шаги: 

short = '';
if divisible by 2, add "a"+the result to short
if divisible by 3, add "b"+the result to short
... until I have divisors for a-z and A-Z.

Это может повторяться до тех пор, пока число больше не будет делиться. Как вы думаете, это хороший подход? У тебя есть идея получше?

Из-за постоянного интереса к этой теме я опубликовал эффективное решение для GitHub с реализациями для JavaScript , PHP , Python и Java . Добавьте ваши решения, если вам нравится:)

Ответы [ 27 ]

767 голосов
/ 12 апреля 2009

Я бы продолжил ваш подход "конвертировать число в строку". Тем не менее, вы поймете, что ваш предложенный алгоритм не работает, если ваш идентификатор простое число и больше, чем 52 .

Теоретический фон

Вам нужна Биективная функция f . Это необходимо для того, чтобы вы могли найти обратную функцию g ('abc') = 123 для вашей f (123) = 'abc' функции. Это значит:

  • Не должно быть x1, x2 (с x1 ≠ x2) , которое составит f (x1) = f (x2) ,
  • и для каждого y вы должны быть в состоянии найти x , чтобы f (x) = y .

Как преобразовать идентификатор в сокращенный URL

  1. Подумайте об алфавите, который мы хотим использовать. В вашем случае это [a-zA-Z0-9]. Содержит 62 буквы .

  2. Возьмите автоматически сгенерированный, уникальный числовой ключ (например, с автоинкрементом id таблицы MySQL).

    В этом примере я буду использовать 125 10 (125 с основанием 10).

  3. Теперь вам нужно конвертировать 125 10 в X 62 (база 62).

    125 10 = 2 × 62 1 + 1 × 62 0 = [2,1]

    Это требует использования целочисленного деления и по модулю. Пример псевдокода: 

    digits = []

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

digits = digits.reverse

    Теперь сопоставьте индексы 2 и 1 с вашим алфавитом. Вот как может выглядеть ваше отображение (например, с массивом): 

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

    С 2 → c и 1 → b вы получите cb 62 в качестве сокращенного URL. 

    http://shor.ty/cb

Как преобразовать сокращенный URL в начальный идентификатор

Обратное еще проще. Вы просто делаете обратный поиск в вашем алфавите.

  1. e9a 62 будет преобразовано в "4-ю, 61-ю и 0-ю букву в алфавите".

    e9a 62 = [4,61,0] = 4 × 62 2 + 61 × 62 1 + 0 × 62 0 = 19158 10

  2. Теперь найдите вашу базу данных с помощью WHERE id = 19158 и выполните перенаправление.

Некоторые реализации (предоставлены комментаторами)

53 голосов
/ 12 апреля 2009

Зачем вам использовать хеш?

Вы можете просто использовать простой перевод значения автоинкремента в буквенно-цифровое значение. Вы можете сделать это легко с помощью некоторого базового преобразования. Допустим, у вас есть место для символов (A-Z, a-z, 0-9 и т. Д.), Состоящее из 40 символов, преобразуйте идентификатор в число base-40 и используйте символы в качестве цифр.

47 голосов
/ 11 июля 2012 
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;
    }   
}
32 голосов
/ 12 апреля 2009

Не ответ на ваш вопрос, но я бы не стал использовать сокращенные URL-адреса с учетом регистра. Их трудно запомнить, как правило, нечитаемые (многие шрифты отображают 1 и l, 0 и O и другие символы очень похожи, так что почти невозможно различить их) и подвержены прямым ошибкам. Попробуйте использовать только нижний или верхний регистр.

Кроме того, попробуйте использовать формат, в котором вы смешиваете цифры и символы в заранее определенной форме. Существуют исследования, которые показывают, что люди, как правило, запоминают одну форму лучше, чем другие (например, номера телефонов, где номера сгруппированы в определенной форме). Попробуйте что-то вроде num-char-char-num-char-char. Я знаю, что это уменьшит комбинации, особенно если у вас нет прописных и строчных букв, но это было бы более удобно и поэтому полезно.

27 голосов
/ 14 апреля 2009

Мой подход: взять идентификатор базы данных, затем Base36 кодировать его . Я НЕ буду использовать как заглавные, так и строчные буквы, потому что это делает передачу этих URL-адресов по телефону кошмаром, но вы, конечно, можете легко расширить эту функцию до базового 62 en / decoder.

8 голосов
/ 05 ноября 2011

Вот мой класс PHP 5. 

<?php
class Bijective
{
    public $dictionary = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

    public function __construct()
    {
        $this->dictionary = str_split($this->dictionary);
    }

    public function encode($i)
    {
        if ($i == 0)
        return $this->dictionary[0];

        $result = '';
        $base = count($this->dictionary);

        while ($i > 0)
        {
            $result[] = $this->dictionary[($i % $base)];
            $i = floor($i / $base);
        }

        $result = array_reverse($result);

        return join("", $result);
    }

    public function decode($input)
    {
        $i = 0;
        $base = count($this->dictionary);

        $input = str_split($input);

        foreach($input as $char)
        {
            $pos = array_search($char, $this->dictionary);

            $i = $i * $base + $pos;
        }

        return $i;
    }
}
5 голосов
/ 23 января 2018

Решение Node.js и MongoDB

Поскольку нам известен формат, который MongoDB использует для создания нового ObjectId с 12 байтами.

  • 4-байтовое значение, представляющее секунды с начала эпохи Unix,
  • 3-байтовый идентификатор машины,
  • 2-байтовый идентификатор процесса
  • 3-байтовый счетчик (на вашем компьютере), начиная со случайного значения.

Пример (я выбираю случайную последовательность) a1b2c3d4e5f6g7h8i9j1k2l3

  • a1b2c3d4 представляет секунды с начала эпохи Unix,
  • 4e5f6g7 представляет идентификатор машины,
  • h8i9 представляет идентификатор процесса
  • j1k2l3 представляет счетчик, начиная со случайного значения.

Поскольку счетчик будет уникальным, если мы храним данные на одной машине, мы можем получить их без сомнений, что они будут повторяться.

Таким образом, короткий URL будет счетчиком , и здесь приведен фрагмент кода, предполагающий, что ваш сервер работает нормально. 

const mongoose = require('mongoose');
const Schema = mongoose.Schema;

// Create a schema
const shortUrl = new Schema({
    long_url: { type: String, required: true },
    short_url: { type: String, required: true, unique: true },
  });
const ShortUrl = mongoose.model('ShortUrl', shortUrl);

// The user can request to get a short URL by providing a long URL using a form

app.post('/shorten', function(req ,res){
    // Create a new shortUrl */
    // The submit form has an input with longURL as its name attribute.
    const longUrl = req.body["longURL"];
    const newUrl = ShortUrl({
        long_url : longUrl,
        short_url : "",
    });
    const shortUrl = newUrl._id.toString().slice(-6);
    newUrl.short_url = shortUrl;
    console.log(newUrl);
    newUrl.save(function(err){
        console.log("the new URL is added");
    })
});
4 голосов
/ 09 марта 2013

C # версия: 

public class UrlShortener 
{
    private static String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static int    BASE     = 62;

    public static String encode(int num)
    {
        StringBuilder sb = new StringBuilder();

        while ( num > 0 )
        {
            sb.Append( ALPHABET[( num % BASE )] );
            num /= BASE;
        }

        StringBuilder builder = new StringBuilder();
        for (int i = sb.Length - 1; i >= 0; i--)
        {
            builder.Append(sb[i]);
        }
        return builder.ToString(); 
    }

    public static int decode(String str)
    {
        int num = 0;

        for ( int i = 0, len = str.Length; i < len; i++ )
        {
            num = num * BASE + ALPHABET.IndexOf( str[(i)] ); 
        }

        return num;
    }   
}
4 голосов
/ 18 января 2011

Вы можете хэшировать весь URL, но если вы просто хотите сократить идентификатор, сделайте, как предложил Марсель. Я написал эту реализацию Python:

https://gist.github.com/778542

3 голосов
/ 20 декабря 2011 
// simple approach

$original_id = 56789;

$shortened_id = base_convert($original_id, 10, 36);

$un_shortened_id = base_convert($shortened_id, 36, 10);
Страница:
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...