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

Question

Я хочу создать службу сокращения 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 . Добавьте ваши решения, если вам нравится:)}

Answer 1

Вот реализация Node.js, которая, вероятно, будет bit.ly. генерировать очень случайную строку из семи символов.

Он использует криптографию Node.js для генерации очень случайного набора из 25 символов вместо случайного выбора семи символов.

var crypto = require("crypto");
exports.shortURL = new function () {
    this.getShortURL = function () {
        var sURL = '',
            _rand = crypto.randomBytes(25).toString('hex'),
            _base = _rand.length;
        for (var i = 0; i < 7; i++)
            sURL += _rand.charAt(Math.floor(Math.random() * _rand.length));
        return sURL;
    };
}

Answer 2

Качественное решение Node.js / JavaScript см. В модуле id-shorttener , который тщательно протестирован и уже несколько месяцев используется в производстве.

Он обеспечивает эффективное сокращение идентификатора / URL, поддерживаемое сменным хранилищем по умолчанию Redis , и вы даже можете настроить свой набор символов короткого идентификатора и определить, является ли сокращение 10000 * idempotent . Это важное различие, которое учитывают не все средства сокращения URL.

По отношению к другим ответам здесь, этот модуль реализует превосходный принятый ответ Марселя Джекверта выше.

Основу решения обеспечивает следующий фрагмент Redis Lua :

local sequence = redis.call('incr', KEYS[1])

local chars = '0123456789ABCDEFGHJKLMNPQRSTUVWXYZ_abcdefghijkmnopqrstuvwxyz'
local remaining = sequence
local slug = ''

while (remaining > 0) do
  local d = (remaining % 60)
  local character = string.sub(chars, d + 1, d + 1)

  slug = character .. slug
  remaining = (remaining - d) / 60
end

redis.call('hset', KEYS[2], slug, ARGV[1])

return slug

Answer 3

My Python 3 версия

base_list = list("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
base = len(base_list)

def encode(num: int):
    result = []
    if num == 0:
        result.append(base_list[0])

    while num > 0:
        result.append(base_list[num % base])
        num //= base

    print("".join(reversed(result)))

def decode(code: str):
    num = 0
    code_list = list(code)
    for index, code in enumerate(reversed(code_list)):
        num += base_list.index(code) * base ** index
    print(num)

if __name__ == '__main__':
    encode(341413134141)
    decode("60FoItT")

Answer 4

/**
 * <p>
 *     Integer to character and vice-versa
 * </p>
 *  
 */
public class TinyUrl {

    private final String characterMap = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private final int charBase = characterMap.length();

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

        while (num > 0){
            sb.append(characterMap.charAt(num % charBase));
            num /= charBase;
        }

        return sb.reverse().toString();
    }

    public int covertToInteger(String str){
        int num = 0;
        for(int i = 0 ; i< str.length(); i++)
            num += characterMap.indexOf(str.charAt(i)) * Math.pow(charBase , (str.length() - (i + 1)));

        return num;
    }
}

class TinyUrlTest{

    public static void main(String[] args) {
        TinyUrl tinyUrl = new TinyUrl();
        int num = 122312215;
        String url = tinyUrl.covertToCharacter(num);
        System.out.println("Tiny url:  " + url);
        System.out.println("Id: " + tinyUrl.covertToInteger(url));
    }
}

Answer 5

Очень хороший ответ, я создал реализацию bjf на Golang:

package bjf

import (
    "math"
    "strings"
    "strconv"
)

const alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

func Encode(num string) string {
    n, _ := strconv.ParseUint(num, 10, 64)
    t := make([]byte, 0)

    /* Special case */
    if n == 0 {
        return string(alphabet[0])
    }

    /* Map */
    for n > 0 {
        r := n % uint64(len(alphabet))
        t = append(t, alphabet[r])
        n = n / uint64(len(alphabet))
    }

    /* Reverse */
    for i, j := 0, len(t) - 1; i < j; i, j = i + 1, j - 1 {
        t[i], t[j] = t[j], t[i]
    }

    return string(t)
}

func Decode(token string) int {
    r := int(0)
    p := float64(len(token)) - 1

    for i := 0; i < len(token); i++ {
        r += strings.Index(alphabet, string(token[i])) * int(math.Pow(float64(len(alphabet)), p))
        p--
    }

    return r
}

Размещено на github: https://github.com/xor-gate/go-bjf

Answer 6

У меня есть вариант проблемы в том, что я храню веб-страницы от разных авторов и должен предотвращать обнаружение страниц путем догадок. Поэтому мои короткие URL-адреса добавляют пару дополнительных цифр к строке Base-62 для номера страницы. Эти дополнительные цифры генерируются из информации в самой записи страницы, и они гарантируют, что только 1 из 3844 URL-адресов являются действительными (при условии 2-значный Base-62). Описание схемы можно посмотреть на http://mgscan.com/MBWL.

Answer 7

Почему бы просто не перевести свой идентификатор в строку? Вам просто нужна функция, которая отображает цифру, скажем, от 0 до 61 в одну букву (верхний / нижний регистр) или цифру. Затем примените это для создания, скажем, четырехбуквенных кодов, и вы получите 14,7 миллионов URL-адресов.