[algorithm] URL 단축기를 어떻게 만듭니 까?

입력 필드에 긴 URL을 쓸 수 있고 URL이 ” http://www.example.org/abcdef“(으)로 단축되는 URL 단축기 서비스를 만들고 싶습니다 .

” abcdef” 대신 6자를 포함하는 다른 문자열이있을 수 있습니다 a-z, A-Z and 0-9. 이는 56 ~ 57 십억 개의 문자열을 가능하게합니다.

내 접근 방식 :

세 개의 열이있는 데이터베이스 테이블이 있습니다.

id, 정수, 자동 증가
long, string, 사용자가 입력 한 긴 URL
short, string, 단축 URL (또는 6 자)

그런 다음 긴 URL을 테이블에 삽입합니다. 그런 다음 ” id“에 대해 자동 증분 값을 선택하고 해시를 작성합니다. 이 해시는 ” short” 로 삽입되어야합니다 . 그러나 어떤 종류의 해시를 만들어야합니까? MD5와 같은 해시 알고리즘은 너무 긴 문자열을 만듭니다. 나는이 알고리즘들을 사용하지 않는다고 생각한다. 자체 빌드 알고리즘도 작동합니다.

내 생각:

” http://www.google.de/“의 경우 자동 증가 ID를 얻습니다 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.

숫자를 더 이상 나눌 수 없을 때까지 반복 할 수 있습니다. 이것이 좋은 접근 방법이라고 생각하십니까? 더 좋은 아이디어가 있습니까?

_{이 주제에 대한 지속적인 관심으로 인해 JavaScript , PHP , Python 및 Java 를 구현 하는 GitHub에 대한 효율적인 솔루션을 발표했습니다 . 원하는 경우 솔루션을 추가하십시오 🙂}

답변

“숫자를 문자열로 변환”접근 방식을 계속합니다. 그러나 ID가 소수이고 52보다 크면 제안 된 알고리즘이 실패 함을 알 수 있습니다 .

이론적 배경

Bijective 기능 이 필요합니다 . f . f (123) = ‘abc’ 함수에 대해 역함수 g ( ‘abc’) = 123 을 찾을 수 있어야 합니다. 이것은 다음을 의미합니다.

f (x1) = f (x2)를 만드는 x1, x2 (x1 ≠ x2 포함) 가 없어야합니다 .
모든 y에 대해 f (x) = y가 되도록 x 를 찾을 수 있어야합니다 .

ID를 단축 URL로 변환하는 방법

우리가 사용하고자하는 알파벳을 생각하십시오. 귀하의 경우에는입니다 [a-zA-Z0-9]. 그것은 62 글자를 포함 합니다 .
자동 생성 된 고유 한 숫자 키 ( id예 : MySQL 테이블 의 자동 증분) 를 가져옵니다 .

이 예에서는 125 ₁₀ (기본은 10 인 125)을 사용합니다.
이제 125 ₁₀ 을 X ₆₂ (기본 62) 로 변환해야합니다 .

125 ₁₀ = 2 × 62 ¹ + 1 × 62 ⁰ =[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를 사용하면 단축 URL로 cb ₆₂ 가 수신됩니다 .
```
http://shor.ty/cb
```

단축 된 URL을 초기 ID로 해결하는 방법

그 반대가 더 쉽습니다. 당신은 당신의 알파벳에서 역방향 조회를 수행합니다.

e9a ₆₂ 는 “알파벳의 4 번째, 61 번째 및 0 번째 문자”로 해석됩니다.

e9a ₆₂ = [4,61,0]= 4 × 62 ² + 61 × 62 ¹ + 0 × 62 ⁰ = 19158 ₁₀
이제 데이터베이스 레코드를 찾아 WHERE id = 19158리디렉션을 수행하십시오.

구현 예 (코멘트 작성자가 제공)

답변

왜 해시를 사용하고 싶습니까?

자동 증분 값을 영숫자 값으로 간단히 변환하면됩니다. 기본 변환을 사용하면 쉽게 할 수 있습니다. 문자 공간 (AZ, az, 0-9 등)에 40자가 있다고 가정하고 ID를 기본 40 숫자로 변환하고 문자를 숫자로 사용하십시오.

답변

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;
    }
}

답변

귀하의 질문에 대한 답변은 아니지만 대소 문자를 구분하는 단축 URL을 사용하지 않습니다. 그것들은 기억하기 어렵고, 일반적으로 읽을 수 없습니다 (많은 글꼴은 1과 l, 0과 O와 다른 문자는 매우 유사하여 차이를 말하기가 거의 불가능합니다). 그리고 명백한 오류가 발생하기 쉽습니다. 소문자 또는 대문자 만 사용하십시오.

또한 미리 정의 된 형식으로 숫자와 문자를 혼합하는 형식을 사용하십시오. 사람들이 다른 형태보다 한 형태를 더 잘 기억하는 경향이 있다는 연구 결과가 있습니다 (전화 번호는 특정 형태로 그룹화되어 있다고 생각하십시오). num-char-char-num-char-char와 같은 것을 시도하십시오. 대문자와 소문자가없는 경우 조합이 낮아질 것이라는 것을 알고 있지만 더 유용하고 유용 할 것입니다.

답변

내 접근 방식 : 데이터베이스 ID를 취한 다음 Base36 인코딩하십시오 . 대문자와 소문자를 모두 사용하지 않을 것입니다. 전화로 URL을 전송하는 것은 악몽이지만, 물론 함수를 기본 62 en / decoder로 쉽게 확장 할 수 있기 때문입니다.

답변

다음은 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;
    }
}

답변

Node.js 및 MongoDB 솔루션

MongoDB가 12 바이트의 새 ObjectId를 작성하는 데 사용하는 형식을 알고 있기 때문에.

유닉스 시대 이후 초를 나타내는 4 바이트 값
3 바이트 머신 식별자
2 바이트 프로세스 ID
컴퓨터에서 임의의 값으로 시작하는 3 바이트 카운터

예 (임의의 순서를 선택합니다)
a1b2c3d4e5f6g7h8i9j1k2l3

a1b2c3d4는 유닉스 시대 이후의 초를 나타냅니다.
4e5f6g7은 기계 식별자를 나타냅니다.
h8i9는 프로세스 ID를 나타냅니다.
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");
    })
});