Как говорили другие, переполнение кэша с параметром запроса обычно считается плохой идеей (tm) и длится долгое время. Лучше отразить версию в имени файла. Html5 Boilerplate рекомендует против , используя строку запроса, среди прочих.
Тем не менее, из рекомендаций, которые я видел, которые цитировали источник, все, кажется, берут свою мудрость из Статья 2008 года от Стива Соудера. Его выводы основаны на поведении прокси в то время, и они могут или не могут быть актуальными в наши дни. Тем не менее, при отсутствии более текущей информации изменение имени файла является безопасным вариантом.
Я бы продолжил ваш подход «преобразовать число в строку». Однако вы поймете, что ваш предложенный алгоритм терпит неудачу, если ваш идентификатор является простым и большим, чем 52 .
Вам нужен Bijective Функция f . Это необходимо, чтобы вы могли найти обратную функцию g ('abc') = 123 для функции f (123) = 'abc' . Это означает:
[a-zA-Z0-9]
. Он содержит 62 буквы . id
таблицы MySQL). В этом примере я буду использовать 12510 (125 с базой 10). [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 вы получите cb62 как сокращенный URL. http://shor.ty/cb
. Реверс еще проще. Вы просто выполняете обратный поиск в своем алфавите.
[4,61,0]
= 4 × 622 + 61 × 621 + 0 × 620 = 1915810 WHERE id = 19158
и выполните перенаправление. Реализация в Scala:
class Encoder(alphabet: String) extends (Long => String) {
val Base = alphabet.size
override def apply(number: Long) = {
def encode(current: Long): List[Int] = {
if (current == 0) Nil
else (current % Base).toInt :: encode(current / Base)
}
encode(number).reverse
.map(current => alphabet.charAt(current)).mkString
}
}
class Decoder(alphabet: String) extends (String => Long) {
val Base = alphabet.size
override def apply(string: String) = {
def decode(current: Long, encodedPart: String): Long = {
if (encodedPart.size == 0) current
else decode(current * Base + alphabet.indexOf(encodedPart.head),encodedPart.tail)
}
decode(0,string)
}
}
Пример теста с тестом Scala:
import org.scalatest.{FlatSpec, Matchers}
class DecoderAndEncoderTest extends FlatSpec with Matchers {
val Alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
"A number with base 10" should "be correctly encoded into base 62 string" in {
val encoder = new Encoder(Alphabet)
encoder(127) should be ("cd")
encoder(543513414) should be ("KWGPy")
}
"A base 62 string" should "be correctly decoded into a number with base 10" in {
val decoder = new Decoder(Alphabet)
decoder("cd") should be (127)
decoder("KWGPy") should be (543513414)
}
}
Я продолжаю увеличивать целую последовательность для каждого домена в базе данных и использовать Hashids для кодирования целого числа в URL-адрес.
static hashids = Hashids(salt = "my app rocks", minSize = 6)
Я запустил скрипт, чтобы посмотреть, сколько времени потребуется, пока он не исчерпает длину символа. Для 6 символов он может использовать 164,916,224
ссылки, а затем до 7 символов. Бит использует 7 символов. Менее 5 символов выглядит странно для меня.
Hashids может декодировать путь URL обратно к целому числу, но более простым решением является использование всей короткой ссылки sho.rt/ka8ds3
в качестве первичного ключа.
Вот полная концепция:
function addDomain(domain) {
table("domains").insert("domain", domain, "seq", 0)
}
function addURL(domain, longURL) {
seq = table("domains").where("domain = ?", domain).increment("seq")
shortURL = domain + "/" + hashids.encode(seq)
table("links").insert("short", shortURL, "long", longURL)
return shortURL
}
// GET /:hashcode
function handleRequest(req, res) {
shortURL = req.host + "/" + req.param("hashcode")
longURL = table("links").where("short = ?", shortURL).get("long")
res.redirect(301, longURL)
}
Если вы не хотите повторно изобретать колесо ... http://lilurl.sourceforge.net/
Не ответ на ваш вопрос, но я бы не использовал уменьшенные URL-адреса с учетом регистра. Их трудно запомнить, обычно нечитабельно (многие шрифты визуализируют 1 и 1, 0 и O и другие персонажи очень похожи, что почти невозможно сказать разницу) и прямой склонностью к ошибкам. Попробуйте использовать только нижний или верхний регистр.
Также попробуйте иметь формат, в котором вы смешиваете числа и символы в предопределенной форме. Существуют исследования, которые показывают, что люди, как правило, помнят одну форму лучше других (подумайте о телефонах, где номера сгруппированы в определенной форме). Попробуйте что-то вроде num-char-char-num-char-char. Я знаю, что это приведет к снижению комбинаций, особенно если у вас нет верхнего и нижнего регистра, но он будет более удобным и, следовательно, полезным.
Вы можете использовать весь URL, но если вы просто хотите сократить идентификатор, сделайте так, как предположил Марсель. Я написал эту реализацию python:
Почему бы просто не перевести свой идентификатор на строку? Вам просто нужна функция, которая отображает цифру между, скажем, 0 и 61, на одну букву (верхний / нижний регистр) или цифру. Затем примените это, чтобы создать, скажем, 4-буквенные коды, и у вас есть 14.7 миллионов URL-адресов.
Это то, что я использую:
# Generate a [0-9a-zA-Z] string
ALPHABET = map(str,range(0, 10)) + map(chr, range(97, 123) + range(65, 91))
def encode_id(id_number, alphabet=ALPHABET):
"""Convert an integer to a string."""
if id_number == 0:
return alphabet[0]
alphabet_len = len(alphabet) # Cache
result = ''
while id_number > 0:
id_number, mod = divmod(id_number, alphabet_len)
result = alphabet[mod] + result
return result
def decode_id(id_string, alphabet=ALPHABET):
"""Convert a string to an integer."""
alphabet_len = len(alphabet) # Cache
return sum([alphabet.index(char) * pow(alphabet_len, power) for power, char in enumerate(reversed(id_string))])
Это очень быстро и может принимать длинные целые числа.
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;
}
}
Поскольку мы знаем формат, который mongodb использует для создания нового ObjectId с 12 байтами.
Пример (я выбираю случайную последовательность) a1b2c3d4e5f6g7h8i9j1k2l3
Поскольку счетчик будет уникальным, если мы будем хранить данные на одной машине, мы можем получить его без каких-либо сомнений, что он будет дублироваться.
Таким образом, короткий 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");
})
});
Для качественного решения NodeJS / Javascript см. модуль id-shortener , который тщательно протестирован и использовался в производстве в течение нескольких месяцев.
Он обеспечивает эффективный идентификатор / url shorter, поддерживаемый подключаемым хранилищем, по умолчанию используется redis, и вы даже можете настроить свой короткий набор символов id, и будет ли сокращение 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
У меня есть вариант проблемы, потому что я храню веб-страницы от разных авторов и должен предотвратить открытие страниц путем догадок. Поэтому мои короткие URL-адреса добавляют пару дополнительных цифр в строку Base-62 для номера страницы. Эти дополнительные цифры генерируются из информации в самой записи страницы, и они гарантируют, что только 1 из 3844 URL-адресов являются действительными (при условии, что 2-значный Base-62). Вы можете увидеть описание схемы в http://mgscan.com/MBWL .
Вот реализация Node.js, которая, скорее всего, будет bit.ly. генерируют очень случайную 7-значную строку. используя криптографию Node.js для генерации высоко случайных 25 символов, чем случайный выбор 7 символов.
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;
};
}
/**
* <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));
}
}
Очень хороший ответ, я создал Golang реализацию bjf:
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
Для аналогичного проекта, чтобы получить новый ключ, я создаю функцию-обертку вокруг генератора случайных строк , который вызывает генератор, пока я не получу строку, которая еще не была использована в моей хэш-таблице , Этот метод будет замедляться, как только ваше пространство имен начнет заполняться, но, как вы уже сказали, даже с 6 символами, у вас есть много пространства имен для работы.
Функция, основанная на классе Xeoncross
function shortly($input){
$dictionary = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','0','1','2','3','4','5','6','7','8','9'];
if($input===0)
return $dictionary[0];
$base = count($dictionary);
if(is_numeric($input)){
$result = [];
while($input > 0){
$result[] = $dictionary[($input % $base)];
$input = floor($input / $base);
}
return join("", array_reverse($result));
}
$i = 0;
$input = str_split($input);
foreach($input as $char){
$pos = array_search($char, $dictionary);
$i = $i * $base + $pos;
}
return $i;
}
Мой подход: возьмите идентификатор базы данных, затем Base36 закодируйте его . Я бы не использовал буквы верхнего и нижнего регистров, потому что это делает передачу этих URL по телефону кошмаром, но вы, конечно, можете легко расширить функцию, чтобы быть базовым 62 en / decoder.
alphabet = map(chr, range(97,123)+range(65,91)) + map(str,range(0,10))
def lookup(k, a=alphabet):
if type(k) == int:
return a[k]
elif type(k) == str:
return a.index(k)
def encode(i, a=alphabet):
'''Takes an integer and returns it in the given base with mappings for upper/lower case letters and numbers 0-9.'''
try:
i = int(i)
except Exception:
raise TypeError("Input must be an integer.")
def incode(i=i, p=1, a=a):
# Here to protect p.
if i <= 61:
return lookup(i)
else:
pval = pow(62,p)
nval = i/pval
remainder = i % pval
if nval <= 61:
return lookup(nval) + incode(i % pval)
else:
return incode(i, p+1)
return incode()
def decode(s, a=alphabet):
'''Takes a base 62 string in our alphabet and returns it in base10.'''
try:
s = str(s)
except Exception:
raise TypeError("Input must be a string.")
return sum([lookup(i) * pow(62,p) for p,i in enumerate(list(reversed(s)))])a
Вот моя версия для тех, кому она нужна.
// simple approach
$original_id = 56789;
$shortened_id = base_convert($original_id, 10, 36);
$un_shortened_id = base_convert($shortened_id, 36, 10);
Не знаю, найдет ли кто-нибудь это полезное - это скорее метод «hack n slash», но он прост и работает хорошо, если вы хотите только определенные символы.
$dictionary = "abcdfghjklmnpqrstvwxyz23456789";
$dictionary = str_split($dictionary);
// Encode
$str_id = '';
$base = count($dictionary);
while($id > 0) {
$rem = $id % $base;
$id = ($id - $rem) / $base;
$str_id .= $dictionary[$rem];
}
// Decode
$id_ar = str_split($str_id);
$id = 0;
for($i = count($id_ar); $i > 0; $i--) {
$id += array_search($id_ar[$i-1], $dictionary) * pow($base, $i - 1);
}
Почему вы хотите использовать хэш? Вы можете просто использовать простой перевод вашего значения автоинкремента в буквенно-цифровое значение. Вы можете сделать это легко, используя базовое преобразование. Скажем, пространство символов (A-Z, a-z, 0-9 и т. Д.) Содержит 40 символов, преобразует идентификатор в номер базы 40 и использует символы - цифры.
Вот достойная функция кодирования URL для PHP ...
// From http://snipplr.com/view/22246/base62-encode--decode/
private function base_encode($val, $base=62, $chars='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ') {
$str = '';
do {
$i = fmod($val, $base);
$str = $chars[$i] . $str;
$val = ($val - $i) / $base;
} while($val > 0);
return $str;
}
опустил ли я O, 0, i?
Просто создал php-класс, основанный на решении Райана.
<?php
$shorty = new App_Shorty();
echo 'ID: ' . 1000;
echo '<br/> Short link: ' . $shorty->encode(1000);
echo '<br/> Decoded Short Link: ' . $shorty->decode($shorty->encode(1000));
/**
* A nice shorting class based on Ryan Charmley's suggestion see the link on stackoverflow below.
* @author Svetoslav Marinov (Slavi) | http://WebWeb.ca
* @see http://stackoverflow.com/questions/742013/how-to-code-a-url-shortener/10386945#10386945
*/
class App_Shorty {
/**
* Explicitely omitted: i, o, 1, 0 because they are confusing. Also use only lowercase ... as
* dictating this over the phone might be tough.
* @var string
*/
private $dictionary = "abcdfghjklmnpqrstvwxyz23456789";
private $dictionary_array = array();
public function __construct() {
$this->dictionary_array = str_split($this->dictionary);
}
/**
* Gets ID and converts it into a string.
* @param int $id
*/
public function encode($id) {
$str_id = '';
$base = count($this->dictionary_array);
while ($id > 0) {
$rem = $id % $base;
$id = ($id - $rem) / $base;
$str_id .= $this->dictionary_array[$rem];
}
return $str_id;
}
/**
* Converts /abc into an integer ID
* @param string
* @return int $id
*/
public function decode($str_id) {
$id = 0;
$id_ar = str_split($str_id);
$base = count($this->dictionary_array);
for ($i = count($id_ar); $i > 0; $i--) {
$id += array_search($id_ar[$i - 1], $this->dictionary_array) * pow($base, $i - 1);
}
return $id;
}
}
?>
Версия 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;
}
}
Моя версия python3
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")
Вот мой класс 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;
}
}
3792586=='F_ck'
с u вместо _). Я бы исключил некоторые символы, такие как u / U, чтобы свести это к минимуму. – Paulo Scardine 28 June 2013 в 17:02